接尾辞木と接尾辞配列は、大規模なテキストデータに対するパターン照合や部分文字列解析を効率的に行うために設計されたアルゴリズム基盤である。特に、文字列内の反復部分の検出や最長共通接尾辞の探索において、線形時間に近い性能を発揮する。本稿では、これらの構造の基本概念と、Java言語を用いた基礎的な実装パターンを解説する。

接尾辞木の設計と構築

接尾辞木は、対象文字列のすべての接尾辞を圧縮したトライ木として定義される。各辺には部分文字列が割り当てられ、根から葉へのパスが元の文字列の特定の接尾辞を表す。理論的にはUkkonenのアルゴリズムを用いることでO(n)での構築が可能だが、学習用に簡略化した逐次挿入アプローチを示す。

実装では、各ノードが子ノードへの参照マップと、接尾辞の終端を示すインデックスを保持する。入力文字列の末尾には一意性を保証する番兵文字を追加する。

public class SuffixTrieImpl {
    static class TreeNode {
        Map<Character, TreeNode> edges = new HashMap<>();
        Integer originOffset = null;
    }

    private final TreeNode root;
    private final String sourceBuffer;

    public SuffixTrieImpl(String input) {
        this.sourceBuffer = input + '$';
        this.root = new TreeNode();
        buildStructure();
    }

    private void buildStructure() {
        for (int start = 0; start < sourceBuffer.length() - 1; start++) {
            TreeNode cursor = root;
            for (int pos = start; pos < sourceBuffer.length(); pos++) {
                char symbol = sourceBuffer.charAt(pos);
                cursor.edges.putIfAbsent(symbol, new TreeNode());
                cursor = cursor.edges.get(symbol);
            }
            cursor.originOffset = start;
        }
    }
}

接尾辞配列の構成

接尾辞配列は、元の文字列に含まれるすべての接尾辞の開始位置を辞書順に並べ替えた整数配列である。接尾辞木と比較してメモリフットプリントが小さいが、探索時に若干の計算オーバーヘッドが生じる。単純な実装では、全接尾辞の比較を用いたソートが採用される。実装例では、インデックス配列を生成し、カスタム比較器を用いて辞書順ソートを実行する。部分文字列生成を回避し、文字単位での比較を行うことで不要なメモリ確保を防ぐ。

public class SuffixArrayIndex {
    private final int[] orderedStarts;
    private final String baseText;

    public SuffixArrayIndex(String content) {
        this.baseText = content;
        int len = content.length();
        Integer[] tempIndices = new Integer[len];
        for (int k = 0; k < len; k++) tempIndices[k] = k;

        Arrays.sort(tempIndices, (a, b) -> {
            int limit = Math.min(baseText.length() - a, baseText.length() - b);
            for (int i = 0; i < limit; i++) {
                char charA = baseText.charAt(a + i);
                char charB = baseText.charAt(b + i);
                if (charA != charB) return Character.compare(charA, charB);
            }
            return Integer.compare(baseText.length() - a, baseText.length() - b);
        });

        orderedStarts = new int[len];
        for (int i = 0; i < len; i++) orderedStarts[i] = tempIndices[i];
    }

    public int[] getIndices() { return orderedStarts; }
}

パターン検索アルゴリズムの適用

両データ構造とも、特定パターンの出現位置を抽出する機能を拡張できる。接尾辞木では木構造をトラバースして一致するノードに到達し、その配下にあるすべての終端オフセットを深さ優先探索で収集する。一方、接尾辞配列はソート済みの特性を活かし、二分探索を用いてパターンが含まれる範囲を特定した後、境界を拡張して全一致位置を取得する。

// 接尾辞木への検索ロジック追加
public List<Integer> searchPattern(String target) {
    List<Integer> matches = new ArrayList<>();
    TreeNode ptr = root;
    for (char ch : target.toCharArray()) {
        if (!ptr.edges.containsKey(ch)) return Collections.emptyList();
        ptr = ptr.edges.get(ch);
    }
    collectLeafOffsets(ptr, matches);
    return matches;
}

private void collectLeafOffsets(TreeNode node, List<Integer> bucket) {
    if (node.originOffset != null) bucket.add(node.originOffset);
    for (TreeNode child : node.edges.values()) {
        collectLeafOffsets(child, bucket);
    }
}

// 接尾辞配列への検索ロジック追加
public List<Integer> locatePatternInArray(String query) {
    List<Integer> results = new ArrayList<>();
    int leftBound = 0, rightBound = orderedStarts.length - 1;

    while (leftBound <= rightBound) {
        int mid = leftBound + (rightBound - leftBound) / 2;
        int cmp = compareSeqWithQuery(orderedStarts[mid], query);

        if (cmp < 0) leftBound = mid + 1;
        else if (cmp > 0) rightBound = mid - 1;
        else {
            scanBoundaries(mid, query, results);
            break;
        }
    }
    return results;
}

private int compareSeqWithQuery(int idx, String pat) {
    int lim = Math.min(baseText.length() - idx, pat.length());
    for (int k = 0; k < lim; k++) {
        int diff = baseText.charAt(idx + k) - pat.charAt(k);
        if (diff != 0) return diff;
    }
    return Integer.compare(pat.length(), baseText.length() - idx);
}

private void scanBoundaries(int center, String pat, List<Integer> out) {
    int l = center, r = center;
    while (l >= 0 && baseText.startsWith(pat, orderedStarts[l])) out.add(orderedStarts[l--]);
    while (r < orderedStarts.length && baseText.startsWith(pat, orderedStarts[r])) out.add(orderedStarts[r++]);
}