نحوه فشرده سازی داده ها با استفاده از رمزگذاری هافمن: 10 مرحله

فهرست مطالب:

نحوه فشرده سازی داده ها با استفاده از رمزگذاری هافمن: 10 مرحله
نحوه فشرده سازی داده ها با استفاده از رمزگذاری هافمن: 10 مرحله

تصویری: نحوه فشرده سازی داده ها با استفاده از رمزگذاری هافمن: 10 مرحله

تصویری: نحوه فشرده سازی داده ها با استفاده از رمزگذاری هافمن: 10 مرحله
تصویری: سه کاری که زنان آرزو می کنند مردان در رختخواب انجام دهند | حقیقت روانشناسی درروابط زن و مرد 2024, مارس
Anonim

الگوریتم هافمن برای فشرده سازی یا کدگذاری داده ها استفاده می شود. به طور معمول ، هر کاراکتر در یک فایل متنی به عنوان هشت بیت (رقم ، 0 یا 1) ذخیره می شود که با استفاده از کدگذاری به نام ASCII به آن کاراکتر ترسیم می شود. یک فایل رمزگذاری شده توسط هافمن ساختار سخت 8 بیتی را تجزیه می کند به طوری که بیشترین کاراکترهای مورد استفاده فقط در چند بیت ذخیره می شوند ("a" می تواند "10" یا "1000" باشد نه ASCII ، که "01100001" است) بنابراین ، کمترین کاراکترها اغلب بیش از 8 بیت را اشغال می کنند ('z' ممکن است "00100011010" باشد) ، اما چون به ندرت رخ می دهند ، رمزگذاری هافمن به طور کلی یک فایل بسیار کوچکتر از نسخه اصلی ایجاد می کند.

مراحل

قسمت 1 از 2: رمزگذاری

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 1
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 1

مرحله 1. فرکانس هر کاراکتر را در فایل کدگذاری شده بشمارید

برای علامت گذاری انتهای فایل ، یک شخصیت ساختگی را وارد کنید - این بعداً مهم خواهد بود. در حال حاضر ، آن را EOF (انتهای فایل) بنامید و آن را با فرکانس 1 علامت گذاری کنید.

به عنوان مثال ، اگر می خواهید یک فایل متنی را با عنوان "ab ab cab" رمزگذاری کنید ، باید "a" با فرکانس 3 ، "b" با فرکانس 3 ، "(فاصله) با فرکانس 2 ،" c "با فرکانس 1 داشته باشید. ، و EOF با فرکانس 1

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 2
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 2

مرحله 2. نویسه ها را به عنوان گره درخت ذخیره کنید و آنها را در صف اولویت قرار دهید

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

  • یک درخت دودویی یک فرمت داده است که در آن هر قطعه داده یک گره است که می تواند حداکثر یک والد و دو فرزند داشته باشد. اغلب به عنوان درخت شاخه ای کشیده می شود ، از این رو نام آن را گرفته اند.
  • صف مجموعه ای از داده های مناسب است که در آن اولین چیزی که وارد صف می شود نیز اولین چیزی است که ظاهر می شود (مانند انتظار در صف). در صف اولویت ، داده ها به ترتیب اولویت ذخیره می شوند ، به طوری که اولین چیزی که ظاهر می شود فوری ترین چیز است ، چیزی که دارای کوچکترین اولویت است ، و نه اولین چیزی که به آن اضافه می شود.
  • در مثال "ab ab cab" ، صف اولویت شما به این شکل است: {'c': 1 ، EOF: 1 ، '': 2 ، 'a': 3 ، 'b': 3}
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 3
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 3

مرحله 3. شروع به ساختن درخت خود کنید

دو مورد ضروری را از صف اولویت حذف (یا حذف کنید). یک گره درختی جدید ایجاد کنید تا والدین این دو گره باشند و گره اول را به عنوان فرزند چپ و دومین را به عنوان فرزند راست ذخیره کنید. اولویت گره جدید باید مجموع اولویت های فرزند آن باشد. سپس این گره جدید را در صف اولویت قرار دهید.

صف اولویت اکنون به این شکل است: {'': 2 ، گره جدید: 2 ، 'a': 3 ، 'b': 3}

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 4
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 4

مرحله 4. ساخت درخت خود را به پایان برسانید:

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

  • پس از اتمام کار ، آخرین گره در صف ، ریشه درخت رمزگذاری خواهد بود ، و همه گره های دیگر از آن منشعب می شوند.
  • بیشترین کاراکترها نزدیکترین برگها به بالای درخت است ، در حالی که نویسه هایی که به ندرت مورد استفاده قرار می گیرند در انتهای درخت و دورتر از ریشه قرار می گیرند.
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 5
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 5

