Back to String Processing Dsa

Myers Bit-Vector Edit Distance

September 17, 2026 Wasil Zafar 9 min read

Packing an edit-distance frontier into machine-word operations

Table of Contents

  1. From DP Columns to Bit Vectors
  2. Pattern Equality Masks
  3. The Update Equations
  4. Implementation and Extensions

From DP Columns to Bit Vectors

For pattern $P$ of length $m$ and text prefix $T[0\dots j)$, let $D[i,j]$ be the Levenshtein distance between $P[0\dots i)$ and $T[0\dots j)$. Adjacent vertical values differ by only $-1$, $0$, or $+1$. Myers’ algorithm stores these differences instead of all $m+1$ cells: bit $i$ of $VP$ marks a $+1$ step, bit $i$ of $VN$ marks a $-1$ step, and an unset bit in both represents zero. A scalar score retains the bottom cell $D[m,j]$.

Initially $D[i,0]=i$, so $VP=2^m-1$, $VN=0$, and the score is $m$. For approximate substring matching, set the top-row boundary to $D[0,j]=0$: this is implemented by shifting a zero, rather than a one, into $P_H$. After consuming $T[j]$, the score is the minimum distance between $P$ and a substring ending at $j$. Thus one machine-word update advances an entire DP frontier.

Mapping an edit-distance column to VP and VN bit vectors For pattern GAT after reading G with a free-start boundary, column values zero, zero, one, two yield VN 000 and VP 110. Pattern P = GAT, current text prefix = G DP column ε G A T 00 12 Vertical differences 0 − 0 = 01 − 0 = +12 − 1 = +1 Bit 2 · Bit 1 · Bit 0 VP = 1 1 0 VN = 0 0 0 bottom score = D[3,1] = 2 The two masks plus the bottom score reconstruct the entire column.

Pattern Equality Masks

Preprocessing constructs one equality mask $Eq[c]$ per pattern symbol. Bit $i$ is set precisely when $P[i]=c$:

$$ Eq[c]=\bigvee_{\{i:P[i]=c\}}2^i. $$

For $P=\texttt{GAT}$, $Eq[G]=001_2$, $Eq[A]=010_2$, and $Eq[T]=100_2$. One lookup therefore identifies every pattern position matching the next text symbol. The alphabet changes only how masks are stored. Dense arrays suit small encoded alphabets, while dictionaries store only symbols present in a large or sparse pattern.

Unicode requires an explicit symbol contract. Code-point matching works naturally with dictionary keys, but canonically equivalent spellings compare differently unless normalized. If the application means user-perceived characters, segment both inputs into grapheme clusters using the same Unicode version before constructing masks.

Alphabet modelMask representationPreprocessingLookupMemoryImportant constraint
DNA or tiny fixed alphabetDense array indexed by encoded symbol$O(m+\lvert\Sigma\rvert)$$O(1)$ worst-case$O(\lvert\Sigma\rvert)$ wordsDefine behavior for ambiguous symbols such as N
BytesArray of 256 masks$O(m+256)$$O(1)$ worst-case256 wordsOperates on encoded bytes, not Unicode characters
ASCIIArray of 128 masks$O(m+128)$$O(1)$ worst-case128 wordsReject or separately handle non-ASCII input
Large sparse alphabetHash map from symbol to mask$O(m)$ expected$O(1)$ expected$O(\min(m,\lvert\Sigma\rvert))$ wordsMissing keys must return the zero mask
Ordered static alphabetSorted (symbol, mask) pairs$O(m+\sigma_P\log\sigma_P)$$O(\log\sigma_P)$$O(\sigma_P)$ wordsDeterministic lookup; $\sigma_P$ counts pattern symbols
Unicode code pointsHash map keyed by code point$O(m)$ expected$O(1)$ expected$O(\sigma_P)$ wordsNormalize if canonical equivalence matters
Unicode grapheme clustersSegment, then hash cluster strings$O(m)$ after segmentation$O(1)$ expected$O(\sigma_P)$ variable-size keysFix normalization and segmentation semantics

The Update Equations

Let $VP$ and $VN$ encode the current column, and let $Eq$ be the equality mask for the next text symbol. For an $m$-bit mask, compute

$$ \begin{aligned} X_V &= Eq\lor VN,\\ X_H &= (((Eq\land VP)+VP)\oplus VP)\lor Eq,\\ P_H &= VN\lor\neg(X_H\lor VP),\\ M_H &= VP\land X_H. \end{aligned} $$

Before shifting, the highest pattern bit changes the bottom score: increment when it is set in $P_H$, and decrement when it is set in $M_H$. Then update

$$ \begin{aligned} P_H &\leftarrow(P_H\ll1)\lor b, & M_H&\leftarrow M_H\ll1,\\ VP'&=M_H\lor\neg(X_V\lor P_H), & VN'&=P_H\land X_V. \end{aligned} $$

Here $b=1$ gives global prefix alignment, while $b=0$ gives the free-start boundary used for approximate substring search. Complements and shifts must be restricted to the lowest $m$ bits when integers are unbounded or unused high bits could contaminate later operations.

Bit Trace

One Myers Step

