文字列のリストをすばやくフィルタリングして、指定した文字列を含むサブセットを取得する方法を知っていますか? 明らかな実装は、リストを反復処理し、各文字列に検索文字列が含まれているかどうかを確認することです。検索を高速化できるように、文字列リストにインデックスを付ける方法はありますか?
3400 次
6 に答える
13
ウィキペディアの記事には、部分文字列にインデックスを付ける方法がいくつかリストされています。あなたが持っている：
于 2009-08-19T11:11:14.330 に答える
2
はい、たとえば、文字列内のすべての文字の組み合わせのインデックスを作成できます。「he」、「el」、「ll」、「lo」のインデックスには「hello」などの文字列が追加されます。文字列「hell」を検索するには、「he」、「el」、および「ll」インデックスのすべてに存在するすべての文字列のインデックスを取得し、それらをループして文字列の実際の内容を確認します。
于 2009-08-19T11:09:02.617 に答える
1
コレクションを前処理できれば、さまざまなことを実行できます。
たとえば、すべての文字列のサフィックスを含むトライを作成し、それを使用して非常に高速なマッチングを行うことができます。
于 2009-08-19T11:12:58.053 に答える
1
同じテキストを繰り返し検索する場合は、サフィックス ツリーを使用する価値があります。慎重に適用すれば、ほとんどの文字列問題に対して線形時間処理を実現できます。そうでない場合、実際には、ハッシュに基づいており、予想される時間に線形であるRabin-Karpよりもはるかに優れた処理を行うことはできません。
サフィックス ツリーには、自由に利用できる実装が多数あります。たとえば、このC 実装を参照するか、Java の場合はBiojavaフレームワークを調べてください。
于 2009-08-19T11:25:27.063 に答える
0
データおよび/または検索語について追加のアプリオリな知識がない限り、実際には実行可能なものではありません。たとえば、文字列の先頭でのみ一致を検索している場合、文字列を並べ替えてのみ検索語の範囲内のものを調べます (または、それらを二分木に保存して、一致する可能性のあるブランチのみを調べます)。同様に、潜在的な検索用語が限られている場合は、最初の入力時に文字列に対して可能なすべての検索を実行し、一致する用語と一致しない用語のテーブルを保存するだけで済みます。
そういうのは別として、基本的にはただ繰り返すだけです。
于 2009-08-19T11:08:08.173 に答える
0
これは、部分文字列が文字列の先頭にあるか、文字列のどこにでもあるかによって異なります。
それがどこにでもある場合は、リストが非常に大きく、より洗練されたインデックス作成ソリューションを構築する価値があるほど頻繁にクエリが発生しない限り、リスト全体を反復処理する必要があります。
部分文字列が文字列の先頭にある場合は簡単です。リストをソートし、バイセクトン検索で開始/終了を見つけ、そのサブセットを取得します。
于 2009-08-19T11:08:52.807 に答える