const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Condensed unigram frequency table (approximate relative counts, enough to illustrate the algorithm)
// Frequencies are scaled integers; real systems use Google Books n-grams or similar corpora.
const WORDS = {
the:8000,be:5000,to:4800,of:4700,and:4600,a:4500,in:4200,that:3800,
have:3500,it:3400,for:3300,not:3000,on:2900,with:2800,he:2700,as:2600,
you:2500,do:2400,at:2300,this:2200,but:2100,his:2000,by:1900,from:1800,
they:1700,we:1600,say:1500,her:1400,she:1300,or:1200,an:1100,will:1000,
my:900,one:850,all:820,would:800,there:780,their:760,what:740,so:720,
up:700,out:680,if:660,about:640,who:620,get:600,which:580,go:560,me:540,
when:520,make:500,can:480,like:460,time:440,no:420,just:400,know:390,
take:380,people:370,into:360,year:350,your:340,good:330,some:320,could:310,
them:300,see:290,other:280,than:270,then:260,now:250,look:240,only:230,
come:220,its:210,over:200,think:190,also:180,back:170,after:160,use:155,
two:150,how:145,our:140,work:135,first:130,well:125,way:120,even:115,
new:110,want:105,because:100,any:98,these:96,give:94,day:92,most:90,
us:88,great:85,computer:80,science:78,dynamic:75,program:72,programming:70,
choose:68,spain:66,solution:65,quick:63,brown:62,fox:61,jump:60,lazy:59,
dog:58,cat:57,is:56,are:55,was:54,were:53,been:52,has:51,had:50,
does:49,did:48,here:47,where:46,every:45,never:44,always:43,often:42,
while:41,still:40,should:39,each:38,much:37,before:36,between:35,need:34,
large:33,small:32,different:31,long:30,little:29,very:28,own:27,right:26,
big:25,high:24,place:23,world:22,real:21,life:20,few:19,north:18,south:17,
set:16,put:15,end:14,turn:13,show:12,hand:11,play:10,run:9,move:8,live:7,
cut:6,seem:5,ask:4,need:3,form:2,island:1,pen:1,fore:1,speed:1,limit:1
};
// Log-probability of a word: log(freq / total). Unknown words get a tiny fallback so the algorithm can still split.
const TOTAL = Object.values(WORDS).reduce((a,b)=>a+b,0);
const logP = w => Math.log((WORDS[w] || 0.1) / TOTAL);
const NEG_INF = -1e9;
// Viterbi DP: score[i] = best log-probability for s[0..i-1]; back[i] = start of last word.
function viterbi(s) {
const n = s.length;
const score = new Array(n+1).fill(NEG_INF);
const back = new Array(n+1).fill(-1);
score[0] = 0;
const MAX_W = 20;
for (let i = 1; i <= n; i++) {
for (let k = 1; k <= Math.min(i, MAX_W); k++) {
const word = s.slice(i-k, i);
if (WORDS[word] !== undefined) {
const candidate = score[i-k] + logP(word);
if (candidate > score[i]) { score[i] = candidate; back[i] = i-k; }
}
}
}
// Backtrack from n to reconstruct the best word sequence.
if (score[n] === NEG_INF) return null;
const words = [];
let pos = n;
while (pos > 0) { words.unshift(s.slice(back[pos], pos)); pos = back[pos]; }
return { words, score: score[n] };
}
function segment() {
const raw = document.getElementById('txt').value.trim().toLowerCase().replace(/\s+/g,'');
const box = document.getElementById('result-box');
const wDiv = document.getElementById('result-words');
const sDiv = document.getElementById('result-score');
if (!raw) { box.classList.add('hidden'); return; }
const res = viterbi(raw);
box.classList.remove('hidden');
if (!res) {
wDiv.innerHTML = '<span class="no-split">No known-word segmentation found for this input.</span>';
sDiv.textContent = '';
return;
}
wDiv.innerHTML = res.words.map(w => `<span class="word-chip">${w}</span>`).join('');
const nBits = (-res.score / Math.LN2).toFixed(1);
sDiv.textContent = i18nFmt('%n% word(s) · cost %b% bits', { n: res.words.length, b: nBits });
}
document.getElementById('btn-segment').addEventListener('click', segment);
document.getElementById('txt').addEventListener('keydown', e => { if (e.key === 'Enter') segment(); });
// Example buttons: fill the input and run segmentation immediately.
document.querySelectorAll('.ex-btn').forEach(btn => {
btn.addEventListener('click', () => {
document.getElementById('txt').value = btn.dataset.val;
segment();
});
});
Comments
Loading comments...