Greedy superstring merging in Python
Repeatedly merges the pair of strings with the largest overlap, giving an approximation.
- File
greedy_superstring_merge.py, 121 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/greedy-superstring-merge/. The authors are listed in prov/HBAFAC.jsonl.
from typing import List, Optional, Sequence, Tuple
_SEP = object()
def _prefix_function(t: Sequence[object]) -> List[int]:
pi = [0] * len(t)
for q in range(1, len(t)):
k = pi[q - 1]
while k > 0 and t[q] != t[k]:
k = pi[k - 1]
if t[q] == t[k]:
k += 1
pi[q] = k
return pi
def overlap(x: str, y: str) -> int:
"""Length of the longest suffix of x that is a prefix of y, below min(|x|, |y|) + 1.
Uses the prefix function of y, a separator, then x: O(|x| + |y|) time.
"""
if not x or not y:
return 0
t: List[object] = list(y)
t.append(_SEP)
t.extend(x)
return _prefix_function(t)[-1]
def _occurs(p: str, t: str) -> bool:
if not p:
return True
u: List[object] = list(p)
u.append(_SEP)
u.extend(t)
return any(v == len(p) for v in _prefix_function(u))
def reduce_strings(strings: Sequence[str]) -> List[str]:
"""Drop duplicates (keeping the first copy) and strings inside other strings.
The order of the kept strings is the input order. O(m * n) time.
"""
distinct: List[str] = []
seen = set()
for s in strings:
if s not in seen:
seen.add(s)
distinct.append(s)
kept: List[str] = []
for i, s in enumerate(distinct):
if not any(j != i and _occurs(s, t) for j, t in enumerate(distinct)):
kept.append(s)
return kept
def greedy_merge_order(strings: Sequence[str]) -> Tuple[List[str], List[Tuple[int, int, int]]]:
"""Return the reduced list and the accepted merges (i, j, w) in greedy order.
Pairs are tried by decreasing overlap w, ties by smaller i, then smaller j,
where i and j index the reduced list.
"""
# @line L1
s = reduce_strings(strings)
m = len(s)
# @line L2
pairs = [(overlap(s[i], s[j]), i, j) for i in range(m) for j in range(m) if i != j]
# @line L3
pairs.sort(key=lambda e: (-e[0], e[1], e[2]))
nxt: List[Optional[int]] = [None] * m
prv: List[Optional[int]] = [None] * m
head_of = list(range(m)) # head_of[t] is the head of the chain whose tail is t
tail_of = list(range(m)) # tail_of[h] is the tail of the chain whose head is h
merges: List[Tuple[int, int, int]] = []
# @line L4
for w, i, j in pairs:
# @line L5
if nxt[i] is None and prv[j] is None and head_of[i] != j:
# @line L6
nxt[i] = j
prv[j] = i
h, t = head_of[i], tail_of[j]
head_of[t] = h
tail_of[h] = t
merges.append((i, j, w))
if len(merges) == m - 1:
break
return s, merges
def greedy_superstring(strings: Sequence[str]) -> str:
"""Greedy superstring of the given strings; the empty string for no input.
Time O(m * n + m^2 log m), space O(n + m^2), for m strings of total length n.
"""
s, merges = greedy_merge_order(strings)
m = len(s)
if m == 0:
return ""
nxt: List[Optional[int]] = [None] * m
weight = [0] * m
has_prev = [False] * m
for i, j, w in merges:
nxt[i] = j
weight[i] = w
has_prev[j] = True
# @line L7
h = has_prev.index(False)
parts = [s[h]]
# @line L8
while nxt[h] is not None:
j = nxt[h]
assert j is not None
parts.append(s[j][weight[h] :])
h = j
# @line L9
return "".join(parts)
test_greedy_superstring_merge.py 147 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/greedy-superstring-merge/. The authors are listed in prov/HBAFAC.jsonl.
import itertools
import random
from typing import List, Sequence
from greedy_superstring_merge import (
greedy_merge_order,
greedy_superstring,
overlap,
reduce_strings,
)
def ov(x: str, y: str) -> int:
for k in range(min(len(x), len(y)), -1, -1):
if x[len(x) - k :] == y[:k]:
return k
return 0
def naive_merge(strings: Sequence[str]) -> str:
# The string form: merge two current strings with the largest overlap,
# ties by the smaller tail index, then the smaller head index.
s = reduce_strings(strings)
chains: List[List[int]] = [[i] for i in range(len(s))]
text = list(s)
while len(chains) > 1:
best = None
for a in range(len(chains)):
for b in range(len(chains)):
if a != b:
w = ov(text[a], text[b])
key = (-w, chains[a][-1], chains[b][0])
if best is None or key < best[0]:
best = (key, a, b, w)
assert best is not None
_, a, b, w = best
new_text = text[a] + text[b][w:]
new_chain = chains[a] + chains[b]
for x in sorted((a, b), reverse=True):
del chains[x]
del text[x]
chains.append(new_chain)
text.append(new_text)
return text[0] if text else ""
def optimum(strings: Sequence[str]) -> int:
s = reduce_strings(strings)
if not s:
return 0
best = None
for p in itertools.permutations(range(len(s))):
length = len(s[p[0]])
for a, b in zip(p, p[1:]):
length += len(s[b]) - ov(s[a], s[b])
best = length if best is None else min(best, length)
assert best is not None
return best
def check(strings: List[str]) -> None:
g = greedy_superstring(strings)
assert g == naive_merge(strings), (strings, g)
for x in strings:
assert x in g
opt = optimum(strings)
assert opt <= len(g) <= 4 * opt or (opt == 0 and g == "")
kept = reduce_strings(strings)
total = sum(map(len, kept))
assert 2 * (total - len(g)) >= total - opt
_, merges = greedy_merge_order(strings)
assert len(g) == total - sum(w for _, _, w in merges)
def test_example() -> None:
s, merges = greedy_merge_order(["abb", "bba", "bbb"])
assert s == ["abb", "bba", "bbb"]
assert merges == [(0, 1, 2), (1, 2, 0)]
assert greedy_superstring(["abb", "bba", "bbb"]) == "abbabbb"
assert greedy_superstring(["abb", "bbb", "bba"]) == "abbba"
assert optimum(["abb", "bba", "bbb"]) == 5
def test_overlap() -> None:
assert overlap("abb", "bba") == 2
assert overlap("bba", "abb") == 1
assert overlap("bba", "bbb") == 0
assert overlap("", "a") == 0
assert overlap("aaa", "aa") == 2
def test_edge_cases() -> None:
assert greedy_superstring([]) == ""
assert greedy_superstring([""]) == ""
assert greedy_superstring(["", ""]) == ""
assert greedy_superstring(["a"]) == "a"
assert greedy_superstring(["a", "a"]) == "a"
assert greedy_superstring(["ab", "b"]) == "ab"
assert greedy_superstring(["aaa", "aa", "a"]) == "aaa"
assert greedy_superstring(["ab", "ba"]) == "aba"
assert reduce_strings(["b", "ab", "b", "abc"]) == ["abc"]
def test_lower_bound_family() -> None:
for k in range(1, 8):
bad = ["a" + "b" * k, "b" * k + "a", "b" * (k + 1)]
good = [bad[0], bad[2], bad[1]]
assert len(greedy_superstring(bad)) == 2 * k + 3
assert len(greedy_superstring(good)) == k + 3
assert optimum(bad) == k + 3
def test_exhaustive_small() -> None:
for k in (1, 2, 3):
alphabet = "abc"[:k]
words = [
"".join(w) for n in range(0, 4) for w in itertools.product(alphabet, repeat=n)
]
limit = 3 if k < 3 else 2
for m in range(1, limit + 1):
for strings in itertools.product(words, repeat=m):
check(list(strings))
def test_random() -> None:
rng = random.Random(2026)
for _ in range(600):
k = rng.choice((1, 2, 3))
alphabet = "abc"[:k]
m = rng.randint(0, 6)
strings = [
"".join(rng.choice(alphabet) for _ in range(rng.randint(0, 6))) for _ in range(m)
]
check(strings)
if __name__ == "__main__":
test_example()
test_overlap()
test_edge_cases()
test_lower_bound_family()
test_exhaustive_small()
test_random()
print("ok")
What the next level needs
- the tests did not run in this build