HYRJE Prirjet e reja që janë shfaqur në matematikë në shekullin e njëzetë zakonisht funksionojnë me koncepte dhe koncepte komplekse që janë të vështira për t'u popullarizuar. Në këtë sfond, merita e matematikanit dhe inxhinierit të shquar amerikan Claude Shannon, i cili në vitet 1947-1948, bazuar në konsideratat elementare, zbuloi zonë e re matematika – teoria e informacionit. Shtysa për të krijuar shkencë e re ishin të pastra probleme teknike transmetimi i informacionit përmes telit telegrafik dhe telefonik, megjithatë, për shkak të natyrës së tij të përgjithshme, teoria e informacionit tani përdoret në kërkimet që lidhen me transmetimin dhe ruajtjen e çdo informacioni në natyrë dhe teknologji. Në fund të viteve dyzet, në agimin e zhvillimit të teorisë së informacionit, ideja e zhvillimit të një të re mënyra efektive informacioni i kodimit ishte në ajër. Studiuesit janë marrë me çështje të entropisë, përmbajtjes së informacionit dhe tepricës. Pyes veten se çfarë janë këto punimet fillestare në fushën e kompresimit të informacionit u kryen para ardhjes së kompjuterit dixhital modern. Sot, teoria e informacionit po zhvillohet paralelisht me programimin, por në atë kohë ideja e zhvillimit të algoritmeve duke përdorur aritmetikë binare për kodimin e karaktereve ishte një hap i rëndësishëm përpara. Algoritmet Shannon - Fano dhe Huffman ishin një nga algoritmet e parë për kodimin efikas të informacionit. Ky punim shqyrton konceptet bazë entropia dhe informacioni, si dhe përshkruan parimet e kodimit të mesazheve sipas Shannon - Fano dhe Huffman, tregon rolin e tyre të rëndësishëm në transmetimin e informacionit përmes linjave të komunikimit. Por linjat e komunikimit për të cilat u zhvilluan këto metoda të kodimit të informacionit janë tashmë në të kaluarën. Për fat të mirë, parimet Shannon-Fano dhe Huffman janë zbatuar në bota moderne: për të kompresuar informacionin. Arkivuesit PKZIP, ARJ, si dhe pjesë e standardit të mirënjohur JPEG (kompresim informacion grafik me humbje) punojnë pikërisht mbi këto parime. Kodet Shannon-Fano dhe Huffman mësohen në të gjitha universitetet teknike në botë dhe, përveç kësaj, përfshihen në programin për studime të avancuara të shkencave kompjuterike në shkollë. Prandaj, studimi i metodave të kodimit Shannon - Fano dhe Huffman është i rëndësishëm. Qëllimi i kësaj pune është të studiojë parimet e kodimit të informacionit të Shannon - Fano dhe Huffman dhe aplikimin e tyre në zgjidhjen e problemeve. Detyra është të studiohet entropia dhe teprica e llojeve specifike të mesazheve për zbatimin e mëvonshëm të parimeve Shannon-Fano dhe Huffman në to. 1. Informacioni dhe kodimi. Kodet Shannon - Fano dhe Huffman. 1.1 Informacioni dhe kodimi. Fjala "informacion" është e njohur për të gjithë në kohën tonë. Vjen nga latinishtja "informatio", që do të thotë - sqarim, mesazh, ndërgjegjësim. Megjithatë, ai hyri në përdorim të vazhdueshëm jo shumë kohë më parë, në mesin e shekullit të njëzetë, me sugjerimin e Claude Shannon. Ai e futi këtë term në një kuptim të ngushtë teknik në lidhje me teorinë e komunikimit ose transmetimit të kodeve, e cila u quajt "Teoria e informacionit". Këtu nuk është i rëndësishëm asnjë informacion, por vetëm ato që heqin ose reduktojnë plotësisht pasigurinë ekzistuese. Një përkufizim filozofik dhe për këtë arsye më i gjerë i këtij termi jepet nga një nga themeluesit e shkencës kompjuterike, shkencëtari i famshëm amerikan Norbert Wiener: "Informacioni është një përcaktim i përmbajtjes që nxjerrim nga bota e jashtme në procesin e përshtatjes sonë ndaj atë dhe sjelljen e të menduarit tonë në përputhje me të." Sigurisht, këto janë larg përkufizimeve unike të informacionit. Aktualisht, ky term ka një kuptim më të thellë dhe më të shumëanshëm. Duke mbetur kryesisht intuitiv, ai merr përmbajtje të ndryshme semantike në degë të ndryshme të veprimtarisë njerëzore: * në aspektin e përditshëm, informacioni kuptohet si informacion për botën rreth tij dhe proceset që ndodhin në të, i perceptuar nga një person ose pajisje speciale; * në teknologji, informacioni kuptohet si mesazhe të transmetuara në formën e shenjave ose sinjaleve; * në teorinë e informacionit (sipas K. Shannon) nuk është i rëndësishëm asnjë informacion, por vetëm ato që heqin ose reduktojnë plotësisht pasigurinë ekzistuese; * në teorinë semantike (kuptimi i një mesazhi) - ky është informacion që ka një risi, e kështu me radhë ... Një shumëllojshmëri e tillë qasjesh nuk është e rastësishme, por pasojë e faktit se nevoja për një organizim të ndërgjegjshëm të proceset e lëvizjes dhe përpunimit të asaj që ka një emër të përbashkët - ka dalë informacioni. Për shqyrtim të mëtejshëm, ne kemi nevojë për konceptin e informacionit, i cili nënkupton transmetimin e mesazheve të informacionit përmes linjave të komunikimit. Merrni parasysh skema e përgjithshme transmetimi i mesazheve; për saktësi, do të flasim, për shembull, për telegrafinë. Në njërën skaj të rreshtit, dërguesi dërgon një mesazh, të shkruar duke përdorur ndonjë nga alfabetet ose numrat e njohur për ne, ose të dyja shkronjat dhe numrat të kombinuara. Për transmetimin e këtij lloji të mesazheve, përdoren sekuenca të sinjaleve të rrymës së drejtpërdrejtë, disa nga karakteristikat e të cilave operatori telegraf mund të ndryshojë sipas gjykimit të tij, të perceptuara nga operatori i dytë telegrafik në skajin marrës të linjës. Sinjalet më të thjeshta të dallueshme, të përdorura gjerësisht në praktikë, është dërgimi i një rryme (d.m.th., ndezja e saj për disa plotësisht kohë të caktuar) dhe pa dërgim - pauzë (fikja e rrymës për të njëjtën kohë); vetëm me ndihmën e këtyre dy sinjaleve, tashmë mund të transmetoni çdo mesazh, nëse pranoni të zëvendësoni secilën shkronjë ose numër një kombinim të caktuar dërgimi i rrymës dhe pauza. Në inxhinierinë e komunikimit, rregulli që lidh çdo mesazh të transmetuar me një kombinim të caktuar sinjalesh zakonisht quhet kod (në rastin e telegrafisë, një kod telegrafi) dhe vetë operacioni i përkthimit të një mesazhi në një sekuencë. sinjale të ndryshme- kodimi i mesazhit. Një "kod" do të kuptohet si një grup i tillë me n emërtime kodesh, të përputhura me n shkronja të alfabetit, për të cilat plotësohet kushti i mëposhtëm: asnjë emërtim kodi i një shkronje të mos përputhet me fillimin e ndonjë emërtimi tjetër kodi më të gjatë, d.m.th. kodet duhet të deshifrohen në mënyrë unike. Megjithatë, kodet që përdorin vetëm dy çipa të ndryshëm (p.sh., dërgoni rrymë dhe pauzë) quhen kode binare. Në disa komplete telegrafike, përveç përfshirje e thjeshtë dhe duke fikur rrymën, mund të ndryshoni edhe drejtimin e saj. Në këtë rast, bëhet e mundur, në vend të dërgimit të rrymës dhe pauzave, të përdoret dërgimi i rrymës në dy drejtime të ndryshme si sinjale kryesore, ose të përdoren tre sinjale të ndryshme elementare me të njëjtën kohëzgjatje në të njëjtën kohë - dërgimi i rrymës në një drejtim. dërgimi i rrymës në drejtimin tjetër dhe pauza (kjo metodë e kodimit quhet kod tresh). Janë të mundshme edhe pajisje telegrafike edhe më komplekse, në të cilat dërgimet e rrymës ndryshojnë jo vetëm në drejtim, por edhe në fuqinë e rrymës; kështu kemi mundësinë që numrin e sinjaleve të ndryshme elementare ta bëjmë edhe më të madh. Rritja e numrit të çipave të ndryshëm e bën kodin më të ngjeshur. Megjithatë, ai gjithashtu ndërlikon dhe rrit koston e sistemit të transmetimit, kështu që kodet e ulëta të çipit janë ende të preferuara në art. Le të ketë një mesazh të shkruar duke përdorur një "alfabet" që përmban n "shkronja". Kërkohet të "kodohet" ky mesazh, d.m.th. tregoni një rregull që lidh çdo mesazh të tillë me një sekuencë specifike të m "çipave" të ndryshëm që përbëjnë "alfabetin" e transmetimit. Ne do ta konsiderojmë kodimin sa më fitimprurës, aq më pak sinjale elementare duhet të shpenzohen për transmetimin e një mesazhi. Nëse supozojmë se secili prej sinjaleve elementare zgjat të njëjtën kohë, atëherë kodi më i favorshëm do të lejojë që sasia më e vogël e kohës të shpenzohet në transmetimin e mesazhit. Prona kryesore ngjarje të rastësishmeështë mungesa e besimit të plotë në shfaqjen e tyre, gjë që krijon një farë pasigurie gjatë kryerjes së eksperimenteve që lidhen me këto ngjarje. Megjithatë, është mjaft e qartë se shkalla e kësaj pasigurie në raste të ndryshme do të jetë krejtësisht e ndryshme. Për praktikë, është e rëndësishme të jeni në gjendje të vlerësoni numerikisht shkallën e pasigurisë së një shumëllojshmërie të gjerë eksperimentesh në mënyrë që të jeni në gjendje t'i krahasoni ato nga kjo anë. Konsideroni dy përvoja të pavarura dhe si dhe një përvojë komplekse që përbëhet nga ekzekutimi i njëkohshëm eksperimente dhe. Lëreni që përvoja të ketë k rezultate të barabarta, dhe përvoja ka l rezultate të barabarta. Natyrisht, pasiguria e përvojës është më e madhe se pasiguria e përvojës, pasi këtu pasigurisë i shtohet edhe pasiguria e rezultatit të përvojës. Është e natyrshme të supozohet se shkalla e pasigurisë së përvojës është e barabartë me shumën e pasigurive që karakterizojnë eksperimentet, d.m.th.:. Vetëm një funksion i plotëson kushtet, kur -:. Konsideroni eksperimentin A, i përbërë nga përvoja dhe me probabilitete. Atëherë pasiguria totale për eksperimentin A do të jetë e barabartë.Ky numër i fundit do të quhet entropia e eksperimentit dhe do të shënohet me. Nëse numri i shkronjave në "alfabet" është i barabartë me n, dhe numri i sinjaleve elementare të përdorura është i barabartë me m, atëherë për çdo metodë kodimi numri mesatar i sinjaleve elementare për një shkronjë të alfabetit nuk mund të jetë më i vogël se; megjithatë, ai gjithmonë mund të bëhet në mënyrë arbitrare afër këtij raporti, nëse vetëm emërtimet individuale të kodeve krahasohen menjëherë me "blloqe" mjaft të gjata që përbëhen nga një numër i madh letra. Ne do të shqyrtojmë vetëm këtu rasti më i thjeshtë mesazhe të shkruara duke përdorur disa n "shkronja", frekuenca e shfaqjes së të cilave në çdo vend të mesazhit karakterizohet plotësisht nga probabilitetet p1, p2, ... ..., pn, ku, natyrisht, p1 + p2 + . .. + pn = 1, në të cilën probabiliteti pi manifestimet e i-të germat në çdo vend të mesazhit supozohen të jenë të njëjta, pavarësisht se cilat shkronja ishin në të gjitha vendet e mëparshme, d.m.th. shkronjat e njëpasnjëshme të mesazhit janë të pavarura nga njëra-tjetra. Në fakt, në mesazhet reale shpesh nuk ndodh kështu; në veçanti, në gjuhën ruse, probabiliteti i shfaqjes së një letre të veçantë varet ndjeshëm nga shkronja e mëparshme. Megjithatë, shqyrtimi i rreptë i varësisë së ndërsjellë të shkronjave do t'i bënte shumë të vështira të gjitha konsideratat e mëtejshme, por nuk do të ndryshonte në asnjë mënyrë rezultatet e ardhshme. Tani për tani do të shikojmë kodet binare; përgjithësimi i rezultateve të marra në këtë rast për kodet që përdorin numër arbitrar Sinjalet elementare janë, si gjithmonë, jashtëzakonisht të thjeshta. Le të fillojmë me rastin më të thjeshtë të kodeve që shoqërojnë një emërtim të veçantë kodi - një sekuencë numrash 0 dhe 1 - me secilën "gërmë" të një mesazhi. Çdo kod binar për një alfabet me shkronja n mund të shoqërohet me një metodë për të gjetur një numër të fshehur x, që nuk e kalon n, duke përdorur pyetje për të cilat përgjigjet vetëm "po" (1) ose "jo" (0), gjë që na çon. te kodi binar. Për probabilitetet e dhëna p1, p2, ..., pn shkronja individuale, transmetimi i një mesazhi me shumë shkronja do të jetë kodi më ekonomik për të cilin, me këto probabilitete n vlera x, vlera mesatare e numrit të pyetjeve të bëra (shenjat binare: 0 dhe 1 ose sinjalet elementare ) rezulton të jetë më e vogla. Para së gjithash, numri mesatar i sinjaleve elementare binare në mesazhin e koduar për një shkronjë të mesazhit origjinal nuk mund të jetë më i vogël se H, ku H = - p1 log p1 - p2 log p2 - ... - pn log pn është entropia të përvojës që konsiston në njohjen e një shkronje të tekstit (ose, shkurt, vetëm entropinë e një shkronje). Nga kjo rrjedh menjëherë se për çdo metodë kodimi, për të shkruar një mesazh të gjatë me shkronja M, kërkohet të paktën MH e karaktereve binare dhe në asnjë mënyrë nuk mund të kalojë një bit. Nëse probabilitetet p1, p2, ... ..., pn nuk janë të gjitha të barabarta me njëra-tjetrën, atëherë H< log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв. 1.2 Коды Шеннона - Фано. Для удобства расположим все имеющиеся п букв в один столбик в порядке убывания вероятностей. Затем все эти буквы следует разбить на две группы - верхнюю и нижнюю - так, чтобы суммарная вероятность первой группы была наиболее близка к суммарной вероятности второй группы. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв второй группы - цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить на две части и в качестве второй цифры кодового обозначения мы будем использовать цифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ко второй из этих подгрупп. Затем, каждая из содержащих более одной буквы групп снова делится на две части возможно более близкой суммарной вероятности и т.д.; процесс повторяется до тех пор, пока мы не придем к группам, каждая из которых содержит по одной единственной букве. Такой метод кодирования сообщений был впервые предложен в 1948 - 1949 гг. независимо друг от друга Р. Фано и К. Шенноном; поэтому соответствующий код обычно называется кодом Шеннона - Фано. Так, например, если наш алфавит содержит всего шесть букв, вероятность которых (в порядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапе деления букв на группы мы отщепим лишь одну первую букву (1-я группа), оставив во второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-й группы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв, будет и далее последовательно делиться на части так, что каждый раз 1-я часть будет состоять лишь из одной буквы. № буквывероят-ностьразбиение на подгруппы (римские цифры обозначают номера групп и подгрупп)кодовое обозначение10,4} I 120,2} II} I 0130,2} II} I 00140,1} II} I 000150,05} II} I0000160,05} II00000 Табл.1 Аналогично предыдущему примеру разобран случай "алфавита", включающего 18 букв, имеющих следующие вероятности: 0,3; 0,2; 0,1 (2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2) № буквывероят-ностьразбиение на подгруппы кодовое обозначение10,3} I} I 1120,2} II 1030,1} II} I} I 01140,1} II} I 010150,05} II 010060,03} II} I} I} I 0011170,03} II 0011080,03} II} I 0010190,03} II 00100100,03} II} I} I 00011110,02} II} I 000101120,02} II 000100130,01} II} I} I 000011140,01} II} I0000101150,01} II0000100160,01} II} I 000001170,01} II} I0000001180,01} II0000000 Табл.2 Основной принцип, положенный в основу кодирования по методу Шеннона - Фано, заключается в том, что при выборе каждой цифры кодового обозначения мы стараемся, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью. Разумеется, количество цифр в emërtime të ndryshme në këtë rast, rezulton të jetë i ndryshëm (në veçanti, në të dytin nga shembujt e analizuar varion nga dy në shtatë), d.m.th., kodi Shannon - Fano është jouniform. Megjithatë, nuk është e vështirë të kuptohet se asnjë emërtim i kodit këtu nuk mund të jetë fillimi i një emërtimi tjetër më të gjatë; prandaj, mesazhi i koduar gjithmonë mund të deshifrohet në mënyrë të paqartë. Si rezultat, vlera mesatare e gjatësisë së një përcaktimi të tillë ende rezulton të jetë vetëm pak më shumë se vlera minimale e H e lejuar nga konsideratat e ruajtjes së sasisë së informacionit gjatë kodimit. Pra, për shembullin e një alfabeti me 6 shkronja të konsideruar më sipër, kodi më i mirë uniform përbëhet nga emërtime të kodit treshifror (sepse 22< 6 < 23), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона - Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно Это значение заметно меньше, чем 3, и не очень далеко от энтропии Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 24 < 18 < 25); в случае же кода Шеннона - Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины Особенно выгодно бывает кодировать по методу Шеннона - Фано не отдельные буквы, а сразу целые блоки из нескольких букв. Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда H = - 0,7 log0,7 - 0,3 log0,3 = 0,881... Применение метода Шеннона - Фано к исходному двухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь к простейшему равномерному коду буква вероятность кодовое обозначение А 0,7 1 Б 0,3 0 требующему для передачи каждой буквы одного двоичного знака - на 12% больше минимального достижимого значения 0,881 дв.зн./букву. Применяя же метод Шеннона - Фано к кодированию всевозможных двухбуквенных комбинаций (вероятность которых определяется правилом умножения вероятностей для независимых событий), мы придем к следующему коду: комбина- ция букв вероятность кодовое обозначение АА 0,49 1 АБ 0,21 01 БА 0,21 001 ББ 0,09 000 Среднее значение длины кодового обозначения здесь равно, так что на одну букву алфавита здесь приходится в среднем двоичных знаков - лишь на 3% больше значения 0,881 дв.зн./букву. Еще лучше результаты мы получим, применив метод Шеннона - Фано к кодированию трехбуквенной комбинации; при этом мы придем к следующему коду: комбина- ция букв вероятность кодовое обозначение ААА 0,343 11 ААБ 0,147 10 АБА 0,147 011 БАА 0,147 010 АББ 0,063 0010 БАБ 0,063 0011 ББА 0,063 0001 БББ 0,027 0000 Среднее значение длины кодового обозначения здесь равно 2,686, т.е. на одну букву текста приходится в среднем 0,895 двоичных знаков, что всего на 1,5% больше значения дв.зн./букву. В случае еще большей разницы в вероятностях букв А и Б приближение к минимально возможному значению Н дв.зн./букву может несколько менее быстрым, но оно проявляется не менее наглядно. Так, при р(А) = 0,89 и р(Б) = 0,11 это значение равно - 0,89 log0,89 - 0,11 log0,11 ≈ 0,5 дв.зн./букву, а равномерный код (равносильный применению кода Шеннона - Фано к совокупности двух имеющихся букв) требует затраты одного двоичного знака на каждую букву - в два раза больше. Нетрудно проверить, что применение кода Шеннона - Фано к всевозможным двухбуквенным комбинациям здесь приводит к коду, в котором на каждую букву приходится в среднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям - 0,55, а к четырехбуквенным блокам - в среднем 0,52 двоичных знаков - всего на 4% больше минимального значения 0,50 дв.зн./букву. 1.3 Коды Хафмана. Близок к коду Шеннона - Фано, но еще выгоднее, чем последний, так называемый код Хафмана. Построение этого кода опирается на простое преобразование используемого алфавита, называемое сжатием алфавита. Пусть мы имеем алфавит А, содержащий буквы, вероятности появления которых в сообщении соответственно равны; при этом мы считаем буквы расположенными в порядке убывания их вероятностей (или частот), т.е. полагаем, что. Условимся теперь не различать между собой две наименее вероятные буквы нашего алфавита, т.е. будем считать, что ап-1 и ап - это одна и та же буква b нового алфавита А1, содержащего теперь уже буквы и b (т.е. ап-1 или ап), вероятности появления которых в сообщении соответственно равны и рп-1 + рп. Алфавит А1 и называется полученным из алфавита А с помощью сжатия (или однократного сжатия). Расположим буквы нового алфавита А1 в порядке убывания их вероятностей и подвергнем сжатию алфавит А1; при этом мы придем к алфавиту А2, который получается из первоначального алфавита А с помощью двукратного сжатия (а из алфавита А1 - с помощью простого или однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего п - 2 буквы. Продолжая эту процедуру, мы будем приходить ко все более коротким алфавитам; после (п - 2)-кратного сжатия мы придем к алфавиту Ап-2, содержащему уже всего две буквы. Вот, например, как преобразуется с помощью последовательных сжатий рассмотренный выше алфавит, содержащий 6 букв, вероятности которых равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05: № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,40,40,40,40,620,20,20,20,40,430,20,20,20,240,10,10,250,050,160,05 Табл.3 Условимся теперь приписывать двум буквам последнего алфавита Ап-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита Aj, то буквам "предыдущего" алфавита Aj-1 (где, разумеется, А1-1 = А0 - это исходный алфавит А), сохранившимся и в алфавите Aj, мы пишем те же кодовые обозначения, которые они имели в алфавите Aj-1; двум же буквам a" и a"" алфавита Aj, "слившимся" в одну букву b алфавита Aj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце. (Табл.4) № буквыВероятностиисходный алфавит Асжатые алфавитыА1А2А3А410,4 00,4 00,4 0 0,4 00,6 120,2 100,2 100,2 100,4 11 0,4 030,2 1110,2 1110,2 1110,2 10 40,1 11010,1 11010,2 110 50,05 110010,1 1100 60,05 11000 Табл. 4 Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет gjendjen e përgjithshme: asnjë shenjë kodi nuk është këtu fillimi i një kodi tjetër, më të gjatë. Vini re gjithashtu se kodimi i një alfabeti të caktuar me metodën Huffman (si dhe me metodën Shannon - Fano) nuk është një procedurë e paqartë. Kështu, për shembull, në çdo fazë të ndërtimit të kodit, natyrisht, mund të zëvendësoni numrin 1 me numrin 0 dhe anasjelltas; me këtë marrim dy kode të ndryshme(shumë të parëndësishëm të ndryshëm nga njëri-tjetri). Por përveç kësaj, në disa raste, është e mundur të ndërtohen disa kode Huffman dukshëm të ndryshme; Kështu, për shembull, në shembullin e zbërthyer më sipër, mund të ndërtoni një kod në përputhje me tabelën e mëposhtme: Numri i shkronjave Probabilitetet alfabeti origjinal Alfabetet e ngjeshur A1A2A3A410.4 110.4 110.4 11 0.4 00.6 120.2 010.2 1100.400. 1000.1 1010.2 00 50.05 10110.1 100 60.05 1010 Tabela 5 kod i ri është gjithashtu një kod Huffman, por gjatësia e emërtimeve ekzistuese të kodit tani rezulton të jetë krejtësisht e ndryshme. Vini re se numri mesatar i sinjaleve elementare për shkronjë është saktësisht i njëjtë për të dy kodet e ndërtuara Huffman: në rastin e parë, është i barabartë, dhe në të dytën, është i barabartë. Mund të tregohet se kodi Huffman është gjithmonë më ekonomiki nga të gjithë të mundshmit në kuptimin që për asnjë metodë tjetër të kodimit të shkronjave të një alfabeti të caktuar, numri mesatar i sinjaleve elementare për shkronjë mund të jetë më i vogël se ai që merret gjatë kodimit nga Metoda Huffman (nga kjo, natyrisht, menjëherë rrjedh se për çdo dy kode Huffman gjatësia mesatare e përcaktimit të kodit duhet të jetë saktësisht e njëjtë - në fund të fundit, të dyja janë më ekonomike). Arsyetimi i dhënë në paragrafët 1.2 dhe 1.3 zbatohet plotësisht gjatë zgjidhjes së problemeve (një shembull i një problemi të tillë është dhënë në Shtojcën A). 2. Entropia e llojeve të veçanta të mesazheve. 2.1 Teorema kryesore rreth kodimit. Shkalla e afërsisë së numrit mesatar të karaktereve binare për një shkronjë të mesazhit me vlerën e H të arritur në shembujt e konsideruar më sipër mund të rritet më tej në mënyrë arbitrare duke kaluar në kodimin e blloqeve gjithnjë e më të gjata. Kjo rrjedh nga pohimi i përgjithshëm vijues, të cilin më tej do ta quajmë teorema kryesore e kodimit, më saktë, teorema kryesore e kodimit në mungesë të interferencës: kur kodojmë një mesazh të ndarë në blloqe me shkronja N, duke zgjedhur N mjaftueshëm të madh, mund të arrihet që numri mesatar i çipave binare për shkronjën e mesazhit origjinal të ishte arbitrarisht afër H. Kodimi i blloqeve të gjata në të njëjtën kohë ka përparësi të konsiderueshme në prani të interferencave që pengojnë funksionimin e linjës së komunikimit. Duke pasur parasysh rëndësinë e madhe të teoremës kryesore të kodimit të formuluar këtu, më poshtë po paraqesim vërtetimin e saj bazuar në përdorimin e metodës së kodimit Shannon - Fano. Së pari, supozojmë se me metodën Shannon - Fano, e cila është baza e ndarjes sekuenciale të grupit të shkronjave të koduara (me të cilat mund të kuptohen edhe "blloqe" të tëra) në grupe gjithnjë e më të vogla, çdo herë arrijmë të sigurojmë që probabilitetet e dy grupeve që rezultojnë janë saktësisht të barabarta me njëri-tjetrin ... Në këtë rast, pas ndarjes së parë, vijmë në grupe me probabilitet të përgjithshëm 1/2, pas të dytës - në grupe me probabilitet të përgjithshëm 1/4, ..., pas ndarjes së 1-të - në grupe me një probabiliteti total prej 1/2l. Në këtë rast, përcaktimi i kodit l do të ketë ato shkronja që rezultojnë të ndahen në një grup prej një elementi pikërisht pas ndarjeve l; me fjalë të tjera, nëse ky kusht plotësohet, gjatësia li e përcaktimit të kodit do të lidhet me probabilitetin pi të shkronjës përkatëse me formulën B. rast i përgjithshëm sasia - log pi, ku pi - probabiliteti i i-të shkronja e alfabetit, nuk do të jetë një numër i plotë, prandaj gjatësia li e kodit shënimi i-të shkronjat nuk mund të jenë të barabarta me log pi. Meqenëse kur kodojmë me metodën Shannon - Fano, ne e ndajmë në mënyrë sekuenciale alfabetin tonë në grupe sa më afër probabilitetit total, gjatësia e përcaktimit të kodit të shkronjës i-të me një kodim të tillë do të jetë afër - log pi. Në lidhje me këtë, ne shënojmë me li numrin e parë të plotë jo më pak se - log pi: (A) Pabarazia e fundit mund të rishkruhet si më poshtë: ose (B) Këtu vërejmë se në rastin e çdo n numri që plotëson pabarazinë, ( 1) ekziston një kod binar për të cilin këta numra janë gjatësia e emërtimeve të kodit që lidhen me n shkronja të një alfabeti të caktuar. Mesatare l sinjale binare për një shkronjë të mesazhit origjinal (ose gjatësia mesatare e përcaktimit të kodit) jepet nga shuma. Tani shumëzojmë pabarazinë (A) duke dhënë vlerën li me pi, mbledhim të gjitha pabarazitë e marra në këtë mënyrë që korrespondojnë me vlerat i = 1, 2, ..., n dhe marrim parasysh se ku është entropia e eksperimentit që konsiston në përcaktimin e një shkronje të mesazhit, dhe atë p1 + p2 + ... + pn = 1. Si rezultat, ne marrim atë. Le ta zbatojmë këtë pabarazi në rastin kur metoda e përshkruar më sipër përdoret për të koduar të gjitha blloqet e mundshme me shkronja N (të cilat mund të konsiderohen shkronja të alfabetit të ri). Në bazë të supozimit për pavarësinë e shkronjave të njëpasnjëshme të mesazhit, entropia e eksperimentit, e cila konsiston në përcaktimin e të gjitha shkronjave të bllokut, është për rrjedhojë, gjatësia mesatare lN e përcaktimit të kodit të një blloku me shkronja N plotëson pabarazitë Por kur kodoni blloqe me shkronja N menjëherë, numri mesatar l i sinjaleve elementare binare për një shkronjë të mesazhit do të jetë i barabartë me gjatësinë mesatare lN të përcaktimit të kodit të një blloku të ndarë me numrin N shkronja në bllok :. Prandaj, me një kodim të tillë, domethënë këtu numri mesatar i sinjaleve elementare për shkronjë ndryshon nga vlera minimale e H jo më shumë se. Duke supozuar, menjëherë vijmë te teorema kryesore rreth kodimit. Prova e mësipërme mund të zbatohet edhe për rastin më të përgjithshëm kur shkronjat e njëpasnjëshme të tekstit varen reciprokisht. Në këtë rast, ju duhet vetëm të shkruani pabarazinë për vlerën lN në formën, ku është entropia e bllokut me shkronja N, e cila në rastin e varësisë së shkronjave të mesazhit nga njëra-tjetra do të jetë gjithmonë më e vogël se NH (për dhe). Nga kjo rrjedh se, pra, në këtë rast më të përgjithshëm (me një rritje të pakufizuar të gjatësisë së blloqeve) numri mesatar i sinjaleve elementare të shpenzuara për transmetimin e një shkronje po i afrohet pafundësisht vlerës ku ka "entropi specifike". për një shkronjë të një teksti me shumë shkronja. Ekzistenca e një kufiri rrjedh nga pabarazitë që tregojnë se një sekuencë është një sekuencë monotonike jo rritje e numrave pozitivë (0 i madh). Të gjitha deklaratat e mëparshme barten lehtësisht në rastin e kodeve t-ary duke përdorur sinjale t elementare. Pra, për të ndërtuar kodet m-ary Shannon - Fano, duhet vetëm të ndahen grupet e simboleve jo në dy, por në m pjesë sa më afër që të jetë e mundur, dhe për të ndërtuar një kod t-ary Huffman, duhet përdorur funksioni i ngjeshja e alfabetit, në të cilin çdo herë nuk bashkohen dy, dhe m shkronja të alfabetit origjinal që kanë më pak probabilitete. Duke pasur parasysh rëndësinë e kodeve Huffman, le të ndalemi pak më në detaje në pyetjen e fundit. Kompresimi i alfabetit, në të cilin shkronjat m zëvendësohen me një, çon në një ulje të numrit të shkronjave me m - 1; meqenëse për të ndërtuar një kod t-ary, natyrisht, kërkohet që sekuenca e "kontraktimeve" në fund të na çojë në një alfabet me m shkronja (të lidhura me sinjalet m të kodit), është e nevojshme që numri n shkronja të alfabeti fillestar mund të përfaqësohet në formën n = m + k (m - 1), ku k është një numër i plotë. Megjithatë, kjo mund të arrihet gjithmonë duke shtuar, nëse është e nevojshme, në alfabetin origjinal edhe disa "shkronja mashtruese", probabilitetet e të cilave llogariten. e barabartë me zero... Pas kësaj, ndërtimi i një kodi t-ary Huffman dhe vërtetimi i optimalitetit të tij (ndër të gjitha kodet t-ary) kryhen saktësisht në të njëjtën mënyrë si në rastin. kodi binar... Kështu, për shembull, në rastin e alfabetit të konsideruar tashmë më lart prej 6 shkronjash, të cilat kanë probabilitete 0.4, 0.2, 0.2, 0.1, 0.05 dhe 0.05 për ndërtimin e kodit tresh të Huffman, duhet t'i shtojmë alfabetit tonë edhe një shkronjë. me probabilitet zero dhe më pas veproni si më poshtë: Numri i përcaktimeve të shkronjave dhe kodeve të probabilitetit alfabetet origjinale të ngjeshur 10.4 00.4 00.4 020.2 20.2 20.4 130.2 100.2 100.2 240, 1 15101 është e lehtë për t'u kryer. 1 1101. mbi rastin e kodeve t-ary dhe në vërtetimin e mësipërm të teoremës kryesore të kodimit. Në veçanti, modifikimi përkatës bazohet në faktin se çdo n numër l1, l2, ..., ln që plotëson pabarazinë janë gjatësia e emërtimit të kodit të disa kodeve t-ar për një alfabet me shkronja n. Duke përsëritur arsyetimin për rastin m = 2, është e lehtë të merret rezultati i mëposhtëm (i quajtur teorema kryesore e kodimit për kodet t-ary): për çdo metodë kodimi duke përdorur një kod t-ary, numri mesatar i çipave për shkronjë mesazhi nuk mund të jetë kurrë më i vogël se raporti (ku H është entropia e një shkronje të mesazhit); megjithatë, ajo gjithmonë mund të bëhet në mënyrë arbitrare afër kësaj vlere nëse "blloqe" mjaft të gjata me shkronja N janë të koduara menjëherë. Prandaj, është e qartë se nëse sinjalet elementare L (duke marrë m vlera të ndryshme) mund të transmetohen përmes një linje komunikimi për njësi të kohës, atëherë shpejtësia e transmetimit të mesazhit në një linjë të tillë nuk mund të jetë më e madhe se shkronjat/njësia. koha; megjithatë, transmetimi me një shpejtësi arbitrare afër v (por më pak se v!) është tashmë i mundur. Vlera në numëruesin e shprehjes për v varet vetëm nga vetë linja e komunikimit (ndërsa emëruesi H karakterizon mesazhin e transmetuar). Kjo vlerë tregon numri më i madh njësi informacioni që mund të transmetohen përgjatë linjës sonë për njësi të kohës (sepse një sinjal elementar, siç e dimë, mund të përmbajë më së shumti log m njësi informacioni); quhet gjerësia e brezit të linjës së komunikimit. Koncepti gjerësia e brezit luan rol i rendesishem në teorinë e komunikimit. 2.2 Entropia dhe informacioni i llojeve specifike të mesazheve. 2.2.1 Të folurit me shkrim Për të transmetuar një mesazh me shkronja M që lejon m sinjale elementare të ndryshme, kërkohet të shpenzohen jo më pak se sinjalet, ku n është numri i shkronjave të "alfabetit". Meqenëse alfabeti telegrafik "rus" përmban 32 shkronja. (gërmat e dhe e nuk dallohen, b dhe b, por numërohen midis shkronjave dhe "gërma zero" është një hapësirë boshe midis fjalëve), atëherë sinjalet elementare duhet të shpenzohen për transmetimin e një mesazhi me shkronjën M. Teksti rus, me kusht që të gjitha shkronjat të konsiderohen njësoj të mundshme. Për të marrë një tekst në të cilin secila shkronja përmban 5 pjesë informacioni, duhet të shkruani 32 shkronja në bileta të veçanta, t'i vendosni të gjitha këto bileta në një urnë dhe më pas t'i nxirrni një. nga një, çdo herë duke shkruar letrën e zgjatur dhe duke e kthyer biletën në koshin e plehrave dhe duke përzier përsëri përmbajtjen e saj. Pasi kemi bërë një eksperiment të tillë, arrijmë në një "frazë" si më poshtë: RYS Sigurisht, ky tekst ka shumë pak të përbashkëta me gjuhën ruse! Për një llogaritje më të saktë të informacionit të përmbajtur në një shkronjë të tekstit rus, duhet të dini probabilitetet e shfaqjes së shkronjave të ndryshme. Vlerat e përafërta të frekuencave të shkronjave individuale të gjuhës ruse janë mbledhur në tabelën e mëposhtme: letra relative. frekuenca - 0,175o 0,090e, d 0,072a 0,062 dhe 0,062t 0,053n 0,053s 0,045 shkronja relative frekuenca 0,040v 0,038l 0,035k 0,028m 0,026d 0,025p 0,023u 0,021 germa relative frekuenca 0,018y 0,016z 0,016b, b 0,014b 0,014g 0,013h 0,012y 0,010 shkronja relative frekuencat 0,009zh 0,007u 0,006sh 0,006ts 0,004sh 0,003e 0,003f 0,002 Nga një krahasim i kësaj vlere me vlerën Н0 = log 32 = 5 bit, mund të shihet se pamja e pabarabartë e shkronjave të ndryshme të alfabetit çon në një ulje të informacionit të përmbajtur në një shkronjë të tekstit rus me rreth 0,65 bit. . Zvogëlimi i numrit të sinjaleve elementare të kërkuara mund të tregohet duke koduar shkronjat individuale të alfabetit rus duke përdorur metodën Shannon-Fano: kodi alfabetik. kodi i shkronjës emërtuese kodi i shkronjës emërtuese obozn.111k01000h0000100a1010l01001ts00000010b000101m00111ch000011v01010n0111sh00000011g000100o110sch00000001d001101p001100y001000e, o1011r01011,00111t1000yu00000010i1001Tabela 8 Numri mesatar i patate të skuqura në këtë metodë e coding është e njëjtë, atëherë nuk do të jetë shumë afër vlerës në përcaktimin eksperimentin entropisë ishte për të përcaktuar një letër tekstin rus, ne e konsideronim të gjitha letrat e pavarur . Kjo do të thotë që për të hartuar një "tekst" në të cilin çdo shkronjë përmban pak informacion, duhet t'i drejtohemi ndihmës së një urne, në të cilën janë përzier me kujdes 1000 copë letre, 175 prej të cilave nuk kanë asgjë të shkruar. , 90 - shkronja o është shkruar, 72 - shkronja e, ..., më në fund, në 2 copa letre - shkronja f (shih tabelën 7). Duke nxjerrë copa letre nga një urnë e tillë një nga një, arrijmë në një "frazë" si më poshtë: YYNT TSIYAA OERV ODNG YUEMLOLIK ZBYA ENVTSHA. Kjo "frazë" është disi më e ngjashme me një fjalim kuptimplotë rus sesa ai i mëparshmi, por, natyrisht, është ende shumë larg nga një tekst i arsyeshëm. Pangjashmëria e frazës sonë me një tekst kuptimplotë shpjegohet natyrshëm me faktin se, në fakt, shkronjat e njëpasnjëshme të tekstit rus nuk janë aspak të pavarura nga njëra-tjetra. Kështu, për shembull, nëse dimë se një zanore është shkronja tjetër, atëherë probabiliteti që një shkronjë bashkëtingëllore të shfaqet në vendin tjetër rritet ndjeshëm; shkronja "ь" nuk mund të ndjekë në asnjë mënyrë një hapësirë ose një zanore; shkronjat "s", "I" ose "u" nuk mund të shfaqen pas shkronjës "h", por me shumë mundësi do të ketë një nga zanoret "and" dhe "e" ose bashkëtingëlloren "t", etj. Prania në Gjuha ruse e rregullsive shtesë që nuk merren parasysh në "frazën" tonë çon në një ulje të mëtejshme të shkallës së pasigurisë së një shkronje të tekstit rus. Për ta bërë këtë, është e nevojshme vetëm të llogaritet entropia e kushtëzuar e eksperimentit që konsiston në përcaktimin e një shkronje të tekstit rus, me kusht që të dimë rezultatin e eksperimentit, i cili konsiston në përcaktimin e shkronjës së mëparshme të të njëjtit tekst. Entropia e kushtëzuar përcaktohet nga formula e mëposhtme: ku p (-), p (a), p (b), ..., p (i) tregojnë probabilitetet (frekuencat) e shkronjave individuale të gjuhës ruse. Natyrisht, mund të thuhet paraprakisht se probabilitetet p (- -), p (nb) dhe shumë të tjera (për shembull, p (bb), p (- b), p (w), etj.) do të jenë e barabartë me zero. Mund të jemi të sigurt se entropia e kushtëzuar do të jetë më e vogël se entropia e pakushtëzuar. Vlera mund të specifikohet si "informacioni mesatar" i përfshirë në përcaktimin e rezultatit të përvojës së ardhshme. Ka 32 urna, të përcaktuara me 32 shkronja të alfabetit rus; secila prej urnave përmban copa letre në të cilat janë shkruar kombinime me dy shkronja, duke filluar me shkronjën e treguar në urnë, dhe numri i copave të letrës me çifte të ndryshme shkronjash është në proporcion me frekuencat (probabilitetet) e dy shkronjave përkatëse. -kombinimet e shkronjave. Përvoja konsiston në heqjen e përsëritur të copave të letrës nga urnat dhe shkrimin e shkronjës së fundit prej tyre. Në këtë rast, çdo herë (duke filluar nga e dyta), nga urna hiqet një copë letër, e cila përmban kombinimet që fillojnë me shkronjën e fundit të shkruar; pasi letra të jetë shkruar, pjesa e letrës kthehet në urnë, përmbajtja e së cilës përsëri përzihet plotësisht. Përvoja e këtij lloji të çon në një "frazë" si më poshtë: UMARONO KACH INSERTED BY DEW NYKH CARPET NEDARE. Tingulli i kësaj "fraze" është shumë më afër gjuhës ruse. Njohja e dy shkronjave të mëparshme zvogëlon më tej pasigurinë e eksperimentit që konsiston në përcaktimin e shkronjës tjetër, e cila reflektohet në pozitivitetin e diferencës, ku është "entropia e kushtëzuar e rendit të dytë": secila prej të cilave përmban copa letre që nisin. me të njëjtat dy shkronja (ose një eksperiment me një libër rus, në të cilin përsëritja e parë e kombinimit të fundit të shkruar tashmë me dy shkronja gjendet në mënyrë të rastësishme shumë herë dhe shkronja pas saj shkruhet) çon në një "frazë" si p.sh. sa vijon: NDËRSA Djersa e ROCKERIT NORMOZ GRADDALE NJOHURI TUAJ MUND TË KONI OBNIL, edhe më afër fjalimit rus se ai i mëparshmi. Në mënyrë të ngjashme, është e mundur të përcaktohet entropia që korrespondon me përvojën e përcaktimit të shkronjës së tekstit rus, me kusht që të njihen tre shkronjat e mëparshme. Ai konsiston në nxjerrjen e copave letre nga 323 urna me kombinime me katër shkronja (ose - një eksperiment i ngjashëm me eksperimentin e përshkruar më sipër me një libër rus), çon në një "frazë" si më poshtë: FUN TO GATE JO DRY DHE NEPO DHE CORKO. vlerat në N = 5.6, .... Është e lehtë të shihet se me një rritje në N, entropia HN vetëm mund të ulet. Nëse marrim gjithashtu parasysh që të gjitha vlerat HN janë pozitive, atëherë do të jetë e mundur të konkludohet nga kjo se vlera në priret në një kufi të caktuar. Tashmë e dimë se numri mesatar i sinjaleve elementare të nevojshme për të transmetuar një shkronjë të tekstit rus nuk mund të jetë më i vogël. Diferenca që tregon se sa më pak se uniteti është raporti i "entropisë kufizuese" me vlerën që karakterizon sa më shumë informacion, e cila mund të përmbahet në një shkronjë të alfabetit me një numër të caktuar shkronjash, Shannon e quajti tepricën e gjuhës. Teprica e gjuhës ruse (si dhe teprica e gjuhëve të tjera evropiane) tejkalon ndjeshëm 50%. Kjo do të thotë, mund të themi se zgjedhja e shkronjës tjetër të një teksti kuptimplotë përcaktohet më shumë se 50% nga struktura e vetë gjuhës dhe, për rrjedhojë, është e rastësishme vetëm në një masë relativisht të vogël. Teprica e R është një karakteristikë statistikore shumë e rëndësishme e një gjuhe, por vlera numerike e saj ende nuk është përcaktuar me saktësi të kënaqshme për asnjë gjuhë. Në lidhje me gjuhën ruse, në veçanti, ekzistojnë vetëm të dhëna për vlerat e sasive H2 dhe H3. Н0Н1Н2Н3log 32 = 54.353.523.01 (për plotësi, këtu kemi dhënë edhe vlerat e entropisë Н0 dhe Н1). Nga kjo mund të konkludohet vetëm se për gjuhën ruse, në fakt, vlera e R është shumë më e madhe se ky numër. Është e qartë se për të gjitha gjuhët që përdorin Alfabeti latin, informacioni maksimal Н0, i cili mund të bjerë në një shkronjë të tekstit, ka të njëjtin kuptim: bit (26 shkronja të ndryshme të alfabetit dhe "shkronja" e 27-të është një hapësirë boshe midis fjalëve). Duke përdorur tabelat e frekuencave relative të shkronjave të ndryshme në anglisht, gjermanisht, frëngjisht dhe spanjisht, mund të tregohet se entropia H1 për këto gjuhë është e barabartë (në bit): gjuha gjermanisht frëngjisht frëngjisht spanjisht Н14,034,103,963,98 Ne shohim se në të gjitha rastet, vlera e H1 është dukshëm më e vogël se H0 = log 27 4.76 bit, dhe vlerat e saj për gjuhë të ndryshme nuk janë shumë të ndryshëm nga njëri-tjetri. Vlerat e H2 dhe H3 për gjuhën angleze u llogaritën nga Shannon, ndërsa ai përdori tabelat e disponueshme të frekuencave në anglisht për kombinime të ndryshme me dy dhe tre shkronja. Duke marrë parasysh edhe statistikat për frekuencat e shfaqjes fjalë të ndryshme në anglisht, Shannon ishte në gjendje të vlerësonte përafërsisht vlerat e H5 dhe H8. Si rezultat, ai mori: Н0Н1 Н2Н3Н5Н84.764.03 3.323.10≈2.1≈1.9 Nga kjo mund të konkludojmë se për gjuhën angleze teprica e R është në çdo rast jo më pak se, d.m.th., kalon 60%. Numërimi i vlerave të H9, H10, etj. sipas formulës së njohur prej nesh është i pamundur, pasi llogaritja e H9 kërkon njohuri për probabilitetet e të gjitha kombinimeve me 9 shkronja, numri i të cilave shprehet me një 13-shifror. numër (triliona!). Prandaj, për të vlerësuar vlerat e HN në vlera të mëdha N duhet të jetë i kufizuar metodat indirekte... Le të ndalemi në një nga këto lloj metodash të propozuara nga Shannon. "Entropia e kushtëzuar" НN është një masë e shkallës së pasigurisë së përvojës, e cila konsiston në përcaktimin Shkronja N-të teksti, me kusht që shkronjat e mëparshme N - 1 të jenë të njohura për ne. Mund të vendoset lehtësisht një eksperiment për të gjetur shkronjën N-të: për këtë, mjafton të zgjidhni një fragment (N - 1) -alfat të një teksti kuptimplotë dhe të ftoni dikë të hamendësojë shkronjën tjetër. Një eksperiment i tillë mund të përsëritet shumë herë, dhe vështirësia për të gjetur shkronjën e N-të mund të vlerësohet duke përdorur vlerën mesatare QN të numrit të përpjekjeve të nevojshme për të gjetur përgjigjen e saktë. Është e qartë se sasitë QN të përcaktuara për kuptime të ndryshme N, janë disa karakteristika të strukturës statistikore të gjuhës, në veçanti, teprica e saj. Shannon kreu një seri eksperimentesh të ngjashme, në të cilat N mori vlerat 1, 2, 3, ..., 14, 15 dhe 100. Duke vepruar kështu, ai zbuloi se hamendja e shkronjës së 100-të nga 99 shkronjat e mëparshme ishte një detyrë shumë më e lehtë sesa të hamendësosh shkronjën e 15-të në 14-tën e mëparshme. Prandaj, mund të konkludojmë se H15 është dukshëm më i madh se H100, domethënë, se H15 ende nuk mund të identifikohet me vlerën kufizuese. Më pas, të njëjtat eksperimente u kryen në një material pak më të madh për N = 1, 2, 4, 8, 16, 32, 64, 128 dhe N ≈ 10,000. Н128) praktikisht nuk ndryshon nga Н10000, ndërsa "entropia e kushtëzuar "Н16 është edhe dukshëm më i madh se kjo vlerë. Kështu, mund të supozohet se me një rritje në N, vlera e HN zvogëlohet deri në vlerat N = 30, por me një rritje të mëtejshme në N, praktikisht nuk ndryshon; prandaj, në vend të "entropisë kufizuese" mund të flitet, për shembull, për entropinë e kushtëzuar H30 ose H40. Eksperimentet në gjetjen e shkronjave jo vetëm që na lejojnë të gjykojmë vlerë krahasuese entropitë e kushtëzuara HN për N të ndryshëm, por gjithashtu bëjnë të mundur mbylljen e vlerave të vetë HN. Sipas të dhënave të eksperimenteve të tilla, është e mundur të përcaktohet jo vetëm numri mesatar i përpjekjeve QN që kërkohen për të gjetur shkronjën e N-të të tekstit nga N - 1 paraardhës, por edhe probabiliteti (frekuenca) që shkronja të jetë e saktë. me mend nga përpjekja 1, 2, 3, ..., n-të (ku n = 27 është numri i shkronjave të alfabetit; QN =). Është e lehtë të kuptohet se probabilitetet janë të barabarta me probabilitetet e shkronjave të alfabetit, të renditura në rend zbritës të frekuencës. Në të vërtetë, nëse nuk dimë asnjë nga shkronjat para shkronjës x për t'u hamendësuar, atëherë është e natyrshme para së gjithash të supozojmë se x përkon me shkronjën më të zakonshme a1 (dhe probabiliteti për të hamendësuar saktë këtu do të jetë i barabartë me p (a1)); atëherë duhet supozuar se x përkon me a2 (probabiliteti i një përgjigjeje të saktë këtu do të jetë i barabartë me p (a2)) dhe kështu me radhë. Prandaj rrjedh se entropia e H1 është e barabartë me shumën. Nëse N> 1, atëherë mund të tregohet se shuma (*) nuk do të kalojë entropinë e kushtëzuar HN (kjo për faktin se vlerat përfaqësojnë në një mënyrë të caktuar probabilitetet mesatare të rezultateve të eksperimentit) . Nga ana tjetër, konsiderata disi më të ndërlikuara, në të cilat nuk do të ndalemi këtu, na lejojnë të vërtetojmë se shuma (**) për çdo N nuk do të jetë më e madhe se entropia e kushtëzuar НN. Kështu, shprehjet (*) dhe (**) (të përbëra nga probabilitete që mund të vlerësohen nga të dhënat eksperimentale) përcaktojnë kufijtë midis të cilëve duhet të shtrihet vlera e HN. Thjesht duhet të keni parasysh se të dy vlerësimet (*) dhe (**) merren me supozimin se këto janë probabilitetet e supozimit të një shkronje nga N - 1 shkronjat e mëparshme nga përpjekjet e para, të dyta, të treta, etj. janë marrë me supozimin se hamendësuesi gjithmonë emërton shkronjën tjetër në mënyrën më të përshtatshme - duke marrë parasysh të gjitha ligjet statistikore të kësaj gjuhe... Në rastin e përvojat realeçdo gabim në strategjinë e personit hamendësues (d.m.th., dallimet midis shkronjave që ai thërret dhe atyre që duhet të emërtohen bazuar në statistikat e sakta të gjuhës) do të çojë në mënyrë të pashmangshme në një mbivlerësim të shumave (*) dhe ( **); kjo është arsyeja pse këshillohet të merren parasysh vetëm të dhënat e "humendësuesit më të suksesshëm", pasi për të ky mbivlerësim do të jetë më i vogli. Meqenëse çdo person hamendësues ndonjëherë bën gabime, vlerësimi (**) në praktikë nuk mund të konsiderohet një vlerësim më i ulët plotësisht i besueshëm i entropisë së vërtetë (në ndryshim nga vlerësimi i sipërm (*), i cili, për shkak të gabimeve të hamendësuesit, mund të bëhet vetëm edhe më i madh). Për më tepër, vlerat e shumave (*) dhe (**), për fat të keq, nuk afrohen pafundësisht me rritjen e N (duke filluar nga N ≈ 30, këto shuma përgjithësisht pushojnë së varur nga N); prandaj, vlerësimet e tepricës së gjuhës të marra përgjatë kësaj rruge nuk do të jenë veçanërisht të sakta. Në veçanti, eksperimentet e Shannon treguan vetëm se vlera e H100 duket të jetë midis 0.6 dhe 1.3 bit. Prandaj, mund të konkludojmë se teprica për gjuhën angleze në rend të madhësisë duhet të jetë afër 80%. 2.2.2 Të folurit gojor. Tani i drejtohemi çështjes së entropisë dhe informacionit në të folurit gojor. Është e natyrshme të mendohet se të gjitha karakteristikat statistikore të një fjalimi të tillë do të varen edhe më shumë nga zgjedhja e njerëzve që flasin dhe nga natyra e bisedës së tyre. Vlera e reduktuar e entropisë së të folurit gojor mund të jetë për shkak të faktit se në një bisedë ne shpesh përdorim më shumë përsëritje të të njëjtave fjalë dhe shpesh shtojmë mjaft fjalë "ekstra" - kjo bëhet si për të lehtësuar perceptimin e të folurit. , dhe thjesht në mënyrë që folësi të ketë kohë të marrë parasysh atë që dëshiron të thotë më pas. Duke përcaktuar numrin mesatar të shkronjave të shqiptuara për njësi të kohës, mund të vlerësohet afërsisht sasia e informacionit të komunikuar gjatë një bisede në 1 sekondë; zakonisht është në rendin prej 5 deri në 6 bit. Nga biseda mund të gjykojmë gjendjen shpirtërore të folësit dhe qëndrimin e tij ndaj asaj që u tha; ne mund ta njohim folësin, edhe nëse asnjë burim tjetër informacioni nuk na e tregon atë; ne mund të përcaktojmë në shumë raste vendin e lindjes së një të huaji nga shqiptimi i tij; ne mund të vlerësojmë zërin e të folurit gojor, i cili në rastin e transmetimit të zërit përmes një linje komunikimi përcaktohet kryesisht në mënyrë të pastër karakteristikat teknike linjat e transmetimit, etj. Përcaktimi sasior i gjithë këtij informacioni është një detyrë shumë e vështirë që kërkon shumë më tepër njohuri të gjuhës. Një përjashtim në këtë drejtim është çështja relativisht e ngushtë e theksimeve logjike që theksojnë fjalët individuale në një frazë. Stresi më së shpeshti bie mbi fjalët më rrallë të përdorura (gjë që, megjithatë, është mjaft e natyrshme - është e qartë se vështirë se dikush do të theksojë elefantin më të zakonshëm me një stres logjik - për shembull, parafjalët ose lidhëzat). Nëse ka gjasa që fjalën e dhënë Wr është nën stres, e shënojmë me qr, atëherë informacioni mesatar, i cili përbëhet nga informacioni për praninë ose mungesën e stresit në këtë fjalë, do të jetë i barabartë. Le të jenë tani probabilitetet (frekuencat) e të gjitha fjalëve W1, W2,. ... ., WK (këtu K - numri total të gjitha fjalët e përdorura. Në këtë rast, për informacionin mesatar H, të mbyllur në një stres logjik, mund të shkruani formulën e mëposhtme: Informacioni mesatar që marrim duke gjetur se në cilat fjalë bie stresi logjik është afër rendit të madhësisë me 0,65 bit/fjalë. . Gjatë një bisede, shkronjat individuale nuk shqiptohen kurrë, por shqiptohen tinguj që janë dukshëm të ndryshëm nga shkronjat. Prandaj, elementi kryesor i fjalës gojore duhet të konsiderohet një tingull i veçantë - një fonemë. Gjuha e folur kuptimplote përbëhet nga fonema në të njëjtën mënyrë që gjuha e shkruar kuptimplote përbëhet nga shkronja. Prandaj, në të gjitha rastet kur na intereson vetëm transmetimi i “informacionit semantik” të fjalës gojore interesi më i madh nuk përfaqëson entropinë dhe informacionin e një "gërteje të folur", por entropinë dhe informacionin e një foneme të shqiptuar në të vërtetë. Lista e fonemave të një gjuhe të caktuar, natyrisht, nuk përkon me listën e shkronjave të alfabetit, pasi e njëjta shkronjë në raste të ndryshme mund të tingëllojë ndryshe. Ka 42 fonema të ndryshme në Rusisht dhe kanë numëruar frekuencat e fonemave individuale (si dhe kombinime të ndryshme dy dhe tre fonema të njëpasnjëshme). Н0 = log 42 i një foneme, entropia e rendit të parë (ku janë frekuencat relative të fonemave të ndryshme) dhe "entropia e kushtëzuar" Н2 dhe Н3: Н0Н1Н2Н3log 42 ≈ 5.38 4.77 3.62 0.70 Nëse i krahasojmë këto vlera prej Н0, Н1, Н2, H3 për fjalimin e shkruar rusisht, atëherë ulja e numrit të entropisë së kushtëzuar për fonemat ndodh dukshëm më shpejt sesa në rastin e shkronjave të tekstit të shkruar. Për të përcaktuar tepricën e R (fjalëve), mund të vendosni një marrëdhënie midis tepricave të të folurit dhe të shkruarit. Nga fakti se e folura gojore mund të regjistrohet dhe shkruhet - lexohet, rrjedh se "informacioni i plotë" që përmban një tekst i caktuar nuk varet nga forma në të cilën - me gojë apo me shkrim - paraqitet ky tekst, domethënë se . .. Prandaj rrjedh se ku është numri mesatar i shkronjave për fonemë ("gjatësia mesatare e fonemës"). Kjo vlerë është një karakteristikë e rëndësishme statistikore e gjuhës që lidh fjalën e folur dhe të shkruar. Nga formula e fundit rezulton gjithashtu se ose ku k është numri i përgjithshëm i fonemave dhe n është numri i shkronjave; sepse këtu është më e natyrshme të merret. Megjithatë, përdorimi i kësaj formule pengohet nga mungesa e të dhënave statistikore për të përcaktuar vlerën. 2.2.3 Muzika. Hulumtime të të njëjtit lloj mund të kryhen në lidhje me mesazhet muzikore. Është e natyrshme të mendohet se lidhjet ndërmjet tingujve të njëpasnjëshëm të një melodie të caktuar, të shprehura nga shenja individuale të notave, janë mjaft të forta: meqenëse disa kombinime tingujsh do të jenë më harmonikë se të tjerët, të parët do të gjenden në veprat muzikore më shpesh sesa kjo e fundit. Nëse shkruajmë një seri shënimesh në mënyrë të rastësishme, atëherë informacioni i përfshirë në secilin shënim të këtij regjistrimi do të jetë më i madhi; megjithatë, nga pikëpamja muzikore, një sekuencë kaq kaotike notash nuk do të kishte asnjë vlerë. Për të marrë një tingull të këndshëm, është e nevojshme të futim një tepricë të caktuar në gamën tonë; Në të njëjtën kohë, mund të frikësohet se në rastin e tepricës së tepërt, në të cilën notat e mëvonshme përcaktohen pothuajse pa mëdyshje nga ato të mëparshme, do të kemi vetëm muzikë jashtëzakonisht monotone dhe jointeresante. Cila është teprica në të cilën mund të merret muzika "e mirë"? Tepricë melodi të thjeshta asgjë më pak se teprica e të folurit kuptimplotë. Do të ishte e nevojshme të studiohej posaçërisht çështja e tepricës së formave të ndryshme vepra muzikore apo vepra të kompozitorëve të ndryshëm. Për shembull, analizoni një album popullor me këngë për fëmijë nga pikëpamja e teorisë së informacionit. Për thjeshtësi, kjo vepër ka supozuar se të gjithë tingujt janë brenda një oktave; meqenëse të ashtuquajturat kromatizma nuk ndodhën në meloditë në shqyrtim, të gjitha këto melodi mund të reduktohen në shtatë tinguj bazë; Do, re, mi, fa, sol, la dhe si, secili i teti në kohëzgjatje. Llogaritja e tingujve me kohëzgjatje më shumë se një e teta u krye duke shtuar në shtatë notat "elementin kryesor" të tetë O, i cili tregon zgjatjen e tingullit të mëparshëm për një periudhë tjetër kohore prej një të teti (ose një pauzë prej një e teta). Kështu, "entropia maksimale e mundshme" H0 e një note është këtu e barabartë me H0 = log 8 = 3 bit. Pasi kemi llogaritur frekuencat (probabilitetet) e notave individuale në të 39 këngët e analizuara, zbulojmë se duke përdorur probabilitetet e gjetura të kombinimeve të dy notave, mund të llogarisim edhe entropinë e kushtëzuar H2, rezulton të jetë afër 2.42. Vetëm nga vlerat e H1 dhe H2, shumë pak mund të thuhet për shkallën e tepricës së atyre të konsideruara, me sa duket, është dukshëm më e lartë se. Ky përfundim mbështetet nga kërkimet e shumë autorëve të njohur. 2.2.4 Transferimi imazhe televizive... Syri ynë është në gjendje të dallojë vetëm një numër të kufizuar shkallësh të shkëlqimit të një imazhi dhe vetëm pjesë jo shumë të afërta të tij, prandaj çdo imazh mund të transmetohet "pikë për pikë", secila prej të cilave është një sinjal që merr vetëm një numër të kufizuar. të vlerave. Është e nevojshme të merret parasysh një numër i konsiderueshëm (disa dhjetëra) gradimesh të shkallës së nxirjes ("shkëlqimit") të secilit element, përveç kësaj, 25 korniza zëvendësohen në ekranin e televizorit çdo sekondë, duke krijuar përshtypjen e "lëvizjes". ". Sidoqoftë, linja e komunikimit në fakt nuk transmeton rezultatin e eksperimentit, i cili konsiston në përcaktimin e vlerës së ndryshimit të vazhdueshëm nga pika në pikë, në kohë, dhe ngjyrën ose shkëlqimin e imazhit, por rezultatin e një ndryshimi krejtësisht të ndryshëm ". eksperiment i kuantizuar", i cili konsiston në përcaktimin e ngjyrës (e bardhë ose e zezë) ose ndriçimit të shkallëzimit në një numër të kufizuar "pikash". Kjo përvojë e re tashmë mund të ketë vetëm një numër të kufizuar rezultatesh, dhe ne mund të matim entropinë e saj H. Numri i përgjithshëm i elementeve ("pikave") për televizionin bardh e zi, në të cilin imazhi duhet të zbërthehet, përcaktohet kryesisht. nga e ashtuquajtura "fuqi zgjidhëse" e syrit, domethënë aftësia e tij për të dalluar zonat e afërta të imazhit. Në televizionin modern, ky numër është zakonisht në rendin e disa qindra mijëra (në programet televizive sovjetike, imazhi i zbërthyer në 400,000 - 500,000 elementë, në amerikan - me rreth 200,000 - 300,000, në programet e disa qendrave televizive franceze dhe belge - - me pothuajse 1,000,000) ... Është e lehtë të kuptohet se për këtë arsye entropia e një imazhi televiziv është e madhe. Edhe nëse supozojmë se syri i njeriut dallon vetëm 16 shkallë të ndryshme të shkëlqimit (vlera është qartësisht e nënvlerësuar) dhe se imazhi zbërthehet në vetëm 200,000 elementë, atëherë gjejmë se "entropia e rendit zero" këtu është e barabartë me Н0 = log 16,200,000 = 800,000 bit. Vlera e entropisë së vërtetë H, natyrisht, do të jetë më e vogël, pasi imazhi televiziv ka një tepricë të konsiderueshme. Gjatë llogaritjes së vlerës së H0, supozuam se vlerat e shkëlqimit në çdo dy "pika" të figurës janë të pavarura nga njëra-tjetra, ndërsa në fakt, shkëlqimi zakonisht ndryshon shumë pak kur shkon në elementet fqinje imazh i njëjtë (ose edhe i ndryshëm, por i afërt në kohë). Kuptimi vizual i kësaj teprice R është se midis 16,200,000 kombinimeve tona të mundshme të vlerave të ndriçimit në të gjitha pikat e ekranit, kombinimet kuptimplote që mund të quhen "imazhe" do të përbëjnë vetëm një pjesë të parëndësishme, dhe pjesa tjetër do të jetë plotësisht e çrregullt. grumbullimi i pikave me shkëlqim të ndryshëm.shumë larg çdo “komplote”. Ndërkohë, "shkalla e vërtetë e pasigurisë" H e imazhit televiziv duhet të marrë parasysh vetëm ato kombinime të vlerave të shkëlqimit që kanë të paktën disa mundësi për t'u transmetuar. Për të përcaktuar vlerën e saktë të entropisë H (ose tepricës R) të një imazhi televiziv, është e nevojshme të studiohen në detaje marrëdhëniet statistikore midis shkëlqimit të pikave të ndryshme në ekran. Kështu, vlerat e entropive H0, H1, H2 dhe H3 u gjetën për dy imazhe specifike televizive, e para prej të cilave (imazhi A - një park me pemë dhe ndërtesa) ishte më komplekse, dhe e dyta (imazhi B - një galeri mjaft e errët me kalimtarë) ishte më monokromatike për nga ngjyra dhe përmbante më pak detaje, duke dalluar 64 shkallë të ndryshme të ndriçimit të një elementi të një imazhi televiziv, pra entropinë H0 (i referohet një elementi dhe jo të gjithë imazhit si një e tërë) këtu doli të jetë e barabartë me H0 = log 64 = 6 bit. Më pas, duke përdorur një pajisje të veçantë radio, frekuencat relative (probabilitetet) e të gjitha gradimeve të dallueshme të ndriçimit u llogaritën për të dy imazhet në shqyrtim dhe përcaktuan "entropinë e rendit të parë". E njëjta pajisje radio më pas u përdor për të llogaritur frekuencat relative pij të çifte elementësh ngjitur (horizontalisht) nga të cilët elementi i parë ka një vlerë dmth të ndriçimit, dhe e dyta j-e, si dhe frekuencat relative pijk të trefishave të elementeve fqinjë (gjithashtu vetëm horizontalisht), në të cilët elementi i parë kishte vlerën e ndriçimit i-e, i dyti j-e dhe e treta kth(numrat i, j dhe k kaluan nëpër të gjitha vlerat nga 1 në 64). Këto frekuenca bënë të mundur përcaktimin e "entropive të eksperimenteve komplekse" dhe më pas "entropive të kushtëzuara" dhe e fundit në të cilën, megjithatë, u llogarit vetëm për imazhin B. Rezultatet e marra janë përmbledhur në tabelën e mëposhtme: , 91.5 Teprica R, e vlerësuar nga vlera e H2 për imazhin A është 44%, dhe për imazhin B - 68%; vlera aktuale mund të ketë vetëm më shumë tepricë se kjo. Sa i përket entropisë së kushtëzuar H3 për shkëlqimin e njohur të dy elementëve të mëparshëm të së njëjtës linjë, ajo ndryshon relativisht pak nga H2 (imazhi B, 75%); nga kjo mund të konkludojmë se njohja e shkëlqimit të elementit më të afërt përcakton një pjesë shumë të madhe të tepricës totale. Një tjetër eksperiencë që mbështetet në ndarje ka gjithashtu një karakter të ngjashëm. vlerat e mundshme shkëlqimi i një elementi të figurës televizive me 8, jo me 64 shkallë, për të cilat u llogaritën entropitë H0 dhe H1 dhe një numër entropish të kushtëzuara H2, H3 dhe H4 të një elementi fotografik për katër parcelat e mëposhtme sportive televizive: A - vrapim i shpejtë lojtarët e basketbollit, B - fytyra e një spektatori nga afër në tribunën e stadiumit, C - panoramë e pamjes së spektatorëve në tribunë dhe D - futbollistë me vrap të shpejtë. Ne do të shënojmë me numrat 1 dhe 2 elementët e imazhit ngjitur me të dhënat horizontalisht dhe vertikalisht, me numrin 3 - elementin ngjitur diagonalisht, me numrin 4 - të njëjtë me atë në shqyrtim, elementin në kornizën e mëparshme të transmetimi televiziv, me numrin 5 - elementi në të njëjtën horizontale , ngjitur me elementin 1, dhe, së fundi, numri 6 - i njëjti element në kornizën që i paraprin atij që përmban elementin 4 (Fig. 1), a) b ) Fig. 1.dhe do të tregojmë në shënimin e entropive të kushtëzuara nga lart në kllapa numrin e imazheve të elementeve, shkalla e ndriçimit të të cilave konsiderohet e njohur. Në këtë rast, vlerat e entropisë (në bit) mund të përmblidhen në tabelën e mëposhtme: A31,960,690,98-1,77B31,950,360.36 - B32,781,341,952.78-G32.45-2.002.08 A0. , 56 - B0.35-0.270.26-B - 1.221.181.19G-1.83 --- Rezultatet e eksperimentit të fundit çojnë në përfundimin se për imazhin e varfër në detaje ("fytyrë") teprica nuk është më pak se 90%, dhe për një imazh të pasur me detaje ("shikues"), është jo më pak se 60%. Arsyet për këtë mospërputhje janë ende të paqarta. Për fotot televizive me ngjyra, informacioni është në rend të madhësisë i krahasueshëm me informacionin e dyfishuar që gjendet në foton bardh e zi përkatëse. PËRFUNDIM Në këtë punim u vendosën synimet dhe objektivat e mëposhtëm. Qëllimi: të studiohen parimet e kodimit të informacionit të Shannon - Fano dhe Huffman dhe aplikimi i tyre në zgjidhjen e problemeve. Objektivi: të studiohet entropia dhe teprica e llojeve specifike të mesazheve për zbatimin e mëvonshëm të parimeve të Shannon - Fano dhe Huffman për to. Pas përfundimit të qëllimeve dhe objektivave tezë u bënë konkluzionet e mëposhtme. Para shfaqjes së veprave të Shannon dhe Fano, kodimi i karaktereve të alfabetit gjatë transmetimit të një mesazhi përmes kanaleve të komunikimit kryhej me të njëjtin numër bitesh, të marra nga formula Hartley. Me ardhjen e këtyre veprave, filluan të shfaqen metoda që kodojnë personazhet me një numër të ndryshëm bitësh, në varësi të mundësisë së paraqitjes së tyre në tekst, domethënë personazhet më të mundshëm kodohen me kode të shkurtra, dhe karakteret e rralla kodohen me të gjata (më të gjata se mesatarja). Që kur D.A. Huffman publikoi veprën e tij "Metoda për ndërtimin e kodeve me tepricë minimale" në vitin 1952, algoritmi i tij i kodimit është bërë baza për sasi e madhe kërkime të mëtejshme në këtë fushë. Vlen të përmendet se mbi 50 vjet nga data e publikimit, kodi Huffman nuk e ka humbur fare rëndësinë dhe rëndësinë e tij. Pra, mund të themi me besim se jemi përballur me të, në një formë ose në një tjetër (fakti është se kodi Huffman përdoret rrallë veçmas, më shpesh duke punuar në lidhje me algoritme të tjera), pothuajse çdo herë që arkivojmë skedarë, shikojmë foto , filma, dërgimi i një faksi ose dëgjimi i muzikës. Përparësitë e këtyre metodave janë lehtësia e dukshme e zbatimit dhe, si pasojë, shpejtësi e lartë kodimi dhe deshifrimi. Disavantazhi kryesor është se ato nuk janë optimale në rastin e përgjithshëm. 3
Konsideroni algoritmin për llogaritjen e kodeve Shannon-Fano (për qartësi, le të marrim sekuencën "aa bbb cccc ddddd" si shembull). Për të llogaritur kodet, duhet të krijoni një tabelë me simbole unike të mesazheve c (i) dhe probabilitetet e tyre p (c (i)), dhe renditni atë në rend jo rritje të probabilitetit të simbolit.
| c (i) | p (c (i)) |
| d | 5 / 17 |
| c | 4 / 17 |
| hapësirë | 3 / 17 |
| b | 3 / 17 |
| a | 2 / 17 |
Më tej, tabela e simboleve ndahet në dy grupe në mënyrë që secili prej grupeve të ketë afërsisht të njëjtën frekuencë në shumën e simboleve. Grupi i parë vendoset në fillim të kodit në "0", i dyti në "1". Për të llogaritur pjesët vijuese të kodeve të karaktereve, kjo procedurë përsëritet në mënyrë rekursive për çdo grup që përmban më shumë se një karakter. Kështu, për rastin tonë, marrim kodet e mëposhtme të karaktereve:
Gjatësia e kodit s (i) në tabelën që rezulton është int (-lg p (c (i))), nëse sivolet mund të ndahen në grupe me të njëjtën frekuencë përndryshe, gjatësia e kodit është int (-lg p (c (i))) + 1.
39 bit i gjatë. Duke marrë parasysh që origjinali ishte 136 bit, marrim një raport kompresimi prej ~ 28% - jo aq i keq.
Duke parë sekuencën që rezulton, lind pyetja: "Si mund ta heqësh këtë tani?" Ne nuk mundemi, si në rastin e kodimit, të zëvendësojmë çdo 8 bit të rrymës hyrëse me një kod me gjatësi të ndryshueshme. Kur dekompresojmë, duhet të bëjmë të kundërtën - të zëvendësojmë kodin me gjatësi të ndryshueshme me një karakter 8-bit. V në këtë rast, do të ishte mirë të përdorni një pemë binare, gjethet e së cilës do të jenë simbole (analoge me pemën Huffman).
Kodimi Shannon-Fano është një metodë mjaft e vjetër e kompresimit dhe sot nuk është me interes të veçantë praktik (përveç si një ushtrim në rrjedhën e strukturave të të dhënave). Në shumicën e rasteve, gjatësia e sekuencës së ngjeshur, sipas kësaj metode, është e barabartë me gjatësinë e sekuencës së ngjeshur duke përdorur kodimin Huffman. Por në disa sekuenca, kodet jo optimale Shannon-Fano janë ende të formuara, prandaj, kompresimi me metodën Huffman konsiderohet të jetë më efikas. Për shembull, merrni parasysh një sekuencë me përmbajtjen e mëposhtme të karaktereve: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Metoda Huffman e ngjesh atë në 77 bit , por Shannon-Fano deri në 79 bit.
|
Si u ndamë në grupe? Mjaft e thjeshtë:
Për shkak të kësaj paqartësie, disa njerëz madje kanë mendime të tilla: "... programi ndonjëherë cakton për disa simbole ..." dhe kështu me radhë - duke arsyetuar për gjatësinë e kodeve. Nëse nuk jeni duke shkruar AI, atëherë një gjë e tillë si "programi ndonjëherë" bën diçka tingëllon qesharake. Një algoritëm i zbatuar saktë funksionon në mënyrë rigoroze.
I njëjti mesazh mund të kodohet menyra te ndryshme... Kodi më i favorshëm është ai që shpenzon më pak kohë në transmetimin e mesazhit. Nëse transmetimi i secilit element të karakterit (për shembull, 0 ose 1) merr të njëjtën kohë, atëherë kodi optimal do të jetë i tillë që kur përdoret për të transmetuar një mesazh gjatësia e dhënë do të shpenzohet numri minimal i karaktereve elementare. Shannon - Kodet Fano janë prefiks, d.m.th. nr fjalen e koduar nuk është një parashtesë e ndonjë tjetër. Kjo pronë lejon dekodimin e qartë të çdo sekuence fjalësh kodike
Le të shqyrtojmë parimin e ndërtimit të një prej algoritmeve të para të kompresimit, i cili u formulua nga shkencëtarët amerikanë Shannon dhe Fano duke përdorur shembullin e shkronjave të alfabetit rus. Algoritmi përdor kode me gjatësi të ndryshueshme, d.m.th. një karakter i zakonshëm është i koduar me një kod me gjatësi më të shkurtër, një karakter i rrallë - një kod më i gjatë.
Për të krijuar një kod të tillë, padyshim, duhet të dini shpeshtësinë e shfaqjes së shkronjave në tekstin rus. Këto frekuenca janë paraqitur në tabelën 1. Shkronjat në tabelë janë renditur në rend zbritës të frekuencës.
Tabela 1
Frekuenca e shfaqjes së shkronjave të alfabetit rus
Duke përdorur tabelën, mund të hartoni kodin më ekonomik bazuar në konsideratat që lidhen me informacionin. Natyrisht, kodi do të jetë më ekonomik kur çdo karakter elementar do të transmetojë informacion maksimal... Konsideroni një simbol elementar (d.m.th., që përfaqëson sinjalin e tij) si sistemi fizik me dy gjendje të mundshme: 0 dhe 1. Informacioni që jep ky simbol është i barabartë me entropinë e këtij sistemi dhe është maksimal në rastin kur të dyja gjendjet janë njësoj të mundshme; në këtë rast, simboli elementar përcjell informacionin 1 (binar). Prandaj, baza për kodimin optimal do të jetë kërkesa që karakteret elementare në tekstin e koduar të ndodhin mesatarisht po aq shpesh.
Ideja e kodimit është që karakteret e koduara (shkronjat ose kombinimet e shkronjave) të ndahen në dy grupe afërsisht njësoj të mundshme: për grupin e parë të karaktereve, vendi i parë i kombinimit është 0 (karakteri i parë i numrit binar që përfaqëson personazhin); për grupin e dytë - 1. Më tej, çdo grup ndahet sërish në dy nëngrupe afërsisht të mundshme; për simbolet e nëngrupit të parë, 0 vendoset në vendin e dytë; për nëngrupin e dytë - një, etj.
Le të demonstrojmë parimin e ndërtimit të kodit Shannon-Fano duke përdorur shembullin e materialit të alfabetit rus (shih Tabelën 1). Le të numërojmë gjashtë shkronjat e para (nga "-" në "t"); duke përmbledhur probabilitetet (frekuencat) e tyre, marrim 0.498; të gjitha shkronjat e tjera nga "n" në "f" do të kenë përafërsisht të njëjtën probabilitet prej 0,502. Gjashtë shkronjat e para (nga "-" në "t") do të kenë në radhë të parë shenjën binare 0. Pjesa tjetër e shkronjave (nga "n" në "f") do të kenë në radhë të parë 1. Më tej, ne do ta ndajmë përsëri grupin e parë në dy nëngrupe afërsisht të mundshëm: nga "-" në "o" dhe nga "e" në "t"; për të gjitha shkronjat e nëngrupit të parë në vendin e dytë vendosim zero, dhe nëngrupin e dytë - një. Ne do të vazhdojmë procesin derisa të ketë saktësisht një shkronjë në çdo nënndarje, e cila do të jetë e koduar në një të caktuar numër binar... Mekanizmi i ndërtimit është paraqitur në tabelën 2, dhe vetë kodi është paraqitur në tabelën 3.
tabela 2
Mekanizmi për ndërtimin e kodit Shannon - Fano në shembullin e alfabetit rus
| Shenjat binare | |||||||||
| letra | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9-të |
| - | |||||||||
| O | |||||||||
| e | |||||||||
| a | |||||||||
| dhe | |||||||||
| T | |||||||||
| n | |||||||||
| me | |||||||||
| R | |||||||||
| v | |||||||||
| l | |||||||||
| për të | |||||||||
| m | |||||||||
| d | |||||||||
| NS | |||||||||
| në | |||||||||
| unë jam | |||||||||
| NS | |||||||||
| s | |||||||||
| b, b | |||||||||
| b | |||||||||
| G | |||||||||
| h | |||||||||
| th | |||||||||
| NS | |||||||||
| f | |||||||||
| NS | |||||||||
| NS | |||||||||
| c | |||||||||
| SCH | |||||||||
| NS | |||||||||
| f |
Tabela 3
Rezultati i kodimit të shkronjave të alfabetit rus me kodin Shannon - Fano
Shembulli 4. Le të shkruajmë frazën "metoda e kodimit" duke përdorur kodin Shannon - Fano.
Zgjidhja: Le të përdorim tabelën 3 dhe të marrim rezultatin e mëposhtëm:
(1001) s (110011) n (001) o (1001) s (001) o (111010) b (000) hapësirë
(10111) deri në (001) o (110010) d (0110) dhe (10100) r (001) o (10101) c
(0101) a (1000) n (0110) dhe (110110) i
Vini re se nuk ka nevojë të ndahen shkronjat nga njëra-tjetra me një karakter të veçantë, pasi edhe pa këtë dekodim kryhet pa mëdyshje për shkak të vetive të prefiksit: asnjë fjalë e koduar më e shkurtër nuk është fillimi i një kodi më të gjatë. Në të vërtetë, Tabela 3 tregon se më të shkurtrat janë kodet për karakteret "hapësirë" dhe "o". Për më tepër, jo një tjetër kod i gjatë nuk ka 000 ("hapësirë") dhe 001 ("o") në fillim të sekuencës. E njëjta gjë mund të vërehet për të gjitha sekuencat e tjera binare të kodit Shannon - Fano, të cilat janë paraqitur në Tabelën 3.
Duhet të theksohet se çdo gabim kodimi (përzierje aksidentale e 0 ose 1 karaktere) me një kod të tillë është fatal, pasi deshifrimi i të gjithë tekstit pas gabimit bëhet i pamundur.
Shembulli 5. Përcaktoni nëse kodi që kemi marrë në konsideratë është optimal në mungesë të gabimeve?
Zgjidhja: Le të gjejmë informacionin mesatar për një simbol elementar (0 ose 1) dhe ta krahasojmë atë me maksimumin informacione të mundshme, e cila është e barabartë me një. Për ta bërë këtë, së pari gjejmë informacionin mesatar të përmbajtur në një shkronjë të tekstit të transmetuar, d.m.th., entropinë për shkronjë (shih formulën 8):
Sipas tabelës 1, ne përcaktojmë numrin mesatar të karaktereve elementare për shkronjë:
Kështu, informacioni për karakter është shumë afër kufirit të tij të sipërm prej një, dhe kodi i dhënë shumë afër optimales.
Në rastin e përdorimit të një kodi binar pesë-bitësh, informacioni për karakter:
Shembulli 6. Le të merret një mesazh (një fjalë në Rusisht) përmes kanalit të komunikimit të koduar me kodin Shannon-Fano: 10111001110010010010100.
Është e nevojshme të deshifrohet sekuenca e dhënë.
Zgjidhja: Procesi i dekodimit bazohet në vetinë e prefiksit të kodit dhe kryhet nga e majta në të djathtë. Tabela 3 tregon se gjatësia minimale e kodit është tre bit. Do të numërohen tre bit nga fillimi i fjalës së koduar të marrë, marrim - 101. Nuk ka një kod të tillë në tabelë, kështu që shtojmë një bit tjetër, marrim - 1011. Ky kod gjithashtu nuk është në tabelë, prandaj, ai është e nevojshme të shtojmë edhe një bit, marrim kombinimin - 10111, që korrespondon me shkronjën "k". Fjala e koduar 10111 përjashtohet nga kodi i marrë dhe zëvendësohet me simbolin origjinal (shkronja "k"). Procesi i deshifrimit të pjesës tjetër të shkronjave mesazh i marrë kryhet në mënyrë të ngjashme.
Procesi i plotë i dekodimit tregohet në tabelën 4. Shenja "-" në tabelë do të thotë që kodi i zgjedhur mungon në tabelën 3.
Tabela 4
Procesi i dekodimit të mesazhit
| Sekuenca e kodit të marrë | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| për të | ||||||||||||||||||||||
| për të | O | |||||||||||||||||||||
| për të | O | - | ||||||||||||||||||||
| për të | O | - | ||||||||||||||||||||
| për të | O | - | ||||||||||||||||||||
| për të | O | d | ||||||||||||||||||||
| për të | O | d | - | |||||||||||||||||||
| për të | O | d | e | |||||||||||||||||||
| për të | O | d | e | - | ||||||||||||||||||
| për të | O | d | e | - | ||||||||||||||||||
| për të | O | d | e | R |
Pra, fjala e përftuar si rezultat i deshifrimit të fjalës së koduar të marrë është "enkoder".
Kodimi optimal
Teorema e kodimit të Shannon-it. Metodat optimale të kodimit shkronjë për shkronjë. Kriteret e optimizmit për kodin. Bllokimi i kodimit. një sistem kodimi i informacionit të tekstit.
Kodimi,minimizimi i tepricës së kodit,quhet optimale.
Çështja e ekzistencës së kodeve të tilla është thelbi i një prej teoremave kryesore të teorisë së informacionit - teorema e kodimit e vërtetuar nga K. Shannon. Këtu është një nga formulimet ekuivalente të kësaj teoreme.
Teorema e kodimit. Mesazhet e një burimi arbitrar informacioni Z me entropi H(Z)mund të kodohet gjithmonë me sekuenca në alfabetin B,i përbërë nga M karaktere,Kështu që,se gjatësia mesatare e fjalës së koduar do të jetë arbitrarisht afër vlerës 
,por jo më pak se ajo.
Për shkak të kompleksitetit të saj, vërtetimi i kësaj teoreme nuk merret parasysh.
Teorema thotë se ndryshimi mund të bëhet arbitrarisht i vogël. Kjo është detyra e metodave optimale të kodimit.
Le të kthehemi te shqyrtimi i një burimi informacioni alfabetik që gjeneron mesazhe me karaktere alfabetike A... Meqenëse teprica e kodit jepet nga formula
është e qartë se sa më pak, aq më optimal është kodi. Për ulje Karakteret që shfaqen shpesh duhet të kodohen me fjalë më të shkurtra dhe anasjelltas. Të gjitha metodat optimale të kodimit bazohen në këtë kërkesë. Përveç kësaj, për të siguruar deshifrimin e një kodi të pabarabartë, është e rëndësishme të vëzhgoni parimi i prefiksit: Asnjë fjalë kod nuk duhet të jetë fillimi i një fjalekodi tjetër.
Këtu janë dy nga metodat më të njohura të kodimit optimal shkronja për shkronjë. Për thjeshtësi, ne marrim alfabeti binar si kod.
Hapi 1. Simbolet e alfabetit origjinal i renditim sipas rendit të mos rritjes së probabiliteteve të tyre. (Ne i shkruajmë ato në një varg.)
Hapi 2. Pa ndryshuar renditjen e simboleve i ndajmë në dy grupe në mënyrë që probabilitetet totale të simboleve në grupe të jenë sa më të barabarta.
Hapi 3. Ne i caktojmë grupit në të majtë "0", dhe grupit në të djathtë "1" si elementë të kodeve të tyre.
Hapi 4. Shfletoni grupet. Nëse numri i elementeve në grup është më shumë se një, shkoni te hapi 2. Nëse ka një element në grup, ndërtimi i kodit për të ka përfunduar.
Oriz. 4.1. Pema binare që korrespondon me kodimin Shannon - Fano
Konsideroni funksionimin e algoritmit të përshkruar duke përdorur shembullin e kodimit të alfabetit 
, simbolet e të cilit ndodhin me probabilitete (0,25; 0,05; 0,25; 0,1; 0,25; 0,1), respektivisht. Rezultati i kodimit është paraqitur në Fig. 4.1.
Është e qartë se procesi i ndërtimit të kodit në rastin e përgjithshëm përmban paqartësi, pasi nuk mund ta ndajmë gjithmonë sekuencën në dy nënbashkësi po aq të mundshme. Në të majtë ose në të djathtë, shuma e probabiliteteve do të jetë më e madhe. Kriteri i rastit më të mirë është më pak tepricë e kodit. Vini re gjithashtu se leximi i saktë i kodit - nga rrënja e pemës deri te simboli - do të sigurojë që ai të jetë prefiks.
