Author: Stan Eisenstat
Subject: Sensitivity of Huffman codes
Date: Thursday, 01 Oct 2020, 15:12:53

Here is an example of the extreme sensitivity of a
Huffman code.  The codes for the 7 characters are

  A 00    B 01    C 100   D 1010  E 1011  F 110   G 111

from which you can construct the Huffman tree.  The
encoding of the 9-character string BBBBBBBBA is

  B  B  B  B  B  B  B  B  A
  01 01 01 01 01 01 01 01 00

(the spaces are for clarity).  But if you flip the first
bit, the decoding is

  110 1010 1010 1010 100
  F   D    D    D    C

which is a 5-character string with a different set of
letters.

More generally, flipping the first bit of the encoding
of a sequence with 2m+2 B's followed by an A and then
decoding gives a sequence with an F, followed by m D's,
followed by a C.

--Stan-