LZ-78 Data Compression Algorithm

Lossless Compression Algorithms

LZ-78 (Lempel-Ziv 78) Data Compression Algorithm

These algorithms compress data without any loss of information, making them ideal for text, executables, and other data where exact replication is essential. The LZ-78 algorithm uses a dictionary-based approach to compress data. It maintains a dictionary of previously encountered patterns and represents new patterns by referencing entries in the dictionary.

Compression

The LZ78compress method in the LZ78 class performs the compression process. It takes a string str as input and generates a vector of tags representing the compressed data. The algorithm scans the input string character by character, building patterns and adding them to the dictionary. Whenever a new pattern is encountered, it is added to the dictionary, and a tag is created consisting of a pointer to the pattern's index in the dictionary and the next character in the input string. These tags are stored in the tags vector.

Decompression

The LZ78decompress method in the LZ78 class performs the decompression process. It takes a vector of tags as input and returns the decompressed string. The algorithm iterates through the tags, interpreting each tag to reconstruct the original data. It uses the dictionary to retrieve patterns based on the provided pointers and appends the characters to the result string.

Usage

The code includes a main method that provides a simple command-line user interface for compression and decompression. Upon running the program, the user is prompted to select either compression or decompression.

For compression:

• The input file path is set to "Compression\\input.txt".
• compressed output is written to "Compression\\compressed.txt".

For decompression:

• The decompressed output is written to "DeCompression\\decompressed.txt".
• The user is prompted to enter the number of tags to process.
• The user is then prompted to enter the tags in the format

Here is the implementation of LZ-78 Algorithm Click Here

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Compression	O(n)	O(n)
Decompression	O(n)	O(n)

© 2024 Adarsh Sidnal - KLE Technological University, Hubballi-31