مواد پیشنهادی اساس کار آزمایشی درس "مبانی ریاضی انفورماتیک" (نویسنده A. Gein) را تشکیل داد که در سال 2011 در دانشگاه راه دور "1 سپتامبر" با موفقیت به پایان رسید. مطالب برای دوره پیشرفته انفورماتیک در پایه یازدهم اقتباس شده است.

دانلود:

پیش نمایش:

لیسه فشرده سازی داده № 329

آندریوا O.A.

طرح درس

درجه 11

موضوع درس: فشرده سازی داده ها

نوع درس : یادگیری جدید مطالب آموزشیبا عناصر یک مکالمه جلویی.

اهداف درس : گسترش شایستگی ها در ایجاد فضای اطلاعاتی خودتان.

اهداف درس:

آموزشی - مفهوم را در نظر بگیریدمتراکم سازی داده ها و با الگوریتم های فشرده سازی داده های کاراکترها آشنا شوید.

شناختی - مفهوم را معرفی کنیدافزونگی داده ها؛

آموزشی - ایجاد شرایط برای فعالیت شدید هر دانش آموز.

نرم افزار

تدارک درس:- ارائه با موضوع "فشرده سازی داده ها"؛

فنی

ارائه یک درس: - محل کاریک دانش آموز با رایانه شخصی PentiumIII.

1. تابلوی نشانگر؛
2. پروژکتور ارائه

در طول کلاس ها

صحنه می کنم : خروجی در مورد موضوع درس و انگیزه مطالعه مطالب.

مرحله دوم : ارتباط مطالب آموزشی

مرحله III : فعلیت بخشیدن به دانش به دست آمده - پاسخ به سوالات برای تثبیت.

مرحله IV : پیام مشق شب; خلاصه کردن درس

خلاصه درس

صحنه می کنم:

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

اولین - محدود کردن حجم اطلاعات متأسفانه همیشه قابل قبول نیست. به عنوان مثال، برای تصاویر، این به معنای کاهش وضوح است، که منجر به از بین رفتن جزئیات دقیق می شود و ممکن است تصاویر را به طور کلی بی فایده کند (مثلاً برای تصاویر پزشکی یا فضایی). برای برنامه ها و متن ها این مسیر قابل اجرا نیست.
دومین - افزایش حجم رسانه های ذخیره سازی و پهنای باندکانالهای ارتباطی. این تصمیم با هزینه های مادی همراه است و گاهی اوقات بسیار قابل توجه است.
سوم - استفاده از فشرده سازی اطلاعات این راه حل اجازه می دهد تا چندین بار نیاز به حجم دستگاه های ذخیره سازی و پهنای باند کانال های ارتباطی را بدون هزینه اضافی (به جز هزینه های اجرای الگوریتم های فشرده سازی) کاهش دهید. شرایط کاربردی بودن آن، اضافه بودن اطلاعات و امکان نصب ویژه است نرم افزاریا تجهیزاتی برای انجام این رویه ها.

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

از لحاظ نظری ثابت شده است که افزونگی یک متن ادبی روسی 0.6 است. به عبارت دیگر، هنگامی که متن از طریق یک کانال ارتباطی مخابره می شود، از هر 10 حرف ارسال شده، هر 6 حرف حاوی هیچ اطلاعاتی نیست و به سادگی نمی توان بدون هیچ ضرری منتقل کرد.

سایر منابع اطلاعاتی اگر نه بیشتر (ρi = 0.9 ... 0.95) افزونگی - گفتار، و به ویژه موسیقی، یکسان هستند. تصاویر تلویزیونیو غیره.

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

مرحله دوم:

نمایش ارائه با سرعت مناسب همراه با توضیحات در مورد مطالب در هر اسلاید.

اسلاید 5 (توضیحات تکمیلی):

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

اسلاید 18 (توضیحات تکمیلی):

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

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

یک خانواده کامل از الگوریتم های LZ وجود دارد که برای آنها موثر است انواع مختلفداده ها.

نتیجه گیری مرحله دوم:

بنابراین، آینده با الگوریتم های جدید با نیاز منابع بالا و نسبت تراکم بالاتر و بالاتر است.

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

پیش نمایش:

برای لذت بردن پیش نمایشارائه ها ایجاد یک حساب کاربری ( حساب) گوگل و وارد شوید: https://accounts.google.com

شرح اسلایدها:

متراکم سازی داده ها

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

نسبت تراکم مقداری برای نشان دادن اثربخشی روش فشرده سازی است. برابر با نسبتمقدار اطلاعات قبل و بعد از فشرده سازی اطلاعات منبع داده های فشرده حجم فایل 2 مگابایت حجم فایل 512 کیلوبایت فشرده سازی K = 2 مگابایت / 0.5 مگابایت = 4

