Полиномиальное асимптотически оптимальное кодирование недоопределенных бернуллиевских источников общего вида

Недоопределенный источник Бернулли порождает независимо с некоторыми вероятностями символы заданного недоопределенного алфавита. Каждому недоопределенному символу соответствует некоторое множество основных (полностью определенных) символов, любым из которых он может быть замещен (доопределен). Недоопределенный источник характеризуется энтропией, которая вводится неявно как минимум некоторой функции и играет роль, подобную роли энтропии Шеннона для полностью определенных источников. Кодирование недоопределенного источника должно обеспечить для всякой порождаемой им последовательности воспроизведение какого-либо ее доопределения. Кодирование асимптотически оптимально, если средняя длина кода асимптотически равна энтропии источника. Оно универсально, если не зависит от вероятностей символов источника. В статье описан метод асимптотически оптимального универсального кодирования недоопределенных источников Бернулли, для которого процедуры кодирования и декодирования реализуемы РАМ-программами почти линейной сложности.