Javaのサフィックスツリーを使用した文字列の高速パターンマッチング

1. 概要

このチュートリアルでは、文字列のパターンマッチングの概念と、それを高速化する方法について説明します。次に、Javaでの実装について説明します。

2. 文字列のパターンマッチング

2.1. 意味

文字列では、パターンマッチングは、textと呼ばれる文字シーケンス内のapatternと呼ばれる特定の文字シーケンスをチェックするプロセスです。

パターンが正規表現でない場合のパターンマッチングの基本的な期待は次のとおりです。

一致は正確である必要があります–部分的ではありません
結果には、最初の一致だけでなく、すべての一致が含まれている必要があります
結果には、テキスト内の各一致の位置が含まれている必要があります

2.2. パターンの検索

例を使用して、単純なパターンマッチングの問題を理解しましょう。

Pattern:   NA
Text:      HAVANABANANA
Match1:    ----NA------
Match2:    --------NA--
Match3:    ----------NA

パターンNAがテキストで3回出現していることがわかります。この結果を得るには、パターンを一度に1文字ずつテキストの下にスライドさせて、一致するかどうかを確認することを考えることができます。

ただし、これは時間計算量 O（p * t）を伴うブルートフォースアプローチです。ここで、 p はパターンの長さ、tは長さです。テキストの。

検索するパターンが複数あるとします。次に、各パターンが個別の反復を必要とするため、時間計算量も直線的に増加します。

2.3. データ構造を試してパターンを保存する

アイテムの高速検索トライで知られるトライデータ構造にパターンを格納することで、検索時間を短縮できます。

トライデータ構造は、文字列の文字をツリーのような構造で格納することがわかっています。したがって、2つの文字列 {NA、NAB} の場合、2つのパスを持つツリーが得られます。

トライを作成すると、パターンのグループをテキストの下にスライドさせて、1回の反復で一致を確認できます。

$文字を使用して文字列の終わりを示していることに注意してください。

2.4. テキストを保存するためのサフィックストライデータ構造

一方、サフィックストライは、単一の文字列のすべての可能なサフィックスを使用して構築されたトライデータ構造です。

前の例HAVANABANANAの場合、接尾辞trieを作成できます。

接尾辞の試行はテキスト用に作成され、通常は前処理ステップの一部として実行されます。その後、パターンシーケンスに一致するパスを見つけることにより、パターンの検索をすばやく実行できます。

ただし、接尾辞trieは、文字列の各文字がエッジに格納されるため、多くのスペースを消費することが知られています。

次のセクションでは、接尾辞trieの改良版を見ていきます。

3. 接尾辞木

接尾辞treeは、単に圧縮された接尾辞trieです。つまり、エッジを結合することで、文字のグループを格納できるため、格納スペースを大幅に削減できます。

したがって、同じテキストHAVANABANANAの接尾辞木を作成できます。

ルートからリーフまでのすべてのパスは、文字列HAVANABANANAのサフィックスを表します。

接尾辞木もリーフノードの接尾辞の位置を保存します。たとえば、 BANANA $ は、7番目の位置から始まるサフィックスです。したがって、その値は、ゼロベースの番号付けを使用すると6になります。同様に、 A-> BANANA $ は、上の図に示すように、位置5から始まる別の接尾辞です。

したがって、物事を概観すると、パターン一致は、指定されたパターンと位置的に完全に一致するエッジを持つルートノードから始まるパスを取得できるときに発生することがわかります。

パスがリーフノードで終了する場合、サフィックスの一致が得られます。それ以外の場合は、部分文字列の一致のみを取得します。たとえば、パターン NA は、 HAVANABANA [NA] のサフィックスであり、 HAVA [NA]BANANAのサブストリングです。

次のセクションでは、Javaでこのデータ構造を実装する方法を説明します。

4. データ構造

接尾辞木のデータ構造を作成しましょう。 2つのドメインクラスが必要です。

まず、ツリーノードを表すクラスが必要です。ツリーのエッジとその子ノードを保存する必要があります。さらに、リーフノードの場合は、サフィックスの位置の値を格納する必要があります。

