УказательРазделыОбозначенияАвторО проекте


Вспомогательная страница к разделам КОДИРОВАНИЕ и ТЕОРИЯ ИНФОРМАЦИИ ПО ШЕННОНУ


Частота встречаемости букв в обычном (неспециальном) тексте (без учета пробелов) [2]:

a б в г д е,ё ж з и й к л м н о п р с т
0.075 0.017 0.046 0.016 0.030 0.087 0.009 0.018 0.075 0.012 0.034 0.042 0.031 0.065 0.110 0.028 0.048 0.055 0.065
у ф х ц ч ш щ ъ,ь ы э ю я
0.025 0.002 0.011 0.005 0.015 0.007 0.004 0.017 0.019 0.003 0.007 0.022

Я решил проверить эти результаты на примере отрывка из [1]

Я находился тогда в Германии, где оказался призванным в связи с войной, не кончившейся там и доныне. Когда я возвращался с коронации императора в армию, начавшаяся зима остановила меня на одной из стоянок, где, лишенный развлекающих меня собеседников и, кроме того, не тревожимый, по счастью, никакими заботами и страстями, я оставался целый день один в теплой комнате, имея полный досуг предаваться размышлениям. Среди них первым было соображение о том, что часто творение, составленное из многих частей и сделанное руками разных мастеров, не столь совершенно, как творение, над которым трудился один человек. Так, мы видим, что здания, задуманные и исполненные одним архитектором, обыкновенно красивее и лучше устроены, чем те, в переделке которых принимали участие многие, пользуясь старыми стенами, построенными для других целей. Точно так же старинные города, разрастаясь с течением времени из небольших посадов и становясь большими городами, обычно столь плохо распланированы по сравнению с городами-крепостями, построенными на равнине по замыслу одного инженера, что, хотя рассматривая эти здания по отдельности, нередко находишь в них никак не меньше искусства, нежели в зданиях крепостей, однако при виде того, как они расположены — здесь маленькое здание, там большое — и как улицы от них становятся искривленными и неравными по длине, можно подумать, что это скорее дело случая, чем разумной воли людей. А если иметь в виду, что тем не менее всегда были должностные лица, обязанные заботиться о том, чтобы частные постройки служили и украшению города, то станет ясным, как нелегко создать что-либо совершенное, имея дело только с чужим творением. Подобным образом я представил себе, что народы, бывшие прежде в полудиком состоянии и лишь постепенно цивилизовавшиеся и утверждавшие свои законы только по мере того, как бедствия от совершаемых преступлений и возникавшие жалобы принуждали их к этому, не могут иметь такие же хорошие гражданские порядки, как те, которые соблюдают установления какого-нибудь мудрого законодателя с самого начала своего объединения. Так же очевидно, что истинная религия, заповеди которой установлены самим Богом, должна быть несравненно лучше устроена, чем какая-либо другая. Если же говорить о людских делах, то я полагаю, что Спарта была некогда в столь цветущем состоянии не оттого, что законы ее были хороши каждый в отдельности, ибо некоторые из них были очень странны и противоречили добрым нравам, но потому, что все они, будучи составлены одним человеком, направлялись к одной цели. Подобным образом, мне пришло в голову, что и науки, заключенные в книгах, по крайней мере те, которые лишены доказательств и доводы которых лишь вероятны, сложившись и мало-помалу разросшись из мнений множества разных лиц, не так близки к истине, как простые рассуждения здравомыслящего человека относительно встречающихся ему вещей. К тому же, думал я, так как все мы были детьми, прежде чем стать взрослыми, и долгое время нами руководили наши желания и наши наставники, часто противоречившие один другим и, возможно, не всегда советовавшие нам лучшее, то почти невозможно, чтобы суждения наши были так же чисты и основательны, какими бы они были, если бы мы пользовались нашим разумом во всей полноте с самого рождения и руководствовались всегда только им.
всего a б в г д е,ё ж з и й к л м н о п р с т
количество 3203 195 42 111 40 94 236 30 46 231 24 94 114 109 201 310 53 116 144 155
вероятность 1.000 0.061 0.013 0.035 0.012 0.029 0.074 0.009 0.014 0.072 0.007 0.029 0.035 0.034 0.063 0.097 0.017 0.036 0.045 0.048
у ф х ц ч ш щ ъ ы ь э ю я пробел
количество 49 0 26 9 48 35 7 1 74 45 4 13 61 486
вероятность 0.015 0.000 0.008 0.003 0.015 0.011 0.002 0.000 0.023 0.014 0.001 0.004 0.019 0.152

