修改莱文斯坦 - 距离无视秩序 [英] Modify Levenshtein-Distance to ignore order

问题描述

我在找计算包含多达6个数值序列之间的莱文斯坦距离。 这些值的顺序不应该影响的距离。

I'm looking to compute the the Levenshtein-distance between sequences containing up to 6 values. The order of these values should not affect the distance.

我将如何落实到迭代或递归算法呢？

How would I implement this into the iterative or recursive algorithm?

例如：

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

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

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

狗和上帝有相同的字母，排序字符串前手将返回所需的结果。然而，这不工作的所有时间：

'dog' and 'god' have the exact same letters, sorting the strings before hand will return the desired result. However this doesn't work all the time:

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

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

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

总督和黄金有3/4的匹配字母，因此应该返回1的距离。 这是我目前的递归code：

'doge' and 'gold' have 3/4 matching letters and so should return a distance of 1. Here is my current recursive code:

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)

编辑：的后续问题：<一href="http://stackoverflow.com/questions/32459196/adding-exceptions-to-levenshtein-distance-like-algorithm">Adding例外莱文斯坦 - 距离般的算法

推荐答案

您不需要莱文斯坦机械这一点。

You don't need the Levenshtein machinery for this.

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)

这篇关于修改莱文斯坦 - 距离无视秩序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！