ГЛАВА 7. ПРИЛОЖЕНИЯ К НЕКОТОРЫМ СПЕЦИАЛЬНЫМ ПРОБЛЕМАМ

1. Задача о расположении с применением смешанной ячейки

Если мы желаем классифицировать данные (буквы, ошибки, растения и т. д.), расположив их в определенном порядке по набору ячеек, то возникает вопрос об оптимальном размере ячейки. Если ячейка мала по сравнению с размерами элементов, то возникает неопределенность; если ячейка слишком велика, то расположение будет неэффективным. Рассмотрим эту задачу и исследуем роль различных возможных правил расположения. Мы можем применить смешанную ячейку (miscellaneous cell) для элементов, принадлежность которых к какой-либо определенной ячейке неясна; мы можем также применить систему перекрестных ссылок (cross-references). Интересно сравнить эффективность обоих методов). Наше рассуждение основывается на общей формуле (1.13):

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

и информация измеряется в двоичных единицах.

В качестве упрощенной схемы рассмотрим расположение отрезка длиной на линии полной длины ; положим, что так что краевыми эффектами можно пренебречь. Линия L разделена на N смежных сегментов длиной m, так что

Длина m представляет размер ячейки, и мы ищем оптимальную длину m, т. е. такое ее значение, которое дает наибольшую информацию. Эта схема представлена на рис. 7.1. Расположим случайным образом на линии L сегмент АВ длиной l. Отрезок CD представляет одну из ячеек длиной m.

Рис. 7.1. Модель расположения с ячейками длиной и длиной располагаемых элементов .

Если точка А попадает между С и Е, то сегмент АВ полностью находится внутри ячейки. Если А попадает между Е и D, то сегмент перекрывает точку D — место стыка двух ячеек. Мы имеем:

Предполагается, что попадание АВ в любую ячейку имеет одинаковую вероятность. Вероятность того, что АВ окажется полностью внутри ячейки, есть

(это выражение сводится к для точечных элементов).

Полная вероятность того, что АВ окажется полностью внутри какой-либо ячейки, равна

Случай m = 0 тривиален и не рассматривается, так что наличие m в знаменателе не приведет к недоразумениям.

Дополнительная вероятность того, что АВ перекроет границу между ячейками и, следовательно, должен быть помещен в (дополнительную) смешанную ячейку, равна, очевидно

Количество информации (на элемент данных) выражается формулой (7.1):

Желая получить максимум информации, мы приравниваем производную нулю:

илиъ

что дает максимум при

или

Очевидно, что оптимальное значение имеет тот же порядок величины, что и , но точное решение зависит (впрочем, некритически, в силу логарифмической зависимости) от выбора L, а точнее говоря, от отношения полной «длины» системы расположения к элементу I. Пусть, например, ; это значит, что «типичная» ошибка занимает

менее 1% всей системы. Тогда, обозначая , имеем:

решение которого это значит, что размер ячейки должен быть примерно вчетверо больше длины элемента.

Если же так что типичная ошибка занимает около 1/200% всей системы, то

что .