それでは、Nodeクラスを作成しましょう。

public class Node {
    private String text;
    private List<Node> children;
    private int position;

    public Node(String word, int position) {
        this.text = word;
        this.position = position;
        this.children = new ArrayList<>();
    }

    // getters, setters, toString()
}

次に、ツリーを表し、ルートノードを格納するクラスが必要です。また、サフィックスの生成元の全文を保存する必要があります。

したがって、SupplementTreeクラスがあります。

public class SuffixTree {
    private static final String WORD_TERMINATION = "$";
    private static final int POSITION_UNDEFINED = -1;
    private Node root;
    private String fullText;

    public SuffixTree(String text) {
        root = new Node("", POSITION_UNDEFINED);
        fullText = text;
    }
}

5. データを追加するためのヘルパーメソッド

データを格納するコアロジックを作成する前に、いくつかのヘルパーメソッドを追加しましょう。これらは後で役立つことがわかります。

SupplementTree クラスを変更して、ツリーの構築に必要ないくつかのメソッドを追加しましょう。

5.1. 子ノードの追加

まず、addChildNodeからに新しい子ノードを任意の親ノードに追加するメソッドを作成しましょう。

private void addChildNode(Node parentNode, String text, int index) {
    parentNode.getChildren().add(new Node(text, index));
}

5.2. 2つの文字列の最長の共通プレフィックスを見つける

次に、単純なユーティリティメソッド getLongestCommonPrefix を記述して、2つの文字列の最長の共通プレフィックスを検索します。

private String getLongestCommonPrefix(String str1, String str2) {
    int compareLength = Math.min(str1.length(), str2.length());
    for (int i = 0; i < compareLength; i++) {
        if (str1.charAt(i) != str2.charAt(i)) {
            return str1.substring(0, i);
        }
    }
    return str1.substring(0, compareLength);
}

5.3. ノードの分割

第三に、与えられた親から子ノードを切り出すメソッドを持ってみましょう。このプロセスでは、親ノードの text 値が切り捨てられ、右に切り捨てられた文字列が子ノードのtext値になります。さらに、親の子は子ノードに転送されます。

下の写真から、ANAがA->NAに分割されていることがわかります。その後、新しい接尾辞 ABANANA$をAとして追加できます。 -> BANANA $ ：

要するに、これは新しいノードを挿入するときに便利な便利な方法です。

private void splitNodeToParentAndChild(Node parentNode, String parentNewText, String childNewText) {
    Node childNode = new Node(childNewText, parentNode.getPosition());

    if (parentNode.getChildren().size() > 0) {
        while (parentNode.getChildren().size() > 0) {
            childNode.getChildren()
              .add(parentNode.getChildren().remove(0));
        }
    }

    parentNode.getChildren().add(childNode);
    parentNode.setText(parentNewText);
    parentNode.setPosition(POSITION_UNDEFINED);
}

6. トラバーサルのヘルパーメソッド

次に、ツリーをトラバースするロジックを作成しましょう。このメソッドは、ツリーの構築とパターンの検索の両方に使用します。

6.1. パーシャルマッチvs. フルマッチ

まず、いくつかの接尾辞が設定されたツリーを検討して、部分一致と完全一致の概念を理解しましょう。

新しいサフィックスANABANANA$ を追加するために、新しい値に対応するように変更または拡張できるノードが存在するかどうかを確認します。このために、新しいテキストをすべてのノードと比較し、既存のノード [A] VANABANANA$が最初の文字と一致することを確認します。したがって、これは変更する必要のあるノードであり、この一致は部分一致と呼ぶことができます。

一方、同じツリーでパターンVANEを検索しているとしましょう。最初の3文字が[VAN]ABANANA$と部分的に一致していることがわかります。 4つの文字すべてが一致した場合、それを完全一致と呼ぶことができます。 パターン検索には、完全一致が必要です。

