On a comparison of underdetermined alphabets.pdf Задан конечный алфавит A0 = {a^ : i G M} основных символов. Каждому непустому T С M соответствует недоопределённый символ aT, доопределением которого считается всякий основной символ a^, i G T. Выделена система T С 2м некоторых подмножеств T С M и с ней связан недоопредёленный алфавит A = {aT : T G T}. Пусть помимо A0 и A заданы основной алфавит B0 = {bj : j G L}, недоопределённый алфавит B = {b^ : U G U С 2l} и соответствие Яав С A х B, указывающее, каким образом символы алфавитов A и B взаимно сопоставлены друг другу (символам одного алфавита могут соответствовать несколько символов другого). Назовём алфавиты A и B с заданным для них соответствием Rab соответственными алфавитами; последовательности a = aTl... aTn и b = bu... bUn, для которых (aTi , bu) E RaB , i = 1,..., n, соответственными последовательностями. В работе представлено несколько подходов к сравнению соответственных недоопре-деленных алфавитов по силе. Первый из них - функциональный - основан на функциональной выразимости символов одного алфавита через символы другого. Следующие три подхода терминологически связаны с подходами к введению меры информации, представленными в работе А. Н. Колмогорова [1]. Это комбинаторный, вероятностный (статистический) и алгоритмический подходы. Доказано, что все подходы приводят к одному и тому же соотношению алфавитов по силе. Функциональный подход. Скажем, что алфавит B функционально выразим через A, если существует функция F : A0 - B0, такая, что для всех пар (aT,bu) E RAB выполнено F(aT) С bu, где F(aT) = {F(ai) : i E T}, bu = {bj : j E U}. Будем говорить, что алфавит A функционально сильнее B, и записывать A ^ f B, если B функционально выразим через A. Соотношение A ^ f B может быть эквивалентно представлено в терминах соответственных последовательностей, а именно: A ^ f B тогда и только тогда, когда существует такая функция F : A0 - B0, что для всякой пары а = aPl ... ayn, b = bu1 ... bun соответственных последовательностей и любого доопределения а0 = ail ... ain последовательности а последовательность F(а0) = F(ail)... F(ain) доопределяет b. В терминах соответственных последовательностей будут даны и последующие определения. Комбинаторный подход. Для последовательности а в алфавите A введём класс К(а) всех последовательностей в алфавите A, в которых каждый символ ay E A встречается такое же, как в а число раз. Обозначим через N (а) минимальную мощность множества последовательностей в основном алфавите A0, среди которых имеются доопределения всех последовательностей из К(а). Аналогично, паре последовательностей а = aT1... ayn и b = bu1... bun сопоставим класс К(а, b) всех пар последовательностей с теми же кратностями появления пар (ay, bu) E A x B, что ив (а, b), и минимальную мощность N (а, b) доопределяющего К(а, b) множества пар. Будем считать, что алфавит A комбинаторно сильнее алфавита B, и записывать A ^c B, если для любых соответственных последовательностей а и b выполнено N (а, b) = N (а). Статистический подход. Будем рассматривать недоопределённые источники X в алфавите A, порождающие независимо символы ay E A с некоторыми вероятностями рт. Определим энтропию H(X) источника X, положив где минимум берётся по наборам Q = (qi, i E M) вероятностей символов ai основного алфавита A0. О свойствах и роли этой энтропии см. в [2]. Источники X и Y в алфавитах A и B, заданные совместным распределением p(ay, bu), ay E A, bu E B, назовём соответственными, если p(aT, bu) > 0 лишь в случае (aT, bu) E RaB. Будем говорить, что алфавит A статистически сильнее алфавита B, и записывать A ^s B, если для любых пар соответственных источников X и Y выполнено H(XY) = H(X). Алгоритмический подход. Модифицируя применительно к недоопределён-ным данным систему понятий из [1], назовём колмогоровской сложностью K(x) недо-определённого слова x минимальную длину двоичной программы для произвольно фиксированного оптимального алгоритма, порождающей какое-либо доопределение слова x. Эта величина задана с точностью до аддитивной константы: сложности K (x) и K'(x) по различным оптимальным алгоритмам удовлетворяют соотношению K(x) « K'(x), где / ~ g означает, что разность / - g ограничена [1]. Будем говорить, что алфавит A алгоритмически сильнее алфавита B, и записывать A £а B, если для любых соответственных последовательностей a и b выполнено K(ab) ~ K(a). Теорема 1. Введенные соотношения недоопределенных алфавитов по силе эквивалентны, т. е. A £ f B ^ A £ c B ^ A £ s B ^ A £ а B. С учётом теоремы будем применять запись A £ B без уточнения смысла, в каком она понимается. Будем алфавиты A и B называть равносильными и записывать A ~ B, если A £ B и B £ A. Теорема 2. Для соответственных алфавитов A и B существуют полиномиальные алгоритмы проверки соотношений A £ B и A ~ B. Задача сжатия недоопределённых последовательностей ставится как задача такого их кодирования, которое обеспечивает для каждой из них возможность восстановления какого-либо доопределения [2]. Если a и b - соответственные последовательности в равносильных алфавитах A и B, то кодирование для a может рассматриваться и как кодирование для b, поскольку доопределение a0, найденное по коду для a, позволяет получить доопределение для b в виде F(a0) (см. функциональный подход). Если кодирование для a оптимально, оно оптимально и для b. За счёт перехода к равносильному алфавиту иногда удаётся упростить процедуру оптимального кодирования.

Скачать электронную версию публикации