simhash功能可靠嗎？

我一直在使用simhash算法。我根據我對爬蟲的理解來實現它。但是，當我做了一些測試時，對我來說似乎不太可靠。simhash功能可靠嗎？

我計算了200,000個不同文本數據的指紋，並看到一些不同的內容具有相同的指紋。所以碰撞的可能性很大。

我的實現代碼如下。

我的問題是：如果我的實現是正確的，這個算法有一個很大的衝突。谷歌如何使用這種算法？否則，我的算法有什麼問題？

public long CalculateSimHash(string input) 
     { 
      var vector = GenerateVector(input); 

      //5- Generate Fingerprint 
      long fingerprint = 0; 
      for (var i = 0; i < HashSize; i++) 
      { 
       if (vector[i] > 0) 
       { 
        var zz = Convert.ToInt64(1 << i); 
        fingerprint += Math.Abs(zz); 
       } 
      } 
      return fingerprint; 
     } 

private int[] GenerateVector(string input) 
     { 
      //1- Tokenize input 
      ITokeniser tokeniser = new OverlappingStringTokeniser(2, 1); 
      var tokenizedValues = tokeniser.Tokenise(input); 

      //2- Hash values 
      var hashedValues = HashTokens(tokenizedValues); 

      //3- Prepare vector 
      var vector = new int[HashSize]; 
      for (var i = 0; i < HashSize; i++) 
      { 
       vector[i] = 0; 
      } 

      //4- Fill vector according to bitsetof hash 
      foreach (var value in hashedValues) 
      { 
       for (var j = 0; j < HashSize; j++) 
       { 
        if (IsBitSet(value, j)) 
        { 
         vector[j] += 1; 
        } 
        else 
        { 
         vector[j] -= 1; 
        } 
       } 
      } 
      return vector;

來源

2015-10-16 mavera

仰望生日問題。 –

生日問題？不能抱歉 – mavera

https://en.wikipedia.org/wiki/Birthday_problem –

我可以看到幾個問題。首先，你只得到32位散列，而不是64位，因爲你使用的是錯誤的類型。請參閱https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/left-shift-operator 此處最好不要使用帶符號的整數類型，以避免混淆。所以：

// Generate Fingerprint 
ulong fingerprint = 0; 
for (int i = 0; i < HashSize; i++) 
{ 
    if (vector[i] > 0) 
    { 
     fingerprint += 1UL << i; 
    } 
}

第二個問題是：我不知道你OverlappingStringTokenizer如何工作 - 所以我只是猜測這裏 - 但如果你的帶狀皰疹（重疊的n-gram）只有2個字符長，那麼很多這些帶狀皰疹將在很多文件中找到。即使文檔的目的和意義完全不同，有可能兩個文檔將共享很多這些功能。

因爲在處理文本時，單詞是最小的簡單單位，所以我通常會根據單詞而不是字符來計算我的單詞。當然，2個字符對於有效的功能來說太小了。我喜歡從5個單詞中生成帶狀皰疹，而忽略標點和空白。

來源

2017-10-10 04:50:19

simhash功能可靠嗎？

回答

相關問題