{"id":13021,"date":"2015-12-04T10:11:13","date_gmt":"2015-12-04T15:11:13","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/?p=13021"},"modified":"2015-12-04T10:12:23","modified_gmt":"2015-12-04T15:12:23","slug":"edit-distance-and-edit-steps","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2015\/12\/04\/edit-distance-and-edit-steps\/","title":{"rendered":"Edit Distance and Edit Steps"},"content":{"rendered":"<p><a href=\"http:\/\/davedelong.tumblr.com\/post\/134367865668\/edit-distance-and-edit-steps\">Dave DeLong<\/a>:<\/p>\n<blockquote cite=\"http:\/\/davedelong.tumblr.com\/post\/134367865668\/edit-distance-and-edit-steps\">\n<p>One of the interesting things about <code>NSMetadataQuery<\/code> is that after it has done its initial &ldquo;gathering&rdquo; of the results, all further updates are reported as a single array of results. Did something get added to the results? Here&rsquo;s a new array of the state of all results now. Did something get removed? Here&rsquo;s another array.<\/p>\n<p>[&#8230;]<\/p>\n<p>In other words, the Levenshtein algorithm can <em>easily<\/em> be generalized to work on any <code>CollectionType<\/code> of <code>Equatables<\/code>. Suddenly, it looks like just the thing we need to implement more-efficient array diffing.<\/p>\n<p>One downside of the Levenshtein algorithm is that it only returns an <code>Int<\/code>. It only tells us how many steps we would need, but not what the actual steps <em>are<\/em>. For that, we&rsquo;ll turn to a specific implementation of the Levenshtein algorithm, called the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Wagner%E2%80%93Fischer_algorithm\">Wagner-Fischer algorithm<\/a>.<\/p>\n<\/blockquote>","protected":false},"excerpt":{"rendered":"<p>Dave DeLong: One of the interesting things about NSMetadataQuery is that after it has done its initial &ldquo;gathering&rdquo; of the results, all further updates are reported as a single array of results. Did something get added to the results? Here&rsquo;s a new array of the state of all results now. Did something get removed? Here&rsquo;s [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[289,30,71,1042,901],"class_list":["post-13021","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-mac","tag-programming","tag-spotlight","tag-swift-programming-language"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13021","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=13021"}],"version-history":[{"count":3,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13021\/revisions"}],"predecessor-version":[{"id":13024,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/13021\/revisions\/13024"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=13021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=13021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=13021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}