MultiPLZW: A novel multiple pattern matching search in LZW-compressed data

Document Type

Article

Source of Publication

Computer Communications

Publication Date

9-1-2019

Abstract

© 2019 Searching encrypted or compressed data provides security and privacy without sacrificing efficiency. It has many applications in cloud storage, bioinformatics, IoT, unmanned aerial vehicles and drones. This paper introduces a novel, simple, and efficient algorithm to locate all occurrences of a set of patterns in LZW-compressed data, in a single pass. The algorithm comprises a preprocessing phase and a subsequent search phase. It uses a modified version of the generalized suffix tree, a lookup table, a mapping table, and a history tree. The proposed algorithm is superior in terms of the time complexity, while maintaining a space complexity of the same order as the best of existing algorithms. The time complexity is O(n+m+r), which is proportional to the length of the LZW-compressed data, where n is the length of the compressed data, m is the total size of the patterns, and r is the number of pattern occurrences in the compressed data. The space complexity is O(m2+t+r), where t is the size of the dictionary table that is used during compression. Experimental results show a significant improvement in search time, approximately twice as fast, compared to decompressing and then searching using Aho–Corasick algorithm. Also, results on various dataset sizes, demonstrate the algorithm's superior scalability, which improves as the size of the dataset increases.

ISSN

0140-3664

Publisher

Elsevier B.V.

Volume

145

First Page

126

Last Page

136

Disciplines

Computer Sciences

Keywords

Aho–Corasick algorithm, Algorithm complexity, Compressed data, LZW compression, Pattern matching

Scopus ID

85068014023

Indexed in Scopus

yes

Open Access

no

Link to Full Text

Share

COinS