Java中的模糊字符串搜索，包括单词交换

Question

4

我是一名Java初学者，尝试编写一个程序，将输入与预定义字符串列表进行匹配。我已经研究了Levenshtein距离算法，但是遇到了以下问题：

例如，如果我的输入是“牛排片”，我希望它与“牛肉片”匹配。问题在于，根据Levenshtein距离算法，“牛排片”更接近于“金枪鱼肉片”，当然这是错误的。

我应该使用类似Lucene这样的工具吗？是否可以在Java类中使用Lucene方法？

谢谢！

- abroekhof

2

Lucene可能不是正确的方法（它的目的是在一组文档中查找匹配项，而不是单个文档），但它构建和搜索索引的方式可能对您有所帮助（特别是“相关性”算法）。以下问题将有助于人们给出一个好的答案：您的输入是什么？您的单词列表有多长？您需要处理拼写错误吗？ - Anon

感谢反馈：我的输入将是从XML文档解析出的字符串。不应该有太多拼写错误，但如果确实发生了，覆盖它们会很好。我的字符串列表大约有1000个。 - abroekhof

3个回答

1

Lucene支持基于Levenshtein距离的模糊搜索。

但是Lucene旨在搜索一组文档，而不是字符串搜索，因此Lucene可能对您来说有些过度。还有其他可用的Java实现。请查看http://www.merriampark.com/ldjava.htm。

- Nishan

谢谢您的回复，Nishan。我尝试了您上面链接的Levenshtein距离Java实现，但遇到了我在问题中所述的问题。 - abroekhof

1

应该可以将Levenshtein距离应用于单词而不是字符。然后，为了匹配单词，可以再次在字符级别上应用Levenshtein，以便“牛肉片”中的“filet”与“beef fillet”中的“fillet”匹配。

- Ingo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anon · Accepted Answer

你需要计算搜索词与输入字符串的相关性。Lucene已经内置了相关性计算，这篇文章可能是理解它们的好起点（我只是浏览了一下，但它似乎比较权威）。

基本过程如下：

初始化：将搜索词进行分词，并将它们存储在一系列HashSet中，每个词一个集合。或者，如果你想给每个单词赋予不同的权重，则使用HashMap，其中单词是键。
处理：对每个输入字符串进行分词，并探查每组搜索词集合，以确定它们与输入的接近程度。有关算法的描述，请参见上文。

处理拼写错误的一个简单技巧是：在初始化期间，创建包含搜索词潜在拼写错误的集合。Peter Norvig在他的博客文章“如何编写拼写校正器”中描述了这个过程（它使用Python代码，但Java实现也是可能的）。