ویرگول
ورودثبت نام
امیررضا ریاحی
امیررضا ریاحی
خواندن ۳ دقیقه·۳ سال پیش

prefix code چیست؟

کد پیشوندی نوعی کد است که در آن هیچ کلمه‌ای، پیشوند کلمه دیگری نباشد. اما این یعنی چه؟

کدگذاری چیست؟

چیز خاصی نیست، صرفا یعنی تبدیل یک الفبا به الفایی دیگر. این الفبا لزوما از حروف تشکیل نشده‌اند. می‌توانند بایت یا کلمه باشند. تعریف دقیق‌تر را از قول ویکی‌پدیا نقل می‌کنم:

کُد (به انگلیسی: Code) دستورالعمل تبدیل اطلاعات از یک قالب به قالبی دیگر است. به فرایند انجام این کار کدگذاری (Encoding) و عکس این عمل کدبرداری (Decoding) گفته می‌شود. کدگذاری عبارت است از تبدیل اسم یا یک موضوع به یک علامت قراردادی. این علامت می‌تواند به صورت شماره یا حرف انتخاب شده باشد. کد به منزلۀ علامت اختصاری طبقه‌بندی نیز محسوب می‌شود.

مثال‌های ساده‌ای می‌توان از کد نشان داد. مثلا فرض کنید هر حرف از حروف الفبا را به شماره ردیف آن حرف در حروف الفبا نظیر کنیم. یعنی:

خروجی کدگذاری کلمه سلام بر اساس این قاعده می‌شود:

{15,27,1,28}

یک مثال پرکاربردتر کد، کد مورس است. که جدول آن به شکل زیر است:


حالا کد پیشوندی چیست؟

به کدی که هیچ‌کدام از حروفش، پیشوند حرف دیگرش نباشد، کد پیشوندی گفته می‌شوند. مثال:

{1,2,3,4,5}

آیا در این ۵ حرف، هیچکدام پیشوند دیگری هست؟ خیر! پس این حروف قاعده را رعایت کردند. اما واضح است که این مثال خیلی راهگشا نیست. باید مثال بهتری زد:

{1,11,12,2,3}

آیا این این ۵ کلمه، پیشوند یکدیگر هستند؟ بله! حرف «۱» پیشوند «۱۱» و «۱۲» است. یعنی اولین کاراکتر «۱۲» می‌شود «۱». پس قاعده را رعایت نمی‌کند.

بدیهی است که برای کلمه‌های تک حرفی همیشه این قاعده بر قرار است. چون هیچ حرفی پیشوند حرف دیگری نیست. اما همان‌طور که در مثال بالا دیدید، وقتی حروف چند حرفی می‌شوند ممکن است این قاعده برقرار نباشد. مثال زیر با کلمه‌های چند حرفی است که قاعده را رعایت کرده:

{11,41,2,42,34}

هیچ‌کدام از کلمات بالا پیشوند دیگری نیستند.

خب که چه؟

این مسئله وقتی اهمیت پیدا می‌کند که ما می‌خواهیم داده‌ای را منتقل کنیم. در واقع وقتی می‌خواهیم رشته‌ای از اطلاعات را به وسیله این کلمات منتقل کنیم. فرض کنید کد ما از این قاعده پیروی نکنند. مثلا همان کد که در مثال دوم دیدیم را در نظر بگیرید:

{1,11,12,2,3}

فرض کنید بخواهیم رشته‌ای از اطلاعات را با استفاده از این کلمات بسازیم و منتقل کنیم، این رشته فرضا رشته زیر است:

11-12-2-3-1

واضح است که انتقال اطلاعات به شکلی که بالا نشان دادیم به صرفه نیست. چون به ازا هر کلمه، باید یک حرف جدا کننده استفاده کنیم. و این یعنی حجم داده‌ای که باید منتقل شود خیلی افزایش پیدا می‌کند. پس سعی می‌کنیم بدون حرف جداکننده رشته را منتقل کنیم. خروجی چنین خواهد شد:

1112231

حال فرض کنید گیرنده پیام این پیام را دریافت می‌کند. چطور باید این رشته را به کلمات سازنده‌اش تجزیه کند؟

با توجه به کلماتی که داریم، چندین حالت ممکن است:

1-1-1-2-2-3-1 1-11-2-2-3-1 1-1-12-2-3-1 11-12-2-3-1

همانطور که نظاره می‌کنید، تا الان توانستیم ۴ حالت مختلف این رشته را تجزیه کنیم و فقط حالت آخری چیزی بود که مدنظر فرستنده است. ممکن است حالت‌های دیگری‌هم باشد، اما مهم نیست. مهم این بود که بجز حالت صحیح، حالت‌های اشتباه دیگری‌هم برای تفسیر ممکن هستند.

پس مشاهده کردیم که بدون استفاده از حروف جداکننده نمی‌توان داده را منتقل کرد طوری که گیرنده دقیقا به همان چیزی که مدنظر فرستنده است برسد. همچنین استفاده از حروف جداکننده به ازا هر کلمه به شدت حجم داده نهایی را بالا می‌برد و به صرفه نیست. به طور مثال در حالت اول (با حروف جداکننده) رشته ما ۱۱ حرفی است. اما بدون این حروف، رشته ما ۷ حرفی است. این اختلاف، در حجم زیاد داده، بیشتر بروز پیدا می‌کند.

چه خاکی؟

یک راه‌حل اینجا استفاده از کد از نوع پیشوندی است. کد‌هایی که این قاعده را رعایت می‌کنند، از این خطا مصونیت دارند. به بیان دیگر، ممکن نیست هیچ رشته‌ای از کلماتی که از این قاعده پیروی می‌کنند را به دو طریق تفسیر کرد. و این یعنی می‌توانیم کلمات را بدون حروف جداکننده ارسال کنیم.

بیایید همین کار را با سومین مثالی که زدیم تکرار کنیم:

{11,41,2,42,34}

حال رشته‌ای از این کلمات می‌سازیم، مثلا:

414223441

می‌توان مطمئن بود تنها راه تجزیه این رشته به کلمات سازنده‌اش، به شیوه زیر است:

41-42-2-34-41

البته بدیهی است که من اثبات نکردم تنها راه تجزیه این رشته همین حالت بالاست. اما با اندکی دست به قلم بردن و کاغذ سیاه کردن می‌توانید خودتان اثبات کنید که تنها راه تجزیه همین است. به علاوه، اگر حجم بیشتری کاغذ سیاه کنید می‌توانید این قاعده را برای تمام کدهای پیشوندی اثبات کنید.

این نوع کد را کد پیشوندی یا prefix code می‌نامند. البته که ترجمه فارسی‌اش را مطمئن نیستم.

در این لینک‌ هم همین مطلب خیلی ساده و سر راست توضیح داده شده.





نظریه اطلاعات
شاید از این پست‌ها خوشتان بیاید