Reparera

Re-Pair (förkortning för rekursiv parning ) är en grammatikbaserad komprimeringsalgoritm som, givet en inmatad text, bygger ett rätlinjeprogram, dvs en kontextfri grammatik som genererar en enda sträng: inmatningstexten. Grammatiken är uppbyggd genom att rekursivt ersätta det vanligaste teckenparet som förekommer i texten. När det inte finns något teckenpar som förekommer två gånger, används den resulterande strängen som grammatikens axiom. Därför är den utgående grammatiken sådan att alla regler utom axiomet har två symboler på höger sida.

Hur det fungerar

Konstruktion av ett raklinjeprogram som genererar strängen w="xabcabcy123123zabc" genom att använda Re-Pair

Re-Pair introducerades först av NJ. Larsson och A. Moffat 1999.

I deras artikel presenteras algoritmen tillsammans med en detaljerad beskrivning av de datastrukturer som krävs för att implementera den med linjär tid och rumskomplexitet. Experimenten visade att Re-Pair uppnår höga kompressionsförhållanden och ger bra prestanda för dekompression. Den stora nackdelen med algoritmen är dock dess minnesförbrukning, som är ungefär 5 gånger storleken på ingången. Sådan minnesanvändning krävs för att utföra komprimeringen i linjär tid men gör algoritmen opraktisk för att komprimera stora filer.

Bilden till höger visar hur algoritmen fungerar komprimerar strängen $w=xabcabcy123123zabc$ .

Under den första iterationen ersätts paret $ab$ , som förekommer tre gånger i ${\displaystyle w} ,$ av en ny symbol $R_{1}$ . Vid den andra iterationen, det vanligaste paret i strängen ${\displaystyle w=xR_{1}cR_{1}cy123123zR_{1}c} ,$ vilket är $R_{1}c$ , ersätts av en ny symbol $R_{2}$ . I slutet av den andra iterationen är alltså den återstående strängen $w=xR_{2}R_{2}y123123zR_{2}$ . I de följande två iterationerna ersätts paren $12$ och ${\displaystyle R_{3}3} med symbolerna$ $R_{3}$ och $R_{4 }$ respektive. Slutligen innehåller strängen $w=xR_{2}R_{2}yR_{4}R_{4}zR_{2}$ inget upprepat par och därför används den som axiom för den utgående grammatiken.

Data struktur

För att uppnå linjär tidskomplexitet kräver Re-Pair följande datastrukturer

En sekvens som representerar inmatningssträngen. Position $i$ i sekvensen innehåller den i -te symbolen för inmatningssträngen plus två referenser till andra positioner i sekvensen. Dessa referenser pekar på nästa/föregående positioner, säg $k$ och $m$ , så att samma delsträng börjar vid $w[i]$ , $w[k]$ och $w[m]$ och alla tre förekomsterna fångas av samma referens (dvs. det finns en variabel i grammatiken som genererar strängen).
En prioriterad kö . Varje element i kön är ett par symboler (terminaler eller tidigare definierade par) som förekommer i följd i sekvensen. Prioriteten för ett par ges av antalet förekomster av paret i den återstående sekvensen. Varje gång ett nytt par skapas uppdateras prioritetskön.
En hashtabell för att hålla reda på redan definierade par. Denna tabell uppdateras varje gång ett nytt par skapas eller tas bort.

Eftersom hashtabellen och prioritetskön refererar till samma element (par) kan de implementeras av en gemensam datastruktur som kallas PAIR med pekare för hashtabellen (h_next) och prioritetskön (p_next och p_prev). Dessutom pekar varje PAIR på början av den första (f_pos) och den sista (b_pos) förekomsten av strängen som representeras av PAIR i sekvensen. Följande bild visar en översikt över denna datastruktur.

Följande två bilder visar ett exempel på hur dessa datastrukturer ser ut efter initieringen och efter tillämpning av ett steg i parningsprocessen (pekare till NULL visas inte):

Kodning av grammatiken

När grammatiken väl har byggts för en given inmatningssträng, för att uppnå effektiv komprimering, måste denna grammatik kodas effektivt. En av de enklaste metoderna för att koda grammatiken är den implicita kodningen , som består av att anropa funktionen encodeCFG(X) , som beskrivs nedan, sekventiellt på alla axiomets symboler. Intuitivt kodas regler när de besöks i en djupgående genomgång av grammatiken. Första gången en regel besöks kodas dess högra sida rekursivt och en ny kod tilldelas regeln. Från den punkten, närhelst regeln uppnås, skrivs det tilldelade värdet.

   

  
     
        


   
               
  	     
      
    
    
         
    
      0
     
  


   
  
    
 num_rules_encoded  =  256  // Som standard är den utökade ASCII-teckenuppsättningen grammatikens terminaler.  skrivSymbol  (  symbol  s  )  {  bitslen  =  log  (  num_rules_encoded  );  // Initialt 8, för att beskriva eventuella utökade ASCII-tecken  skriv  s  i  binärt  med  bitslen  -  bitar  }  void  encodeCFG_rec  (  symbol  s  )  {  if  (  s  är  icke  -  terminal  och  detta  är  första  gången  symbol  s  visas  )  {  take  rule  s  →  X  Y  ;  skriv  bit  1  ;  kodaCFG_rec  (  X  );  kodaCFG_rec  (  Y  );  tilldela  symbolens  värde  ++  num_rules_encoded  ;  _  _  }  else  {  skriv  bit  ;  writeSymbol  (  terminal  /  värde  tilldelat  )  }  }  void  encodeCFG  (  symbol  s  )  {  encodeCFG_rec  (  s  );  skriv  bit  1  ;  }

En annan möjlighet är att dela upp grammatikens regler i generationer så att en regel $X\to YZ$ tillhör generation $i$ om minst en av $Y$ eller $Z$ tillhör generation $i-1$ och den andra tillhör generation $j$ med $j\leq i-1$ . Sedan kodas dessa generationer sedan med start från generation { $\displaystyle 0}$ . Detta var den metod som ursprungligen föreslogs när Re-Pair först introducerades. De flesta implementeringar av Re-Pair använder dock den implicita kodningsmetoden på grund av dess enkelhet och goda prestanda. Dessutom tillåter den on-the-fly dekompression.

Versioner

Det finns ett antal olika implementeringar av Re-Pair . Var och en av dessa versioner syftar till att förbättra en specifik aspekt av algoritmen, såsom att minska körtiden, minska utrymmesförbrukningen eller öka kompressionsförhållandet.

Förbättring	År	Genomförande	Beskrivning
Frasbläddring	2003	[1]	Istället för att manipulera inmatningssträngen som en sekvens av tecken, grupperar det här verktyget först tecknen i fraser (till exempel ord). Kompressionsalgoritmen fungerar som Re-Pair men med tanke på de identifierade fraserna som terminalerna i grammatiken. Verktyget accepterar olika alternativ för att bestämma vilken sorts fraser som ska beaktas och kodar den resulterande grammatiken i separerade filer: en som innehåller axiomet och en med resten av reglerna.
Original	2011	[2]	Detta är en av de mest populära implementeringarna av Re-Pair. Den använder de datastrukturer som beskrivs här (de som föreslogs när den ursprungligen publicerades) och kodar den resulterande grammatiken med den implicita kodningsmetoden. De flesta senare versioner av Re-Pair implementeras från och med denna.
Kodning	2013	[3]	Istället för den implicita kodningsmetoden använder den här implementeringen en metod med variabel längd till fast längd, där varje regel (representerad med en sträng med variabel längd) kodas med en kod med fast längd.
Minnesanvändning	2017	[4]	Algoritmen fungerar i två faser. Under den första fasen tar den hänsyn till högfrekvensparen , dvs de som förekommer mer än $\lceil {\sqrt {n}}/3\rceil$ gånger, medan lågfrekvensparen beaktas i andra. Huvudskillnaden mellan de två faserna är implementeringen av motsvarande prioriterade köer.
Kompression	2017	[5]	Denna version ändrar hur nästa par som ska ersättas väljs. Istället för att bara överväga det vanligaste paret, använder den en heuristik som straffar par som inte är koherenta med en Lempel-Ziv-faktorisering av inmatningssträngen.
Kompression	2018	[6]	Denna algoritm minskar storleken på grammatiken som genereras av Re-Pair genom att ersätta maximala upprepningar först. När ett par identifieras som det vanligaste paret, dvs det som ska ersättas i det aktuella steget av algoritmen, utökar MR-repair paret för att hitta den längsta strängen som förekommer lika många gånger som paret som ska ersättas. Den tillhandahållna implementeringen kodar grammatiken genom att helt enkelt lista reglerna i text, därför är detta verktyg enbart för forskningsändamål och kan inte användas för komprimering som det är.

Se även