Моделі джерел відкритого тексту. Ентропія на символ джерела

ЛЕКЦІЯ №2

МОДЕЛІ ДЖЕРЕЛ ВІДКРИТОГО ТЕКСТУ. ЕНТРОПІЯ НА СИМВОЛ ДЖЕРЕЛА

Схема передачі захищеного повідомлення за допомогою криптосистеми з єдиним ключем (симетричної криптосистеми).

відкритий канал зв’язку

ключ

ключ

ВТ′

ШТ′′

ШТ

ВТ

Джерело повідомлення

Шифратор

Дешифратор

Отримувач

Перехоплюючий противник

Джерело ключа

Закритий канал зв’язку

п-грамою називається послідовність з п символів тексту, що стоять підряд. При n = 2 це біграма, при n =3 це триграма.

Під джерелом (відкритого тексту) будемо розуміти деякий пристрій, що у кожен послідовний момент часу видає деякий символ заданого алфавіту. Тобто виходом джерела є випадковий процес з дискретним часом і множиною станів, що співпадає з алфавітом.. Крім алфавіту для джерела треба задати закон, відповідно до

якого генеруються n-грами: Р(х_і+1 = , цілих n Тут х_1, х₂, х_n - випадкові величини, а z₁,...,z_n - букви алфавіту - значення випадкового процесу у моменти часу і+1, i+2,,і + п. Якщо ці ймовірності підсумувати за всіма z₁,...,z_n то отримаємо 1.

Джерело називають стаціонарним, якщо виконується рівність:

У подальшому будемо розглядати лише стаціонарні джерела, тобто такі, у яких немає залежності від зсуву j. Для стаціонарних джерел достатньо задати імовірності

Розглянемо 4 моделі відкритого тексту, з яких кожна наступна враховує все більше залежностей у структурі мови.

Модель МО. Якщо алфавіт Z складається з m елементів, то у моделі МО джерело генерує символи із Z у кожен момент часу незалежно та рівноймовірно:

Всі n-грами в МО є рівно ймовірними:

Модель МО на практиці майже не використовується, бо вона не враховує навіть найпростіших властивостей мови.

М1. Символи тексту х₁, х₁,..., є незалежними, але вони генеруються із різними ймовірностями

Розподіл ймовірностей p(z) відповідає частотам виникнення літер z є Z у мові. У цій моделі ймовірність виникнення n-грам має вигляд:

Зазначимо, що ймовірності літер у різних мовах значно відрізняються. Наприклад, найбільшу частоту в російській мові має літера "о", в англійській - "е". Наступна модель враховує залежність в мові між двома літерами, що стоять поряд.

М2. Джерело генерує біграми х_1, х₂,... і т.д. незалежно одну від одної. Тобто на множині всіх біграм заданий розподіл ймовірностей і кожна нова біграма джерела генерується незшіежно від інших.

Більш складні залежності мови враховуються за допомогою марківської моделі.

Однорідний ланцюг Маркова - це такий випадковий процес (х, }, і = 1,2,... у дискретному часі з дискретною множиною станів Z. що

.

(Для неоднорідного марківського ланцюга імовірності переходу залежали б від п, а в нашому випадку вони залежать лише від станів Таким чином, однорідний ланцюг Маркова - стаціонарний випадковий процес.)

МЗ. В моделі МЗ джерела BT символи генеруються у відповідності до деякого однорідногомарківського ланцюга. Для задання такого ланцюга Маркова достатньо задати розподіл початкових станів та перехідні ймовірності

При виконанні деяких умов (які для мови, як джерела, можуть вважатися виконаними) існує граничний розподіл

що називається стаціонарним розподілом ймовірностей марківського ланцюга. Ці ймовірності задовольняють наступним рівностям

Ймовірність n-грам у моделі МЗ можна зиписати у вигляді

Деякі відомості з теорії інформації

Розглянемо деяку скінченну множину X = { } на якій заданий розподіл ймовірностей Така пара (Х,Р) в теорії інформації називається ансамблем. Елементи х, будемо називати повідомленнями. Інтуітивно зрозуміло, що малоймовірне повідомлення несе у собі більше інформації, ніж більш ймовірне.

Шеннон запропонував для вимірення кількості інформації функцію

що називається власною інформацією повідомлення х,. Усереднимо цю інформацію за всіма повідомленнями ансамбля

Отримана величина називається ентропією ансамбля X. Н(Х) може бути інтерпретована як невизначеність експерименту, коли ми вибираємо з ансамбля повідомлення х, з ймовірністю p( Найчастіше в означенні ентропії беруть логарифм за основою 2, тоді інформація та ентропія вимірюються и бігах. Якщо логарифм десятковий (lg), то - в дитах. Якшо натуральний логарифм (In), то в натах.

Властивості ентропії:

1)

2) Н(Х) = 0 тоді і тільки тоді, коли деяке , а всі інші

