Диссертация (Модели, методы и комплексы программ построения зависимостей, основанные на решетках замкнутых множеств), страница 10

Предложенный алгоритм ос-69нован на лемме из [54] о том, что множество является посылкой контекста K = (, , ) тогда и только тогда, когда найдется признак такой,что ( ∖ ′ ) ∩ ̸= ∅ выполнено для всех ∈ , для которых ↘ и является собственной посылкой, когда является посылкой и минимальносреди всех посылок(по включению).Оказывается, что этот алгоритм можно переформулировать как частный случай общего алгоритма . Для каждого признака ∈ = {1 , . .

. , | | } мы построим формальный контекст K =( , , ), объектные содержания которого будут определяться следующим образом:1. Для каждого объекта ∈ , такого, что ∈/ ′ в K будут объекты ссодержаниями равными: ′ , а также ′ ∖{1 }, ′ ∖{2 }, . . . , ′ ∖{| | }2. Для каждого объекта ∈ , такого, что ∈ ′ в K будут объектыс содержаниями из множества { ∖ {} | ∈/ ′}3.3.Интенсионально связанные понятияПусть 1 = (1 , , 1 ), 2 = (2 , , 2 ), .

. . , = ( , , ) – кон-тексты с общим множеством признаков . Обозначим через (·) оператор штриха контекста . Набор понятий (1 , 1 ), (2 , 2 ), . . . , ( , ))соответствующих контекстов 1 , 2 , . . . , называется интенсионально70связанным [77], если⋂︁( )11 = 11≤≤⋂︁( )22 = 21≤≤···(⋂︁ ) = 1≤≤Таким образом, любые интенсионально связанные понятия однозначно⋂︀определены множествами 1≤≤ .Рассмотрим оператор (·)* , определенный как * = 11 ∩ 22 ∩. . .∩ для ⊆ .Утверждение 8. Пусть 1 = (1 , , 1 ), 2 = (2 , , 2 ), .

. . , =( , , ) – контексты с общим множеством признаков . Тогда оператор(·)* удовлетворяет следующим свойствам:(1) ( * ) = , для любых ⊆ и 1 ≤ ≤ .(2) (·)* является оператором замыкания.Доказательство. (1) Действительно, ( * ) = (⋂︀1≤≤ ) , поскольку⋂︀ ⊆ для любого 1 ≤ ≤ , следовательно ⊆ 1≤≤ и отсюда⋂︀ ⊆ ( * ) . С другой стороны, 1≤≤ ⊆ , таким образом ( * ) ⊆ .(2) Не сложно проверить, что этот оператор является оператором замыкания:1. ⊆ ⇒ ⊆ , for 1 ≤ i ≤ r ⇒ * ⊆ *2.

⊆ * (доказано выше)⋂︀⋂︀3. ** = 1≤≤ ( * ) = 1≤≤ = *2(монотонность)(экстенсивность)(идемпотентность)71Утверждение можно обобщить на случай, когда 1 , 2 , . . . , имеютразличные множества признаков 1 , 2 , . . . , . Для этого нужно просто⋃︀определить := =1 .Используя оператор (·)* в качестве оракула, можно перечислить всеинтенсионально связанные понятия с полиномиальной задержкой, применив стандартные алгоритмы анализа формальных понятий (см. обзор [71]):Norris, Next Closure, Close-by-One, и.т.д. Напомним, что алгоритм, перечисляющий комбинаторные структуры в каком либо порядке называется алгоритмом с полиномиальной задержкой, если время его выполнения междулюбыми двумя последовательными структурами, которые он перечисляет,полиномиально от размера входа.3.4.Понятия с общими содержаниямиКак и в прошлом разделе, пусть 1=(1 , , 1 ), 2=(2 , , 2 ), .

