Created: 2014-05-19 10:39
Updated: 2018-10-18 17:51
License: mit


Build Status

Categories to calculate the edit distance between NSString objects.

#import <MDCDamerauLevenshtein/MDCDamerauLevenshtein.h>

[@"Central Park" mdc_levenshteinDistanceTo:@"Centarl Prak"];         // => 4
[@"Central Park" mdc_damerauLevenshteinDistanceTo:@"Centarl Prak"];  // => 2

MDCDamerauLevenshtein includes two algorithms for calculating the edit distance between NSString objects:

  1. Levenshtein distance calculates the number of insertions, deletions, and substitions necessary in order to convert one string into the other.
  2. Damerau-Levenshtein improves upon Levenshtein to include the transposition of two adjacent characters. Damerau states that some combination of the four operations make up for 80% of all human spelling errors.

Potential applications for this library:

  • Don't just use -[NSString compare:options:] to filter search results, display terms with small edit distances.
  • ...and many more!

Benchmarking Against Other Implmentations

The benchmarking app is included in this repository. It consists of two benchmarks:

  1. Normal: Finding the Levenshtein distance between "sitting" and "kitten"
  2. Large: Finding the Levenshtein distance between two paragraphs of text (409 and 728 characters, respectively)
Library Avg. Time (Normal) Avg. Time (Large)
MDCDamerauLevenshtein 14,218 nanoseconds 0.0792383 seconds
NSString+LevenshteinDistance 17,812 nanoseconds (25% slower) 0.0949104 seconds (20% slower)

koyachi/NSString-LevenshteinDistance only computes Levenshtein distance, not Damerau-Levenshtein, so only Levenshtein benchmarks are included here. The project does not include unit tests, but when benchmarked it produced correct distances.

Cookies help us deliver our services. By using our services, you agree to our use of cookies Learn more