Efficient Grammar Compression via RLZ-based RePair

Deze paper introduceert RLZ-RePair, een schaalbaar algoritme dat een exacte RePair-grammatica construeert door de RLZ-parsing te benutten, waardoor de geheugengebruik met meer dan 80% daalt ten opzichte van standaard RePair terwijl de compressiekwaliteit behouden blijft.

De kern

Stel je voor dat je een enorme, uit de hand gelopen kookreceptenboek hebt. Het bevat duizenden pagina's, maar als je goed kijkt, zie je dat er veel herhaling is. "Roer de eieren," "Voeg de bloem toe," "Bak 20 minuten" – deze zinnen komen steeds terug.

Het probleem:
De oude manier om zo'n boek te comprimeren (kleiner te maken zonder informatie te verliezen), heet RePair. Het werkt als een slimme editor die elke keer de meest voorkomende zinsdelen zoekt en vervangt door een kort symbool. Bijvoorbeeld: elke keer dat "Roer de eieren" staat, vervangt hij dat door het symbool A.
Het probleem is dat deze editor het hele boek in zijn geheugen moet laden om te kunnen zoeken. Als het boek 100 gigabyte groot is, heb je een supercomputer nodig om het te openen. Voor grote datasets (zoals menselijk DNA of duizenden virale genomen) is dit simpelweg te duur en te traag.

De nieuwe oplossing: RLZ-RePair
De auteurs van dit paper hebben een slimme truc bedacht die we RLZ-RePair noemen. Ze combineren twee ideeën:

1. De Referentie (Het Voorbeeld): In plaats van het hele boek te lezen, kiezen ze één "voorbeeldrecept" (de referentie).
2. De Verwijzingen (RLZ): Ze kijken naar de rest van het boek en zeggen: "Dit stukje staat precies zo in het voorbeeldrecept, op pagina 5." Ze hoeven het dus niet zelf op te slaan, ze verwijzen alleen naar het voorbeeld.

De creatieve analogie: De Bouwmeester en de Blauwdruk

Stel je voor dat je een enorme stad moet bouwen (de data).

• De oude methode (RePair) probeert elke steen, elke baksteen en elk raam van elke woning apart te nummeren en te comprimeren. Om dit te doen, moet de bouwmeester alle bouwplannen van alle huizen tegelijkertijd op zijn bureau hebben liggen. Zijn bureau (het computergeheugen) wordt overvol en hij kan niet meer werken.
• De nieuwe methode (RLZ-RePair) werkt anders. Ze hebben één perfecte "Blauwdruk" (de referentie).
  • Als een huis er precies zo uitziet als op de blauwdruk, zeggen ze: "Dit is Blauwdruk A, sectie 3." Ze hoeven de stenen niet te tellen, ze verwijzen alleen.
  • Nu komt de magie: Ze willen de stad nog kleiner maken door herhalingen te vinden (zoals "Roer de eieren"). In plaats van het hele boek te scannen, kijken ze alleen naar de Blauwdruk.
  • Als ze op de blauwdruk zien dat "Roer de eieren" vaak voorkomt, vervangen ze dat door een symbool op de blauwdruk. Omdat alle andere huizen alleen maar verwijzen naar die blauwdruk, worden die huizen automatisch ook kleiner!

Waarom is dit zo slim?

1. Geen zware geheugens nodig: Omdat ze alleen naar de blauwdruk (de referentie) hoeven te kijken, hebben ze veel minder geheugen nodig. Het is alsof je in plaats van het hele boek te lezen, alleen naar de index kijkt.
2. Precies hetzelfde resultaat: Andere methoden probeerden dit ook, maar ze maakten vaak "snelle" oplossingen die de structuur van de tekst verbraken. Het was alsof je zinnen in stukjes hakte die niet meer logisch waren. RLZ-RePair is zo slim dat hij de exacte zelfde, perfecte grammatica maakt als de zware oude methode, maar dan met een fractie van de moeite.
3. Grootte maakt niet uit: Of je nu 100 of 100.000 virale genomen hebt, deze methode blijft werken. In de tests met SARS-CoV-2 en menselijk DNA bleek dat ze 80% minder geheugen gebruikten dan de oude methode, terwijl het resultaat net zo goed was.

