Skip to content

Instantly share code, notes, and snippets.

@daehn
Created June 29, 2015 10:29
Show Gist options
  • Save daehn/29b901456cb7b65edd49 to your computer and use it in GitHub Desktop.
Save daehn/29b901456cb7b65edd49 to your computer and use it in GitHub Desktop.
Levenshtein Distance calculation in a category on NSString.
@implementation NSString (Levenshtein)
- (NSUInteger)lev_distanceToString:(NSString *)comparisonString {
NSString *referenceString = [self copy];
NSUInteger referenceLength = referenceString.length;
NSUInteger comparisonLength = comparisonString.length;
unsigned long m, n;
unsigned int distanceMatrix[comparisonLength + 1][referenceLength + 1];
distanceMatrix[0][0] = 0;
for (m = 1; m <= comparisonLength; m++) {
distanceMatrix[m][0] = distanceMatrix[m - 1][0] + 1;
}
for (n = 1; n <= referenceLength; n++) {
distanceMatrix[0][n] = distanceMatrix[0][n - 1] + 1;
}
for (m = 1; m <= comparisonLength; m++) {
for (n = 1; n <= referenceLength; n++) {
BOOL equalChars = [referenceString characterAtIndex:n - 1] == [comparisonString characterAtIndex:m - 1];
int penalty = equalChars ? 0 : 1;
distanceMatrix[m][n] = lev_min(distanceMatrix[m - 1][n] + 1,
distanceMatrix[m][n - 1] + 1,
distanceMatrix[m - 1][n - 1] + penalty);
}
}
unsigned int distance = distanceMatrix[comparisonLength][referenceLength];
return distance;
}
unsigned int lev_min(unsigned int a, unsigned int b, unsigned int c) {
return MIN(MIN(MIN(a, b), MIN(a, c)), MIN(b, c));
}
@end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment