提问人： 提问时间：1/13/2018 更新时间：1/13/2018 访问量：73
哪种算法可以匹配集合中最相似的字符串？
Which algorithm to match most similar string from a set?
问：
假设我有一个包含书名的书籍数据库。对于来自 eBay 或 Craigslist 或其他类似网站的给定列表，我想将其标题字符串与我数据库中的所有书名进行比较，以尝试找到匹配项。
不太可能有确切的字符串相等，因为这些网站上的用户喜欢在他们的列表标题中包含“完美条件”和“快速发货”等内容以吸引买家。
我应该使用什么算法来执行这种类型的关联？我知道 n-gram 和 Levenshtein 距离，但我不知道哪个能做最准确的工作。
对于各种适用的算法，它们的计算性能如何比较？使用多种算法并平均其结果以平衡其优势和劣势是否有意义？是否有可能设定最低置信度？我宁愿没有比赛，也不愿有质量很差的比赛。
答：
0赞
Prune
1/13/2018
#1
对于手头的任务，我认为通过一些预处理可以获得最佳结果：删除常见的“空”短语（那些你不想看到的短语），这样你就有一个较小的标题，很可能将实际标题作为主要部分。
下一步取决于数据库大小和请求开销。如果这些标题很便宜，那么从你的数据库中提取一个标题列表，看看eBay文本中存在哪些标题（许多语言的单个命令）。如果这对您有用，那么即使是预处理也可能是不必要的开销。
如果完整的数据库列表很昂贵，但数据库索引得很好，那么请尝试从 eBay 文本中获取可能的 n-gram（例如，2-3 个单词），并在数据库中搜索它们。您应该获得相对较少的返回值，然后您可以尝试与完整的 eBay 文本进行匹配。
评论
0赞
1/14/2018
我不知道。我怀疑在没有进一步处理的情况下是否真的可以工作，例如将所有内容更改为相同的大小写并剥离前导和后导空格。同时将多个相邻空间替换为单个空间。但这就是我试图用算法解决的问题。在大多数情况下，我应该能够找到一个相当接近的匹配项。哪种算法最能为我的用例定义“亲密度”？
0赞
Prune
1/14/2018
LCS -- 最长的公共子字符串怎么样？这肯定已经在 SO 和在线其他地方得到了足够多的解决。
上一个：如何迭代平衡的二进制字符串？
下一个：单元测试应该测试多少个方案？
评论