مرحله 5. ایجاد نقشه رمزگذاری. از طریق درخت عبور کنید تا به هر شخصیت برسید. هر بار که از فرزند سمت چپ گره دیدن می کنید ، این یک "0" است. هر بار که از فرزند راست گره دیدن می کنید ، این یک "1" است. هنگامی که به یک کاراکتر رسیدید ، شخصیت را با دنباله 0s و 1s که برای رسیدن به آنجا لازم بود ذخیره کنید. این دنباله همان چیزی است که کاراکتر در فایل فشرده کدگذاری می شود. شخصیت ها و دنباله های آنها را در نقشه ذخیره کنید.

  • به عنوان مثال ، از ریشه شروع کنید. از فرزند سمت چپ ریشه دیدن کنید ، و سپس از فرزند چپ آن گره دیدن کنید. از آنجا که گره ای که اکنون در آن هستید هیچ فرزندی ندارد ، به یک شخصیت رسیده اید. این هست ' '. از آنجا که برای رسیدن به اینجا دوبار از چپ پیاده روی کرده اید ، رمزگذاری '' "00" است.
  • برای این درخت ، نقشه به این شکل است: {'': "00" ، "a": "10" ، "b": "11" ، "c": "010" ، EOF: "011"}.
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 6
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 6

مرحله 6. در فایل خروجی ، نقشه کدگذاری را به عنوان هدر قرار دهید

با این کار می توانید فایل را رمزگشایی کنید.

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 7
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 7

مرحله 7. فایل را رمزگذاری کنید

برای هر یک از کاراکترهای پرونده که باید کد گذاری شود ، دنباله ای دودویی که در نقشه ذخیره کرده اید بنویسید. پس از اتمام رمزگذاری فایل ، مطمئن شوید که EOF را به انتها اضافه می کنید.

  • برای فایل "ab ab cab" ، فایل کد شده به این شکل است: "1011001011000101011011".
  • فایلها بصورت بایت (8 بیت یا 8 رقم باینری) ذخیره می شوند. از آنجا که الگوریتم رمزگذاری هافمن از فرمت 8 بیتی استفاده نمی کند ، فایلهای کد شده اغلب دارای طولهایی چند برابر 8 نخواهند بود. ارقام باقی مانده با 0s پر می شوند. در این حالت ، دو عدد 0 در انتهای فایل اضافه می شود که شبیه فضای دیگری است. این می تواند یک مشکل باشد: چگونه رمزگشایی می داند که چه موقع خواندن را متوقف کند؟ با این حال ، از آنجا که ما یک کاراکتر پایان پرونده را در نظر گرفتیم ، رمزگشایی به این حالت می رسد و سپس متوقف می شود و از موارد دیگری که پس از آن اضافه شده است چشم پوشی می کند.

قسمت 2 از 2: رمزگشایی

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 8
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 8

مرحله 1. در یک فایل رمزگذاری شده توسط هافمن بخوانید

ابتدا ، سربرگ را بخوانید ، که باید نقشه رمزگذاری باشد. از این روش برای ساختن یک درخت رمزگشایی به همان روشی که درختی را که برای کدگذاری فایل استفاده می کردید بسازید. این دو درخت باید یکسان باشند.

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 9
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 9

مرحله 2. دودویی را یک رقمی در یک زمان بخوانید

هنگام خواندن درخت ، از آن عبور کنید: اگر "0" را می خوانید ، به فرزند سمت چپ گره ای که در آن هستید بروید ، و اگر در "1" می خوانید ، به سمت کودک راست بروید. وقتی به یک برگ (گره بدون فرزند) می رسید ، به یک شخصیت رسیده اید. کاراکتر را در فایل رمزگشایی شده بنویسید.

به دلیل نحوه ذخیره سازی کاراکترها در درخت ، کدهای هر کاراکتر دارای ویژگی پیشوند هستند ، به طوری که رمزگذاری باینری هیچ کاراکتری هرگز نمی تواند در ابتدای کدگذاری شخصیت دیگری رخ دهد. رمزگذاری برای هر شخصیت کاملاً منحصر به فرد است. این امر رمزگشایی را بسیار ساده تر می کند

فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 10
فشرده سازی داده ها با استفاده از رمزگذاری هافمن مرحله 10

مرحله 3. این کار را تکرار کنید تا به EOF برسید

تبریک می گویم! شما فایل را رمزگشایی کرده اید.

توصیه شده: