识别字符串相似性

Question

我正在开发一个系统，允许将导入的文件本地化成其他语言。

这主要是为了熟悉MVC3、EntityFramework、LINQ等技术而进行的私人项目。因此，我喜欢做一些疯狂的事情来调整最终结果，其中之一就是识别相似的字符串。

想象一下你有以下字符串列表 - 借鉴自我过去使用过的游戏：

如您所见，一旦用户已经翻译了前4个字符串，接下来的4个字符串共享很多相似之处，在这种情况下包括：

考虑到前4个字符串确实已经被翻译，当用户从列表中选择第5个字符串时，我可以使用什么算法或技术向用户显示"相似字符串"的子标题下的第1个字符串（以及可能的其他字符串）？

编辑-关于Levenshtein距离的一点注释： 我目前正在针对数据库中的10k个字符串。Levenshtein距离逐个比较字符串，因此在这种情况下有10k x (10k -1)种可能的组合。我该如何以可行的方式解决这个问题？是否有比这个特定算法更好的解决方案？

- Lennard Fonteijn

---

有趣的问题。我不知道从哪里开始回答，但我会待在这里观察。 - Grahame A

编辑距离有许多种类，而且相当直观。如果矩阵变得很大，计算成本可能会很高。 - DarthVader

你可以将所有字符串连接起来，然后使用正则表达式按空格拆分，再使用.Distinct()进行Linq操作，并使用替换进行翻译。但问题在于，并非所有语言都是逐字翻译的。 - Jay

@Jay 没关系，它应该帮助用户进行翻译过程，而不是全部替他完成...至少现在是这样:p - Lennard Fonteijn

Answer 1

你可以研究Levenshtein Distance。低于某个阈值的将被视为相似。两个完全相同的字符串距离为零。

Rosetta Code上有C#实现，以及其他语言。

- keyboardP

---

+1，我刚想推荐Levenshtein算法，你比我先了。 - CaffGeek

确实，我碰到过那个算法，但老实说我忘记了它的名字，谢谢。我很好奇还有哪些答案，所以我会把这个问题保持开放一段时间 ;) - Lennard Fonteijn

没问题，我也很想看看是否有其他解决方案 :) - keyboardP

更多信息：我目前的目标是在数据库中处理10k个字符串。Levenshtein距离逐个比较字符串，因此在这种情况下有10k x（10k-1）个可能的组合。我该如何以可行的方式解决这个问题？ - Lennard Fonteijn

@LennardFonteijn - 你可以在T-SQL中执行它 https://dev59.com/3nRB5IYBdhLWcg3wpopm 当用户选择一个字符串时，你可以将该字符串与数据库中的所有其他字符串进行比较。然后仅返回那些低于某个阈值的值。 - keyboardP

Answer 2

这将取决于数据的大小和词汇量的丰富程度。 以下是第一个想法： 建立单词到字符串的映射 然后建立另一个单词对到字符串的映射 如果数据不是很大，可以再建立一个字符串三元组到字符串的映射。 删除指向单个字符串的映射（这将大大减少三元组映射的数量）。 如果构建它需要时间，将结果字典保存在磁盘或数据库中。

现在，给定一个字符串，您应该能够快速将其拆分为单词、单词对和三元组，并查找与之相关的所有字符串。您需要尝试给三元组匹配和四个单词匹配赋予权重。例如，“我是一个老人”更接近于“一个老人吃了一根胡萝卜”还是“男人用箭杀死了老狗”（听起来三元组匹配更重要）。

更新：如果这是在Microsoft SQL Server数据库中，您可以尝试使用全文搜索功能。我从未尝试过。 您还应该看看Lucene。

- MK.