Algorithmica Прикладные компьютерные науки
Compressed Dictionary Matching on Run-Length Encoded Strings
Аннотация
Abstract Given a set of pattern strings $$\mathcal {P}=\{P_1, P_2,\ldots P_k\}$$ P = { P 1 , P 2 , … P k } and a text string S , the classic dictionary matching problem is to report all occurrences of each pattern in S . We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let m and n be the total length of the patterns $$\mathcal {P}$$ P and the length of the text string S , respectively, and let $$\overline{m}$$ m ¯ and $$\overline{n}$$ n ¯ be the total number of runs in the run-length encoding of the patterns in $$\mathcal {P}$$ P and S , respectively. Our main result is an algorithm that achieves $$O( (\overline{m} + \overline{n})\log \log m + \textrm{occ})$$ O ( ( m ¯ + n ¯ ) log log m + occ ) expected time, and $$O(\overline{m})$$ O ( m ¯ ) space, where $$\textrm{occ}$$ occ is the total number of occurrences of patterns in S . This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within a $$\log \log m$$ log log m factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.