مقدمه و معرفی الگوریتم

برای دیدن مسئله‌های بیشتر در زمینه‌ی الگوریتم‌های رمزنگاری به مطالب زیر رجوع کنید:
  -
  -
  - کدگذاری و فشرده‌سازی متون - روش 827

فرض کنید قصد داریم متن I am a C++ programmer from Iran را فشرده کنیم. با استفاده از الگوریتم کدگذاری هافمن، در قدم اول جدول فراوانی حروف در متن مورد نظر را تشکیل می‌دهیم. تعداد تکرار هر یک از حروف متن در جدول زیر آمده است. دقت کنید که برای خوانایی بیشتر، به‌جای حرف فاصله (Space)، علامت ¬ نوشته شده است:

الگوریتم کدگذاری هافمن سعی دارد به‌جای هر یک از حروف از یک کد باینری کوتاه استفاده کند. کوتاه‌ترین کدها (کدهایی با طول کمتر) به حروف پر تکرار اختصاص داده می‌شوند تا حجم متن کدشده‌ی نهایی، در نتیجه‌ی تکرارها به حداقل برسد. برای جلوگیری از ابهام و دوگانگی هنگام تفسیر متن کدگذاری شده، کدها نباید پیش‌وند یکدیگر باشند، مسئله‌ای که یکی از چالش‌های اصلی دیوید هافمن برای طراحی الگوریتمی کارامد به‌شمار می‌رفت و در نهایت با معرفی ساختار درختی برای نگهداری کدها، این ویژگی اساسی را تثبیت کرد.

برای آشنایی با داده‌ساختار درخت دودویی و دریافت جزئیات بیشتر به معرفی درخت دودویی، پیاده‌سازی درخت دودویی با آرایه‌ی خطی و پیاده‌سازی درخت دودویی با حافظه‌ی پویا رجوع کنید.

به بیان دقیق‌تر، هیچ ترکیبی از کدها، نباید کد دیگری از همان مجموعه را تولید کند. در واقع صرف پیش‌وند بودن، فقط عملیات تفسیر متن کدشده را دچار مشکل می‌کند اما این ترکیب کدهاست که ابهام و بن‌بست را به‌وجود می‌آورد. برای درک بهتر موضوع به یک مثال توجه کنید:

فرض کنید برای کد کردن 3 حرف A، B و C به ترتیب از کدهای 0، 1 و 01 استفاده می‌کنیم و می‌خواهیم پیامی را به فرد دیگری بفرستیم. فرستنده و گیرنده‌ی پیام، جدول نگاشت کدها را در اختیار دارند. پیام عبارت‌است‌از CC، و طبق جدول، هریک از حروف C به کد 01 نگاشت شده و پیام رمز حاوی متن 0101 ارسال می‌شود. در سمت گیرنده برای بازیابی متن اصلی ابهام به‌وجود می‌آید چون پیام دریافتی را می‌توان به هریک از متون مجاز زیر ترجمه کرد:

مشکل این سیستم کدگذاری این‌است که ترکیب کدهای 0 و 1 کد 01 را به‌وجود می‌آورد و همان‌طور که در جدول بالا دیدیم، کد 01 بیش از یک تفسیر خواهد داشت. به هر‌حال در حالت کلی اگر ترکیب کد C₁ و C₂ کد C₃ را تولید کند، حداقل به‌این معنی است که کد C₁ پیش‌وند کد C₃ است (و به همین ترتیب کد C₂ پسوند آن است) و اگر ساختاری داشته باشیم که اجازه ندهد کدها به‌صورت پیش‌وند همدیگر تعریف شوند، این ابهام رفع می‌شود.

برخلاف الگوریتم کدگذاری شانون-فانو درخت کدهای هافمن از پایین به بالا، یعنی از برگ‌ها ساخته می‌شود. همه‌ی حروف در برگ‌های درخت هستند و گره‌های میانی (حتی ریشه) هیچ‌یک از حروف را شامل نمی‌شوند. درخت ساخته شده، یک درخت دودویی است و لذا هر گره حداکثر 2 فرزند دارد. برای شهود بهتر، فرزندان را بصورت فرزند چپ و فرزند راست در نظر گرفته و طبق قرارداد، شاخه‌ی مربوط به فرزند چپ را با برچسب 0 و شاخه‌ی مربوط به فرزند سمت راست را با برچسب 1 نشانه‌گذاری می‌کنیم. با شروع از ریشه، دنباله‌ی برچسب‌های مسیر منتهی به هر یک از حروف (برگ‌ها)، کد مربوط به آن حرف است.

