Алгоритм четырёх русских — в информатике представляет собой метод ускорения алгоритмов с использованием булевых матриц или, в более общем смысле, алгоритмов с использованием матриц, в которых каждая ячейка может принимать только ограниченное число возможных значений.

Разработанный комбинаторный алгоритм позволяет умножать матрицы за ${\displaystyle O(n^{3}/\log n)}$ . С некоторыми изменениями можно получить время работы ${\displaystyle O(n^{3}/\log ^{2}n)}$ . В 2015 году был получен алгоритм, работающий за ${\displaystyle {\hat {O}}(n^{3}/\log ^{4}n)}$ .

Идея

Основная идея метода состоит в том, чтобы разделить матрицу на небольшие квадратные блоки размером ${\displaystyle t\times t}$ для некоторого параметра ${\displaystyle t}$ и использовать таблицу поиска для быстрого выполнения алгоритма в каждом блоке. Индекс в таблице поиска кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а значения в таблице поиска кодируют значения граничных ячеек в правом нижнем углу блока после операции. Таким образом, общий алгоритм может быть выполнен с использованием только ${\displaystyle (n/t)^{2}}$ блоков вместо ${\displaystyle n^{2}}$ ячеек матрицы, где ${\displaystyle n}$ — длина строки матрицы. Для того чтобы размер таблиц поиска (и время, необходимое для их инициализации) было достаточно малым, ${\displaystyle t}$ обычно выбирается равным ${\displaystyle O(\log n)}$ .

Применение

Алгоритмы, к которым может быть применен метод четырех русских:

• вычисление транзитивного замыкания графа,
• умножение булевых матриц ,
• расчет расстояния редактирования ,
• выравнивание последовательности ,
• вычисление индекса для двоичного сопоставления с шаблоном.

В каждом из этих случаев это ускоряет алгоритм в ${\displaystyle \log n}$ или ${\displaystyle \log ^{2}n}$ раз.

Опубликованный Бардом алгоритм инверсии матрицы «Метод четырёх русских» реализован в библиотеке M4RI для быстрой арифметики с плотными матрицами над F2. M4RI используется SageMath и библиотекой PolyBoRi.

Алгоритм умножения булевых матриц

Описание алгоритма

Алгоритм получает на вход две булевы матрицы ${\displaystyle (n\times n)}$ ${\displaystyle A}$ и ${\displaystyle B}$ и возвращает матрицу ${\displaystyle C=AB}$ .

Пусть ${\displaystyle m=\lfloor \log n\rfloor }$ .

Разобьём ${\displaystyle A}$ на матрицы ${\displaystyle A_{1},A_{2},...,A_{\lceil n/m\rceil }}$ , где ${\displaystyle A_{i},1\leq i<\lceil n/m\rceil }$ , состоит из столбцов матрицы ${\displaystyle A}$ с номерами от ${\displaystyle m(i-1)+1}$ до ${\displaystyle mi}$ , а ${\displaystyle A_{\lceil }n/m\rceil }$ — из оставшихся столбцов, к которым добавлены столбцы нулей, если это нужно, чтобы в матрице было ${\displaystyle m}$ столбцов.

Разобьём ${\displaystyle B}$ на матрицы ${\displaystyle B_{1},B_{2},...,B_{\lceil n/m\rceil }}$ , где ${\displaystyle B_{i},1\leq i<\lceil n/m\rceil }$ , состоит из строк матрицы ${\displaystyle B}$ с номерами от ${\displaystyle m(i-1)+1}$ до ${\displaystyle mi}$ , а ${\displaystyle B_{\lceil }n/m\rceil }$ — из оставшихся строк, к которым добавлены строки нулей, если это нужно, чтобы в матрице было ${\displaystyle m}$ строк.

Псевдокод

begin

for ${\displaystyle i\leftarrow 1}$ to ${\displaystyle \lceil n/m\rceil }$ do

begin

