Levenshtein distance in Python: keep two rows instead of the whole matrix

Problem. A Levenshtein distance routine compares two strings through an m × n dynamic-programming table. When the caller needs only the final distance, older rows still occupy memory after their values have done their job.

Baseline. The full-table implementation below performs O(mn) cell updates and keeps O(mn) Python list entries alive. That time cost grows with the product of the two input lengths. The storage statement describes this particular Python implementation.

Solution. The rolling-row version calculates the same recurrence while keeping only the previous and current rows. With a right-hand string of length n, it retains O(n) entries. It returns the distance and releases older rows, so it cannot reconstruct an edit script afterwards.

Measured result. In the captured CPython 3.13.5 run, both versions returned distance 270 for two strings of length 512. The full matrix reached 4,746.3 KiB of traced Python allocations; the rolling-row version reached 40.7 KiB. Median times were 0.144222 seconds and 0.142007 seconds respectively, a 1.02x matrix-to-row ratio on this host.

Reproduce the result

Complete code

from __future__ import annotations
import gc
import platform
import random
import sys
import timeit
import tracemalloc
ALPHABET = "abcd"
SEED = 20261014
SIZES = (64, 128, 256, 512)
REPEATS = 5
def levenshtein_matrix(left: str, right: str) -> int:
    """Return edit distance while retaining the complete dynamic-programming table."""
    rows = [list(range(len(right) + 1))]
    for i, left_char in enumerate(left, start=1):
        previous = rows[-1]
        current = [i]
        for j, right_char in enumerate(right, start=1):
            insertion = current[j - 1] + 1
            deletion = previous[j] + 1
            substitution = previous[j - 1] + (left_char != right_char)
            current.append(min(insertion, deletion, substitution))
        rows.append(current)
    return rows[-1][-1]
def levenshtein_row(left: str, right: str) -> int:
    """Return edit distance while retaining only the previous row."""
    previous = list(range(len(right) + 1))
    for i, left_char in enumerate(left, start=1):
        current = [i]
        for j, right_char in enumerate(right, start=1):
            insertion = current[j - 1] + 1
            deletion = previous[j] + 1
            substitution = previous[j - 1] + (left_char != right_char)
            current.append(min(insertion, deletion, substitution))
        previous = current
    return previous[-1]
def make_pair(length: int) -> tuple[str, str]:
    rng = random.Random(SEED + length)
    left = "".join(rng.choice(ALPHABET) for _ in range(length))
    right = "".join(rng.choice(ALPHABET) for _ in range(length))
    return left, right
def timed(function, left: str, right: str) -> list[float]:
    function(left, right)
    timer = timeit.Timer(lambda: function(left, right))
    return timer.repeat(repeat=REPEATS, number=1)
def peak_bytes(function, left: str, right: str) -> tuple[int, int]:
    gc.collect()
    tracemalloc.start()
    result = function(left, right)
    current, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return result, peak
def format_samples(samples: list[float]) -> str:
    return ",".join(f"{sample:.6f}" for sample in samples)