ساختار درخت دودویی، ویژگی‌های منحصربه‌فردی را به ارمغان می‌آورد:
  - باتوجه به این‌که مسیر از ریشه به برگ در درخت دودویی یکتاست، لذا هر حرف با یک کد یکتا متناظر است.
  - چون حروف فقط در برگ‌ها ذخیره شده‌اند، لذا در بین مسیر، هیچ حرفی وجود ندارد و هیچ‌یک از کدها در بین مسیر و پیش از رسیدن به برگ کامل نمی‌شود لذا تضمین کننده‌ی این است که کدها نمی‌تواند پیش‌وند یک‌دیگر باشند.

برگردیم به مثال اصلی و به‌عنوان قدم بعدی می‌خواهیم درخت دوددویی کدها را بسازیم. گفتیم که درخت هافمن از پایین به بالا ساخته می‌شود لذا اولین برگ‌های ساخته شده که پایین‌تر از سایرین قرار می‌گیرند، احتمالا دورترین برگ‌ها به ریشه خواهند بود و به‌همین خاطر دارای مسیر طولانی و کدهای بزرگتری هستند. کدهای بزرگتر به حروف کم‌تکرار اختصاص دارند، پس جدول فراوانی حروف را بر اساس تعداد تکرار به صورت صعودی (از کوچک به بزرگ) مرتب کرده و از ابتدای لیست شروع به برداشتن حروف و تشکیل درخت هافمن می‌کنیم. جدول فراوانی مرتب‌شده برای مثال داده‌شده به‌صورت زیر است:

الگوریتم تشکیل درخت دودویی هافمن عبارت است از:
  1- تا زمانی‌که بیش از یک عنصر در جدول فراوانی وجود دارد، مراحل زیر را تکرار کن
    1.1- جدول را به‌صورت صعودی براساس فراوانی مرتب کن
    1.2- دو عنصر ابتدایی n₁ و n₂ را از جدول حذف کن و به‌عنوان فرزندان چپ و راست یک درخت دودویی جدید با ریشه‌ی n قرار بده
    1.3- فراوانی عنصر جدید n برابر است با مجموع فراوانی‌های n₁ و n₂
    1.4- عنصر جدید (n) را به جدول فراوانی اضافه کن

الگوریتم را برای جدول فراوانی بالا به‌کار می‌گیریم. در مرحله‌ی اول دو عنصر ابتدایی لیست یعنی C و p از جدول حذف می‌شوند و درختی به‌صورت زیر تشکیل می‌شود:

برای قرار دادن یک عنصر در فرزند چپ یا راست، لازم است تابعی به‌عنوان قرارداد داشته باشیم. در این‌جا مقدار فراوانی کوچکتر یا مساوی را به‌عنوان فرزند چپ در نظر می‌گیریم. برای مقادیر فراوانی برابر، عنصر اول در چپ و عنصر بعدی در راست قرار می‌گیرد. حال این عنصر جدید را که Cp نام دارد و دارای فراوانی 2 است را به جدول فراوانی اضافه می‌کنیم. وضعیت جدول پس از این تغییرات و مرتب‌سازی دوباره به قرار زیر است:

دو عنصر بعدی، g و e هستند. مانند قبل، آن‌ها را از جدول حذف کرده و والد آن‌ها را به جدول اضافه می‌کنیم. در زیر، گره جدید و ساختار جدول پس از حذف آن‌ها را ملاحظه می‌کنید:

حرف f n I + o Cp ge a m r ¬ فراوانی 1 1 2 2 2 2 2 4 4 5 6

نوبت f و n است که از جدول حذف شوند. مشابه عناصر قبلی درخت جدیدی تشکیل داده و ریشه‌ی آن را به جدول اضافه می‌کنیم. پس از مرتب‌سازی خواهیم داشت:

حرف I + o Cp ge fn a m r ¬ فراوانی 2 2 2 2 2 2 4 4 5 6

