Алгоритм четырёх русских

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

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

Идея

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

Применение

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

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

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

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

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

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

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

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

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

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

Псевдокод

begin

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

  begin

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

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

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

    begin

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

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

    end

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

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

  end;

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

end.

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

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

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

Время работы

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

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

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

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

История

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

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

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