Title :
Compressed and fully compressed pattern matching in one and two dimensions
Author :
Rytter, Wojciech
Author_Institution :
Inst. of Inf., Warsaw Univ., Poland
Abstract :
We survey the complexity issues related to several algorithmic problems for compressed and fully compressed pattern matching in one- and two-dimensional texts without explicit decompression. Several related problems for compressed strings and arrays are considered: equality testing, computation of regularities, subsegment extraction, language membership, and solvability of word equations.
Keywords :
computational complexity; data compression; string matching; text analysis; algorithmic problems; complexity issues; compressed arrays; compressed pattern matching; compressed strings; equality testing; fully compressed pattern matching; language membership; one-dimensional texts; regularities; two-dimensional texts; word equations; Computer science; Data compression; Data mining; Equations; Finishing; Image coding; Pattern matching; Polynomials; Testing;
Journal_Title :
Proceedings of the IEEE
