c# - 检查字符串哈希是否包含子字符串哈希

Question

假设我有大量文档以某种方式散列(例如 Sha256)并存储它们的散列。是否有一种散列技术可以让我通过查看它们的散列来检查 string1 是否包含在 string2 中？我想避免加载全文。

澄清一下:这与 sim/min-hashing 无关，寻找近似重复项或 Levenshtein 距离。我正在寻找一种哈希算法，它可以通过查看哈希以某种方式让我检查子字符串。

例如

var string1 = "bla bla bla cat dog bla bla";
var string2 = "cat dog";
var hash1 = HashAlgo(string1); // <-- magic goes here
var hash2 = HashAlgo(string2);
Assert.IsTrue(string1.Contains(string2));
Assert.IsTrue(hash1.Contains(hash2)); // <--- magic goes here

Answer 1

如果你仔细想想，这不可能是有道理的。

首先，所有 SHA256 哈希值的长度都完全相同。我的答案基于 SHA256，但据我所知，这适用于任何哈希方法。

• 考虑一个 1000 个字符的文档，您已经对其进行了 SHA256 哈希处理。它的哈希值长 64 位。
• 考虑一个 100 个字符的文档，您已经对其进行了 SHA256 哈希处理。它的哈希值长 64 位。这份文件的内容恰好是更大文件的第一章。
• 考虑第二个 100 个字符的文档，您已经对其进行了 SHA256 哈希处理。它的哈希值长 64 位。这份文件的内容恰好是更大文件的第二章。

较大文件的哈希值不可能包含两个较小文件的哈希值，因为只有当所有三个哈希值彼此相等时才有可能。

其次，想一想我可以从 1000 个字符的文档中提取多少个 100 个字符的子字符串。它不仅仅是 10(如 1000/100 = 10)，而是 900。将子字符串表示为索引边界，有多种可能性:

• 0 到 100
• 1 到 101
• 2 到 102
• ...
• 897 到 997
• 898 到 998
• 899 到 999

总共有 900 个选项。假设您的初始文档不会以任何方式重复自身(因此您不会得到两个相等的子字符串)，这将导致 900(假定的)唯一哈希值。

这 900 个唯一的哈希值不能都是初始文件哈希值的子字符串。

此外，考虑到我们甚至没有考虑过其他长度的子串!假设任何可能的子串长度，您最终可以得到 999,000 个不同的子串(但当然其中一些会重复)

这还没有考虑原始文档可能超过 1000 个字符的事实。对于包含 n 个字符的任何文档，您可以期望找到 n*(n-1) 个子字符串(长度在 1 到 n 之间)，主要具有唯一的哈希值。

只有当您处于 10⁷⁷(更准确地说，2²⁵⁶)的数量级时，这种可能值的扩展才会稳定下来，因为这是唯一值的数量SHA 哈希可能存在。
餐巾纸的背面是一个 10³⁸ 字节的文档。一旦达到该文件大小，所有可能的子字符串(任意长度)都必须包含至少一个重复项。

我想您明白为什么您的建议在数学上根本不可能。

I will keep this as a sidenote, but superpermutations are a tangential topic worth looking at to understand how impossible this is. For 7 unique characters, you need a superpermutation of 5907 digits if you want to encompass all possible permutations of the 7 characters. This is the highest N for which we have found (minimal) superpermutations.

For the initial example of 900 unique hashes (= unique permutations of hexedecimal characters) which would all be contained in your "master" hash, the minimum required length of the master hash is simply incalculable. But as an absolute minimum (which you provably cannot go under), your master hash would have to be 963 characters long (if you assume that every single 64-character substring always gives you a unique new hash)