. . , = ( , , ) — контексты с общим множеством признаков , (·) обозначает оператор штриха контекста для 1 ≤ ≤ .Подмножество признаков ⊆ называется общим содержанием контекстов 1 , 2 , . . . , , если оно является содержанием каждого контекста ,то есть = .Поскольку у любого контекста множество его содержаний образуетсистему замыканий, то и множество общих содержаний тоже образует систему замыканий. Обозначим соответствующий оператор замыкания как(·) .В [44] была рассмотрена задача поиска модели из пересечения Хорнов­ских теорий, заданных своими характеристическими моделями, более то-72го был получен алгоритм с полиномиальной задержкой для перечислениявсех моделей из пересечения Хорновских теорий. На языке анализа формальных понятий Хорновская теория, заданная своими характеристическими моделями означает в точности систему замыканий, заданную (формальным) контекстом, а пересечение Хорновских теорий соответствует системе замыканий общих содержаний.

Из результатов авторов [44] следует,что задача построения минимального (по количеству объектных содержаний) контекста задающего систему замыканий общих содержаний, по двумзаданным контекстам не может быть решена за полиномиальная время,если ̸= .Отметим, что авторы [44] в своей статье не интересовались оператором замыкания (·) системы замыканий общих содержаний. Помимо того,что быстрое вычисление (·) несет в себе самостоятельный интерес, используя линейный алгоритм для вычисления (·) можно получить большинствоалгоритмических результатов из [44] с такой же оценкой сложности, но более коротким путем. Более того, используя алгоритм вычисления (·) какоракул, можно применять множество известных алгоритмов перечислениязамкнутых множеств.Теорема 5. ЗадачаВХОДФормальныеконтексты1=(1 , , 1 ), 2=(2 , , 2 ), .

. . , = ( , , ) с общим множеством признаков ,и множество ⊆ . Контексты заданы бинарными матрицами.ВЫХОД Замыкание множества .∑︀может быть решена за время (| | 1≤≤ | |).Доказательство. Рассмотрим множества = { ′ | ∈ , ⊆ ′ }∪{ },731 ≤ ≤ . Обозначим⋂︀ =⋂︀∈. Мы будем поддерживать тот факт,что для любого 1 ≤ ≤ , каждое общее содержание, которое содержит ,может быть получено пересечением некоторых элементов из .Предположим, что существует такой признак ∈ , что для неко⋂︀торого 1 ≤ ≤ выполнено ∈ . Тогда, поскольку каждое общеесодержание, которое содержит может быть получено пересечением некоторых элементов из , каждое общее содержание, содержащее , должносодержать . Следовательно, если для некоторого 1 ≤ ≤ существует ∈ , которое не содержит , мы можем обновить , удалив из него и инвариант останется выполненным.

Когда ни одно такое удаление не может быть выполнено, мы пытаемся найти другой элемент ∈ , которыйсодержится во всех элементах из и так далее. Поскольку конечно,то на некотором шаге такое ∈ не найдется. Это означает, что любойэлемент ∈ либо принадлежит каждому элементу каждого , либо онне принадлежит какому-то элементу из , для любого 1 ≤ ≤ .

Поэтому⋂︀⋂︀⋂︀⋂︀⋂︀1 = 2 = . . . = , ⊆ 1 и 1 содержится во всех общих⋂︀содержаниях, которые содержат т.е. 1 = .74GetClosure()1 answer ← 2 for ← 1 to 3do remove all rows from [] that does not contain 4 for ← 1 to 56do for ← 1 to | |do if not answer [m]then if [][][] = true for all 1 ≤ ≤ | |7then answer [] ← true8push in shared -attributes9else for each 1 ≤ ≤ | | such that not [][][]10do push (, ) in not-in[]11counter [][] ← counter [][] + 11213 while shared -attributes not empty141516do pop from shared -attributeswhile not-in[] not emptydo pop (object-index , context-index ) from not-in[]171819for ← 1 to | |do if not [][context-index ][object-index ]then counter [context-index ][i ] ←← counter [context-index ][i ] −120if counter [context-index ][i ] ≤ 0and not answer [i ]212223 return answerthen answer [i ] = truepush in shared -attributes75Псевдокод алгоритма, вычисляющего (·) .Здесь [] - это бинарная матрица, задающая отношение ,counter [][] равно количеству объектов из , для которых невыполнено, shared-attributes и not-in[] могут быть реализованы как сте­ки или как любые другие структуры данных, поддерживающие операции“вытащить"(pop) любой объект и “вставить"(push) любой объект за время(1).

