4 ms·
Always choose the one that makes a new 6-gram, or that makes a 6-gram with the fewest previous appearances?
by ikeboy 10y ago
Always choose the one that makes a new 6-gram, or that makes a 6-gram with the fewest previous appearances?
- schoen 10y agoSure, is there an easy way to generate that algorithmically without maintaining an explicit history? Is there a well-known sequence with that property? Do Gray codes have it, for example?
- ikeboy 10y agoYou'd want a sequence that contains every 6-gram exactly once and ends with the same 5 digits as it starts with: such a sequence would be 2^6=64+5=69 bits long, and then you'd repeat the first 64 over and over. (Or just contains exactly once up to cycles.) Some searching tells me this already has a name, see https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence So yes, just take a De Bruijb sequence B(2,6) (algorithms in the link can generate them) and repeat it.
- schoen 10y agoNice!
- smoyer 10y agoYep ... Grays code was my immediate thought too.
- schoen 10y agoThe Gray code turns out to work if you require the n-grams to be aligned to n-character boundaries. So if you interpreted "00001111" as containing only the two 4-grams "0000" and "1111", you're OK; but if you allow arbitrary alignments, so that "00001111" contains the 5 4-grams "0000", "0001", "0011", "0111", and "1111", the Gray code doesn't work. For example, the 4-bit Gray code (under this interpretation) when concatenated into a single bitstream begins "00000001", which then contains the 4-grams "0000", "0000", "0000", "0000", "0001", so the predictor gains an advantage right at the outset. (I didn't check whether it then loses its advantage over time... that's an interesting question.)