در تپش این هفته، ماجرای فریب و تعرض در پوشش عرفانهای دروغین و رمالی را بررسی کردیم
آشنایی با الگوریتمهای فشردهسازی دادهها
فایلهایتان را کوچکتر کنید
یکی از الگوریتمهای مطرح در کامپیوتر و بهویژه در مورد تصاویر، الگوریتمهای فشردهسازی است. این الگوریتمها دادهها را فشرده میکنند طوری که بتوان بهراحتی با داده فشرده شده به داده اصلی رسید. یکی از این الگوریتمها الگوریتم کدگذاری هافمن است.
این الگوریتم که توسط دیوید هافمن توسعه یافت، از یک جدول به نام «کد طول متغیر» برای کد کردن دادهها استفاده میکند. اطلاعات جدول کد طول متغیر بر اساس احتمال وقوع یک کاراکتر در داده منبع بهدست میآید.
کارکرد
این الگوریتم یک داده را میگیرد و سپس جدول طول متغیر را بر اساس آن تولید میکند. مثلا فرض کنید داده ما رشته متنی مثل «روزنامه جامجم هر روز صبح منتشر میشود.» است، حالا بیاییم جدول کد طول متغیر را برای این رشته محاسبه کنیم. کاراکتر فاصله 6 بار و کاراکتر (ز) 2 بار تکرار شده است و همینطور برای بقیه کاراکترها این عدد را بهدست میآوریم. در نهایت یک جدول بهدست میآید که مشخص میکند هر کاراکتر در متن بالا چند بار تکرار شده است.
جدول شامل دو ستون است که یکی ستون آن کاراکتر و دیگری کد طول متغیر است. ما دادههای جدول را بر اساس کد طول متغیر بهصورت صعودی مرتب میکنیم. سپس دو عنصر کوچکتر را انتخاب کرده و آنها را درون درختی قرار میدهیم که برگهای آن، دو عدد و ریشه آن، مجموع کد طول متغیر آن دو برگ است.
به فرض کد طول متغیر دو کاراکتر اول مجموعه مرتب شده بهترتیب برابر 3 و 5 است. این دو کاراکتر در یک درخت به ریشهای با عدد 8 و یال سمت چپ برابر 3 و یال سمت راست برابر 5 قرار میگیرند (به این نکته باید توجه داشته باشید که در درخت حاصل از هر مرحله باید یال سمت راست بزرگتر از یال سمت چپ باشد). حال عدد 8 را به عنوان امید ریاضی در نظر میگیریم و بر اساس جدول طول متغیر دوباره دادهها را مرتب میکنیم و دوباره درخت متناظری درست میکنیم که متشکل از اولین عنصر مرتب شده برابر 7 و درخت قبلی است.
در این مرحله کاراکتری که طول کد متغیر آن برابر 7 است در سمت چپ درختی قرار میگیرد که ریشه آن برابر 15 است و سمت راست آن همان درختی است که در مرحله پیش ساختیم. آنقدر این کار را ادامه میدهیم تا به یک درخت برسیم.
نتایج حاصل از پیمایش درخت برابر کد هافمن هستند. در این درخت یال سمت راست را برابر صفر و یال سمت چپ را برابر یک در نظر میگیرند. فرض کنید درختی مطابق شکل زیر داشته باشیم:
کد هافمن مربوط به عدد a برابر 010 است، به این دلیل که ابتدا به سمت چپ رفته پس یک صفر داریم، سپس به سمت راست رفته پس یک داریم و دوباره به سمت چپ آمده و صفر داریم و نتیجه برابر 010 است.
برای این که مراحل ایجاد کد هافمن را مشاهده کنید به نشانی زیر مراجعه کنید:
http://upload.wikimedia.org/wikipedia/commons/a/ac/Huffman_huff_demo.gif
شبه کد الگوریتم هافمن
C نشان دهنده یک رشته اطلاعات است. ابتدا طول رشته را در N میریزیم. سپس برای این رشته اطلاعاتی جدول کد طول متغیر را محاسبه میکنیم که این عمل از مرتبه (O(n انجام میشود. سپس برای دو کاراکتر اولی یک درخت تشکیل داده و بعد آن را در جای مناسب خود در جدول قرار میدهیم طوری که مرتب بودن بر اساس کد طول متغیر همچنان حفظ شود. این عمل از مرتبه (O(nLogn انجام میپذیرد. در نهایت عنصر کوچک مجموعه را برمیگردانیم.
تازه ها
گوناگون
پیشنهاد سردبیر
گزارش «جامجم» درباره دستاوردهای زبان فارسی در گفتوگو با برخی از چهرههای ادب معاصر
فارسی، زبان گفتوگوی جهان
معاون وزیر بهداشت:
