识别字符串中的相似性

我正在研究一个允许导入的文件被本地化为其他语言的系统。识别字符串中的相似性

这主要是一个私人项目获得MVC3，的EntityFramework，LINQ，诸如此类的窍门。因此，我喜欢做一些疯狂的事情来增加最终结果，其中之一就是对类似字符串的认识。

想象一下，你有一个字符串下面的列表 - 从游戏我已经在过去曾与借来的：

正如你可以看到，当用户已经翻译了第4串，以下4个份额有很多相似之处，在这种情况下：

考虑的第一个4串确实已经翻译，当用户从列表中选择5号线，是什么样的算法或技术可以用来向用户显示“类似字符串”的子标题下的第一个字符串（以及其他可能的字符）？

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

有趣的问题。我不知道该从哪里开始回答这个问题，但是生病了，看着。 – Gallen

编辑距离。其品种很多。而且相当直接。如果矩阵变大，可能在计算上很昂贵。 – DarthVader

你可以连接所有的字符串，然后通过空格分隔（使用正则表达式），然后用'.Distint（）'将其转换并用替换执行翻译。与此相关的问题是，并非所有的语言都会逐字翻译。 – Jay

你可以看着Levenshtein Distance。低于某个阈值的那些将被认为是相似的。两个相同的字符串的距离为零。

有一个C＃实现，除其他语言，在Rosetta Code。

2012-10-22 20:20:26 keyboardP

+1，只是推荐Levenshtein，你打我吧 – CaffGeek

我我确实碰到过这个算法，但坦率地忘记了这个名字，谢谢。我很想知道更多的答案，所以我会留下这个开放的一点;） –

这很好，我也有兴趣看看别人是否有另一种解决方案:) – keyboardP

这将取决于数据的大小以及丰富的词汇量。这里的第一个想法：在地图上标注的单词为字符串然后词的对另一个地图为字符串也许如果数据不是字符串三胞胎为字符串的巨大的地图。删除指向单个字符串的映射（这将显着减少三元映射的数量）。将结果字典保存在磁盘或数据库中，如果构建它需要时间。

现在给出一个字符串，你应该能够快速地将它分成单词，单词对和三元组，并查找与之相关的所有字符串。你将需要发挥重量来匹配三字符匹配与四字匹配。即是 “我是一个老人”，更接近“一位老人吃了胡萝卜”或“男人用箭射死了老狗”（听起来像三胞胎比赛更重要）。

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

2012-10-22 20:25:40

回答