String Compression and Encoding Algorithms: RLE, Huffman, LZW

String compression means storing the same text in fewer bits without losing anything. The main lossless techniques are run-length encoding (RLE), which replaces repeats with counts; Huffman coding, which gives common characters short bit codes; LZW, which replaces repeated substrings with dictionary indexes; and the Burrows-Wheeler transform, which rearranges text so the others work better. This post explains each with Python code that was run, and clears up the difference between compression and encoding, a mix-up that causes bugs.

Compression vs. encoding

The two words are often used loosely, so separate them:

• Compression makes data smaller by exploiting redundancy. It is lossless if you can get the original back exactly (zip, gzip, PNG) and lossy if you can’t (JPEG, MP3).
• Encoding changes the representation so another system can read it: UTF-8 for text, Base64 for sending bytes through text-only channels. Encoding usually does not shrink data. Base64 makes it about a third bigger, since every 3 bytes become 4 characters.

import base64
print(base64.b64encode(b"hello world!"))        # b'aGVsbG8gd29ybGQh'
print(len(base64.b64encode(bytes(300))))        # 400

No compression algorithm can shrink every input. If it makes some inputs smaller it must make others larger or equal, which is a counting argument: there are fewer short strings than long ones. Random data is the standard example. Running 1,000 random bytes through zlib gave 1,011 bytes of output, slightly larger than the input.

Run-length encoding

RLE replaces each run of the same character with the count and the character. “AABBBCCCC” becomes “2A3B4C”. It is the simplest scheme and works well when long runs are common, such as simple bitmaps or fax-style images, and badly on ordinary text.

import itertools

def rle(s):
    return "".join(f"{len(list(g))}{ch}" for ch, g in itertools.groupby(s))

print(rle("AABBBCCCC"))   # 2A3B4C
print(rle("abc"))         # 1a1b1c  (longer than the input)

Two things to be careful about. First, with no repeats the output doubles in size, so real formats add a flag or only encode runs of a minimum length. Second, if the original text can contain digits, “2A3B” is ambiguous. Decoding only works when the counts cannot be confused with data, so either escape digits or encode the text in binary with fixed-size counts.

The interview version: LeetCode “String Compression”

LeetCode problem 443, String Compression, asks for RLE in place on a character array. A group of one character stays as that character, a longer group becomes the character followed by the digits of its count, each digit in its own slot, and you return the new length using O(1) extra space. The standard solution uses a read pointer and a write pointer:

def compress(chars):
    write = read = 0
    while read < len(chars):
        ch, start = chars[read], read
        while read < len(chars) and chars[read] == ch:
            read += 1
        chars[write] = ch
        write += 1
        count = read - start
        if count > 1:
            for d in str(count):
                chars[write] = d
                write += 1
    return write

c = list("aabbccc");        k = compress(c); print(k, c[:k])  # 6 ['a', '2', 'b', '2', 'c', '3']
c = list("a");              k = compress(c); print(k, c[:k])  # 1 ['a']
c = list("abbbbbbbbbbbb");  k = compress(c); print(k, c[:k])  # 4 ['a', 'b', '1', '2']

The write pointer can never overtake the read pointer, because a run of length 1 writes one slot and a longer run writes at most 1 + the number of digits, which is never more than the run length. That is the reason overwriting the array in place is safe. Time is O(n), extra space O(1). The usual mistakes are building a separate string (which breaks the in-place requirement) and writing a count of 12 as a single element instead of the two characters “1” and “2”.

Huffman coding

Huffman coding assigns each symbol a variable-length bit code so that frequent symbols get short codes. No code is a prefix of another, so a stream of bits can be decoded without separators. Steps:

1. Count the frequency of each character.
2. Put every character in a min-heap keyed by frequency.
3. Pop the two lowest-frequency nodes, join them under a new node whose frequency is the sum, and push it back. Repeat until one node is left.
4. Walk the tree: left edge is 0, right edge is 1. The path to a leaf is that character’s code.

import heapq, itertools
from collections import Counter

def huffman_codes(s):
    freq = Counter(s)
    if len(freq) == 1:                      # edge case: one distinct symbol
        return {next(iter(freq)): "0"}
    tie = itertools.count()                 # tie-breaker so tuples never compare nodes
    heap = [(f, next(tie), ch) for ch, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        f1, _, a = heapq.heappop(heap)
        f2, _, b = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, next(tie), (a, b)))
    codes = {}
    def walk(node, code):
        if isinstance(node, tuple):
            walk(node[0], code + "0")
            walk(node[1], code + "1")
        else:
            codes[node] = code
    walk(heap[0][2], "")
    return codes

def decode(bits, codes):
    rev = {v: k for k, v in codes.items()}
    out, cur = [], ""
    for b in bits:
        cur += b
        if cur in rev:
            out.append(rev[cur])
            cur = ""
    return "".join(out)

s = "abracadabra"
codes = huffman_codes(s)
bits = "".join(codes[c] for c in s)
print(codes)    # {'a': '0', 'c': '100', 'd': '101', 'b': '110', 'r': '111'}
print(bits, len(bits), len(s) * 8)   # 01101110100010101101110 23 88
print(decode(bits, codes) == s)      # True

