文字列の類似性の問題にk最近傍法を利用しようとしています。つまり、文字列と知識ベースが与えられた場合、与えられた文字列に類似したk個の文字列を出力したいと思います。kdツリーを利用して文字列のこのk最近傍ルックアップを効率的に行う方法を説明するチュートリアルはありますか？文字列の長さは20文字を超えてはなりません。
3641 次
1 に答える
8
おそらく、私が1年ほど前に読んだ最もホットなブログ投稿の1つ、LevensteinAutomataです。その記事を見てください。アルゴリズムの説明だけでなく、従うべきコードも提供します。技術的には、これはkdツリーではありませんが、現実の世界で遭遇/使用する可能性のある文字列照合および辞書修正アルゴリズムに非常に関連しています。
彼はまた、 BKツリーに関する別のブログ投稿を持っています。これは、文字列のあいまい一致と、スペルミスのある文字列ルックアップではるかに優れています。これは、 BKツリーのソースコードを含む別のリソースです（これは、正確性や適切な実装を確認できません）。
于 2011-04-17T22:26:30.930 に答える