文字列一致検索アルゴリズムの中で、最も有名なものは、KMP アルゴリズム (Knuth-Morris-Pratt) と BM アルゴリズム (Boyer-Moore) の 2 つです。どちらのアルゴリズムも、最悪の場合でも検索時間は線形です。ただし、実際には、KMP アルゴリズムは最も単純な C ライブラリ関数 strstr() よりもそれほど高速ではありませんが、BM アルゴリズムは KMP アルゴリズムよりも 3 ～ 5 倍高速であることがよくあります (個人的に実践したわけではありません)。ただし、BM アルゴリズムはまだ最速のアルゴリズムではありません。ここに、BM アルゴリズムよりも高速な検索アルゴリズム、Sunday アルゴリズムがあります。
サンデーアルゴリズムの考え方は、BMアルゴリズムの悪い文字の考え方と非常に似ています。唯一の違いは、Sunday アルゴリズムが一致に失敗した後、パターン文字列に対応するターゲット文字列の現在の部分の 1 つ後ろの文字を取得して不正な文字一致を実行することです。一致に失敗した場合は、親文字列の現在のオフセット+パターン文字列長+1(K位置とする)の文字がパターン文字列に存在するかどうかを判定する。存在する場合は、パターン文字列内の文字と位置を合わせてから、存在しない場合は、パターン文字列を後方に移動し、親文字列の k+1 の文字と位置を合わせてから、マッチ。見つかるまで、または親文字列が見つかるまで、上記の操作を繰り返します。次のアルゴリズムを実装するための小さな例を書きました。
コードでは、2 つの文字列マッチング アルゴリズムが実装されています。1 つは Sunday メソッド、もう 1 つは一度に 1 ビットを移動する通常のメソッドで、両方ともナノ秒レベルで 2 つの効率の比較が main 関数に示されています。 。アルゴリズムの詳細な手順は、コード内に対応するコメントとともに追加されています。 BMアルゴリズムについては、次回空の場合に一緒に比較・解析してみます。
次のようにコードをコピーします。
java.util.HashMapをインポートします。
java.util.LinkedListをインポートします。
java.util.Listをインポートします。
java.util.Mapをインポートします。
/**
* @著者スコット
* @日付 2013 年 12 月 28 日
* @説明
*/
パブリック クラス SundySearch {
文字列テキスト = null;
文字列パターン = null;
int currentPos = 0;
/**
* 一致した部分文字列の最初の文字位置のリスト
*/
List<Integer> matchedPosList = new LinkedList<Integer>();
/**
* 一致する文字のマップ、一致する文字列に含まれる文字、および各文字の最後の変位を記録します
*/
Map<文字, 整数> map = new HashMap<文字, 整数>();
public SundySearch(文字列テキスト、文字列パターン) {
this.text = テキスト;
this.pattern = パターン;
this.initMap();
};
/**
※日曜日に一致する場合、パターン内の各文字の最後の出現位置を左から右の順に格納するために使用されます。
*/
private void initMap() {
for (int i = 0; i < pattern.length(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* 通常の文字列の再帰一致。一致が失敗した場合は 1 つ進みます。
*/
public List<Integer> NormalMatch() {
// 一致しませんでした。下に進みます
if (!matchFromSpecialPos(currentPos)) {
現在の位置 += 1;
if ((text.length() - currentPos) < pattern.length()) {
matchedPosList を返します。
}
NormalMatch();
} それ以外 {
// 一致に成功し、場所を記録します
matchedPosList.add(currentPos);
現在の位置 += 1;
NormalMatch();
}
matchedPosList を返します。
}
/**
* 日曜日のマッチング。テキスト内の K 文字の位置が現在のオフセット + パターン文字列の長さ + 1 であると仮定します。
*/
public List<Integer> sundayMatch() {
// 一致が成功しなかった場合
if (!matchFromSpecialPos(currentPos)) {
// Text の K 文字がパターン文字列に現れない場合は、パターン文字列全体の長さをスキップします。
if ((currentPos + pattern.length() + 1) < text.length()
&& !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
currentPos += pattern.length();
}それ以外 {
// Text の K 文字がパターン文字列に出現する場合、Text の K 文字の位置をパターン文字列の最後の K 文字の位置に揃えます。
if ((currentPos + pattern.length() + 1) > text.length()) {
現在の位置 += 1;
} それ以外 {
currentPos += pattern.length() - (整数) map.get(text.charAt(currentPos + pattern.length()));
}
}
// 一致が完了したら、成功したすべての一致の初期ディスプレイスメントを返します。
if ((text.length() - currentPos) < pattern.length()) {
matchedPosList を返します。
}
sundayMatch();
}それ以外 {
// 照合が成功した場合は、1 ビット進めてから再度照合します
matchedPosList.add(currentPos);
現在の位置 += 1;
sundayMatch();
}
matchedPosList を返します。
}
/**
* Text の指定されたオフセットから始まる部分文字列がパターンと一致するかどうかを確認します
*/
public boolean matchFromSpecialPos(int pos) {
if ((text.length()-pos) < pattern.length()) {
false を返します。
}
for (int i = 0; i < pattern.length(); i++) {
if (text.charAt(pos + i) == pattern.charAt(i)) {
if (i == (pattern.length()-1)) {
true を返します。
}
続く;
} それ以外 {
壊す;
}
}
false を返します。
}
public static void main(String[] args) {
SundySearch sundySearch = new SundySearch("こんにちは、ああアドルフ adfsadfklf adf234masdfsdfdsfdsfdsffwerwrerwerwersdf2666sdflsdfk", "adf");
長い開始 = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - begin));
begin = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - begin));
}
}