## Abstract

In this paper we address the problem of searching in LZW compressed text directly, and present a new algorithm for finding multiple patterns by simulating the move of the Aho-Corasick pattern matching machine. The new algorithm finds all occurrences of multiple patterns whereas the algorithm proposed by Amir, Benson, and Farach finds only the first occurrence of a single pattern. The new algorithm runs in O(n + m^{2} + r) time using O(n + m^{2}) space, where n is the length of the compressed text, m is the length of the total length of the patterns, and r is the number of occurrences of the patterns. We implemented a simple version of the algorithm, and showed that it is approximately twice faster than a decompression followed by a search using the Aho-Corasick machine.

Original language | English |
---|---|

Pages (from-to) | 103-112 |

Number of pages | 10 |

Journal | Data Compression Conference Proceedings |

Publication status | Published - 1998 Jan 1 |

Externally published | Yes |

Event | Proceedings of the 1998 Data Compression Conference, DCC - Snowbird, UT, USA Duration: 1998 Mar 30 → 1998 Apr 1 |

## ASJC Scopus subject areas

- Computer Networks and Communications