Name
Abstract | ||
|---|---|---|
The recent explosion in the amount of stored data has necessitated the storage and transmission of data in compressed form. The need to quickly access this data has given rise to a new paradigm in searching, that of compressed matching (Proc. Data Compression Conf, Snow Bird, UT, 1992, pp. 279-288; Proc. 8th Annu. Symp. on Combinatorial Pattern Matching (CPM 97), Lecture Notes in Computer Science, Vol. 1264, Springer, Berlin, 1997, pp. 40-51; Proc. 7th Annu. Symp. on Combinatorial Pattern Matching (CPM 96), Lecture Notes in Computer Science, Vol. 1075, Springer, Berlin, 1996, pp. 39-49). The goal of the compressed pattern matching problem is to find a pattern in a text without decompressing the text.The criterion of extra space is very relevant to compressed searching. An algorithm is called inplace if the amount of extra space used is proportional to the input size of the pattern. In this paper we present a 2d compressed matching algorithm that is inplace. Let compressed(T) and compressed(P) denote the compressed text and pattern, respectively. The algorithm presented in this paper runs in time O(|compressed(T)| + |P|log σ) where σ is min(|P|,|Σ), and Σ is the alphabet, for all patterns that have no trivial rows (rows consisting of a single repeating symbol). The amount of space used is O(|compressed(P)|). The compression used is the 2d run-length compression, used in FAX transmission. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(02)00041-5 | Theoretical Computer Science |
Keywords | Field | DocType |
input size,FAX transmission,Computer Science,Lecture Notes,time O,Data Compression Conf,Inplace run-length,run-length compression,Combinatorial Pattern Matching,extra space,Snow Bird | Discrete mathematics,Roundness (object),Computer science,Metrology,Algorithm,Geometry | Journal |
Volume | Issue | ISSN |
290 | 3 | Theoretical Computer Science |
ISBN | Citations | PageRank |
0-89871-453-2 | 18 | 0.90 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amihood Amir | 1 | 1985 | 191.89 |
| Gad M. Landau | 2 | 1558 | 239.71 |
| Dina Sokol | 3 | 144 | 12.84 |