Сейчас уже не помню как точно, но в GFXcon я обошелся таблицей в 12К для распаковки GIFов. На элемент я тратил по 3 байта, максимальная длина кода - 12 бит (4096 значений).
"Новая" цепочка была не блинее 2 байт, а все остальные складывались по принципу "старая" цепочка + еще один байт.
Т.е например:
12,32 - это цепочка с кодом 258 (хранится в виде #00,#0C,#20)
12,32,48 = (цепочка 258) + байт 48 - это код 259 (#01,#02,#30)
12,32,48,56 = (цепочка 259) + байт 56 - код 260 (#01,#03,#38)
итд.

Если кто придумает, как можно обойтись менее чем 12К на таблицу - поставлю памятник на центральной площади славного Бобруйска.