예상치 못한 값을 내고있는 해밍 거리 (Simhash python)

Question

Simhash 모듈 (https://github.com/leonsim/simhash)을 확인하고있었습니다.

나는 Simhash ("String") 거리 (Simhash ("Another string"))는 두 문자열 사이의 해밍 거리라고 가정합니다. 지금, 나는이 이해가 확실하지 않다 "(https://leons.im/posts/a-python-implementation-of-simhash-algorithm/)에서와 같이 완전히 get_features (문자열) 방법을.

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()를 출력 같은

[ 'AA', 'AA', '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 

from: leonsim/simhash

계산 과정은 4 단계로 divied 할 수 있습니다 :의 코드로 살펴 보자 1) 해시 각 분할 할 단어 (기능), 이진수로 문자열을 변환하는; 2) 무게를 잰다; 3) 가정 된 가중치 비트 함께; 4) 일치 된 숫자를 2 진수로 변경하고 값으로 출력하십시오.

자, 경우에, 단계 (3)가 출력 같은

[-3, 3, -3, -3, 3, -3, -3, -3, 3, -3, -3, 3, -3, -3, 3, -3, -3, 3, -3, 3, 3, 3, 3, -3, -3, -3, -3, -3, -3, 3, -3, -3, -3, 3, -3, 3, 3, 3, -3, 3, -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())의 다른 결과를 얻을 것이다.

귀하의 사례는 짧은 길이의 텍스트가있는 심해시의 제한 사항을 보여줍니다.