2012-01-17 27 views
1

Rabin-Karp検索アルゴリズムはうまくいきますが、誰でも再帰検索に変更する際の手引きはありますか? http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html。 例:再帰的一致を返す文字列検索アルゴリズム - Java

* **pattern:** rar 
* **text:** abacadabrararbracabrarararacadabrabrarbracad 
* **match1:**   rar    
* **match2:**   rar 
* **match3:**      rar 
* **match4:**      rar 
* **match5:**       rar 
* **match5:**          rar 

再帰的なテキストマッチング検索のアルゴリズムは他に高速ですか?

SOLUTION

パスを構築するためにhttp://johannburkard.de/software/stringsearch/から外部ライブラリを追加します。以下のコードは、マッチの開始位置をすべて返します。 match1とmatch2のように埋め込まれたものを含みます。

import com.eaio.stringsearch.BNDM; 

String pattern = "rar"; 
String text = "abacadabrararbracabrarararacadabrabrarbracad"; 

// Loop through text to get starting position of matched pattern. 
List<Integer> matchPoint =new ArrayList<Integer>(); 
int slice = -1; 
while (slice<text.length()){ 
    slice+=1; 
    com.eaio.stringsearch.BNDM result = new BNDM(); 
    int pos = result.searchString(text, slice, pattern); 
    if (pos != -1) { 
     slice = pos; 
     matchPoint.add(pos); 
    } 
} 
+0

反復コードを再帰的コードに変換した経験がありますか? –

+0

いいえ、通常は単に 'pattern'を関数に入れて、関数が' text'の最後に返答するまで検索を呼び出します。 – alvas

+1

まあ、あなたは正しい軌道にいるのです。アイデアは、ある反復が2つ以上のサブ問題に解決し、次に別の再帰呼び出しでそれらを解決するという問題を解くことです。それが基本原則です。 –

答えて

2

もちろんあります。文字列中の小さなパターンを検索する場合、Rabin-Karpの使用はお勧めしません。 Knuth-Morris-Prattアルゴリズムは線形時間と線形の追加メモリを必要とし、Rabin-Karpを扱うときの衝突の場合を除いてすべての一致を返すことができます。それについてはwikiをお読みください。このアルゴリズムは、理解するのが少し難しいですが、コードには短く、いったん正しいとすれば、とても満足しています。

+0

私はこのKMPモジュールを自分のコードに走らせてみました。 http://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/KMPMatch_java.html。文字列検索のための他のシンプルでメモリを節約する方法はありますか?私はhttp://johannburkard.de/software/stringsearch/からBNDMを試しましたが、コードを書き換えるのに時間がかかりすぎてしまいました。検索はシンプルで時間/メモリを無駄にする助言がありますか? – alvas

+0

これは、入力自体よりも2倍のメモリを必要とするアルゴリズム(または、パターンが検索する文字列よりも小さい場合は大幅に少なくて済むアルゴリズム)のためにメモリを使い果たした場合に少し面倒です。おそらく、あなたはjavaのVMの設定が悪い可能性が高いです。今私はあなたが私たちが同じ大学から来ていることを知ったので、あなたを助けることをさらに強く勧めます:P –

+0

=)ボリス、あなたはNTUかUDSですか?ははは。私はRabin-Karpを再帰的にしましたが、それもメモリ不足の問題になります。私はBNDM algoを実装することでこの問題を解決しました。しかし、http://johannburkard.de/software/stringsearch/からAPIを使用した場合と同じくらい速くはありません。 – alvas

1

パターンが長い場合、Boyer-Moore algorithmまたはHorspool's algorithmのようなバリアントが一般的に高速です。 Boyer-Mooreアルゴリズムは、大きなアルファベットにはあまり適していません。テキストが完全なUnicode範囲になることができる場合は、かなり大きなシフトテーブルを使用しますが、テキストがASCIIまたはlatin1の場合、ルックアップテーブルの余分なスペースは小さくなります。大きなアルファベットの場合は、KMPもお勧めします。

関連する問題