java - 500,000 通りの名前 - 高速検索を実装するために使用するデータ構造とは?

Question

そのため、通りの名前がたくさんあります。それらはファイルに入っています。サーバーを本番環境で起動するときに、おそらくそれらをキャッシュします。検索は、次のようにオートコンプリートである必要があります。たとえば、「lang」と入力すると、langstr、langestr のように 8 件のヒットが表示されます。等

Answer 1

あなたが探しているのは、ある種の圧縮されたトライ表現です。簡潔な試行またはDAWGを開始点として検討することをお勧めします。これらは優れた効率と非常に優れたスペース使用を提供するためです。

お役に立てれば！

Answer 2

オートコンプリートは通常、次のいずれかを使用して実装されます。

• 木。ツリー構造 (プレフィックス ツリー、サフィックス ツリー、dawg など) で検索可能なテキストをインデックス化することにより、メモリ ストレージを犠牲にして非常に高速な検索を実行できます。ツリー トラバーサルは、近似マッチングに適合させることができます。
• パターン分割。テキストをトークン (ngram) に分割することにより、単純なハッシュ スキームを使用してパターンの出現を検索できます。
• フィルタリング。一連の潜在的な一致を見つけ、順次アルゴリズムを適用して各候補をチェックします。

後者の概念のいくつかを実装する Java オートコンプリート ライブラリである fully を見てください。