Edit Distance for OCR Correction

mediumPRODynamic ProgrammingDynamic Programming, StringCV - DSA

Problem Statement

In Optical Character Recognition (OCR), text extracted from images often contains errors. Edit Distance (Levenshtein Distance) measures how different two strings are, which helps in:

Spell checking OCR output
Finding the closest dictionary word
Post-processing recognized text

Given two strings source and target, find the minimum number of operations required to convert source to target. The allowed operations are:

Insert a character
Delete a character
Replace a character

Constraints

$0 \leq len(source), len(target) \leq 500$
Strings contain lowercase English letters only

Example

Input

source = "kitten", target = "sitting"

Output

Reasoning

Inputs: source is the OCR reading "kitten" (6 letters) and target is the intended word "sitting" (7 letters). Each insert, delete or replace costs exactly 1.
Line the words up: k/s, i/i, t/t, t/t, e/i, n/n, and "sitting" has one extra g at the end. Four positions already agree and cost nothing.
Count the edits: replace k with s (sitten), replace e with i (sittin), insert g (sitting). That is $1 + 1 + 1 = 3$ operations.
Why not fewer? The lengths differ by $7 - 6 = 1$ , so at least one insertion is unavoidable. Even after it, the letters k and e have no matching letter in the right place of "sitting", and each mismatch needs its own edit. So 3 is the minimum, and the output is 3.
Notice: the answer is a single non-negative integer, never larger than the longer string's length. Identical strings give 0. If one string is empty, the answer is just the other string's length (an empty string to "abc" needs 3 inserts).

Learn this in

Dynamic Programming AdvancedDSA Study Plan Introduction to Vision-Language ModelsVLM Study Plan

More from CV - DSA

Concept primerPREVIEW

Edit Distance for OCR Correction: Comprehensive Background

1. Background Knowledge

Edit Distance (Levenshtein Distance) quantifies the minimum number of single-character insertions, deletions, or substitutions needed to transform one string into another. Each operation costs 1, making it ideal for OCR error correction where scanned text has substitution errors (e.g., 'o'→'0'), insertions, or deletions.

Key prerequisites:

Dynamic Programming (DP): Solves overlapping subproblems by building solutions bottom-up.
String alignment: Measures similarity via transformations, used in spell-checking, bioinformatics, and plagiarism detection.
OCR context: Errors arise from image noise; edit distance finds closest dictionary words efficiently.

Mathematical definition: For strings $S$ (length $m$ ) and $T$ (length $n$ ), distance $d(S, T)$ satisfies the triangle inequality and is a metric on strings.

2. Algorithm Approach

The standard approach is a 2D Dynamic Programming table $dp[i][j]$ , where $dp[i][j]$ = minimum operations to convert $S[0..i)$ to $T[0..j)$ .

Recurrence relation:

dp[i][j] = \begin{cases} 0 & \text{if } i=0, j=0 \\ i & \text{if } j=0 \quad (\text{delete } i \text{ chars}) \\ j & \text{if } i=0 \quad (\text{insert } j \text{ chars}) \\ dp[i-1][j-1] & \text{if } S[i-1] = T[j-1] \quad (\text{match}) \\ 1 + \min\begin{cases} dp[i-1][j] & \text{(delete)} \\ dp[i][j-1] & \text{(insert)} \\ dp[i-1][j-1] & \text{(substitute)} \end{cases} & \text{otherwise} \end{cases}

Initialization: $dp[j] = j$ , $dp[i] = i$ .

Result: $dp[m][n]$ .

Variants like Damerau-Levenshtein add transpositions (swap adjacent chars), but standard Levenshtein suffices here.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results