HashChain

HashChain is a family of very fast factor-based sublinear exact-matching search algorithms.

They work by building a bloom-filter based on hashes of q-grams within the pattern to be searched, and hashes of their adjacent q-gram. This permits the algorithm to efficiently reject non-adjacent q-grams in the text with very high probability, allowing it to skip ahead of the mis-matching factor.

Publications

A pre-print of the paper describing the HashChain algorithm is available on arXiv at https://arxiv.org/abs/2310.15711v1.

A version of this paper was accepted at the Symposium on Experimental Algorithmics 2024: https://sea2024.univie.ac.at/accepted-papers/

It is available at https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.24

Algorithms

Algorithms in the HashChain family include:

• HashChain - the original HashChain algorithm.
• LinearHashChain - HashChain with a guaranteed linear worst-case, based on Linear WFR.
• SentinelHashChain - a faster HashChain using a search text modification hack (store a copy of the pattern to be located after the text to be searched, to avoid having to check the position in the main search loop). This is mostly not practical unless you can directly modify the text being searched. If you can, it offers a reasonable speed up.
• WeakerHashChain - a HashChain variant which does not re-scan data during filtering, but is not linear.

q-grams

These algorithms fundamentally work on q-grams - processing several bytes at a time. Variants of them for q-grams of lengths of 2, 3 and 4 are provided, although bigger ones can be created. The sweet spot for most searches is a q-gram of length 3. Longer q-grams tend to work better on lower entropy data (e.g. DNA), while shorter ones can often perform very well on high entropy data.

One practical implication of this is they cannot search for strings smaller than the q-gram they process. So HashChain with a q-gram lenght of 3 cannot search for 1 or 2 length strings, and a different algorithm would need to be used for those.

Hash Table Size

HashChain can use different sizes of hash table for the bloom filter, always a power of two. This is parameterised on construction by the ALPHA value (the power of 2). Larger tables can be faster, but only up to a point, beyond which the larger table has more cache misses. In general an ALPHA value of 10 to 12 performs well (1024, 2048 or 4096 size). When the q-gram length is 1, the hash table size is hardcoded to 256 (ALPHA = 8), as the total addressable space is just 256 values.

Code

In the src folder are two implementations in both C and Java for HashChain searchers.

C

The C code is created to integrate with the SMART (String Matching Algorithms Research Tool). As such, it only counts the number of occurences in the entire text to search, and does not return the match position of the patterns. The home page for this tool can be found at https://smart-tool.github.io/smart/, and the repository at https://github.com/smart-tool/smart/. Note there is a heavily updated version of SMART, which is more reliable and powerful in development at: https://github.com/ostafen/smart/tree/develop

Java

The Java code contains implementations of some classic search algorithms, along with the 2 main HashChain variants (HashChain and LinearHashChain), in order they can be compared. In addition, two new variants of Horspool are included: Linear Signed Horspool and Signed Horspool. These are unpublished algorithms that improve on basic Horspool using signed shifts, and KMP pattern validation for the linear version. While they are not as fast as HashChain, they are faster than standard Horspool and may be of some interest, as they can work on single characters, whereas HashChain really needs to work on q-grams longer than a single byte to be fast. A HashChain version operating on a single byte (QLEN = 1) is provided, but will perform very badly on low entropy data.

They can all return either the match position, or the count of occurrences. A simple benchmarking tool, and a test suite that ensures all implementations find the same results are provided.

The algorithms perform some pre-processing on the pattern before searching. If you want to search for the same pattern repeatedly, you should separate out the pre-processing and store the results (i.e.. tables and derived constants) for re-use, to avoid having to re-compute this on each search for the same pattern.

Similar algorithms

Similar algorithms include:

• Weak Factor Recognition (WFR) by Simone Faro,
• Linear WFR (LWFR) by Domenico Cantone, Simone Faro and Arianna Pavone,
• Q-gram filtering (QF) by Branislav Ďurian, Hannu Peltola, Leena Salmela, and Jorma Tarhio.

WFR uses a rolling hash function that gives it a longer pre-processing stage and which sets more bits in its filter, giving it a higher false positive rate. It is especially effective on low entropy data as the rolling hash expands the accessible space in the filter table.

LWFR uses two techniques to achieve linearity in the worst case, while remaining sublinear on average. First that it does not re-scan data it has previously scanned during the filtering phrase, and second, that it uses a forward linear matching algorithm (KMP) for verification that likewise guarantees linearity.

QF uses an alignment concept; that successive q-grams of size Q read back in the text should be aligned in the pattern in the same way. Either they belong to the chain of q-grams that start from the end of the pattern, or the second from the end, and so on up to Q chains. It appears to be an efficient filter, but the space it has to set bits is limited by Q rather than the size of a word in memory.