string - 任何可以破坏/散列字符串但可以匹配的算法？

Question

用例：客户端需要通过 HTTP 发送一个巨大的字符串。服务器回复字符串是否包含一些子字符串。然而，巨大的字符串是巨大的。结果，这个系统效率很低。此外，巨大的字符串包含一些敏感信息，所以这真的很不安全。

是否有一些伪散列机制以某种方式将一个大字符串总结为某个数字，这个大字符串的所有子字符串都会散列到相同的数字，但非子字符串很可能不会散列到这个大字符串？

Answer 1

是否有一些伪散列机制以某种方式将一个大字符串总结为某个数字，这个大字符串的所有子字符串都会散列到相同的数字，但非子字符串很可能不会散列到这个大字符串？

不。

让我们f成为这样的哈希。考虑一个字符串s和非子字符串t。注意s和t是 的子串s + t。因此，s和t具有相同的哈希值（即f(s) = f(t) = f(s + t)）。这f(s) != f(t)与大概率的要求相反。

特别是s = ""，我们看到所有字符串t都有f(s) = f(t)，所以它f是常数并且等于f("")。

Answer 2

是否有一些伪散列机制以某种方式将一个大字符串总结为某个数字，这个大字符串的所有子字符串都会散列到相同的数字，但非子字符串很可能不会散列到这个大字符串？

我想我必须解释为什么这不会发生：

String string = "the quick brown fox jumps over the lazy dog";

这意味着，根据您的要求，其中的每个字母都将散列到相同的值。散列算法是确定性的。在这个例子中，t -> 5, h -> 5, e -> 5... 等等，但是如果你有一些字符串：

String string2 = "hello there";

然后现在，你想要h散列到不同的东西，你想要e散列到不同的东西，所以给定完全相同的输入，你想要一个不同的值。这违背了数学函数的定义。

这是什么意思？

好吧，如果您的函数中没有确定性的任何方面，您的数据在值和被散列的字母之间没有可重复的映射，这意味着您的数据是没有意义的。

Answer 3

If you have a constant length for the substrings you could do what many file-sharing programs do and use a list of hashes or something like the tiger-tree hash.

List of hashes: Make a hash for every chunk of the file of some pre-set length (say 64kB), then transmit a list of these hashes so these chunks can be verified.

Tiger-Tree hash: http://en.wikipedia.org/wiki/Merkle_tree#Tiger_tree_hash Basically build a binary tree of hashes with the leaves being hashes of chunks like in a list of hashes.

If you need to match to every possible substring instead of just pre-defined chunks this isn't going to work though.

Answer 4

所有子字符串听起来都不可行，但我想您可能对您尚未告诉我们的子字符串有一些限制。

如果您对子字符串进行块对齐或空白对齐或其他操作，您可能会考虑使用布隆过滤器，例如：https ://pypi.python.org/pypi/drs-bloom-filter/1.01 。布隆过滤器可以存储集合的成员并用于测试集合的成员资格，有时每个元素只需一位。它们有时会给出误报，但误报的概率可由用户调整。