Voltnisky字符串搜索算法

https://clickhouse.tech/codebrowser/html_report/ClickHouse/src/Common/Volnitsky.h.html

感觉这个算法并不是特别难理解,但是一些数值选择上很有讲究:

  1. hashtable 大小设置成为了64K, 这个和l2 cache大小相同
  2. 如果是ascii字符的话,那么选择2-gram做快速检查,2-gram就是uint16_t. 范围是64K.
  3. 将needle大小上限设置为255,偏移就是[0,254],可以使用1个字节表示。为了表示hashtable中没有使用的状态(0), 所以needle大小故意减少1
  4. 如果偏移使用1个字节表示,那么hashtable可以有64K个buckets.
  5. needle有了长度上限之后,2-gram的上限就是255个
  6. 所以理想状态下这个load factor就会是 255/64K ~= 0.3%

本质上这个算法就是快速过滤不合理的搜索区间。这样的话,我们能否把这个gram大小增加,比如4-gram? 这样是不是更容易减少false positive?。不过这样的后果是,hash collision也会更大,又会提高false positive。感觉4-gram还是2-gram的选择可以具体分析pattern string.