فشرده‌سازی داده‌ها می‌تواند با اتلاف و بدون تلفات باشد فشرده‌سازی بدون تلفات (کاملاً برگشت‌پذیر) یک روش فشرده‌سازی داده است که در آن داده‌ها پس از فشرده‌سازی کامل و بدون تغییر بازیابی می‌شوند (برای متون، برنامه‌ها استفاده می‌شود) Cszh تا ۵۰ درصد روش‌های فشرده‌سازی داده که در آن بخشی از داده‌ها دور انداخته شده و قابل بازیابی نیست (برای ویدیو، صدا، تصاویر استفاده می شود) Kszh تا 99٪

فشرده سازی از دست رفته نوع داده نوع فایل پس از فشرده سازی نسبت فشرده سازی Graphics.JPG تا 99% Video.MPG Audio.MP3 نوع داده نوع فایل پس از فشرده سازی نسبت فشرده سازی Graphics.GIF .TIF .PCX تا 50% Video.AVI هر نوع.ZIP . ARJ .RAR .LZH فشرده سازی بدون تلفات

الگوریتم های فشرده سازی داده های کاراکتر روش های آماری روش های فشرده سازی مبتنی بر پردازش متن آماری هستند. فشرده سازی دیکشنری یک تکنیک فشرده سازی است که بر اساس ساخت یک فرهنگ لغت داخلی است.

بسته بندی داده های همگن 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 1000 9 1001 _ 1010 + 1011 - 1100، رمزگذاری اسکیپیام 16 بایت است. جدول کد جدید بسته بندی: کد پیام پس از بسته بندی 8 بایت است: 000011010 01010101 00011000 0100011 110101011 01100011 00011010 000000001 =2 Ks

نسبت فشرده سازی با اندازه پیام کاراکتر افزایش می یابد. برای باز کردن بسته بندی جدید باید مشخص شود جدول کد; فقط برای پیام های همگن با استفاده از مجموعه محدودی از حروف الفبای اصلی موثر است. + - - مزایا و معایب روش

روش فشرده سازی آماری الگوریتم هافمن نمادهای متفرقهملاقات در پیامی با فرکانس متفاوتبه عنوان مثال، برای الفبای روسی، به طور متوسط، برای 1000 کاراکتر: فضای کاراکتر o ar k y g yu f فرکانس 175 90 62 40 28 18 13 6 2 کدگذاری)

کدگذاری هافمن (فشرده سازی) یک روش فشرده سازی است که کدهایی را به کاراکترهای حروف الفبا اختصاص می دهد. طول متغیر، بر اساس فراوانی وقوع این کاراکترها در پیام. فاصله کد کاراکتر 00 o 01 r 101 k 110 u 0110 f 1001

مشکل رمزگشایی مثال: اجازه دهید کدهای کاراکتر a -10، b -101، c -1010 پیام کد 10101011010 10 101 1010 10 10 101 10 10 1010 101 1010 را رمزگشایی کنند.

کد پیشوند کدی است که در آن هیچ کلمه رمزی پیشوند هیچ کلمه رمز دیگری نیست. نمونه کد پیشوند: 00 10 010 110 0110 0111 1110 1111 0 0 0 0 0 0 0 1 1 1 1 1 1 1

مثال: یک کد هافمن برای عبارت FROM_TOPOTA_HOOVES_DUST_TO_FIELD_FLIGHT بسازید بیایید بسامد وقوع کاراکترها را در عبارت تعیین کنیم: Build the Huffman digraph: -symbol رئوس صفحه دیگراف را تعریف می کند. - وزن بالا برابر فرکانسوقوع شخصیت؛ - جفت رئوس با کوچکترین وزن به هم متصل می شوند: - شاخه های چپ با 0 نشان داده می شوند. -شاخه های سمت راست با 1 نشان داده می شوند. -تعیین کد کاراکتر از ریشه تا برگ. نماد A E I CLOPTY L Y _ فرکانس 1 1 1 1 3 6 5 6 2 1 1 6

ریشه درخت T- O- Y- _ P- L- Yu- L- E- K- I- A- 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 00011 00010 11000 11001 11011 11010 001 010 011 111 10 0000 هر رأس با یک فلش مشخص شده است

ساخته شده کدهای پیشوندکاراکترها: پیام در کدهای جدید شامل 110 بیت است، در رمزگذاری ASCII - 34 * 8 = 272 بیت و سپس K szh = 272 / 110 = 2.47 10 011 010 0000 00011 00010 132 355 طول کد 5 5 5 3

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

