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

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

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

ИдеяПравить

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

ПрименениеПравить

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

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

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

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

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

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

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

Пусть $m=\lfloor <!--\; \lfloor \; -->\log <!--\; \; -->n\rfloor <!--\; \rfloor \; -->$$m=\lfloor \log n\rfloor$ .

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

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

ПсевдокодПравить

begin

  for $i\leftarrow <!--\; \leftarrow \; -->1$$i\leftarrow 1$  to $\lceil <!--\; \lceil \; -->n/m\rceil <!--\; \rceil \; -->$$\lceil n/m\rceil$  do

  begin

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

    СУММАСТРОК[$0$$0$ ] $\leftarrow <!--\; \leftarrow \; -->\underset{n}{\underset{⏟<!--\; ⏟\; -->}{[0,0,\cdots <!--\; \cdots \; -->,0]}}$$\leftarrow \underbrace {[0,0,\cdots ,0]} _{n}$ 

    for $j\leftarrow <!--\; \leftarrow \; -->1$$j\leftarrow 1$  to $2^m-<!--\; -\; -->1$$2^{m}-1$  do

    begin

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

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

    end

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

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

  end;

  Пусть $C=\underset{i=1}{\overset{\lceil <!--\; \lceil \; -->n/m\rceil <!--\; \rceil \; -->}{\sum <!--\; \sum \; -->}}{C}_i$$C=\sum _{i=1}^{\lceil n/m\rceil }C_{i}$ 

end.

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

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

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

Время работыПравить

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

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

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

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

ИсторияПравить

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

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

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