Vi ser över problemet med att indexera en sträng S[1.n] för att stödja att hitta alla delsträngar i S som matchar ett givet mönster P [1.1.m] med de flesta k fel. Tidigare lösningar kräver antingen ett index av storlek exponentiellt i k eller behov (m k ) tid för sökning. Motiverade av indexeringen av DNA, undersöker vi utrymme effektiva index som upptar endast O(n) utrymme. För k = 1, ger vi ett index för att stödja matchning i O(m + occ + log n log log n) tid. Den tidigare bästa lösningen för att uppnå denna tids komplexitet kräver ett index av O(n log n) utrymme. Det nya indexet kan också användas för att förbättra befintliga index för k ≥ 2 fel. Bland annat kan det stödja 2-terror matchning i O(m log n log log n + occ) tid, och k-terror matchning, för alla k > 2, i O(m k‐1 log n log log n + occ) tid.
Chan och Al. REF O(n log n) O(m + log n log log n + occ)
Compressed Indexes for Approximate String Matching
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}