Abstrakt. Eftersom en sekvens S = s 1 s 2... s n heltal mindre än r = O(polylog(n)), visar vi hur S kan representeras med n H 0 (S) + o(n) bitar, så att vi kan veta alla s q, samt svar rank och välj frågor på S, i konstant tid. H 0 (S) är nollordnad empirisk entropi av S och n H 0 (S) ger en informationsteori lägre bundet till bitlagring av någon sekvens S via en fast kodning av dess symboler. Detta utökar tidigare resultat på binära sekvenser och förbättrar tidigare författares adresser: P. Ferragina, Dipartimento di Informatica, Università di Pisa, Largo Bruno Pontecorvo 3, I-56127 Pisa, Italien, e-post: ferragina@di.unipi.it; G. Manzini, Dipartimento di Informatica, Università del Piemonte Orientale, Via Bellini, 25g, I-15100 Alessandria, Italien, e-post: manzini@mfn.unipmn.it; V. Mäkinen, Institutionen för datavetenskap, P.O. Box 68 (Gustaf Hällströmin katu 2b), FI-00014 Helsingfors universitet, e-post: vmakinen@cs.helsinki.fi; G. Navarro (kontaktförfattare), Departamento de Ciencias de la Computación, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile, e-post: gnavarro@dcc.uchile.cl. Tillstånd att göra digitala eller hårda kopior av delar eller allt detta arbete för personligt bruk eller klassrum beviljas utan avgift under förutsättning att kopior inte görs eller distribueras för vinst eller direkt kommersiell fördel och att kopior visar detta meddelande på första sidan eller första skärmen av en skärm tillsammans med den fullständiga citering. Upphovsrätt till delar av detta verk som ägs av andra än ACM måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar, för att omfördela till listor, eller för att använda någon komponent i detta verk i andra verk krävs förhandsgodkännande och/eller avgift. Behörighet kan begäras från publikationsavdelningen, ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, eller behörigheter@acm.org. resultat på allmänna sekvenser där dessa frågor besvaras i O(log r ) tid. För större r kan vi fortfarande representera S i n H 0 (S) + o(n log r ) bitar och svara på frågor i O(log r / log log n) tid. Ett annat bidrag av denna artikel är att visa hur man kombinerar vår komprimerade representation av heltal sekvenser med en komprimering öka teknik för att utforma komprimerade full-text index som skala väl med storleken på ingång alfabetet. Specifikt, vi designar en variant av FM-index som indexerar en sträng T [1, n] inom n H k (T) + o(n) bitar av lagring, där H k (T ) är kth-order empirisk entropi av T. Detta utrymme bundet håller samtidigt för alla k ≤ α log  på n, konstant 0 < α < 1, och  till = O (polylog(n) ). Detta index räknar förekomsten av ett godtyckligt mönster P [1, p] som en delsträng av T i O( p) tid; det lokaliserar varje mönsterförekomst i O(log 1+ε n) tid för varje konstant 0 < ε < 1; och rapporterar en textdelsträng av längd i O( + log 1+ε n) tid. Jämfört med alla tidigare verk, är vårt index det första som tar bort alfabetets storlek beroende från alla frågetider, särskilt, räkna tiden är linjär i mönstrets längd. Ändå använder vårt index i huvudsak samma utrymme för kth-order entropi av texten T, vilket är det bästa utrymmet som erhållits i tidigare arbete. Vi kan också hantera större alfabet av storlek  till = O (n β ), för alla 0 < β < 1, genom att betala o (n log  på) extra utrymme och multiplicera alla frågetider med O (log  på / log log log n).
Till exempel den mest kompakta medlemmen i den så kallade FM-Index familjen REF, som vi helt enkelt kommer att kalla FMI, är en CSA som kräver nH k + o(n log σ) bitar av utrymme och räknar antalet förekomster av ett mönster av längd m i tid O(m (1 + log σ log n )).
Compressed representations of sequences and full-text indexes
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}