PHI algorithm in Python
Compute the LCP array in linear time using the predecessor array without the inverse suffix array.
- File
phi_algorithm.py, 52 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/phi-algorithm/. The authors are listed in prov/46X4G6.jsonl.
from typing import Sequence
def plcp_array(t: Sequence[object], sa: list[int]) -> list[int]:
"""The permuted LCP array: plcp[i] = lcp(suffix i, suffix phi[i]), where phi[i] is the
suffix just before suffix i in the suffix array (plcp[sa[0]] = 0).
One array of n integers holds phi and is then overwritten by plcp, in text order.
"""
n = len(t)
a = [0] * n
if n == 0:
return a
a[sa[0]] = -1 # @line L1
for r in range(1, n):
a[sa[r]] = sa[r - 1]
h = 0 # @line L2
for i in range(n): # @line L3
j = a[i]
if j == -1:
a[i], h = 0, 0
continue
while i + h < n and j + h < n and t[i + h] == t[j + h]: # @line L4
h += 1
a[i] = h # @line L5
if h > 0:
h -= 1
return a
def lcp_array(t: Sequence[object], sa: list[int]) -> list[int]:
"""lcp[r] = lcp(suffix sa[r - 1], suffix sa[r]) and lcp[0] = 0, by the PHI algorithm."""
plcp = plcp_array(t, sa)
return [plcp[p] for p in sa] # @line L6
def suffix_array(t: Sequence[object]) -> list[int]:
seq = list(t)
return sorted(range(len(seq)), key=lambda i: seq[i:])
def naive_lcp(t: Sequence[object], sa: list[int]) -> list[int]:
out = [0] * len(sa)
for r in range(1, len(sa)):
i, j, h = sa[r - 1], sa[r], 0
while i + h < len(t) and j + h < len(t) and t[i + h] == t[j + h]:
h += 1
out[r] = h
return out
test_phi_algorithm.py 41 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/phi-algorithm/. The authors are listed in prov/46X4G6.jsonl.
import random
from phi_algorithm import lcp_array, naive_lcp, plcp_array, suffix_array
def test_example() -> None:
t = "banana"
sa = suffix_array(t)
assert sa == [5, 3, 1, 0, 4, 2]
assert plcp_array(t, sa) == [0, 3, 2, 1, 0, 0]
assert lcp_array(t, sa) == [0, 1, 3, 0, 0, 2]
def test_edges() -> None:
assert lcp_array("", []) == [] and lcp_array("a", [0]) == [0]
t = "aaaaaaa"
assert lcp_array(t, suffix_array(t)) == [0, 1, 2, 3, 4, 5, 6]
t = "abcdefg"
assert lcp_array(t, suffix_array(t)) == [0] * 7
t = [3, 1, 3, 1, 3] # integer alphabets work too
assert lcp_array(t, suffix_array(t)) == naive_lcp(t, suffix_array(t))
def test_plcp_property() -> None:
# plcp[i + 1] >= plcp[i] - 1, the fact the algorithm relies on
rng = random.Random(7)
for _ in range(200):
t = "".join(rng.choice("ab") for _ in range(rng.randint(1, 40)))
p = plcp_array(t, suffix_array(t))
assert all(p[i + 1] >= p[i] - 1 for i in range(len(t) - 1))
def test_random_against_naive() -> None:
rng = random.Random(2009)
for case in range(600):
t = "".join(rng.choice("ab" if case % 2 else "acgt") for _ in range(rng.randint(0, 60)))
sa = suffix_array(t)
assert lcp_array(t, sa) == naive_lcp(t, sa)
What the next level needs
- the tests did not run in this build