How might your method compare to the tech in ripgrep or The Silver Searcher? Are there cases where it might be faster?
The paper under discussion here is about a new way to create an index that also takes time ~linear in the size of the files to be searched, although presumably with a higher constant factor than just searching those files. After you have the index it's possible to search it in time linear in the length of the query rather than the files. This is much faster, but requires storing an index that is at least as large as the original file set, and keeping it up to date as things are changed etc.
If nothing else, I think it is possible to retrieve a complete file from any index that lets you search for substrings and get a full string and position in the file back. Just search for all length 1 substrings, get a map from position -> string, then reconstruct the file from that.
I doubt it's worth storing files this way, because turning the index back into the file sounds very slow. I'd rather just store the file and the index, the time v. space tradeoff seems like a good one if you really care about search performance. That said, I use The Silver Searcher, and it's fast enough with no index that I don't think any of this stuff is worth the effort for searching text files on a file system.
There are actually several tricks at the "string algorithm" level. I didn't invent any of them, but no other search tool combines all of them AFAIK. They are:
* Heuristic for choosing the skip character in boyer moore. (Pick rare bytes.)
* Roll UTF-8 decoding into the regex automaton.
* Use SIMD for multiple string literal search. (This is an unpublished algorithm from Intel's Hyperscan project.)
There was also significant work required for scaling glob matching. Some popular repositories have gitignore files with over 3000 rules.
These are important because ripgrep isn't just for searching code repositories. It should be able to do most things that grep can do, but faster. (The smarter UTF-8 handling is particularly beneficial when searching non-ASCII text.)
Within the context of this thread though, and as someone who has written a linear time suffix array algorithm, the suffix array isn't particularly well suited to the problem of code search. Its constant factors are just too high. Generating an index would take a long time. (Although I haven't read the OP yet.)
> some system call tricks for reading files as quickly as possible.
ripgrep does two different types of searches. One uses memory maps. The other uses standard `read` calls. The latter is actually faster on Linux when searching code repositories. So no real tricks there. :-)
(I wrote an implementation of Ukkonen's suffix tree algorithm in C as maybe my second C program, it was pretty frustrating for a long time)
> (I wrote an implementation of Ukkonen's suffix tree algorithm in C as maybe my second C program, it was pretty frustrating for a long time)
Oh dear. You are brave. I briefly considered implementing Ukkonen's algorithm, but ran away scared. :-)
The reason why I wrote the SAIS implementation was because I am generally interested in text search, and because I was interested in exploring the idea of building an index around suffix arrays. Once I finished my implementation and realized that the cutting edge SACA algorithm (at the time) was as slow as it was, I mostly gave up that idea.
Since then, I've been itching to find use cases for it. As a former computational biologist, I'm familiar with how they are used in that field, but I've been looking for other places as well. Haven't found one yet, although I can think of some specialized (hypothetical) things where it might be useful.