Как найти клики / одинаковые комбинации в битовом массиве?

#массивы #алгоритм #математика #комбинаторика

В массив у каждого элемента u1..uN есть своя комбинация битовых свойств b1..bN.

Задача найти наиболее крупные группы с одинаковыми включенными битами. Например:



Зеленым отмечены «включённые» биты, и ниже – две найденные группы. Чем-то задача
похожа на поиск клик в графе, но вроде бы, задача с графом сложнее. Первый найденный
кластер: строки u1 и u2 обе содержат включенными биты 1,3,4,5. Второй кластер: строки
2,3,4 одинаково содержат включенными биты 2 и 4.

В моей задаче число строк измеряется миллионами, а свойств (бит) – сотнями. Поэтому
надеюсь, что есть какое-то более эффективное решение, чем перебор всех возможных комбинаций.

Находить собираюсь наиболее крупные «компании», ограничив поиск неким порогом. Бизнес
цель – анализ данных пользователей в соц. сетях для выявления значимых «общностей».

Подскажите, какая здесь математика поможет?

Связанный вопрос, задавал раньше.
    

Ответы

Ответ 1

Можно поменять строки (а потом - столбцы) так, чтобы включённые биты максимально
приблизились к левому углу.
Это приводит задачу к каноническому виду, поскольку значительное количество разных
массивов сводятся к одному. В размерностях приведённого примера выигрыш по количеству
масок в 4!*5! = 2880 раз, в то время как затраты на перестановку столбцов и строк по
данным сортировки эквивалентны обработке ~+10 масок

P.S. К полученному массиву можно применить алгоритм Кадане 2D, который можно усложнить
вычёркиванием одной-двух строк (столбцов), в зависимости от размерности массива.