高速挿入検索

Question

私は10百万語句をすばやく検索しなければならないオートコンプリートを構築しており、いくつかの問題が発生しています。私の最初のアイデアは、ある種のトライ/三元ツリー構造を通過することでしたが、それらは厳密にプレフィックスマッチングであり、私のアプリケーションには十分ではありません（完全なインフィクスマッチングが必要です）。私は大きなソリューションSqlServer FullText Indexing、Lucene、Solr、Sphinxに移行しましたが、LuceneとSqlServer FullText Indexingはフルテキストではなく、素敵な機能（soundex、proximityなど）を前置しています。私はLevenshtein編集距離を助けることができる方法を考えようとしましたが、編集距離の高い単語をサポートするだけでなく、合理的に正確な方法を見つけることができませんでした（つまり、googleとogl。一般的なケースではしきい値を高くする）。

私の質問は、Google/bingなどの強力なハウスはどうしますか？彼らはちょっとしただけでそれを強制しますか？私はノーと思いますが、私はそれを支持することはできません。

助けていただけたら幸いです！

Answer 1

、次のような先頭と末尾にワイルドカードを使用することができます。

これは十分に速くないかもしれませんが、以前の「用語とインデックスを逆にして取得できるクエリ文字列を前処理できる場合は、プレフィックスのみのワイルドカード検索が必要な場合があります。それはまた "トリック：

acillateM 

Answer 2

Lucene/Solrはこれを非常に簡単に行うことができます。 Lucene/Solrの検索単位はTermです。これは通常は単語ですが、text analysisがどのように構成されているかによって実際にはほとんど何でもあります。

Solrには、これを実装する方法がたくさんあります（ngrams/shingles、facet prefix、TermsComponentなど）。最近のバージョンのSolrには、autocomplete based on spell checkingの特定のコンポーネントが付属しています。 「メタリカ」を含む「talli」を含むすべての単一ワードの用語を拾うでしょう

*talli* 

：あなたはLuceneのでqueryParser.setAllowLeadingWildcard(true);を有効にした場合

Answer 3

私は2013年に挿入検索が必要なときに、私はいくつかの調査をしました。私が見つけた唯一の方法はSphinx engineでした。一つは、それが目の点滅で問題を扱う中置検索この後

index tra 
{ 
    [...] 
    enable_star=1 
    min_infix_len=2 
} 

をサポートするように設定する必要があります。私はそれが検索する約200Kレコードだったと思います。私はメモリ内の検索ライブラリを模倣するためにローカルエンジンを使用しました。