0

我一直在努力使用 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;
4

1 回答 1

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 是如何工作的——所以我只是在这里猜测——但如果你的带状疱疹（重叠的 ngram）只有 2 个字符长，那么很多这些带状疱疹会在很多地方被发现的文件。即使文档的目的和含义完全不同，两个文档也有可能共享很多这些功能。

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

于 2017-10-10T04:50:19.860 回答