要約すると、ツリーを構築するときは部分一致を使用し、パターンを検索するときは完全一致を使用します。フラグisAllowPartialMatchを使用して、それぞれの場合に必要な一致の種類を示します。

6.2. ツリーをトラバースする

次に、特定のパターンを位置的に一致させることができる限り、ツリーをトラバースするロジックを記述しましょう。

List<Node> getAllNodesInTraversePath(String pattern, Node startNode, boolean isAllowPartialMatch) {
    // ...
}

これを再帰的に呼び出し、パスで見つかったすべてのノードのリストを返します。

パターンテキストの最初の文字をノードテキストと比較することから始めます。

if (pattern.charAt(0) == nodeText.charAt(0)) {
    // logic to handle remaining characters       
}

部分一致の場合、パターンの長さがノードテキストより短いか等しい場合は、現在のノードをノードリストに追加し、ここで停止します。

if (isAllowPartialMatch && pattern.length() <= nodeText.length()) {
    nodes.add(currentNode);
    return nodes;
}

次に、このノードテキストの残りの文字をパターンの文字と比較します。パターンの位置がノードテキストと一致しない場合は、ここで停止します。現在のノードは、部分的に一致する場合にのみnodesリストに含まれます。

int compareLength = Math.min(nodeText.length(), pattern.length());
for (int j = 1; j < compareLength; j++) {
    if (pattern.charAt(j) != nodeText.charAt(j)) {
        if (isAllowPartialMatch) {
            nodes.add(currentNode);
        }
        return nodes;
    }
}

パターンがノードテキストと一致した場合、現在のノードをnodesリストに追加します。

nodes.add(currentNode);

ただし、パターンにノードテキストよりも多くの文字が含まれている場合は、子ノードを確認する必要があります。このために、 currentNode を開始ノードとして渡し、patternの残りの部分を新しいパターンとして渡す再帰呼び出しを行います。この呼び出しから返されたノードのリストは、空でない場合はnodesリストに追加されます。完全一致シナリオで空の場合は、不一致があったことを意味するため、これを示すために、nullアイテムを追加します。そして、ノードを返します。

if (pattern.length() > compareLength) {
    List nodes2 = getAllNodesInTraversePath(pattern.substring(compareLength), currentNode, 
      isAllowPartialMatch);
    if (nodes2.size() > 0) {
        nodes.addAll(nodes2);
    } else if (!isAllowPartialMatch) {
        nodes.add(null);
    }
}
return nodes;

これらすべてをまとめて、getAllNodesInTraversePathを作成しましょう。

private List<Node> getAllNodesInTraversePath(String pattern, Node startNode, boolean isAllowPartialMatch) {
    List<Node> nodes = new ArrayList<>();
    for (int i = 0; i < startNode.getChildren().size(); i++) {
        Node currentNode = startNode.getChildren().get(i);
        String nodeText = currentNode.getText();
        if (pattern.charAt(0) == nodeText.charAt(0)) {
            if (isAllowPartialMatch && pattern.length() <= nodeText.length()) {
                nodes.add(currentNode);
                return nodes;
            }

            int compareLength = Math.min(nodeText.length(), pattern.length());
            for (int j = 1; j < compareLength; j++) {
                if (pattern.charAt(j) != nodeText.charAt(j)) {
                    if (isAllowPartialMatch) {
                        nodes.add(currentNode);
                    }
                    return nodes;
                }
            }

            nodes.add(currentNode);
            if (pattern.length() > compareLength) {
                List<Node> nodes2 = getAllNodesInTraversePath(pattern.substring(compareLength), 
                  currentNode, isAllowPartialMatch);
                if (nodes2.size() > 0) {
                    nodes.addAll(nodes2);
                } else if (!isAllowPartialMatch) {
                    nodes.add(null);
                }
            }
            return nodes;
        }
    }
    return nodes;
}

7. アルゴリズム

7.1. データの保存

これで、データを格納するロジックを記述できます。 SuffixTreeクラスで新しいメソッドaddSuffixを定義することから始めましょう。

private void addSuffix(String suffix, int position) {
    // ...
}

発信者はサフィックスの位置を提供します。

