Levenshtein 距离与邻接权重/惩罚

Question

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

基本上，字符串的字母指的是 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在一个字符串给出了相同的估计为comparicona和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 算法版本。即，通常的算法有+1、 use+del_cost(a[i])等，并定义del_cost,ins_cost和sub_cost作为采用一两个符号的函数（可能只是表查找）。

Answer 2

如果有人遇到同样的“问题”，这是我的解决方案。我对 Kyle Gorman 编写的 Wagner-Fischer 算法的 Python 实现做了一个附加组件。

附加组件是权重函数及其在 _dist 函数中的实现。

#!/usr/bin/env python
# wagnerfischer.py: Dynamic programming Levensthein distance function 
# Kyle Gorman <gormanky@ohsu.edu>
# 
# Based on:
# 
# Robert A. Wagner and Michael J. Fischer (1974). The string-to-string 
# correction problem. Journal of the ACM 21(1):168-173.
#
# The thresholding function was inspired by BSD-licensed code from 
# Babushka, a Ruby tool by Ben Hoskings and others.
# 
# Unlike many other Levenshtein distance functions out there, this works 
# on arbitrary comparable Python objects, not just strings.


try: # use numpy arrays if possible...
    from numpy import zeros
    def _zeros(*shape):
        """ like this syntax better...a la MATLAB """
        return zeros(shape)

except ImportError: # otherwise do this cute solution
    def _zeros(*shape):
        if len(shape) == 0:
            return 0
        car = shape[0]
        cdr = shape[1:]
        return [_zeros(*cdr) for i in range(car)]

def weight(A,B, weights): 
    if weights == True:
        from numpy import matrix
        from numpy import where
        # cost_weight defines the matrix structure of the AOI-placement
        cost_weight = matrix([["a","b","c","d","e","f"],["g","h","i","j","k","l"],
        ["m","n","o","p","q","r"],["s","t","u","v","w","x"]])

        max_walk = 8.00 # defined as the maximum posible distance between letters in 
                        # the cost_weight matrix

        indexA = where(cost_weight==A)
        indexB = where(cost_weight==B)

        walk = abs(indexA[0][0]-indexB[0][0])+abs(indexA[1][0]-indexB[1][0])

        w = walk/max_walk

        return w
    else:
        return 1

def _dist(A, B, insertion, deletion, substitution, weights=True):
    D = _zeros(len(A) + 1, len(B) + 1)
    for i in xrange(len(A)): 
        D[i + 1][0] = D[i][0] + deletion * weight(A[i],B[0], weights)
    for j in xrange(len(B)): 
        D[0][j + 1] = D[0][j] + insertion * weight(A[0],B[j], weights)
    for i in xrange(len(A)): # fill out middle of matrix
        for j in xrange(len(B)):
            if A[i] == B[j]:
                D[i + 1][j + 1] = D[i][j] # aka, it's free. 
            else:
                D[i + 1][j + 1] = min(D[i + 1][j] + insertion * weight(A[i],B[j], weights),
                                      D[i][j + 1] + deletion * weight(A[i],B[j], weights),
                                      D[i][j]     + substitution * weight(A[i],B[j], weights))
    return D

def _dist_thresh(A, B, thresh, insertion, deletion, substitution):
    D = _zeros(len(A) + 1, len(B) + 1)
    for i in xrange(len(A)):
        D[i + 1][0] = D[i][0] + deletion
    for j in xrange(len(B)): 
        D[0][j + 1] = D[0][j] + insertion
    for i in xrange(len(A)): # fill out middle of matrix
        for j in xrange(len(B)):
            if A[i] == B[j]:
                D[i + 1][j + 1] = D[i][j] # aka, it's free. 
            else:
                D[i + 1][j + 1] = min(D[i + 1][j] + insertion,
                                      D[i][j + 1] + deletion,
                                      D[i][j]     + substitution)
        if min(D[i + 1]) >= thresh:
            return
    return D

def _levenshtein(A, B, insertion, deletion, substitution):
    return _dist(A, B, insertion, deletion, substitution)[len(A)][len(B)]

def _levenshtein_ids(A, B, insertion, deletion, substitution):
    """
    Perform a backtrace to determine the optimal path. This was hard.
    """
    D = _dist(A, B, insertion, deletion, substitution)
    i = len(A) 
    j = len(B)
    ins_c = 0
    del_c = 0
    sub_c = 0
    while True:
        if i > 0:
            if j > 0:
                if D[i - 1][j] <= D[i][j - 1]: # if ins < del
                    if D[i - 1][j] < D[i - 1][j - 1]: # if ins < m/s
                        ins_c += 1
                    else:
                        if D[i][j] != D[i - 1][j - 1]: # if not m
                            sub_c += 1
                        j -= 1
                    i -= 1
                else:
                    if D[i][j - 1] <= D[i - 1][j - 1]: # if del < m/s
                        del_c += 1
                    else:
                        if D[i][j] != D[i - 1][j - 1]: # if not m
                            sub_c += 1
                        i -= 1
                    j -= 1
            else: # only insert
                ins_c += 1
                i -= 1
        elif j > 0: # only delete
            del_c += 1
            j -= 1
        else: 
            return (ins_c, del_c, sub_c)


def _levenshtein_thresh(A, B, thresh, insertion, deletion, substitution):
    D = _dist_thresh(A, B, thresh, insertion, deletion, substitution)
    if D != None:
        return D[len(A)][len(B)]

def levenshtein(A, B, thresh=None, insertion=1, deletion=1, substitution=1):
    """
    Compute levenshtein distance between iterables A and B
    """
    # basic checks
    if len(A) == len(B) and A == B:
        return 0       
    if len(B) > len(A):
        (A, B) = (B, A)
    if len(A) == 0:
        return len(B)
    if thresh:
        if len(A) - len(B) > thresh:
            return
        return _levenshtein_thresh(A, B, thresh, insertion, deletion,
                                                            substitution)
    else: 
        return _levenshtein(A, B, insertion, deletion, substitution)

def levenshtein_ids(A, B, insertion=1, deletion=1, substitution=1):
    """
    Compute number of insertions deletions, and substitutions for an 
    optimal alignment.
    There may be more than one, in which case we disfavor substitution.
    """
    # basic checks
    if len(A) == len(B) and A == B:
        return (0, 0, 0)
    if len(B) > len(A):
        (A, B) = (B, A)
    if len(A) == 0:
        return len(B)
    else: 
        return _levenshtein_ids(A, B, insertion, deletion, substitution)