روش دیکشنری الگوریتم فشرده سازی LZ این الگوریتم برای اولین بار توسط A. Lempel و J. Ziv (Abraham Lempel, Jacob Ziv) در سال 1977-1978 توصیف شد، بنابراین این روش اغلب Lempel-Ziv یا به اختصار LZ نامیده می شود. این مبتنی بر ایده جایگزینی رایج‌ترین رشته‌های کاراکترها (رشته‌ها) در یک فایل با ارجاع به «نمونه‌های» رشته‌های ذخیره شده در یک فایل خاص است. جدول ایجاد کرد(فرهنگ لغت).

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

قابل اجرا برای هر داده؛ - خیلی سرعت بالافشرده سازی؛ - نسبت تراکم بالا؛ + - مزایا و معایب روش - دیکشنری به نوع متن تنظیم شده است. - فرهنگ لغت می تواند بسیار بزرگ باشد.

سخنرانی شماره 4. فشرده سازی اطلاعات

اصول فشرده سازی اطلاعات

هدف از فشرده سازی داده ها ارائه یک نمایش فشرده از داده های تولید شده توسط منبع برای ذخیره سازی و انتقال اقتصادی تر آنها از طریق کانال های ارتباطی است.

فرض کنید یک فایل 1 (یک) مگابایتی داریم. باید یک فایل از آن بگیریم کوچکتر. هیچ چیز پیچیده ای نیست - ما یک بایگانی را راه اندازی می کنیم، به عنوان مثال، WinZip، و در نتیجه، مثلاً، یک فایل به اندازه 600 کیلوبایت دریافت می کنیم. 424 کیلوبایت باقی مانده کجا رفت؟

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

انواع فشرده سازی

تمام روش های فشرده سازی اطلاعات را می توان به طور مشروط به دو کلاس بزرگ غیر همپوشانی تقسیم کرد: فشرده سازی با ضرر - زیاناطلاعات و فشرده سازی بدون ضرراطلاعات

فشرده سازی بدون از دست دادن اطلاعات

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

روش‌های فشرده‌سازی این کلاس نمی‌توانند اجازه از دست دادن اطلاعات را بدهند، بنابراین آنها فقط بر اساس حذف افزونگی آن هستند و اطلاعات تقریباً همیشه دارای افزونگی هستند (درست است، اگر کسی قبلاً آن را فشرده نکرده باشد). اگر افزونگی وجود نداشت، چیزی برای فشرده سازی وجود نداشت.

در اینجا یک مثال ساده است. زبان روسی دارای 33 حرف، ده عدد و حدود ده ها علامت نگارشی دیگر و سایر کاراکترهای خاص است. برای متنی که نوشته شده است فقط با حروف بزرگ روسی(مانند تلگرام و رادیوگرام) شصت معنی مختلف کفایت می کند. با این حال، هر کاراکتر معمولاً به صورت یک بایت رمزگذاری می شود که حاوی 8 بیت است و می تواند نشان دهنده 256 کد مختلف باشد. این اولین دلیل برای افزونگی است. برای متن "تلگرافیک" ما، شش بیت در هر کاراکتر کافی است.

در اینجا یک مثال دیگر وجود دارد. در رمزگذاری کاراکترهای بین المللی ASCIIبرای رمزگذاری هر کاراکتری، همان تعداد بیت (8) اختصاص داده می‌شود، در حالی که همه مدت‌ها و به خوبی می‌دانستند که رمزگذاری متداول‌ترین کاراکترها با کاراکترهای کمتر منطقی است. بنابراین، برای مثال، در "کد مورس" حروف "E" و "T" که رایج هستند، با یک کاراکتر رمزگذاری می شوند (به ترتیب، این یک نقطه و یک خط تیره است). و حروف کمیاب مانند "Yu" (- -) و "C" (- -) با چهار کاراکتر کدگذاری می شوند. رمزگذاری ناکارآمد دومین دلیل برای افزونگی است. برنامه هایی که اطلاعات را فشرده می کنند می توانند رمزگذاری خود را وارد کنند (متفاوت برای فایل های مختلف) و به فایل فشردهبرخی از جدول (فرهنگ لغت)، که از آن برنامه باز کردن بسته یاد می گیرد که چگونه به فایل داده شدهکاراکترهای خاص یا گروه های آنها کدگذاری می شوند. الگوریتم های مبتنی بر رمزگذاری مجدد اطلاعات نامیده می شوند الگوریتم های هافمن

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

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

فشرده سازی از دست رفته.

فشرده سازی از دست رفته به این معنی است که پس از فشرده سازی آرشیو فشرده، سندی به دست می آوریم که تا حدودی با آنچه در ابتدا بود متفاوت است. واضح است که هر چه نسبت تراکم بالاتر باشد، ارزش بیشترضرر و بالعکس

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

