Избыточность языка

Избыточность языка — статистическая величина, обозначающая избыточность информации, содержащейся в тексте на определённом языке.

Избыточность языка определяется по формуле^[1][2][3]:

${\displaystyle R=1-{\frac {H}{H_{max}}},}$

где

${\displaystyle H_{max}=\log _{2}(M)}$ — абсолютная энтропия языка, то есть максимально возможное значение энтропии языка, состоящего из ${\displaystyle M}$ букв,

${\displaystyle H=\lim _{n\to \infty }H_{n+1}}$ — фактическая энтропия языка, где

${\displaystyle H_{n+1}=-\sum _{q=1}^{Q}\sum _{i=1}^{M}p(b_{q},a_{i})\log _{2}p_{q}(a_{i})}$ — условная энтропия текста, если известны вероятности появления одной буквы после последовательности из предыдущих букв, где ${\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}}$^[4].

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

${\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 a_{i}}$ при условии, что им известны предыдущие ${\displaystyle n}$ букв текста. Далее подсчитывалась вероятность, с которой эта буква была угадана и с какой попытки.

Величина избыточности разных языков мира колеблется в пределах 70—80%^[5]. Во всех языках на всех уровнях присутствуют избыточные элементы. Избыточность в языке неслучайна: её функция — облегчить коммуникацию при неблагоприятных условиях передачи информации. Избыточность представляет собой систему предупреждения возможных ошибок^[6].

Для английского текста, состоящего из 26 букв, ${\displaystyle H_{max}=\log _{2}26=4.7}$. Шенноном было уcтановлено, что энтропия английского текста при ${\displaystyle n=100}$ равна 0.6—1.3 бит/символ^[7], что может быть принято за энтропию английского текста^[8]. Таким образом, избыточность английского текста составляет 72—87%.

Также с помощью экспериментальных оценок были определены энтропии других языков. В таблице представлены энтропии русского и французского языков, а также их избыточности для разных типов текста^[3].

Также в лингвистике избыточность означает информацию, повторяющуюся более одного раза^[9][10]. Примерами избыточности служат элементы множественного согласования в морфологии^[9], множественные признаки отличающие фонемы в фонологии^[10], или использование нескольких слов для выражения одной идеи в риторике^[9].

Избыточность может возникать на любом уровне грамматики из-за согласования – необходимого условия во многих языках, позволяющего формам различных слов сочетаться друг с другом во фразе или предложении – одна и та же семантическая информация может быть передана несколько раз. Например, в испанском во фразе los árboles verdes («зелёные деревья») артикль los, существительное árboles и прилагательное verdes преобразованы и указывают на форму множественного числа^[9]. В английском таким примером будет that man is a soldier по сравнению с those men are soldiers. («Этот человек солдат» по сравнению с «эти люди солдаты»).

В фонологии, избыточность возникает в минимальных парах – пары слов или фраз, отличающихся друг от друга только одной фонемой, самой маленькой отличительной единицей звуковой системы. Тем не менее, фонемы могут отличаться по нескольким фонетическим признакам. Например, в английском фонемы /p/ и /b/ в словах pin и bin имеют различную звонкость, придыхание и произносятся с разным уровнем напряжения. Любого из этих признаков достаточно, чтобы отличить /p/ и /b/ в английском^[10].

В генеративной грамматике избыточность используется для упрощения формы грамматического описания. Любой признак, который может быть предсказан (выведен) на основании другого признака (например как придыхание напрямую зависит от звонкости) не должен быть включён в грамматические правила. Следовательно, неизбыточные признаки, которые должны быть описаны в грамматических правилах называются дифференциальными признаками^[10].

Наряду с согласованием в морфологии, фонологически обусловленное чередование, такое как коартикуляция и ассимиляция добавляют избыточность на фонологический уровень. Избыточность фонологических правил может объяснить некоторые неясности в устной коммуникации. Согласно психологу Стивену Пинкеру, «В понимании речи избыточность в фонологических правилах может компенсировать некоторые неточности звуковой волны. Например, говорящий знает, что thisrip должно быть this rip а не the srip,потому как сочетание согласных sr в английском не употребляется^[11].

Избыточность можно уменьшить с помощью сжатия источника. В случае, когда источник не имеет избыточности (${\displaystyle H=H_{max}}$), то есть вероятности всех символов одинаковы, оптимальным кодированием является равномерное кодирование, при котором каждый символ кодируется одинаковым числом битов, равным ${\displaystyle \log _{2}(M)}$. В случае, когда ${\displaystyle H<H_{max}}$ источник имеет избыточность, и равномерное кодирование не является оптимальным, так как требует ${\displaystyle \log _{2}(M)}$ битов для кодирования каждого символа. Однако избыточность может быть уменьшена полностью или частично, если при кодировании представлять наиболее вероятные символы короткими последовательностями битов, а менее вероятные — более длинными. В этом случае среднее количество битов, приходящихся на один символ, окажется меньшей, чем в случае равномерного кодирования^[12]. В результате устранения избыточности источник (файл) будет занимать меньший размер, и его символы могут быть переданы по каналу связи более быстро.

Основная теорема кодирования канала без шума гласит, что символы источника с основанием алфавита ${\displaystyle M}$, имеющее энтропию ${\displaystyle H}$, можно так закодировать посредством кодовых символов с основанием алфавита ${\displaystyle D}$, что среднее число кодовых символов на один символ источника ${\displaystyle {\bar {n}}}$ удовлетворяет неравенству^[13]:

${\displaystyle {\frac {H}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H}{\log _{2}(D)}}+\epsilon ,}$

где ${\displaystyle \epsilon }$ — сколь угодно мало.

Это неравенство выполняется в случае, когда символы источника объединяются в группы по ${\displaystyle N}$ символов, и производится кодирование этих групп кодовыми символами, причём величина ${\displaystyle N}$ стремится к бесконечности^[14][15].

Таким образом, среднее число кодовых символов на один символ источника не может быть сделан меньше, чем ${\displaystyle {\frac {H}{\log _{2}(D)}}}$. В противном случае, символы источника нельзя достоверно восстановить.

Если кодирование производится двоичными кодовыми символами ${\displaystyle D=2}$, то это означает, что при кодировании без потерь среднее число битов, приходящихся на символ источника, может быть сделано очень близким к энтропии источника, которая и является средним количеством информации (битов), приходящееся на символ источника. Такое кодирование устраняет избыточность без потери информации.

Сжатие без потерь может быть реализовано с помощью кодирования Хаффмана, кодирования Лемпеля — Зива — Велча или арифметического кодирования.

• Шнайер Б. Глава 11. Математические основы. Энтропия языка. // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 269. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.