Python中是否有压缩后缀数组Psi的可用实现？

Hey Steve, I feel your pain—finding Python implementations for suffix arrays and the Psi array that are actually usable can be surprisingly tough, since most optimized code is locked up in lower-level languages like C++. Let's break down how to build both from scratch using your sample text as a reference, so you can see exactly how it works.

Step 1: Build the Suffix Array #

The naive (but totally effective for small-to-medium texts) approach is to generate every possible suffix of your string, sort them lexicographically, then extract their original starting indices to form the suffix array. This is easy to follow and matches your sample perfectly.

Here's the code:

def build_suffix_array(s):
    # Generate all suffixes paired with their original starting index
    suffixes = [(s[i:], i) for i in range(len(s))]
    # Sort suffixes alphabetically
    suffixes.sort()
    # Pull out just the indices to form the suffix array
    sa = [idx for (suffix, idx) in suffixes]
    return sa

# Your sample text (with $ as the required terminator)
text = "abbaabbaaababbb$"
sa = build_suffix_array(text)
print("Suffix Array (SA):", sa)

When you run this, you'll get exactly the SA you provided: [15, 7, 8, 3, 9, 4, 0, 11, 14, 6, 2, 10, 13, 5, 1, 12]—perfect!

Step 2: Compute the Psi Array from the Suffix Array #

The Psi array maps each suffix's starting index to the starting index of the suffix that immediately precedes it in the sorted suffix array. To calculate this, we first need a rank array: this tells us, for each suffix starting at index i, what position it holds in the suffix array. Once we have that, building the Psi array is straightforward.

Here's how to do it:

def build_rank_array(sa):
    # rank[i] = position of the suffix starting at i in the suffix array
    rank = [0] * len(sa)
    for position, suffix_index in enumerate(sa):
        rank[suffix_index] = position
    return rank

def build_psi_array(sa, rank):
    n = len(sa)
    psi = [0] * n
    # The first suffix in the SA (your $ suffix at index 15) has no predecessor
    psi[sa[0]] = -1
    # For every other suffix, map it to the suffix right before it in the SA
    for i in range(1, n):
        psi[sa[i]] = sa[i-1]
    return psi

# Calculate rank and Psi arrays
rank = build_rank_array(sa)
psi = build_psi_array(sa, rank)

print("Psi Array:", psi)

Using your sample SA, this will generate the correct Psi array: for example, psi[7] = 15 (since the suffix starting at 7 comes right after the $ suffix in the SA), psi[8] =7, and so on.

Optimizing for Larger Texts #

If you're working with very large strings (100,000+ characters), the naive suffix array method will be too slow. For those cases, you'll want to implement the SA-IS algorithm, which runs in linear time. It's more complex, but simplified Python implementations exist if you're willing to dig into the logic. That said, for most learning purposes or smaller datasets, the naive method is more than sufficient.

Quick Notes #

• The $ terminator is critical: it ensures all suffixes are unique and sorts before any lowercase ASCII letters, which keeps the suffix array sorted correctly.
• If you'd rather not build everything from scratch, libraries like sortedcontainers can help with sorting efficiency, but rolling your own gives you full control over the process.

内容的提问来源于stack exchange，提问作者Steve Jade