1

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

我认为 Simhash("String").distance(Simhash("Another string")) 是两个字符串之间的汉明距离。现在，我不确定我是否完全理解这个“get_features(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。

from simhash import Simhash

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

我不确定我在这里错过了什么。

4

1 回答 1

3

深入研究代码

在您的情况下，宽度是 中的关键参数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

来自：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 的限制。

于 2017-03-24T10:09:47.820 回答