Using NSPredicate to filter NSArray and find similar strings

Question

I've been trying to work out how to use NSPredicate but I am struggling to work out how to use "like".

For example, lets say I have an NSArray:

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

and I accidentally search for the word "Nink" instead of "Nick".

Can I use NSPredicate to return an array with the object "Nick"?

This is what I have tried so far:

NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF like[cd] %@", @"nink"];

[array filterUsingPredicate:bPredicate];

An empty array is returned.

Is this something that NSPredicate is capable of or am I wasting my time here?

To clarify your Q: You are looking for a way to match a string that is not matched by the predicate? What about "Nock", "Nonk"? — Amin Negm-Awad
Yes, even if the search term was nock or nonk than I would like it to return nick. Basically like auto correct. — Shayno
So, essentially, you want a predicate that returns the keys with the lowest Levenshtein Distance (or similar metric) to the search term, correct? — Itai Ferber
@ItaiFerber Yes, but only to a certain extent, for example if the search term was Trevor, than I would not like to return any results as Trevor is not a close enough match to the other names in the array. — Shayno

Itai Ferber Itai Ferber · Accepted Answer · 2016-05-31T02:50:39

What you are looking for is a custom predicate which uses a bounded Levenshtein Distance to filter out words that are sufficiently different from a target word.

Assuming you use an implementation of Levenshtein Distance as found in this gist, your code will look approximately like this:

NSPredicate *distancePredicate = [NSPredicate predicateWithBlock:^(NSString *name, NSDictionary<NSString *, id> *bindings) {
    // key is the string you're looking for (e.g. 'nink')
    NSString *key = bindings[@"key"];

    // Calculate the Levenshtein Distance. This may be different depending
    // on how you implement it. You may want to weight matchGain and
    // missingCost differently.
    NSInteger score = [key compareWithWord:name matchGain:0 missingCost:1];

    // Only include words that are "close enough", i.e. within two a letter
    // difference.
    return (BOOL)(score < 2);
}];

This predicate defines a general predicate "template", which you can then use to filter the array with the actual string you're looking for:

    NSDictionary<NSString *, id> *bindings = @{@"key": @"Nink"};
    NSMutableArray *array = [NSMutableArray arrayWithObjects:@"Nick", @"Ben", @"Adam", @"Melissa", nil];
    NSIndexSet *indices = [array indexesOfObjectsPassingTest:^(id object, NSUInteger index, BOOL *stop) {
        return [distancePredicate evaluateWithObject:object substitutionVariables:bindings];
    }];

    NSArray *results = [array objectsAtIndexes:indices];

BTW, there is nothing special about the word @"key"; you can change that to be any string identifying the substitution (e.g. @"name", @"term", etc., are all valid). The key you provide in the substitution variables is the key you should use to retrieve the value.

Using NSPredicate to filter NSArray and find similar strings

1 Answers