识别字符串中的相似性

Len*_*ijn 5 c# entity-framework localization similarity asp.net-mvc-3

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

这主要是一个私有项目,可以获得MVC3,EntityFramework,LINQ等等.因此,我喜欢做一些疯狂的事情来为最终结果增添趣味,其中一件事就是识别相似的字符串.

想象一下,你有以下的字符串列表 - 从我过去曾经使用过的游戏中借来的:

  • Megabeth:神圣的滚轮制服 - 包括头部,躯干和腿部
  • Megabeth:神圣的滚轮制服头
  • Megabeth:神圣的滚轮制服腿
  • Megabeth:神圣的滚轮制服躯干
  • Megabeth:PAX East 2012制服 - 包括头部,躯干和腿部
  • Megabeth:PAX East 2012 Uniform Head
  • Megabeth:PAX East 2012 Uniform Legs
  • Megabeth:PAX East 2012 Uniform Torso

正如您所看到的,一旦用户翻译了前4个字符串,以下4个字符串就有很多相似之处,在这种情况下:

  • Megabeth
  • 制服
  • 包括头部,躯干和腿部
  • 躯干

考虑前4个字符串确实已经翻译,当用户从列表中选择第5个字符串时,我可以使用什么样的算法或技术向用户显示"类似"的子标题下的第1个字符串(可能还有其他字符串)字符串"?

编辑 - 关于Levenshtein距离的一点评论:我目前正在瞄准数据库中的10k字符串.Levenshtein Distance比较每串的字符串,因此在这种情况下10k x(10k -1)可能的组合.我将如何以可行的方式处理这个问题?这个特定算法有更好的解决方案吗?

key*_*rdP 5

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

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