simhash函数有那么可靠吗？

Question

我已经纠结于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;

Answer 1

我能看到几个问题。首先，你只能得到一个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是如何工作的--所以我在这里只是猜测--但是如果您的shingles (重叠的ngram)只有2个字符长，那么在很多文档中就会发现很多这样的shingles。即使两个文档的目的和含义完全不同，两个文档也有可能共享许多这些特性。

因为在处理文本时，单词是最小的简单意义单位，所以我通常以单词而不是字符来计算我的标记。当然，对于一个有效的功能来说，2个字符太小了。我喜欢从5个单词生成带状疱疹，忽略标点符号和空格。