Ruby
Rev 3, 55bytes
i=1
'S, OJ1*$HCH(#%0'.bytes{|e|puts "%x"%i+=e*130&9011}
As a further development on Randomra's idea, consider the output and difference table below. The difference table can be compressed as before, and expanded by multiplying by 65=binary 1000001 and applying a mask 11001100110011. However, Ruby does not work predictably with 8 bit characters (it tends to interpret them as Unicode.)
Surprisingly, the last column is entirely even. Because of this, in compression we can perform a rightshift on the data. This ensures all codes are 7 bit ASCII. In expansion we simply multiply by 65*2=130 instead of 65.
The first column is also entirely even. Therefore we can add 1 to each element (32 to each byte) where necessary, to avoid any control characters. The unwanted 1 is removed by using the mask 10001100110011=9011 instead 11001100110011.
Solution 59 of document linked in question
Start0001
Out Diff
2223 2222
2433 0210
2433 0000
4445 2012
6555 2110
6577 0022
6687 0110
6887 0200
8897 2010
aa99 2202
caa9 2010
cab9 0010
cbbb 0102
cdbd 0202
cddd 0020
Although I use 15 bytes for the table, I only really use 6 bits of each byte, which is a total of 90 bits. There are in fact only 36 possible values for each byte, which is 2.21E23 possibities in total. That would fit in 77 bits of entropy.
Rev 2, 58 bytes, using Randomra's incremental approach
i=0
'UPEIP@bPHPBETTEPRADT'.bytes{|e|puts "%x"%i+=e*65&819}
Finally, something shorter than the naive solution. Randomra's incremental approach, with the bytepacking method of Rev 1.
Rev 1, 72 bytes, golfed version of rev 0
Some changes were made to the baseline to accomodate a reordering of the code for golfing reasons, but still came in longer than the naive solution.
i=0
'UPUIYD&!)$&V*).);c+*'.bytes{|e|i+=1;puts "%x"%(i/2*273+(e*65&819))}
The offsets are encoded into each character of the magic string in base 4 in format BAC, ie with the 1's representing the righthand symbol, the 16's representing the middle symbol, and the lefthand symbol shoehorned into the 4's position. In order to extract them, the ascii code is multiplied by 65 (binary 1000001) to give BACBAC, then it is anded with 819 (binary 1100110011) to give .A.B.C.
Some of the ascii codes have the 7th bit set, i.e. they are 64 higher than the required value, to avoid control characters. Because this bit is removed by the mask 819, this is inconsequential, except when the value of C is 3, which causes a carryover. This has to be corrected in one place only (instead of g we have to use c.)
Rev 0, ungolfed version
a= %w{000 010 000 201 100 100 011 021 110 120 011 112 111 221 211 221 122 123 112 222}
i=2
a.each{|e|puts "%x"%(i/2*273+e.to_i(16));i+=1}
Output
111
121
222
423
433
433
455
465
665
675
677
778
888
998
a99
aa9
abb
abc
bbc
ccc
Explanation
From the following solution, I subtract the baseline, giving the offset which I store as data. The baseline is regenerated as a hexadecimal number in the code by i/2*273 (273 decimal = 111 hex.)
solution baseline offset
AAA AAA 000
ABA AAA 010
BBB BBB 000
DBC BBB 201
DCC CCC 100
DCC CCC 100
DEE DDD 011
DFE DDD 021
FFE EEE 110
FGE EEE 120
FGG FFF 011
GGH FFF 112
HHH GGG 111
IIH GGG 221
JII HHH 211
JJI HHH 221
JKK III 122
JKL III 123
KKL JJJ 112
LLL JJJ 222
