En längst gemensam förlängning (LCE) fråga på en text T av längd N ber om längden på den längsta gemensamma prefix av suffix som börjar vid givna två positioner. Vi visar att signaturen kodar G storlek w = O(min(z log N log * M, N )) [Mehlhorn et al., Algorithmica 17.2:183-198, 1997] av T, som kan ses som en komprimerad representation av T, har en förmåga att stödja LCE frågor i O(log N + log l log * M ) tid, där l är svaret på frågan, z är storleken på Lempel-Ziv77 (LZ77) faktorisering av T, och M ≥ 4N är ett heltal som kan hanteras i konstant tid under ordet RAM-modell. I komprimerat utrymme är detta den snabbaste deterministiska LCE-datastrukturen i många fall. Dessutom kan G förbättras för att stödja effektiva uppdateringsåtgärder: Efter bearbetning G i O (wfA) tid, kan vi infoga / ta bort någon (under) sträng av längd y till / från en godtycklig position av T i O (y + log N log * M ) fA) tid, där fA = O (min { log log M log log w log log log M, log w log log w }). Detta ger den första fullt dynamiska LCE-datastrukturen som arbetar i komprimerat utrymme. Vi presenterar också effektiva konstruktionsalgoritmer från olika typer av ingångar: Vi kan konstruera G i O(N fA) tid från okomprimerad sträng T ; i O(n log log(n log * M ) log N log * M ) tid från grammatikkomprimerad sträng T representeras av en rak linje program av storlek n; och i O(zfA log N log * M ) tid från LZ77-komprimerad sträng T med z faktorer. Utöver ovanstående bidrag visar vi flera tillämpningar av våra datastrukturer som förbättrar tidigare mest kända resultat vid grammatikkomprimerad strängbearbetning.
Som en annan tillämpning av signaturkodningar, Nishimoto et al. visade att signaturkodningar för en dynamisk sträng T kan stödja Longest Common Extension (LCE) frågor om T effektivt i komprimerat utrymme REF.
Fully dynamic data structure for LCE queries in compressed space
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}