Samenvattend:
Stel je voor dat je een gigantische muur van Lego-blokken moet inpakken.

• De oude manier is: "Ik pak elke steen uit de muur, tel ze, en doe ze in een doos." (Je hebt een enorm magazijn nodig).
• De nieuwe manier (RLZ-RePair) is: "Ik heb één patroon. Ik zeg: 'Deze muur is 90% dat ene patroon.' Ik pak alleen de kleine afwijkingen in. En als ik in dat patroon zie dat 'Rood-Blauw' vaak samenkomt, maak ik daar een nieuw labeltje voor. Omdat de hele muur naar dat patroon verwijst, wordt de hele muur automatisch kleiner."

Het is een manier om enorme hoeveelheden data (zoals ons DNA) compact te houden, zonder dat je een supercomputer nodig hebt om het te openen.

Technische samenvatting

Probleemstelling

Grammaticagebaseerde compressie, en specifiek het RePair-algoritme, staat bekend om zijn vermogen om hiërarchische structuren in tekstdata te ontdekken door het herhaaldelijk vervangen van de meest voorkomende opeenvolgende symbolenparen (bigrammen) door niet-terminals. Hoewel RePair theoretisch uitstekende resultaten levert en compacte grammatica's produceert, heeft het een ernstig nadeel: schaalbaarheid.

• Geheugengebruik: RePair moet de volledige invoer in het geheugen laden om bigramfrequenties te berekenen en te vervangen. Bij grote datasets (zoals genomische sequenties of webdata) leidt dit tot een geheugengebruik dat vele malen groter is dan de invoer zelf, wat het onpraktisch maakt voor moderne, massale datasets.
• Bestaande oplossingen: Methodes zoals BigRePair en Re2Pair proberen dit op te lossen door de invoer eerst te parsen in stukken (bijv. via rsync of recursieve prefix-vrije parsing) en deze apart te comprimeren. Hoewel dit het geheugengebruik verlaagt, introduceert het een kunstmatige structuur in de grammatica. Deze methodes missen vaak frequent voorkomende substrings die over de grenzen van de oorspronkelijke stukken heen lopen, waardoor de grammatica minder compact en theoretisch minder waardevol is dan een echte RePair-grammatica.

Methodologie: RLZ-RePair

De auteurs introduceren RLZ-RePair, een hybride algoritme dat de schaalbaarheid van Relative Lempel-Ziv (RLZ) parsing combineert met de structurele integriteit van RePair.

Kernprincipes:

1. RLZ Parsing: De invoer ($T$) wordt eerst geparsed ten opzichte van een referentiestring ($R$). In plaats van de volledige tekst te laden, wordt $T$ opgesplitst in zinnen (phrases), waarbij elke zin verwijst naar een interval in de referentiestring. Dit reduceert de data die in het geheugen moet worden bewaard aanzienlijk.
2. Niet-expliciete Zinnen (Non-Explicit Phrases): De zinnen worden niet als losse strings opgeslagen, maar als intervallen $(s_i, e_i)$ in de referentiestring. Dit betekent dat de zinnen "virtueel" bestaan; ze verwijzen naar de referentie.
3. Bigram Vervanging:
   • Het algoritme berekent de frequentie van bigrammen over de hele dataset, rekening houdend met zowel binnen-zin als over-zin-grenzen.
   • Bij het vervangen van het meest frequente bigram wordt de referentiestring $R$ aangepast. Omdat de zinnen verwijzen naar $R$, worden de vervangingen automatisch doorgevoerd in de zinnen die naar die delen van $R$ verwijzen.
   • Behoud van invarianten: Als een bigramvervanging de grenzen van een zin raakt (bijvoorbeeld een bigram dat deels in een zin zit en deels buiten), worden de betrokken tekens expliciet gemaakt en opgeslagen als een nieuwe "expliciete zin" (Explicit Phrase). Dit voorkomt dat de referentie-intervallen ongeldig worden.
