SQLite FTS is amazingly fast, but allows only prefix (e.g.
query*) matches by default. For Dash, I needed to persuade it to also perform contains matches (e.g.
*query*) or suffix matches (e.g.
How it works
It’s simple, for each term I want to be able to search, I store all of its suffixes.
First of all, the table structure:
CREATE VIRTUAL TABLE searchIndex USING FTS4(suffixes)
Add the term
INSERT INTO searchIndex(suffixes) VALUES("NSString SString String tring ring ing ng g")
Search using suffix queries:
SELECT * FROM searchIndex WHERE suffixes MATCH 'string';
Or contains queries:
SELECT * FROM searchIndex WHERE suffixes MATCH 'str*';
The only downside I could find was that the database got too large. To avoid this, I compress the data into its actual term.
The compress and uncompress functions behave in this way:
compress("NSString SString String tring ring ing ng g") -> NSString uncompress("NSString") -> NSString SString String tring ring ing ng g
This compression reduces the database size to what it would be if only the actual terms were added (without all the suffixes).
Searching over 1,110,381 terms (in 102 docsets) using contains queries:
Search for "string" using LIKE: 3.22 seconds Search for "string" using FTS: 0.18 seconds Search for "s" using LIKE: 6.87 seconds Search for "s" using FTS: 0.22 seconds
I chose SQLite FTS because I was already familiar with SQLite and I also needed to work around some Dash-specific edge cases (e.g. how symbols are treated).
Depending on your project, these may be suitable alternatives: