在 Java 中快速比较字符串和集合
我正在尝试计算字符串与集合的编辑距离以找到最接近的匹配。我当前的问题是该集合非常大（大约 25000 个项目），因此我必须将集合缩小到长度相似的字符串，但这仍然只能将其缩小到几千个字符串，而且这仍然非常慢。是否有一种数据结构可以快速查找相似的字符串，或者是否有其他方法可以解决这个问题？
I am trying to calculate edit distances of a string against a collection to find the closest match. My current problem is that the collection is very large (about 25000 items), so I had to narrow down the set to just strings of similar lengths but that still would only narrow it down to a few thousand strings and this still is very slow. Is there a datastructure that allows for a quick lookup of similar strings or is there another way I could address this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
听起来 BK-tree 可能就是你想要的。这是一篇讨论它们的文章： http://blog .notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。 快速 Google产生一些 Java 实现。
Sounds like a BK-tree might be what you want. Here's an article discussing them: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees. A quick Google yields some Java implementations.
编辑自动机允许从大型词典中快速选择一组单词，使它们与给定单词在给定的编辑距离内。
请参阅：Schulz K、Mihov S. (2002) 快速字符串更正编辑自动机。
Levenshtein Automata allow for fast selection of a set of words from a large dictionary such that they are within the given Levenshtein distance from a given word.
See: Schulz K, Mihov S. (2002) Fast String Correction with Levenshtein-Automata.
如果您的“相似”标准定义了总排序，那么您应该能够定义一个比较器并使用 TreeSet 来查找最接近的匹配（例如使用上限和下限方法）。
If your criteria for 'similar' define a total ordering, you should be able to define a Comparator and use a TreeSet to find the closest matches (eg using the ceiling and floor methods).