Без учета пробелов:

a б в г д е,ё ж з и й к л м н о п р с т
вероятность 0.072 0.015 0.041 0.015 0.035 0.087 0.011 0.017 0.085 0.009 0.035 0.042 0.040 0.074 0.114 0.019 0.043 0.053 0.058
у ф х ц ч ш щ ъ ы ь э ю я
вероятность 0.018 0.000 0.009 0.003 0.017 0.012 0.002 0.000 0.027 0.016 0.001 0.004 0.022

Для иллюстрации некоторых методов кодирования, я решил построить два искусственных языка

П

Пример 1. Оставим из всех букв русского алфавита только 10_{}: а, б, в, г, д, е, ж, з, и, к. Жесткое усечение предыдущего текста приведет к


ади тгда в Геаии где каза пизва в взи в е киве а и де Кгда взваа каии иеаа в аи аава зиа авиа е а д из к где ие азвекаи е беедикв и ке г е евжи а икакии забаи и аи ава е де ди в е кае ие дг едава азеи еди и ев б бажеие а веие авее из ги ае и деае каи аз аев е вее как веие ад к ди ди евек ак види здаи задае и иее ди аиек бкве каивее и е е е е в еедеке к ииаи аие гие з аи еаи еи д дги ее ак же аие гда азаа ееие вееи из еби адв и ав бии гдаи б ааива авеи гдаи кеи еи а авие за дг ижееа ааива и здаи деи еедк ади в и икак е ее иква ежеи в здаи кее дак и виде г как и аже зде аеке здаие а бе и как и и ав икивеи и еави дие ж да кее де а е аз ви де а еи ие в вид е е еее вегда би дже иа бзае заби б ае ки жии и каеи гда ае как еегк зда иб веее ие де к жи веие дб баз едави ебе ад бвие ежде в дик ии и и ее ивиизвавие и веждавие ви зак к ее г как бедви веае ееи и взикавие жаб иждаи и к е г ие акие же ие гаждакие дки как е ке бда авеи какг ибд дг закдае аг ааа вег бедиеи ак же евид ииа еиги заведи к аве аи Бг джа б еаве е еа е кака-иб дга Еи же гви дки деа ага аа ба екгда в вее ии е г зак ее би и кажд в деи иб еке из и би е а и ивеии дб ава ве и бди аве ди евек аави к д еи дб баз е и в гв и аки закее в кига кае ее е ке ие дказаев и двд к и ве живи и а а ази из еи жева аз и е ак бизки к иие как е аждеи здавег евека ие веаи е вее К же да ак как ве би деи ежде е а взи и дге ве аи квдии аи жеаи и аи аавики а ивеивие ди дги и взж е вегда вевавие а ее и евзж б ждеи аи би ак же и и вае какии б и би еи б зваи аи аз в ве е аг ждеи и квдвваи вегда к и


Частоты встречаемости букв (пробелы между словами не учитываем)

е и а в д к з б г ж
вероятность 0.211 0.206 0.174 0.099 0.084 0.084 0.041 0.038 0.036 0.027
П

Пример 2. Еще более суровая вивисекция — оставим только 4_{} буквы и пробелы


