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

Question

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

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

from simhash import Simhash 

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

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

Answer 1

Dig в код

Ширина в вашем случае является ключевым параметром в 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 

from: leonsim/simhash

Процесс расчета можно divied в 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()).

В вашем случае показано ограничение на симхаш с текстом короткой длины.