4

私の問題は、約20万語程度の語彙を持っていることです。ファイルのサイズは1.8MBです。ユーザーからの入力、たとえば** idが必要であり、可能なすべての一致を表示したいと思います。ここで、*は任意の文字AZにすることができます。（言った、メイドなど）

これを行うための最も効率的な方法に関するいくつかの提案を探しています。ユーザーがより具体的な文字を追加し、単語の一致をライブで更新できるようにするためです。

私の考えはRegexKitLiteを使おうと思ったのですが、信じられないほど遅い気がします。

ご入力いただきありがとうございます。

編集：これを達成するためにNSPredicatesを使用することは可能だと思いますか？

4

1 に答える 1

4

検索パフォーマンスを最適化するためにできることは、これらのワイルドカードの使用をどのように制限したいかによって大きく異なります。

正確に言えば、あなたのワイルドカードの特徴は何ですか?

  • プレフィックスのみのワイルドカード (m/.+foobar/)
  • サフィックスのみのワイルドカード (m/foobar.+/)
  • アトミックワイルドカード ( m/./)
  • 動的ワイルドカード ( m/.+/)

プレフィックスのみのワイルドカード

プレフィックス ツリーまたはDAWGを使用する

サフィックスのみのワイルドカード

サフィックス ツリーまたはDAWGを使用する

アトミックワイルドカード

実行する必要があるマッチの数を大幅に減らす 1 つの方法は次のとおりです。

単語コレクションからBKTreeを構築します。

ワイルドカードが固定長 (この場合は 1) である限り (および限り)、ワイルドカードの数である の正確な編集距離を持つノードを BKTree にクエリするだけnですn。従来の BKTree クエリには分散の上限があります。あなたの場合、追加の下限を導入して[n,1]、許容される分散の範囲を正確に(vs. 従来の )に絞り込み[0,n]ます。クエリ単語と正確に文字が異なる単語の配列を取得しますn。

クエリ**idの場合、可能な一致は次のとおりです。

  • void(2回追加)
  • laid(2回追加)
  • bad(交換1回、追加1回)
  • to(2回交換)

これらはクエリに対してまだ正しく一致していませんが、単語のコレクション全体の非常に小さなサブセットを表しています。

最後になりましたが、これらの結果に対して Regex マッチングを実行し、残りのすべての一致を返します。

BKTreeは、必要な比較/照合の数を(単語コレクション内のエントロピーに応じて)劇的に削減するために、いくつかの空間ヒューリスティックとしてレーベンシュタイン距離を導入します。

さらに最適化するには、複数の BKTreesを使用できます。

コレクションをサブセットに分割します。長さ の単語に対して 1 つのセット、長さ1に対して 1 つ、 に対して213つなど。次に、各サブセットから BKTree を構築します。クエリの場合、長さ 4 のBKTree**idをクエリします(ワイルドカードは文字のようにカウントされます)。 これは、ワイルドカードが として解釈される場合に適用されます。ただし、ワイルドカードが長さ 3 と 4のBKTreeを照会するように解釈される場合。
m/./m/.?/

BKTreesの代わりに、特に Scrabble スタイルのルックアップに特化したデータ構造 (Trie の特殊化) であるGADDAGを使用することもできます。

私が間違っていなければ、ワイルドカードも厳密に解釈する必要がありますm/./。

動的ワイルドカード

単語のコレクションに対して正規表現を実行するよりも、はるかに優れたソリューションは今のところ考えられません。

于 2011-06-12T21:13:13.027 に答える