Edit Distance and Edit Steps
One of the interesting things about
NSMetadataQueryis 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
CollectionTypeofEquatables. 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.
