Расстояние Хэмминга (питон Симхаша), выдающее неожиданное значение

Question

Я проверял модуль Simhash ( https://github.com/leonsim/simhash).

Я предполагаю, что расстояние Simhash ("String"). (Simhash ("Другая строка")) - это расстояние Хемминга между двумя строками. Теперь я не уверен, что полностью понимаю этот метод "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))]

Теперь, когда я пытаюсь вычислить расстояние между "aaaa" и "aaas", используя ширину 2, он выдает расстояние как 0.

from simhash import Simhash

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

Я не уверен, что мне здесь не хватает.

Answer 1

Копаться в коде

Ширина, в вашем случае, является ключевым параметром в get_features(), которые дают разные расщепленные слова. get_features() в вашем случае будет выводиться как:

['аа', 'аа', 'аа']

['аа', 'аа', 'как']

Затем 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 с коротким текстом.