9
文字列のリストをすばやくフィルタリングして、指定した文字列を含むサブセットを取得する方法を知っていますか？明白な実装は、リストを繰り返し、各文字列に検索文字列が含まれているかどうかをチェックすることです。検索がより速くできるように文字列リストをインデックスする方法はありますか？部分文字列による文字列コレクションの高速フィルタリング？
A
答えて
13
Wikipedia articleには、部分文字列をインデックスするいくつかの方法が記載されています。あなたは持っている：
- Suffix tree
- Suffix array
- N-gramインデクス、テキストのすべてのNグラムのための転置ファイル
- 圧縮接尾辞配列1
- FM-index
- LZ-インデックス
0
そうでもない、あなたのデータの追加の事前知識を持っている、および/または用語を検索しない限り、実行可能なのです何も、ない、 - たとえば、あなただけのあなたが、あなたの文字列のを開始で一致を検索する場合文字列をソートして、検索タームの範囲内のものだけを見ることができます（または、バイナリツリーに格納して、おそらく一致する可能性のある枝だけを見ることもできます）。同様に、潜在的な検索条件が限られている場合は、最初に入力された文字列に対してすべての可能な検索を実行してから、一致する単語と一致しない単語のテーブルを保存するだけです。
この種のもののほかに、基本的には反復スルーがあります。
0
これは、部分文字列が文字列の先頭にあるのか、文字列のどこにあるのかによって異なります。
リストが非常に大きく、クエリが十分に頻繁に行われ、より洗練されたインデックスソリューションを構築する価値がない限り、リスト全体を繰り返し処理する必要があります。
部分文字列が文字列の先頭にある場合、それは簡単です。リストをソートし、biseciton検索で開始/終了を探し、そのサブセットを取得します。
2
はい、たとえば、文字列内のすべての文字の組み合わせに対してインデックスを作成できます。 "hel"のような文字列が "he"、 "el"、 "ll"、 "lo"のインデックスに追加されます。文字列 "hell"を検索するには、 "he"、 "el"、および "ll"のすべてのインデックスに存在するすべての文字列のインデックスを取得し、それらをループして文字列の実際の内容をチェックします。
1
コレクションを前処理することができれば、さまざまなことができます。
たとえば、すべての文字列の接尾辞を含むトライを作成し、それを使って非常に高速なマッチングを行うことができます。
1
同じテキストを繰り返し検索する場合は、おそらくsuffix treeの価値があります。慎重に適用すると、ほとんどの文字列の問題に対して線形時間処理を実現できます。そうでない場合は、実際には、ハッシュに基づいたRabin-Karpよりもはるかにうまくやることができず、予想される時間内に線形です。
サフィックスツリーには、多くの自由に利用できる実装があります。たとえば、このC implementationを参照するか、Javaの場合Biojavaフレームワークを参照してください。
関連する問題
- 1. 部分文字列置換
もちろん、データを最適化する際の実際の効果については、データによって異なります。 – Amber
このアルゴリズムとは何ですか？私はこれを最近実装しました。これはかなり単純で、特定のユースケースのスピードが大幅に向上しました。 – ChrisInEdmonton
ああ、これはすべてのバイグラム（n-gram、n = 2）の逆インデックスと思われる。 – ChrisInEdmonton