“abracadabra” takes 88 bits as 8-bit characters and 23 bits with these codes. Different tie-breaking can give a different but equally short set of codes, so don’t treat the exact codes as the only right answer. Building the tree is O(k log k) for k distinct symbols. Two practical notes: the decoder needs the code table (or the frequencies), which counts against small inputs, and the single-symbol edge case above is a common source of crashes. Huffman is optimal among codes that assign a whole number of bits per symbol. Arithmetic coding and ANS can get closer to the entropy limit by not rounding to whole bits.

LZW

LZW (Lempel-Ziv-Welch) replaces repeated substrings by indexes into a dictionary that the compressor and decompressor build on the fly, so no table is sent. Start with all single characters, extend the current match one character at a time, and when the extended string is not in the dictionary, output the code for the match, add the extended string as a new entry, and restart from the last character.

def lzw_compress(s):
    d = {chr(i): i for i in range(256)}
    nxt, w, out = 256, "", []
    for ch in s:
        wc = w + ch
        if wc in d:
            w = wc
        else:
            out.append(d[w])
            d[wc] = nxt
            nxt += 1
            w = ch
    if w:
        out.append(d[w])
    return out

def lzw_decompress(codes):
    d = {i: chr(i) for i in range(256)}
    nxt = 256
    w = d[codes[0]]
    out = [w]
    for c in codes[1:]:
        entry = d[c] if c in d else w + w[0]   # code not yet known: the tricky case
        out.append(entry)
        d[nxt] = w + entry[0]
        nxt += 1
        w = entry
    return "".join(out)

t = "TOBEORNOTTOBEORTOBEORNOT"
codes = lzw_compress(t)
print(codes)
# [84, 79, 66, 69, 79, 82, 78, 79, 84, 256, 258, 260, 265, 259, 261, 263]
print(len(codes), len(t), lzw_decompress(codes) == t)   # 16 24 True

The decompressor sometimes receives a code it has not added yet, which happens with inputs like “aaaaaaa”. The fix is the w + w[0] line; leaving it out is the classic LZW bug. Here 24 characters become 16 codes. Whether that is smaller in bits depends on how wide the codes are: each code here needs more than 8 bits, so on a short input like this one the saving is small, and LZW pays off on longer, repetitive data. Real implementations cap the dictionary size and reset it, and variants of it appear in GIF and in the old Unix compress tool.

Burrows-Wheeler transform

The Burrows-Wheeler transform (BWT) doesn’t compress anything by itself. It permutes the characters so that equal characters tend to land next to each other, which then makes RLE or Huffman-style coders much more effective. It is the first stage of bzip2. To compute it, append a unique end marker, sort all rotations of the string, and take the last column:

def bwt(s):
    s += "$"
    return "".join(r[-1] for r in sorted(s[i:] + s[:i] for i in range(len(s))))

def ibwt(b):
    table = [""] * len(b)
    for _ in range(len(b)):
        table = sorted(b[i] + table[i] for i in range(len(b)))
    return next(r for r in table if r.endswith("$"))[:-1]

print(bwt("BANANA"))          # ANNB$AA
print(ibwt(bwt("BANANA")))    # BANANA

This version is O(n² log n) and meant for learning. Production code builds a suffix array instead. Note that the marker must sort before every other character; here “$” does in ASCII.

What real tools use

Everyday formats combine ideas rather than using one. DEFLATE, the algorithm inside zip, gzip and zlib, combines LZ77 (replace repeats with back-references to earlier data) with Huffman coding (RFC 1951). Python exposes it as zlib:

import zlib
text = ("the quick brown fox " * 50).encode()
z = zlib.compress(text, 9)
print(len(text), len(z), zlib.decompress(z) == text)   # 1000 37 True

For application code, use the library. Write your own only to learn, for a constrained format, or because an interview asks. Newer general-purpose compressors such as zstd and Brotli follow the same pattern of a dictionary or match stage followed by entropy coding, tuned for speed or ratio.

Choosing a technique

Technique	Exploits	Good for	Weak spot
RLE	Consecutive repeats	Bitmaps, sparse data, interview problems	Doubles size when there are no runs
Huffman	Uneven symbol frequencies	Final stage of many formats	Needs the code table; whole-bit codes
LZW	Repeated substrings	Text and similar data, no table sent	Dictionary growth; short inputs
BWT + RLE/Huffman	Context similarity	Text, via bzip2-style pipelines	Needs the whole block in memory

Before choosing, measure on your real data: ratio, compression speed, decompression speed and memory all matter, and they pull in different directions.

Practice

If strings are the weak spot, work through the AlgoCademy String Immutability lesson first, since it explains why repeated concatenation in a loop is slow and why the two-pointer in-place approach matters. For a deeper look at string search, see our post on the rolling hash. Then implement RLE, Huffman and LZW from memory and test them on empty strings, single characters, all-equal strings and strings with digits.