File Compression Algorithm

Build frequency table from input bytes. Create leaf node for each symbol with frequency. Build Huffman tree using min-heap: repeatedly merge two lowest-frequency nodes. Traverse tree to assign codes: left=0, right=1. Shorter codes for frequent symbols (e.g.,

LZ77 replaces repeated patterns with back-references. Maintain: search buffer (last N bytes encoded) and look-ahead buffer (next bytes to encode). For each position: find longest match in search buffer. Output: if match found → (offset, length, next_char). If no match → (0, 0, literal_char). Tunable parameters: window size (4KB–32KB — larger = better compression but slower and more memory), minimum match length (3 bytes — shorter matches waste space). LZ77 is the basis of deflate (used in zip, gzip, PNG).

LZW builds a dictionary during compression. Initialize: 256-entry dictionary (ASCII characters). Encoder: find longest match in dictionary. Output index. Add (match + next char) to dictionary. Decoder: receives index, looks up dictionary. Same dictionary builds in sync — no need to transmit it. Variable-length codes: start at 9 bits, grow as dictionary expands, reset at 4096 entries. LZW used in GIF and original ZIP format. Achieves 50–70% compression on typical text.