حروف I و + نیز به همان ترتیب حذف شده و گره جدید I+ با فراوانی 4 به جدول اضافه می‌شود:

حرف o Cp ge fn a m I+ r ¬ فراوانی 2 2 2 2 4 4 4 5 6

دقت داشته باشید که هر یک از درخت‌های دودویی جدید، در کنار حروف به جدول فراوانی اضافه می‌شوند و هیچ تفاوتی بین آنها وجود ندارد. درواقع هر یک از حروف، درخت دودیی با یک گره (فقط ریشه) است. این مطلب مهم در گام بعدی باید بیشتر مورد توجه قرار بگیرد، جایی‌که در آن، حرف o و ریشه‌ی درخت دودویی Cp باهم ترکیب شده و درخت جدیدی با ریشه‌ی oCp تولید می‌کنند:

حرف o فرزند چپ و کل درخت دودویی Cp به‌عنوان فرزند راست قرار می‌گیرد. جدول فراوانی پس از این عملیات و مرتب‌سازی به شکل زیر خواهد بود:

حال درخت‌های ge و fn را برمی‌داریم. از آن‌جایی‌که پس از مرتب‌سازی، عنصر ge قبل از همه ظاهر شده، لذا به‌عنوان فرزند چپ قرار گرفته و درخت دودویی جدید با ریشه‌ی gefn به‌شکل زیر ساخته شده و در جدول قرار داده می‌شود:

حروف a و m هم به سادگی باهم ترکیب شده و درخت دودویی am را به شکل زیر تشکیل می‌دهند:

حرف I+ oCp gefn r ¬ am فراوانی 4 4 4 5 6 8

اجرای الگوریتم را تا رسیدن به تنها یک عنصر ادامه می‌دهیم. نتیجه‌ی ترکیب گره‌های I+ و oCp به قرار زیر است:

و حال نوبت گره‌های gefn و r است:

پس از ترکیب گره‌های ¬ و am داریم:

با ترکیب I+oCp و gefnr داریم:

در نهایت اینکه دو گره باقی‌مانده ¬am و I+oCpgefnr را باهم ترکیب می‌کنیم تا به ریشه‌ی ¬amI+oCpgefnr که ترکیبی از همه‌ی حروف را شامل می‌شود برسیم. درخت نهایی عبارت است:

پس از تشکیل درخت، گره‌های میانی (گره‌های زرد رنگ در تصویر بالا) صرفا برای شمارش گام‌ها بوده و محتوای آن‌ها هیچ استفاده‌ای ندارند. برای شهود بهتر، ضمن حذف محتوای آن‌ها، یال‌هایی که به سمت چپ هستند و قرار بود با برچسب 0 نشانه‌گذاری شوند را به‌رنگ آبی، و یالهایی که به سمت راست هستند و قرار بود با برچسب 1 نشانه‌گذاری شوند را به‌رنگ قرمز نشان می‌دهیم:

با شروع از ریشه، برچسب‌های مسیر منتهی به هر یک از حروف موجود در برگ‌ها را یادداشت کرده و به‌عنوان کد آن حرف در نظر می‌گیریم:

