Минимальное представительное множество для системы частотных классов недоопределённых слов | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/11

Минимальное представительное множество для системы частотных классов недоопределённых слов

Частотный класс недоопределённых слов - это множество всех слов в некотором недоопределённом алфавите, имеющих заданную длину и заданные частоты вхождения символов. Рассматривается задача доопределения произвольной системы частотных классов. Предложен метод выделения из этой системы минимальной по мощности подсистемы, такой, что достаточно получить доопределения для классов этой подсистемы, а по ним доопределения других классов системы находятся просто.

Minimal representative set for a system of frequency classes of underdetermined words.pdf Пусть M = {0,1,... , m - 1} и выделена система T С 2м некоторых непустых подмножеств T С M. С множеством M связан алфавит A0 = {aj : i G M} основных символов, с множеством T - алфавит A = {ay : T G T} недоопределённых символов. Доопределением символа aT считается всякий основной символ aj, i G T, доопределением слова v в алфавите A - любое слово, полученное из v заменой каждого символа каким-либо его доопределением, а доопределением множества V слов в алфавите A - любое множество слов в алфавите A0, содержащее для каждого слова v Е V некоторое его доопределение. Символ ам, доопределимый любым основным символом, называется неопределённым и обозначается *. Подробнее о недоопределённых данных в [1]. Будем говорить, что недоопределённый символ ат чётче символа ат/, если T С T', и что слово v = ат • • • ат, чётче слова v' = ат' • • • ат', если каждый символ атг слова v 1 1 1 l ' г чётче соответствующего символа а^ слова v'. Ясно, что если v чётче v', то любое доопределение слова v доопределяет v'. Для заданного набора r = (гт : T Е T) натуральных чисел положим l = гт т ет и обозначим через Ki(r) класс всех слов длины l в алфавите A, в которых каждый символ ат встречается гт раз (т.е. с частотой гт/I). Такие классы называют частотными. Скажем, что класс Kll (r1) представительнее класса Ki2 (r2), если l1 ^ l2 и, каково бы ни было доопределение Dll (r1) класса Kll (r1), множество Dll (r1)|l2 начал длины l2 слов, входящих в Dll(r1), образует некоторое доопределение класса Ki2(r2). Отметим, что если в качестве возможных доопределений для Ki2 (r2) использовать вместо начал слов из Dil (r1) другие их фрагменты, расположенные в l2 различных фиксированных разрядах, это не повлияет на введённое понятие, поскольку частотные классы замкнуты относительно перестановок символов в словах. Пусть K - некоторая конечная система частотных классов, заданная перечислением параметров (l, r) входящих в неё классов Ki (r). Подсистему M С K назовём представительным множеством системы K, если для любого K^(r) Е K в M имеется класс, который представительнее K (r). Представительное множество M называется минимальным, если не существует представительного множества для K, содержащего меньшее число частотных классов. Цель данной работы - построение минимального представительного множества для заданной системы частотных классов. Такая задача возникает в некоторых методах сжатия недоопределённых данных и реализации недоопределённых функций (см., например, [2]). Они обобщают подход Э. И. Нечипорука [3]. Эти методы требуют нахождения доопределений для всех частотных классов подходящей системы. Решение задачи упрощается за счёт сведения к задаче доопределения минимального представительного множества этой системы. Пусть заданы классы Kil(r1) и Ki2(r2), l1 ^ l2, и требуется выяснить, является ли Kil (r1) более представительным. Образуем класс Kil (r+), слова которого получены из слов класса Ki2(r2) добавлениями l1 -12 символов *. Компоненты г2,т и г2т наборов r2 и r+ связаны соотношениями г2 * = г2>* + l1 - l2 и г2т = г2,т, ат = *. Лемма 1. Класс Kil (r1) представительнее Ki2 (r2) тогда и только тогда, когда найдётся пара слов (v,v'), v Е Kil(r1), v' Е Kil(r+), в которой v чётче v'. Доказательство. Пусть такая пара (v, v') существует. Рассмотрим произвольное слово w класса K|2 (r2). Образуем слово w' Е K|l (r+) путём дописывания к w в конце l1 - l2 символов *. Найдётся перестановка а символов слова w', для которой a(w') = = v'. Построим слово u = a-1(v). Оно чётче w' и принадлежит классу Kil(r1). Любое доопределение слова u доопределяет w', а его начало длины l2 доопределяет w. Допустим теперь, что пара (v, v') с указанным свойством отсутствует, т. е. для любых v Е Kil (r1) и v' Е Kil (r+) слово v не чётче v'. Возьмём некоторое слово w Е Ki2 (r2) и образуем из него слово v' Е Kil(r+) приписыванием l1 - l2 символов *. Всякое слово v Е Kil (r 1) не чётче v', а потому в нём присутствует символ атг, хотя бы одно из доопределений которого не доопределяет соответствующий символ атг слова v'. Поскольку последними /i - /2 символами слова v' являются *, символ ay принадлежит началу слова v. Это означает возможность доопределить слово v так, чтобы начало этого доопределения не являлось доопределением слова w. В силу произвольности слова v G (ri) отсюда следует существование для класса K^ (ri) такого доопределения, среди начал слов которого нет доопределений слова w G Kl2(r2), а потому K1l(ri) не представительнее класса Kl2 (r2). ■ Пусть, как и раньше, ri = (ri,T : T G 7i), r+ = (r2T/ : T' G 72), где E ri,T = E r2,y/ = ^i. t e-71 T/eT2 Построим ориентированную потоковую сеть [4] с полюсами s (источник) и t (сток), с внутренними вершинами ay, T G 7i, и ву/, T' G 72, с дугами (s, ay), имеющими пропускные способности г1,т, с дугами (ву/, t), имеющими пропускные способности r2y/, а также с дугами (ay,вт/), T С T', обладающими достаточно большими пропускными способностями (например, равными /i). Лемма 2. Пара слов (v,v'), такая, что v G K1l(ri), v' G K1l(r+) и v чётче v', существует тогда и только тогда, когда максимальный поток в построенной сети равен /i. Доказательство. Пусть максимальный поток равен /i. Поскольку совокупность дуг (s,aT), T G 7i, образует разрез, из равенства Е ri,y = 1i следует, что в каждой т из них поток совпадает с пропускной способностью ri,y. Аналогичные рассуждения показывают, что и в дугах (вт/, t), T' G 72, достигается пропускная способность r2 у/. Обозначим через zyy/ поток в дуге (ay, ву/). В соответствии с теоремой Форда - Фалкерсона величины zyy/ можно считать целыми. По набору чисел zyy/, где T G 7i, T' G 72, T С T', образуем слова v и v' так, чтобы в них имелось ровно zyy/ позиций, в которых в слове v находится символ ay, а в слове v' - символ ay/. Из конструкции сети и сказанного выше о достижимости в дугах (s,ay) и (ву/, t) пропускных способностей следует, что Е zTT/ = ri,T, Е zTT/ = r2T/, а потому v G K1l (ri), v' G K1l (r+). T/ T , Кроме того, v очевидно чётче v' и, следовательно, пара слов (v,v') обладает требуемыми свойствами. Эти рассуждения допускают обращение. По паре (v, v') с указанными свойствами может быть построен поток, равный /i, который максимален. ■ Лемма 3. Существует полиномиальный алгоритм выяснения по наборам параметров (/i, ri) и (/2, r2), является ли класс K^ (ri) более представительным, чем K^2(r2). Доказательство. Если /i < /2, то ответ отрицателен. Дальше считаем Zi ^ 12. Образуем из r2 набор r+ заменой компоненты r2,* на r2,* +/i -/2 и построим по (/i, ri) и (/2, r+) потоковую сеть описанным выше способом. Применением полиномиального алгоритма найдём в ней максимальный поток [4]. Из лемм 1 и 2 следует, что класс K1l (ri) представительнее Kl2 (r2) тогда и только тогда, когда этот поток равен /i. ■ Теорема 1. Для любой системы K частотных классов имеется единственное минимальное представительное множество M. Оно может быть найдено со сложностью, ограниченной полиномом от максимальной длины / слов из K. Доказательство. Отношение представительности частотных классов - частичный порядок. В конечной системе K частотных классов имеется единственная подсистема классов, максимальных по этому отношению, которая и образует минимальное представительное множество. Оно может быть найдено путём попарного сравнения частотных классов системы K по отношению представительности с использованием леммы 3. Мощность системы K ограничена числом частотных классов с длиной слов не выше l, которое не превосходит где |A| -мощность алфавита A, а число пар классов из K не больше l2|A|. Поскольку |A| -константа, а трудоёмкость сравнения одной пары по представительности полиномиальна, процедура выделения минимального представительного множества полиномиальна по l. ■

Ключевые слова

недоопределённые данные, доопределение, частотный класс, представительное множество, underdetermined data, specification, frequency class, representative set

Авторы

ФИООрганизацияДополнительноE-mail
Шоломов Лев АбрамовичФедеральный исследовательский центр «Информатика и управление» РАНпрофессор, доктор физико-математических наук, главный научный сотрудникlevshol@mail.ru
Всего: 1

Ссылки

Шоломов Л. А. Элементы теории недоопределённой информации // Прикладная дискретная математика. Приложение. 2009. №2. С. 18-42.
Шоломов Л. А. О функционалах, характеризующих сложность систем недоопределенных булевых функций // Проблемы кибернетики. Вып. 19. М.: Физматлит, 1967. С. 123-139.
Нечипорук Э. И. О сложности вентильных схем, реализующих булевские матрицы с неопределенными элементами // ДАН СССР. 1965. Т. 163. №1. С. 40-42.
Адельсон-Вельский Г. М., Диниц Е. А., Карзанов А. В. Потоковые алгоритмы. М.: Наука, 1975.
 Минимальное представительное множество для системы частотных классов недоопределённых слов | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/11

Минимальное представительное множество для системы частотных классов недоопределённых слов | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/11