Vi presenterar en nästan linjär tid algoritm som approximerar redigeringsavståndet mellan två strängar inom en polylogaritmisk faktor. För strängar av längd n och varje fast ε > 0, beräknar algoritmen a (log n) O(1/ε) approximation i n 1+ε tid. Detta är en exponentiell förbättring jämfört med den tidigare kända approximationsfaktorn, 2Õ ( ε log n), med en jämförbar körtid [Ostrovskij och Rabani, J. ACM 2007; Andoni och Onak, STOC 2009]. Detta resultat uppstår naturligt i studiet av en ny asymmetrisk frågemodell. I denna modell, indata består av två strängar x och y, och en algoritm kan komma åt y på ett obegränsat sätt, samtidigt som debiteras för att fråga varje symbol av x. I själva verket får vi vårt huvudsakliga resultat genom att utforma en algoritm som gör ett litet antal frågor i denna modell. Vi ger sedan en nästan-matchande lägre gräns på antalet frågor. Vår nedre gräns är den första som avslöjar hårdheten i redigeringsavståndet som härrör från att inmatningssträngarna är "repetitiva", vilket innebär att många av deras understrängar är ungefär identiska. Följaktligen ger vår nedre gräns den första rigorösa separationen mellan redigeringsavstånd och Ulamavstånd. 1 Resultatet av [26] gäller för alfabet med konstant storlek. Det utökades till godtyckligt stora alfabet i [11], om än med en O (log log n) 2 faktor förlust i körtid. 2 Vi ska inte försöka att presentera en komplett lista över resultat för begränsade inställningar (t.ex., genomsnittlig-case/smoothed analys, svagt repetitiva strängar, och avgränsade avstånd-regime), för varianter av distansfunktionen (t.ex., tillåter mer redigeringsåtgärder), eller för relaterade beräkningsproblem (såsom mönstermatchning, närmaste grannsökning, och skissning). Se även undersökningarna [29] och [31].
För strängredigeringsavstånd beror nuvarande bästa approximationsförhållande på (log n) O( 1 ) i n 1+ körtid för varje fast > 0 på Andoni, Krauthgamer och Onak REF.
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}