Re: [PATCH] spellcheck: support transpositions aka Damerau-Levenshtein (PR other/69968)

[Jeff Law <law@redhat.com>]

On 04/30/2018 06:37 PM, David Malcolm wrote:
> This patch updates the edit-distance algorithm in spellcheck.c to
> support transpositions as well as additions/deletions/substitutions,
> so that a transposition error counts as a distance of 1 rather than 2.
> 
> This leads to saner suggestions for such cases.
> 
> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu.
> 
> OK for trunk?
> 
> gcc/fortran/ChangeLog:
> 	PR other/69968
> 	* misc.c (gfc_closest_fuzzy_match): Update for renaming of
> 	levenshtein_distance to get_edit_distance.
> 
> gcc/ChangeLog:
> 	PR other/69968
> 	* spellcheck-tree.c (levenshtein_distance): Rename to...
> 	(get_edit_distance): ...this, and update for underlying renaming.
> 	* spellcheck-tree.h (levenshtein_distance): Rename to...
> 	(get_edit_distance): ...this.
> 	* spellcheck.c (levenshtein_distance): Rename to...
> 	(get_edit_distance): ...this.  Convert from Levenshtein distance
> 	to Damerau-Levenshtein distance by supporting transpositions of
> 	adjacent characters.  Rename "v1" to "v_next" and "v0" to
> 	"v_one_ago".
> 	(selftest::levenshtein_distance_unit_test_oneway): Rename to...
> 	(selftest::test_edit_distance_unit_test_oneway): ...this, and
> 	update for underlying renaming.
> 	(selftest::levenshtein_distance_unit_test): Rename to...
> 	(selftest::test_get_edit_distance_unit): ...this, and update for
> 	underlying renaming.
> 	(selftest::test_find_closest_string): Add example from PR 69968
> 	where transposition helps
> 	(selftest::test_metric_conditions): Update for renaming.
> 	(selftest::test_metric_conditions): Likewise.
> 	(selftest::spellcheck_c_tests): Likewise.
> 	* spellcheck.h (levenshtein_distance): Rename both overloads to...
> 	(get_edit_distance): ...this.
> 	(best_match::consider): Update for renaming.
> 
> gcc/testsuite/ChangeLog:
> 	PR other/69968
> 	* gcc.dg/spellcheck-transposition.c: New test.
Going to trust you've got the algorithm right :-)

OK

jeff