Энтропия языка

Энтропия языка — статистическая функция текста на определённом языке либо самого языка, определяющая количество информации на единицу текста.

Условная энтропия текста, если известны вероятности появления одной буквы после последовательности из ${\displaystyle n}$ предыдущих букв определяется по формуле:

${\displaystyle H_{n+1}=-\sum _{q=1}^{Q}\sum _{i=1}^{M}p(b_{q},a_{i})\log _{2}p_{q}(a_{i}),}$

где ${\displaystyle M}$ — число букв в алфавите языка, ${\displaystyle b_{q}}$ — ${\displaystyle q}$-ая последовательность из ${\displaystyle n}$ букв, предшествующая букве ${\displaystyle a_{i}}$, ${\displaystyle p(b_{q},a_{i})}$ — совместная вероятность появления последовательности ${\displaystyle b_{q}}$ и ${\displaystyle a_{i}}$, ${\displaystyle p_{q}(a_{i})}$ — условная вероятность появления буквы ${\displaystyle a_{i}}$ после последовательности ${\displaystyle b_{q}}$^[1].

По определению принимают^[1]:

${\displaystyle H_{0}=\log _{2}M.}$

Для ${\displaystyle n=0}$:

${\displaystyle H_{1}=-\sum _{i=1}^{M}p(a_{i})\log _{2}p(a_{i})}$,

где ${\displaystyle p(a_{i})}$ — безусловная вероятность появления буквы ${\displaystyle a_{i}}$.

Согласно Клоду Шеннону, энтропия текста равна:

${\displaystyle H=\lim _{n\to \infty }H_{n+1}.}$

Для английского текста без учетов пробелов и знаков пунктуации (${\displaystyle M=26}$) значения ${\displaystyle H_{n+1}}$ равны^[1]:

${\displaystyle H_{0}=4.7}$, ${\displaystyle H_{1}=4.14}$, ${\displaystyle H_{2}=3.56}$, ${\displaystyle H_{3}=3.3.}$

Для русского текста без буквы «ё» (${\displaystyle M=32}$)^[2]:

${\displaystyle H_{0}=5}$, ${\displaystyle H_{1}=4.358}$, ${\displaystyle H_{2}=3.52}$, ${\displaystyle H_{3}=3.01.}$

Шеннон предложил следующий способ для оценки ${\displaystyle H=\lim _{n\to \infty }H_{n+1}}$. Он предлагал людям угадывать букву ${\displaystyle a_{i}}$ при условии, что им известны предыдущие ${\displaystyle n}$ букв текста. Далее подсчитывалась вероятность, с которой эта буква была угадана и с какой попытки. В результате Шенноном было определено, что для английского текста при ${\displaystyle n=100}$ величина ${\displaystyle H_{n+1}}$ составляет от 0.6—1.3 бит/буква^[3], что может быть принято за энтропию английского текста^[4].

Также с помощью экспериментальных оценок установлено, что энтропия русского языка с учетом вероятностных связей между элементами равна 1.4 бит/буква для разговорной речи, 1.19 бит/буква для литературного текста, 0.83 бит/буква для делового текста. Энтропия французского языка с учетом вероятностных связей между элементами равна 1.5, 1.38, 1.22 бит/буква соответственно^[5].

• Шнайер Б. Глава 11. Математические основы. Теория информации. // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 269. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• C. E. Shannon. Prediction and entropy of printed English (англ.) // Bell Systems Technical Journal. — 1951. — Vol. 30. — P. 50—64. Архивировано 5 февраля 2007 года.
• Cover, T., King, R. A convergent gambling estimate of the entropy of English // Information Theory, IEEE Transactions on. — 1978. — Т. 24, вып. 4. — С. 413—421. — ISSN 0018-9448.