5.11. Что такое перемешивание?

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

Для конкретности рассмотрим множество всех возможных фамилий, имен переменных в программе на языке ФОРТРАН или любое другое большое множество названий. В каждом частном случае, например в одной, платежной ведомости, в конкретной программе и в другом процессе обработки имен, истюдь-. зуется лишь очень небольшая часть всех возможных имен. Предположим для определенности, что ожидаются 500 имен. Можно выделить 10 бит (210— -это число более чем вдвое превосходит 500). Для каждого имени сначала берутся его первые 10 бит, затем к ним логически, прибавляются следующие 10 бит, затем следующие 10 бит и так далее, до окончания имени (дополняя, если нужно; последние биты до 10 бит необходимым числом нулей). Такой процесс однозначно порождает по данномуимени перемешанную сумму, при этом, конечно, два разных имени могут дать одинаковые перемешанные суммы.

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

Как найти вероятность того, что два разных имени дадут одну и ту же перемешанную сумму? Если после перемешивания имена становятся случайными (а логическим сложением каждых 10 бит мы пытаемся достичь именно этого), то имеется примерно 5002 возможных вариантов столкновений. Как в известной задаче о днях рождения, в которой вероятность того, что дни рождения хотя бы у двух из 23 возможных, людей совпадают, существенно больше, половины, так и здесь вероятность по крайней мере одного столкновения очень велика. Вместе с тем, вероятность того, что. некоторое фиксированное имя вступи? в столкновение с каким-либо другим именем, меньше 1/2, поскольку число мест в таблице имен более чем вдвое превышает, число имен. Таким образом, при перемешивании (кодировании) типичного имени в 10-битовое слово, вероятность его столкновения с каким-либо другим именем меньше половины. Однако, вероятность столкновения между какими-либо из 500 имен весьма велика, и следует допустить возможность его появления.