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;

计算大小为 1000000 的字符串的所有大小为 2 (AC,CH,TA,...) 的子串，并向 hash_table 添加值，但需要花费大量时间才能完成过程，我想。我想知道是否有比上面介绍的过程更高效、更快速的过程？

Answer 1

首先，一个字符串有很多子串，大约有 n^2/2 个。当 n = 1e6 时，这是一个很大的数字。如果你的散列函数是一个没有已知算术属性的黑盒子，并且你的字符串也没有已知的额外属性，你基本上必须对你的散列函数进行 O(n^2) 次调用，这将花费很长时间。

如果您的散列函数具有有趣的算术性质，例如 hash(a ^ b) = hash(a) + hash(b) mod K，您可能会做得更好一些。另一方面，像这样的属性可能会产生较弱的散列。

作为直接改进，您可以考虑直接作用于子字符串的散列函数。这将为您节省大量对 String.sub 的调用以及相关的 consing 和 GC。（可能这不会有太大帮助，因为 OCaml 对短暂的值有一个非常好的 GC。）

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

Ocaml-What is the most efficient way to calculate hash values for all substrings in a string?

string

hash

ocaml