Obiettivo-c: corrispondenza ricerca fuzzy veloce

Question

Qualcuno sa di un'implementazione rapida della ricerca di ricerca fuzzy per Objective-c? (algoritmo levenshtein-distanza).

Ho trovato questo: https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - ma sfortunatamente è piuttosto lento. Ho bisogno di confrontare questo con un circa 200 stringhe, ed è continuo - per ogni nuova battitura digitata.

Qualche idea?

Answer 1

Se NSString + punteggio fa quello che si vuole, ma è troppo lento, si potrebbe iniziare da accelerarlo. Le righe da 23 a 28 in -scoreAgainst:fuzziness:options: sono codice di installazione che deve essere eseguito solo una volta, non su ciascuno dei 200 confronti. Quindi estrai il codice in un metodo di configurazione e misura nuovamente.

Edit:

Come esercizio, ho forked StringScore, estratto il codice di impostazione e ha fatto modifiche minime per ottenere qualche miglioramento delle prestazioni, quindi misurate esso. Ho usato 1000 parole casuali, raggruppandole in tre ciascuna (ad esempio "bere punti interrotto"). Per ciascuno di questi gruppi ho eseguito il setup (come detto in questa risposta originale) e poi ho confrontato la stringa con tutti i 1000 gruppi. Questo richiede circa 11 secondi sul mio Core 2 Duo.

Quindi il confronto di una parola in 1000 richiede circa 11 ms. Ora hai solo bisogno di 1 a 200, quindi sarà probabilmente ben meno di 10 ms. Questo dovrebbe funzionare per te?

(A proposito, quasi la metà del tempo è ancora spesi in rangeOfString: trovare un singolo carattere, questo può probabilmente fatto molto molto più veloce, ma non ho voglia di entrare nei dettagli dell'algoritmo.)

Answer 2

Non so circa l'algoritmo ti riferisci implementato in Objective-C

c'è un motivo non si utilizza il costruito nel funzionalità di NSPredicate con CoreData. Ho trovato questa ricerca molto veloce più di 200 stringhe.

Per esempio, dato un NSString * Testo di ricerca e di un fetchedResultsController

NSPredicate * predicate = [NSPredicate predicateWithFormat:@"name CONTAINS[cd] %@", searchText]; 

self.filteredListContents = [[[self fetchedResultsController] fetchedObjects] filteredArrayUsingPredicate:predicate]; 

È inoltre possibile utilizzare un NSPredicate su un NSArray, che presumo avete provato e trovato per essere troppo lento.

Dalla documentazione mela

NSMutableArray *array = 
[NSMutableArray arrayWithObjects:@"Nick", @"Ben", @"Adam", @"Melissa", nil]; 

NSPredicate *bPredicate = [NSPredicate predicateWithFormat:@"SELF beginswith[c] 'a'"]; 

NSArray *beginWithB = [array filteredArrayUsingPredicate:bPredicate]; 
// beginWithB contains { @"Adam" }. 

NSPredicate *sPredicate = [NSPredicate predicateWithFormat:@"SELF contains[c] 'e'"]; 

[array filterUsingPredicate:sPredicate]; 
// array now contains { @"Nick", @"Ben", @"Melissa" } 

https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html