Покрытие множества почти последовательными подмножествами: различия между версиями

'''Расширенное правило доминирования для столбцов:''' Пусть имеются два столбца <math>c_{j_1}, c_{j_2} \in C</math> и строка, которую покрывают оба столбца <math>c_{j_1}</math> и <math>c_{j_2}</math>, и если <math>w(c_{j_1}) \ge w(c_{j_2}) + \sum_{c \in X (c_{j_1}, c_{j_2}) w(c)}</math>, то <math>c_{j_1}</math> ''доминируется'' <math>\{ c_{j_2} \} \cup X(c_{j_1}, c_{j_2})</math>. Удалить столбец <math>c_{j_1}</math> из матрицы A.

В базах данных, которые использовали Руф и Шёбель [8], матрицы представлены столбцовыми индексами первой и последней единицами в ее блоках последовательных единиц. Для таких матричных представлений было предложено правило быстрой редукции данных [8], которое устраняет «лишние» столбцы и в конкретных реализациях заменяет правило доминирования для столбцов. Новое правило работает быстрее, чем правило доминирования для столбцов (редукция матрицы по новому правилу может быть выполнена за время O(mn)), однако оно является менее мощным: в результате редукции матрицы A с использованием нового правила может получиться матрица с большим числом столбцов, чем в результате ее редукции по правилу доминирования для столбцов.