Redigera avståndet mellan strängar a~... a m och bl "'" b, är den minsta kostnaden s för en sekvens av redigering steg (insättningar, raderingar, ändringar) som omvandlar en sträng till den andra. En välkänd tabulatormetod beräknar s samt motsvarande redigeringssekvens i tid och i mellanslag O(mn) (i mellanslag O(min(m, n)) om redigeringssekvensen inte krävs). Med utgångspunkt från denna metod utvecklar vi en förbättrad algoritm som fungerar i tid och i rymden O(s. min(m, n)). En annan förbättring med tiden O(s.min(s.m, n) och utrymmet O (s-min(s, m, n)) ges för specialfallet där alla redigeringssteg har samma kostnad oberoende av de berörda tecknen. Om redigeringssekvensen som ger kostnad s inte krävs, kan våra algoritmer implementeras i rymden O(min(s, m, n)). Eftersom s= O(max(m, n)) är de nya metoderna alltid asymptotiskt lika bra som den ursprungliga tabellformsmetoden. Som en biprodukt erhålls algoritmer som, med tanke på ett tröskelvärde t, testar i tid O (t'min(m,n)) och i rymden O(min(t,m,n) om s < <.t. Slutligen analyseras olika generaliserade redigeringsavstånd och villkor anges under vilka våra algoritmer kan användas i samband med utökade redigeringsoperationer, inklusive t.ex. införlivande av intilliggande tecken.
Det är välkänt att redigeringen avstånd verikation problem under avstånd tröskel K kan lösas i tid O (N K) genom dynamisk programmering REF.
Algorithms for Approximate String Matching
{'venue': 'Information and Control', 'journal': 'Information and Control', 'mag_field_of_study': ['Computer Science', 'Mathematics']}