Хичээл эхлэхээс өмнө өөр нэг хэрэгтэй материалын орчуулгыг танд зориулан бэлтгэв.
Хаффман кодчилол нь файл шахах үндсэн санааг илэрхийлдэг өгөгдөл шахах алгоритм юм. Энэ нийтлэлд бид тогтмол болон хувьсах урттай кодчилол, өвөрмөц декодчилох кодууд, угтвар дүрмүүд, Хаффман модыг бүтээх талаар ярих болно.
Тэмдэгт бүр нь 0 ба 1-ийн дараалал хэлбэрээр хадгалагдаж, 8 бит эзэлдэг гэдгийг бид мэднэ. Тэмдэгт бүр хадгалахдаа ижил тогтмол тооны бит ашигладаг тул үүнийг тогтмол урттай кодчилол гэж нэрлэдэг.
Бидэнд текст өгсөн гэж бодъё. Нэг тэмдэгт хадгалахад шаардагдах зайг хэрхэн багасгах вэ?
Гол санаа нь хувьсах урттай кодчилол юм. Текст дэх зарим тэмдэгтүүд бусдаас илүү олон удаа гардаг гэдгийг бид ашиглаж болно () ижил тэмдэгтүүдийн дарааллыг цөөн битээр илэрхийлэх алгоритм боловсруулах. Хувьсах урттай кодчилолд бид тэмдэгтүүд өгөгдсөн текстэд хэр олон удаа гарч байгаагаас хамааран хувьсах тооны бит оноодог. Эцсийн эцэст, зарим тэмдэгтүүд 1 бит хүртэл бага, бусад нь 2, 3 ба түүнээс дээш бит авч болно. Хувьсах урттай кодчилолтой холбоотой асуудал нь зөвхөн дарааллын дараагийн кодыг тайлах явдал юм.
Битийн дарааллыг мэдэхийн тулд үүнийг хоёрдмол утгагүйгээр яаж тайлах вэ?
Шугамыг анхаарч үзээрэй "абакдаб". Энэ нь 8 тэмдэгттэй бөгөөд тогтмол уртыг кодлох үед үүнийг хадгалахад 64 бит шаардлагатай болно. Тэмдгийн давтамж гэдгийг анхаарна уу "а", "б", "в" и "D" 4, 2, 1, 1-тэй тэнцүү байна. Төсөөлж үзье "абакдаб" гэдгийг ашиглан цөөн бит "to" -аас илүү олон удаа тохиолддог "Б"болон "Б" -аас илүү олон удаа тохиолддог "в" и "D". Кодлохоос эхэлцгээе "to" нэг бит нь 0-тэй тэнцүү, "Б" бид хоёр битийн код 11 оноож, 100 ба 011 гэсэн гурван битийг ашиглан бид кодчилно. "в" и "D".
Үүний үр дүнд бид дараахь зүйлийг авах болно.
a
0
b
11
c
100
d
011
Тиймээс шугам "абакдаб" гэж кодлох болно 00110100011011 (0|0|11|0|100|011|0|11)дээрх кодуудыг ашиглан. Гэсэн хэдий ч гол асуудал нь декодчилоход байх болно. Бид мөрийг тайлах гэж оролдох үед 00110100011011, бид хоёрдмол утгатай үр дүнг авдаг, учир нь үүнийг дараах байдлаар илэрхийлж болно.
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
...
гэх мэт.
Энэ хоёрдмол байдлаас зайлсхийхийн тулд бид кодчилол нь ийм ойлголтыг хангаж байгаа эсэхийг баталгаажуулах ёстой угтвар дүрэм, энэ нь эргээд кодуудыг зөвхөн нэг өвөрмөц аргаар тайлж болно гэсэн үг юм. Угтвар дүрм нь ямар ч код өөр код биш гэдгийг баталгаажуулдаг. Кодоор бид тодорхой тэмдэгтийг төлөөлөх битүүдийг хэлнэ. Дээрх жишээнд 0 угтвар юм 011, энэ нь угтварын дүрмийг зөрчсөн. Тиймээс, хэрэв бидний кодууд угтвар дүрмийг хангаж байвал бид өвөрмөц байдлаар тайлж чадна (мөн эсрэгээр).
Дээрх жишээг дахин авч үзье. Энэ удаад бид тэмдэгтүүдийг хуваарилах болно "а", "б", "в" и "D" угтвар дүрмийг хангасан кодууд.
a
0
b
10
c
110
d
111
Энэ кодчилолоор мөр "абакдаб" гэж кодлох болно 00100100011010 (0|0|10|0|100|011|0|10). Энд байна 00100100011010 Бид аль хэдийн хоёрдмол утгагүйгээр тайлж, анхны мөр рүүгээ буцах боломжтой болно "абакдаб".
Хаффман кодчилол
Бид хувьсах уртын кодчилол болон угтвар дүрмийн талаар ярилцсан бол одоо Huffman кодчиллын талаар ярилцъя.
Энэ арга нь хоёртын модыг бий болгоход суурилдаг. Үүний дотор зангилаа нь эцсийн эсвэл дотоод байж болно. Эхэндээ бүх зангилаанууд нь тэмдэг нь өөрөө болон түүний жинг (өөрөөр хэлбэл үүсэх давтамж) илэрхийлдэг навч (терминал) гэж үздэг. Дотоод зангилаа нь тэмдэгтийн жинг агуулдаг бөгөөд хоёр удам зангилааг илэрхийлдэг. Ерөнхий тохиролцоогоор, бит «0» зүүн мөчрийг дагаж, мөн «1» - баруун талд. бүрэн модонд N навч ба N-1 дотоод зангилаа. Хаффман модыг бүтээхдээ оновчтой уртын кодыг олж авахын тулд ашиглагдаагүй тэмдэглэгээг хаяхыг зөвлөж байна.
Бид хамгийн бага давтамжтай зангилаанд хамгийн чухал ач холбогдол өгөх Хаффман модыг бүтээхийн тулд тэргүүлэх дарааллыг ашиглах болно. Барилгын үе шатуудыг доор тайлбарлав.
- Тэмдэгт бүрт навчны зангилаа үүсгэж, тэдгээрийг тэргүүлэх дараалалд нэмнэ үү.
- Дараалалд нэгээс олон хуудас байгаа бол дараах зүйлийг хийнэ үү.
- Хамгийн өндөр ач холбогдолтой (хамгийн бага давтамжтай) хоёр зангилааг дараалалаас хасах;
- Эдгээр хоёр зангилаа нь хүүхэд байх шинэ дотоод зангилаа үүсгэх ба үүсэх давтамж нь эдгээр хоёр зангилааны давтамжийн нийлбэртэй тэнцүү байх болно.
- Тэргүүлэх дараалалд шинэ зангилаа нэмнэ үү.
- Үлдсэн цорын ганц зангилаа нь үндэс байх бөгөөд энэ нь модыг барьж дуусгах болно.
Бидэнд зөвхөн тэмдэгтүүдээс бүрдсэн текст байна гэж төсөөлөөд үз дээ "a B C D" и "ба", тэдгээрийн илрэлийн давтамж нь тус тус 15, 7, 6, 6, 5 байна. Алгоритмын алхамуудыг тусгасан зургуудыг доор харуулав.
Үндэс цэгээс дурын төгсгөлийн зангилаа хүртэлх зам нь тухайн төгсгөлийн зангилаатай холбоотой тэмдэгтэд тохирох хамгийн оновчтой угтвар кодыг (мөн Хаффманы код гэж нэрлэдэг) хадгална.
Хаффман мод
C++ болон Java хэл дээрх Хаффманы шахалтын алгоритмын хэрэгжилтийг доороос үзнэ үү.
#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);
}
}Тайлбар: Оролтын мөрөнд ашигладаг санах ой нь 47 * 8 = 376 бит, кодлогдсон мөр нь зөвхөн 194 бит, өөрөөр хэлбэл. өгөгдөл ойролцоогоор 48% шахагдсан байна. Дээрх C++ программ дээр бид програмыг унших боломжтой болгохын тулд кодлогдсон мөрийг хадгалахын тулд string классыг ашигладаг.
Учир нь үр ашигтай тэргүүлэх дарааллын өгөгдлийн бүтэц нь оруулах бүрийг шаарддаг O(лог(N)) цаг хугацаа, гэхдээ бүрэн хоёртын модонд N навчнууд байдаг 2N-1 зангилаа, Хаффманы мод нь бүрэн хоёртын мод байвал алгоритм ажиллаж эхэлнэ O(Nlog(N)) цаг, хаана N - Тэмдэгтүүд.
Эх сурвалж:
Эх сурвалж: www.habr.com