c# - 识别字符串中的相似性

Question

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

这主要是一个私人项目，用于掌握 MVC3、EntityFramework、LINQ 等。因此，我喜欢做一些疯狂的事情来为最终结果增添趣味，其中之一就是识别相似的字符串。

想象一下，您有以下字符串列表 - 从我过去使用过的游戏中借来的：

如您所见，一旦用户翻译了前 4 个字符串，以下 4 个字符串有很多相似之处，在本例中：

考虑前 4 个字符串确实已经翻译，当用户从列表中选择第 5 个字符串时，我可以使用哪种算法或技术在“类似”的子标题下向用户显示第一个字符串（以及可能的其他字符串）字符串”？

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

score 5 · Accepted Answer

您可以查看Levenshtein Distance。低于某个阈值的将被视为相似。两个相同的字符串的距离为零。

在Rosetta Code上有一个 C# 实现以及其他语言。

score 0 · Accepted Answer

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

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

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

2 回答 2