修改Levenshtein距离算法以忽略顺序。

Question

我希望计算包含最多6个值的序列之间的Levenshtein距离。这些值的顺序不应影响距离。

我该如何将其实现到迭代或递归算法中？

示例：

# Currently 
>>> LDistance('dog', 'god')
2

# Sorted
>>> LDistance('dgo', 'dgo')
0

# Proposed
>>> newLDistance('dog', 'god')
0

'dog'和'god'是由完全相同的字母组成的，将字符串排序后会得到期望的结果。但是这种方法并不总是适用：

# Currently 
>>> LDistance('doge', 'gold')
3

# Sorted
>>> LDistance('dego', 'dglo')
2

# Proposed
>>> newLDistance('doge', 'gold')
1

“doge”和“gold”有3/4个匹配字母，因此应该返回距离为1。这是我当前的递归代码：

def mLD(s, t):
    memo = {}
    def ld(s, t):
        if not s: return len(t)
        if not t: return len(s)
        if s[0] == t[0]: return ld(s[1:], t[1:])
        if (s, t) not in memo:
            l1 = ld(s, t[1:])
            l2 = ld(s[1:], t)
            l3 = ld(s[1:], t[1:])
            memo[(s,t)] = 1 + min(l1, l2, l3)
        return memo[(s,t)]
    return ld(s, t)

编辑：跟进问题：如何在Levenshtein距离算法中添加例外

- Luis

---

更简单的解决方案：编写一个函数，只需对两个输入字符串进行排序，然后以正常方式调用LDistance函数即可。 - elixenide

比起 @EdCottrell（已经很好的）建议更简单：分别计算每个字符串中字符出现的频率。然后将频率差值相加，最后将总和除以2。 - j_random_hacker

Answer 1

你不需要使用Levenshtein算法来完成这个任务。

import collections
def distance(s1, s2):
    cnt = collections.Counter()
    for c in s1:
        cnt[c] += 1
    for c in s2:
        cnt[c] -= 1
    return sum(abs(diff) for diff in cnt.values()) // 2 + \
        (abs(sum(cnt.values())) + 1) // 2   # can be omitted if len(s1) == len(s2)

- David Eisenstat

---

好的方法，但我认为在所有情况下//2都不正确。例如，如果您向单词添加了两个字符，则距离仍应为2，而不是1。我认为应该是abs(sum(...))，即有太多和太少的字符相互平衡... 不，那也不对... - tobias_k

通过添加插入/删除项来修复它。 - David Eisenstat

谢谢！我一直在专注于学习编辑距离算法，以至于忽视了集合。如果我认为某些项目相似，比如'K'和'C'是如此相似，我希望它们的距离值为0.5而不是1，那该怎么添加异常呢？ - Luis

@Luis 这个比较棘手。也许可以提一个新问题，并将这个作为背景？除非这些异常有良好的结构，否则您可能最终需要一个通用匹配算法。 - David Eisenstat

我已经编辑了帖子并链接到了新的问题。希望这够清楚明白。 - Luis

Answer 2

为什么不直接计算共同字母数量，然后从中找到答案呢？对于每个字符，计算其出现频率，然后对于每个字符串，根据频率计算它有多少个“额外”字符，并取这些“额外”字符的最大值。

伪代码：

for c in s1:
    cnt1[c]++
for c in s2:
    cnt2[c]++
extra1 = 0
extra2 = 0
for c in all_chars:
    if cnt1[c]>cnt2[c]
        extra1 += cnt1[c]-cnt2[c]
    else
        extra2 += cnt2[c]-cnt1[c]
return max(extra1, extra2)

- Petr

Answer 3

这可能有点晚了，但我认为它可以帮助某些人，而且我仍在寻求改进。 我遇到的挑战是：

1. match_function('kigali rwanda','rwanda kigali') 可能匹配的百分比应该是100%

2. match_function('kigali','ligaki') 可能匹配的百分比应该是+50%...

   我用交叉连接和Levenstein在T-SQL中编写了一个有趣的函数，它在某些时候很有帮助，但我仍然需要改进：

    Create FUNCTION [dbo].[GetPercentageMatch](@left  VARCHAR(100),@right VARCHAR(100))
    RETURNS DECIMAL
    AS
    BEGIN
    DECLARE @returnvalue DECIMAL(5, 2);
    DECLARE @list1 TABLE(value VARCHAR(50));
    declare @count1 int, @count2 int, @matchPerc int;
    INSERT INTO @list1 (value) select value from STRING_SPLIT(@left, ' ');
   
    DECLARE @list2 TABLE(value VARCHAR(50));
    INSERT INTO @list2 (value) select * from STRING_SPLIT(@right, ' ');
   
    select @count1 = count(*) from @list1
    select @count2 = count(*) from @list2
   
    select @matchPerc = (r3.percSum/case when @count1 > @count2 then @count1 else @count2 end) from (
    select count(r2.l1) rCount, sum(r2.perc) percSum from(
    select r.t1, r.t2, r.distance, (100-((r.distance*100)/(case when len(r.t1) > len(r.t2) then len(r.t1) else len(r.t2) end))) perc, len(r.t1) l1,len(r.t2)l2 from
    (select 
    isnull(t1.value,'') t1, 
    isnull(t2.value,'') t2, 
    [dbo].[LEVENSHTEIN](isnull(t1.value,''),isnull(t2.value,'')) distance
    from @list1 t1 cross join @list2 t2 ) as r
    ) r2
    ) r3
   
    return case when @matchPerc > 100 then 100 else @matchPerc end
    END;
   

- Ishimwe Aubain Consolateur