3 ms·
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 f
by ccleve 13y ago
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?
- silentbicycle 13y agoThanks! 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. I realized yesterday that it can also be used as the basis for a linear-time sorting algorithm: https://gist.github.com/silentbicycle/8389129 https://gist.github.com/silentbicycle/8389129 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.