4. Идеальное N-граммное предсказывание

Данные табл. 1 могут быть использованы для получения верхней и нижней границ для -граммной энтропии Для этого необходимо вначале вывести некоторые общие закономерности, относящиеся к наилучшему возможному предсказанию языка, когда предыдущие букв известны. Для языка имеются условные вероятности обозначающие вероятность того, что после -граммы будет стоять буква

(кликните для просмотра скана)

(кликните для просмотра скана)

Наилучшее угадывание за уже известной -граммой будет для буквы с наибольшей условной вероятностью. Второй должна быть угадана буква со следующей по величине вероятностью и т. д. Машина или лицо, производящее угадывание наилучшим способом, будет угадывать буквы в порядке убывания условных вероятностей. Итак, процесс приведения текста с таким идеальным предсказанием состоит в отображении букв на числа от 1 до 27 таким образом, что наиболее вероятная следующая буква (при условии, что известна предыдущая -грамма) отображается в 1 и т. д. Частота единиц в приведенном тексте будет даваться выражением

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

При таком отображении -грамм получается другая совокупность вероятностей для символов приведенного текста: Поскольку предсказание основано теперь на большем знании прошлого, то следует ожидать, что вероятности маловероятных букв будут больше; и действительно, можно доказать следующее неравенство:

Оно означает, что вероятность правильного угадывания за первые попыток, когда известны предыдущие букв, больше или равна той же вероятности, когда известны предыдущие букв для всех Для доказательства представим себе, что вероятности упорядочены в таблицу, где номера у расположены по горизонталям, а все -граммы — по вертикали. Таблица будет содержать, таким образом, 27 столбцов и строк. Член в левой части неравенства (11) есть сложенная по всем строкам сумма наибольших чисел в каждой строке. Член, стоящий в правой части неравенства (11), также есть сумма чисел таблицы, причем из каждой строки берется также чисел, но не обязательно наибольших. Это следует из того, что член, стоящий справа в выражении (11), может быть вычислен из аналогичной таблицы для -грамм, полученной из таблицы -грамм. Каждая строка в -граммной таблице есть сумма 27 строк в -граммной таблице, поскольку

Сумма наибольших чисел некоторой строки -граммной таблицы будет равна сумме чисел, отобранных из соответствующих 27 строк А-граммной таблицы только в том случае, когда эти отобранные строки попадают лишь в столбцов таблицы. Для того чтобы равенство в выражении (15) было верно для заданного это утверждение должно выполняться для каждой строки -граммной таблицы. В этом случае первая буква М-граммы не влияет на множество наиболее вероятных выборов для следующей буквы, хотя упорядочение внутри этого множества может от нее зависеть. Однако если равенство в выражении (11) выполняется для всех то упорядочение также будет независимым от первой буквы -граммы. Приведенный текст, полученный с помощью -граммного идеального предсказывания, совпадает тогда с текстом, полученным от идеального -граммного предсказывания.

Поскольку частные суммы

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

Идеальное -граммное предсказание можно рассматривать, как уже было указано, как преобразователь, переводящий язык в последовательность чисел от 1 до 27. Он обладает при этом следующими двумя свойствами.

1. Выходной символ есть функция от входного символа в настоящий момент времени и от предшествующих букв.

2. Он мгновенно обратим. Входной сигнал может быть восстановлен без потери времени с помощью соответствующей операции над приведенным текстом. В самом деле обратный оператор также действует только над предшествующими символами приведенного текста и выходным символом, полученным в данный момент.

Все изложенное является доказательством того, что частоты выходных символов при -граммном предсказании удовлетворяют неравенствам

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

от этих величин, то получаем определенный выходной символ, который можно расположить на пересечении соответствующих строки и столбца. Далее, мгновенная обратимость требует, чтобы на каждой строке не было одинаковых чисел. Иначе при обратном декодировании возникала бы неопределенность в выборе между несколькими возможностями для входной буквы, принимаемой в настоящий момент. Общая вероятность наиболее вероятных символов на выходе, скажем . будет суммой чисел, просуммированной по всем строкам, взятым по из каждой строки, и, следовательно, не больше чем сумма наибольших чисел в каждой строке. Таким образом, имеем

Иными словами, идеальное предсказывающее устройство, которое было описано выше, обладает преимуществом перед всеми преобразователями, которые могут быть применены к языку, и обладают двумя указанными свойствами. Грубо говоря, идеальное предсказывающее устройство разбивает вероятности различных символов на меньшие группы, чем любой другой мгновенно обратимый преобразователь, пользующийся тем же самым числом букв.

Совокупности чисел, удовлетворяющих неравенству (15), изучались Мюирхедом в связи с теорией алгебраических неравенств. Если неравенство (15) выполняется, когда расстановлены в порядке убывания их величин, и (в данном случае это выполняется, поскольку общая вероятность в каждом случае равна 1), то первое множество чисел мажорирует второе множество чисел Известно, что свойство мажорирования эквивалентно каждому из следующих свойств.

1. Числа могут быть получены из с помощью конечного числа «переносов». Под переносом понимается передача вероятности от больших к меньшим подобно тому, как тепло течет от более нагретых к менее нагретым телам, а не наоборот.

2. Числа могут быть получены из обобщенным «усреднением», т. е. существуют неотрицательные действительные числа для которых такие, что