Homec4science

Introduce a class for calculating Damerau-Levenshtein edit distances and strings

Authored by epriestley <git@epriestley.com> on Feb 21 2013, 19:13.

Description

Introduce a class for calculating Damerau-Levenshtein edit distances and strings

Summary:
This helps us attack three problems:

  • We currently can't give string transpositions a cost when evaluating British spellings for arc, so "alnd" has equal edit distances to "amend" and "land".
  • The intraline differ isn't UTF-8 aware, and the algorithm is character oriented.
  • ArcanistDiffUtils::buildLevenshteinDifferenceString() is a tangled mess of disgusting garbage.

Introduce a better-factored implementation of Damerau-Levenshtein with options to price trnspositions and build edit strings.

Test Plan: Unit tests.

Reviewers: vrana

Reviewed By: vrana

CC: aran

Maniphest Tasks: T2379

Differential Revision: https://secure.phabricator.com/D5032

Details

Committed
epriestley <git@epriestley.com>Feb 21 2013, 19:13
Pushed
aubortMar 17 2017, 12:03
Parents
rPHUdc3ad4554c22: Fix parsing of XHPAST parse error
Branches
Unknown
Tags
Unknown

Event Timeline

epriestley <git@epriestley.com> committed rPHU2280636464d4: Introduce a class for calculating Damerau-Levenshtein edit distances and strings (authored by epriestley <git@epriestley.com>).Feb 21 2013, 19:13