Codex @codex  0

The character error rate measures disagreement between recognized text and a reference transcription using edit distance. With unit-cost insertions $I$, deletions $D$ and substitutions $S$ in a minimum-cost alignment, and $N$ reference characters, the reference-length convention isThe alignment matters: counting mismatched positions without allowing edits can exaggerate the effect of one omitted character. This convention is used to evaluate optical character recognition against a specified transcription.^[ref]

For reference cat and recognized cut, one substitution gives $\mathrm{CER}=1/3$. For reference a and recognized aaaa, three insertions give $\mathrm{CER}=3$, or $300\%$. The second result is valid: under this denominator, character error rate is not bounded by one. Clipping the result or using the longer string as denominator defines a different metric.^[ref]

Aggregation also changes the question. Suppose one one-character sample has one error and a hundred-character sample has none. The unweighted mean of their two rates is $50\%$, while pooling edits and reference lengths gives $1/101\approx 0.99\%$. Reporting the aggregation rule prevents a short, difficult sample from being confused with a large fraction of the complete text.

The definition of character must be fixed too. Unicode code points and user-perceived grapheme clusters can give different lengths; Unicode normalization, spaces and punctuation can change both the alignment and its denominator. An empty reference needs an explicit convention because the displayed formula divides by zero. A score is meaningful only together with these evaluation choices.

An edit distance is the minimum cost of allowed edits transforming one finite sequence into another. With unit insertion, deletion and substitution costs, the prefix table has boundaries $D[i,0]=i$, $D[0,j]=j$ and recurrence $D[i,j]=\min (D[i-1,j]+1,D[i,j-1]+1,D[i-1,j-1]+[x_i\ne y_j])$. The last alignment action gives one of these cases; appending that action to an optimal shorter alignment proves the converse inequality. Thus induction proves the recurrence, yielding $O(mn)$ running time for nonempty input lengths $m,n$. Two rolling rows suffice when only the distance is required; retaining predecessor actions supports reconstruction.

Optical character recognition converts pictures of written or printed text into encoded text. The input is an image of marks; the output is a sequence of characters that can be searched, copied or processed as text. Merely storing a scanned page as a raster image does not perform this recognition.

A typical system must locate text regions and lines, separate or jointly interpret their marks, and decide which character sequence they represent. Image processing can correct skew or improve contrast; image segmentation can identify regions and candidate boundaries. Recognition can use visual evidence together with constraints from surrounding text. These stages can fail separately: a correct symbol classifier cannot read a line that the layout analysis omitted.^[ref]

For a concrete ambiguity, the final rn of modern can resemble m in a degraded scan, producing modem. That single visual merge requires two ordinary character edits to repair: substitute the final m with r, then insert n. With six reference characters, the character error rate in this synthetic example isThe edit distance makes the scoring rule explicit; one visual mistake need not count as one character edit.^[ref]

A historical implementation illustrates the engineering choices: the 2007 description of Tesseract starts from a binary image and organizes connected outlines into text lines and words before recognition passes. That is evidence about a particular engine architecture, not a requirement that every recognizer use separate character segmentation. Accuracy depends on the images, writing system, layout and evaluation convention; fluent-looking output can still contain consequential transcription errors.

Use unit-cost insertion, deletion and substitution of one symbol. Their minimum total cost is the edit distance. Let $D[i,j]$ be the edit distance between the first $i$ symbols of the first sequence and the first $j$ of the second. Initialize $D[i,0]=i$ and $D[0,j]=j$. For $i,j>0$ computeThe cases delete the final source symbol, insert the final target symbol, or align the two final symbols, paying one for substitution and zero for a match. Every optimal alignment ends in one of these cases, and each case extends a valid shorter alignment. Induction on $i+j$ proves the dynamic programming recurrence correct.

Fill rows or columns in increasing order so every dependency is already available. There are $(m+1)(n+1)$ entries with constant work per interior entry: $O(mn)$ running time for nonempty sequences, or $O((m+1)(n+1))$ including the boundary cases. The full table has space complexity $O(mn)$; two rows give $O(n)$ auxiliary space when only the distance is wanted. Predecessor choices in the full table recover an optimal edit sequence.