Use pattern GAT, assigning bit 0 to G, bit 1 to A, and bit 2 to T. Initially $VP=111_2$, $VN=000_2$, and the score is 3. Process G, whose equality mask is $Eq=001_2$.

  1. $X_V=001\lor000=001$.
  2. $X_H=(((001\land111)+111)\oplus111)\lor001=111$ after retaining three bits.
  3. $P_H=000\lor\neg(111\lor111)=000$ within three bits.
  4. $M_H=111\land111=111$.
  5. The high bit 100 is set in $M_H$, so the score falls from 3 to 2.
  6. For free-start search, shift in zero: $P_H=000\ll1=000$ and $M_H=(111\ll1)\land111=110$.
  7. $VP'=110\lor\neg(001\lor000)=110$ and $VN'=000\land001=000$.

The encoded differences are $(0,+1,+1)$, reconstructing the free-start column $[0,0,1,2]$. Its bottom value 2 is the best distance between GAT and a substring ending at this G.

Implementation and Extensions

When $m\le w$, each text symbol costs a constant number of $w$-bit operations, giving $O(m+n)$ preprocessing and scanning time. Native implementations should use unsigned words and mask complements. When $m>w$, store each vector in $\lceil m/w\rceil$ blocks and propagate addition and shift carries between blocks, yielding $O(n\lceil m/w\rceil)$ time.

Python integers already provide multiword arithmetic, so the same recurrence works for long patterns, although its cost grows with the number of internal limbs. The bounded mode below rejects patterns exceeding a specified word width; the unbounded mode is a compact multiword reference. Search results contain inclusive endpoints and scores. Recovering starts or edit scripts requires verification or additional traceback state.

from collections.abc import Hashable, Iterable, Sequence
from typing import TypeVar

Symbol = TypeVar("Symbol", bound=Hashable)


def equality_masks(pattern: Sequence[Symbol]) -> dict[Symbol, int]:
    """Map each pattern symbol to the bitset of positions containing it."""
    masks: dict[Symbol, int] = {}
    for position, symbol in enumerate(pattern):
        masks[symbol] = masks.get(symbol, 0) | (1 << position)
    return masks


def myers_endpoint_scores(
    pattern: Sequence[Symbol],
    text: Iterable[Symbol],
    *,
    word_bits: int | None = None,
) -> list[int]:
    """Return the best edit distance for a match ending at each text position."""
    m = len(pattern)
    symbols = list(text)
    if m == 0:
        return [0] * len(symbols)
    if word_bits is not None:
        if word_bits <= 0:
            raise ValueError("word_bits must be positive")
        if m > word_bits:
            raise ValueError(f"pattern length {m} exceeds {word_bits}-bit limit")

    peq = equality_masks(pattern)
    active_mask = (1 << m) - 1
    high_bit = 1 << (m - 1)
    vp, vn, score = active_mask, 0, m
    scores: list[int] = []

    for symbol in symbols:
        eq = peq.get(symbol, 0)
        xv = eq | vn
        xh = ((((eq & vp) + vp) ^ vp) | eq) & active_mask
        ph = (vn | ~(xh | vp)) & active_mask
        mh = vp & xh

        if ph & high_bit:
            score += 1
        elif mh & high_bit:
            score -= 1

        # Shift in zero so D[0,j] remains zero: text prefixes may be skipped.
        ph = (ph << 1) & active_mask
        mh = (mh << 1) & active_mask
        vp = (mh | ~(xv | ph)) & active_mask
        vn = ph & xv
        scores.append(score)

    return scores


def myers_search(
    pattern: Sequence[Symbol],
    text: Sequence[Symbol],
    max_distance: int,
    *,
    word_bits: int | None = None,
) -> list[tuple[int, int]]:
    """Return inclusive text endpoints and scores for matches within k edits."""
    if max_distance < 0:
        raise ValueError("max_distance must be non-negative")
    if len(pattern) == 0:
        return [(end, 0) for end in range(-1, len(text))]
    return [
        (end, score)
        for end, score in enumerate(
            myers_endpoint_scores(pattern, text, word_bits=word_bits)
        )
        if score <= max_distance
    ]


def substring_oracle(pattern: str, text: str, end: int) -> int:
    """Slow oracle: best distance to any non-empty substring ending at end."""
    def distance(a: str, b: str) -> int:
        previous = list(range(len(b) + 1))
        for row, left in enumerate(a, 1):
            current = [row]
            for column, right in enumerate(b, 1):
                current.append(min(
                    previous[column] + 1,
                    current[column - 1] + 1,
                    previous[column - 1] + (left != right),
                ))
            previous = current
        return previous[-1]
    return min(distance(pattern, text[start:end + 1]) for start in range(end + 1))


if __name__ == "__main__":
    assert equality_masks("GAT") == {"G": 0b001, "A": 0b010, "T": 0b100}
    assert myers_endpoint_scores("GAT", "G", word_bits=64) == [2]

    for pattern, text in [
        ("kitten", "xxsitting kitten"),
        ("GAT", "CGATT"),
        ("café", "xxcafe café"),
    ]:
        scores = myers_endpoint_scores(pattern, text)
        assert scores == [substring_oracle(pattern, text, end) for end in range(len(text))]

    matches = myers_search("kitten", "xxsitting kitten", 2, word_bits=64)
    assert (7, 2) in matches
    assert (15, 0) in matches

    long_pattern = "a" * 130
    assert myers_endpoint_scores(long_pattern, long_pattern)[-1] == 0
    try:
        myers_endpoint_scores(long_pattern, long_pattern, word_bits=64)
    except ValueError:
        pass
    else:
        raise AssertionError("bounded mode must reject an oversized pattern")