Veriler, hiçbir bilgisini kaybetmeden küçültmek için Huffman Kodlama tekniği kullanılarak sıkıştırılabilir. David Huffman'dan sonra onu başlangıçta kim yarattı? Sık sık tekrarlanan karakterleri içeren veriler genellikle Huffman kodlaması kullanılarak sıkıştırılır.
İyi bilinen bir Açgözlü algoritma Huffman Kodlamasıdır. Bir karaktere tahsis edilen kodun boyutu, karakterin frekansına bağlıdır, bu nedenle açgözlü algoritma olarak anılır. Kısa uzunluklu değişken kodu, en yüksek frekansa sahip karaktere atanır ve bunun tersi, daha düşük frekansa sahip karakterler için de geçerlidir. Değişken uzunluklu bir kodlama kullanır; bu, sağlanan veri akışındaki her karaktere farklı bir değişken uzunluklu kod verdiği anlamına gelir.
Önek Kuralı
Bu kural esas olarak bir karaktere tahsis edilen kodun başka bir kodun öneki olamayacağını belirtmektedir. Bu kuralın ihlali durumunda oluşturulan Huffman ağacının kodu çözülürken çeşitli belirsizlikler ortaya çıkabilir.
Daha iyi anlamak için bu kuralın bir örneğine bakalım: Her karakter için aşağıdaki gibi bir kod sağlanır:
a - 0 b - 1 c - 01
Üretilen bit akışının 001 olduğunu varsayarak kodun kodu çözüldüğünde aşağıdaki gibi ifade edilebilir:
0 0 1 = aab 0 01 = ac
Huffman Kodlama süreci nedir?
Huffman Kodu her farklı karakter için öncelikle iki adımda elde edilir:
- Öncelikle yalnızca sağlanan veri akışındaki benzersiz karakterleri kullanarak bir Huffman Ağacı oluşturun.
- İkinci olarak, oluşturulmuş Huffman Ağacı boyunca ilerlemeli, karakterlere kodlar atamalı ve daha sonra bu kodları sağlanan metnin kodunu çözmek için kullanmalıyız.
Huffman Kodlamada Atılacak Adımlar
java'da örnek
Verilen karakterleri kullanarak Huffman ağacını oluşturmak için kullanılan adımlar
Input: string str = 'abbcdbccdaabbeeebeab'
Bu durumda veri sıkıştırma için Huffman Kodlaması kullanılıyorsa, kod çözme için aşağıdaki bilgilerin belirlenmesi gerekir:
ağ oluşturma ve türleri
- Her karakter için Huffman Kodu
- Huffman kodlu mesaj uzunluğu (bit olarak), ortalama kod uzunluğu
- Aşağıda anlatılan formüller kullanılarak son ikisi keşfedilir.
Girdi Karakterlerinden Bir Huffman Ağacı Nasıl Oluşturulabilir?
Sağlanan dizedeki her karakterin sıklığı öncelikle belirlenmelidir.
| Karakter | Sıklık |
|---|---|
| A | 4 |
| B | 7 |
| C | 3 |
| D | 2 |
| Bu | 4 |
- Karakterleri artan sıklığa göre sıralayın. Bunlar Q/min-yığın öncelik kuyruğunda tutulur.
- Veri akışındaki her farklı karakter ve sıklığı için bir yaprak düğüm oluşturun.
- Düğümlerden en düşük iki frekansa sahip iki düğüm çıkarılır ve bu frekansların toplamı kullanılarak ağacın yeni kökü oluşturulur.
- Minimum yığından en düşük frekansa sahip düğümleri çıkarırken, çıkarılan ilk düğümü sol çocuğu ve ikinci çıkarılan düğümü sağ çocuğu yapın.
- Min-heap'e bu düğümü ekleyin.
- Kökün sol tarafı her zaman minimum frekansı içermesi gerektiğinden.
- Yığında yalnızca bir düğüm kalana veya tüm karakterler ağaçtaki düğümler tarafından temsil edilene kadar 3. ve 4. adımları tekrarlayın. Yalnızca kök düğüm kaldığında ağaç biter.
Huffman Kodlama Örnekleri
Algoritmayı açıklamak için bir örnek kullanalım:
Huffman Kodlama Algoritması
Aşama 1: Her düğümün, tek düğümlü bir ağacın kökünü temsil ettiği ve 5 (sağlanan veri akışındaki benzersiz karakter sayısı) değerini tuttuğu bir minimum yığın oluşturun.
Adım 2: İkinci adımda minimum yığından iki minimum frekans düğümü edinin. Çıkarılan iki düğümün birleştirilmesiyle oluşturulan, frekans 2 + 3 = 5 olan üçüncü bir dahili düğüm ekleyin.
- Şimdi min-heap'te 4 düğüm var, bunlardan 3'ü her biri tek elemanlı ağaçların kökleri ve 1'i iki elemanlı bir ağacın kökü.
Aşama 3: Üçüncü adımda benzer şekilde yığından iki minimum frekans düğümünü alın. Ek olarak, çıkarılan iki düğümün birleştirilmesiyle oluşturulan yeni bir iç düğüm ekleyin; ağaçtaki sıklığı 4 + 4 = 8 olmalıdır.
- Artık minimum yığının üç düğümü olduğuna göre, bir düğüm tek öğeli ağaçların kökü olarak hizmet eder ve iki yığın düğümü birden fazla düğüme sahip ağaçların kökü olarak hizmet eder.
Adım 4: Dördüncü adımda iki minimum frekans düğümünü alın. Ek olarak, çıkarılan iki düğümün birleştirilmesiyle oluşturulan yeni bir iç düğüm ekleyin; ağaçtaki sıklığı 5 + 7 = 12 olmalıdır.
- Huffman ağacı oluştururken minimum değerin daima sol tarafta, ikinci değerin ise daima sağ tarafta olmasına dikkat etmeliyiz. Şu anda aşağıdaki resimde oluşan ağaç gösterilmektedir:
Adım 5: 5. adımda aşağıdaki iki minimum frekans düğümünü elde edin. Ayrıca, çıkarılan iki düğümün birleştirilmesiyle oluşturulan yeni bir dahili düğüm ekleyin; ağaçtaki sıklığı 12 + 8 = 20 olmalıdır.
Tüm farklı karakterler ağaca eklenene kadar devam edin. Belirtilen karakter kadrosu için oluşturulan Huffman ağacı yukarıdaki resimde gösterilmektedir.
Şimdi, yaprak olmayan her düğüm için, her harfin kodunu oluşturmak üzere sol kenara 0 ve sağ kenara 1 atayın.
Kenar ağırlıklarının belirlenmesinde uyulması gereken kurallar:
- Sol kenarlara ağırlık 0 verirseniz sağ kenarlara ağırlık 1 vermeliyiz.
- Sol kenarlara ağırlık 1 verilirse sağ kenarlara ağırlık 0 verilmelidir.
- Yukarıda belirtilen iki sözleşmeden herhangi biri kullanılabilir.
- Ancak ağacın kodunu çözerken de aynı protokolü izleyin.
Ağırlıklandırmanın ardından değiştirilen ağaç aşağıdaki gibi görüntülenir:
Kodu Anlamak
- Ortaya çıkan Huffman ağacından her karakter için Huffman kodunu çözmek amacıyla, elemanın bulunduğu yaprak düğümüne ulaşana kadar Huffman ağacından geçmeliyiz.
- Düğümler arasındaki ağırlıklar geçiş sırasında kaydedilmeli ve belirli yaprak düğümde bulunan öğelere tahsis edilmelidir.
- Aşağıdaki örnek ne demek istediğimizi daha iyi anlamanıza yardımcı olacaktır:
- Yukarıdaki resimdeki her karakterin kodunu elde etmek için ağacın tamamında yürümemiz gerekir (tüm yaprak düğümleri kaplanana kadar).
- Sonuç olarak oluşturulan ağaç, her düğümün kodlarını çözmek için kullanılır. Aşağıda her karaktere ait kodların bir listesi bulunmaktadır:
| Karakter | Frekans/sayım | Kod |
|---|---|---|
| A | 4 | 01 |
| B | 7 | on bir |
| C | 3 | 101 |
| D | 2 | 100 |
| Bu | 4 | 00 |
Aşağıda C programlamada uygulama verilmiştir:
// 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; } Çıktı
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Yukarıdaki kodun Java Uygulaması:
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;> Çıktı
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Açıklama:
Geçiş yaparak Huffman Ağacı oluşturulur ve kodu çözülür. Geçiş sırasında toplanan değerler daha sonra yaprak düğümde bulunan karaktere uygulanacaktır. Sağlanan veri akışındaki her benzersiz karakter, Huffman Kodu kullanılarak bu şekilde tanımlanabilir. O (nlogn), burada n toplam karakter sayısıdır ve zaman karmaşıklığını gösterir. Eğer n düğüm varsa ExtractMin() 2*(n - 1) kez çağrılır. extractMin(), minHeapify()'ı çağırdığından yürütme süresi O'dur (logn). Bu nedenle toplam karmaşıklık O (nlogn)'dur. Giriş dizisi sıralanırsa doğrusal bir zaman algoritması vardır. Bu konuyu gelecek yazımızda daha ayrıntılı olarak ele alacağız.
Huffman Kodlamayla İlgili Sorunlar
Bu bölümde Huffman kodlamanın dezavantajlarından ve neden her zaman en iyi seçenek olmadığından bahsedelim:
Java'da dize yöntemleri
- Karakterlerin tüm olasılıkları veya frekansları 2'nin negatif kuvvetleri değilse ideal olarak kabul edilmez.
- Sembolleri gruplandırarak ve alfabeyi genişleterek ideale yaklaşılabilse de engelleme yöntemi daha büyük bir alfabenin kullanılmasını gerektirir. Bu nedenle Huffman kodlaması her zaman çok etkili olmayabilir.
- Her sembolün veya karakterin sıklığını saymanın birçok etkili yolu olmasına rağmen, her biri için ağacın tamamını yeniden oluşturmak çok zaman alabilir. Alfabe büyük olduğunda ve olasılık dağılımları her sembolle hızlı bir şekilde değiştiğinde, durum genellikle budur.
Açgözlü Huffman Kod Yapım Algoritması
- Huffman, giriş veri akışındaki her farklı karakter için ideal bir önek kodu olan Huffman Kodu'nu üreten açgözlü bir teknik geliştirdi.
- Yaklaşım, aşağıdan yukarıya doğru Huffman ağacını oluşturmak için her seferinde en az sayıda düğümü kullanır.
- Her karakter, verilen veri akışında ne sıklıkta göründüğüne bağlı olarak bir kod uzunluğu aldığından, bu yöntem açgözlü bir yaklaşım olarak bilinir. Alınan kodun boyutunun daha az olması verilerde yaygın olarak oluşan bir öğedir.
Huffman Kodlamasının Kullanımı
- Burada Huffman Kodlamanın bazı pratik kullanımlarından bahsedeceğiz:
- PKZIP, GZIP vb. gibi geleneksel sıkıştırma formatları genellikle Huffman kodlamasını kullanır.
- Huffman Kodlaması, dosya boyutunu en aza indirdiği ve iletim hızını arttırdığı için faks ve metin yoluyla veri aktarımında kullanılır.
- Huffman kodlaması (özellikle önek kodları), dosyaları sıkıştırmak için JPEG, PNG ve MP3 dahil olmak üzere çeşitli multimedya depolama formatları tarafından kullanılır.
- Huffman Kodlaması çoğunlukla görüntü sıkıştırma için kullanılır.
- Sık sık yinelenen karakterlerden oluşan bir dizenin gönderilmesi gerektiğinde, bu daha yararlı olabilir.
Çözüm
- Genel olarak Huffman Kodlaması, sık karşılaşılan karakterleri içeren verileri sıkıştırmak için faydalıdır.
- En sık geçen karakterin en kısa koda sahip olduğunu, en az görülen karakterin ise en büyük koda sahip olduğunu görebiliriz.
- Huffman Kodu sıkıştırma tekniği, her harf veya sembol için çeşitli miktarda bit kullanan değişken uzunluklu kodlama oluşturmak için kullanılır. Bu yöntem, daha az bellek kullanması ve verileri daha hızlı iletmesi nedeniyle sabit uzunluklu kodlamaya göre daha üstündür.
- Açgözlü algoritma hakkında daha iyi bilgi sahibi olmak için bu makaleyi inceleyin.