Abstrakt. Problemet med redigeringsavstånd är ett klassiskt grundläggande problem inom datavetenskapen i allmänhet, och i kombinationsmönster som matchar i synnerhet. Standarden dynamisk programmering lösning för detta problem beräknar redigeringsavståndet mellan ett par strängar av total längd O(N ) i O(N 2 ) tid. Hittills har denna quadratic övre gräns aldrig förbättrats avsevärt för allmänna strängar. Det finns dock kända tekniker för att bryta denna bundna i fall strängarna är kända för att komprimera väl under en viss komprimeringsschema. Grundidén är att först komprimera strängarna och sedan beräkna redigeringsavståndet mellan de komprimerade strängarna. Som det visar sig, praktiskt taget alla kända o(N 2 ) redigera-distansalgoritmer fungerar, i någon mening, under samma paradigm som beskrivs ovan. Det är därför naturligt att fråga om det finns en enda edit-distansalgoritm som fungerar för strängar som komprimeras under något komprimeringssystem. En refrasering av denna fråga är att fråga om en enda algoritm kan utnyttja kompressibilitet egenskaper strängar under någon komprimeringsmetod, även om varje sträng komprimeras med hjälp av en annan kompression. I detta dokument har vi föresatt oss att besvara denna fråga med hjälp av straight-line-program. Dessa ger en generisk plattform för att representera många populära komprimeringssystem inklusive LZ-familjen, Run-Length Encoding, Byte-Pair Encoding, och ordboksmetoder. För två strängar av total längd N med raka program representationer av total storlek n, presenterar vi en algoritm som körs i O(n 1.4 N 1.2 ) tid för att beräkna redigeringsavståndet för dessa två strängar under någon rationell poängfunktion, och en O (n 1.34 N 1.34 )-tid algoritm för godtyckliga poängsättning funktioner. Detta förbättrar på en ny algoritm av Tiskin som körs i O (nN 1.5 ) tid, och fungerar endast för rationella poäng funktioner.
Hermelin m.fl. REF generalisera idén om att tillämpa redigeringsavstånd på de komprimerade formerna av strängarna och presentera en generisk plattform för populära komprimeringssystem som LZ-familjen, Run-Length Encoding, Byte-Pair Encoding och ordboksmetoder.
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
{'venue': '26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009 (2009) 529-540', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}