در عین حال، موادی وجود دارند که در آنها ارزش دارد که چند درصد از اطلاعات را قربانی کنیم تا فشرده سازی ده برابری حاصل شود. اینها شامل تصاویر عکاسی، فیلمبرداری و ساخته های موسیقی. از دست دادن اطلاعات در حین فشرده سازی و کاهش فشار بعدی در چنین موادی به عنوان ظهور برخی "صدای" اضافی درک می شود. اما از آنجایی که هنگام ایجاد این مواد هنوز "نویز" خاصی وجود دارد، افزایش اندک آن همیشه حیاتی به نظر نمی رسد و افزایش اندازه فایل بسیار زیاد است (10-15 برابر برای موسیقی، 20-30 برابر برای مواد عکس و ویدئو) .

الگوریتم های فشرده سازی با اتلاف شامل الگوریتم های معروفی مانند JPEG و MPEG هستند. الگوریتم JPEG هنگام فشرده سازی تصاویر ثابت استفاده می شود. فایل های گرافیکی فشرده شده با این روش دارای پسوند JPG هستند. الگوریتم های MPEG در فشرده سازی ویدیو و موسیقی استفاده می شود. این فایل ها بسته به برنامه خاص ممکن است پسوندهای مختلفی داشته باشند، اما معروف ترین آنها .mpg برای ویدیو و .mp3 برای موسیقی است.

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

مقدار افت فشاری قابل تحمل معمولاً قابل کنترل است. این به شما امکان می دهد آزمایش کنید و به نسبت اندازه / کیفیت مطلوب برسید. در تصاویر عکاسی که برای نمایش روی صفحه در نظر گرفته شده اند، از دست دادن 5 درصد اطلاعات معمولاً مهم نیست و در برخی موارد 20 تا 25 درصد قابل تحمل است.

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

کد شانون-فانو

برای ملاحظات بیشتر، ارائه ما راحت خواهد بود فایل اصلیبا متن به عنوان منبع کاراکترهایی که هر بار در خروجی آن ظاهر می شوند. ما از قبل نمی دانیم کدام کاراکتر بعدی خواهد بود، اما می دانیم که با احتمال p1 حرف "a" ظاهر می شود، با احتمال p2 حرف "b" و غیره.

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

بیایید متنی را تصور کنیم که الفبای آن فقط از 16 حرف تشکیل شده است: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. هر یک از این کاراکترها می توانند باشند. فقط با 4 بیت رمزگذاری کنید: از 0000 تا 1111. حال تصور کنید که احتمال ظاهر شدن این کاراکترها به صورت زیر توزیع می شود:

مجموع این احتمالات البته وحدت است. اجازه دهید این نمادها را به دو گروه تقسیم کنیم به گونه ای که احتمال کل نمادهای هر گروه ~0.5 باشد (شکل). در مثال ما، اینها گروه خواهند بود شخصیت های A-Bو G-R. دایره‌های موجود در شکل که نشان‌دهنده گروه‌هایی از نمادها هستند، راس یا گره (گره) نامیده می‌شوند و ساختار خود این گره‌ها یک درخت دوتایی (B-tree) است. بیایید به هر گره یک کد اختصاص دهیم و یک گره را با عدد 0 و دیگری را با عدد 1 مشخص کنیم.

باز هم گروه اول (A-B) را به دو زیر گروه تقسیم می کنیم به گونه ای که مجموع احتمالات آنها تا حد امکان به یکدیگر نزدیک باشد. عدد 0 را به کد زیرگروه اول و عدد 1 را به کد زیرگروه دوم اضافه می کنیم.

این عمل را تا زمانی تکرار می کنیم که در هر رأس "درخت" ما فقط یک علامت باقی بماند. درخت کامل برای الفبای ما 31 گره خواهد داشت.

کدهای کاراکتر (راست ترین گره های درخت) دارای کدهایی با طول نابرابر هستند. بنابراین، حرف A که احتمال p=0.2 برای متن خیالی ما دارد، تنها با دو بیت و حرف P (که در شکل نشان داده نشده است) که احتمال p=0.013 دارد، با یک عدد شش کد گذاری می شود. ترکیب بیت

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

جایی که ni تعداد بیت هایی است که کاراکتر i را کد می کنند، pi احتمال وقوع کاراکتر i است.

کد هافمن

الگوریتم هافمن ایده کلی کدگذاری آنتروپی را با استفاده از مجموعه های پیشوندی به زیبایی پیاده سازی می کند و به شرح زیر عمل می کند:

1. همه حروف الفبا را در یک ردیف به ترتیب افزایش یا نزول احتمال وقوع آنها در متن می نویسیم.

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

