python - 具有权重/邻接惩罚的编辑距离

Question

我正在使用字符串编辑距离 (Levenshtein-distance) 来比较眼动追踪实验的扫描路径。 (现在我在 R 中使用 stringdist 包)

基本上，字符串中的字母指的是 6x4 矩阵中的(注视)位置。矩阵配置如下:

     [,1] [,2] [,3] [,4]
[1,]  'a'  'g'  'm'  's' 
[2,]  'b'  'h'  'n'  't'
[3,]  'c'  'i'  'o'  'u'
[4,]  'd'  'j'  'p'  'v'
[5,]  'e'  'k'  'q'  'w'
[6,]  'f'  'l'  'r'  'x'

如果我使用基本的 Levenshtein 距离来比较字符串，a 的比较和 g在字符串中给出与 a 的比较器相同的估计值和 x .

例如:

'abc' compared to 'agc' -> 1
'abc' compared to 'axc' -> 1

这意味着字符串是等(不)相似

我希望能够以一种在矩阵中包含邻接关系的方式对字符串比较进行加权。例如。 a 之间的距离和 x应该比 a 之间的权重更大和 g .

一种方法是计算矩阵中一个字母到另一个字母的“步行”(水平和垂直步长)，然后除以最大“步行”距离(即从 a 到 x )。例如。 “步行”距离a至 g将是 1 并且来自 a至 x它将是 8，导致权重分别为 1/8 和 1。

有没有办法实现这个(在 R 或 python 中)？

Answer 1

您需要一个版本的 Wagner-Fisher algorithm在其内部循环中使用非单位成本。 IE。其中通常的算法有+1，使用+del_cost(a[i])等，定义del_cost，ins_cost 和 sub_cost 作为采用一个或两个符号的函数(可能只是表查找)。