OPTIMIZATION OF LZW (LEMPEL-ZIV-WELCH) ALGORITHM TO REDUCE TIME COMPLEXITY FOR DICTIONARY CREATION IN ENCODING AND DECODING

Main Article Content

Article Sidebar

PDF
Published Oct 12, 2013
Nishad P M, R. Manicka Chezian

Abstract

LZW (Lempel-Ziv-Welch) is a universal lossless data compression algorithm, which takes linear time in encoding and decoding. This paper discusses a methodology to reduce time complexity by combining binary search with LZW. The existing LZW compression algorithm takes large time for dictionary creation while encoding and decoding. By using binary search with LZW the time complexity can be reduced optimally and gradually because the comparison ratio is less while creating the dictionary. Especially while compressing the search for patterns in the table and also in the decompression algorithm for finding the pattern in the table is taking linear time for searching. Therefore, combining Enhanced LZW with binary search reduces the time complexity. The proposed methodology may be bust in data compression for communication, Maximizes the reduction of complexity in pattern identification for compression. The proposed methodology reduces the complexity in time with Binary search tree (BST). The experimental result shows 94.21 % improvement on Compression and 93.34% improvement on Decompression.
Abstract 184 | PDF Downloads 375

Article Details

Issue
Vol 2 No 5 (2012): Asian Journal of Computer Science and Information Technology
Section
Articles

COPYRIGHT AGREEMENT AND AUTHORSHIP RESPONSIBILITY

 All paper submissions must carry the following duly signed by all the authors:

“I certify that I have participated sufficiently in the conception and design of this work and the analysis of the data (wherever applicable), as well as the writing of the manuscript, to take public responsibility for it. I believe the manuscript represents valid work. I have reviewed the final version of the manuscript and approve it for publication. Neither has the manuscript nor one with substantially similar content under my authorship been published nor is being considered for publication elsewhere, except as described in an attachment. Furthermore I attest that I shall produce the data upon which the manuscript is based for examination by the editors or their assignees, if requested.”