پایگاه دانش علوم کامپیوتر و مهندسی نرم‌افزار - sref.ir

مسئله‌های چالشی برنامه‌نویسی، داده‌ساختارها و الگوریتم‌ها

پل‌های ارتباطی

کدگذاری/فشرده‌سازی - روش 827

جوان‌تر که بودم، یکی از دوستانم مسئله‌ای را مطرح کرد با این عنوان که چگونه می‌توان 8 کاراکتر را در 7 بایت ذخیره کرد؟ یادم نیست آن موقع چگونه مسئله را حل کردم اما چندین سال بعد به فکر توسعه و کار جدی بر روی آن افتادم که نتیجه را در این مطلب برایتان آورده‌ام.

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

کد ASCII کاراکتر معادل باینری   کد ASCII کاراکتر معادل باینری
32Space00100000  80P01010000
33!00100001  81Q01010001
34"00100010  82R01010010
35#00100011  83S01010011
36$00100100  84T01010100
37%00100101  85U01010101
38&00100110  86V01010110
39'00100111  87W01010111
40(00101000  88X01011000
41)00101001  89Y01011001
42*00101010  90Z01011010
43+00101011  91[01011011
44,00101100  92\01011100
45-00101101  93]01011101
46.00101110  94^01011110
47/00101111  95_01011111
48000110000  96`01100000
49100110001  97a01100001
50200110010  98b01100010
51300110011  99c01100011
52400110100 100d01100100
53500110101 101e01100101
54600110110 102f01100110
55700110111 103g01100111
56800111000 104h01101000
57900111001 105i01101001
58:00111010 106j01101010
59;00111011 107k01101011
60<00111100 108l01101100
61=00111101 109m01101101
62>00111110 110n01101110
63?00111111 111o01101111
64@01000000 112p01110000
65A01000001 113q01110001
66B01000010 114r01110010
67C01000011 115s01110011
68D01000100 116t01110100
69E01000101 117u01110101
70F01000110 118v01110110
71G01000111 119w01110111
72H01001000 120x01111000
73I01001001 121y01111001
74J01001010 122z01111010
75K01001011 123{01111011
76L01001100 124|01111100
77M01001101 125}01111101
78N01001110 126~01111110
79O01001111 12701111111
جدول کدهای ASCII برای کاراکترهای قابل چاپ (محدوده‌ی 32 تا 127)

می‌دانیم که اعداد کمتر از 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 شماره‌ی بایت
S01010011 831
R01010010 822
e011001011013
f011001101024
a01100001 975
g011001101036
a01100001 977
t011101001168
وضعیت بیت‌های هر 8 بایت برای ذخیره‌ی کلمه‌ی SRefagat

جدول بالا وضعیت بیت‌های فضای ذخیره‌ی هریک از کاراکترها را نشان می‌دهد. هر ردیف (سطر) از جدول بالا نماینده‌ی یک بایت است و ستون‌های بیت0، بیت 1، ... و بیت 7 مقدار کاراکتر ذخیره شده را درمبنای 2 نشان می‌دهند (هر خانه یک بیت را نشان می‌دهد). برای بررسی بیشتر، بیایید جدول را کمی تغییر دهیم:

S7S6S5S4S3S2S1S01
R7R6R5R4R3R2R1R02
e7e6e5e4e3e2e1e03
f7f6f5f4f3f2f1f04
a7a6a5a4a3a2a1a05
g7g6g5g4g3g2g1g06
a7a6a5a4a3a2a1a07
t7t6t5t4t3t2t1t08

داده‌های اضافی در جدول بالا حذف شده است. خانه‌ی اول (از سمت راست) شماره‌ی بایت را نشان می‌دهد. در 8 خانه‌ی بعدی که از 0 تا 7 شماره‌گذاری شده‌اند، 8 بیت متناظر آن بایت قرار دارد. محتوای بیت‌ها نشان‌دهنده‌ی هر بیت کاراکتر ذخیره شده در آن بایت است. به‌عنوان مثال در بایت اول، S0 نشان‌دهنده‌ی بیت اول حرف S (سمت راست‌ترین بیت)، S1 بیت دوم حرف S، ... و S7 بیت هشتم حرف S است. گفتیم که بیت‌های هشتم (بیت شماره‌ی 7) برای کاراکترهای اصلی برابر صفر است. پس داریم:

0S6S5S4S3S2S1S01
0R6R5R4R3R2R1R02
0e6e5e4e3e2e1e03
0f6f5f4f3f2f1f04
0a6a5a4a3a2a1a05
0g6g5g4g3g2g1g06
0a6a5a4a3a2a1a07
0t6t5t4t3t2t1t08

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

t0S6S5S4S3S2S1S01
t1R6R5R4R3R2R1R02
t2e6e5e4e3e2e1e03
t3f6f5f4f3f2f1f04
t4a6a5a4a3a2a1a05
t5g6g5g4g3g2g1g06
t6a6a5a4a3a2a1a07

این جدول نشان‌دهنده‌ی وضعیت بیت‌های 7 بایت از حافظه است که ما 8 کاراکتر را در آن به شکل خاصی ذخیره کرده‌ایم. هر ردیف هنوز هم 8 بیتی است و اگر کد معادل ASCII هر سطر را بازیابی کنیم، هریک از ردیف‌ها ممکن است مبنای ده‌دهی جدیدی را نمایش دهند. برای مثال خاصی که بر روی آن کار می‌کنیم (ذخیره‌ی کلمه‌ی SRefagat) داریم:

کاراکتر بیت 7 بیت 6 بیت 5 بیت 4 بیت 3 بیت 2 بیت 1 بیت 0 کد ASCII شماره‌ی بایت
S01010011 831
R01010010 822
å111001012293
f011001101024
á111000012255
æ111001102306
á111000012257
وضعیت بیت‌ها بعد از دست‌کاری‌های اخیر

همان‌طور که در جدول قابل مشاهده است، بدلیل ظاهر شدن رقم 1 (به‌جای صفر) در بیت باارزش (بیت هشتم)، در ردیف‌های 3، 5، 6 و 7 معادل ده‌دهی آن‌ها تغییر یافته‌است. این مقادیر جدید هنوز جزو کدهای ASCII هستند، لکن بدلیل اضافه شدن یک بیت باارزش به آن‌ها، از محدوده‌ی کاراکترهای اصلی خارج شده و به کدهای بالای 127 (تا 255) تغییر یافته‌اند.

کدهای ASCII محدوده‌ی 128 تا 255 به‌کاراکترهای فرعی (یا تعمیم یافته) اختصاص دارند و شامل علائم جدول‌کشی، نمادهای ریاضی، الفبای اضافی سایر زبان‌های خانواده‌ی لاتین و کاراکترهای خاص می‌شود.

اگرکلمات SRefagat و SRåfáæá را در فایل‌های متنی جداگانه‌ای ذخیره کنیم، فایل اول 8 بایت فضا بر روی دیسک اشغال می‌کند، درحالی‌که فایل دوم 7 بایت فضا اشغال می‌کند. اما مشکل فایل دوم این‌است که محتوی آن قابل خواندن نیست و نسبت به متن اصلی دچار دگرگونی و به‌هم ریختگی شده‌است. برای رفع این مشکل، پسوند فایل‌هایی که محتوای آن به این شکل به‌هم ریخته را به یک عبارت جدید (مثلا 827) عوض کرده و یک ویرایشگر جدید متنی طراحی می‌کنیم که در محیط ویندوز بتوانیم متن اصلی آن‌ها را بازیابی کنیم.

کم شدن 1 بایت از هر 8 بایت، در مجموع 12.5% صرفه‌جویی به‌همراه دارد و این روش که نام آن‌را از این به بعد «روش کدگذاری و فشرده‌سازی 827» می‌گذاریم، با نرخ ثابت 12.5% و بدون توجه به آرایش حروف و فراوانی کاراکترها، یکی از ساده‌ترین الگوریتم‌های فشرده‌سازی متن می‌باشد. در این روش، متن به بلوک‌های 8 حرفی تقسیم شده و هر بلوک در 7 بایت فشرده می‌شود. بسیاری از روش‌های کدگذاری و فشرده‌سازی متون مانند روش کدگذاری هافمن بر اساس جدول فراوانی حروف یک متن عمل می‌کنند و کدگذاری به‌صورت حرف به حرف انجام می‌گیرد.

    تگ ها