次に、接尾辞を処理するロジックを記述しましょう。最初に、少なくともisAllowPartialMatchをtrueに設定してヘルパーメソッドgetAllNodesInTraversePathを呼び出すことにより、サフィックスに部分的に一致するパスが存在するかどうかを確認する必要があります ]。パスが存在しない場合は、ルートに子としてサフィックスを追加できます。

List<Node> nodes = getAllNodesInTraversePath(pattern, root, true);
if (nodes.size() == 0) {
    addChildNode(root, suffix, position);
}

ただし、パスが存在する場合は、既存のノードを変更する必要があることを意味します。このノードは、ノードリストの最後のノードになります。また、この既存のノードの新しいテキストを把握する必要があります。 ノードリストに項目が1つしかない場合は、サフィックスを使用します。それ以外の場合は、サフィックスから最後のノードまでの共通プレフィックスを除外して、newTextを取得します。

Node lastNode = nodes.remove(nodes.size() - 1);
String newText = suffix;
if (nodes.size() > 0) {
    String existingSuffixUptoLastNode = nodes.stream()
        .map(a -> a.getText())
        .reduce("", String::concat);
    newText = newText.substring(existingSuffixUptoLastNode.length());
}

既存のノードを変更するために、新しいメソッド extendsNode、を作成しましょう。これは、addSuffixメソッドで中断したところから呼び出します。この方法には2つの重要な責任があります。 1つは、既存のノードを親と子に分割することであり、もう1つは、新しく作成された親ノードに子を追加することです。親ノードを分割して、すべての子ノードの共通ノードにします。これで、新しいメソッドの準備が整いました。

private void extendNode(Node node, String newText, int position) {
    String currentText = node.getText();
    String commonPrefix = getLongestCommonPrefix(currentText, newText);

    if (commonPrefix != currentText) {
        String parentText = currentText.substring(0, commonPrefix.length());
        String childText = currentText.substring(commonPrefix.length());
        splitNodeToParentAndChild(node, parentText, childText);
    }

    String remainingText = newText.substring(commonPrefix.length());
    addChildNode(node, remainingText, position);
}

これで、サフィックスを追加する方法に戻ることができます。これで、すべてのロジックが配置されました。

private void addSuffix(String suffix, int position) {
    List<Node> nodes = getAllNodesInTraversePath(suffix, root, true);
    if (nodes.size() == 0) {
        addChildNode(root, suffix, position);
    } else {
        Node lastNode = nodes.remove(nodes.size() - 1);
        String newText = suffix;
        if (nodes.size() > 0) {
            String existingSuffixUptoLastNode = nodes.stream()
                .map(a -> a.getText())
                .reduce("", String::concat);
            newText = newText.substring(existingSuffixUptoLastNode.length());
        }
        extendNode(lastNode, newText, position);
    }
}

最後に、 SupplementTree コンストラクターを変更してサフィックスを生成し、前のメソッド addSuffix を呼び出して、それらをデータ構造に繰り返し追加しましょう。

public void SuffixTree(String text) {
    root = new Node("", POSITION_UNDEFINED);
    for (int i = 0; i < text.length(); i++) {
        addSuffix(text.substring(i) + WORD_TERMINATION, i);
    }
    fullText = text;
}

7.2. データの検索

データを格納するための接尾辞ツリー構造を定義したので、検索を実行するためのロジックを記述できます。

まず、SuffixTreeクラスに新しいメソッドsearchTextを追加し、patternを入力として検索します。

public List<String> searchText(String pattern) {
    // ...
}

次に、 pattern がサフィックスツリーに存在するかどうかを確認するために、部分一致を許可した場合のデータの追加時とは異なり、完全一致のみにフラグを設定してヘルパーメソッドgetAllNodesInTraversePathを呼び出します。一致：

List<Node> nodes = getAllNodesInTraversePath(pattern, root, false);

次に、パターンに一致するノードのリストを取得します。リストの最後のノードは、パターンが完全に一致したノードを示します。したがって、次のステップは、この最後に一致したノードから発生したすべてのリーフノードを取得し、これらのリーフノードに格納されている位置を取得することです。

これを行うために、別のメソッドgetPositionsを作成しましょう。指定されたノードがサフィックスの最後の部分を格納しているかどうかを確認して、その位置の値を返す必要があるかどうかを判断します。そして、指定されたノードのすべての子に対してこれを再帰的に実行します。

private List<Integer> getPositions(Node node) {
    List<Integer> positions = new ArrayList<>();
    if (node.getText().endsWith(WORD_TERMINATION)) {
        positions.add(node.getPosition());
    }
    for (int i = 0; i < node.getChildren().size(); i++) {
        positions.addAll(getPositions(node.getChildren().get(i)));
    }
    return positions;
}

位置のセットを取得したら、次のステップは、それを使用して、接尾辞ツリーに格納したテキストのパターンをマークすることです。位置の値は接尾辞の開始位置を示し、パターンの長さは開始点からオフセットする文字数を示します。このロジックを適用して、簡単なユーティリティメソッドを作成しましょう。

private String markPatternInText(Integer startPosition, String pattern) {
    String matchingTextLHS = fullText.substring(0, startPosition);
    String matchingText = fullText.substring(startPosition, startPosition + pattern.length());
    String matchingTextRHS = fullText.substring(startPosition + pattern.length());
    return matchingTextLHS + "[" + matchingText + "]" + matchingTextRHS;
}

これで、サポートメソッドの準備が整いました。したがって、それらを検索メソッドに追加して、ロジックを完成させることができます。

public List<String> searchText(String pattern) {
    List<String> result = new ArrayList<>();
    List<Node> nodes = getAllNodesInTraversePath(pattern, root, false);
    
    if (nodes.size() > 0) {
        Node lastNode = nodes.get(nodes.size() - 1);
        if (lastNode != null) {
            List<Integer> positions = getPositions(lastNode);
            positions = positions.stream()
              .sorted()
              .collect(Collectors.toList());
            positions.forEach(m -> result.add((markPatternInText(m, pattern))));
        }
    }
    return result;
}

8. テスト

アルゴリズムが整ったので、テストしてみましょう。

まず、SuffixTreeにテキストを保存しましょう。

SuffixTree suffixTree = new SuffixTree("havanabanana");

次に、有効なパターンaを検索しましょう。

List<String> matches = suffixTree.searchText("a");
matches.stream().forEach(m -> LOGGER.debug(m));

コードを実行すると、期待どおりに6つの一致が得られます。

h[a]vanabanana
hav[a]nabanana
havan[a]banana
havanab[a]nana
havanaban[a]na
havanabanan[a]

次に、別の有効なパターンnabを検索しましょう。

List<String> matches = suffixTree.searchText("nab");
matches.stream().forEach(m -> LOGGER.debug(m));

コードを実行すると、期待どおりに1つの一致のみが得られます。

hava[nab]anana

最後に、無効なパターンnagを検索しましょう。

List<String> matches = suffixTree.searchText("nag");
matches.stream().forEach(m -> LOGGER.debug(m));

コードを実行しても結果は得られません。一致は部分的ではなく正確である必要があることがわかります。

したがって、私たちのパターン検索アルゴリズムは、このチュートリアルの最初に提示したすべての期待に応えることができました。

9. 時間計算量

長さtの特定のテキストの接尾辞木を作成する場合、時間計算量はO（t）です。

次に、長さ p、 のパターンを検索する場合、時間計算量はO（p）です。強引な検索の場合は、 O（p * t）であったことを思い出してください。したがって、パターン検索は、テキストの前処理後に高速になります。

10. 結論

この記事では、最初に3つのデータ構造（trie、suffix trie、suffix tree）の概念を理解しました。次に、接尾辞ツリーを使用して接尾辞をコンパクトに格納する方法を確認しました。

後で、接尾辞木を使用してデータを格納し、パターン検索を実行する方法を見ました。

いつものように、テスト付きのソースコードはGitHubで利用できます。