Бұл не?
Сабақтың тақырыбы — «Ақпарат мөлшері және сығу». Талдап көрейік. «Санды тап» ойынын еске түсір: жақсы сұрақ нұсқалардың жартысын бірден қысқартады. «Иә» немесе «жоқ» жауабы, егер екеуі бірдей ықтимал болса, дәл бір бит ақпарат береді. Ал сығу — дәл сол нәрсені аз бит санымен жаза білу, досыңа жазған жазбадағы қысқа қысқартулар сияқты.
Бұл не үшін керек?
Сығусыз бейнебайланыс та, телефондағы музыка да, ғарыш аппараттары басқа ғаламшарлардан жіберетін суреттер де болмас еді. Жасанды интеллектті оқытып, іске қосатын дата-орталықтар деректерді сақтау мен жіберуге орасан көп ақша жұмсайды, сондықтан ол жерде үнемделген әр бит есепте. Жасанды интеллект сыға алады, бірақ қай жерде ұсақ-түйекті тастауға болатынын, ал қай жерде, мысалы бағдарлама мәтінінде немесе банк үзінді-көшірмесінде, бір битті де жоғалтуға болмайтынын адам шешуі керек. Хабарламада қанша ақпарат барын түсінген адам болашақтың байланысын, қоймалары мен форматтарын жобалайды.
Бұл қалай жұмыс істейді?
Бірден алпыс төртке дейінгі санды табу үшін, егер әр жолы қалған сандарды дәл қақ бөлсең, алты сұрақ жеткілікті. Сығу жиілікке сүйенеді: жиі кездесетін таңбаларға қысқа код береді, сирек кездесетіндерге — ұзын; Хаффман коды осылай құрылған, ал Морзе әліпбиінде жиі кездесетін Е әрпі — бір ғана нүкте. Сонымен қатар бірде-бір код басқа кодтың басы болмауы керек, әйтпесе мәтінді бір мәнді шеше алмайсың — бұл Фано шарты. Клод Шеннон мәтін неғұрлым болжамды болса, оны соғұрлым күштірек сығуға болатынын дәлелдеді. ЗИП архивтері мен ПНГ суреттері шығынсыз сығылады, ал МП3 музыкасы, ДЖЕЙПЕГ фотосы және бейне шығынмен сығылады: құлақ пен көз байқай қоймайтын нәрселер тасталады.
Аздап тарих
Хаффман кодын елуінші жылдардың басында студент Дэвид Хаффман ойлап тапты. Оқытушы топқа таңдау ұсынды: емтихан тапсыру немесе ең тиімді екілік код туралы жұмыс жазу. Хаффман есепті ұзақ шешіп, тіпті беріле жаздап, емтиханға дайындалмақ болды, кенет ол қарапайым тәсіл тапты, және ол оқытушының өз әдістерінен де жақсы болып шықты.
Формула: ақпарат мөлшері
«Иә» немесе «жоқ» деп жауап берілетін әр сұрақ нұсқаларды қақ бөледі. Демек, бір сұрақтан кейін екі нұсқаны ажыратамыз, екеуінен кейін — төртеуін, и сұрақтан кейін — екінің и дәрежесін. Осыдан Хартли формуласы шығады: эн тең екінің и дәрежесі, немесе басқаша айтқанда, и тең екі негізі бойынша эннің логарифмі. Мұндағы эн — тең ықтимал нұсқалар саны, ал и — биттермен берілген ақпарат мөлшері, яғни қанша сұрақ керек екені. Егер эн екінің дәрежесі болмаса, логарифм бөлшек болып шығады, және сұрақтарды жоғары қарай дөңгелектеп, артығымен алады: жүз сан үшін жеті сұрақ керек. Нұсқалар санын екі есе көбейтсең — бір ғана артық сұрақ қажет болады.
N = 2ᴵN — тең ықтимал нұсқалар саны, —
I — ақпарат мөлшері, битI = log₂NI — ақпарат мөлшері, яғни сұрақтар саны, бит
N — нұсқалар саны, —
Формула: хабарлама көлемі
Егер әр таңба бірдей ұзындықтағы кодпен жазылса, бүкіл хабарламаның көлемі оңай есептеледі: үлкен и тең ка көбейтілген кіші и. Мұндағы ка — хабарламадағы таңбалар саны, кіші и — бір таңбаға қанша бит кететіні, ал үлкен и — хабарламаның биттермен берілген көлемі. Бір таңбаға қанша бит керек екенін әліпби шешеді: бес әріпке үш бит жетеді, өйткені екінің кубы — сегіз, бұл бестен кем емес, ал отыз екі әріпке бес бит керек. Хабарламаны екі есе ұзартсаң — көлем екі есе өседі; жиі кездесетін әріптердің кодтарын қысқартсаң — көлем азаяды, сығу осыған негізделген.
I = K · iI — хабарлама көлемі, бит
K — таңбалар саны, —
i — бір таңбаға кететін бит, бит
Практикада не істейміз?
Ал енді практикалық тапсырманы орындап көрейік. Бірінші бөлімде жүргізуші бірден алпыс төртке дейінгі сан ойлады, ал сен ка санын басасың — бұл «ка-дан үлкен бе?» деген сұрақ. Жүргізуші айлакер: екі жауаптың ішінен ол сандар көбірек қалатынын таңдайды, сондықтан әр жолы «иә» болғанда және «жоқ» болғанда қанша сан қалатынын ойлап, дәл қақ бөлуге тырыс. Екінші бөлімде «ОКОЛО_КОЛОКОЛА» жолын сық: қазір әр әріптің коды үш биттен тұрады, сонда қырық екі бит шығады, ал отызға сыйғызу керек. Қай әріп жиі кездесетінін санап, кодтардың ұзындығын өзгерт, ал бағдарлама префикстік кодты өзі құрып, көлемді қайта есептейді. Бірдеңе түсініксіз болып қалса, ештеңе етпейді, маған кез келген сұрақ қой, мен жауап беремін. Уайымдама.