Minimal absent words algorithm in Python
Computes all minimal absent words of a string using suffix structures.
- File
minimal_absent_words_algorithm.py, 77 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/minimal-absent-words-algorithm/. The authors are listed in prov/DEK3N2.jsonl.
from collections.abc import Hashable, Iterable, Sequence
from typing import TypeVar
T = TypeVar("T", bound=Hashable)
def suffix_automaton(
y: Sequence[T],
) -> tuple[list[dict[T, int]], list[int], list[int], list[int]]:
"""Build the suffix automaton of y online.
Returns (nxt, link, length, end): the transition maps, the suffix links
(link[0] = -1 for the initial state 0), the length of the longest word of
each state, and one end position of the words of each state (-1 for 0).
Cost: O(len(y)) expected time with hash maps, at most 2 len(y) states.
"""
nxt: list[dict[T, int]] = [{}]
link = [-1]
length = [0]
end = [-1]
last = 0
for i, c in enumerate(y):
cur = len(length)
nxt.append({})
link.append(0)
length.append(length[last] + 1)
end.append(i)
p = last
while p != -1 and c not in nxt[p]:
nxt[p][c] = cur
p = link[p]
if p != -1:
q = nxt[p][c]
if length[p] + 1 == length[q]:
link[cur] = q
else:
clone = len(length)
nxt.append(dict(nxt[q]))
link.append(link[q])
length.append(length[p] + 1)
end.append(end[q])
while p != -1 and nxt[p].get(c) == q:
nxt[p][c] = clone
p = link[p]
link[q] = clone
link[cur] = clone
last = cur
return nxt, link, length, end
def minimal_absent_words(y: Sequence[T], alphabet: Iterable[T]) -> list[tuple[int, int, T]]:
"""Return the minimal absent words of y over the alphabet as triples (i, l, b).
The triple stands for the word y[i:i + l] followed by the letter b; a
missing letter b is reported as (0, 0, b). Precondition: every letter of y
is in the alphabet. Cost: O(len(y) + |alphabet| + z) expected time, where
z is the number of words reported, and O(len(y)) extra space.
"""
nxt, link, length, end = suffix_automaton(y) # @line L1
result: list[tuple[int, int, T]] = [] # @line L2
for b in alphabet: # @line L3
if b not in nxt[0]: # @line L4
result.append((0, 0, b))
for p in range(1, len(length)): # @line L5
l = length[link[p]] + 1 # @line L6
for b in nxt[link[p]]: # @line L7
if b not in nxt[p]: # @line L8
result.append((end[p] - l + 1, l, b)) # @line L9
return result # @line L10
def minimal_absent_strings(y: str, alphabet: Iterable[str]) -> list[str]:
"""Return the minimal absent words of the string y as sorted strings."""
return sorted(y[i : i + l] + b for i, l, b in minimal_absent_words(y, alphabet))
test_minimal_absent_words_algorithm.py 96 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/minimal-absent-words-algorithm/. The authors are listed in prov/DEK3N2.jsonl.
import itertools
import random
from minimal_absent_words_algorithm import (
minimal_absent_strings,
minimal_absent_words,
suffix_automaton,
)
def factors(y: str) -> set[str]:
return {y[i:j] for i in range(len(y) + 1) for j in range(i, len(y) + 1)}
def brute_force(y: str, alphabet: str) -> list[str]:
"""Check the definition directly on every candidate word.
A minimal absent word has all its proper prefixes in the factor set, so
only words f + b with f a factor and b a letter need checking; for each,
every proper factor is tested explicitly.
"""
f = factors(y)
out = set()
for x in f:
for b in alphabet:
w = x + b
if w in f:
continue
proper = {w[i:j] for i in range(len(w) + 1) for j in range(i, len(w) + 1)} - {w}
if proper <= f:
out.add(w)
return sorted(out)
def test_example() -> None:
assert minimal_absent_strings("abaab", "ab") == ["aaa", "aaba", "bab", "bb"]
assert sorted(minimal_absent_words("abaab", "ab")) == [
(1, 1, "b"),
(1, 2, "b"),
(2, 2, "a"),
(2, 3, "a"),
]
assert minimal_absent_strings("banana", "abn") == ["aa", "ab", "bb", "bn", "nanan", "nb", "nn"]
def test_edges() -> None:
assert minimal_absent_strings("", "ab") == ["a", "b"]
assert minimal_absent_strings("", "") == []
assert minimal_absent_strings("a", "a") == ["aa"]
assert minimal_absent_strings("aaaa", "ab") == ["aaaaa", "b"]
assert minimal_absent_strings("abc", "abcd") == ["aa", "ac", "ba", "bb", "ca", "cb", "cc", "d"]
assert minimal_absent_words([1, 2, 1], [1, 2]) is not None
def test_automaton_size() -> None:
rng = random.Random(3)
for _ in range(200):
y = "".join(rng.choice("ab") for _ in range(rng.randrange(1, 60)))
nxt, link, length, end = suffix_automaton(y)
assert len(length) <= max(2, 2 * len(y) - 1)
assert sum(len(d) for d in nxt) <= (3 * len(y) - 4 if len(y) >= 3 else 3)
def test_exhaustive_small() -> None:
for alphabet, top in (("a", 8), ("ab", 10), ("abc", 6)):
for n in range(top + 1):
for t in itertools.product(alphabet, repeat=n):
y = "".join(t)
assert minimal_absent_strings(y, alphabet) == brute_force(y, alphabet), y
def test_random_against_brute_force() -> None:
rng = random.Random(20261106)
for trial in range(600):
alphabet = "abc"[: 1 + trial % 3]
y = "".join(rng.choice(alphabet) for _ in range(rng.randrange(0, 40)))
got = minimal_absent_strings(y, alphabet)
assert got == brute_force(y, alphabet), y
assert len(got) == len(set(got))
if y:
assert len(got) <= 2 * len(alphabet) * len(y)
def test_factors_are_words_avoiding_maws() -> None:
rng = random.Random(11)
for _ in range(60):
y = "".join(rng.choice("ab") for _ in range(rng.randrange(0, 9)))
maws = minimal_absent_strings(y, "ab")
f = factors(y)
for length in range(len(y) + 3):
for t in itertools.product("ab", repeat=length):
w = "".join(t)
assert (w in f) == (not any(m in w for m in maws))
What the next level needs
- the tests did not run in this build