Date: Mon, 7 Mar 2022 19:13:52 -0500
From: Christopher Wellons <wellons@nullprogram.com>
To: Angel Ortega <angel@triptico.com>
Cc: ~skeeto/public-inbox@lists.sr.ht
Subject: Re: Compressing and embedding a Wordle word list
Message-ID: <20220308001352.unpovkjxsnmrf7eu@nullprogram.com>
References: <YiXIayjFm2O0um8e@triptico.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <YiXIayjFm2O0um8e@triptico.com>
User-Agent: NeoMutt/20170113 (1.7.2)

I don't understand the specifics of your scheme. It sounds like delta 
encoding, but I'm not sure. I also don't follow your math.

I hadn't thought of delta encoding, though, so I just tried it out in a 
straightforward way. With each word as a base-26 number, I encoded the 
differences between adjacent words using Huffman coding, and I get 13,182 
bytes of compressed data. Initially this seems much better, except the 
state table has 3,535 entries (from a Huffman tree of 1,768 leaves), many 
of which are large (up to 18 bits). In other words, it pushed all the 
storage into the state table, which isn't particularly efficient.

The largest delta in the original Wordle list is 164,068, meaning every 
delta fits in 18 bits. Storing 12,972 of these makes for 29,187 bytes, 
which isn't quite as good as the Huffman coded version even counting the 
inefficient state table.