Hamming距离(Simhash )给出了意想不到的值

Question

我正在查看Sim散列模块( https://github.com/leonsim/simhash )。

我假定Simhash(“string”).distance(Simhash(“另一个字符串”))是两个字符串之间的hamming距离。现在，我不确定我是否完全理解这个“get_features(字符串)方法”，如(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计算“aaa”和"aaas“之间的距离时，它给出的距离为0。

from simhash import Simhash

Simhash(get_features("aaas")).distance(Simhash(get_features("aaaa")))

我不知道我在这里遗漏了什么。

Answer 1

挖掘代码

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

'aa'，'aa'，'aa‘

然后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

出发地: leonsim/simhash

计算过程可分为四个步骤: 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、-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、-3、-3、-3、-3、-3、-3、-3、-3、-3、-3、-3、-3、-3、-

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

其他参数

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

您的案例显示了短文本simhash的局限性。