روش کدنویسی ساده ( RUN LENGHT CODING) که با موفقیت توسط آرشیوهای محبوب استفاده می شود.
این روش بر اساس شمارش طول کاراکترهای تکرار شده در یک ردیف، و نوشتن در فایل بسته بندی شده به جای دنباله ای از این کاراکترها، نوع اطلاعات: تعداد کاراکترها و خود کاراکتر تکراری است. به عنوان مثال، یک رشته مانند " AAAAABBBCCCADDDEEL". به دنباله ای مانند" بسته می شود 5A3B3CADDEELهمانطور که از مثال مشخص است، دنباله 5 حرف "الف" به دو کاراکتر "5" و "الف" بسته بندی شده است، و دنباله های "DD"، "EE"، "L" اصلاً بسته بندی نشده اند. ، زیرا هیچ سودی از جایگزینی این کاراکترها در دنباله ای از نوع "طول" + "حرف" وجود ندارد.
هنگام پیاده‌سازی بسته‌بندی یک فایل با استفاده از این روش، مشکلاتی از جمله اینکه چگونه بازکننده اطلاعات کنترل را از یک فایل بسته‌بندی شده از داده‌های بسته‌نشده تشخیص می‌دهد، پیش می‌آید. به عنوان مثال، همانطور که در موردی که در بالا بحث شد، آیا بازکننده کاراکتر کنترل "5" را از یک کاراکتر بسته نشده با همان کد متمایز می کند؟ برای حل این مشکل دو گزینه وجود دارد:
(من). نمادی را پیدا کنید که کمتر از بقیه وجود دارد یا اصلاً در فایل بسته بندی شده وجود ندارد و از آن به عنوان کنترل استفاده کنید. برای راحتی در توضیح زیر آن را پیشوند بنامیم. اکنون دنباله "AAAAA" توسط بسته بندی به پیشوند (8 بیت)، "A" (8 بیت)، مقدار (8 بیت) تبدیل می شود، یعنی 5 بایت با سه بایت جایگزین می شود. اگر در هنگام بسته‌بندی، بیتی با کد پیشوندی در فایل منبع مواجه شد، دو بایت با کد پیشوند در فایل به دست آمده نوشته می‌شود و با این ویژگی، بسته‌کننده تشخیص می‌دهد که پیشوند کجا نماد و کجا کنترل است. اطلاعات تغییراتی در این روش ممکن است، به عنوان مثال:
1. تعداد کدگذاری شده نه با هشت بیت، بلکه با سه، چهار و غیره، که درصد بسته بندی را افزایش می دهد، اما حداکثر طول کاراکترهای تکراری را که می توان در مورد رمزگذاری با سه بیت بسته بندی کرد، محدود می کند. (از 3 تا 10، یعنی 000=3، ...،111=10)، و اگر طول آن بیش از 10 کاراکتر باشد، هر کدام ده کاراکتر را بسته بندی کنید.
2. تغییر دوم امکان پذیر است، زمانی که تعداد کاراکترهای تکراری نه با هشت بیت، بلکه با سه بیت کدگذاری شود و طول نویسه های تکراری به 265 بیت محدود شود. این سوال پیش می آید که چگونه می توان 256 طول مختلف را در 3 بیت رمزگذاری کرد. به نظر می رسد که ممکن است، اما فقط محدوده از 3 تا 9 است، اگر طول کاراکترهای تکراری بیش از 9 باشد، "111" در کد باینری در سه بیت نوشته می شود که برابر با "7" است. این بدان معنی است که طول واقعی دنباله در بایت بعدی است (8 بیت برای طول های 10 تا 256 کاراکتر اختصاص داده می شود).
در اینجا چند نمونه آورده شده است:
دنباله هایی داریم:
الف) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"
ب) "CBBBBBBBBBBEEEEEEEEEEEEA"
بیایید آنها را بسته بندی کنیم:
1. با روش RLE (رمزگذاری طول اجرا - بسته بندی بایت های مکرر).
الف) پیشوند برابر با "D" را بگیرید، دریافت می کنیم:
«د»، «د»، «الف»، 5، «د»، «ب»، 10، «ج»، «د»، «الف»، 15.درصد فشرده سازی = 12 بایت / 32 بایت = 37.5٪
در یک فایل بسته بندی شده، بایت پیشوند اولین بایت است تا بسته بندی کننده بداند کدام بایت پیشوند است.
ب) یک پیشوند برابر با "A" بگیرید، اگرچه در واقع بسته بندی این کار را انجام نمی دهد، زیرا کاراکترهای زیادی در این دنباله وجود ندارد، بنابراین بایگانی یک کاراکتر استفاده نشده را به عنوان پیشوند می گیرد.
دنباله بسته بندی شده:
"الف"، "ج"، "الف"، "ب"، 10، "الف"، "ه"، 10، "الف"، "الف"درصد فشرده سازی = 10 بایت / 22 بایت = 45.5٪
2. حالا بیایید همان خطوط را طبق اصلاح 1 روش RLE با مقادیر پیشوند یکسان بسته بندی کنیم تا کارایی را تجزیه و تحلیل کنیم.
"د"، "د"، "الف"، 2، "د"، "ب"، 7،
8 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 3 بیت"د"، "الف"، 7، "د"، "الف"، 2
8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 3 بیتدرصد فشرده سازی = 84 بیت / (22 * 8) بیت = 32.8٪
"الف"، "ج"، "الف"، "ب"، 7، "الف"، "ه"، 7، "الف"، "الف"
8 بیت 8 بیت 8 بیت 8 بیت 4 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیتدرصد فشرده سازی = 70 بیت / (22 * 8) بیت = 39.8٪
3. حالا بیایید اثربخشی آخرین اصلاح را بررسی کنیم:
الف) دنباله بسته بندی شده:
"د"، "د"، "الف"، 2، "د"، "ب"، 7، 0
8 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 3 بیت 8 بیت"د"، "الف"، 7، 5
8 بیت 8 بیت 3 بیت 8 بیتدرصد فشرده سازی = 81 بیت / (32 * 8) بیت = 31.6٪
ب) دنباله بسته بندی شده:
"A"، "C"، "A"، "B"، 7، 0، "A"، "E"
8 بیت 8 بیت 8 بیت 8 بیت 3 بیت 8 بیت 8 بیت 8 بیت7 , 0 , "A" , "A"
3 بیت 8 بیت 8 بیت 8 بیتدرصد فشرده سازی = 86 بیت / (22 * 8) بیت = 48.9٪
این مثال‌ها نشان می‌دهند که بسته به محتوای داده‌های بسته‌بندی شده، یکی یا دیگری الگوریتم مؤثر است، بنابراین برای اینکه انتخاب کنید کدام الگوریتم کارآمدتر است، باید آنها را روی انواع مختلف فایل‌ها آزمایش کنید.
(II). گزینه دوم برای ضبط اطلاعات کنترل برای unpacker به این صورت است: اگر یک کاراکتر در متن وجود داشته باشد، یک بیت کنترل برابر با یک و خود این کاراکتر در فایل خروجی نوشته می شود. اگر دنباله ای از بایت های تکراری وجود داشته باشد، به عنوان مثال "AAAAAA"، اطلاعات بسته بندی شده به این صورت خواهد بود: 0 (1 بیت)، بایت A (8 بیت)، تعداد (3-8 بیت).
بیایید برای وضوح مثالی بزنیم. برای این کار، دنباله هایی از مثال های قبلی بگیرید.
1) تعداد بایت های تکرار شده به 8 بیت کدگذاری می شود.
الف) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C" , 0 , "A" , 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.درصد فشرده سازی = 71 بیت / 256 بیت = 27.7٪
ب) 1، "C"، 0، "B"، 10، 0، "E"، 10، 1، "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.درصد فشرده سازی = 52 بیت / 176 بیت = 29.5٪
2) اکنون 3 بیت برای رمزگذاری تعداد بایت های تکراری در نظر می گیریم که در آن مقادیر از 2 تا 8 (0 - 6) را می توان رمزگذاری کرد، اگر طول دنباله تکرار بیشتر باشد، این سه بیت شامل "111" (7 اعشاری)، و طول واقعی در بایت بعدی است (طول 9 تا 264).
الف) 0 , "A" , 3 , 0 , "B" , 7 , 1 , 0 , "C" , 0 , 0 , "A" , 7 , 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.درصد فشرده سازی = 64 بیت / 256 بیت = 20.3٪
ب) 1، "C"، 0، "B"، 7، 1، 0، "E"، 7، 1، 1، "A"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.درصد فشرده سازی = 58 بیت / 176 بیت = 33٪
اگر مقدار در 4 بیت (2..16) کدگذاری شده باشد، پس
1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.درصد فشرده سازی = 44 بیت / 176 بیت = 25٪
همانطور که از مثال‌ها می‌بینید، گزینه بسته‌بندی دوم کارآمدتر است، زیرا توالی‌هایی را که با دو کاراکتر شروع می‌شوند، فشرده می‌کند، که معمولا اکثریت قریب به اتفاق هستند. اولین نوع شامل توالی هایی بود که از سه کاراکتر شروع می شد.
طبقه بندی اساسی الگوریتم های فشرده سازی برگشت پذیر
روش های عملی مختلفی برای فشرده سازی بدون تلفات وجود دارد که برای انواع مختلف داده ها و حجم های مختلف کارایی متفاوتی دارند. با این حال، این روش ها بر اساس سه طرح اصلی فشرده سازی کلاسیک هستند:
کدگذاری سری دنباله ای (RLE)؛
روش های فشرده سازی آماری؛
روش های فشرده سازی دیکشنری (اکتشافی).
فشرده سازی با روش رمزگذاری سری: الگوریتم RLE
شناخته شده ترین روش ساده و الگوریتم فشرده سازی برگشت پذیر، رمزگذاری طول اجرا (RLE) است. ماهیت روش های این رویکرد جایگزینی زنجیره ها یا سری از بایت های تکرار شونده یا توالی آنها با یک بایت رمزگذاری و شمارنده برای تعداد تکرارهای آنها است. مشکل همه روش‌های مشابه تعیین روشی است که در آن الگوریتم فشرده‌سازی می‌تواند سری رمزگذاری‌شده را از دیگر توالی‌های بایت رمزگذاری نشده در جریان بایت‌های حاصل تشخیص دهد. راه حل مشکل معمولا با قرار دادن برچسب ها در ابتدای زنجیره های کدگذاری شده به دست می آید. چنین علائمی ممکن است، به عنوان مثال، مقادیر بیت مشخصه در اولین بایت اجرای کدگذاری شده، مقادیر اولین بایت اجرای کدگذاری شده و موارد مشابه باشد. این روش ها معمولا برای فشرده سازی بیت مپ بسیار کارآمد هستند. تصاویر گرافیکی(BMP، PCX، TIF، GIF)، زیرا دومی شامل چند سری طولانی از دنباله های تکراری بایت است. نقطه ضعف روش RLE نسبت فشرده سازی نسبتا کم یا هزینه رمزگذاری فایل ها با تعداد سری کم و حتی بدتر از آن، با تعداد کمی بایت های تکراری در سری است.
الگوریتم RLE مبتنی بر ایده شناسایی توالی داده های مکرر و جایگزینی آنها با ساختار ساده تری است که کد داده و ضریب تکرار را مشخص می کند. به عنوان مثال، اجازه دهید چنین دنباله ای از داده ها داده شود که در معرض فشرده سازی هستند: 1 1 1 1 2 2 3 4 4 4 . در الگوریتم RLE، پیشنهاد شده است که آن را با ساختار زیر جایگزین کنید: 1 4 2 2 3 1 4 3 ، که در آن عدد اول هر جفت عدد کد داده و عدد دوم ضریب تکرار است. اگر 1 بایت برای ذخیره هر عنصر داده از دنباله ورودی اختصاص داده شود، کل دنباله 10 بایت حافظه اشغال می کند، در حالی که دنباله خروجی (نسخه فشرده) 8 بایت حافظه را اشغال می کند. واضح است که الگوریتم RLE با طول بیشتر توالی داده های مکرر اثر فشرده سازی بهتری را ارائه می دهد. در مورد مثال بالا، اگر دنباله ورودی به این صورت باشد: 1 1 1 1 1 1 3 4 4 4، آنگاه نسبت تراکم 60 درصد خواهد بود. در این راستا، کارایی بیشتر الگوریتم RLE با فشرده سازی داده های گرافیکی (به ویژه برای تصاویر تک رنگ) حاصل می شود.
الگوریتم های اکتشافی (لغت نامه).فشرده سازی (LZ, LZW) به دنبال خطوطی در فایل بگردید که تکرار شده اند و فرهنگ لغت عباراتی را بسازید که قبلاً با آنها روبرو شده اند. به طور معمول، چنین الگوریتم هایی دارای تعدادی پارامتر خاص (اندازه بافر، حداکثر طول عبارت و غیره) هستند که انتخاب آنها به تجربه نویسنده اثر بستگی دارد و این پارامترها به گونه ای انتخاب می شوند که به دست آیند. نسبت بهینهزمان اجرای الگوریتم، نسبت فشرده سازی و لیست فایل هایی که به خوبی فشرده می شوند.
الگوریتم های آماری(هافمن، شانون فانو، حساب) الگوریتم‌های آماری از مدل داده‌های آماری استفاده می‌کنند و کیفیت فشرده‌سازی اطلاعات مستقیماً به خوب بودن این مدل بستگی دارد. در نظر گرفتن ویژگی‌های آماری داده‌ها در ساده‌ترین حالت به معنای استفاده از کدهای غیریکنواخت برای رمزگذاری است - کاراکترهای متداول در کدهای کوتاه و به ندرت در کدهای طولانی رمزگذاری می‌شوند. یعنی چنین الگوریتم هایی نیاز به دانستن احتمالات وقوع کاراکترها در تصویر دارند که در حالت ساده می توان با فراوانی وقوع کاراکترها در داده های ورودی تخمین زد. به عنوان یک قاعده، این احتمالات ناشناخته هستند. هدف از رمزگذاری تبدیل جریان ورودی به یک جریان بیت با حداقل طول است که با کاهش آنتروپی (آشوب) جریان ورودی با در نظر گرفتن فرکانس های نماد به دست می آید.
طول کد نشان دهنده کاراکترهای الفبای جریان باید متناسب با مقدار اطلاعات جریان ورودی باشد و طول کاراکترهای جریان در بیت ممکن است مضربی از 8 یا حتی متغیر نباشد. اگر توزیع احتمال فراوانی‌های وقوع کاراکترها از الفبای جریان ورودی مشخص باشد، می‌توان یک مدل کدگذاری بهینه ساخت. با این حال، به دلیل وجود تعداد زیادی از فرمت های مختلف فایل، کار بسیار پیچیده تر می شود، زیرا. توزیع فرکانس نماد داده از قبل مشخص نیست. در این مورد از دو رویکرد استفاده می شود.
اولینشامل مشاهده جریان ورودی و ایجاد یک رمزگذاری بر اساس آمارهای جمع آوری شده است (این به دو گذر از فایل نیاز دارد - یکی برای مشاهده و جمع آوری اطلاعات آماریدوم - برای کدگذاری، که تا حدودی دامنه چنین الگوریتم هایی را محدود می کند، زیرا، بنابراین، امکان کدگذاری تک گذر "در حال پرواز"، مورد استفاده در سیستم های مخابراتی، جایی که مقدار داده ها گاهی اوقات مشخص نیست، و آنها را محدود می کند. ارسال مجدد یا تجزیه ممکن است زمان زیادی طول بکشد). در چنین حالتی، طرح آنتروپی کدگذاری استفاده شده در جریان خروجی نوشته می شود. این تکنیک به کدگذاری هافمن ایستا معروف است. جدول نمادها به همراه فایل فشرده منتقل می شود. چنین الگوریتم هایی اکثر فایل ها را به خوبی فشرده می کنند، اما انتقال اضافی لازم جدول فرکانس نماد و همچنین نیاز به دو پاس منبع فایلبرای جمع آوری و فشرده سازی آمار.
روش دوم- روش کدگذاری تطبیقی اصل آن تغییر طرح رمزگذاری بسته به ماهیت تغییرات در جریان ورودی است. تطبیقی - شروع به کار با یک جدول اولیه ثابت فرکانس کاراکترها (معمولاً همه کاراکترها در ابتدا به یک اندازه محتمل هستند) و در روند کار این جدول بسته به کاراکترهایی که در فایل رخ می دهد تغییر می کند. مزایا: الگوریتم یک گذر، عدم نیاز به انتقال جدول فرکانس نمادها، فشرده سازی کلاس گسترده ای از فایل ها به طور کاملا موثر. این رویکرد دارای یک الگوریتم یک گذر است و نیازی به ذخیره صریح اطلاعات در مورد رمزگذاری مورد استفاده ندارد. کدگذاری تطبیقی می‌تواند نسبت به کدگذاری استاتیک میزان فشرده‌سازی بیشتری داشته باشد، زیرا تغییرات در فرکانس‌های جریان ورودی کاملاً در نظر گرفته می‌شود. این تکنیک به کدگذاری پویا هافمن معروف است.
با داشتن این نکته در ذهن الگوریتم های آماریرا می توان به سه کلاس تقسیم کرد:
1. غیر تطبیقی - از احتمالات نمادهای ثابت و از پیش تعیین شده استفاده کنید. جدول احتمال نماد با فایل منتقل نمی شود زیرا از قبل مشخص شده است. نقطه ضعف: منطقه باریک استفاده برای یک جدول فرکانس خاص، که برای آن نسبت فشرده سازی قابل قبولی به دست می آید.
2. نیمه تطبیقی - برای هر فایل جدولی از فرکانس های کاراکتر ساخته شده و فایل بر اساس آن فشرده می شود. جدول نمادها به همراه فایل فشرده منتقل می شود. چنین الگوریتم‌هایی اکثر فایل‌ها را به خوبی فشرده می‌کنند، اما ارسال اضافی جدول فرکانس نماد ضروری است و همچنین نیاز به دو پاس از فایل منبع برای جمع‌آوری آمار و فشرده‌سازی است.
3. تطبیقی - شروع به کار با یک جدول اولیه ثابت فرکانس کاراکترها (معمولاً همه کاراکترها در ابتدا به یک اندازه محتمل هستند) و در روند کار این جدول بسته به کاراکترهایی که در فایل رخ می دهد تغییر می کند. مزایا: الگوریتم یک گذر، عدم نیاز به انتقال جدول فرکانس نمادها، فشرده سازی کلاس گسترده ای از فایل ها به طور کاملا موثر.
الگوریتم هافمن مبتنی بر ایده رمزگذاری توسط گروه های بیتی است. ابتدا انجام شد تجزیه و تحلیل فرکانستوالی داده های ورودی، یعنی فرکانس وقوع هر کاراکتر در آن تنظیم می شود. پس از آن، کاراکترها با کاهش دفعات وقوع مرتب می شوند.
ایده اصلی این است که هر چه یک کاراکتر رایج تر باشد، بیت های کمتری را رمزگذاری می کند. نتیجه رمزگذاری به فرهنگ لغت مورد نیاز برای رمزگشایی وارد می شود. مثال ساده ای را در نظر بگیرید که عملکرد الگوریتم هافمن را نشان می دهد.
در کدنویسی هافمن ایستا، کاراکترهای ورودی (رشته‌هایی از بیت‌های با طول‌های مختلف) به رشته‌های بیتی، همچنین با طول متغیر - کدهای آنها، اختصاص داده می‌شوند. طول کد هر کاراکتر متناسب با لگاریتم باینری فرکانس آن گرفته می شود که با علامت مخالف گرفته می شود. ولی مجموعه مشترکاز میان تمام کاراکترهای مختلف که با آنها مواجه می شویم، الفبای جریان را تشکیل می دهد. این رمزگذاری پیشوند است، که رمزگشایی آن را در جریان حاصل آسان می کند، زیرا با رمزگذاری پیشوند، کد هر کاراکتری پیشوند کد هیچ کاراکتر دیگری نیست - الفبای منحصر به فرد است.
حتی 10-15 سال پیش، بایگانی ها عمدتاً برای صرفه جویی در فضا استفاده می شدند دیسکهای سختو به منظور جا دادن حداکثر داده بر روی فلاپی دیسک. با این حال، زمان تغییر کرده است. هیچ کس مدت زیادی است که از فلاپی دیسک به عنوان وسیله ای برای انتقال و ذخیره اطلاعات استفاده نمی کند و هزینه درایوها به قدری کم شده است که هیچ کس حتی به فشرده سازی داده ها برای صرفه جویی در فضا فکر نمی کند. علاوه بر این، حجم داده ها به قدری بزرگ شده است که بایگانی و حذف آنها برای صرفه جویی در فضا به سادگی عملی نیست، زیرا زمان زیادی می برد. خب، در واقع، امروزه حجم اطلاعات درایوهای کاربران بر حسب ترابایت اندازه گیری می شود. حال تصور کنید که آرشیو یک ترابایت داده چقدر طول می کشد. این نه یک یا حتی دو ساعت، بلکه حداقل 10-12 ساعت طول می کشد، یعنی کامپیوتر باید تمام شب روشن بماند.
به نظر می رسد که آرشیوهای امروزی باید به تدریج ارتباط خود را از دست بدهند. اما چنین اتفاقی نمی افتد. اکثریت قریب به اتفاق کاربران، در میان سایر برنامه‌ها، بایگانی‌هایی را نصب کرده‌اند، یا از بایگانی‌کننده‌ای استفاده می‌کنند که در سیستم عامل ویندوز تعبیه شده است (ما دیگر سیستم‌عامل‌ها را در این نشریه در نظر نمی‌گیریم).
واقعیت این است که انتصاب بایگانی ها تغییر کرده است. امروزه از آنها عمدتاً برای ارسال داده ها به وب استفاده می شود. اکثر درایورها در وب سایت های تولید کنندگان در آرشیو قرار می گیرند و بیشتر برنامه های موجود در منابع مختلف نیز بایگانی می شوند. به هر حال، خود کاربر، قبل از آپلود هر گونه داده در شبکه (مثلاً برای منابع اشتراک فایل)، داده ها را در یک آرشیو بسته بندی می کند.
مربوط به بازار روسیه، سپس ما رایج ترین سه بایگانی را داریم: WinRAR، WinZip و 7-Zip که در هر دو نسخه 32 و 64 بیتی ارائه شده اند. این آنها هستند که در این مقاله با هم مقایسه خواهیم کرد. با این حال، ابتدا اجازه دهید نگاهی گذرا به برخی از آنها بیندازیم جنبه های نظریکار بایگانی
الگوریتم های فشرده سازی اطلاعات
ماهیت هر الگوریتم فشرده سازی اطلاعات این است که با مقداری تبدیل مجموعه اولیه بیت های اطلاعاتی، مجموعه خاصی را در خروجی به دست آوریم. کوچکتر. علاوه بر این، تمام الگوریتم های تبدیل داده ها را می توان به صورت مشروط به دو دسته تقسیم کرد: برگشت پذیر و غیر قابل برگشت.
الگوریتم فشرده سازی اطلاعات برگشت ناپذیر به معنای چنین تغییر شکلی از توالی بیت اصلی است که در آن توالی خروجی با اندازه کوچکتر اجازه نمی دهد دنباله ورودی دقیقاً بازیابی شود. از الگوریتم‌های فشرده‌سازی برگشت‌ناپذیر برای مثال در رابطه با داده‌های گرافیکی، تصویری و صوتی استفاده می‌شود و این همیشه منجر به از دست دادن کیفیت آنها می‌شود. طبیعتاً الگوریتم‌هایی برای فشرده‌سازی برگشت‌ناپذیر داده‌ها در بایگانی‌کننده‌ها استفاده نمی‌شوند و بنابراین ما آنها را بیشتر در نظر نخواهیم گرفت.
الگوریتم های فشرده سازی برگشت پذیر داده ها به شما این امکان را می دهند که دقیقاً دنباله داده های اصلی را از دنباله فشرده بازیابی کنید. این الگوریتم ها هستند که در بایگانی ها استفاده می شوند. ویژگی های مشترک همه الگوریتم های فشرده سازی عبارتند از: نسبت فشرده سازی (نسبت حجم توالی داده های اصلی و فشرده)، نرخ فشرده سازی (زمان صرف شده برای بایگانی مقدار معینی از داده ها) و کیفیت فشرده سازی (مقداری که نشان می دهد چقدر قوی است. توالی داده با اعمال فشرده سازی مجدد بر روی آن مطابق با همان الگوریتم یا الگوریتم دیگری فشرده می شود.
نظریه فشرده سازی اطلاعات که به عنوان نظریه کدگذاری اقتصادی اطلاعات گسسته نیز شناخته می شود، شاخه نسبتاً پیچیده ای از علوم ریاضی است. البته ارائه حتی مبانی آن نیز بسیار فراتر از حوصله این مقاله است و به همین دلیل الگوریتم های مختلف فشرده سازی اطلاعات را بدون پرداختن به جزئیات تنها به صورت سطحی بررسی می کنیم. علاوه بر این، امروزه الگوریتم‌های فشرده‌سازی داده‌های زیادی توسعه یافته‌اند و در نظر گرفتن آنها نیز بخشی از وظیفه ما است. بنابراین، ما فقط چند الگوریتم را به صورت کیفی توصیف می کنیم که به ما امکان می دهد به دست آوریم ایده کلیدر مورد روش های فشرده سازی اطلاعات
الگوریتم RLE
یکی از قدیمی‌ترین و ساده‌ترین روش‌های فشرده‌سازی اطلاعات، الگوریتم RLE (Run Length Encoding) است، یعنی الگوریتم رمزگذاری سری‌های توالی. پیاده سازی این روش بسیار ساده است و یکی از الگوریتم های بایگانی است و ماهیت آن جایگزینی یک سری (گروه) از بایت های تکراری با یک بایت رمزگذاری و یک شمارنده برای تعداد تکرارهای آنها است. یعنی گروهی از بایت های یکسان با یک جفت جایگزین می شوند:<счетчик повторений, значение>، که باعث کاهش افزونگی داده ها می شود.
در این الگوریتم علامت شمارنده همان هایی است که در دو بیت بالای بایت خوانده شده قرار دارند. به عنوان مثال، اگر دو بیت اول 11 باشد، 6 بیت باقی مانده به شمارنده اختصاص داده می شود که می تواند مقادیری از 1 تا 64 داشته باشد. بر این اساس، یک سری از 64 بایت تکراری را می توان تنها با دو بایت تعریف کرد، که است، 32 بار فشرده شده است.
اجرای دیگری از این الگوریتم وجود دارد، زمانی که علامت شمارنده در اولین بایت شمارنده 1 باشد. در این مورد، شمارنده می تواند حداکثر مقدار، برابر با 127 - و بنابراین حداکثر نسبت تراکم برابر با 64 خواهد بود.
واضح است که الگوریتم RLE تنها زمانی کارآمد است که تعداد زیادی گروه طولانی از بایت های یکسان وجود داشته باشد. اگر بایت ها تکرار نشوند، استفاده از روش RLE منجر به افزایش حجم فایل می شود.
روش RLE عموماً برای فشرده‌سازی گرافیک‌های بیت مپ (BMP، PCX، TIF، GIF) بسیار کارآمد است، زیرا این روش‌ها شامل سری‌های طولانی از توالی بایت‌های تکراری هستند.
محدودیت الفبای اطلاعات
یک راه نسبتا ساده دیگر برای فشرده سازی اطلاعات را می توان محدودیت نامید الفبای اطلاعاتی. بلافاصله متذکر می شویم که در عمل چنین الگوریتمی اجرا نمی شود، اما ارائه این روش به درک بهتر روش کدهای طول متغیر کمک می کند.
در ادامه، منظور ما از الفبای اطلاعاتی مجموعه ای از نمادهای مورد استفاده برای رمزگذاری توالی اطلاعاتی است. به عنوان مثال، فرض کنید یک پیام متنی وجود دارد. هر حرف از این پیام با استفاده از جدول ASCII شامل 256 کاراکتر کدگذاری می شود. در این حالت دقیقاً 8 بیت (1 بایت) برای رمزگذاری هر کاراکتر اختصاص داده می شود. در این مورد، الفبای اطلاعات تمام 256 کاراکتر جدول رمزگذاری ASCII است.
واضح است که تمام 256 کاراکتر جدول ASCII ممکن است در پیام متنی اصلی استفاده نشود. به عنوان مثال، اگر ما در مورد یک پیام متنی به زبان روسی صحبت می کنیم که در آن هیچ عددی وجود ندارد، 64 کاراکتر کافی است (33 حروف کوچک و 31 حرف بزرگ). اگر به این علائم نگارشی، پاراگراف ها و علامت های خط جدید اضافه کنیم، مشخص می شود که تعداد کاراکترها از 100 بیشتر نخواهد شد. در این صورت، می توانید از رمزگذاری نویسه نه 8، بلکه 7 بیتی استفاده کنید که به شما امکان می دهد جدول 128 کاراکتری به این معنی که ما، همانطور که بودیم، الفبای اطلاعاتی را محدود می کنیم، به همین دلیل می توانیم عمق بیت هر کاراکتر جمع آوری شده را کاهش دهیم. می توانید بیشتر بروید - برای تعیین دقیق تعداد کاراکترهای استفاده شده در یک پیام متنی. به عنوان مثال، اگر معلوم شود که فقط 30 کاراکتر در پیام استفاده شده است (شامل کاراکترهای خط جدید)، می توان از یک جدول رمزگذاری 5 بیتی حاوی 32 کاراکتر و سپس نسبت فشرده سازی استفاده کرد. پیام متنیحتی بزرگتر خواهد شد. در واقع، اگر در پیام اصلی از رمزگذاری کاراکتر 8 بیتی و در پیام فشرده شده از رمزگذاری کاراکتر 5 بیتی استفاده شود، نسبت فشرده سازی 8/5 خواهد بود.
با وجود سادگی ظاهری روش محدود کردن الفبا، در عمل از آن استفاده نمی شود. واقعیت این است که روش توصیف شده اجازه رمزگشایی صحیح پیام اصلی را بدون انتقال اطلاعات اضافی نمی دهد. در واقع، بدون دانستن جداول رمزگذاری مورد استفاده برای فشرده سازی اطلاعات، رمزگشایی آن غیرممکن است. یعنی در کنار توالی اطلاعات کدگذاری شده، انتقال جداول رمزگذاری نیز ضروری است. واضح است که در این حالت سود حاصل از استفاده از یک الفبای محدود به صفر می رسد.
روش حروف الفبای محدود معایب دیگری نیز دارد. اگر پیام اطلاعاتی اصلی حاوی تعداد زیادی کاراکتر مختلف باشد، امکان کاهش عمق بیت نمایش کاراکترهای الفبایی وجود نخواهد داشت و این روش به سادگی کار نخواهد کرد. برای مثال، فرض کنید که پیام اصلی حاوی 129 کاراکتر از یک الفبای 256 کاراکتری است. در این مورد نمی توان از رمزگذاری نویسه های 7 بیتی استفاده کرد، زیرا 7 بیت فقط 128 کاراکتر را رمزگذاری می کند. بنابراین، برای 129 کاراکتر، باید از همان رمزگذاری 8 بیتی مانند الفبای 256 کاراکتری اصلی استفاده کنید.
کدهای با طول متغیر
یکی از معایب اصلی روش محدودیت الفبای فرضی که در نظر گرفته‌ایم این است که زمانی از یک کد یکنواخت استفاده می‌کند که تمام کاراکترهای الفبای اطلاعات دارای طول یکسانی (8.7 بیت یا کمتر) باشند. منطقی تر است که از چنین سیستم کدگذاری استفاده کنیم که در آن طول کد کاراکتر به دفعات وقوع آن در پیام اطلاعاتی بستگی دارد. یعنی اگر در پیام اطلاعاتی اصلی، برخی از کاراکترها بیشتر از بقیه اتفاق می‌افتند، بهتر است از کدهای کوتاه استفاده کنند و برای کاراکترهایی که به ندرت اتفاق می‌افتند، از کاراکترهای طولانی‌تر استفاده کنند.
به عنوان یک مثال فرضی، پیام اطلاعاتی زیر را در نظر بگیرید: "سانحه هوایی" که شامل 14 کاراکتر می باشد. فرض کنید الفبای 14 کاراکتری داریم که به ما امکان می دهد این پیام را رمزگذاری کنیم. اگر از یک کد یکنواخت استفاده شود، برای هر کاراکتر الفبا 4 بیت لازم است (طول کد 4 بیتی 16 کاراکتر را تشکیل می دهد). با این حال، به راحتی می توان فهمید که در پیام اطلاعاتی ما نماد "a" پنج بار، نماد "t" - دو بار و بقیه نمادها - یک بار رخ می دهد. اگر برای نماد "a" از کد 2 بیتی، برای نماد "t" - 3 بیت و برای بقیه کاراکترها - 4 بیت استفاده کنیم، مطمئناً می توانیم ذخیره کنیم. فقط لازم است بدانیم که دقیقاً چگونه کدهای با طول متغیر بسازیم و دقیقاً چگونه طول کد باید به فرکانس نماد در پیام اطلاعاتی بستگی داشته باشد.
اگر همه کاراکترها در پیام اطلاعاتی با همان فرکانس(تعادل احتمالی)، سپس با یک الفبای اطلاعاتی از N کاراکتر، هر کاراکتر باید دقیقاً log 2 رمزگذاری شود. نبیت در واقع، این یک مورد از کد یکنواخت است.
اگر احتمال ظاهر شدن کاراکترها در پیام اطلاعاتی متفاوت باشد، طبق نظریه K. Shannon، شخصیتی که احتمال آن برابر با p است، بهینه است و آنچه اهمیت ویژه دارد، از نظر نظری مجاز است یک کد با طول -log 2 مرتبط کنید پ. برگردیم به مثال خود با پیام اطلاعاتی "سانحه هوایی" و با توجه به اینکه احتمال ظاهر شدن کاراکتر "a" (p(a)) 5/14 است، احتمال ظهور کاراکتر "t" 2 است. /14، و احتمال وقوع همه کاراکترهای دیگر 1/14 است، دریافت می کنیم که: برای کاراکتر "a"، طول کد بهینه -log 2 (5/14) = 1.48 بیت است. برای کاراکتر "t" - -log 2 (2/14) = 2.8 بیت، و برای همه کاراکترهای دیگر -log 2 (1/14) = 3.8 است. از آنجایی که در مورد ما طول کد فقط می تواند یک مقدار صحیح داشته باشد، پس با گرد کردن، دریافت می کنیم که برای نماد "a" بهتر است از یک کد 2 بیتی استفاده کنیم، برای نماد "t" - 3. بیت طولانی، و برای بقیه - 4 بیت طول.
بیایید نسبت فشرده سازی را هنگام استفاده از این رمزگذاری محاسبه کنیم. اگر از یک کد یکنواخت مبتنی بر الفبای 14 کاراکتری استفاده شود، برای رمزگذاری کلمه "سانحه هوایی" به 56 بیت نیاز است. هنگام استفاده از کدهای با طول متغیر، 5×2 بیت + 2×3 بیت + 7×4 بیت = 44 بیت مورد نیاز است، یعنی نسبت فشرده سازی 1.27 خواهد بود.
اکنون الگوریتم های بدست آوردن کدهای با طول متغیر را در نظر بگیرید.
رمزگذاری پیشوند
اکثر روش سادهبه دست آوردن کدهایی با طول متغیر به اصطلاح کدگذاری پیشوندی است که به شما امکان می دهد کدهای با طول عدد صحیح را دریافت کنید. ویژگی اصلیکدهای پیشوندی در این واقعیت نهفته است که در هر یک از سیستم های آنها کدهای کوتاه تر با آغاز (پیشوند) کدهای طولانی تر منطبق نیستند. این ویژگی کدهای پیشوندی است که رمزگشایی اطلاعات را بسیار آسان می کند.
اجازه دهید این ویژگی کدهای پیشوندی را توضیح دهیم مثال خاص. اجازه دهید یک سیستم از سه کد پیشوند وجود داشته باشد: (0، 10، 11). همانطور که می بینید، کد کوتاهتر 0 با ابتدای کدهای طولانی تر 10 و 11 منطبق نیست. اجازه دهید کد 0 کاراکتر "a"، کد 10 کاراکتر "m" و کد 11 کاراکتر "p" را مشخص کند. سپس کلمه "frame" توسط دنباله 110100 رمزگذاری می شود. بیایید سعی کنیم این دنباله را رمزگشایی کنیم. از آنجایی که بیت اول 1 است، کاراکتر اول فقط می تواند "m" یا "p" باشد و با مقدار بیت دوم تعیین می شود. از آنجایی که بیت دوم 1 است، کاراکتر اول "p" است. بیت سوم 0 است و به طور منحصر به فردی با کاراکتر "a" مطابقت دارد. بیت چهارم 1 است، یعنی باید به مقدار بیت بعدی نگاه کنید که 0 است، سپس کاراکتر سوم "m" است. بیت آخر 0 است که به طور منحصر به فردی با کاراکتر "a" مطابقت دارد. بنابراین، ویژگی کدهای پیشوند، که شامل این واقعیت است که کدهای کوتاهتر نمی توانند با آغاز کدهای طولانی تر منطبق شوند، رمزگشایی بدون ابهام یک پیام اطلاعاتی رمزگذاری شده با کدهای پیشوندی با طول متغیر را امکان پذیر می کند.
کدهای پیشوند معمولاً با درختان کد ساختمانی (برای سیستم باینری) به دست می آیند. هر گره داخلی چنین درخت باینری دارای دو یال خروجی است و یک یال مربوط به آن است نماد باینری"0" و دیگری - "1". برای قطعیت، می توانیم توافق کنیم که به لبه سمت چپ نماد "0" و لبه سمت راست - نماد "1" اختصاص داده شود.
از آنجایی که هیچ چرخه ای در یک درخت وجود ندارد، همیشه می تواند تنها یک مسیر از گره ریشه به گره برگ وجود داشته باشد. اگر لبه های درخت شماره گذاری شده باشند، هر یک از این مسیرها به دنباله ای باینری منحصر به فرد مربوط می شود. مجموعه تمام این توالی ها سیستمی از کدهای پیشوندی را تشکیل می دهند.
برای مثال در نظر گرفته شده از یک سیستم از سه کد پیشوند: (0، 10، 11)، که نمادهای "a"، "m" و "p" را تعریف می کنند، درخت کد در شکل نشان داده شده است. یکی
برنج. 1. درخت کد برای سیستم
از سه کد پیشوند: (0، 10، 11)
راحتی نمایش درختی کدهای پیشوندی در این واقعیت نهفته است که این ساختار درختی است که امکان تشکیل کدهایی با طول متغیر را فراهم می کند که شرایط اصلی کدهای پیشوند را برآورده می کند، یعنی شرایطی که کدهای کوتاه تر با آنها مطابقت ندارند. آغاز کدهای طولانی تر
تا اینجا ما فقط ایده کدهای پیشوند با طول متغیر را در نظر گرفتیم. در مورد الگوریتم های به دست آوردن کدهای پیشوندی، می توان آنها را بسیار توسعه داد، اما معروف ترین آنها دو روش است: شانون-فانو و هافمن.
الگوریتم شانون-فانو
این الگوریتم برای بدست آوردن کدهای پیشوند به طور مستقل توسط R. Fano و K. Shannon ارائه شده است که به شرح زیر است. در مرحله اول، تمام نمادهای توالی اطلاعات اولیه بر حسب احتمالات نزولی یا افزایشی وقوع آنها (فرکانس های وقوع آنها) مرتب می شوند و پس از آن، مجموعه مرتب شده نمادها در جایی به دو قسمت تقسیم می شوند به طوری که در هر یک از آنها مجموع فرکانس های نماد تقریباً یکسان است. به عنوان نمایش، کلمه آشنا را در نظر بگیرید "سانحه هوایی" .
اگر کاراکترهایی که یک کلمه معین را تشکیل می دهند به ترتیب نزولی تعداد دفعات وقوعشان مرتب شوند، دنباله زیر به دست می آید: (a(5)، m(2)، b(1)، u(1)، k( 1)، c(1)، p(1)، o(1)، f(1)) (در پرانتز تعداد تکرار یک نماد در یک کلمه نشان داده شده است). در مرحله بعد، باید این دنباله را به دو قسمت تقسیم کنیم تا در هر یک از آنها مجموع فرکانس های نماد تقریباً یکسان باشد (تا جایی که ممکن است). واضح است که بخش از بین نمادهای "t" و "c" عبور می کند، در نتیجه دو دنباله تشکیل می شود: (a (5)، t (2)) و (در (1)، u (1). )، k (1)، c(1)، p(1)، o(1)، φ(1)). همچنین مجموع فراوانی های تکرار نمادها در سکانس اول و دوم یکسان و برابر با 7 خواهد بود.
در اولین مرحله از تقسیم یک دنباله از کاراکترها، اولین رقم کد هر کاراکتر را دریافت می کنیم. قانون در اینجا ساده است: برای آن دسته از کاراکترهایی که در دنباله سمت چپ هستند، کد با "0" شروع می شود، و برای کسانی که در سمت راست هستند - با "1".
به طور خاص، دنباله (a(5)، m(2)) به دو کاراکتر جداگانه تقسیم می شود: a(5) و m(2) (هیچ گزینه تقسیم دیگری وجود ندارد). سپس رقم دوم کد برای نماد "a" "0" و برای نماد "t" - "1" است. از آنجایی که در نتیجه تقسیم دنباله ، عناصر جداگانه دریافت کردیم ، آنها دیگر تقسیم نمی شوند و برای کاراکتر "a" کد 00 و برای کاراکتر "t" - کد 01 دریافت می کنیم.
دنباله (in(1)، u(1)، k(1)، c(1)، p(1)، o(1)، f(1)) را می توان به دنباله هایی تقسیم کرد (in(1)، u(1)، k(1)) و (c(1)، p(1)، o(1)، φ(1))، یا در (v(1)، u(1)، k(1) )، (c(1)) و (p(1)، o(1)، φ(1)).
در حالت اول مجموع فرکانس های نمادها در دنباله اول و دوم به ترتیب 3 و 4 و در حالت دوم 4 و 3 خواهد بود. برای قطعیت از گزینه اول استفاده می کنیم.
برای کاراکترهای دنباله جدید حاصل (v(1)، u(1)، k(1)) (این دنباله سمت چپ است)، دو رقم اول کد 10 خواهد بود و برای دنباله (c( 1)، p(1)، o(1)، f(1)) - 11.
در مثال ما (شکل 2 و 3)، سیستم کدهای پیشوند زیر به دست آمده است: "a" - 00، "t" - 01، "c" - 100، "i" - 1010، "k" - 1011، "s" - 1100، "r" - 1101، "o" - 1110، "f" - 1111. همانطور که می بینید، کدهای کوتاهتر آغاز کدهای طولانی تر نیستند، یعنی ویژگی اصلی کدهای پیشوند برآورده شده است. .
برنج. 2. نمایش الگوریتم شانون-فانو
برنج. 3. درخت کد برای کلمه "سانحه هوایی"
در الگوریتم شانون-فانو
الگوریتم هافمن
الگوریتم هافمن الگوریتم دیگری برای به دست آوردن کدهای پیشوند با طول متغیر است. برخلاف الگوریتم شانون-فانو که ساخت را فراهم می کند درخت کداز بالا به پایین، این الگوریتم مستلزم ساخت یک درخت کد به ترتیب معکوس، یعنی از پایین به بالا (از گره های برگ به گره ریشه) است.
در مرحله اول، مانند الگوریتم شانون-فانو، توالی اولیه نمادها به ترتیب نزولی فراوانی تکرار نمادها (عناصر دنباله) مرتب می شوند. برای مثال مورد بحث قبلی با کلمه "سانحه هوایی" دنباله مرتب شده زیر را از عناصر بدست می آوریم: (a(5)، m(2)، b(1)، u(1)، k(1)، c(1)، p(1)، o(1)، f(1)).
بعد، دو عنصر آخر دنباله با عنصر جدید S1 که تکرارپذیری برابر با مجموع تکرارپذیری عناصر اصلی به آن اختصاص داده شده است. سپس مرتب سازی جدیدی از عناصر دنباله مطابق با تکرار آنها انجام می شود. در مورد ما، دو عنصر آخر o(1) و f(1) با عنصر S1(2) جایگزین می شوند، و دنباله مرتب شده جدید به شکل زیر خواهد بود: (a(5)، m(2)، S1( 2)، c(1)، u(1)، k(1)، c(1)، p(1)).
ادامه این روش جایگزینی دو آخرین عناصردنباله به یک عنصر جدید با تکرارپذیری کامل و مرتب سازی مجدد بعدی دنباله مطابق با تکرارپذیری عناصر، به وضعیتی خواهیم رسید که فقط یک عنصر در دنباله باقی می ماند (شکل 4).
برنج. 4. نمایش الگوریتم هافمن
به عنوان مثال کلمه "سانحه هوایی"
همزمان با جایگزینی عناصر و مرتب سازی مجدد توالی، یک درخت باینری کد ساخته می شود. الگوریتم برای ساخت یک درخت بسیار ساده است: عملیات ترکیب (جایگزینی) دو عنصر از یک دنباله، یک عنصر گره جدید در درخت کد ایجاد می کند. یعنی اگر از پایین به بالا به درخت نگاه کنید، لبه‌های درخت کدگذاری همیشه از عناصر جایگزین شده می‌آیند و در یک عنصر گره جدید مطابق با عنصر دنباله به‌دست‌آمده با جایگزینی همگرا می‌شوند (شکل 5). در این حالت، لبه سمت چپ درخت کد را می توان مقدار "0" و لبه سمت راست - "1" اختصاص داد. این مقادیر بعداً به عنوان عناصر کد پیشوند عمل خواهند کرد.
برنج. 5. ساختن درخت کد
در الگوریتم هافمن
(به جای عناصر "o" و "f"
عنصر جدید S1)
درخت کد کامل هافمن برای یک کلمه "سانحه هوایی" نشان داده شده در شکل 6.
برنج. 6. درخت کد کامل کلمه "سانحه هوایی"،
بر اساس الگوریتم هافمن ساخته شده است
با قدم زدن در لبه های درخت کد از بالا به پایین، به راحتی می توان کدهای پیشوندی را برای همه کاراکترهای الفبای اطلاعاتی ما دریافت کرد:
حالا اگر سعی کنید یک کلمه بنویسید "سانحه هوایی" در رمزگذاری هافمن، یک دنباله 41 بیتی دریافت می کنیم 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. جالب است توجه داشته باشید که هنگام استفاده از Shannon-Fano، کدهای پیشوند 1-bit را نیز برای کدهای 4 دریافت می کنیم. کلمه "سانحه هوایی". یعنی در یک مثال خاص، بازده کدگذاری هافمن و شانون فانو یکسان است. اما اگر در نظر بگیریم که الفبای اطلاعات واقعی 256 کاراکتر است (و نه 14، همانطور که در مثال ما وجود دارد)، و توالی اطلاعات واقعی فایل هایی با هر محتوا و طولی هستند، در این صورت این سوال در مورد کد پیشوند بهینه مطرح می شود. ، کدی که به شما امکان می دهد حداقل طول دنباله خروجی را بدست آورید.
می توان ثابت کرد که سیستم کد به دست آمده با استفاده از الگوریتم هافمن در بین همه بهترین است سیستم های ممکنکدهای پیشوندی به این معنا که طول توالی اطلاعات کدگذاری شده حداقل است. یعنی الگوریتم هافمن بهینه است.
نقطه ضعف اصلی الگوریتم هافمن پیچیدگی فرآیند ساخت سیستم کدها است. با این وجود، این الگوریتم بهینه هافمن است که رایج ترین الگوریتم تولید کد با طول متغیر است و در اکثر ابزارهای کاربردی برای فشرده سازی و بایگانی اطلاعات گنجانده شده است.
کدگذاری حسابی
همانطور که قبلاً اشاره کردیم، با توجه به معیار شانون، کد بهینه کدی است که در آن یک کد با طول –log 2 برای هر کاراکتر اختصاص داده شود. پبیت و اگر به عنوان مثال، احتمال یک کاراکتر خاص 0.2 باشد، طول بهینه کد آن -log 2 0.2 = 2.3 بیت خواهد بود. واضح است که کدهای پیشوندی نمی توانند چنین طول کدی را ارائه دهند و بنابراین بهینه نیستند. به طور کلی، طول کد تعیین شده توسط معیار شانون تنها یک حد نظری است. تنها سوال این است که کدام روش رمزگذاری به شما امکان می دهد تا حد امکان به این حد نظری نزدیک شوید. کدهای پیشوند با طول متغیر کارآمد هستند و پیاده‌سازی آنها نسبتاً آسان است، اما روش‌های رمزگذاری کارآمدتر، به‌ویژه الگوریتم کدگذاری حسابی وجود دارد.
ایده رمزگذاری حسابی این است که به جای رمزگذاری کاراکترهای فردی، کد به طور همزمان به کل توالی اطلاعات اختصاص داده می شود. در عین حال، بدیهی است که طول کد به ازای هر کاراکتر منفرد ممکن است یک عدد صحیح نباشد. به همین دلیل است که این روش رمزگذاری بسیار کارآمدتر از رمزگذاری پیشوندی است و با معیار شانون سازگارتر است.
ایده الگوریتم کدگذاری حسابی به شرح زیر است. مانند تمام روش‌های رمزگذاری که قبلاً در نظر گرفته شد، هر نماد از توالی اطلاعات اصلی با احتمال آن مشخص می‌شود. به دنباله بدون کد اصلی یک نیم فاصله اختصاص داده می شود)