3. مسیر هر برگ درخت را دنبال می کنیم و جهت هر گره را مشخص می کنیم (به عنوان مثال، راست - 1، چپ - 0). دنباله به دست آمده یک کلمه رمز مربوط به هر کاراکتر را می دهد (شکل).

بیایید بسازیم درخت کدبرای پیامی با الفبای زیر:

معایب روش ها

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

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

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

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

Run Length Encoding (RLE) یکی از قدیمی ترین و ساده ترین الگوریتم های آرشیو است. فشرده‌سازی در RLE با جایگزینی زنجیره‌های بایت‌های یکسان با جفت‌های «counter, value» اتفاق می‌افتد. («قرمز، قرمز، ...، قرمز» به صورت «N قرمز» نوشته می شود).

یکی از پیاده‌سازی‌های این الگوریتم به شرح زیر است: آنها به دنبال بایت‌هایی هستند که کمتر اتفاق می‌افتد، آن را پیشوند می‌نامند و زنجیره‌ای از کاراکترهای یکسان را با سه‌گانه «پیشوند، شمارنده، ارزش» جایگزین می‌کنند. اگر این بایت یک یا دو بار پشت سر هم در فایل منبع رخ دهد، با یک جفت "پیشوند، 1" یا "پیشوند، 2" جایگزین می شود. یک جفت استفاده نشده "پیشوند، 0" وجود دارد که می تواند به عنوان پایان دهنده برای داده های بسته بندی شده استفاده شود.

هنگام رمزگذاری فایل‌های exe، می‌توانید دنباله‌هایی مانند AxAyAzAwAt... را جستجو و بسته‌بندی کنید، که اغلب در منابع (رشته‌های یونیکد) یافت می‌شوند.

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

کد LZW (Lempel-Ziv & Welch) یکی از رایج ترین کدهای فشرده سازی بدون تلفات امروزی است. با کمک کد LZW است که فشرده سازی در قالب های گرافیکی مانند TIFF و GIF انجام می شود ، با کمک تغییرات LZW ، بسیاری از بایگانی های جهانی عملکردهای خود را انجام می دهند. عملکرد الگوریتم بر اساس جستجو است فایل ورودیتکرار دنباله ای از کاراکترها که در ترکیبات 8 تا 12 بیتی کدگذاری شده اند. بنابراین، کارآمدترین این الگوریتمبر این است فایل های متنیو روی فایل‌های گرافیکی که دارای قسمت‌های بزرگ همرنگ یا توالی پیکسل‌های تکراری هستند.

عدم از دست دادن اطلاعات در طول کدگذاری LZW منجر به استفاده گسترده از آن شد فرمت TIFF. این فرمت هیچ محدودیتی در اندازه و عمق رنگ تصویر ایجاد نمی کند و به طور گسترده ای مثلا در چاپ استفاده می شود. یکی دیگر از فرمت های مبتنی بر LZW - GIF - ابتدایی تر است - به شما امکان می دهد تصاویر را با عمق رنگ بیش از 8 بیت / پیکسل ذخیره کنید. در ابتدای فایل GIF - یک پالت - جدولی است که مطابقت بین شاخص رنگ - عددی در محدوده 0 تا 255 و مقدار رنگ واقعی 24 بیتی را ایجاد می کند.

الگوریتم های فشرده سازی با اتلاف

الگوریتم JPEG توسط گروهی از شرکت ها به نام Joint Photographic Experts Group توسعه داده شد. هدف این پروژه ایجاد یک استاندارد فشرده سازی بسیار کارآمد برای تصاویر سیاه و سفید و رنگی بود و این هدف توسط توسعه دهندگان محقق شد. در حال حاضر، JPEG به طور گسترده در مواردی که به درجه بالایی از فشرده سازی نیاز است استفاده می شود - به عنوان مثال، در اینترنت.

بر خلاف الگوریتم LZW، رمزگذاری JPEG یک رمزگذاری با اتلاف است. الگوریتم رمزگذاری خود بر اساس ریاضیات بسیار پیچیده است، اما به طور کلی می توان آن را به شرح زیر توصیف کرد: تصویر به مربع های 8 * 8 پیکسل تقسیم می شود و سپس هر مربع به یک زنجیره متوالی 64 پیکسل تبدیل می شود. علاوه بر این، هر یک از این زنجیره‌ها در معرض به اصطلاح تبدیل DCT قرار می‌گیرند که یکی از انواع تبدیل فوریه گسسته است. در این واقعیت نهفته است که دنباله ورودی پیکسل ها را می توان به صورت مجموع مولفه های سینوسی و کسینوس با فرکانس های متعدد (به اصطلاح هارمونیک) نشان داد. در این حالت فقط باید دامنه این اجزا را بدانیم تا بتوانیم توالی ورودی را با دقت کافی بازسازی کنیم. هر چه اجزای هارمونیک بیشتری بشناسیم، اختلاف بین تصویر اصلی و فشرده کمتر می شود. اکثر رمزگذارهای JPEG به شما این امکان را می دهند که میزان فشرده سازی را تنظیم کنید. این بسیار به دست آمده است راه ساده: هرچه نسبت تراکم بالاتر باشد، هر بلوک 64 پیکسلی هارمونیک کمتری نشان داده می شود.

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

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

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

