/* Farnabaz */
My Mind Overflow

پیاده سازی الگوریتم فشره سازی هافمن با جاوا

جمعه, 1391/01/04 - 13:00 — by Ahad Birang

الگوریتم های فراوانی برای فشرده سازی اطلاعات وجود دارد که هریک کاربردی مخصوص خود را دارند، یکی از ماثرترین و کاربردی ترین این ها روش کدهافمن است. کاربرد این روش برای فشرده سازی فایلهای متنی می باشد و وابسته به کاراکترهای موجود در متن می تواند از ۲۰ تا ۹۰ در صد، یک فایل را فشرده کند.‬
در این روش با استفاده از جدول توضیع کاراکترهای موجود در متن، هر کاراکتر را بصورت یک رشته از صفر و یک هر نمایش می دهد.
فرض کنید فایلی شامل صد هزار کاراکتر داریم و می خواهیم آن را با کمترین حجم ذخیره کنیم، ما مشاهده می کنید که توضیع کاراکتر هر در متن مطابق جدول (الف) می باشد، که تنها شامل ۶ نوع کاراکتر بوده و حرف a با تعداد ۴۵۰۰۰ بار تکرار شده.
روش های فراوانی برای نمایش این نوع فایل ها وجود دارد، ما می خواهیم هر کاراکتر را بصورت یک کد باینری یکتا نمایش دهیم. اگر ما از کدهای هم اندازه برای نمایش استفاده کنیم، نیاز به ۳بیت احتیاج داریم تا بتوانیم ۶ کاراکتر را نمایش دهیم.(a=000,b=001,…,f=1100)
این روش نیاز مند ۳۰۰۰۰۰ بیت برای کد کردن این متن می باشد.آیا راه بهتری نیز وجود دارد؟
کددهی با طول های متفادت روش بهتری از کدهای هم اندازه می باشد به صورت که کاراکتری که تکرار بیشتری دارد را با کدی به کوتاه و کم فراوانی ترین کاراکتر را باکدی بلند تر نمایش می دهیم. جدول (الف) اینچنین کدی را نمایش می دهد: رشته ی تک بیتی 0 کاراکتر a و رشته ی ۴ بیتی 1100 کاراکتر f را نمایش می دهد.این کد نیازمند (45 · 1 + 13 · 3 + 12 · 3 + 16 · 3 + 9 · 4 + 5 · 4) · 1,000 = 224,000 بیت برای نمایش فایل است. حدود ۲۵٪ ذخیره سازی می کند.
کدهای پیشوندی:
تمرکز ما بروی کدهایی است که در آن ها هیچ یک پیشوندی از دیگری نیست (برای مثال 0101 پیشوندی از 0101100110011 میباشد ولی 00 پیشوندی از آن نمی باشد.)به این نوع کدها ،کدهای پیشوندی می گویند. می توان نشان داد بهترین راه برای فشرده سازی اطلاعات با کددهی کاراکتری استفاده از کدهای پیشوندی است.
تبدیل کردن بفرم باینری کد فرآیند ساده ایست ، فقط کافیست کد مربوط به هر کارکتر را کنار هم قرار دهیم.برای مثال: برای مثال برای کددهی با طول متفاوت طبق جدول (الف) ما سه کاراکتر abc را بصورت 0.101.100=0101100 کد می کنیم.

a b c d e f
فراوانی (درصد) 45 13 12 16 9 5
کددهی هم اندازه 000 001 010 011 100 101
کددهی متغییر 0 101 100 111 1101 1100
جدول (الف)

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

درخت هافمن
شکل (ب)

