Az adatok a Huffman kódolási technikával tömöríthetők, hogy kisebbek legyenek anélkül, hogy az információjuk elveszne. David Huffman után ki hozta létre az elején? A gyakran ismétlődő karaktereket tartalmazó adatok tömörítése általában Huffman kódolással történik.
hogyan kell java-ban frissíteni
Egy jól ismert Greedy algoritmus a Huffman Coding. A karakterhez rendelt kód mérete a karakter gyakoriságától függ, ezért nevezik mohó algoritmusnak. A rövid hosszúságú változó kód a legmagasabb gyakoriságú karakterhez van hozzárendelve, és fordítva az alacsonyabb frekvenciájú karakterekhez. Változó hosszúságú kódolást alkalmaz, ami azt jelenti, hogy a megadott adatfolyam minden karakteréhez más változó hosszúságú kódot ad.
Előtag szabály
Lényegében ez a szabály kimondja, hogy egy karakterhez hozzárendelt kód nem lehet másik kód előtagja. Ha ezt a szabályt megszegik, akkor a létrehozott Huffman-fa dekódolása során különböző kétértelműségek jelenhetnek meg.
Nézzük meg ennek a szabálynak az illusztrációját, hogy jobban megértsük: Minden karakterhez tartozik egy kód, például:
a - 0 b - 1 c - 01
Feltételezve, hogy az előállított bitfolyam 001, a kód a következőképpen fejezhető ki dekódoláskor:
0 0 1 = aab 0 01 = ac
Mi a Huffman kódolási folyamat?
A Huffman-kódot minden egyes karakterhez alapvetően két lépésben kapjuk meg:
Futtatási hiba
- Először hozzon létre egy Huffman-fát a megadott adatfolyam egyedi karaktereinek felhasználásával.
- Másodszor, végig kell haladnunk a felépített Huffman-fán, kódokat kell rendelnünk a karakterekhez, majd ezekkel a kódokkal dekódolni kell a megadott szöveget.
A Huffman-kódolás lépései
A Huffman-fa felépítéséhez használt lépések a megadott karakterek használatával
Input: string str = 'abbcdbccdaabbeeebeab'
Ha ebben az esetben Huffman kódolást alkalmaznak az adattömörítéshez, akkor a következő információkat kell meghatározni a dekódoláshoz:
- Minden karakterhez a Huffman-kód
- Huffman-kódolt üzenethossz (bitekben), átlagos kódhossz
- Az alábbi képletek felhasználásával az utolsó kettőt fedezzük fel.
Hogyan lehet Huffman-fát építeni bemeneti karakterekből?
Először meg kell határozni a megadott karakterlánc egyes karaktereinek gyakoriságát.
| karakter | Frekvencia |
|---|---|
| a | 4 |
| b | 7 |
| c | 3 |
| d | 2 |
| Ez | 4 |
- Rendezd a karaktereket gyakoriság szerint, növekvő sorrendben. Ezeket a Q/min-halom prioritási sorban tartják.
- Az adatfolyamban minden egyes karakterhez és annak gyakoriságához hozzon létre egy levél csomópontot.
- Távolítsa el a két legalacsonyabb frekvenciájú csomópontot a csomópontokból, és ezeknek a frekvenciáknak az összegével létrejön a fa új gyökere.
- Tegye az első kivont csomópontot bal gyermekévé, a második kibontott csomópontot pedig jobb gyermekévé, miközben kivonja a legalacsonyabb frekvenciájú csomópontokat a min-halomból.
- Adja hozzá ezt a csomópontot a min-halomhoz.
- Mivel a gyökér bal oldalán mindig szerepelnie kell a minimális frekvenciának.
- Ismételje a 3. és 4. lépést, amíg csak egy csomópont marad a kupacban, vagy az összes karaktert csomópontok jelzik a fában. A fa akkor fejeződik be, amikor csak a gyökércsomópont marad.
Példák a Huffman kódolásra
Használjunk egy illusztrációt az algoritmus magyarázatához:
Algoritmus a Huffman kódoláshoz
1. lépés: Hozzon létre egy minimális kupacot, amelyben minden csomópont egy fa gyökerét képviseli egyetlen csomóponttal, és 5-öt tartalmaz (a megadott adatfolyam egyedi karaktereinek száma).
2. lépés: A második lépésben szerezzen be két minimális frekvenciájú csomópontot a minimális kupacból. Adjunk hozzá egy harmadik belső csomópontot, frekvencia 2 + 3 = 5, amely a két kivont csomópont összekapcsolásával jön létre.
- Most 4 csomópont van a min-halomban, amelyek közül 3 egy-egy elemű fák gyökere, 1 pedig egy két elemű fa gyökere.
3. lépés: A harmadik lépésben hasonló módon vegye ki a két minimális frekvenciájú csomópontot a kupacból. Ezenkívül adjon hozzá egy új belső csomópontot, amely a két kivont csomópont összekapcsolásával jön létre; frekvenciája a fában 4 + 4 = 8 legyen.
- Most, hogy a minimális kupacnak három csomópontja van, az egyik csomópont az egyetlen elemű fák gyökereként, két kupaccsomópont pedig a több csomóponttal rendelkező fák gyökereként szolgál.
4. lépés: Szerezze meg a két minimális frekvenciájú csomópontot a negyedik lépésben. Ezenkívül adjon hozzá egy új belső csomópontot, amely a két kivont csomópont összekapcsolásával jön létre; frekvenciája a fában 5 + 7 = 12 legyen.
- A Huffman-fa létrehozásakor ügyelnünk kell arra, hogy a minimális érték mindig a bal oldalon, a második érték pedig mindig a jobb oldalon legyen. Jelenleg az alábbi képen látható a kialakult fa:
5. lépés: Szerezze be a következő két minimális frekvenciájú csomópontot az 5. lépésben. Ezenkívül adjon hozzá egy új belső csomópontot, amely a két kibontott csomópont összekapcsolásával jön létre; frekvenciája a fában 12 + 8 = 20 legyen.
Addig folytassa, amíg az összes megkülönböztető karaktert hozzáadta a fához. A megadott karaktersorhoz létrehozott Huffman-fa a fenti képen látható.
java gyűjtemények java
Most minden nem levél csomóponthoz rendeljen 0-t a bal szélhez és 1-et a jobb szélhez, hogy létrehozza az egyes betűk kódját.
vlc videók letöltése a youtube-ról
Az élsúly meghatározásához követendő szabályok:
- A jobb oldali éleknek 1-et kell adnunk, ha a bal élek súlyát 0-val adjuk meg.
- Ha a bal élek 1-es súlyt kapnak, a jobb oldali éleket 0-val kell súlyozni.
- A fent említett két konvenció bármelyike használható.
- Kövesse azonban ugyanezt a protokollt a fa dekódolásakor is.
A súlyozást követően a módosított fa a következőképpen jelenik meg:
A kódex megértése
- Végig kell mennünk a Huffman-fán, amíg el nem érjük a levél csomópontot, ahol az elem jelen van, hogy a kapott Huffman-fából az egyes karakterekhez tartozó Huffman-kódot dekódolhassuk.
- A csomópontokon átívelő súlyokat a bejárás során rögzíteni kell, és hozzá kell rendelni az adott levélcsomóponton található elemekhez.
- A következő példa segít jobban illusztrálni, mire gondolunk:
- Ahhoz, hogy a fenti képen szereplő karakterekhez megkapjuk a kódot, végig kell járnunk az egész fát (amíg az összes levélcsomópontot be nem fedik).
- Ennek eredményeként a létrehozott fát használják az egyes csomópontok kódjainak dekódolására. Az alábbiakban az egyes karakterekhez tartozó kódok listája található:
| karakter | Gyakoriság/szám | Kód |
|---|---|---|
| a | 4 | 01 |
| b | 7 | tizenegy |
| c | 3 | 101 |
| d | 2 | 100 |
| Ez | 4 | 00 |
Az alábbiakban bemutatjuk a megvalósítást a C programozásban:
// C program for Huffman Coding #include #include // This constant can be avoided by explicitly // calculating height of Huffman Tree #define MAX_TREE_HT 100 // A Huffman tree node struct MinHeapNode { // One of the input characters char data; // Frequency of the character unsigned freq; // Left and right child of this node struct MinHeapNode *left, *right; }; // A Min Heap: Collection of // min-heap (or Huffman tree) nodes struct MinHeap { // Current size of min heap unsigned size; // capacity of min heap unsigned capacity; // Array of minheap node pointers struct MinHeapNode** array; }; // A utility function allocate a new // min heap node with given character // and frequency of the character struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc( sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } // A utility function to create // a min heap of given capacity struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // current size is 0 minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } // A utility function to // swap two min heap nodes void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } // The standard minHeapify function. void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // A utility function to insert // a new node to Min Heap void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // A utility function to print an array of size n void printArr(int arr[], int n) { int i; for (i = 0; i left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: Create a new internal // node with frequency equal to the // sum of the two nodes frequencies. // Make the two extracted node as // left and right children of this new node. // Add this node to the min heap // '$' is a special value for internal nodes, not // used top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } Kimenet
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
A fenti kód Java implementációja:
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Huffman { // recursive function to print the // huffman-code through the tree traversal. // Here s is the huffman - code generated. public static void printCode(HuffmanNode root, String s) { // base case; if the left and right are null // then its a leaf node and we print // the code s generated by traversing the tree. if (root.left == null && root.right == null && Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + ':' + s); return; } // if we go to left then add '0' to the code. // if we go to the right add'1' to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + '0'); printCode(root.right, s + '1'); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue q = new PriorityQueue( n, new MyComparator()); for (int i = 0; i <n; i++) { creating a huffman node object and add it to the priority queue. huffmannode hn="new" huffmannode(); hn.c="charArray[i];" hn.data="charfreq[i];" hn.left="null;" hn.right="null;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = '-'; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, ''); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;> Kimenet
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Magyarázat:
Átjárással létrejön és dekódolja a Huffman-fát. A bejárás során összegyűjtött értékeket ezután a levél csomópontjában található karakterre kell alkalmazni. A szolgáltatott adatfolyam minden egyedi karaktere azonosítható a Huffman-kóddal ilyen módon. O (nlogn), ahol n a karakterek teljes száma, az idő bonyolultsága. Az ExtractMin() 2*(n - 1) alkalommal kerül meghívásra, ha n csomópont van. Mivel az extractMin() meghívja a minHeapify()-t, a végrehajtási ideje O (logn). A teljes komplexitás tehát O (nlogn). Van egy lineáris idő algoritmus, ha a bemeneti tömb rendezve van. Erről a következő cikkünkben lesz szó részletesebben.
Problémák a Huffman kódolással
Beszéljünk a Huffman kódolás hátrányairól ebben a részben, és arról, hogy miért nem mindig a legjobb megoldás:
- Ha nem minden karakter valószínűsége vagy gyakorisága 2 negatív hatványa, akkor ez nem tekinthető ideálisnak.
- Bár a szimbólumok csoportosításával és az ábécé bővítésével közelebb kerülhetünk az ideálishoz, a blokkoló módszer nagyobb ábécé kezelését teszi szükségessé. Ezért a Huffman-kódolás nem mindig túl hatékony.
- Bár számos hatékony módszer létezik az egyes szimbólumok vagy karakterek gyakoriságának megszámlálására, a teljes fa rekonstrukciója mindegyikhez nagyon időigényes lehet. Ha az ábécé nagy, és a valószínűségi eloszlások gyorsan változnak minden szimbólummal, akkor ez általában a helyzet.
Mohó Huffman kód építési algoritmus
- Huffman kifejlesztett egy mohó technikát, amely egy Huffman-kódot, ideális előtagkódot generál a bemeneti adatfolyam minden egyes karakteréhez.
- A megközelítés minden alkalommal a legkevesebb csomópontot használja a Huffman-fa alulról felfelé történő létrehozásához.
- Mivel minden karakter aszerint kap egy hosszú kódot, hogy milyen gyakran jelenik meg az adott adatfolyamban, ezt a módszert mohó megközelítésnek nevezik. Az adatokban gyakran előforduló elem, ha a lekért kód mérete kisebb.
A Huffman kódolás használata
- Itt a Huffman kódolás néhány gyakorlati felhasználásáról fogunk beszélni:
- A hagyományos tömörítési formátumok, mint a PKZIP, GZIP stb., általában Huffman kódolást alkalmaznak.
- A Huffman-kódolást faxon és szöveges úton történő adatátvitelre használják, mivel minimalizálja a fájlméretet és növeli az átviteli sebességet.
- A Huffman-kódolást (különösen az előtagkódokat) számos multimédiás tárolási formátum, köztük a JPEG, PNG és MP3 használja a fájlok tömörítésére.
- A Huffman kódolást leginkább képtömörítésre használják.
- Ha gyakran ismétlődő karakterláncot kell elküldeni, az hasznosabb lehet.
Következtetés
- A Huffman Coding általában hasznos a gyakran előforduló karaktereket tartalmazó adatok tömörítéséhez.
- Láthatjuk, hogy a leggyakrabban előforduló karakternek van a legrövidebb kódja, míg a leggyakrabban előforduló karakternek a legnagyobb kódja.
- A Huffman Code tömörítési technikát változó hosszúságú kódolás létrehozására használják, amely változó mennyiségű bitet használ minden betűhöz vagy szimbólumhoz. Ez a módszer jobb, mint a rögzített hosszúságú kódolás, mivel kevesebb memóriát használ, és gyorsabban továbbítja az adatokat.
- Olvassa el ezt a cikket, hogy jobban megismerje a mohó algoritmust.