Abstrakt. Att indexera mycket repetitiva texter - som genomiska databaser, programvaruarkiv och versionsbaserade textsamlingar - har blivit ett viktigt problem sedan millennieskiftet. En relevant kompressibilitetsåtgärd för repetitiva texter är r, antalet körningar i deras Burrows-Wheeler Transform (BWT). En av de tidigaste indexen för repetitiva samlingar, Run-Length FM-index, använde O(r) utrymme och kunde effektivt räkna antalet förekomster av ett mönster av längd m i texten (i loglogaritmisk tid per mönster symbol, med aktuella tekniker). Det var dock inte möjligt att lokalisera positionerna för dessa händelser effektivt inom ett utrymme avgränsat i termer av r. Sedan dess, ett antal andra index med utrymme begränsas av andra mått av repetitivitet - antalet fraser i Lempel-Ziv tolkning, storleken på den minsta grammatik som genererar texten, storleken på den minsta automaton som känner igen textfaktorer - har föreslagits för att effektivt lokalisera, men inte direkt räkna, förekomsten av ett mönster. I detta papper avslutar vi detta långvariga problem, visar hur man utökar Run-Length FM-index så att det kan lokalisera okt förekomster effektivt inom O(r) utrymme (i loglogaritmisk tid vardera), och nå optimal tid O(m + okt) inom O(r log(n/r)) utrymme, på en RAM-maskin av w =  och (log n) bitar. Inom O(r log(n/r) utrymme kan vårt index också räkna i optimal tid O(m). Vi höjer utrymmet till O(rw log σ (n/r)), vi stöder räkna och lokalisera i O(m log(σ)/w) och O(m log(σ)/w + occ) tid, vilket är optimalt i den packade inställningen och inte hade erhållits tidigare i komprimerat utrymme. Vi beskriver också en struktur med hjälp av O(r log(n/r)) utrymme som ersätter texten och extraherar någon text delsträng av längd i nästan optimal tid O(log(n/r) + log(σ)/w). Inom det utrymmet ger vi på liknande sätt direkt tillgång till suffix array, invers suffix array, och längsta gemensamma prefix array celler, och utöka dessa funktioner till full suffix träd funktionalitet, typiskt i O(log(n/r) tid per operation. Slutligen avslöjar vi nya relationer mellan r, storleken på den minsta grammatik som genererar texten, Lempel-Ziv tolkning, och den optimala dubbelriktade tolkning.
Extern personal och andra administrativa utgifter till stöd för politikområdet Hälsa och konsumentskydd
Optimal-Time Text Indexing in BWT-runs Bounded Space
{'venue': 'SODA 2018', 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}