检查字符串哈希值是否包含子字符串哈希值

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

- hyankov

---

我不确定在不扭曲“哈希”的定义的情况下是否可能实现这一点。据我所知，哈希处理是一种有损过程。 - Joe Sewell

我认为这是不可能的。如果可能的话，它可能会带来巨大的安全风险。 - Bashnia007

继续之前两条评论的内容。这是不可能的，也不应该发生。任何允许这种情况的哈希函数都会成为一个安全漏洞，并违背了“哈希”本身的意义。想象一下使用这个“神奇”的哈希函数对值a、ab、abc、abcd和abcde进行哈希。每个哈希值都会包含前面的值，最终你只会得到一些奇怪的转换函数，而不是一个哈希值。 - JNevill

请查看Rabin-Karp算法。 - Dmytro Mukalov

你需要索引而非哈希。建立一个包含所有文档中所有单词的索引。或者更好的方法是使用一个能为你完成这项任务的数据库。在Google上搜索“全文索引”。 - Dialecticus

Answer 1

如果你思考一下，这是不可能的，并没有任何意义。

首先，所有的SHA256哈希都具有完全相同的长度。我已经基于SHA256进行回答，但据我所知，这适用于任何散列方法。

考虑一个1000个字符的文档，它被SHA256哈希。它的哈希值为64位数字。

再考虑一个100个字符的文档，它被SHA256哈希。它的哈希值也是64位数字。这份文件的内容恰好是较大文档的第一章。

再考虑一个另外的100个字符的文档，它也被SHA256哈希。与上一份文件一样，它的哈希值也是64位数字。这份文件的内容是较大文档的第二章。

如果较大文档的哈希包含了这两份小文件的哈希，那肯定只有一种情况：三个哈希值都相等。但这不可能发生。

其次，想象一下从一个1000个字符的文档中可以取出多少个100个字符的子字符串。不仅仅是10个(即1000/100=10)，而是900个。假设将子字符串的索引边界表示为x和x+100，就会有很多可能性：

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^77的数量级时，可能的值才不断扩展(更准确地说，是2^256)，因为这是可能存在的唯一SHA哈希的数量。很显然，这个数字是极其巨大的！

我想你可以看出来，你的建议在数学上根本行不通。

我会将这个作为旁注, 但超级排列是一个值得研究的相关话题，以便理解这是多么不可能。对于7个唯一字符，如果您想包含所有可能的7个字符的排列，您需要一个5907位数的超级排列。这是我们找到的（最小）超级排列的最高N。

对于初始示例中的900个唯一哈希（=十六进制字符的唯一排列），这些都包含在您的“主”哈希中，主哈希所需的最小长度简直无法计算。但作为一个绝对最小值（您可以证明不能低于此），如果您假设每个64个字符的子字符串始终给您提供一个唯一的新哈希，则您的主哈希将需要963个字符长。

- Flater