کد هافمن:
هافمن الگوریتمی اختراع کرده است که کددهی پیشوندی بهینه ای ایجاد می کند که کد هافمن نام دارد.
در شبه کد زیر فرض بر این است که C مجموعه ای از n کاراکتر و هر کاراکتر c یک شی است دارای تکرار [f[c می باشد. این الگوریتم درخت T را ایجاد می کند که همانند کد مورد نظر است. آن با یک آرایه از |C| برگ آغاز میکند و با انجام 1-|C| عمل ادغام درخت نهایی را تولید می کند. صف اولویت Q که برای مشخص کردن دو برگی که فراوانی کمتری از بقیه دارند برای ادغام آنها مورد استفاده قرار می گیرد، نتیجه ی این ادغام شیی است که فراوانی آن حاصلجمع فراوانی های دو برگ ادغام شده می باشد.

HUFFMAN(C)
  n ← |C|
  Q ← C
  for i 1 to n - 1
       do allocate a new node z
          left[z] ← x ← EXTRACT-MIN (Q)
          right[z] ← y ← EXTRACT-MIN (Q)
          f [z] ← f [x] + f [y]
          INSERT(Q, z)
  return EXTRACT-MIN(Q)   ▹Return the root of the tree.

‫(به زبان ساده این الگویتم دو برگ با کاراکتری کمتری دارند را به یک گره وصل کرده و آن را به لیست اضافه می کنیم ،این عمل را تازمانی که لیست بیش از یک عضو دارد ادامه می دهیم.)‬
برای مثال ما درخت هافمن بصورت شکل (پ) می باشد که دارای ۶ نوع کاراکتر و صف اپولویت با تعداد عضو اولیه ی ۶ می باشد و ۵ عمل ادغام لازم است تا درخت نهایی حاصل شود، درخت نهایی کد پیشوندی مورد نظر را بدست می دهد که متناظر با آدرس برگ است.
خط ۳ صف اولویت Q را با کاراکتر های موجود در C مقدار دهی می کند. حلقه ی for بین خط های ۴ -۹ پیوسته دو گره که کمترین فراوانی را دارند از صف خارج کرده و دوباره آنها را بوسیله ی یک گره جدید z که حاصل ادغام این دو می باشد وارد لیست می کند. فراوانی گره z برابر مجموع فراوانی گره x وy است (خط ۸) . ‫گره z ، گره x را بعنوان فرزند چپ و گره y را بعنوان گره راست با خود بهمراه دارد.پس از n-1 ادغام یک گره در صف باقی می ماند که ریشه ی ‬درخت نهایی است که در خط ۱۰ بازگردانده می شود.

درخت هافمن
شکل (پ)

پیاده سازی ک هافمن در جاوا:
برای ایجاد درخت هافمن لازم است ابتدا لازم است کلاسی طراحی کنیم تا بتوان از آن بعنوان گره های درخت استفاده کنیم، این کلاس بایستی بتواند یک کراکتر و فراوانی آن را همراه داشته و لینکی به فرزند چپ و فرزند راست خود داشته باشد. همانند کلاس Link که دارای ۴ فیلد و ۳ سازنده می باشد.


class Link {

    Link left;
    Link right;
    Character c;
    int weight;

    public Link(int weight, Character c, Link left, Link right) {
        this.weight = weight;
        this.c = c;
        this.left = left;
        this.right = right;
    }

    public Link(int weight, Character c) {
        this.weight = weight;
        this.c = c;
        this.left = null;
        this.right = null;
    }

    public Link(int weight, Link left, Link right) {
        this.weight = weight;
        this.c = null;
        this.left = left;
        this.right = right;
    }
}

‎پس از این لازم است فراوانی هر یک از کاراکتر های موجود در فایل را بدست بیاوریم


public ArrayList<Link> search(FileReader fr, ArrayList<Character> ch) {
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        char[] tmp = new char[1];
        try {
            while (fr.ready()) {
                fr.read(tmp);
                if (hm.containsKey(tmp[0])) {
                    hm.put(tmp[0], hm.get(tmp[0]) + 1);
                } else {
                    ch.add(tmp[0]);
                    hm.put(tmp[0], 1);
                }
            }
        } catch (IOException ex) {
            Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
        }
        ArrayList<Link> st = new ArrayList<Link>();
        int temp;
        for (int i = 0; i < ch.size(); i++) {
            temp = hm.get(ch.get(i));
            if (st.isEmpty()) {
                st.add(new Link(temp, ch.get(i)));
            } else {
                int j = i;
                while (j > 0 && temp < st.get(j - 1).weight) {
                    j--;
                }
                st.add(j, new Link(temp, ch.get(i)));
            }
        }
        return st;
}

این متود دارای دو ورودی fr از نوع FileReader و ch که لیستی از نوع کاراکتر است، fr مشخص کننده ی مسیر ورودی فایل مورد نظر و ch آرایه ای است که برای نگه داری نوع کاراکترهای موجود درفایل مورد استفاده قرار می گیرد. hm شیئ از کلاس HashMap که برای نگه داری فراوانی کاراکترها استفاده می شود، آرایه تک عضوی tmp نیز بعنوان بافر برای خواندن متن از فایل تعریف شده است. حلقه ی while تا زمانی که به انتهای فایل نرسیده تکرار می شود و کاراکتر به کاراکتر متن را می خواند و در صورتی که کاراکتر جدیدی مشاهده کند آنرا به لیست ch اضافه می کند در غیر این صورت به فراوانی آن یک واحد می افزاید. حلقه ی for که به تعداد طول لیست ch تکرار می شود و لیست st را بصورت صعودی با گره های اولیه یا همان برگ های درخت مقدار دهی می کند و درنهایت st برگردانده می شود.(st در حقیقت همان صف اولویت است.)
حال می توانیم درخت مورد نظر را ایجاد کنیم.


private Link makeTree(ArrayList<Link> node) {
        ArrayList<Link> nodes = node;
        Link a, b;
        int tmp, i;
        while (nodes.size() > 1) {
            a = nodes.remove(0);
            b = nodes.remove(0);
            tmp = a.weight + b.weight;
            i = 0;
            while (i < nodes.size() && tmp > nodes.get(i).weight) {
                i++;
            }
            nodes.add(i, new Link(a.weight + b.weight, a, b));
        }
        return nodes.get(0);
}

نحوه ی کار متود makeTree همانند شبه کد درخت هافمن می باشد. این متود دارای یک آرگمان ورددی (node) است که همان لیست برگ هاست، حلقه ی while تا زمانی که درون لیست بیش از یک عضو وجود داشته باشد تکرار می شود و در هر بار تکرار خود دو گرهی که دارای فراوانی کمتری هستند را از لیست خارج کرده و آنها ادغام نموده و دوباره بطوری که ترتیب لیست بهم نخورد وارد آن می کند و در نهایت تنها عضو باقی مانده در لیست که همان ریشه ی درخت است را برمی گرداند.
با بدست آوردن درخت می توانیم کدها از آن استخراج کنیم.


private HashMap<Character, String> hash(Link root, String value,
            HashMap<Character, String> has) {
        if (root.left == null && root.right == null) {
            if (value.equals("")) {
                value = "0";
            }
            has.put(root.c, value);
        } else {
            if (root.left != null) {
                hash(root.left, value + "0", has);
            }
            if (root.right != null) {
                hash(root.right, value + "1", has);
            }
        }
        return has;
}

این متود طبق یک روند بازگشتی کد مربوط به هر کاراکتر را از درخت ساخته شده استخراج می کند‬. این متود دارای سه آرگومان ورودی root که نشانگر ریشه ی درخت است ، value که کد هر کاراکتر را در ذخیره می کند و has که سیستم کددهی نهایی را در خود ذخیره می کند. نحوه ی کار به این صورت است که اگر گرهی که بررسی می شود برگی از درخت باشد (root.left == null && root.right == null) کد متناظر آن (value) را در has ذخیره می کند ، اگر دارای فرزند چپ یا راست باشد تابع را برای هریک از فرزندانش فراخوانی می کند.در آخر نیز has را بر می گرداند.
از کنار هم قرار دادن این کدها رشته ای از 0 و1 ها بوجود می آید که همان کد مورد نظر ماست، برای تبدیل این رشته به مجموعه ای از بایت ها نیاز به فرآیندی شبیه متود زیر داریم.


public static Byte toByte(String str) {
        int io = 0;
        for (int i = 0; i < str.length(); i++) {
            io += Math.pow(2, i) * Byte.parseByte(str.charAt(str.length() - i - 1) + "");
        }
        return (byte) io;
}

این متود رشته ی str را که رشته ای به طول ۸ یا کمتر است را به یک بایت تبدیل می کند.
برای برگرداندن بایت به حالت رشته نیز بایستی تک تک بیت های بایت را چک کرده و صفر یا یک بودن آنها را تعیین کنیم،فرض کنید رشته کد تولیدی ما 0101001100 می باشد، برای ذخیره ی این کد به دو بایت حافظه نیاز داریم بایت اول برای ۸ رقم اول و بیت دوم برای دو رقم باقی مانده ، کار تبدیل کردن رشته به بایت کار ساده ایست ولی هنگام تبدیل بایت ها به رشته اگر طول رشته ی اولیه مضربی از ۸ نبوده باشد کار کمی دشوار است ، چون با خواندن آخرین بایت بجای ۸ رقم تعداد کمتری برگرداند برای این نیز نیازمند فرآیند دیگری هستیم. متود to‪_‬String این عمل را انجام میدهد، این متود overload شده و اگر یک رشته بعنوان ورودی به آن داده شود یک رشته بطول ۸ بر می گرداند ولی اگر علاوه بر رشته عددی مثل n را نیز به آن پاس کنیم فقط n رقم (n رقم پایین) بر می گرداند.


public static String to_String(Byte byt) {
        String tmp = Integer.toBinaryString(byt);
        if (tmp.length() > 8) {
            tmp = tmp.substring(24);
        }
        while (tmp.length() < 8) {
            tmp = "0" + tmp;
        }
        return tmp;
    }

    public static String to_String(Byte byt, int len) {
        String tmp = Integer.toBinaryString(byt);
        if (tmp.length() > 8) {
            tmp = tmp.substring(24);
        }
        while (tmp.length() < 8) {
            tmp = "0" + tmp;
        }

        return tmp.substring(8 - len);
}

اکنون با کنار هم قرار دادن اینها و جایگذاری کدها به جای کاراکترها، می توانیم یک فایل متنی را فشرده کرده و در فایلی کم حجم تر ذخیره کنیم، فقط لازم است به نکاتی توجه کنیم:
۱- همواره باید تعداد بیت های مفید بایت آخر را در فایل خروجی ذخیره کنیم تا هنگام بازگردانی فایل اشتباهی حاصل نشود.
۲- برای اینکه بخواهیم فایلی که به فرم بایتی ذخیره شده را به فایل متنی بارگردانی کنیم لازم سیستم کددهی اولیه که با آن فایل بایتی را ساخته ایم داشته باشم برای این کار می توانیم به ۲ روش عمل کنیم: الف) سیستم کددهی را بطور مستقیم در فایلی بایتی ذخیره کنیم. ب) هر کاراکتر را با فراوانی آن در فایل بایتی ذخیره کنیم و هنگام بازگردانی دوباره درخت هافمن را ساخته و سیستم کددهی را دوباره بدست آوریم.

برگرفته از:

Introduction to Algorithms, Second Edition

+1
-2
-1

نظرات

Omid
1393/03/23

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

امیر
1391/04/12

ممنونم ازت ولی ترجمه اش یک کم مشکل داشت. در کل دمتون گرم

ارسال نظر جدید

(If you're a human, don't change the following field)
Your first name.
محتوای این فیلد مخفی مانده و نمایش داده نمی شود.