A nice trick. It could be used for generalized string search as well as compression. And if you indexed bigrams instead of single characters, it could be even faster.
I especially like the clear, easy-to-understand, well-written presentation along with links to prior art. Wouldn't it be nice if most academic papers were written like this?
Thanks! There are much better indexing algorithms if you don't have such tight resource constraints, but it may be a useful trick to speed up inner loops in some other algorithms.
Benchmarking indicates that it's probably not competitive speed-wise compared to counting sort (of which it is a variant), but the implementation should be pretty easy to understand. It may be good for pedagogical purposes.
I especially like the clear, easy-to-understand, well-written presentation along with links to prior art. Wouldn't it be nice if most academic papers were written like this?