Kurs başlamadan önce sizin için başka bir yararlı materyalin çevirisini hazırladı.
Huffman kodlaması, dosya sıkıştırmanın temel fikrini formüle eden bir veri sıkıştırma algoritmasıdır. Bu yazımızda sabit ve değişken uzunluklu kodlama, benzersiz olarak çözülebilen kodlar, önek kuralları ve Huffman ağacı oluşturma hakkında konuşacağız.
Her karakterin 0'lar ve 1'ler dizisi olarak saklandığını ve 8 bit kapladığını biliyoruz. Buna sabit uzunlukta kodlama denir, çünkü her karakter depolamak için aynı sabit sayıda bit kullanır.
Diyelim ki bize metin verildi. Tek bir karakteri saklamak için gereken alan miktarını nasıl azaltabiliriz?
Ana fikir, değişken uzunluklu kodlamadır. Metindeki bazı karakterlerin diğerlerinden daha sık geçtiği gerçeğini kullanabiliriz () aynı karakter dizisini daha az bitte temsil edecek bir algoritma geliştirmek. Değişken uzunluklu kodlamada, belirli bir metinde ne sıklıkta göründüklerine bağlı olarak karakterlere değişken sayıda bit atarız. Sonunda, bazı karakterler 1 bit kadar az alabilirken, diğerleri 2 bit, 3 veya daha fazla alabilir. Değişken uzunluklu kodlamayla ilgili sorun, dizinin yalnızca müteakip kodunun çözülmesidir.
Bit sırasını bilerek, onu açık bir şekilde nasıl çözersiniz?
çizgiyi düşün "abadab". 8 karaktere sahiptir ve sabit bir uzunluğu kodlarken, depolamak için 64 bite ihtiyaç duyacaktır. Sembol frekansının "a", "b", "c" и "NS" sırasıyla 4, 2, 1, 1'e eşittir. hayal etmeye çalışalım "abadab" gerçeğini kullanarak daha az bit "to" daha sık meydana gelir "B"Ve "B" daha sık meydana gelir "c" и "NS". Kodlayarak başlayalım "to" 0'a eşit bir bit ile, "B" iki bitlik bir kod 11 atayacağız ve üç bit 100 ve 011 kullanarak kodlayacağız "c" и "NS".
Sonuç olarak, şunları elde edeceğiz:
a
0
b
11
c
100
d
011
Yani çizgi "abadab" olarak kodlayacağız 00110100011011 (0|0|11|0|100|011|0|11)yukarıdaki kodları kullanarak Ancak, asıl sorun kod çözme olacaktır. Dizeyi çözmeye çalıştığımızda 00110100011011, belirsiz bir sonuç alacağız, çünkü şu şekilde temsil edilebilir:
0|011|0|100|011|0|11 adacdab
0|0|11|0|100|0|11|011 aabacabd
0|011|0|100|0|11|0|11 adacabab
...
vb
Bu belirsizliği önlemek için, kodlamamızın aşağıdaki gibi bir kavramı karşılamasını sağlamalıyız: önek kuralıbu da kodların yalnızca tek bir benzersiz şekilde çözülebileceği anlamına gelir. Önek kuralı, hiçbir kodun diğerinin öneki olmamasını sağlar. Kod derken, belirli bir karakteri temsil etmek için kullanılan bitleri kastediyoruz. Yukarıdaki örnekte 0 bir önek 011, önek kuralını ihlal eden. Dolayısıyla, kodlarımız önek kuralını karşılıyorsa, benzersiz bir şekilde kodu çözebiliriz (ve tersi de geçerlidir).
Yukarıdaki örneği tekrar gözden geçirelim. Bu sefer semboller için atayacağız "a", "b", "c" и "NS" önek kuralına uyan kodlar.
a
0
b
10
c
110
d
111
Bu kodlama ile dizi "abadab" olarak kodlanacak 00100100011010 (0|0|10|0|100|011|0|10). Fakat 00100100011010 zaten açık bir şekilde kodu çözebileceğiz ve orijinal dizimize geri dönebileceğiz "abadab".
Huffman kodlaması
Değişken uzunluklu kodlamayı ve önek kuralını hallettiğimize göre, şimdi Huffman kodlamasından bahsedelim.
Yöntem, ikili ağaçların oluşturulmasına dayanmaktadır. İçinde, düğüm son veya dahili olabilir. Başlangıçta, tüm düğümler, sembolün kendisini ve ağırlığını (yani, oluşum sıklığını) temsil eden yapraklar (terminaller) olarak kabul edilir. Dahili düğümler, karakterin ağırlığını içerir ve iki alt düğüme atıfta bulunur. Genel anlaşmaya göre, bit «0» sol dalı takip etmeyi temsil eder ve «1» - Sağdaki. tam ağaçta N yapraklar ve N-1 iç düğümler. Bir Huffman ağacı oluştururken, optimum uzunluk kodlarını elde etmek için kullanılmayan sembollerin atılması önerilir.
En düşük frekansa sahip düğüme en yüksek önceliğin verileceği bir Huffman ağacı oluşturmak için bir öncelik sırası kullanacağız. Yapım adımları aşağıda açıklanmıştır:
- Her karakter için bir yaprak düğüm oluşturun ve bunları öncelik sırasına ekleyin.
- Kuyrukta birden fazla sayfa varken aşağıdakileri yapın:
- Sıradan en yüksek önceliğe (en düşük frekansa) sahip iki düğümü çıkarın;
- Bu iki düğümün çocuk olacağı ve oluşum sıklığının bu iki düğümün frekanslarının toplamına eşit olacağı yeni bir dahili düğüm oluşturun.
- Öncelik kuyruğuna yeni bir düğüm ekleyin.
- Geriye kalan tek düğüm kök olacaktır ve bu ağacın yapımını tamamlayacaktır.
Yalnızca karakterlerden oluşan bir metnimiz olduğunu hayal edin. "a", "b", "c", "d" и "ve"ve oluşum sıklıkları sırasıyla 15, 7, 6, 6 ve 5'tir. Algoritmanın adımlarını yansıtan resimler aşağıdadır.
Kökten herhangi bir son düğüme giden bir yol, o uç düğümle ilişkili karaktere karşılık gelen en uygun önek kodunu (Huffman kodu olarak da bilinir) saklayacaktır.
Huffman ağacı
Aşağıda, C++ ve Java'da Huffman sıkıştırma algoritmasının uygulanmasını bulacaksınız:
#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
// A Tree node
struct Node
{
char ch;
int freq;
Node *left, *right;
};
// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
Node* node = new Node();
node->ch = ch;
node->freq = freq;
node->left = left;
node->right = right;
return node;
}
// Comparison object to be used to order the heap
struct comp
{
bool operator()(Node* l, Node* r)
{
// highest priority item has lowest frequency
return l->freq > r->freq;
}
};
// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
unordered_map<char, string> &huffmanCode)
{
if (root == nullptr)
return;
// found a leaf node
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
if (root == nullptr) {
return;
}
// found a leaf node
if (!root->left && !root->right)
{
cout << root->ch;
return;
}
index++;
if (str[index] =='0')
decode(root->left, index, str);
else
decode(root->right, index, str);
}
// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
// count frequency of appearance of each character
// and store it in a map
unordered_map<char, int> freq;
for (char ch: text) {
freq[ch]++;
}
// Create a priority queue to store live nodes of
// Huffman tree;
priority_queue<Node*, vector<Node*>, comp> pq;
// Create a leaf node for each character and add it
// to the priority queue.
for (auto pair: freq) {
pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
// Create a new internal node with these two nodes
// as children and with frequency equal to the sum
// of the two nodes' frequencies. Add the new node
// to the priority queue.
int sum = left->freq + right->freq;
pq.push(getNode('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node* root = pq.top();
// traverse the Huffman Tree and store Huffman Codes
// in a map. Also prints them
unordered_map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes are :n" << 'n';
for (auto pair: huffmanCode) {
cout << pair.first << " " << pair.second << 'n';
}
cout << "nOriginal string was :n" << text << 'n';
// print encoded string
string str = "";
for (char ch: text) {
str += huffmanCode[ch];
}
cout << "nEncoded string is :n" << str << 'n';
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
cout << "nDecoded string is: n";
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
// Huffman coding algorithm
int main()
{
string text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
return 0;
}import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
// A Tree node
class Node
{
char ch;
int freq;
Node left = null, right = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
};
class Huffman
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
if (root.left == null && root.right == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.left, index, sb);
else
index = decode(root.right, index, sb);
return index;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> freq = new HashMap<>();
for (int i = 0 ; i < text.length(); i++) {
if (!freq.containsKey(text.charAt(i))) {
freq.put(text.charAt(i), 0);
}
freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// do till there is more than one node in the queue
while (pq.size() != 1)
{
// Remove the two nodes of highest priority
// (lowest frequency) from the queue
Node left = pq.poll();
Node right = pq.poll();
// Create a new internal node with these two nodes as children
// and with frequency equal to the sum of the two nodes
// frequencies. Add the new node to the priority queue.
int sum = left.freq + right.freq;
pq.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}Not: giriş dizisi tarafından kullanılan bellek 47 * 8 = 376 bittir ve kodlanmış dizi yalnızca 194 bittir, yani. veriler yaklaşık %48 oranında sıkıştırılmıştır. Yukarıdaki C++ programında, programı okunabilir kılmak için kodlanmış dizgiyi saklamak için string sınıfını kullanıyoruz.
Verimli öncelikli kuyruk veri yapıları ekleme başına gerektirdiğinden O(günlük(N)) zaman, ancak tam bir ikili ağaçta N mevcut yapraklar 2N-1 düğümler ve Huffman ağacı tam bir ikili ağaçtır, o zaman algoritma çalışır Ç(Nlog(N)) zaman, nerede N - Karakterler.
Kaynaklar:
Kaynak: habr.com