2

我必须在源字符串和一组模式字符串之间执行模糊匹配。这种匹配由公式 1 - D(I,P) / max(length(I),length(P))
给出，其中

  • 我是输入字符串
  • P 是一个模式字符串
  • D(I,P) 是 I 和 P 之间的 levenshtein 距离。

一旦我找到了最大化这个分数的 P，我想要 I 和 P 的公共部分之间的映射

例如：如果 I="sunday" 和 P="saturday"，则映射将类似于以下对的列表：
{{0, 0}, {1, 3}, {3, 5}, {4 , 6}, {5, 7}}
因为常见的字符有 's', 'u', 'd', 'a' 和 'y'

在这篇 wikipedia article 中，可以很容易地找到一种计算 levenshtein 距离的实现，但我并不完全清楚如何从它描述的过程中构建的矩阵中获取映射。任何人都可以启发我吗？

谢谢

4

2 回答 2

2

您作为示例提供的映射根本没有包含我所看到的编辑距离，因为它只是在寻找常见字符。也许我误解了你，但你不需要编辑距离矩阵来映射常用字符；您唯一会查看编辑距离的时间是在 D(I,P) 计算期间以确定得分最高的模式字符串。要生成您作为示例给出的映射，只需遍历两个字符串即可确定用于识别对的字符索引。

于 2010-12-08T05:58:06.580 回答
0

从名为“source”和“destination”的同一数组的两个副本开始，它们是枚举的源字符串中的位置。删除从两个数组中删除相应的元素，并减少目标数组中的后续值。插入增加目标数组中的以下值。然后只需压缩两个数组并生成您的地图。

于 2010-12-04T20:35:49.830 回答