Shannon-Fano algoritme
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. september 2018; checks kræver 8 redigeringer .Shannon-Fanó-algoritmen er en af de første kompressionsalgoritmer, som først blev formuleret af de amerikanske videnskabsmænd Claude Shannon og Robert Fano . Denne komprimeringsmetode minder meget om Huffman-algoritmen , som dukkede op et par år senere og er en logisk fortsættelse af Shannon-algoritmen . Algoritmen bruger koder af variabel længde: et hyppigt forekommende tegn kodes med en kode af mindre længde, og et sjældent forekommende tegn kodes med en kode af større længde. Shannon-Fano-koder er præfikskoder, det vil sige, at intet kodeord er et præfiks for noget andet. Denne egenskab gør det muligt entydigt at afkode enhver sekvens af kodeord.
Grundlæggende information
Shannon -Fano-kodning er en præfiks ikke-ensartet kodningsalgoritme. Henviser til probabilistiske komprimeringsmetoder (mere præcist, nulordens kontekstuelle modelleringsmetoder ). Ligesom Huffman -algoritmen bruger Shannon-Fano-algoritmen redundansen af beskeden, som ligger i den uensartede frekvensfordeling af tegnene i dets ( primære ) alfabet, det vil sige, at den erstatter koderne for hyppigere tegn med korte binære tegn. sekvenser og koderne for sjældnere tegn med længere binære sekvenser.
Algoritmen blev uafhængigt udviklet af Shannon (udgivet "Mathematical Theory of Communication", 1948) og senere af Fano (udgivet som en teknisk rapport).
Milepæle
- Symbolerne for det primære alfabet m 1 er skrevet ud i faldende rækkefølge af sandsynligheder.
- Symbolerne i det resulterende alfabet er opdelt i to dele, hvis samlede sandsynlighed for symbolerne er så tæt som muligt på hinanden.
- I præfikskoden tildeles det binære ciffer "0" til den første del af alfabetet og "1" til den anden del.
- De resulterende dele opdeles rekursivt, og deres dele tildeles de tilsvarende binære cifre i præfikskoden.
Når størrelsen af underalfabetet bliver lig med nul eller én, så udvides præfikskoden for de tilsvarende tegn i det primære alfabet ikke yderligere, så algoritmen tildeler præfikskoder af forskellig længde til forskellige tegn. Der er en tvetydighed i trinnet med at dividere alfabetet, da forskellen i de samlede sandsynligheder kan være den samme for to opdelingsmuligheder (under hensyntagen til, at alle tegn i det primære alfabet har en sandsynlighed større end nul).
Algoritme til beregning af Shannon-Fano-koder
Shannon-Fano-koden er bygget ved hjælp af et træ. Konstruktionen af dette træ starter fra roden. Hele sættet af kodede elementer svarer til roden af træet (toppen af det første niveau). Det er opdelt i to delmængder med omtrent samme samlede sandsynligheder. Disse delmængder svarer til to toppunkter på andet niveau, der er forbundet med roden. Yderligere er hver af disse delmængder opdelt i to delmængder med omtrent samme samlede sandsynligheder. De svarer til toppen af det tredje niveau. Hvis delmængden indeholder et enkelt element, svarer det til endeknudepunktet i kodetræet; et sådant undersæt kan ikke opdeles. Vi fortsætter på denne måde, indtil vi får alle endespidserne. Vi markerer grenene af kodetræet med symbolerne 1 og 0, som i tilfældet med Huffman-koden.
Ved konstruktion af Shannon-Fano-koden kan sættet af elementer opdeles, generelt set, på flere måder. Valget af opdeling på niveau n kan forværre opdelingsmulighederne på næste niveau (n + 1) og føre til ikke-optimal kode som helhed. Med andre ord garanterer optimal adfærd ved hvert trin på stien endnu ikke optimaliteten af hele sættet af handlinger. Derfor er Shannon-Fano-koden ikke optimal i generel forstand, selvom den giver optimale resultater under visse sandsynlighedsfordelinger. For den samme sandsynlighedsfordeling kan der generelt konstrueres flere Shannon-Fano-koder, og alle kan give forskellige resultater. Hvis vi bygger alle mulige Shannon-Fano-koder til en given sandsynlighedsfordeling, så vil der blandt dem være alle Huffman-koder, det vil sige optimale koder.
Et eksempel på et kodetræ
Kildetegn:
- A (hyppighed af forekomst 50)
- B (hyppighed af forekomst 39)
- C (hyppighed af forekomst 18)
- D (hyppighed af forekomst 49)
- E (hyppighed af forekomst 35)
- F (hyppighed af forekomst 24)
Modtaget kode: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.
Shannon-Fano-kodning er en ret gammel komprimeringsmetode, og i dag er den af ringe praktisk interesse. I de fleste tilfælde er længden af en sekvens komprimeret ved denne metode lig med længden af en komprimeret sekvens ved hjælp af Huffman-kodning. Men på nogle sekvenser kan der dannes ikke-optimale Shannon-Fano-koder, så Huffman-metoden anses for at være mere effektiv.
Litteratur
- A. M. Yaglom , I. M. Yaglom . Sandsynlighed og information. — M.: Nauka, 1973.
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||