Русская Википедия:Алгоритм четырёх русских
Алгоритм четырёх русских — в информатике представляет собой метод ускорения алгоритмов с использованием булевых матриц или, в более общем смысле, алгоритмов с использованием матриц, в которых каждая ячейка может принимать только ограниченное число возможных значений.
Разработанный комбинаторный алгоритм позволяет умножать матрицы за <math>O(n^3/\log n)</math>. С некоторыми изменениями можно получить время работы <math>O(n^3/\log^2 n)</math>. В 2015 году был получен алгоритм, работающий за <math>\hat{O}(n^3/\log ^4 n)</math>.[1]
Идея
Основная идея метода состоит в том, чтобы разделить матрицу на небольшие квадратные блоки размером <math>t \times t </math> для некоторого параметра <math>t</math> и использовать таблицу поиска для быстрого выполнения алгоритма в каждом блоке. Индекс в таблице поиска кодирует значения ячеек матрицы в верхнем левом углу границы блока до некоторой операции алгоритма, а значения в таблице поиска кодируют значения граничных ячеек в правом нижнем углу блока после операции. Таким образом, общий алгоритм может быть выполнен с использованием только <math>(n/t)^2</math> блоков вместо <math>n^2</math> ячеек матрицы, где <math>n</math> — длина строки матрицы. Для того чтобы размер таблиц поиска (и время, необходимое для их инициализации) было достаточно малым, <math>t</math> обычно выбирается равным <math>O(\log n)</math>.
Применение
Алгоритмы, к которым может быть применен метод четырех русских:
- вычисление транзитивного замыкания графа,
- умножение булевых матриц,
- расчет расстояния редактирования,
- выравнивание последовательности,
- вычисление индекса для двоичного сопоставления с шаблоном.
В каждом из этих случаев это ускоряет алгоритм в <math>\log n</math> или <math>\log^2 n</math> раз.
Опубликованный Бардом алгоритм инверсии матрицы «Метод четырёх русских» реализован в библиотеке M4RI для быстрой арифметики с плотными матрицами над F2. M4RI используется SageMath и библиотекой PolyBoRi.[1]
Алгоритм умножения булевых матриц
Описание алгоритма
Алгоритм получает на вход две булевы матрицы <math>(n\times n)</math> <math>A</math> и <math>B</math> и возвращает матрицу <math>C=AB</math>.
Пусть <math>m=\lfloor \log n\rfloor</math>.
Разобьём <math>A</math> на матрицы <math>A_1, A_2, ..., A_{\lceil n/m \rceil}</math>, где <math>A_i, 1\leq i < \lceil n/m \rceil</math>, состоит из столбцов матрицы <math>A</math> с номерами от <math>m(i-1)+1</math> до <math>mi</math>, а <math>A_\lceil n/m \rceil</math> — из оставшихся столбцов, к которым добавлены столбцы нулей, если это нужно, чтобы в матрице было <math>m</math> столбцов.
Разобьём <math>B</math> на матрицы <math>B_1, B_2, ..., B_{\lceil n/m \rceil}</math>, где <math>B_i, 1\leq i < \lceil n/m \rceil</math>, состоит из строк матрицы <math>B</math> с номерами от <math>m(i-1)+1</math> до <math>mi</math>, а <math>B_\lceil n/m \rceil</math> — из оставшихся строк, к которым добавлены строки нулей, если это нужно, чтобы в матрице было <math>m</math> строк.
Псевдокод
begin
for <math>i \leftarrow 1</math> to <math>\lceil n/m\rceil</math> do
begin
comment Вычисляем суммы строк <math>b_1^{(i)}, ..., b_m^{(i)}</math> матрицы <math>B_i</math>;
СУММАСТРОК[<math>0 </math>] <math>\leftarrow \underbrace{[0, 0, \cdots, 0]}_{n}</math>
for <math>j \leftarrow 1</math> to <math>2^m - 1</math> do
begin
Пусть <math>k</math> таково, что <math>2^k\leq j < 2^{k+1} </math>
СУММАСТРОК[<math>j</math>]<math>\leftarrow </math>СУММАСТРОК[<math>j-2^k </math>]<math>+b_{k+1}^{(i)} </math>
end
Пусть <math>C_i</math> — матрица, i-я строка которой равна СУММАСТРОК[ЧИС(<math>a_j</math>)],
где <math>a_j </math> — j-я строка матрицы <math>A_i</math>, <math>1\leq j < n </math>,
end;
Пусть <math>C=\sum_{i=1}^{\lceil n/m\rceil}C_i </math>
end.[2]
ЧИС(v) — целое число, представленное двоичным вектором v, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС([0,1,1])=6.
Обоснование корректности
Простая индукция по <math>j</math> показывает, что СУММАСТРОК[<math>j</math>] становится равной поразрядной булевой сумме таких строк <math>b_k</math> матрицы <math>B_i</math>, что в двоичном представлении числа <math>j</math> на <math>k</math>-том месте справа стоит 1. Отсюда вытекает, что <math>C_i=A_iB_i</math> и <math>C=AB</math>.
Время работы
Рассмотрим цикл по <math>j</math>. Вычисление и присваивание значений СУММАСТРОК[<math>j</math>] происходит за <math>O(n)</math>. Вычисление <math>k</math> занимает время <math>O(m)</math>. Итерация цикла выполняется за <math>O(n)</math>, всего <math>2^m-1</math> итераций. <math>m<\log n </math>, <math>2^m-1<n</math>, следовательно весь цикл выполнится за <math>O((2^m-1)n)=O(n^2)</math>.
Вычисление ЧИС(<math>a_j </math>) имеет сложность <math>O(m)</math>, а копирование вектора СУММАСТРОК[ЧИС(<math>a_j </math>)] — сложность <math>O(n)</math>, так что инициализация <math>C_i</math> выполняется за <math>O(n^2)</math>. Итого, цикл по <math>i</math> выполняется за <math>O(n^2)</math>. Всего <math>\lceil n/m\rceil</math> итераций. <math>\lceil n/m\rceil<2n/\log n</math>, следовательно сложность цикла — <math>O(n^3/ \log n)</math>.
Сумма <math>C_i</math> вычисляется за <math>O(n^2*\lceil n/m\rceil)=O(n^3/ \log n) </math>.
Итоговая сложность алгоритма — <math>O(n^3/ \log n)</math>.
История
Алгоритм был введён В. Л. Арлазаровым, Е. А. Диницем, М. А. Кронродом и И. А. Фараджевым в 1970 году. Происхождение названия неизвестно; Ахо, Хопкрофт и Ульман (1974) объясняют:
- Второй метод, часто называемый алгоритмом «четырёх русских», в честь его изобретателей, в какой-то мере «практичнее» алгоритма в теореме 6.9.[2]
Все четыре автора работали в Москве в то время.[3]
Примечания
- ↑ Шаблон:Статья
- ↑ 2,0 2,1 А. Ахо, Дж. Ульман, Дж. Хопкрофт. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979
- ↑ Шаблон:Cite web
