Ocaml-计算一个字符串中所有子串的哈希值的最有效方法是什么？

Question

获取一个字符串中所有子串的哈希值的最有效方法是什么。我试着用:

let str1 = "AHTG...";;(*1000000 chars*)
let tam = 2;;
for i = 0 to String.length str1 - tam do
  let st = String.sub str1 i tam in
  Hashtbl.add hash_table (Hashtbl.hash st) i;
done;

计算大小=2(AC,CH,TA,...)的字符串中所有大小为1000000的子串，并将其值添加到hash_table中，但它需要很多时间来完成这个过程，我想。我想知道是否有比上面介绍的过程更有效和更快的方法？

Answer 1

首先，一个字符串有很多子串，我想说大约有n^22个。当n=1e6时，这是一个很大的数字。如果你的哈希函数是一个没有已知算术属性的黑盒子，而且你的字符串也没有已知的额外属性，那么你基本上要对你的哈希函数进行O(n^2)次调用，这将需要很长的时间。

如果你的哈希函数具有有趣的算术属性，比如说哈希(a ^ b) =哈希(a) +哈希(b) mod K，你可能会做得更好一些。另一方面，这样的属性可能会让哈希变得更弱。

作为一个直接的改进，你可以考虑一个直接在子串上工作的哈希函数。这将为你节省大量调用 String.sub 以及相关的 consing 和 GC 的次数。(可能这不会有很大的帮助，因为OCaml有一个非常好的GC来处理短暂的值。)