Most blogposts I found on this topic don’t explain it from the beginning, so it took me quite a while to figure out how simple and powerful the sqlite fulltext search API (FTS3) actually is.
get the sqlite3 amalgamation sources (v3.6.22) and just unpack it into your iPhone project – sqlite3 as shipped on the …
There’s a spec at the w3c about compressing (XML) named “Efficient XML Interchange” Format taking into account the grammar and likelihood of atoms within the document. They indeed use something similar the the Huffman Coding.
The results are quite impressive – nice charts!
Though CFArray comes with binary search capability, NSArray does not – at least not within the iPhone SDK. The indexOfObject:inSortedRange:options:usingComparator: can’t be found.
Plus the CFArrayBSearchValues doesn’t tell you whether the key actually is part of the list or not. That’s what the Java JDK does, so let’s implement some category methods
-(NSInteger)binarySearch:(id)key;
-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator;
-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator inRange:(NSRange)range;
-(NSInteger)binarySearch:(id)key …
The query optimiser for NSPredicate queries ontop CoreData/SQLite on the iPhone is a bit rudimentary (cough) and so I had to optimise myself to get binary-search enabled quick results:
+(NSPredicate*)findBySearchTerm:(NSString*)rawTerm within:(BOOL)within context:(NSManagedObjectContext*)context
{
NSSet *tokens = ;
if(tokens == nil || tokens.count < = 0)
…