大きなテキストのための文字列検索アルゴリズム

getdocs

4年前

1前書き

この記事では、大きなテキスト内のパターンを検索するためのいくつかのアルゴリズムを紹介します。各アルゴリズムについて、提供されているコードと簡単な数学的背景で説明します。

提供されているアルゴリズムは、より複雑なアプリケーションで全文検索を実行するための最良の方法ではありません。全文検索を正しく行うには、

Solr

または

ElasticSearch

を使用します。

2アルゴリズム

私たちは最も直感的なものであり、そのタスクに関連した他の高度な問題を発見するのを助ける素朴なテキスト検索アルゴリズムから始めます。

2.1. ヘルパーメソッド

始める前に、Rabin Karpアルゴリズムで使用する素数を計算する簡単な方法を定義しましょう。

public static long getBiggerPrime(int m) {
    BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random());
    return prime.longValue();
}
private static int getNumberOfBits(int number) {
    return Integer.SIZE - Integer.numberOfLeadingZeros(number);
}

2.2. 簡易テキスト検索

このアルゴリズムの名前は他のどの説明よりもよくそれを説明しています。

これは最も自然な解決策です。

public static int simpleTextSearch(char[]pattern, char[]text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0;

    while ((i + patternSize) <= textSize) {
        int j = 0;
        while (text[i + j]== pattern[j]) {
            j += 1;
            if (j >= patternSize)
                return i;
        }
        i += 1;
    }
    return -1;
}

このアルゴリズムの考え方は簡単です。テキストを繰り返し処理し、パターンの最初の文字と一致するものがあれば、そのパターンのすべての文字がテキストと一致するかどうかを確認します。

m

がパターン内の文字数で、

n

がテキスト内の文字数である場合、このアルゴリズムの時間計算量は

O（m（n-m + 1））

です。

最悪の場合のシナリオは、

String

に部分的な出現が多数ある場合に発生します。

Text: baeldunbaeldunbaeldunbaeldun
Pattern: baeldung

2.3. ラビンカープアルゴリズム

前述のように、単純テキスト検索アルゴリズムは、パターンが長い場合やパターンの繰り返し要素が多数ある場合は非常に非効率的です。

Rabin Karpアルゴリズムのアイデアはテキストのパターンを見つけるためにハッシュを使うことです。アルゴリズムの開始時に、後でアルゴリズムで使用されるパターンのハッシュを計算する必要があります。このプロセスはフィンガープリント計算と呼ばれ、詳細な説明はhttps://en.wikipedia.org/wiki/Rabin%E2%80%93Karp__algorithm[ここ]にあります。

前処理ステップについての重要なことは、その時間の複雑さが

O（m）

であり、テキストを介した繰り返しは

O（n）

を要することであり、これは全体のアルゴリズムの時間の複雑さ__O（m n）を与える。

アルゴリズムのコード:

public static int RabinKarpMethod(char[]pattern, char[]text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    long prime = getBiggerPrime(patternSize);

    long r = 1;
    for (int i = 0; i < patternSize - 1; i++) {
        r ** = 2;
        r = r % prime;
    }

    long[]t = new long[textSize];
    t[0]= 0;

    long pfinger = 0;

    for (int j = 0; j < patternSize; j++) {
        t[0]= (2 **  t[0]+ text[j]) % prime;
        pfinger = (2 **  pfinger + pattern[j]) % prime;
    }

    int i = 0;
    boolean passed = false;

    int diff = textSize - patternSize;
    for (i = 0; i <= diff; i++) {
        if (t[i]== pfinger) {
            passed = true;
            for (int k = 0; k < patternSize; k++) {
                if (text[i + k]!= pattern[k]) {
                    passed = false;
                    break;
                }
            }

            if (passed) {
                return i;
            }
        }

        if (i < diff) {
            long value = 2 **  (t[i]- r **  text[i]) + text[i + patternSize];
            t[i + 1]= ((value % prime) + prime) % prime;
        }
    }
    return -1;

}

最悪のシナリオでは、このアルゴリズムの時間計算量は

O（m（n-m 1））

です。しかしながら、平均して、このアルゴリズムは

O（n m）

時間複雑度を有する。

さらに、このアルゴリズムのモンテカルロバージョンは高速ですが、一致が誤っている可能性があります（誤検出）。

2.4 Knuth-Morris-Prattアルゴリズム

単純テキスト検索アルゴリズムでは、テキストにパターンと一致する部分が多いと、アルゴリズムが遅くなる可能性があることを確認しました。

Knuth-Morris-Prattアルゴリズムのアイデアは、シフトテーブルを計算することです。これにより、パターン候補を検索する場所に関する情報が得られます。シフトテーブルhttps://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt__algorithm[here]についてもっと読むことができます。

KMPアルゴリズムのJava実装

public static int KnuthMorrisPrattSearch(char[]pattern, char[]text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0, j = 0;

    int[]shift = KnuthMorrisPrattShift(pattern);

    while ((i + patternSize) <= textSize) {
        while (text[i + j]== pattern[j]) {
            j += 1;
            if (j >= patternSize)
                return i;
        }

        if (j > 0) {
            i += shift[j - 1];
            j = Math.max(j - shift[j - 1], 0);
        } else {
            i++;
            j = 0;
        }
    }
    return -1;
}

そして、これがシフトテーブルの計算方法です。

public static int[]KnuthMorrisPrattShift(char[]pattern) {
    int patternSize = pattern.length;

    int[]shift = new int[patternSize];
    shift[0]= 1;

    int i = 1, j = 0;

    while ((i + j) < patternSize) {
        if (pattern[i + j]== pattern[j]) {
            shift[i + j]= i;
            j++;
        } else {
            if (j == 0)
                shift[i]= i + 1;

            if (j > 0) {
                i = i + shift[j - 1];
                j = Math.max(j - shift[j - 1], 0);
            } else {
                i = i + 1;
                j = 0;
            }
        }
    }
    return shift;
}

このアルゴリズムの時間の複雑さもまた

O（m n）

です。

2.5. 単純ボイヤームーアアルゴリズム

2人の科学者、BoyerとMooreが別のアイデアを思いついた。シフト方向を同じに保ちながら、左から右ではなく右から左にパターンとテキストを比較しないでください。

public static int BoyerMooreHorspoolSimpleSearch(char[]pattern, char[]text) {
    int patternSize = pattern.length;
    int textSize = text.length;

    int i = 0, j = 0;

    while ((i + patternSize) <= textSize) {
        j = patternSize - 1;
        while (text[i + j]== pattern[j]) {
            j--;
            if (j < 0)
                return i;
        }
        i++;
    }
    return -1;
}

予想通り、これは

O（m ** n）

時間で実行されます。しかし、このアルゴリズムはオカレンスの実装とアルゴリズムを大幅にスピードアップする一致ヒューリスティックを導きました。

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore

string

search__algorithm[here]を見つけることができます。

2.6. Boyer-Moore-Horspoolアルゴリズム

Boyer-Mooreアルゴリズムのヒューリスティックな実装にはさまざまなバリエーションがあり、最も簡単なものはHorspoolのバリエーションです。

このバージョンのアルゴリズムは、Boyer-Moore-Horspoolと呼ばれ、この変化形は負のシフトの問題を解決しました（負のシフト問題についてはBoyer-Mooreアルゴリズムの説明で読むことができます）。

Boyer-Mooreアルゴリズムと同様に、最悪シナリオの時間複雑度は

O（m）です。
** n）

平均複雑度はO（n）です。スペース使用量はに依存しません

パターンのサイズ。ただし、アルファベットのサイズは256で、それ以降は英語のアルファベットのASCII文字の最大値です

public static int BoyerMooreHorspoolSearch(char[]pattern, char[]text) {

    int shift[]= new int[256];

    for (int k = 0; k < 256; k++) {
        shift[k]= pattern.length;
    }

    for (int k = 0; k < pattern.length - 1; k++){
        shift[pattern[k]]= pattern.length - 1 - k;
    }

    int i = 0, j = 0;

    while ((i + pattern.length) <= text.length) {
        j = pattern.length - 1;

        while (text[i + j]== pattern[j]) {
            j -= 1;
            if (j < 0)
                return i;
        }

        i = i + shift[text[i + pattern.length - 1]];
    }
    return -1;
}