汉明距离（Simhash python）给出意外值

Question

我正在检查Simhash模块（https://github.com/leonsim/simhash）。在

我假设Simhash（“String”）.distance（Simhash（“另一个字符串”））是两个字符串之间的汉明距离。现在，我不确定我是否完全理解这个“getfeatures（string）方法，如（https://leons.im/posts/a-python-implementation-of-simhash-algorithm/）所示。在

def get_features(s):
    width = 2
    s = s.lower()
    s = re.sub(r'[^\w]+', '', s)
    return [s[i:i + width] for i in range(max(len(s) - width + 1, 1))]

现在，当我试图用宽度2计算“aaaa”和“aaas”之间的距离时，它给出的距离是0。在

^{pr2}$

我不知道我错过了什么。在

Answer 1

深入研究代码

在您的例子中，宽度是get_features()中的关键参数，它给出了不同的拆分词。本例中的get_features()将输出如下：

['aa', 'aa', 'aa']

['aa', 'aa', 'as']

然后Simhash将这些列表计算为未加权的特性（这意味着每个特性的默认权重为1），并输出如下：

86f24ba207a4912

86f24ba207a4912

他们是一样的！在

原因在于simhash算法本身。让我们看看代码：

def build_by_features(self, features):
    """
    `features` might be a list of unweighted tokens (a weight of 1
        will be assumed), a list of (token, weight) tuples or
        a token -> weight dict.
    """
    v = [0] * self.f
    masks = [1 << i for i in range(self.f)]
    if isinstance(features, dict):
        features = features.items()
    for f in features:
        if isinstance(f, basestring):
            h = self.hashfunc(f.encode('utf-8'))
            w = 1
        else:
            assert isinstance(f, collections.Iterable)
            h = self.hashfunc(f[0].encode('utf-8'))
            w = f[1]
        for i in range(self.f):
            v[i] += w if h & masks[i] else -w
    ans = 0
    for i in range(self.f):
        if v[i] >= 0:
            ans |= masks[i]
    self.value = ans

from: leonsim/simhash

计算过程可分为4个步骤： 1） 散列每个拆分的单词（特征），将字符串转换成二进制数； 2） 称重； 3） 将加权比特放在一起； 4） 将给定的数字改为二进制，并作为值输出。在

现在，在您的例子中，步骤3将输出如下：

[-3, 3, -3, -3, 3, -3, -3, -3, 3, -3, -3, 3, -3, -3, 3, -3, -3, 3, -3, 3, 3, 3, 3, -3, -3, -3, -3, -3, -3, 3, -3, -3, -3, 3, -3, 3, 3, 3, -3, 3, -3, -3, 3, -3, -3, 3, -3, -3, 3, 3, 3, 3, -3, 3, 3, -3, -3, -3, -3, 3, -3, -3, -3, -3]

[-1, 3, -3, -1, 3, -3, -3, -1, 3, -3, -3, 1, -1, -1, 1, -3, -3, 3, -1, 3, 1, 3, 1, -3, -1, -3, -3, -1, -1, 3, -1, -1, -1, 3, -1, 1, 3, 1, -1, 1, -3, -3, 1, -1, -3, 3, -3, -1, 1, 3, 3, 3, -3, 3, 3, -3, -1, -1, -1, 1, -3, -3, -3, -1]

在步骤4之后，2输出相同的值。在

其他参数

如果将宽度从2更改为1、3、4，将得到 Simhash(get_features())的不同结果。在

您的案例显示了使用短长度文本的simhash的局限性。在