algorithm - 是否有考虑 "chunk transposition"的编辑距离算法？

Question

我把“chunk transposition”放在引号里是因为我不知道这个技术术语应该是什么。只要知道该过程是否有一个技术术语就会非常有帮助。

Wikipedia article on edit distance为这个概念提供了一些很好的背景。

考虑到“ block 转置”，我的意思是

Turing, Alan.

应该匹配

Alan Turing

比匹配更接近

Turing Machine

即距离计算应该检测文本的子字符串何时在文本中简单地移动。常见的 Levenshtein 距离公式不是这种情况。

字符串最多只有几百个字符——它们是作者姓名或作者姓名列表，可以采用多种格式。我不是在做 DNA 测序(尽管我怀疑这样做的人会对这个主题有所了解)。

Answer 1

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

例如，您可以首先通过确保所有分隔符都是空格或您喜欢的任何其他内容来统一您的字符串，这样您就可以将“Alan Turing”与“Turing Alan”进行比较。然后拆分其中一个字符串并执行精确的字符串匹配算法(如 Horspool -算法)，将这些部分与另一个字符串进行匹配，计算匹配子字符串的数量。

如果您想找到仅相似但不相等的匹配项，可以使用类似 local alignment 的匹配项可能更合适，因为它提供了描述相似性的分数，但引用的 Smith-Waterman-Algorithm 可能对您的应用程序来说有点矫枉过正，甚至不是可用的最佳局部对齐算法。

根据您的编程环境，可能已经有可用的实现。我个人曾与 SeqAn 合作过最近，这是一个用于 C++ 的生物信息学库，绝对提供了所需的功能。

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