From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 117401 invoked by alias); 11 Jun 2018 21:15:50 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 117116 invoked by uid 89); 11 Jun 2018 21:15:36 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.9 required=5.0 tests=BAYES_00,SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=Successfully X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 11 Jun 2018 21:15:35 +0000 Received: from smtp.corp.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.27]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 00D6530832E9 for ; Mon, 11 Jun 2018 21:15:34 +0000 (UTC) Received: from localhost.localdomain (ovpn-112-10.rdu2.redhat.com [10.10.112.10]) by smtp.corp.redhat.com (Postfix) with ESMTP id 2EADE8E1B4; Mon, 11 Jun 2018 21:15:32 +0000 (UTC) Subject: Re: [PATCH] spellcheck: support transpositions aka Damerau-Levenshtein (PR other/69968) To: David Malcolm , gcc-patches@gcc.gnu.org References: <1525135053-44850-1-git-send-email-dmalcolm@redhat.com> From: Jeff Law Openpgp: preference=signencrypt Message-ID: <01c80ac3-b988-7b63-d068-b3b4eae8b3ec@redhat.com> Date: Mon, 11 Jun 2018 21:15:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.8.0 MIME-Version: 1.0 In-Reply-To: <1525135053-44850-1-git-send-email-dmalcolm@redhat.com> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes X-SW-Source: 2018-06/txt/msg00622.txt.bz2 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