فشرده سازی فراکتال

فشرده‌سازی تصویر فراکتال یک الگوریتم فشرده‌سازی تصویر با اتلاف است که مبتنی بر کاربرد سیستم‌های توابع تکراری (IFS، معمولاً تبدیل‌های وابسته) به تصاویر است. این الگوریتم به این دلیل شناخته شده است که در برخی موارد اجازه می دهد تا نسبت های فشرده سازی بسیار بالایی را بدست آورید ( بهترین نمونه ها- تا 1000 بار با کیفیت بصری قابل قبول) برای عکس های واقعی از اشیاء طبیعی که اصولاً برای سایر الگوریتم های فشرده سازی تصویر موجود نیست. به خاطر اینکه موقعیت سختاین الگوریتم به طور گسترده با ثبت اختراع مورد استفاده قرار نگرفت.

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

به بیان دقیق، IFS مجموعه ای از تبدیل های وابسته سه بعدی است که یک تصویر را به تصویر دیگر تبدیل می کند. نقاط در فضای سه بعدی (مختصات x، مختصات y، روشنایی) در معرض تبدیل قرار می گیرند.

اساس روش رمزگذاری فراکتال، تشخیص مناطق خود مشابه در یک تصویر است. امکان بکارگیری نظریه سیستم‌های تابع تکراری (IFS) برای مشکل فشرده‌سازی تصویر برای اولین بار توسط مایکل بارنزلی و آلن اسلون مورد بررسی قرار گرفت. آنها ایده خود را در سال های 1990 و 1991 ثبت کردند. ژاکین یک روش رمزگذاری فراکتال را معرفی کرد که از سیستمی از بلوک‌های تصویر فرعی دامنه و محدوده استفاده می‌کند، بلوک‌های مربعی شکل که کل تصویر را پوشش می‌دهند. این رویکرد مبنایی برای اکثر روش‌های رمزگذاری فراکتال است که امروزه مورد استفاده قرار می‌گیرند. این توسط یووال فیشر و تعدادی از محققان دیگر بهبود یافته است.

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

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

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

به طور خلاصه، روش پیشنهادی بارنزلی را می توان به شرح زیر توصیف کرد. تصویر توسط چندین تبدیل ساده (در مورد ما، affine) کدگذاری می شود، یعنی با ضرایب این تبدیل ها (در مورد ما، A، B، C، D، E، F) تعیین می شود.

به عنوان مثال، تصویر منحنی کخ را می توان با چهار تبدیل افین کدگذاری کرد، ما آن را به طور منحصر به فرد تنها با استفاده از 24 ضریب تعریف می کنیم.

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

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

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

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

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

مقایسه با JPEG

امروزه رایج ترین الگوریتم آرشیو گرافیکی JPEG است. آن را با فشرده سازی فراکتال مقایسه کنید.

ابتدا توجه داشته باشید که هر دو الگوریتم بر روی تصاویر 8 بیتی (مقیاس خاکستری) و 24 بیتی تمام رنگی کار می کنند. هر دو الگوریتم های فشرده سازی با اتلاف هستند و نسبت های آرشیو نزدیکی را ارائه می دهند. هر دو الگوریتم فراکتال و JPEG این قابلیت را دارند که با افزایش تلفات، نسبت فشرده سازی را افزایش دهند. علاوه بر این، هر دو الگوریتم به خوبی موازی می شوند.

تفاوت‌ها زمانی شروع می‌شوند که زمان بایگانی/آشیو کردن الگوریتم‌ها را در نظر می‌گیریم. بنابراین، الگوریتم فراکتال صدها و حتی هزاران بار بیشتر از JPEG فشرده می شود. برعکس، باز کردن تصویر 5-10 برابر سریعتر اتفاق می افتد. بنابراین، اگر تصویر فقط یک بار فشرده شود، اما بارها از طریق شبکه منتقل شود و از حالت فشرده خارج شود، استفاده از الگوریتم فراکتال سود بیشتری دارد.

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

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

جابجایی JPEG توسط الگوریتم فراکتال در استفاده گسترده به زودی اتفاق نخواهد افتاد (حداقل به دلیل سرعت کم بایگانی دومی)، با این حال، در زمینه برنامه های چند رسانه ای، در بازی های کامپیوتریاستفاده از آن موجه است

