Hamming Entfernung (Simhash Python) geben unerwarteten Wert

Question

Ich war Auschecken Simhash-Modul (https://github.com/leonsim/simhash).

Ich nehme an, dass die Simhash ("String") Entfernung (Simhash ("Another string")) die Hamming-Distanz zwischen den beiden Saiten ist. Nun, ich bin nicht sicher, ob ich verstehe dieses „get_features (string) Methode vollständig, wie in (https://leons.im/posts/a-python-implementation-of-simhash-algorithm/) gezeigt.

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))] 

jetzt, wenn ich versuche, zwischen zu berechnen Abstand‚AAAA‘und‚AAAS‘die Breite mit 2, gibt es den Abstand als 0.

from simhash import Simhash 

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

out ich bin nicht sicher, was ich hier raus bin fehlt.

Answer 1

Dig in Code

Die Breite, in Ihrem Fall, ist der Schlüsselparameter in get_features(), die verschiedene gespaltene Wörter geben. Die get_features() in Ihrem Fall wird eine Ausgabe wie:

[ 'aa', 'aa', 'aa']

[ 'aa', 'aa', 'als']

Dann berechnet Simhash diese Liste als ungewichtete Funktionen (die das Standardgewicht jedes Merkmal bedeutet, ist 1) und eine Ausgabe wie:

86f24ba207a4912

86f24ba207a4912

Sie sind gleich!

Der Grund ist von Simhash-Algorithmus selbst. Lassen Sie uns den Code schauen in:

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

den Berechnungsprozess in 4 Schritten divied werden können: 1) hash jedes gespaltet Wort (Funktion), String in Binärzahlen zu transformieren; 2) gewichten sie; 3) assumble gewichtete Bits zusammen; 4) ändern Sie die angenommene Zahl in binär und geben Sie als Wert aus.

nun in Ihrem Fall der Schritt 3 ausgeben wird, wie:

[-3, 3, -3, -3, 3, -3, -3, -3, 3, -3, -3, 3, -3, -3, 3, -3, -3, 3, -3, 3, 3, 3, 3, -3, -3, -3, -3, -3, -3, 3, -3, -3, -3, 3, -3, 3, 3, 3, -3, 3, -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] 

Und nach dem Schritt 4 wird der 2-Ausgang den gleichen Wert.

Andere Parameter

Wenn Sie die Breite von 2 auf 1 zu ändern, 3, 4, finden Sie verschiedenes Ergebnis Simhash(get_features()) bekommen.

Ihr Fall zeigt die Einschränkung von Simhash mit Kurztext.