2

一連の単語 (「辞書」) があり、新しい単語が与えられた場合、辞書から最も近い単語を見つける必要があります。(実際には可変長の抽象的な「文字」のシーケンスであるため、「単語」をキーワードとして使用しています)。

メトリックとしてレーベンスタイン距離の一般化を使用しています。一般化する必要がある理由は、特定の 2 文字を交換する特定の「コスト」が必要だからです。 'a' と 'c' を交換することにより、より少なくなります。私の一般化はまだメトリックであることを自分自身に納得させる必要があると思います.

現在、単純な線形検索を使用しています。つまり、辞書内のすべての単語を繰り返し処理し、最小距離を追跡しています。より効率的な方法を探しています。

最近傍探索の方法について読み始めましたが、概念上の主な難点は、「ポイント」(単語) が視覚化できる空間に埋め込まれておらず、次元などを持つベクトルではないことです。

それを念頭に置いて、どのアルゴリズムを探すべきかについてアドバイスを聞きたいと思います。

4

1 に答える 1

1

あなたの質問をもう一度言語化して、考えられる答えを教えてください。あなたのデータセットを見なければ、どれがあなたにとってより良いかわかりません.

与えられた 2 つの単語から単語間の距離を求めるアルゴリズムは既にあります。これは、これらの単語間のパスのレーベンスタイン距離に基づいており、コストにいくつかの変更が加えられています。また、辞書全体を検索することなく、特定の単語に最も近い単語を見つけたいと考えています。

私が試みる最も簡単なことは、あなたの単語から始めて、辞書で最も近い単語が見つかるまで、可能なすべての修飾セットを検索することです. 変更された幅優先検索が必要です。ある種のhttp://en.wikipedia.org/wiki/Priority_queue(0, your_word) (ヒープは簡単に実装できます)に唯一のエントリとして保存し、現在の最善の解決策としてランダムな辞書単語までの距離を取得します。プライオリティ キューが空ではありません:

Take the lowest cost element out.
If it is more expensive than your best solution:
    stop, return your best.
For each possible one step modification of that word:
    if the new word is in the dictionary and is lower cost than your best:
        improve best estimate
    else:
        store (new_cost, new_word) in the priority queue

これにより、元の単語から始まる検索セットが指数関数的に増加します。しかし、辞書に近くの単語がある場合は、かなり迅速に見つける必要があります。このルートに行く場合は、検索スペースに上限を設けてからあきらめることをお勧めします。

これは最適な解決策とはほど遠いかもしれませんが、プログラミングして試すのはそれほど難しいことではありません。

于 2011-04-26T16:12:25.657 に答える