Efficient pattern matching in compressed text via bit-parallel word-based encoding

This paper introduces an optimized algorithm designed to accelerate compressed word matching using advanced bit-parallelism techniques, resulting in a high-performance solution. The proposed algorithm (BIT_COMP) uses the concept of word-based tagged code (WBTC) and a bit-parallel technique (shift-or). BIT_COMP reports the exact number of matches (no false positives) while improving asymptotic searching cost in practice by applying q-gram (q=2) packing and bit-parallel operations. We provide a formal time-complexity characterization showing the search phase runs in O ( ⌈ n / 2 ⌉ . ⌈ m / w ⌉ + o c c ) machine-word operations (where n is the text length in characters, m the pattern length in bits after WBTC encoding, w the machine word size, and o c c the number of actual matches), together with a proof sketch that the verification step eliminates false matches produced by raw codeword alignment. Experimental results confirm both the theoretical speedup and the zero false-positive behaviour compared with prior WBTC and tagged-Huffman-based approaches.