2

検索語と照合したい文字列がたくさんあります。

例：

folks
fort
garage
grabbed
grandmother
habit
happily
harry
heading
hunter

文字列「ha」と、文字列が「ha」で始まるリストの先頭（この場合は「habit」）を返すアルゴリズムを検索したいと思います。

もちろん、リストが膨大なので、一人ずつ行くことはしません。リストを並べ替えたり、この種の検索を高速化する構造にリストを配置したりするために、いくつかの前処理を行うことができます。

助言がありますか？

4

5 に答える 5

3

ある種のソートされた構造が必要です。TreeMap または Radix Tree を使用して問題を解決できます (Radix を使用すると、スペースがいくらか節約されます)。このオーバーヘッドは、ソート操作またはソートされたデータ構造への挿入のオーバーヘッドになります。ただし、バイナリ検索をソートすると、logN+1検索パフォーマンスが最悪になります。

注目すべきLuceneは、基数ツリーを使用しています

于 2013-01-10T22:07:55.760 に答える
1

あなたはいつでもパトリシアの木を見ることができます。彼らはこの種のものにほぼ完全に適しています。

于 2013-01-10T22:08:56.943 に答える
1

トライはあなたが探しているものです。

于 2013-01-10T22:09:10.773 に答える
1

あなたの投稿では、未回答の質問が多すぎます。私の解釈では、順序付けられていない単語のリストから辞書を作成したいと考えています。しかし、検索するときha、本当に欲しいものは何でしょうか?

欲しいですか

  1. ha?で始まる最初の単語

  2. ha?で始まる最初の単語のインデックス

  3. で始まるすべての単語に簡単にアクセスするには、ha?

1および/またはが必要な場合は、 trie3と言う人が正しいです。（私が提供するリンクには、読みやすい実装があります）。

ご希望の場合2は、ユースケースについてお話しいただけますか? そうでない場合は、文字列検索アルゴリズムの使用を検討しています。詳細がなければ、より正確なアドバイスを提供することは困難です。

于 2013-01-10T22:52:18.990 に答える
0

あなたの質問には多くのあいまいな領域があります。要件によっては、Rabin-Karp文字列検索方法が役立つ場合があります。

于 2013-01-12T13:35:17.840 に答える