{"action":"closed","number":15689,"pull_request":{"url":"https://api.github.com/repos/Microsoft/TypeScript/pulls/15689","id":119564453,"html_url":"https://github.com/Microsoft/TypeScript/pull/15689","diff_url":"https://github.com/Microsoft/TypeScript/pull/15689.diff","patch_url":"https://github.com/Microsoft/TypeScript/pull/15689.patch","issue_url":"https://api.github.com/repos/Microsoft/TypeScript/issues/15689","number":15689,"state":"closed","locked":false,"title":"Use damerau-levenshtein algorithm for edit distance","user":{"login":"weswigham","id":2932786,"avatar_url":"https://avatars0.githubusercontent.com/u/2932786?v=3","gravatar_id":"","url":"https://api.github.com/users/weswigham","html_url":"https://github.com/weswigham","followers_url":"https://api.github.com/users/weswigham/followers","following_url":"https://api.github.com/users/weswigham/following{/other_user}","gists_url":"https://api.github.com/users/weswigham/gists{/gist_id}","starred_url":"https://api.github.com/users/weswigham/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/weswigham/subscriptions","organizations_url":"https://api.github.com/users/weswigham/orgs","repos_url":"https://api.github.com/users/weswigham/repos","events_url":"https://api.github.com/users/weswigham/events{/privacy}","received_events_url":"https://api.github.com/users/weswigham/received_events","type":"User","site_admin":false},"body":"This PR is opened against #15507 to propose using the damerau-levenshtein edit distance algorithm instead of just levenshtein distance - the primary differentiator being that the damerau variant finds adjacent transpositions and calls them a single edit operation, lowering the edit distance for that score. _Additionally_, I've further tweaked the algorithm to consider transpositions as ever so slightly cheaper than additions/deletions/substitutions, so that a transposed similar name, all other options considered, is guaranteed to come first.\r\n\r\nIn effect, this means that in a situation like this one (attached as a test case to highlight the difference):\r\n```ts\r\nvar twnty;\r\nvar twenty;\r\nvar which = tewnty; \r\n```\r\nWith normal levenshtein we'd suggest `twnty`, but with `damerau-levenshtein` both `twnty` and `twenty` are equally scored, and with my slight alteration to the weights, `twenty` ranks slightly cheaper and becomes the suggestion, which, I argue, is the better suggestion (and in the general case, I believe a transposition to be a more likely error on a keyboard over an omission, addition, or substitution, all other things equal - unfortunately I only have my gut and experience to back me up on this, not data).\r\n\r\nA few new things also got suggestions in the baselines with this change (desirable, looks like) thanks to the often lowered cost.\r\n\r\nThe downside to the `damerau-levenshtein` algorithm is that it needs to keep an extra row of the table around (since to score a transposition it needs the score from two positions ago two rows ago), and it needs to make a few extra comparisons to check for transpositions. However with the top-level bucketing of obviously bad matches, I think the extra cost is likely worth the improved suggestion ranking. ","created_at":"2017-05-09T00:59:14Z","updated_at":"2017-05-23T22:03:01Z","closed_at":"2017-05-23T22:03:01Z","merged_at":null,"merge_commit_sha":"334b8194f155945cb9f8b472b1680e254810dad1","assignee":null,"assignees":[],"requested_reviewers":[],"milestone":null,"commits_url":"https://api.github.com/repos/Microsoft/TypeScript/pulls/15689/commits","review_comments_url":"https://api.github.com/repos/Microsoft/TypeScript/pulls/15689/comments","review_comment_url":"https://api.github.com/repos/Microsoft/TypeScript/pulls/comments{/number}","comments_url":"https://api.github.com/repos/Microsoft/TypeScript/issues/15689/comments","statuses_url":"https://api.github.com/repos/Microsoft/TypeScript/statuses/ed873e36030afffe5cec20f2e0de254458d822a1","head":{"label":"weswigham:damerau-ive-come-to-bargain","ref":"damerau-ive-come-to-bargain","sha":"ed873e36030afffe5cec20f2e0de254458d822a1","user":{"login":"weswigham","id":2932786,"avatar_url":"https://avatars0.githubusercontent.com/u/2932786?v=3","gravatar_id":"","url":"https://api.github.com/users/weswigham","html_url":"https://github.com/weswigham","followers_url":"https://api.github.com/users/weswigham/followers","following_url":"https://api.github.com/users/weswigham/following{/other_user}","gists_url":"https://api.github.com/users/weswigham/gists{/gist_id}","starred_url":"https://api.github.com/users/weswigham/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/weswigham/subscriptions","organizations_url":"https://api.github.com/users/weswigham/orgs","repos_url":"https://api.github.com/users/weswigham/repos","events_url":"https://api.github.com/users/weswigham/events{/privacy}","received_events_url":"https://api.github.com/users/weswigham/received_events","type":"User","site_admin":false},"repo":{"id":37160442,"name":"TypeScript","full_name":"weswigham/TypeScript","owner":{"login":"weswigham","id":2932786,"avatar_url":"https://avatars0.githubusercontent.com/u/2932786?v=3","gravatar_id":"","url":"https://api.github.com/users/weswigham","html_url":"https://github.com/weswigham","followers_url":"https://api.github.com/users/weswigham/followers","following_url":"https://api.github.com/users/weswigham/following{/other_user}","gists_url":"https://api.github.com/users/weswigham/gists{/gist_id}","starred_url":"https://api.github.com/users/weswigham/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/weswigham/subscriptions","organizations_url":"https://api.github.com/users/weswigham/orgs","repos_url":"https://api.github.com/users/weswigham/repos","events_url":"https://api.github.com/users/weswigham/events{/privacy}","received_events_url":"https://api.github.com/users/weswigham/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/weswigham/TypeScript","description":"TypeScript is a superset of JavaScript that compiles to clean JavaScript output.","fork":true,"url":"https://api.github.com/repos/weswigham/TypeScript","forks_url":"https://api.github.com/repos/weswigham/TypeScript/forks","keys_url":"https://api.github.com/repos/weswigham/TypeScript/keys{/key_id}","collaborators_url":"https://api.github.com/repos/weswigham/TypeScript/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/weswigham/TypeScript/teams","hooks_url":"https://api.github.com/repos/weswigham/TypeScript/hooks","issue_events_url":"https://api.github.com/repos/weswigham/TypeScript/issues/events{/number}","events_url":"https://api.github.com/repos/weswigham/TypeScript/events","assignees_url":"https://api.github.com/repos/weswigham/TypeScript/assignees{/user}","branches_url":"https://api.github.com/repos/weswigham/TypeScript/branches{/branch}","tags_url":"https://api.github.com/repos/weswigham/TypeScript/tags","blobs_url":"https://api.github.com/repos/weswigham/TypeScript/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/weswigham/TypeScript/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/weswigham/TypeScript/git/refs{/sha}","trees_url":"https://api.github.com/repos/weswigham/TypeScript/git/trees{/sha}","statuses_url":"https://api.github.com/repos/weswigham/TypeScript/statuses/{sha}","languages_url":"https://api.github.com/repos/weswigham/TypeScript/languages","stargazers_url":"https://api.github.com/repos/weswigham/TypeScript/stargazers","contributors_url":"https://api.github.com/repos/weswigham/TypeScript/contributors","subscribers_url":"https://api.github.com/repos/weswigham/TypeScript/subscribers","subscription_url":"https://api.github.com/repos/weswigham/TypeScript/subscription","commits_url":"https://api.github.com/repos/weswigham/TypeScript/commits{/sha}","git_commits_url":"https://api.github.com/repos/weswigham/TypeScript/git/commits{/sha}","comments_url":"https://api.github.com/repos/weswigham/TypeScript/comments{/number}","issue_comment_url":"https://api.github.com/repos/weswigham/TypeScript/issues/comments{/number}","contents_url":"https://api.github.com/repos/weswigham/TypeScript/contents/{+path}","compare_url":"https://api.github.com/repos/weswigham/TypeScript/compare/{base}...{head}","merges_url":"https://api.github.com/repos/weswigham/TypeScript/merges","archive_url":"https://api.github.com/repos/weswigham/TypeScript/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/weswigham/TypeScript/downloads","issues_url":"https://api.github.com/repos/weswigham/TypeScript/issues{/number}","pulls_url":"https://api.github.com/repos/weswigham/TypeScript/pulls{/number}","milestones_url":"https://api.github.com/repos/weswigham/TypeScript/milestones{/number}","notifications_url":"https://api.github.com/repos/weswigham/TypeScript/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/weswigham/TypeScript/labels{/name}","releases_url":"https://api.github.com/repos/weswigham/TypeScript/releases{/id}","deployments_url":"https://api.github.com/repos/weswigham/TypeScript/deployments","created_at":"2015-06-09T21:48:48Z","updated_at":"2016-02-04T07:57:52Z","pushed_at":"2017-05-13T23:38:50Z","git_url":"git://github.com/weswigham/TypeScript.git","ssh_url":"git@github.com:weswigham/TypeScript.git","clone_url":"https://github.com/weswigham/TypeScript.git","svn_url":"https://github.com/weswigham/TypeScript","homepage":"http://www.typescriptlang.org","size":325477,"stargazers_count":0,"watchers_count":0,"language":"TypeScript","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":1,"mirror_url":null,"open_issues_count":0,"forks":1,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"Microsoft:master","ref":"master","sha":"5143a3ce1603dc4cf0e9466ee43b302c447f78e0","user":{"login":"Microsoft","id":6154722,"avatar_url":"https://avatars1.githubusercontent.com/u/6154722?v=3","gravatar_id":"","url":"https://api.github.com/users/Microsoft","html_url":"https://github.com/Microsoft","followers_url":"https://api.github.com/users/Microsoft/followers","following_url":"https://api.github.com/users/Microsoft/following{/other_user}","gists_url":"https://api.github.com/users/Microsoft/gists{/gist_id}","starred_url":"https://api.github.com/users/Microsoft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Microsoft/subscriptions","organizations_url":"https://api.github.com/users/Microsoft/orgs","repos_url":"https://api.github.com/users/Microsoft/repos","events_url":"https://api.github.com/users/Microsoft/events{/privacy}","received_events_url":"https://api.github.com/users/Microsoft/received_events","type":"Organization","site_admin":false},"repo":{"id":20929025,"name":"TypeScript","full_name":"Microsoft/TypeScript","owner":{"login":"Microsoft","id":6154722,"avatar_url":"https://avatars1.githubusercontent.com/u/6154722?v=3","gravatar_id":"","url":"https://api.github.com/users/Microsoft","html_url":"https://github.com/Microsoft","followers_url":"https://api.github.com/users/Microsoft/followers","following_url":"https://api.github.com/users/Microsoft/following{/other_user}","gists_url":"https://api.github.com/users/Microsoft/gists{/gist_id}","starred_url":"https://api.github.com/users/Microsoft/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Microsoft/subscriptions","organizations_url":"https://api.github.com/users/Microsoft/orgs","repos_url":"https://api.github.com/users/Microsoft/repos","events_url":"https://api.github.com/users/Microsoft/events{/privacy}","received_events_url":"https://api.github.com/users/Microsoft/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/Microsoft/TypeScript","description":"TypeScript is a superset of JavaScript that compiles to clean JavaScript output.","fork":false,"url":"https://api.github.com/repos/Microsoft/TypeScript","forks_url":"https://api.github.com/repos/Microsoft/TypeScript/forks","keys_url":"https://api.github.com/repos/Microsoft/TypeScript/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Microsoft/TypeScript/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Microsoft/TypeScript/teams","hooks_url":"https://api.github.com/repos/Microsoft/TypeScript/hooks","issue_events_url":"https://api.github.com/repos/Microsoft/TypeScript/issues/events{/number}","events_url":"https://api.github.com/repos/Microsoft/TypeScript/events","assignees_url":"https://api.github.com/repos/Microsoft/TypeScript/assignees{/user}","branches_url":"https://api.github.com/repos/Microsoft/TypeScript/branches{/branch}","tags_url":"https://api.github.com/repos/Microsoft/TypeScript/tags","blobs_url":"https://api.github.com/repos/Microsoft/TypeScript/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Microsoft/TypeScript/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Microsoft/TypeScript/git/refs{/sha}","trees_url":"https://api.github.com/repos/Microsoft/TypeScript/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Microsoft/TypeScript/statuses/{sha}","languages_url":"https://api.github.com/repos/Microsoft/TypeScript/languages","stargazers_url":"https://api.github.com/repos/Microsoft/TypeScript/stargazers","contributors_url":"https://api.github.com/repos/Microsoft/TypeScript/contributors","subscribers_url":"https://api.github.com/repos/Microsoft/TypeScript/subscribers","subscription_url":"https://api.github.com/repos/Microsoft/TypeScript/subscription","commits_url":"https://api.github.com/repos/Microsoft/TypeScript/commits{/sha}","git_commits_url":"https://api.github.com/repos/Microsoft/TypeScript/git/commits{/sha}","comments_url":"https://api.github.com/repos/Microsoft/TypeScript/comments{/number}","issue_comment_url":"https://api.github.com/repos/Microsoft/TypeScript/issues/comments{/number}","contents_url":"https://api.github.com/repos/Microsoft/TypeScript/contents/{+path}","compare_url":"https://api.github.com/repos/Microsoft/TypeScript/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Microsoft/TypeScript/merges","archive_url":"https://api.github.com/repos/Microsoft/TypeScript/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Microsoft/TypeScript/downloads","issues_url":"https://api.github.com/repos/Microsoft/TypeScript/issues{/number}","pulls_url":"https://api.github.com/repos/Microsoft/TypeScript/pulls{/number}","milestones_url":"https://api.github.com/repos/Microsoft/TypeScript/milestones{/number}","notifications_url":"https://api.github.com/repos/Microsoft/TypeScript/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Microsoft/TypeScript/labels{/name}","releases_url":"https://api.github.com/repos/Microsoft/TypeScript/releases{/id}","deployments_url":"https://api.github.com/repos/Microsoft/TypeScript/deployments","created_at":"2014-06-17T15:28:39Z","updated_at":"2017-05-23T20:37:51Z","pushed_at":"2017-05-23T21:41:31Z","git_url":"git://github.com/Microsoft/TypeScript.git","ssh_url":"git@github.com:Microsoft/TypeScript.git","clone_url":"https://github.com/Microsoft/TypeScript.git","svn_url":"https://github.com/Microsoft/TypeScript","homepage":"http://www.typescriptlang.org","size":378732,"stargazers_count":22216,"watchers_count":22216,"language":"TypeScript","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":3228,"mirror_url":null,"open_issues_count":2080,"forks":3228,"open_issues":2080,"watchers":22216,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/Microsoft/TypeScript/pulls/15689"},"html":{"href":"https://github.com/Microsoft/TypeScript/pull/15689"},"issue":{"href":"https://api.github.com/repos/Microsoft/TypeScript/issues/15689"},"comments":{"href":"https://api.github.com/repos/Microsoft/TypeScript/issues/15689/comments"},"review_comments":{"href":"https://api.github.com/repos/Microsoft/TypeScript/pulls/15689/comments"},"review_comment":{"href":"https://api.github.com/repos/Microsoft/TypeScript/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/Microsoft/TypeScript/pulls/15689/commits"},"statuses":{"href":"https://api.github.com/repos/Microsoft/TypeScript/statuses/ed873e36030afffe5cec20f2e0de254458d822a1"}},"merged":false,"mergeable":false,"rebaseable":false,"mergeable_state":"dirty","merged_by":null,"comments":9,"review_comments":16,"maintainer_can_modify":false,"commits":6,"additions":59,"deletions":16,"changed_files":5}}
{"actor":{"display_login":"mhegazy"}}