4. Geheugenoptimalisatie: De referentiestring wordt opgeslagen als een dubbelgekoppelde lijst in een array. Hierdoor kunnen tekens worden verwijderd zonder dat de absolute posities van de resterende tekens hoeven te worden herschreven; alleen de pointers worden bijgewerkt. Dit zorgt ervoor dat het geheugengebruik dicht bij de grootte van de referentiestring blijft, in plaats van de grootte van de volledige invoer.

Belangrijkste Bijdragen

• Exacte RePair Grammatica met Schaalbaarheid: RLZ-RePair is een van de eerste methodes die een grammatica bouwt die structureel identiek is aan die van standaard RePair, maar dit doet met een fractie van het geheugengebruik.
• Integriteit van Hiërarchie: In tegenstelling tot BigRePair en Re2Pair, breekt RLZ-RePair geen frequent voorkomende patronen op die over pars-grenzen heen lopen. Het behoudt de theoretische eigenschappen van RePair (zoals optimaliteit voor Fibonacci-strings).
• Efficiënte Datastructuren: Het gebruik van een geoptimaliseerde intervalboom en hash-tabellen maakt het mogelijk om bigramfrequenties bij te werken en grenscondities te beheren zonder de volledige tekst te hoeven herladen.

Resultaten

De auteurs hebben RLZ-RePair getest op twee grote biologische datasets:

1. SARS-CoV-2 Genomen (400.000 sequenties, ~12 GB):
   • Geheugen: RLZ-RePair gebruikte 82,8% minder geheugen dan de standaard RePair-implementatie (17,17 GB vs. 99,88 GB).
   • Snelheid: De compressietijd was slechts 27,5% trager.
   • Compressie: De gecomprimeerde grootte en het aantal regels waren bijna identiek aan standaard RePair, maar aanzienlijk beter (kleiner) dan BigRePair en Re2Pair.
2. Menselijk Chromosoom 19 (1.024 sequenties, ~60 GB):
   • Schaalbaarheid: Standaard RePair faalde volledig bij deze dataset (geheugenthrashing of tijdslimiet). RLZ-RePair slaagde erin om de volledige dataset te comprimeren met minder dan 42 GB geheugen.
   • Efficiëntie: RLZ-RePair gebruikte 83,1% minder geheugen dan RePair (op een subset van 256 sequenties waar RePair nog wel werkte), met een tijdsverlies van 34,5%.
   • Kwaliteit: De gecomprimeerde bestanden waren kleiner dan die van BigRePair en Re2Pair, wat aantoont dat het behoud van de exacte RePair-structuur leidt tot betere compressie.

Betekenis en Conclusie

RLZ-RePair lost een fundamenteel probleem op in het domein van grammaticagebaseerde compressie: het compromis tussen theoretische optimaliteit en praktische schaalbaarheid.

• Het bewijst dat het mogelijk is om de combinatorische voordelen van RePair te behouden zonder de invoer volledig in het geheugen te hoeven laden.
• Het maakt grammaticagebaseerde compressie haalbaar voor zeer grote, repetitieve datasets (zoals genomische data), waar eerdere methodes ofwel faalden ofwel in kwaliteit inboetten.
• De methode biedt een nieuwe standaard voor het comprimeren van grote collecties vergelijkbare bestanden, waarbij de structuur van de data volledig wordt gerespecteerd.

Kortom, RLZ-RePair combineert de beste eigenschappen van twee werelden: de schaalbaarheid van RLZ en de compressiekracht van RePair, waardoor het een krachtig en praktisch hulpmiddel wordt voor big data-analyse.