3) Н(Х) приймає максимальне значення тоді, коли всі є

рівноймовірними:

Розглянемо дві скінченні множини Х та У, а також їхній декартовий добуток, тобто множину пар (х,у), х є,у є У. Нехай на множині пар задано розподіл ймовірностей р(х,у). Тоді говорять, що ансамблі Хта У задані сукупно. Дійсно, розподіл р(х,у) індукує розподіл на X та Y:

Сукупна ентропія:

Сукупно задані ансамблі X та У називаються незалежними, якщо

4) Якщо X та У - незалежні, то

З курсу теорії ймовірностей відомо визначення умовної ймовірності:

Нехай відомий результат експерименту)' (знаємо, що випало у). Тоді можна визначити умовну ентропію таким чином:

Усереднивши за всіма у, отримаємо умовну ентропію одного ансамбля відносно іншого:

5)

6)

Інтуїтивно: сукупна невизначеність експериментів X та У дорівнює невизначеності X плюс невизначеність У, що залишилася після того, як результат експерименту X став відомим. Х та У входять у формулу симетрично.

7)

Додаткові знання не можуть збільшити невизначеність.

Якщо Х=У, то ХУ позначимо як X². Аналогічно якщо всі .

Якщо X=Z - алфавіт, то n-грама . Ентропія n-грами (джерело стаціонарне: немає залежності від розташування n-грами всередині тексту)

Усереднена ентропія на один символ n-грами дорівнює Для п стаціонарних джерел існує границя цієї величини (у теорії інформації доведено, що послідовність є монотонно незростаючою):

Ця границя мас назву ентропії на символ джерела. Розглянемо, чому буде дорівнювати ентропія на символ джерела для різних моделей BT. що введені раніше.

M0. (бо символи є незалежними - четверта властивість ентропії)

М1. Аналогічно

М2. Будемо розглядати тексти довжиною 2п:

Це є друге визначення ентропії на символ джерела. Воно використовується для оцінки , бо важко обчислити навіть при невеликих значеннях n через велику кількість можливих n-грам.

Англійська мова	4.76	4.03	3.32	3.10
Російська мова		4.35	3.52	3.01	-	-
	Безпосереднім підрахунком	Обхідним шляхом

Використовуючи друге визначення , А.Н. Колмогоров експериментально оцінив для російської мови при великих значеннях п. Виявилося, що після значення вже практично не змінюється, тобто дорівнює ; в той час, як ще істотно відрізняється від . Аналогічні результати було отримано ІНШИМИ вченими (Шеннон та ін.) і для інших європейських мов.

Надлишковістю на символ джерела називається величина де (т - кількість символів алфавіту), тобто_: дорівнює максимальній кількості інформації, яку може нести в собі один символ джерела, а - та кількості інформації, яку насправді несе в собі один символ джерела. R*n -кількість "зайвих" символів у тексті довжиною n. Надлишковість європейських мов знаходиться десь на рівні 60-80%. Але це не означає, що можна випадковим чином викинути 60% символів (літер) і після цього можна буде відновити текст. Викидати літери треба вибірково, використовуючи всі закономірності мови, і відновлювати також, використовуючи всі ці закономірності. Але це практично неможливо.

Експериментально встановлено: тільки до 25% літер можна викинути випадковим чином, щоб при цьому текст залишився придатним для відновлення.

Якщо б літери в тексті були незалежними та рівномірно розподіленими, то . Але тоді будь-яка послідовність літер була б осмисленим текстом, а помилка при передачі призводила б до іншого осмисленого тексту й не могла бути визначена. При усному мовленні ми "ковтаємо" частину літер, або виголошуємо їх нечітко, та завдяки надмірності мови все одно розуміємо. Тож надмірність - це механізм, що сприяє розумінню та протидіє помилкам.

---

Дата добавления: 2015-08-29