Expand description
Whether a string holds some pieces in order, answered on its FSST codes without decompressing it.
LIKE '%special%requests%' asks whether special is somewhere in a string and requests is
somewhere after it. Finding each piece as soon as it can be found is never worse than finding it
later, so the question is a walk over the bytes with one automaton per piece, each one handing
over to the next when its piece is complete. Laid end to end that is one automaton with a state
for every byte of every piece and one more for having found them all, and a string holds the
pieces when its walk ends in that last state.
A compressed string is codes, and each code stands for up to eight bytes. Walking a code is
walking its bytes, and since the bytes a code stands for do not change within a chunk, where a
code takes each state can be worked out once per chunk and then looked up. A string is then one
lookup per code rather than a decompression, a copy and a search over the bytes, and the lookups
are filled in only for the states a string actually reached. See spec/perf/44-like-on-codes.md.