An economical representation of underdeter-mined data and superimposed codes.pdf Задан алфавит A0 = {ao, a1,..., am-1} основных символов. Каждому непустому T С M = {0,1,...,m — 1} поставлен в соответствие недоопределённый символ aT. Его доопределением считается всякий основной символ ai, i Е T. Символ a^, доопре-делимый любым ai, называется неопределённым и обозначается *. Выделена система T некоторых непустых подмножеств T множества M и с ней связан недоопределённый алфавит A = At = {aT : T Е T}. Подробнее о недоопределённых данных см. в [1]. Задавшись натуральным числом s, припишем каждому ai Е A0 набор Ai = (Ai(1), ...,Ai(s)) Е {0,1}s — код символа ai, а каждому aT Е A — набор AT = (AT(1),..., AT(s)) Е {0,1, *}s. Обозначим через Л и Л матрицы со столбцами Ai, i Е M, и AT, T Е T, соответственно. Скажем, что пара (Л, Л) задаёт для алфавита A двоичное представление (размерности s), если при всех i и T столбец Ai доопределяет At тогда и только тогда, когда i Е T .В случае, когда Л — матрица в двухбуквенном алфавите {0, *}, представление будем называть строго двоичным. Будем говорить, что множество столбцов T матрицы Л (i) покрывает, (ii) инверсно покрывает, (iii) дважды покрывает столбец Aj, если (i) дизъюнкция столбцов Ai, i Е T, покрывает Aj, (ii) дизъюнкция инверсий столбцов Ai, i Е T, покрывает инверсию столбца Aj, (iii) множество столбцов T покрывает и инверсно покрывает Aj. Матрица Л свободна от T-покрытий (двойных T-покрытий), если для любого T Е T множество столбцов T не покрывает (не покрывает дважды) ни одного Aj, j Е T. Теорема 1. Двоичное (строго двоичное) представление (Л, Л) с матрицей кодирования Л существует для алфавита A = At тогда и только тогда, когда она свободна от двойных T-покрытий (T-покрытий). По матрице Л из теоремы можно эффективно (полиномиально) строить (строгие) представления недоопределённых последовательностей и восстанавливать по ним исходные последовательности, не используя Л. Скажем, что система Z подмножеств множества M образует конъюнктивный базис (обобщённый конъюнктивный базис) системы T, если каждое множество T Е T может быть получено как пересечение некоторых множеств (множеств либо их дополнений) из Z. Строке v, v = 1,..., s, матрицы Л сопоставим множество С M, образованное номерами единичных разрядов строки. Положим Z = {Z1,... , Zs}, Z' = {Z1,... , Zs}, где чёрточка означает дополнение. Для построения матриц, свободных от покрытий (либо двойных покрытий), может быть использован следующий факт. Теорема 2. Матрица Л свободна от T-покрытий (двойных T-покрытий) тогда и только тогда, когда соответствующая ей система Z' (система Z) образует конъюнктивный базис (обобщённый конъюнктивный базис) системы T. Пусть s(A) и s0(A) означают наименьшую размерность соответственно двоичных и строго двоичных представлений алфавита A. Недоопределённые данные, с которыми имеют дело в приложениях, обычно помимо неопределённого символа * используют лишь символы, имеющие небольшое число доопределений. Обозначим через s(m,n,t) максимумальную из размерностей s(A) алфавитов A, для которых |A0| = m, |A| = n и каждый символ aT Е A имеет не более t доопределений либо является неопределённым. Аналогичную величину при использовании s0(A) обозначим s0(m,n,t). Теорема 3. Справедливы оценки s(m, n, t) ^ s0(m, n, t) ^ e(t + 1) ln(mn) + 1. Используя очевидное соотношение n ^ m*, получаем границу вида O(t2 ln m). При малых t эта величина существенно меньше длины m естественного задания недоопре-делённых символов ay посредством характеристического набора множества T. Теорема 4. При выполнении условия t = o(log n/ log log n) имеют место оценки (t - 1)log n (t + 1)log n s(m, n,t) > ——:—-----, s0(m, n, t) ^ ——:-т, v ' 2(2log(t - 1) + c)' 01 ; 2(2 logt + c)' где log x = log2 x, c = log(3e/4) < 1,027. При естественном условии m ^ n верхние и нижние оценки теорем 3 и 4 различаются по порядку в log t раз. В случае, когда система T состоит из всех t-элементных подмножеств множества M, T-дизъюнктивную матрицу называют t-дизъюнктивной. Множество её столбцов образует t-дизъюнктивный код. Дизъюнктивные (superimposed) коды, введённые в [2], находят широкое применение в информатике. Эффективные методы построения t-дизъюнктивных кодов, развитые в [2, 3] и других работах, могут быть использованы для эффективного представления недоопределённых данных. Более подробное изложение представленных результатов можно найти в [4].

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