comment Вычисляем суммы строк ${\displaystyle b_{1}^{(i)},...,b_{m}^{(i)}}$ матрицы ${\displaystyle B_{i}}$ ;

СУММАСТРОК[ ${\displaystyle 0}$ ] ${\displaystyle \leftarrow \underbrace {[0,0,\cdots ,0]} _{n}}$

for ${\displaystyle j\leftarrow 1}$ to ${\displaystyle 2^{m}-1}$ do

begin

Пусть ${\displaystyle k}$ таково, что ${\displaystyle 2^{k}\leq j<2^{k+1}}$

СУММАСТРОК[ ${\displaystyle j}$ ] ${\displaystyle \leftarrow }$ СУММАСТРОК[ ${\displaystyle j-2^{k}}$ ] ${\displaystyle +b_{k+1}^{(i)}}$

end

Пусть ${\displaystyle C_{i}}$ — матрица,  i-я строка которой равна СУММАСТРОК[ЧИС( ${\displaystyle a_{j}}$ )],

где ${\displaystyle a_{j}}$ — j-я строка матрицы ${\displaystyle A_{i}}$ , ${\displaystyle 1\leq j<n}$ ,

end;

Пусть ${\displaystyle C=\sum _{i=1}^{\lceil n/m\rceil }C_{i}}$

end.

ЧИС(v) — целое число, представленное двоичным вектором v, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС([0,1,1])=6.

Обоснование корректности

Простая индукция по ${\displaystyle j}$ показывает, что СУММАСТРОК[ ${\displaystyle j}$ ] становится равной поразрядной булевой сумме таких строк ${\displaystyle b_{k}}$ матрицы ${\displaystyle B_{i}}$ , что в двоичном представлении числа ${\displaystyle j}$ на ${\displaystyle k}$ -том месте справа стоит 1. Отсюда вытекает, что ${\displaystyle C_{i}=A_{i}B_{i}}$ и ${\displaystyle C=AB}$ .

Время работы

Рассмотрим цикл по ${\displaystyle j}$ . Вычисление и присваивание значений СУММАСТРОК[ ${\displaystyle j}$ ] происходит за ${\displaystyle O(n)}$ . Вычисление ${\displaystyle k}$ занимает время ${\displaystyle O(m)}$ . Итерация цикла выполняется за ${\displaystyle O(n)}$ , всего ${\displaystyle 2^{m}-1}$ итераций. ${\displaystyle m<\log n}$ , ${\displaystyle 2^{m}-1<n}$ , следовательно весь цикл выполнится за ${\displaystyle O((2^{m}-1)n)=O(n^{2})}$ .

Вычисление ЧИС( ${\displaystyle a_{j}}$ ) имеет сложность ${\displaystyle O(m)}$ , а копирование вектора СУММАСТРОК[ЧИС( ${\displaystyle a_{j}}$ )] — сложность ${\displaystyle O(n)}$ , так что инициализация ${\displaystyle C_{i}}$ выполняется за ${\displaystyle O(n^{2})}$ . Итого, цикл по ${\displaystyle i}$ выполняется за ${\displaystyle O(n^{2})}$ . Всего ${\displaystyle \lceil n/m\rceil }$ итераций. ${\displaystyle \lceil n/m\rceil <2n/\log n}$ , следовательно сложность цикла — ${\displaystyle O(n^{3}/\log n)}$ .

Сумма ${\displaystyle C_{i}}$ вычисляется за ${\displaystyle O(n^{2}*\lceil n/m\rceil )=O(n^{3}/\log n)}$ .

Итоговая сложность алгоритма — ${\displaystyle O(n^{3}/\log n)}$ .

История

Алгоритм был введён В. Л. Арлазаровым , , и в 1970 году. Происхождение названия неизвестно; Ахо, Хопкрофт и Ульман (1974) объясняют:

Второй метод, часто называемый алгоритмом «четырёх русских», в честь его изобретателей, в какой-то мере «практичнее» алгоритма в теореме 6.9.

Все четыре автора работали в Москве в то время.

Примечания