1#include <iostream>
2#include <fstream>
3#define MAX_TREE_NODES 40
4#define MAX_SYMBOLS 15
5#define MAX_INPUT 100
6#define MAX_OUTPUT 60
7#define MAX_CODE_LEN 10
8using namespace std;
9struct Node {
10  char CHAR;
11  int COUNT;
12  Node* LEFT;
13  Node* RIGHT;
14};
15struct MapNode {
16  char CHAR;
17  int LEN, CODE[MAX_CODE_LEN];
18};
19int InitTree(char TEXT[], Node NODES[]) {
20  int I, J, K = -1, F;
21  for (I = 0; I < strlen(TEXT); I++) {
22    F = 0;
23    for (J = 0; J <= K; J++)
24      if (NODES[J].CHAR == TEXT[I]) {
25        NODES[J].COUNT++;
26        F = 1;
27        break;
28      }
29      if (F == 0) {
30        K++;
31        NODES[K].CHAR = TEXT[I];
32        NODES[K].COUNT = 1;
33      }
34  }
35  return K;
36}
37void Sort(Node NODES[], int START, int END) {
38  for (int I = START; I <= END; I++) {
39    int J = I;
40    Node X = NODES[I];
41    while (J > START && NODES[J - 1].COUNT > X.COUNT) {
42      NODES[J] = NODES[J - 1];
43      J--;
44    }
45    NODES[J] = X;
46  }
47}
48Node MakeTree(Node NODES[], int START, int END) {
49  while (END > START) {
50    Sort(NODES, START, END);
51    END++;
52    NODES[END].COUNT = NODES[START].COUNT + NODES[START + 1].COUNT;
53    if (NODES[START].COUNT <= NODES[START + 1].COUNT) {
54      NODES[END].LEFT = &NODES[START];
55      NODES[END].RIGHT = &NODES[START + 1];
56    }
57    else {
58      NODES[END].LEFT = &NODES[START + 1];
59      NODES[END].RIGHT = &NODES[START];
60    }
61    START += 2;
62  }
63  return NODES[END];
64}
65void CreateMap(Node ROOT, MapNode MAP[], int& MC, int CODE[], int LEN) {
66  if (ROOT.LEFT != NULL) {
67    CODE[LEN] = 0;
68    CreateMap(*ROOT.LEFT, MAP, MC, CODE, LEN + 1);
69  }
70  if (ROOT.RIGHT != NULL) {
71    CODE[LEN] = 1;
72    CreateMap(*ROOT.RIGHT, MAP, MC, CODE, LEN + 1);
73  }
74  if (ROOT.CHAR != NULL) {
75    MAP[MC].CHAR = ROOT.CHAR;
76    MAP[MC].LEN = LEN;
77    for (int I = 0; I < LEN; I++)
78      MAP[MC].CODE[I] = CODE[I];
79    MC++;
80  }
81}
82void HuffmanCode(MapNode MAP[], int MC, char TEXT[], unsigned char CODE[], int& OUT_LEN) {
83  int I, J, K, P, BITS[8], B = 0, ASCII;
84  OUT_LEN = 0;
85  for (I = 0; I < strlen(TEXT); I++)
86    for (J = 0; J < MC; J++)
87      if (MAP[J].CHAR == TEXT[I])
88        for (K = 0; K < MAP[J].LEN; K++) {
89          BITS[B++] = MAP[J].CODE[K];
90          if (B == 8) {
91            ASCII = 0;
92            for (P = 7; P >= 0; P--)
93              if (BITS[P] == 1) {
94                int g = pow(2, 7 - P);
95                ASCII += g;
96              }
97            CODE[OUT_LEN] = ASCII;
98            OUT_LEN++;
99            B = 0;
100          }
101        }
102  if (B != 0) {
103    ASCII = 0;
104    for (P = B - 1; P >= 0; P--)
105      if (BITS[P] == 1)
106        ASCII += pow(2, B - P - 1);
107    CODE[OUT_LEN] = ASCII;
108  }
109}
110void main() {
111  char CLEAR_TEXT[MAX_INPUT];
112  unsigned char CODDED_TEXT[MAX_OUTPUT];
113  int MC = 0, S[MAX_CODE_LEN], IN_LEN = 0, OUT_LEN, START = 0, END, I, J;
114  Node NODES[MAX_TREE_NODES] = { NULL }, ROOT;
115  MapNode MAP[MAX_SYMBOLS] = { NULL };
116  fstream IN, OUT, CODES;
117  IN.open("INPUT.TXT", ios::in);
118  IN.getline(CLEAR_TEXT, MAX_INPUT);
119  END = InitTree(CLEAR_TEXT, NODES);
120  ROOT = MakeTree(NODES, START, END);
121  CreateMap(ROOT, MAP, MC, S, 0);
122  CODES.open("MAP.TXT", ios::out);
123  for (I = 0; I < MC; I++) {
124    CODES << "'" << MAP[I].CHAR << "'=";
125    for (J = 0; J < MAP[I].LEN; J++)
126      CODES << MAP[I].CODE[J];
127    CODES << endl;
128  }
129  CODES.close();
130  HuffmanCode(MAP, MC, CLEAR_TEXT, CODDED_TEXT, OUT_LEN);
131  OUT.open("OUTPUT.TXT", ios::out);
132  for (I = 0; I < OUT_LEN; I++)
133    OUT << CODDED_TEXT[I];
134  OUT.close();
135}