خلاصه درس انفورماتیک و ICT

یک نوع : درس یادگیری مطالب جدید

موضوع : بایگانی ها روش های فشرده سازی اطلاعات

اهداف :

آموزش روش های فشرده سازی اطلاعات (بسته بندی و هافمن)

تفکر الگوریتمی را توسعه دهید

پرورش نگرش مسئولانه نسبت به انجام کار.

روش: توضیحی-تصویری

در طول کلاس ها:

زمان سازماندهی(2 دقیقه)

به روز رسانی دانش (5 دقیقه)

توضیح مطالب و نوشتن در دفتر. (25 دقیقه)

تثبیت اولیه مواد (10 دقیقه)

خلاصه کردن (3 دقیقه)

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

مفهوم "فشرده سازی اطلاعات" را چگونه درک می کنید؟

اطلاعات دیجیتال چگونه فشرده می شود؟

چه برنامه های بایگانی را می شناسید؟

اطلاعات به چه شکلی نیاز به فشرده سازی اجباری دارد؟

مطالب نظری:

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

بایگانی‌ها برنامه‌هایی هستند که به شما امکان می‌دهند با استفاده از روش‌های فشرده‌سازی خاص، کپی‌های کوچک‌تری از فایل‌ها ایجاد کنید و کپی‌های چند فایل را در یک فایل بایگانی ترکیب کنید، و همچنین بایگانی‌ها را باز کنید (فایل‌ها را از یک آرشیو استخراج کنید).

الگوریتم های مختلفی برای بایگانی داده ها بدون از دست دادن اطلاعات وجود دارد، به عنوان مثال. باز کردن زیپ باعث بازیابی داده ها می شود فرم اصلی. برای سیستم عامل ویندوز، محبوب ترین ها هستند بایگانی های WinRAR، WinZIP، WinACE.

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

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

روش بسته بندی

متن ورودی "COLUMN_ABOUT_BELLS" فقط شامل 5 نویسه مختلف است (K، O، L، A، _). بنابراین، هر کاراکتر را می توان با سه بیت کدگذاری کرد. در مجموع، 18 کاراکتر در تست اصلی وجود دارد، بنابراین 18x3=54 بیت مورد نیاز است. نسبت تراکم 144/54=2.7 است

روش هافمن

ضعفروش بسته بندی به این صورت است که کاراکترها توسط دنباله بیت هایی با طول یکسان کدگذاری می شوند. به عنوان مثال، هر متنی که فقط از حروف "A" و "B" تشکیل شده باشد، هشت بار با روش بسته بندی فشرده می شود. با این حال، اگر فقط یک حرف به چنین متنی اضافه شود، به عنوان مثال "C"، نسبت فشرده سازی بلافاصله نصف می شود و صرف نظر از طول متن و تعداد کاراکترهای اضافه شده "C"

بهبود در نسبت فشرده سازی را می توان با رمزگذاری کاراکترهای متداول به دست آورد کدهای کوتاه، و موارد کمیاب طولانی تر هستند. این دقیقاً ایده روشی است که توسط D. Huffman در سال 1952 منتشر شد.

الگوریتم هافمن

کاراکترهای الفبای ورودی فهرستی از گره های آزاد را تشکیل می دهند. هر گره دارای وزنی برابر با تعداد تکرار کاراکتر در پیام اصلی است.

دو گره آزاد با کمترین وزن از لیست انتخاب می شوند.

گره "والد" آنها با وزنی برابر با مجموع وزن آنها ایجاد می شود، به قوس های "فرزندان" متصل می شود.

یک قوس که از "والد" خارج می شود، به بیت 1 اختصاص داده می شود، و دیگری - بیت 0.

"والد" به لیست گره های آزاد اضافه می شود و دو "فرزند" آن از این لیست حذف می شوند.

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

وظایف برای تعمیر

پیام را به دو روش بسته بندی کنید: Archip_osip._Osip_hoarse.

سوالات خلاصه درس:

فشرده سازی اطلاعات چیست؟

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

امروزه چه روش های فشرده سازی مورد مطالعه قرار گرفته است.

کارآمدترین روش فشرده سازی چیست و چرا؟

طرح:

معرفی

• 1 اصول فشرده سازی داده ها
• 2 ویژگی های الگوریتم های فشرده سازی و کاربرد آنها
  • 2.1 نسبت تراکم
  • 2.2 پذیرش ضرر و زیان
  • 2.3 سیستم مورد نیاز الگوریتم ها
• 3 الگوریتم های فشرده سازی داده ها فرمت ناشناخته
ادبیات

معرفی

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

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

1. اصول فشرده سازی داده ها

