public
Last active

  • Download Gist
NSString+Levenshtein.h
Objective-C
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
NSString+Levenshtein.m
Objective-C
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
readme.md
Markdown

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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.