Word Segmentation

Type the URL choosespain.com into a browser and you read it instantly as choose spain. Your brain did something remarkable: it split a run of twenty characters into two words with no spaces as a guide. Computers cannot rely on intuition — they need an algorithm.

The same challenge appears everywhere modern language meets machines. Chinese and Japanese have no spaces between words. Hashtags on social media pack whole phrases into one token: #nowthatcherisdead was famously ambiguous. Search engines must decide whether penisland is a pen store or an island. Even gene names and product codes routinely mash words together.

The problem is called word segmentation: given a string of characters with no word boundaries marked, find the split that makes the most linguistic sense. A greedy "take the longest word you can" strategy sounds reasonable, but it fails on cases like thereisnosolution — the greedy approach might lock in there and then struggle with isnosolution, missing the natural cut there is no solution.

The right tool is dynamic programming — specifically, a clean instance of the Viterbi algorithm. Instead of trying every possible split ($2^{n-1}$ possibilities for a string of $n$ characters), it builds the best segmentation one character at a time, reusing sub-results, and finishes in $O(n \cdot W)$ time where $W$ is the maximum word length considered.

Type any run-on English text (no spaces) in the box below. The Viterbi algorithm will split it into the most probable word sequence, scored by log-probability from a small built-in word list.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="input-row">
  <input id="txt" type="text" placeholder="{{placeholder}}" spellcheck="false" autocomplete="off" />
  <button id="btn-segment" type="button">{{btn_segment}}</button>
</div>
<div id="result-box" class="result-box hidden">
  <div id="result-words" class="result-words"></div>
  <div id="result-score" class="result-score"></div>
</div>
<div class="examples-label">{{examples_label}}</div>
<div class="examples">
  <button class="ex-btn" type="button" data-val="choosespain">choosespain</button>
  <button class="ex-btn" type="button" data-val="thereisnosolution">thereisnosolution</button>
  <button class="ex-btn" type="button" data-val="thequickbrownfox">thequickbrownfox</button>
  <button class="ex-btn" type="button" data-val="computerscienceisgreat">computerscienceisgreat</button>
  <button class="ex-btn" type="button" data-val="dynamicprogramming">dynamicprogramming</button>
</div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.input-row { display: flex; gap: .5rem; margin-bottom: .8rem; }
#txt { flex: 1; font: 14px ui-monospace, monospace; padding: .45rem .7rem;
       border: 1px solid #adb1b8; border-radius: 8px; outline: none; }
#txt:focus { border-color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; white-space: nowrap; }
button:hover { background: #163048; }
/* {{c_result_styles}} */
.result-box { border: 1px solid #cdd9e3; border-radius: 10px; padding: .8rem 1rem;
              margin-bottom: .8rem; background: #f4f7fa; }
.result-box.hidden { display: none; }
.result-words { display: flex; flex-wrap: wrap; gap: .35rem; margin-bottom: .45rem; }
.word-chip { background: #1d3557; color: #fff; border-radius: 6px;
             padding: .25rem .55rem; font: 600 13px ui-monospace, monospace; }
.result-score { font-size: .82rem; color: #555; }
/* {{c_example_styles}} */
.examples-label { font-size: .8rem; color: #666; margin-bottom: .35rem; }
.examples { display: flex; flex-wrap: wrap; gap: .4rem; }
.ex-btn { background: #e8eef3; color: #1d3557; border-color: #cdd9e3;
          font: 500 12px ui-monospace, monospace; padding: .3rem .6rem; }
.ex-btn:hover { background: #d4dde6; }
.no-split { color: #c92f3c; font-style: italic; font-size: .92rem; }

// Code not found

Notice that the algorithm does not always take the longest possible word. It weighs the probability of the whole sequence — so there + fore beats the + refore even though refore is not a word at all. Common words like the, is, and a carry high probability; unknown fragments are penalized heavily.

How hard is word segmentation without the Viterbi trick?

• Brute force considers every way to insert word boundaries into a string of $n$ characters: that is $2^{n-1}$ splits. For a 30-character string that is already more than half a billion candidates.

• The Viterbi insight: the best segmentation of the prefix $s[0..i]$ depends only on the best segmentations of shorter prefixes — not on how future characters will be split. This optimal substructure lets us write the recurrence

  $$\text{score}[i] = \max_{1 \le k \le W,\; s[i-k..i] \in \text{vocab}} \bigl(\text{score}[i-k] + \log P(w)\bigr)$$

  where $P(w)$ is the unigram probability of word $w = s[i-k..i]$.

• Complexity: we compute $\text{score}[i]$ for each of the $n$ positions, checking at most $W$ candidate last-word lengths. Total work: $O(n \cdot W)$ — linear in practice since $W$ is bounded (longest English word is around 20 characters).

• Solved, not hard: word segmentation is in polynomial time. It is not NP-complete. The exponential explosion is entirely avoided by dynamic programming, in the same spirit as the dynamic programming family of algorithms.

• Probabilistic models matter: a purely Boolean "is this a word?" vocabulary gives the correct splits most of the time, but using log-probabilities from a frequency corpus (like Google Books n-grams) handles ambiguity far better — choosing there + in + after over there + in + a + fter because after is common and fter is not.

Separating words from a stream of characters is one of the oldest preprocessing steps in computing:

• Chinese and Japanese NLP: neither language uses spaces. Every downstream task — machine translation, sentiment analysis, named-entity recognition — depends on a fast, accurate segmenter running on every sentence.
• Search-engine query parsing: users type javascript tutorial, but they also type javascripttutorial or java script tutorial. A search engine must normalize all three before matching.
• URL disambiguation: human-readable slugs like penisland.net or choosespain.com require a segmenter to surface the intended meaning and filter spam.
• Hashtag and username parsing: #nowthatcherisdead and #SuperBowl are social-media staples that need splitting before sentiment or topic analysis can proceed.
• OCR post-processing: when a scanner misses a space, the Viterbi segmenter can repair the output using language-model evidence.
• Gene and protein annotation: identifiers like BRCA1, p53, or concatenated gene-name strings in databases require the same splitting logic as natural language.

In each case the algorithm is the same: a one-pass dynamic program that trades an exponential search for a linear sweep guided by word probabilities.

Word segmentation looks deceptively simple — just find the right places to insert spaces — yet a naïve search explodes exponentially. The Viterbi algorithm collapses that explosion into a single linear sweep by insisting that the best split of any prefix can be computed from the best splits of smaller prefixes, and never reconsidered.

The algorithm is solved and efficient: $O(n \cdot W)$ with a small constant, fast enough to preprocess billions of web pages or tokenize a live chat stream in real time. What makes it interesting is not computational hardness but probabilistic elegance — the log-probability scoring turns a combinatorial puzzle into a shortest-path problem on a DAG, solved by the same dynamic programming idea that underlies sequence alignment and speech recognition.

The next time you read a URL and instantly parse it into words, remember: your brain is running a variant of Viterbi, and it is doing so in linear time.