کدگذاری/فشرده‌سازی - روش 827
جوان‌تر که بودم، یکی از دوستانم مسئله‌ای را مطرح کرد با این عنوان که چگونه می‌توان 8 کاراکتر را در 7 بایت ذخیره کرد؟ یادم نیست آن موقع چگونه مسئله را حل کردم اما چندین سال بعد به فکر توسعه و کار جدی بر روی آن افتادم که نتیجه را در این مطلب برایتان آورده‌ام.
اگر نگاهی به جدول کدهای ASCII بیاندازید، می‌بینید که همه‌ی ارقام، حروف انگلیسی (هم کوچک و هم بزرگ)، علایم نشانه گذاری نظیر نقطه، پارانتز و... در کدهای کمتر از 128 جا دارند یعنی مقدار کد ASCII همه‌ی آنها کمتر از 27 = 128 است و می‌توان حداکثر در 7 بیت آنها را نمایش داد. این کاراکترها را کاراکترهای اصلی (یا استاندارد) می‌نامیم. یک متن به زبان انگلیسی از کاراکترهای اصلی تشکیل می‌شود. هرچند ممکن است در عمل از برخی کاراکترهای خاص نیز استفاده کنیم، اما اغلب متون (ادبی، علمی و...) به کاراکترهای اصلی محدود است. در زیر، جدول کدهای ASCII برای کاراکترهای اصلی آمده است:
| کد ASCII | کاراکتر | معادل باینری | کد ASCII | کاراکتر | معادل باینری | |
| 32 | Space | 00100000 | 80 | P | 01010000 | |
| 33 | ! | 00100001 | 81 | Q | 01010001 | |
| 34 | " | 00100010 | 82 | R | 01010010 | |
| 35 | # | 00100011 | 83 | S | 01010011 | |
| 36 | $ | 00100100 | 84 | T | 01010100 | |
| 37 | % | 00100101 | 85 | U | 01010101 | |
| 38 | & | 00100110 | 86 | V | 01010110 | |
| 39 | ' | 00100111 | 87 | W | 01010111 | |
| 40 | ( | 00101000 | 88 | X | 01011000 | |
| 41 | ) | 00101001 | 89 | Y | 01011001 | |
| 42 | * | 00101010 | 90 | Z | 01011010 | |
| 43 | + | 00101011 | 91 | [ | 01011011 | |
| 44 | , | 00101100 | 92 | \ | 01011100 | |
| 45 | - | 00101101 | 93 | ] | 01011101 | |
| 46 | . | 00101110 | 94 | ^ | 01011110 | |
| 47 | / | 00101111 | 95 | _ | 01011111 | |
| 48 | 0 | 00110000 | 96 | ` | 01100000 | |
| 49 | 1 | 00110001 | 97 | a | 01100001 | |
| 50 | 2 | 00110010 | 98 | b | 01100010 | |
| 51 | 3 | 00110011 | 99 | c | 01100011 | |
| 52 | 4 | 00110100 | 100 | d | 01100100 | |
| 53 | 5 | 00110101 | 101 | e | 01100101 | |
| 54 | 6 | 00110110 | 102 | f | 01100110 | |
| 55 | 7 | 00110111 | 103 | g | 01100111 | |
| 56 | 8 | 00111000 | 104 | h | 01101000 | |
| 57 | 9 | 00111001 | 105 | i | 01101001 | |
| 58 | : | 00111010 | 106 | j | 01101010 | |
| 59 | ; | 00111011 | 107 | k | 01101011 | |
| 60 | < | 00111100 | 108 | l | 01101100 | |
| 61 | = | 00111101 | 109 | m | 01101101 | |
| 62 | > | 00111110 | 110 | n | 01101110 | |
| 63 | ? | 00111111 | 111 | o | 01101111 | |
| 64 | @ | 01000000 | 112 | p | 01110000 | |
| 65 | A | 01000001 | 113 | q | 01110001 | |
| 66 | B | 01000010 | 114 | r | 01110010 | |
| 67 | C | 01000011 | 115 | s | 01110011 | |
| 68 | D | 01000100 | 116 | t | 01110100 | |
| 69 | E | 01000101 | 117 | u | 01110101 | |
| 70 | F | 01000110 | 118 | v | 01110110 | |
| 71 | G | 01000111 | 119 | w | 01110111 | |
| 72 | H | 01001000 | 120 | x | 01111000 | |
| 73 | I | 01001001 | 121 | y | 01111001 | |
| 74 | J | 01001010 | 122 | z | 01111010 | |
| 75 | K | 01001011 | 123 | { | 01111011 | |
| 76 | L | 01001100 | 124 | | | 01111100 | |
| 77 | M | 01001101 | 125 | } | 01111101 | |
| 78 | N | 01001110 | 126 | ~ | 01111110 | |
| 79 | O | 01001111 | 127 | | 01111111 |
می‌دانیم که اعداد کمتر از 27 در مبنای 2 حداکثر از 7 بیت تشکیل شده‌اند. بزرگترین عدد 7 بیتی 127 است که در مبنای 2 همه‌ی 7 بیت آن برابر یک است، یعنی:
(127)10 = (1111111)2
از آن‌جایی‌که هر بایت از 8 بیت تشکیل شده، و نیز هر کاراکتر ASCII در یک بایت ذخیره می‌شود، اما همان‌طور که در جدول بالا ملاحظه می‌کنید در کاراکترهای اصلی بیت هشتم همواره برابر صفر است. بیایید با یک مثال پیش برویم. فرض کنید می‌خواهیم کلمه‌ی SRefagat را ذخیره کنیم. طول این کلمه 8 کاراکتر است پس در 8 بایت ذخیره می‌شود:
| کاراکتر | بیت 7 | بیت 6 | بیت 5 | بیت 4 | بیت 3 | بیت 2 | بیت 1 | بیت 0 | کد ASCII | شماره‌ی بایت |
| S | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 83 | 1 |
| R | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 82 | 2 |
| e | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 101 | 3 |
| f | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 102 | 4 |
| a | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 97 | 5 |
| g | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 103 | 6 |
| a | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 97 | 7 |
| t | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 116 | 8 |
جدول بالا وضعیت بیت‌های فضای ذخیره‌ی هریک از کاراکترها را نشان می‌دهد. هر ردیف (سطر) از جدول بالا نماینده‌ی یک بایت است و ستون‌های بیت0، بیت 1، ... و بیت 7 مقدار کاراکتر ذخیره شده را درمبنای 2 نشان می‌دهند (هر خانه یک بیت را نشان می‌دهد). برای بررسی بیشتر، بیایید جدول را کمی تغییر دهیم:
| S7 | S6 | S5 | S4 | S3 | S2 | S1 | S0 | 1 |
| R7 | R6 | R5 | R4 | R3 | R2 | R1 | R0 | 2 |
| e7 | e6 | e5 | e4 | e3 | e2 | e1 | e0 | 3 |
| f7 | f6 | f5 | f4 | f3 | f2 | f1 | f0 | 4 |
| a7 | a6 | a5 | a4 | a3 | a2 | a1 | a0 | 5 |
| g7 | g6 | g5 | g4 | g3 | g2 | g1 | g0 | 6 |
| a7 | a6 | a5 | a4 | a3 | a2 | a1 | a0 | 7 |
| t7 | t6 | t5 | t4 | t3 | t2 | t1 | t0 | 8 |
داده‌های اضافی در جدول بالا حذف شده است. خانه‌ی اول (از سمت راست) شماره‌ی بایت را نشان می‌دهد. در 8 خانه‌ی بعدی که از 0 تا 7 شماره‌گذاری شده‌اند، 8 بیت متناظر آن بایت قرار دارد. محتوای بیت‌ها نشان‌دهنده‌ی هر بیت کاراکتر ذخیره شده در آن بایت است. به‌عنوان مثال در بایت اول، S0 نشان‌دهنده‌ی بیت اول حرف S (سمت راست‌ترین بیت)، S1 بیت دوم حرف S، ... و S7 بیت هشتم حرف S است. گفتیم که بیت‌های هشتم (بیت شماره‌ی 7) برای کاراکترهای اصلی برابر صفر است. پس داریم:
| 0 | S6 | S5 | S4 | S3 | S2 | S1 | S0 | 1 |
| 0 | R6 | R5 | R4 | R3 | R2 | R1 | R0 | 2 |
| 0 | e6 | e5 | e4 | e3 | e2 | e1 | e0 | 3 |
| 0 | f6 | f5 | f4 | f3 | f2 | f1 | f0 | 4 |
| 0 | a6 | a5 | a4 | a3 | a2 | a1 | a0 | 5 |
| 0 | g6 | g5 | g4 | g3 | g2 | g1 | g0 | 6 |
| 0 | a6 | a5 | a4 | a3 | a2 | a1 | a0 | 7 |
| 0 | t6 | t5 | t4 | t3 | t2 | t1 | t0 | 8 |
پس تا اینجای کار، نتیجه می‌گیریم که از هریک از کاراکترهای اصلی، 7 بیت دارای مقدار است لذا از بیت هشتم که همواره مقدار صفر دارد، استفاده‌ای نمی شود. 7 کاراکتر اول، هرکدام یک بیت اضافی دارند لذا کاراکتر هشتم را (که آن هم فقط 7 بیت دارد) را می‌توان در آن‌جا جای داد. به شکل زیر توجه کنید:
| t0 | S6 | S5 | S4 | S3 | S2 | S1 | S0 | 1 |
| t1 | R6 | R5 | R4 | R3 | R2 | R1 | R0 | 2 |
| t2 | e6 | e5 | e4 | e3 | e2 | e1 | e0 | 3 |
| t3 | f6 | f5 | f4 | f3 | f2 | f1 | f0 | 4 |
| t4 | a6 | a5 | a4 | a3 | a2 | a1 | a0 | 5 |
| t5 | g6 | g5 | g4 | g3 | g2 | g1 | g0 | 6 |
| t6 | a6 | a5 | a4 | a3 | a2 | a1 | a0 | 7 |
این جدول نشان‌دهنده‌ی وضعیت بیت‌های 7 بایت از حافظه است که ما 8 کاراکتر را در آن به شکل خاصی ذخیره کرده‌ایم. هر ردیف هنوز هم 8 بیتی است و اگر کد معادل ASCII هر سطر را بازیابی کنیم، هریک از ردیف‌ها ممکن است مبنای ده‌دهی جدیدی را نمایش دهند. برای مثال خاصی که بر روی آن کار می‌کنیم (ذخیره‌ی کلمه‌ی SRefagat) داریم:
| کاراکتر | بیت 7 | بیت 6 | بیت 5 | بیت 4 | بیت 3 | بیت 2 | بیت 1 | بیت 0 | کد ASCII | شماره‌ی بایت |
| S | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 83 | 1 |
| R | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 82 | 2 |
| å | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 229 | 3 |
| f | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 102 | 4 |
| á | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 225 | 5 |
| æ | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 230 | 6 |
| á | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 225 | 7 |
همان‌طور که در جدول قابل مشاهده است، بدلیل ظاهر شدن رقم 1 (به‌جای صفر) در بیت باارزش (بیت هشتم)، در ردیف‌های 3، 5، 6 و 7 معادل ده‌دهی آنها تغییر یافته‌است. این مقادیر جدید هنوز جزو کدهای ASCII هستند، لکن بدلیل اضافه شدن یک بیت باارزش به آنها، از محدوده‌ی کاراکترهای اصلی خارج شده و به کدهای بالای 127 (تا 255) تغییر یافته‌اند.
کدهای ASCII محدوده‌ی 128 تا 255 به‌کاراکترهای فرعی (یا تعمیم یافته) اختصاص دارند و شامل علائم جدول‌کشی، نمادهای ریاضی، الفبای اضافی سایر زبان‌های خانواده‌ی لاتین و کاراکترهای خاص می‌شود.
اگرکلمات SRefagat و SRåfáæá را در فایل‌های متنی جداگانه‌ای ذخیره کنیم، فایل اول 8 بایت فضا بر روی دیسک اشغال می‌کند، درحالی‌که فایل دوم 7 بایت فضا اشغال می‌کند. اما مشکل فایل دوم این‌است که محتوی آن قابل خواندن نیست و نسبت به متن اصلی دچار دگرگونی و به‌هم ریختگی شده‌است. برای رفع این مشکل، پسوند فایل‌هایی که محتوای آن به این شکل به‌هم ریخته را به یک عبارت جدید (مثلا 827) عوض کرده و یک ویرایشگر جدید متنی طراحی می‌کنیم که در محیط ویندوز بتوانیم متن اصلی آنها را بازیابی کنیم.
پروژه‌ی برنامه‌نویسی ویرایشگر متون فشرده‌ی 827 یک ویرایشگر متنی برای کار با فایل‌های 827 ارائه می‌دهد. پیشنهاد می‌شود برای بهره‌مندی بیشتر، به آن رجوع کنید.
کم شدن 1 بایت از هر 8 بایت، در مجموع 12.5% صرفه‌جویی به‌همراه دارد و این روش که نام آن‌را از این به بعد «روش کدگذاری و فشرده‌سازی 827» می‌گذاریم، با نرخ ثابت 12.5% و بدون توجه به آرایش حروف و فراوانی کاراکترها، یکی از ساده‌ترین الگوریتم‌های فشرده‌سازی متن می‌باشد. در این روش، متن به بلوک‌های 8 حرفی تقسیم شده و هر بلوک در 7 بایت فشرده می‌شود. بسیاری از روش‌های کدگذاری و فشرده‌سازی متون مانند روش کدگذاری هافمن بر اساس جدول فراوانی حروف یک متن عمل می‌کنند و کدگذاری به‌صورت حرف به حرف انجام می‌گیرد.
تگ ها
- پیشنهادی
- تازهها
- ویژهنامه
