文字列の類似性を判断するためにkdツリーを使用するにはどうすればよいですか？

Question

私は文字列の類似性の問題、すなわち文字列と知識ベースに対してk-最近傍点を利用しようとしています。私は与えられた文字列に似たk個の文字列を出力したいと思います。このk-nearest neighbor lookupを効率的に行うためにkd-treesを利用する方法を説明するチュートリアルはありますか？文字列の長さは20文字を超えてはなりません。

Answer 1

おそらく、私が1年ほど前に読んだ最もホットなブログ投稿の1つ：Levenstein Automata。その記事を見てください。アルゴリズムの説明だけでなく、それに続くコードも提供します。技術的にはkdツリーではありませんが、現実世界で遭遇する文字列照合アルゴリズムや辞書訂正アルゴリズムにはかなり関連しています。

また、BK-treesについての別のブログ記事があります。これは、文字列の誤った一致や誤字がある文字列検索の方がはるかに優れています。ここにはBK-treeのソースコードを含む別のリソースがあります（これは正確性や適切な実装を検証できません）。