Predict Match (pm-k) is a fuzzy matching algorithm that enables looking for a potential match across multiple substrings at the same time. We take two approaches, one is Bitap (Bit Approximation) which uses a sliding window of the size of the smallest substring (small substrings will create more false positives). Bitap is very quick for scanning potential matches. We then use pm-8, a sliding window of a fixed size (in our case 8 bytes), to further look for potential matches. If we find a hit, we must defer to slower substring matching approaches to confirm the match. PredictMatch relies on hashing to distribute the mapping of characters in substrings at specific offsets. This hashing helps reduce overlaps between similar substrings which reduces false positives, however this does mean that if your hash is poor, or the table size is too small, you may have more false positives than preferred.
This implementation is written by Epic but based on the licensed pm4-bitap.c implementation found at https://www.genivia.com/ugrep.html
1.9.8