我正在嘗試計算字符串與集合的編輯距離以找到最接近的匹配。我目前的問題是這個集合非常大(大約25000個條目),所以我不得不將它縮小到只有相似長度的字符串,但仍然只能縮小到幾千個字符串,而且這個速度仍然很慢。是否有數據結構允許快速查找類似的字符串,或者有另一種方法可以解決此問題嗎?快速比較字符串與Java中的集合
5
A
回答
8
聽起來像BK-tree可能是你想要的。這裏有一篇文章討論它們:http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。 A quick Google產生一些Java實現。
2
如果您的「類似」條件定義了總排序,您應該能夠定義一個比較器並使用TreeSet來查找最接近的匹配(例如,使用天花板和地板方法)。
6
Levenshtein自動機允許從一個大字典中快速選擇一組單詞,使它們在給定單詞的給定Levenshtein距離內。 (2002)Fast String Correction with Levenshtein-Automata。
相關問題
- 1. Java中的快速字符串集合
- 2. 快速比較字典的方法比使用集合
- 3. 字符數組的快速比較?
- 4. 爲什麼Java中的字符串比較(CompareTo)比C#更快?
- 5. 的java字符串比較
- 6. 比較字符串或字節數組的速度更快嗎?
- 7. 如何比較字符與C中給定字符的集合?
- 8. 在快速單元測試中比較字符串
- 9. 字符串/字符比較與python中的按位比較
- 10. 數字比較比字符串比較更快嗎?
- 11. Java字符串比較
- 12. Java字符串比較
- 13. Java比較字符串
- 14. 與字符串比較字符串值
- 15. nsis中的複合字符串比較
- 16. 字符串比較比字符串長度更快嗎?
- 17. 比較datetimepicker與字符串
- 18. 與字符串比較
- 19. 比較字符串與document.getElementById()
- 20. 比較Java中的字符串
- 21. 比較java中字符串的索引
- 22. Java中的字符串比較...?
- 23. Java中的字符串比較
- 24. Java中字符串的比較
- 25. 使用Dalvik VM進行字符串快速比較?
- 26. 如何快速比較很多字符串?
- 27. 爲什麼整數比較比字符串比較快?
- 28. 通過子串快速過濾字符串集合?
- 29. 與整數比較相比,爲什麼字符串比較如此之快?
- 30. 比較常量字符與字符串
你現在怎麼做?你能顯示一些代碼嗎? – 2012-02-04 08:12:33
定義「相似」。 – 2012-02-04 08:23:59
類似的,我的意思是比較常見的拼寫錯誤,如「exanple」和「example」或「怪異」和「奇怪」。 – Lezan 2012-02-04 09:01:30