Не сложно заметить, что каждая клетка таблицы контекста [], ≤ будет обработана не более 3 раз. Поэтому суммарное время работы данногоалгоритма равно O(суммы размеров таблиц формальных контекстов).2На практике часто бывает ситуация когда бинарное отношение формального контекста сильно разрежено и поэтому такой контекст задаетсяне бинарной матрицей, а списками признаков для каждого объекта (массив признаков, которыми обладает данный объект, отсортированные повозрастанию).

Размером такого контекста можно считать || т.е. число ×в табличном представлении данного контекста (|| может быть <<, чем|| · | |). Ниже мы докажем, что даже в случае разреженных контекстов,которые заданы списками признаков, оператор замыкания общих содержаний можно вычислять за линейное от входа время.

Приведем псевдокодэтого алгоритма:76GetClosure_2()1 answer ← 2 for ← 1 to 3do [] ← transposed relation of []4objects[i ] ← { ∈ [] | ⊆ ′ }5for each a ∈ 6do ← |[] ∖ [][]|7PQ[].(, )8if x = 0then push a in shared _attributes910 while shared _attributes not empty11do pop from shared _attributes12answer ← answer ∪{}13for ← 1 to 14do removed _objects ← objects[i ] ∖ [][]15objects[i ] ← objects[i ] ∩ [][]16for each o ∈ removed _objectsdo PQ[i ].decrease_all()17for each a ∈ 18do PQ[i ].increase(a)19while PQ[i ] ._() = 020do ← PQ[i ] ._()21push a in shared _attributes2223 return answerПсевдокод алгоритма, вычисляющего (·) , когда контексты заданысписками признаков.77Операции ∪, ∩ и ∖ для списков и можно делать за время (|| + ||), используя алгоритм слияния, аналогичный алгоритму всортировке слияниями.

Следовательно, время работы выполнения строк14 и 15 можно оценить как (|[]| + | [][]|), а новое значение |[]| можно оценить как (| [][]|). Поэтому для каждого1 ≤ ≤ , суммарное время выполнения строк 14 и 15 оценивается как∑︀( 1≤≤| | | [][ ]| + | [][−1 ]|) = (| []|). Если время выполнениявсех операций структуры равно (1), то время выполнения цикла на∑︀строках 16–19 можно оценить как ( ∈_ |′ |).

Для каждого ≤ , любой объект из массива _ встречается ровно 1 раз.Поэтому суммарное время выполнения цикла на строках 16–19 можно оце∑︀нить как ≤ (| []|). Следовательно суммарное время работы алго∑︀∑︀ритма можно оценить как ≤ ((|[]|) + (| []|)) = ≤ (|[]|).Осталось описать устройство структуры данных . Структураданных это приоритетная очередь, которая поддерживает операции:узнать минимум (get_min), удалить минимум (extract_min), а также операции - уменьшить все ключи на 1 (decrease_all) и увеличить значение ключа, данного элемента на 1 (increase()).

Если изначально все ключи принимают только целые значения от 0 до | |, а также операции decrease_allи increase вызывается не более | | раз, то эту структуру данных можно реализовать так, чтобы ее инициализация занимала (| |) времени, авсе операции выполнялись за (1). Для этого достаточно создать массивразмера 2| |, элементы которого будут хранить списки, добавляемых вструктуру элементов. Также для каждого, хранимого элемента нужно запоминать где он в этом массиве и соответствующем списке находится (за-78вести вспомогательный массив для этого). Кроме того нужно завести двепеременных: ∈ {0, 1, . . .