Aritmetisk kodning

Aritmetisk kodning  är en av entropikomprimeringsalgoritmerna .

Till skillnad från Huffman-algoritmen har den inte en hård konstant överensstämmelse mellan indatatecken och grupper av bitar i utmatningsströmmen. Detta ger algoritmen mer flexibilitet när det gäller att representera bråkteckenfrekvenser.

Som regel överträffar den Huffman-algoritmen när det gäller komprimeringseffektivitet, låter dig komprimera data med entropi mindre än 1 bit per kodat tecken, men vissa versioner har patentrestriktioner från IBM . [ett]

Egenskaper

Ger nästan optimalt kompressionsförhållande i form av Shannon-kodningsentropiuppskattning. Nästan lite krävs för varje symbol, där  är informationsentropin för källan.

Till skillnad från Huffman-algoritmen visar den aritmetiska kodningsmetoden hög effektivitet för bråkdelar av olikformiga intervall av sannolikhetsfördelningen för de kodade symbolerna. Men i fallet med en lika sannolik fördelning av tecken, till exempel för en bitsträng 010101…0101 med längden s , närmar sig den aritmetiska kodningsmetoden prefixet Huffman-koden och kan till och med ta en bit mer. [2]

Hur det fungerar

Låt det finnas ett visst alfabet, samt data om hur ofta tecken används (valfritt). Betrakta sedan linjesegmentet från 0 till 1 på koordinatlinjen.

Låt oss kalla detta segment fungerande. Låt oss ordna punkterna på det på ett sådant sätt att längden på de bildade segmenten kommer att vara lika med frekvensen för att använda symbolen, och varje sådant segment kommer att motsvara en symbol.

Låt oss nu ta en symbol från strömmen och hitta ett segment för den bland de nybildade, nu har segmentet för denna symbol börjat fungera. Låt oss dela upp det på samma sätt som vi delar upp segmentet från 0 till 1. Låt oss utföra denna operation för ett visst antal på varandra följande tecken. Sedan väljer vi valfritt tal från arbetssegmentet. Bitarna av detta nummer, tillsammans med längden på dess bitpost, är resultatet av den aritmetiska kodningen av de använda strömsymbolerna.

Ett exempel på hur den aritmetiska kodningsmetoden fungerar

Probabilistisk modell

Med hjälp av den aritmetiska kodningsmetoden kan man uppnå en nästan optimal representation för en given uppsättning symboler och deras sannolikheter (enligt Shannons källentropikodningsteori kommer den optimala representationen att tendera att vara −log 2 P bitar per symbol vars sannolikhet är P ). Datakomprimeringsalgoritmer som använder den aritmetiska kodningsmetoden i sitt arbete, före direktkodning, bildar en indatamodell baserad på kvantitativa eller statistiska egenskaper, såväl som all ytterligare information som finns i den kodade sekvensen av upprepningar eller mönster - all ytterligare information som tillåter du att klargöra sannolikheten för utseendet av symbolen P i kodningsprocessen. Uppenbarligen, ju mer exakt symbolsannolikheten bestäms eller förutsägs, desto högre blir kompressionseffektiviteten.

Betrakta det enklaste fallet med en statisk modell för kodning av information som kommer från ett signalbehandlingssystem. Signaltyper och deras motsvarande sannolikheter är fördelade enligt följande:

• 60 % chans för ett neutralt signalvärde, eller NEUTRAL.
• 20 % chans för ett positivt signalvärde, eller POSITIVT.
• 10 % chans för ett negativt signalvärde, eller NEGATIV.
• 10 % chans för ett tecken på slutet av sekvensen, eller END-OF-DATA.

Uppkomsten av den sista symbolen för avkodaren betyder att hela sekvensen har avkodats framgångsrikt (som ett alternativt tillvägagångssätt, men inte nödvändigtvis mer framgångsrikt, kan en blockalgoritm med fast längd användas) .

Det bör också noteras att vilken uppsättning symboler som helst kan betraktas som alfabetet för metodens probabilistiska modell, baserat på egenskaperna hos det problem som ska lösas. Mer heuristiska tillvägagångssätt, med hjälp av det grundläggande schemat för den aritmetiska kodningsmetoden, tillämpar dynamiska eller adaptiva modeller . Tanken med dessa metoder är att förfina sannolikheten för det kodade tecknet genom att ta hänsyn till sannolikheten för det tidigare eller framtida sammanhanget (det vill säga sannolikheten för förekomsten av det kodade tecknet efter ett visst k:te antal tecken till vänster eller höger, där k är ordningen för sammanhanget).

Meddelandekodning

Låt oss ta följande sekvens som ett exempel:

NEUTRAL NEGATIV SLUT-PÅ-DATA

Låt oss först dela upp segmentet från 0 till 1 enligt signalernas frekvenser. Vi kommer att bryta segmentet i den ordning som anges ovan: NEUTRAL - från 0 till 0,6; NEGATIV - från 0,6 till 0,8; END-OF-DATA - från 0,8 till 1.

Låt oss nu börja koda från det första tecknet. Det första tecknet - NEUTRAL motsvarar ett segment från 0 till 0,6. Låt oss dela detta segment på samma sätt som segmentet från 0 till 1.

Låt oss koda det andra tecknet - NEGATIV. På segmentet från 0 till 0,6 motsvarar det segmentet från 0,48 till 0,54. Låt oss dela detta segment på samma sätt som segmentet från 0 till 1.

Låt oss koda det tredje tecknet - END-OF-DATA. På segmentet från 0,48 till 0,54 motsvarar det segmentet från 0,534 till 0,54.

Eftersom detta var det sista tecknet är kodningen klar. Det kodade meddelandet är ett segment från 0,534 till 0,54 eller valfritt nummer från det, till exempel 0,538.

Meddelandeavkodning

Anta att vi behöver avkoda ett meddelande med den aritmetiska kodningsmetoden enligt modellen som beskrivs ovan. Det kodade meddelandet representeras av bråkvärdet 0,538 (för enkelhetens skull används decimalrepresentationen av bråkdelen istället för den binära basen). Det antas att det kodade meddelandet innehåller exakt så många tecken i det betraktade numret som nödvändigt för att unikt återställa originaldata.

Det initiala tillståndet för avkodningsprocessen sammanfaller med kodningsprocessen och intervallet [0,1) beaktas. Baserat på den kända probabilistiska modellen faller bråkvärdet 0,538 inom intervallet [0, 0,6). Detta låter dig bestämma det första tecknet som valdes av kodaren, så dess värde matas ut som det första tecknet i det avkodade meddelandet.

Anteckningar

1. ↑ Historien om utvecklingen av informationskomprimeringsteori Arkivexemplar av 28 december 2010 på Wayback Machine / Compression.ru, Sarmin Alexey, 10 mars 2011
2. ↑ Dr. Dobbs nyhetsbrev för datakomprimering arkiverat 11 december 2017 på Wayback Machine 13 augusti 2001

Länkar

• (13 augusti 2001) Dobbs nyhetsbrev för datakomprimering