快速比較字符串與Java中的集合

我正在嘗試計算字符串與集合的編輯距離以找到最接近的匹配。我目前的問題是這個集合非常大（大約25000個條目），所以我不得不將它縮小到只有相似長度的字符串，但仍然只能縮小到幾千個字符串，而且這個速度仍然很慢。是否有數據結構允許快速查找類似的字符串，或者有另一種方法可以解決此問題嗎？快速比較字符串與Java中的集合

來源

2012-02-04 Lezan

你現在怎麼做？你能顯示一些代碼嗎？ – 2012-02-04 08:12:33

定義「相似」。 – 2012-02-04 08:23:59

類似的，我的意思是比較常見的拼寫錯誤，如「exanple」和「example」或「怪異」和「奇怪」。 – Lezan 2012-02-04 09:01:30

聽起來像BK-tree可能是你想要的。這裏有一篇文章討論它們：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。 A quick Google產生一些Java實現。

來源

2012-02-04 08:50:22 SimonC

謝謝我會查找並讓你知道它是怎麼回事，謝謝！ – Lezan 2012-02-04 09:07:56

是的，它需要一個不同的搜索實現，但它是完美的！謝謝！！ – Lezan 2012-02-05 11:16:42

如果您的「類似」條件定義了總排序，您應該能夠定義一個比較器並使用TreeSet來查找最接近的匹配（例如，使用天花板和地板方法）。

來源

2012-02-04 08:42:32

Levenshtein自動機允許從一個大字典中快速選擇一組單詞，使它們在給定單詞的給定Levenshtein距離內。（2002）Fast String Correction with Levenshtein-Automata。

來源

2012-02-04 10:32:52 kkm

快速比較字符串與Java中的集合

回答

相關問題