是否有一个编辑距离算法考虑到“块转换”?

看看JacCard距离度量(JDM)。这是一个古老的古蒂,但古蒂是相当熟练的令牌级别的差异,如姓氏优先,名字最后。对于两个字符串比较符,JDM计算只是两个字符串共同拥有的唯一字符数除以它们之间的唯一字符总数(换句话说,是并集的交集)。例如,给定“jeffktyzzer”和“tyzzerjeff”这两个参数,分子为7,分母为8,得出的值为0.875。我选择字符作为令牌并不是唯一可用的,顺便说一句,N-grams也经常被使用。

对于您的应用程序,您可能应该考虑采用生物信息学中的一些算法。

例如,您可以首先通过确保所有分隔符都是空格或您喜欢的任何内容来统一字符串,这样您就可以将“alan turing”与“turing alan”进行比较。然后分割其中一个字符串并执行精确的字符串匹配算法(如 Horspool -算法)使用另一个字符串的片段,计算匹配子字符串的数目。

如果你想找到只相似但不相等的匹配项,沿着 local alignment 可能更合适,因为它提供了描述相似性的分数,但是引用的Smith Waterman算法可能对您的应用程序有点杀伤力,甚至不是可用的最佳局部对齐算法。

根据编程环境的不同,实现可能已经可用。我个人曾与 SeqAn 最近,它是一个C++的生物信息库,并提供了所需的功能。

嗯,这是一个相当抽象的答案,但我希望它能为你指明正确的方向,但遗憾的是,它不能为你提供解决问题的简单公式。

我想你在找 Jaro-Winkler distance 正是为了名称匹配。

你可能会发现压缩距离对这个很有用。见 an answer I gave for a very similar question .

或者可以使用基于k元组的计数系统:

1. 选择k的小值,例如k=4。
2. 将字符串的所有length-k子字符串提取到列表中。
3. 排序列表。(O(knlog(n)时间。)
4. 对要比较的另一个字符串执行相同的操作。现在有两个排序列表。
5. 计算两个字符串共享的k元组的数目。如果字符串的长度为n和m,则可以使用列表合并在o(n+m)时间内完成,因为列表是按排序顺序排列的。
6. k-元组的共同点是你的相似性得分。

对于较小的字母(例如DNA),您通常会保持一个向量来存储每个可能的k-元组的计数,而不是一个排序列表,尽管当字母表是任何字符时这是不实际的--对于k=4,您需要一个256^4数组。

编辑距离的最简单和最有效的现代选择之一被称为标准化压缩距离,或NCD。这个基本想法很容易解释。选择使用您的语言实现的常用压缩程序,例如 ZLIB . 那么,给定的字符串 一 字符串 乙 让 C(a) 压缩后的大小 一 和 C(b) 压缩后的大小 乙 . 让 抗体 平均 一 与连接 乙 “所以 C(ab) 表示“压缩尺寸” 一 与连接 乙 “。接下来,计算分数

( C(ab) -分钟( C(a) , C(b) (max) C(a) , C(b) )

这个值称为ncd( 一 , 乙 )并且测量类似于编辑距离的相似性,但支持更多形式的相似性,具体取决于您选择的数据压缩器。当然,zlib支持您描述的“块”样式的相似性。如果两个字符串相似,则连接的压缩大小将接近每个字符串的大小,因此分子将接近0,结果将接近0。如果两个字符串非常不同,则压缩大小加在一起将大致等于压缩大小的总和,因此结果将接近1。如果您已经可以访问像zlib这样的数据压缩程序,那么这个公式比编辑距离或几乎任何其他显式字符串相似性度量更容易实现。这是因为大多数“艰苦”的工作,如启发式和优化已经在数据压缩部分完成,这个公式简单地提取了大量类似的模式,它发现使用通用信息理论,这是不可知的语言。此外,对于您描述的几百字节大小的范围,此技术将比大多数显式相似性度量(如编辑距离)快得多。有关这方面的更多信息和示例实现,只需搜索规范化压缩距离(NCD),或查看以下文章和Github项目:

http://arxiv.org/abs/cs/0312044 “按压缩分类”

https://github.com/rudi-cilibrasi/libcomplearn C语言实现

在过去的十年中,有许多关于这个主题的其他实现和论文,您可以在其他语言中使用,也可以进行修改。

我不确定您真正想要的是编辑距离——它只对字符串有效——或者语义距离——选择最合适或者最相似的含义。您可能需要查看 information retrieval 对于如何区分给定特定术语或短语的最合适匹配术语/短语的想法。在某种意义上,您所做的是比较非常短的文档,而不是字符串。