def main() -> None:
    print(f"python={sys.version.split()[0]} platform={platform.platform()} machine={platform.machine()}")
    print(f"seed={SEED} alphabet={ALPHABET} repeats={REPEATS} warmup=1")
    print("checks=empty:0,kitten_sitting:3,full_row_equal:true")
    if levenshtein_matrix("", "") != 0:
        raise AssertionError("empty case")
    if levenshtein_row("kitten", "sitting") != 3:
        raise AssertionError("known case")
    if levenshtein_matrix("", "abc") != 3:
        raise AssertionError("empty-left case")
    for length in SIZES:
        left, right = make_pair(length)
        full_distance = levenshtein_matrix(left, right)
        row_distance = levenshtein_row(left, right)
        if full_distance != row_distance:
            raise AssertionError(f"distance mismatch at n={length}")
        full_samples = timed(levenshtein_matrix, left, right)
        row_samples = timed(levenshtein_row, left, right)
        full_result, full_peak = peak_bytes(levenshtein_matrix, left, right)
        row_result, row_peak = peak_bytes(levenshtein_row, left, right)
        if (full_result, row_result) != (full_distance, row_distance):
            raise AssertionError(f"measured result mismatch at n={length}")
        full_median = sorted(full_samples)[len(full_samples) // 2]
        row_median = sorted(row_samples)[len(row_samples) // 2]
        print(
            f"n={length} distance={full_distance} "
            f"matrix_samples={format_samples(full_samples)} "
            f"row_samples={format_samples(row_samples)} "
            f"matrix_median={full_median:.6f} row_median={row_median:.6f} "
            f"matrix_peak_kib={full_peak / 1024:.1f} row_peak_kib={row_peak / 1024:.1f}"
        )
if __name__ == "__main__":
    main()

Command

python3 levenshtein_benchmark.py

Output

python=3.13.5 platform=Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41 machine=aarch64
seed=20261014 alphabet=abcd repeats=5 warmup=1
checks=empty:0,kitten_sitting:3,full_row_equal:true
n=64 distance=34 matrix_samples=0.001923,0.001860,0.001773,0.001770,0.001807 row_samples=0.001822,0.001769,0.001781,0.002141,0.002976 matrix_median=0.001807 row_median=0.001822 matrix_peak_kib=43.0 row_peak_kib=1.6
n=128 distance=74 matrix_samples=0.007082,0.007056,0.007064,0.007032,0.006993 row_samples=0.007009,0.007017,0.007018,0.007016,0.007014 matrix_median=0.007056 row_median=0.007016 matrix_peak_kib=157.5 row_peak_kib=2.8
n=256 distance=142 matrix_samples=0.029115,0.028785,0.027312,0.027862,0.028389 row_samples=0.027119,0.026192,0.025947,0.027282,0.027178 matrix_median=0.028389 row_median=0.027119 matrix_peak_kib=554.6 row_peak_kib=4.6
n=512 distance=270 matrix_samples=0.142348,0.148445,0.144222,0.144802,0.142980 row_samples=0.142007,0.142254,0.142857,0.141752,0.141597 matrix_median=0.144222 row_median=0.142007 matrix_peak_kib=4746.3 row_peak_kib=40.7

Environment

The captured run used CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8, aarch64, with the Python standard library only. The source prints the runtime and platform before the result rows. No package installation or external data is involved.

Methodology

make_pair() uses a private random.Random instance for each length, with seed 20261014 + length, and draws both strings from the alphabet abcd. The tested lengths are 64, 128, 256 and 512. Input construction happens before timing.

The Python documentation describes independent Random instances that do not share state.^[3] The exact seed arithmetic and alphabet are local properties of this benchmark.

The correctness checks run before timing. They cover an empty pair, kitten versus sitting, an empty left string, and equality between the full-table and rolling-row results for every generated pair.

Each function receives one untimed warm-up call, followed by five timeit.Timer.repeat() samples with one call per sample. The output preserves every sample and the median.

The timeit module uses time.perf_counter() as its default timer and disables garbage collection during timed calls by default.^[1]

The memory probe starts tracemalloc immediately before a fresh function call and records its peak afterwards. Python documents tracemalloc as a tool for tracing Python memory blocks.^[2] The measurement includes allocations made by the function, while imports, string generation, resident-set memory and native allocations remain outside the probe.

Limits of this run

The strings are equal-length pseudo-random sequences over four characters. They are a controlled input, not a production corpus. The timings describe one Linux aarch64 host, one interpreter build and one process state. They are useful for this comparison, not portable conversion factors.

The code measures ordinary Levenshtein edits: insertion, deletion and single-character substitution. Transpositions, weighted edits, Unicode grapheme handling and edit-script reconstruction are separate requirements. The rolling implementation keeps the right-hand dimension, so a production version can swap inputs first when the shorter dimension should bound storage.

tracemalloc reports traced Python allocations under the stated start point. It does not report RSS, allocator arenas or native memory. The benchmark also measures one pair at a time. An index that compares every query with every candidate adds a separate candidate-selection cost.

The problem

For prefixes left[:i] and right[:j], this implementation chooses the cheapest of three moves: delete the next character from the left prefix, insert the next character from the right prefix, or match or substitute the two current characters. The first row and first column contain the cost of creating an empty prefix. The final cell contains the distance between the complete strings.

The recurrence therefore has a rectangular work surface. The storage question is separate: does the implementation need every completed row, or only the row that feeds the next calculation?

Baseline complexity

levenshtein_matrix() stores the initial row in rows. Every outer-loop iteration appends a new list, and every new cell reads from the previous row and the current row. The function returns the bottom-right value, but all earlier rows remain reachable until the function returns.

For strings of lengths m and n, the function evaluates mn interior cells, uses O(mn) table storage and returns one integer. The table is easy to inspect and can be extended to recover a path, but retaining it for a distance-only call is the part this comparison removes.

Solution: retain the boundary between completed work and pending work

levenshtein_row() keeps previous, the completed row for the preceding left-prefix, and builds current, the row for the current prefix. Once the outer loop advances, current becomes previous; older rows have no remaining consumer and can be released.

The recurrence and the input pairs stay unchanged. Only the storage boundary moves. The function still performs mn cell updates, so this version targets memory pressure rather than a better asymptotic time bound. It also returns a score, not the sequence of edits that produced it.

What the measurement shows

The memory gap grows with the string length. At n = 64, the full matrix reached 43.0 KiB and the rolling version 1.6 KiB. At n = 128, the figures were 157.5 KiB and 2.8 KiB. At n = 256, they were 554.6 KiB and 4.6 KiB.

At n = 512, the full matrix reached 4,746.3 KiB while the rolling row reached 40.7 KiB. The full-matrix peak was about 116.6 times the rolling-row peak. Both returned distance 270. The full-table median was 0.144222 seconds and the rolling-row median was 0.142007 seconds. The timing ratio was only 1.02x, so this run shows a large storage change with little timing movement.

The raw samples support the same reading across the four sizes. The benchmark did not count allocations by type, inspect RSS or instrument cache behaviour, so the explanation rests on the retained data structures and the observed peaks. It does not establish a universal speed difference between all matrix and row implementations.

Practical applications

The edit operations are useful when a system needs a bounded similarity score rather than exact string equality. The measured code covers one pair at a time; the applications below add indexing, threshold policy or downstream work that this benchmark does not measure.

• Spelling correction: rank a small candidate set by distance after tokenisation and dictionary lookup. A large dictionary needs candidate generation first, because comparing the query with every word can dominate the distance calculation.

• Duplicate record review: compare short names, identifiers or address fields before sending close pairs to a review queue. Normalisation, field weighting and the chosen threshold affect the result, and the benchmark says nothing about false-match rates.

• OCR and noisy labels: score an extracted label against a known vocabulary before selecting a likely correction. Image recognition, token confidence and candidate retrieval remain outside this string routine.

• Short-field diff prefilters: use the rolling version to reject clearly distant pairs before a richer diff or edit-script reconstruction. The score-only function has discarded the table needed to explain each edit, so a surviving pair needs a second traceback-capable step.

Where it stops helping

Use the rolling rows when the caller needs the distance and memory is the limiting resource. Use a full table when the caller needs direct access to every prefix distance or wants to trace an edit path from the final cell. That choice changes the state retained by the implementation; it does not remove the O(mn) cell work.

For long strings, many candidate pairs or weighted edit rules, measure the complete workload. The 40.7 KiB figure belongs to a 512-character pair and the stated tracing boundary. It is a useful check on this implementation, not a promise about the memory of an entire fuzzy-matching service.

Sources

[1] Python 3.13 timeit documentation

[2] Python 3.13 tracemalloc documentation

[3] Python 3.13 random documentation