Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP

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
//
// 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
// 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
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.