در قلب هر روش فشرده سازی، یک مدل منبع داده یا به طور دقیق تر، یک مدل افزونگی وجود دارد. به عبارت دیگر، فشرده سازی داده ها از دانش پیشینی در مورد اینکه چه نوع داده ای فشرده می شود استفاده می کند. بدون چنین اطلاعاتی در مورد منبع، نمی توان هر گونه فرضی در مورد تغییر ایجاد کرد که اندازه پیام را کاهش دهد. مدل افزونگی می تواند ثابت باشد، برای کل پیام فشرده بدون تغییر باشد، یا در مرحله فشرده سازی (و بازیابی) ساخته یا پارامتر شود. روش هایی که امکان تغییر مدل افزونگی اطلاعات بر اساس داده های ورودی را فراهم می کنند، تطبیقی ​​نامیده می شوند. غیر تطبیقی ​​معمولاً الگوریتم‌هایی بسیار تخصصی هستند که برای کار با داده‌هایی استفاده می‌شوند که ویژگی‌های کاملاً تعریف شده و تغییرناپذیری دارند. اکثریت قریب به اتفاق الگوریتم های به اندازه کافی جهانی تا حدی تطبیقی ​​دارند.

تمام روش های فشرده سازی داده ها به دو دسته اصلی تقسیم می شوند:

• فشرده سازی بدون اتلاف
• فشرده سازی از دست رفته

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

2. ویژگی های الگوریتم های فشرده سازی و کاربرد آنها

2.1. نسبت تراکم

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

جایی که ک- نسبت تراکم، اس o مقدار داده های اولیه و اسج - حجم فایل های فشرده. بنابراین، هر چه نسبت تراکم بالاتر باشد، الگوریتم کارآمدتر است. باید توجه داشت:

• اگر ک= 1، سپس الگوریتم فشرده سازی را انجام نمی دهد، یعنی پیام خروجی از نظر حجم با ورودی برابر است.
• اگر ک < 1, то алгоритм порождает сообщение اندازه بزرگترنسبت به حالت فشرده نشده، یعنی کار "مضر" انجام می دهد.

وضعیت با ک < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или طول مساوی. دلیل این واقعیت این است که از آنجایی که تعداد پیام های متمایز از طول nبیت دقیقا 2 است n، تعداد پیام های مختلف با طول کمتر یا مساوی n(اگر حداقل یک پیام با طول کمتر وجود داشته باشد) کمتر از 2 خواهد بود n. این به این معنی است که نمی‌توان بدون ابهام همه پیام‌های اصلی را به یک پیام فشرده نگاشت: یا برخی از پیام‌های اصلی نمایش فشرده‌ای ندارند، یا چندین پیام اصلی نمایش فشرده‌شده یکسانی خواهند داشت، به این معنی که نمی‌توان آنها را متمایز کرد.

نسبت فشرده سازی می تواند ثابت باشد (برخی الگوریتم های فشرده سازی صدا، تصاویر و غیره مانند A-law، μ-law، ADPCM، کدگذاری بلوک کوتاه) یا متغیر. در حالت دوم، می توان آن را برای هر کدام تعریف کرد پیام خاص، یا بر اساس برخی معیارها ارزیابی می شود:

• متوسط ​​(معمولا مجموعه تستداده ها)؛
• حداکثر (مورد بهترین فشرده سازی)؛
• حداقل (بدترین حالت فشرده سازی)؛

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

2.2. پذیرش ضرر و زیان

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

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

2.3. سیستم مورد نیاز الگوریتم ها

الگوریتم های مختلف ممکن است به منابع متفاوتی نیاز داشته باشند سیستم محاسباتیکه بر روی آنها اجرا می شوند:

• RAM (برای داده های متوسط)؛
• حافظه دائمی (تحت کد برنامه و ثابت ها)؛
• زمان پردازنده

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

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

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

3. الگوریتم هایی برای فشرده سازی داده ها با فرمت ناشناخته

دو رویکرد اصلی برای فشرده سازی داده های فرمت ناشناخته وجود دارد.

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

ادبیات

• D. Vatolin، A. Ratushnyak، M. Smirnov، V. Yukin.روش های فشرده سازی داده ها ترتیب آرشیوها، فشرده سازی تصویر و ویدئو. - Dialog-MEPhI, 2002. - S. 384. - ISBN 5-86404-170-X 3000 نسخه
• دی سالومون.فشرده سازی داده ها، تصاویر و صدا. - M .: Technosphere, 2004. - S. 368. - ISBN 5-94836-027-X 3000 نسخه

اسلاید 2

• برای ذخیره سازی طولانی مدت داده ها در رسانه های ذخیره سازی مختلف
• برای انتقال داده ها از طریق کانال های ارتباطی