Bit-parallel LCS algorithm in Python
Packs DP rows into machine words so LCS runs in about O(nm / w) word operations.
- File
bit_parallel_lcs.py, 36 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bit-parallel-lcs/. The authors are listed in prov/FSVMW5.jsonl.
from collections.abc import Hashable, Sequence
from typing import TypeVar
T = TypeVar("T", bound=Hashable)
def match_masks(x: Sequence[T]) -> dict[T, int]:
"""Return M with bit i - 1 of M[c] set exactly when x[i] == c (1-based i)."""
masks: dict[T, int] = {}
for i, c in enumerate(x): # @line L1
masks[c] = masks.get(c, 0) | (1 << i)
return masks
def bit_parallel_columns(x: Sequence[T], y: Sequence[T]) -> list[int]:
"""Return the words V after each column 0, 1, ..., len(y); a zero bit i - 1 marks a step of the column at row i."""
m = len(x)
full = (1 << m) - 1
masks = match_masks(x)
v = full # @line L2
cols = [v]
for c in y: # @line L3
mk = masks.get(c, 0)
u = v & mk # @line L4
v = ((v + u) | (v & ~mk)) & full # @line L5
cols.append(v)
return cols
def bit_parallel_lcs_length(x: Sequence[T], y: Sequence[T]) -> int:
"""Return the length of a longest common subsequence of x and y."""
v = bit_parallel_columns(x, y)[-1]
return len(x) - bin(v).count("1") # @line L6
test_bit_parallel_lcs.py 55 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bit-parallel-lcs/. The authors are listed in prov/FSVMW5.jsonl.
import random
from bit_parallel_lcs import bit_parallel_columns, bit_parallel_lcs_length, match_masks
def lcs_table(x: str, y: str) -> list[list[int]]:
c = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]
for i in range(1, len(x) + 1):
for j in range(1, len(y) + 1):
if x[i - 1] == y[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
else:
c[i][j] = max(c[i - 1][j], c[i][j - 1])
return c
def test_example() -> None:
x, y = "ABCBDAB", "BDCABA"
assert match_masks(x)["B"] == 0b1001010
cols = bit_parallel_columns(x, y)
assert cols[0] == 0b1111111
assert cols[1] == 0b1111101
assert bit_parallel_lcs_length(x, y) == 4
def test_edges() -> None:
assert bit_parallel_lcs_length("", "") == 0
assert bit_parallel_lcs_length("abc", "") == 0
assert bit_parallel_lcs_length("", "abc") == 0
assert bit_parallel_lcs_length("abc", "xyz") == 0
assert bit_parallel_lcs_length("abc", "abc") == 3
assert bit_parallel_lcs_length("a" * 200, "a" * 150) == 150
def test_columns_match_table() -> None:
rng = random.Random(1986)
for _ in range(500):
x = "".join(rng.choice("ACGT"[: rng.randint(1, 4)]) for _ in range(rng.randrange(20)))
y = "".join(rng.choice("ACGT") for _ in range(rng.randrange(20)))
c = lcs_table(x, y)
for j, v in enumerate(bit_parallel_columns(x, y)):
for i in range(1, len(x) + 1):
step = c[i][j] - c[i - 1][j]
assert ((v >> (i - 1)) & 1) == 1 - step
assert bit_parallel_lcs_length(x, y) == c[len(x)][len(y)]
def test_long_inputs() -> None:
rng = random.Random(7)
x = "".join(rng.choice("ACGT") for _ in range(300))
y = "".join(rng.choice("ACGT") for _ in range(250))
assert bit_parallel_lcs_length(x, y) == lcs_table(x, y)[300][250]
What the next level needs
- the tests did not run in this build