Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View NSString+Levenshtein.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
//
// NSString+Levenshtein.h
// PyHelp
//
// Modified by Michael Bianco on 12/2/11.
// <http://mabblog.com>
//
// Created by Rick Bourner on Sat Aug 09 2003.
// rick@bourner.com
 
#import <Foundation/Foundation.h>
 
@interface NSString (Levenshtein)
 
// calculate the smallest distance between all words in stringA and stringB
- (CGFloat) compareWithString: (NSString *) stringB matchGain:(NSInteger)gain missingCost:(NSInteger)cost;
 
// calculate the distance between two string treating them each as a single word
- (NSInteger) compareWithWord:(NSString *) stringB matchGain:(NSInteger)gain missingCost:(NSInteger)cost;
@end
View NSString+Levenshtein.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
//
// NSString+Levenshtein.m
// PyHelp
//
// Modified by Michael Bianco on 12/2/11.
// <http://mabblog.com>
//
// Created by Rick Bourner on Sat Aug 09 2003.
// rick@bourner.com
 
#import "NSString+Levenshtein.h"
 
@implementation NSString (Levenshtein)
 
// default match: 0
// default cost: 1
 
// calculate the mean distance between all words in stringA and stringB
- (CGFloat) compareWithString: (NSString *) stringB matchGain:(NSInteger)gain missingCost:(NSInteger)cost {
CGFloat averageSmallestDistance = 0.0;
CGFloat smallestDistance;
NSString *mStringA = [self stringByReplacingOccurrencesOfString:@"\n" withString:@" "];
NSString *mStringB = [stringB stringByReplacingOccurrencesOfString:@"\n" withString:@" "];
NSArray *arrayA = [mStringA componentsSeparatedByString: @" "];
NSArray *arrayB = [mStringB componentsSeparatedByString: @" "];
for (NSString *tokenA in arrayA) {
smallestDistance = 99999999.0;
for (NSString *tokenB in arrayB) {
smallestDistance = MIN((CGFloat) [tokenA compareWithWord:tokenB matchGain:gain missingCost:cost], smallestDistance);
}
averageSmallestDistance += smallestDistance;
}
return averageSmallestDistance / (CGFloat) [arrayA count];
}
 
 
// calculate the distance between two string treating them eash as a single word
- (NSInteger) compareWithWord:(NSString *) stringB matchGain:(NSInteger)gain missingCost:(NSInteger)cost {
// normalize strings
NSString * stringA = [NSString stringWithString: self];
stringA = [[stringA stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]] lowercaseString];
stringB = [[stringB stringByTrimmingCharactersInSet:[NSCharacterSet whitespaceAndNewlineCharacterSet]] lowercaseString];
// Step 1
NSInteger k, i, j, change, *d, distance;
NSUInteger n = [stringA length];
NSUInteger m = [stringB length];
if( n++ != 0 && m++ != 0 ) {
d = malloc( sizeof(NSInteger) * m * n );
// Step 2
for( k = 0; k < n; k++)
d[k] = k;
for( k = 0; k < m; k++)
d[ k * n ] = k;
// Step 3 and 4
for( i = 1; i < n; i++ ) {
for( j = 1; j < m; j++ ) {
// Step 5
if([stringA characterAtIndex: i-1] == [stringB characterAtIndex: j-1]) {
change = -gain;
} else {
change = cost;
}
// Step 6
d[ j * n + i ] = MIN(d [ (j - 1) * n + i ] + 1, MIN(d[ j * n + i - 1 ] + 1, d[ (j - 1) * n + i -1 ] + change));
}
}
distance = d[ n * m - 1 ];
free( d );
return distance;
}
return 0;
}
 
@end
View NSString+Levenshtein.h

Original Reference:
http://www.merriampark.com/ldobjc.htm

Store & Sort Matches Based on Search String

    NSMutableArray *results = [NSMutableArray array];

    for (id item in theItemList) {
        // note the modified weighting, this ends up working similiar to Alfred / TextMate searching method
        // TextMate takes into account camelcase while matching and is a little smarter, but you get the idea
        NSInteger score = [_searchString compareWithWord:[item searchOnString] matchGain:10 missingCost:1];

        [results addObject:[NSDictionary dictionaryWithObjectsAndKeys:[NSNumber numberWithInteger:score], @"score", list, @"item", nil]];
    }

    // sort list
    results = [results sortedArrayUsingComparator: (NSComparator)^(id obj1, id obj2) {
        return [[obj1 valueForKey:@"score"] compare:[obj2 valueForKey:@"score"]];
    }];g

Note:

  • The compareWithString: has not been tested extensively.
  • 64bit compatible
  • There are a couple more modifications / tweaks from the original, look at revision history for details
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.