Friday, December 4, 2015

Edit Distance and Edit Steps

Dave DeLong:

One of the interesting things about NSMetadataQuery is that after it has done its initial “gathering” of the results, all further updates are reported as a single array of results. Did something get added to the results? Here’s a new array of the state of all results now. Did something get removed? Here’s another array.

[…]

In other words, the Levenshtein algorithm can easily be generalized to work on any CollectionType of Equatables. Suddenly, it looks like just the thing we need to implement more-efficient array diffing.

One downside of the Levenshtein algorithm is that it only returns an Int. It only tells us how many steps we would need, but not what the actual steps are. For that, we’ll turn to a specific implementation of the Levenshtein algorithm, called the Wagner-Fischer algorithm.

Comments RSS · Twitter

Leave a Comment