Start Logga In Skriv Artikel Om Oss
Vad söker du?
Allt om 'Huffmankodning'

Huffmankodning

Innehåll- 1. Mer teknisk beskrivning

Huffmankodningär en ickeförstörande kompressionsalgoritm baserad på statistisk analys av tecknena i datan som ska komprimeras. När sannolikheten för tecknena är kända skapas ett så kallat huffmanträd där vanligt förekommande tecken hamnar nära trädets rot och ovanliga tecken hamnar långt ut i trädet. Koden för ett visst tecken blir sedan "vägbeskrivningen" från trädets rot till lövet för tecknet i fråga, vänster ger en nolla och höger ger en etta. Huffmankodningen skapades av David A. Huffman.

1. Mer teknisk beskrivning

Exempel: Vi vill komprimera strängen "AAABBAC".

1. Skapa en frekvenstabell för tecknenaA: 4B: 2C: 1

2. Skapa en nod för varje tecken tillsammans med dess sannolikhet

|A:4| |B:2| |C:1|

3. Slå ihop noder

  • välj de två noder som har lägst sannolikhet.
  • skapa en ny nod med summan av de två nodernas sannolikheter och med de två noderna som barn.
  • upprepa tills det bara finns en toppnod

B och C har lägst sannolikhet|:3| |A:4| / |B:2||C:1|

Bara två toppnoder kvar, slå ihop dom |:7|/ |:3||A:4| / |B:2||C:1|

4. Skapa bitsträngarna för varje tecken genom att traversera trädetEn nolla för vänster och en etta för högerA: 1B: 00C: 01

5. Skriv ut bitsträngen för varje tecken i datan som ska komprimeras

AAABBAC 1 1 1 00 00 1 01 Vi fick alltså totalt 10 bitar

Vi fick en kompression på ungefär 1,42 bits per byte, eller 82 procent. Detta förutsatt att vi använder åtta bitar för att representera ett tecken.

Redigera?

Artikeln skriven 2009-01-17 av Learning4sharing

Inga kategorier för denna artikel än...

Vi behhöver hjälp att kategorisera våra artiklar. Kan du skriva ett nyckelord för denna artikel? Du kan skriva upp till 3 olika nyckelord för denna artikel, vi uppskattar din hjälp!

Skriv nyckelord som du tycker beskriver denna artikel på ett bra sätt. Du kan ange 3 olika nyckelord för denna artikel, max 20 tecken per nyckelord.

  1. Lägg till fler
    Skriv in svaret på frågan: 8+7

Intresserad av fler artiklar?

Tre amigos
Ivar Jacobson
Rational Quantify
Stendhals syndrom
Ullervad
Hällevadsholm
Gördelmaskar
Iglar
Arhynchobdellida

Senaste sökningarna

dogmafilm har fått 1638 sökningar. Den senaste gjordes 2024-03-29 08:21:20.

synthare har fått 1468 sökningar. Den senaste gjordes 2024-03-29 08:14:43.

geografi har fått 1475 sökningar. Den senaste gjordes 2024-03-29 08:13:16.

ekonomi har fått 1441 sökningar. Den senaste gjordes 2024-03-29 08:05:50.

brun hattmurkla har fått 1343 sökningar. Den senaste gjordes 2024-03-29 07:59:15.

Remiss har fått 1559 sökningar. Den senaste gjordes 2024-03-29 07:55:41.

avlat har fått 1413 sökningar. Den senaste gjordes 2024-03-29 07:54:05.

Lysekil har fått 1077 sökningar. Den senaste gjordes 2024-03-29 07:53:40.

tunnelbana har fått 1547 sökningar. Den senaste gjordes 2024-03-29 07:53:08.

merit har fått 1304 sökningar. Den senaste gjordes 2024-03-29 07:50:35.

helium har fått 1754 sökningar. Den senaste gjordes 2024-03-29 07:44:38.

Nina Allergren har fått 1393 sökningar. Den senaste gjordes 2024-03-29 07:36:27.

Designed by: template world
Learning4sharing.nu
All Rights Reserved. 0.08 SEK

Logga in

Välkommen att redigera och skriva nya artiklar!

Ingent Konto?

Skaffa konto för att redigera och skapa nya ariklar Nytt Konto.

Ny Användare

Välkommen att redigera och skriva nya artiklar! Skapa konto nedan.


Ett verifieringsmail kommer att skickas till din E-post som du måste öppna och verifiera din E-post med

Lägg till artikel

Du är inte inloggad.

Logga In eller Skapa konto.