lcs2

lcs2 is a Python package that helps find the longest common—or optimal weighted—subsequence of a pair of sequences and compute their diff. Among all optimal subsequences, it returns the one with the fewest runs (i.e., contiguous segments) across the two sequences.

Installation

pip install lcs2

Reference

The package provides the following functions, where weight[A, B] = Callable[[A, B], int | float].

If the weight function is provided, it should return positive values if and only if the two elements can be matched. If the weight function is omitted, the elements are considered equal if they are identical, and the classical LCS sequence is returned.

Sample Usage

from lcs2 import diff, diff_ranges, lcs, lcs_indices, lcs_length, lcs_weight

a = 'Hello, world!'
b = 'Foobar'

print(lcs(a, b))  # ['o', 'o', 'r']
print(lcs_indices(a, b))  # [(4, 1), (8, 2), (9, 5)]
print(lcs_length(a, b))  # 3

print(diff(a, b))  # [(['H', 'e', 'l', 'l'], ['F']),
                   # ([',', ' ', 'w'], []),
                   # ([], ['b', 'a']),
                   # (['l', 'd', '!'], [])]
print(diff_ranges(a, b))  # [(range(0, 4), range(0, 1)),
                          # (range(5, 8), range(2, 2)),
                          # (range(9, 9), range(3, 5)),
                          # (range(10, 13), range(6, 6))]

print(lcs(
    'xo',
    'xXOo',
    weight=lambda ca, cb: 1 if ca.lower() == cb.lower() else 0,
    take_b=True,
))  # ['X', 'O']

print(lcs_weight(
    'xxxoo',
    'ooxxx',
    weight=lambda ca, cb: {'x': 1, 'o': 2}[ca] if ca == cb else 0,
))  # 4