هافمن کد: برنامه نمونه

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

الگوریتم تاریخچه

اولین الگوریتم برنامه نویسی کارآمد از اطلاعات الکترونیکی تبدیل شده است کد هافمن پیشنهاد به عنوان اوایل اواسط قرن بیستم، یعنی در سال 1952. او بود که در حال حاضر عنصر پایه اکثر برنامه های ایجاد شده برای فشرده سازی اطلاعات است. در حال حاضر، یکی از محبوب ترین منابع با استفاده از این کد می آرشیوهایی همچون ZIP، ARJ، RAR و بسیاری دیگر. همچنین، الگوریتم هافمن استفاده می شود برای فشرده سازی JPEG-تصاویر و دیگر اشیاء گرافیکی. خب، همه فکس نیز با استفاده از برنامه نویسی مدرن، در سال 1952 اختراع شد. با وجود این واقعیت است که از زمان ایجاد کد زمان زیادی به این روز آن است که در انواع غشاء های جدید و تجهیزات انواع قدیمی و مدرن استفاده می شود.

اصل برنامه نویسی کارآمد

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

کد هافمن، به عنوان مثال

برای نشان دادن الگوریتم، در نظر گرفتن نوع گرافیکی از ساخت و ساز از درخت کد. برای استفاده از این روش می تواند موثر باشد، برای روشن شدن تعریف ارزش های خاصی لازم برای مفهوم فرایند لازم است. مجموعه ای از تعدد گره ها و کمان، که از گره به گره کارگردانی، به نام نمودار. خود درخت یک گراف با مجموعه ای از ویژگی های خاص است:

• در هر گره ممکن است شامل بیش از یکی از کمان.
• یکی از گره ها باید ریشه درخت، است که، آن نباید بخشی از قوس الکتریکی در تمام؛
• اگر ساقه شروع به حرکت در امتداد کمان، این روند باید اجازه می دهد تا به طور کامل در هر یک از گره ها.

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

یک الگوریتم برای ساخت درخت هافمن

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

بهبود بهره وری از فشرده سازی

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

شتاب فرآیند فشرده سازی

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

نتیجه

کد هافمن - ساده و بلند تاسیس الگوریتم، که هنوز هم توسط بسیاری از برنامه ها و شرکت های شناخته شده استفاده می شود. سادگی و وضوح آن می تواند دستیابی به نتایج موثر فشرده سازی فایل ها از هر حجم و به طور قابل توجهی کاهش فضای در ذخیره سازی دیسک. به عبارت دیگر، هافمن - تا به مدت طولانی مورد مطالعه و در طرح کار می کرد، ارتباط است که به این روز کاهش می یابد. و با توانایی به منظور کاهش حجم از فایل ها، انتقال آنها را بر روی یک شبکه و یا توسط دیگر معنی آن را ساده تر، سریع و راحت است. کار با الگوریتم، شما می توانید هر گونه اطلاعات کامل و بدون آسیب رساندن به ساختار و کیفیت آن را فشرده، اما با حداکثر اثر برای کاهش وزن فایل. به عبارت دیگر، برنامه نویسی از کد هافمن بوده است و محبوب ترین روش و مرتبط به فشرده سازی حجم فایل باقی مانده است.