Compressed Parameterized Pattern Matching
Richard Beal, Donald Adjeroh · 2013
Traditional pattern matching between strings, from the alphabet Σ, is well defined for both uncompressed and compressed sequences. Prior to this work, parameterized pattern matching (p-matching) was defined predominately by the matching between uncompressed parameterized strings (p-strings) from the constant alphabet Σ and the parameter alphabet II. In this work, we define the compressed parameterized pattern matching (compressed p-matching) problem to find all of the p-matches between a pattern P and text T, using only P and the compressed text Tc. Initially, we present parameterized compression (p-compression) as a new way to losslessly compress data to support p-matching. Experimentally, we show that p-compression is competitive with various other standard compression schemes. Subsequently, we provide the compression and decompression algorithms. Using p-compression, we address the compressed p-matching problem. Our general solution is independent of the underlying compression scheme. The results are further examined for the specific case of Tunstall codes.