有趣的問題。我在這一領域的經驗有限，但由于Levenshtein距離滿足三角形不等式，我認為必須有一種方法來計算到原點的某種絕對距離，以便在不與整個數據庫中的所有條目進行直接比較的情況下找到彼此鄰近的字符串。

在第26頁，他討論了基于kd樹和其他樹的相似性度量，但得出結論：However, general metric spaces do not provide the geometry required by

those techniques. For a general metric space with no other

assumptions, it is necessary distance-based to use a distance-based

approach that indexes points solely on the basis of their distance

from each other. Burkhard and Keller [35] offered one of the first

such index structures, now known as a BK-tree for their initials, in

1973. In a BK-tree, the metric is assumed to have a few discrete return values, each internal node contains a vantage point, and the

subtrees correspond to the different values of the metric.

關于BK樹如何工作的博客文章可以找到here。

在論文中，Skala繼續描述這個問題的其他解決方案，包括VP-trees樹和GH樹。第六章分析了基于Levenshtein編輯距離的距離。他還提出了一些其他有趣的弦距離度量。

總結

以上是生活随笔為你收集整理的字符串相似度匹配算法python_算法字符串相似度得分/哈希的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。