Эффективные алгоритмы анализа джевонс-эквивалентности данных

Актуальность темы и степень её разработанности. Цифровая ин-
формация представляется преимущественно двумя способами: комбинацион-
ным и функциональным. Первый рассматривает её в виде комбинации симво-
лов некоторого алфавита, а второй – в виде множества значений некоторой
дискретной функции. Комбинационные способы представления информации
и соответствующие им алгоритмы её обработки начали развиваться с начала
ХХ века. Эти способы представления обычно связывают с работами К. Шенно-
на [1], Р. В. Хэмминга [2] и многих других исследователей. В конце XX века в
связи с развитием информационных технологий и естественной потребностью
в качественно новых методах обработки информации начали появляться функ-
циональные способы её представления. Одним из примеров обработки инфор-
мации в таком представлении является серия алгоритмов сжатия графических
данных JPEG [3]. Цифровая информация отображается на некоторую функцию
двух аргументов. Далее функция преобразуется и определяющие её парамет-
ры (коэффициенты Фурье) округляются, кодируются, и их коды сжимаются
комбинационными методами. Такой способ сжатия, как правило, приводит к
потерям информации во время преобразования.
Для функционального представления цифровой двоичной информации
естественно подходят булевы функции (далее – БФ) [4]. Любому бинарному
вектору (далее – БВ), состоящему из нулей и/или единиц, можно инъектив-
но поставить в соответствие БВ длины, кратной степени двойки. Последнему
можно взаимно однозначно поставить некоторую БФ. Для этого важно одно-
значно упорядочить область определения БФ. Это можно выполнить, зафик-
сировав порядок её аргументов, и в соответствии с ним упорядочить область
её определения, например, лексикографически. Сама БФ может быть описана
реализующими её функциональными элементами или формулой [5]. Множе-
ства отрицаний и перестановок аргументов БФ образуют группу Джевонса [6]
и определяют действие над БФ. Указанное действие замечательно тем, что оно
нейтрально, т.к. не затрагивает связей между функциональными элементами
и не меняет формулы. Джевонс-эквивалентные БФ будут иметь одинаковые
КНФ и ДНФ [7]. Такое действие задаёт естественную эквивалентность БФ и,
как следствие, джевонс-эквивалентность соответственных им данным.
Группа Джевонса была определена в конце XIX века С. Джевонсом для
описания действия над системой связанных понятий, представленных в виде
БФ [6]. Более формальное представление этой группы и другое её название
(гипероктаэдральная группа) были предложены А. Янгом [8] в 1930 г. Работы,
связанные с группой Джевонса и её приложениями, ведутся с начала XX века, –
как за рубежом, так и в России. К ним можно отнести, прежде всего, работы о
представлении группы и изучении её свойств исследователей Л. Гейссингера и
Д. Кинча [9], М. Баака [10], В. Н. Иванова [11], С. Билли и Т. К. Ламма [12],
М. Парвафи, Б. Сивакумара и А. Тамилселви [13], Б. Бьянок [14], Дж. Кон-
да [15], Б. В. Олийныка и В. И. Сущанского [16, 17] и др.; труды, связанные с
теорией перечислений исследователей Д. Слепиана [18], П. Константинески [19],
Н. Дж. Де Брёйна [20] и др.; практические работы, связанные с кодированием
и обработкой информации исследователей О. В. Денисова [21], Д. Г. Видеман-
на [22] и др.; теоретические и прикладные работы в области криптографии и
криптологии исследователей А. В. Тарасова [23], В. Г. Никонова и А. В. Саран-
цева [24], М. Л. Бурякова и О. А. Логачева [25], Б. А. Погорелова и М. А. Пу-
довкиной [26, 27], С. П. Горшкова [28], Е. К. Алексеева и Е. К. Карелиной [29]
и др.; труды в области генетики исследователей С. Ханненнфлли и П. А. Пе-
взнера [30] и др.; работы в области кристаллографии исследователей Э. Заппа,
Э. Дюкмана, и Р. Тварока [31]. К известным нерешенным проблемам, связан-
ным с группой Джевонса, относится также Burnt Pancake problem о сортировке
префикс-реверсалами, сформулированная Б. Гейтсом и К. Пападимитроу [32].
Перечислим некоторые важные проблемы в этой предметной области:
– анализ джевонс-эквивалентности данных;
– поиск элементов группы, связывающих джевонс-эквивалентные данные.
Поэтому необходимы эффективные алгоритмы, т.е. такие, которые могут
находить решение указанных проблем за разумное время. Как известно, по-
рядок группы Джевонса для БФ n переменных равен 2n · n!. Исходя из этого,
оценим возможность применения тривиальных алгоритмов, перечисляющих все
элементы группы. Время проверки одного элемента составляет τ(n) = 10−9 · 2n ,
где 2n – число значений БФ и 10−9 с – примерное время вычисления одно-
го значения на ЭВМ (1 ГГц). Тогда полное время работы алгоритма составит
T ime(n) = τ(n) · dtrivial = τ(n) · 2n · n!, где dtrivial – число действий над БФ три-
виальным алгоритмом (порядок группы). В табл. 1 приведены оценки времени
работы тривиальных алгоритмов.