10

我将“块转置”放在引号中，因为我不知道技术术语是否或应该是什么。只知道该过程是否有技术术语将非常有帮助。

关于编辑距离的Wikipedia 文章为这个概念提供了一些很好的背景。

通过考虑“块转置”，我的意思是

Turing, Alan.

应该匹配

Alan Turing

比匹配更接近

Turing Machine

即距离计算应该检测文本的子串何时在文本中简单地移动。常见的 Levenshtein 距离公式并非如此。

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

4

6 回答 6

3

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

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

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

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

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

于 2009-05-19T16:21:01.017 回答
2

查看 Jaccard 距离度量 (JDM)。这是一个老的但很好的东西，非常擅长处理令牌级别的差异，例如姓氏在前，名字在后。对于两个字符串比较，JDM 计算只是两个字符串共有的唯一字符数除以它们之间的唯一字符总数（换句话说，联合上的交集）。例如，给定两个参数“JEFFKTYZZER”和“TYZZERJEFF”，分子为 7，分母为 8，得出的值为 0.875。我选择的字符作为标记并不是唯一可用的，顺便说一句，也经常使用 n-gram。

于 2009-08-19T22:57:15.873 回答
2

编辑距离的最简单和最有效的现代替代方法之一称为归一化压缩距离或 NCD。基本思想很容易解释。选择用您的语言实现的流行压缩器，例如zlib。然后，给定字符串A和字符串B，让C(A)是 A 的压缩大小，C ( B)是 B 的压缩大小。令AB表示“ A与B连接”，因此C(AB)表示“ A与B连接”的压缩大小。接下来，计算分数

( C(AB) - 最小值( C(A) , C(B) )) / 最大值( C(A) , C(B) )

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

http://arxiv.org/abs/cs/0312044 "Clustering by Compression"

https://github.com/rudi-cilibrasi/libcomplearn C language implementation

There are many other implementations and papers on this subject in the last decade that you may use as well in other languages and with modifications.

于 2015-07-09T06:58:08.493 回答
1

我认为您正在寻找恰好用于名称匹配的Jaro-Winkler 距离。

于 2009-05-18T15:26:23.557 回答
1

您可能会发现压缩距离对此很有用。请参阅我为非常相似的问题给出的答案。

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

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

对于小字母表（例如 DNA），您通常会维护一个向量来存储每个可能的 k 元组的计数，而不是一个排序列表，尽管当字母表是任何字符时这是不切实际的——对于 k=4，你会需要一个 256^4 数组。

于 2009-05-19T15:57:38.300 回答
0

我不确定你真正想要的是编辑距离——它只适用于字符串——或语义距离——选择最合适或相似的含义。您可能想查看信息检索中的主题，以了解如何区分给定特定术语或短语的最合适的匹配术语/短语。从某种意义上说，您正在做的是比较非常短的文档而不是字符串。

于 2009-05-18T15:11:28.143 回答