Оитомии о ими оооитми о о о ооииимтомиимотоим оои тоо и и м оио и омтоо тоимо т иимиотмии ттмиотоитоомт имо о т мим и и м о оои о том тототои ото и мои т и о мимто тооотои отомтиоио Т м иим тои м и иооим иттоомооо и и том т ото иимитимои о тми тми отоми и Тоо т тиоот тим мии оиоои тооимиоомиоотоооиоо и оомиотмиотоми и о м ооо и тоотмтити и о ототи о оии и м ити и отоои и тоооиоомо и тмоои и оти тот иимии мио и моо омт тотоо о м мооии имт и тотмм и оот и о отито том тот отоииии и оототтм о оттоиоооимо тоо имтоимоом оом титоо и оиомотоии и и ото иииои и тиоио тоо о м тоо тиотомтии оии о иии том мот имт тиоои и оит ото оттои оои моо оот моо оооии Т оио тоити ииоиотоотомим оом о т о том иои ооито и тоо тот о тотмотоии оттоо тоо и оои ототи иоото и и и о т и отиоииомм о отомтооии отоим оом и оои оом оом м иооотои и и о м т ото и отт и ооото и отоии и моомоии мимот и т ииити оти омо о отоитотим том м т м и тми м ттоми и оом миооиии и и и тии тоотиоииоиими омооотоим тооти омоотои и и т ити оот ими оии и м оои иммом о оот моо оии оотои тоо им


Каждое слово (кроме последнего) — нечетной длины.

Всего букв 1050, частоты встречаемости букв1)

и м о т пробел
количество 230 109 310 155 246
вероятность 0.219 0.104 0.295 0.148 0.234

Теперь разбиваем текст на биграммы, объединяя последнюю букву каждого слова со следующим за ней пробелом. Всего биграмм 1051, из них

и м о т пробел
и 39 30 33 15 113
м 28 3 25 12 40
о 63 36 83 64 64
т 25 12 81 8 29
пробел 75 28 88 56 0

Первая буква биграммы берется из первого столбца, вторая буква — из первой строки; количество получившейся биграммы в тексте — на перекрестье. Частоты встречаемости биграмм

ии им ио ит и_ ми мм мо мт м_ ои ом оо от о_ ти тм то тт т_
вероятность 0.037 0.028 0.031 0.014 0.108 0.027 0.003 0.024 0.011 0.038 0.060 0.034 0.079 0.061 0.061 0.024 0.011 0.077 0.008 0.028
_o __
вероятность 0.071 0.027 0.084 0.053 0.000

Матрица условных вероятностей

\mathfrak P= \left( \begin{array}{ccccc} 0.170 & 0.130 & 0.144 & 0.065 & 0.491 \\ 0.259 & 0.029 & 0.231 & 0.111 & 0.370 \\ 0.204 & 0.116 & 0.268 & 0.206 & 0.206 \\ 0.161 & 0.077 & 0.523 & 0.052 & 0.187 \\ 0.304 & 0.113 & 0.356 & 0.227 & 0 \end{array} \right)

Проверка:

P( ит )= 0.014,\ P_1\cdot P_{1,4} = 0.219\cdot 0.065 \approx 0.014;
P( ом )= 0.034;\ P_3\cdot P_{3,2} = 0.295 \cdot 0.116 \approx 0.034;
P( т_ )= 0.028;\ P_4\cdot P_{4,5} = 0.148 \cdot 0.187 \approx 0.0276.

Если весь текст разбить на 525_{} биграмм по схеме:

Ои | то | ми | и_ | о_ | им | и_ | оо | ои | тм | и_ | о_ | о_ | о_ | оо | ии | им | то | ми | им | от | ои | м_ |

то из них

и м о т пробел
и 13 14 10 8 113
м 18 0 12 2 40
о 30 16 43 40 64
т 11 7 52 3 29
пробел 0 0 0 0 0

Источники

[1]. Декарт Р. Рассуждение о методе, чтобы верно направлять свой разум и отыскивать истину в науках. (1637 г.)

[2]. Яглом А.М., Яглом И.М. Вероятность и информация. М. ГТТИ. 1957, с.110

1) Имеются небольшие нестыковки с содержимым таблиц предыдущего примера — но лень переделывать схемы из раздела КОДИРОВАНИЕ.

2015/10/22 10:17 редактировал au