Динамика на отрезках

Сто самых частых слов «Войны и мира» — «и», «в», «не», «что», «он» и ещё 95 — составляют 39,7 % всех слов романа. Положим их в дерево поиска, где слова стоят по алфавиту, и будем искать каждое столько раз, сколько оно встречается в тексте. Сколько сравнений уйдёт на поиск в среднем? Если делить алфавит пополам — 5,55. Если ставить в корень самое частое слово — 4,81. А лучшее дерево даёт 4,40, и в его корне стоит не «и», а «не». Сцена строит все три дерева, а под ними — таблицу, которая нашла лучшее.

Почему не «и», если оно встречается чаще всех — 21 079 раз? В корне оно делит словарь очень неровно. Слева от «и» по алфавиту 32 слова — «а», «в», «был», «его»… — и вместе они встречаются 46 887 раз. Справа 67 слов, среди них «не», «он», «что», «с», «как», «на», и 104 976 употреблений: больше чем вдвое. Всё правое поддерево опустится на уровень глубже, и каждый его поиск станет дороже. «Не» делит ровнее — 94 391 употребление слева, вместе с самим «и», и 70 035 справа, — а «и» оказывается на втором уровне, всего одним сравнением дальше. Правило «самое частое — в корень» об этом не думает и проигрывает 0,41 сравнения на каждом поиске.

Под деревом — пирамида. Её нижний ряд — отрезки алфавита из одного слова, следующий — из двух соседних, и так до вершины, где весь словарь. Каждый блок — одна клетка таблицы динамики: лучшее дерево для этого отрезка. Цвет показывает, где в отрезке стоит его лучший корень. Длинные косые полосы одного цвета — это одно и то же частое слово, которое остаётся лучшим корнем для многих отрезков подряд.

Идея

В задаче о куске последовательности последний (или первый) шаг делит кусок на две части поменьше где-то внутри: корень дерева делит отрезок словаря, последнее умножение делит цепочку матриц, первый распил делит бревно. Части решаются независимо и так же. Значит, состояние — отрезок [i, j], а переход — перебор места разреза k внутри. Отрезки считаются по возрастанию длины: всё, на что опирается отрезок, короче его, и уже готово.

Это динамика на отрезках. От обычной динамики по префиксам она отличается тем, что подзадача — не начало последовательности, а любой её кусок, и кусок может разрезаться где угодно. Плата за это — лишний множитель n: отрезков n(n + 1)/2, и у каждого до n вариантов разреза.

Лучшее дерево поиска

Слова a₁ < a₂ < … < a_n с частотами w₁, …, w_n. Поиск слова в дереве поиска стоит столько сравнений, на какой глубине оно лежит, считая корень первым уровнем. Цена дерева — сумма w_i · глубина(a_i). Пусть C[i][j] — цена лучшего дерева из слов отрезка, а W(i, j) — их суммарная частота. Тогда

Слагаемое W(i, j) появляется потому, что корень добавляет одно сравнение к поиску каждого слова отрезка: все слова поддеревьев опускаются на уровень ниже. Суммы W считаются за O(1) по префиксным суммам.

Обратите внимание, что именно сделало задачу задачей на отрезки: поддерево всегда занимает сплошной кусок алфавита. Если бы порядок не был важен — как в коде Хаффмана, где можно переставлять символы как угодно, — хватило бы жадного слияния двух самых лёгких. Порядок по алфавиту эту свободу отнимает, и вместо жадности приходится перебирать корни.

Дональд Кнут в статье 1971 года заметил больше. Лучший корень отрезка [i, j] лежит между лучшими корнями отрезков [i, j − 1] и [i + 1, j]: если к отрезку справа добавить слово, корень может сдвинуться только вправо. Поэтому корень ищут не по всему отрезку, а между двумя уже известными, и вся таблица считается за O(n²) вместо O(n³). Когда такой приём законен и как он обобщается — в статье об оптимизациях динамики.

Порядок умножения матриц

Умножение матриц ассоциативно: (AB)C = A(BC), и результат от расстановки скобок не зависит. А время — зависит, и сильно. Матрица p × q на матрицу q × r требует p · q · r умножений чисел, и в цепочке из многих матриц разные порядки дают разные промежуточные размеры. В документации функции numpy.linalg.multi_dot есть пример из четырёх матриц: 10 000 × 100, 100 × 1000, 1000 × 5 и 5 × 333. Слева направо их умножение стоит больше миллиарда умножений чисел, а лучший порядок — 22 миллиона, в 48 раз меньше.

Задача — снова про отрезки. Последнее умножение делит цепочку A_i … A_j на две части, A_i … A_k и A_k+1 … A_j, и стоит p_i−1 · p_k · p_j, где p — размеры по цепочке:

Это ровно то, что делает numpy: в исходниках multi_dot функция _multi_dot_matrix_chain_order заполняет таблицы стоимостей и разрезов по возрастанию длины отрезка, а комментарий говорит, что реализация «близко следует» главе учебника Кормена, Лейзерсона, Ривеста и Штайна. Порядков, которые она выбирает из, — числа Каталана: для четырёх матриц их 5, для шести — 42, для двадцати — больше миллиарда. Таблица перебирает их все, не перечисляя ни одного: каждый порядок — это выбор последнего умножения плюс порядки двух частей.

Переключитесь на «строка × … × столбец»: строка из 1000 чисел, две матрицы 1000 × 1000 и столбец. Если сначала перемножить две большие матрицы, это миллиард умножений; если везти строку через цепочку — пара миллионов. Отсюда простое правило: если в цепочке есть вектор, умножать начинают с него, а не с матриц друг на друга.

Код

Словарь из начала статьи. Листинг сам считает слова романа в песочнице, берёт сто самых частых, строит три дерева и печатает первые уровни лучшего.

Таблица — 5050 отрезков и 171 700 шагов: по шагу на каждую пару «отрезок, корень». Корень «не», под ним «и» и «с», ещё ниже «в», «как», «он», «что».

Порядок умножения: пример numpy и цепочка из шести матриц из учебника Кормена и соавторов, где лучший порядок стоит 15 125 умножений. Вместе с лучшим порядком листинг ищет и худший — той же таблицей, где минимум заменён максимумом.

Сколько это стоит

Отрезков n(n + 1)/2, у отрезка длины ℓ — ℓ вариантов разреза; всего около n³/6 шагов, время O(n³), память O(n²) на таблицу. Для ста слов это 171 700 шагов, для тысячи — уже 167 миллионов.

Наклон перебора всех корней — 3: вдвое больше слов, в восемь раз дольше. С окном Кнута наклон 2. На четырёхстах словах в Python это 3,1 секунды против 0,11 — почти в тридцать раз быстрее, и разрыв растёт. Без такого наблюдения динамика на отрезках остаётся кубической, и n около тысячи — её предел; задачи с n до ста-двухсот она решает сразу.

Где работает

Линейная алгебра. numpy.linalg.multi_dot выбирает порядок умножения цепочки массивов этой динамикой. Для трёх матриц numpy сравнивает два порядка напрямую, для большего числа — строит таблицу. Если цепочка длинная, есть и более быстрый алгоритм: Т. Ч. Ху и М. Т. Шинг в начале 1980-х нашли решение за O(n log n), сведя задачу к разрезанию многоугольника на треугольники.

Биология. Молекула РНК сворачивается сама на себя: основания на разных концах цепочки образуют пары, и форма молекулы определяет её работу. Пары не пересекаются — внутри «шпильки» из пары (i, j) все остальные пары лежат либо целиком внутри отрезка, либо снаружи. Это снова отрезки: Рут Нусинов в конце 1970-х предложила динамику, которая находит укладку с наибольшим числом пар за O(n³), а более точные модели считают не пары, а энергию. Программы пакета ViennaRNA строят таблицы по всем отрезкам последовательности по схеме Майкла Цукера и Патрика Стиглера 1981 года.

Разбор предложений. Алгоритм Кока — Янгера — Касами проверяет, выводится ли предложение из грамматики, той же пирамидой: клетка для отрезка предложения хранит, какими частями грамматики этот отрезок может быть, а собирается из двух клеток поменьше.

Задачи с разрезами и слияниями. Распилить бревно, склеить соседние куски, расставить скобки в выражении, разрезать многоугольник на треугольники — всё, где последний шаг делит отрезок на два и порядок элементов менять нельзя.

История

Лучшие деревья поиска считали ещё в конце 1950-х: Эдгар Гилберт и Эдвард Мур решали близкую задачу о кодах, сохраняющих алфавитный порядок, кубической динамикой. Дональд Кнут в статье «Optimum binary search trees» в первом томе журнала Acta Informatica (1971) построил таблицу для деревьев поиска с частотами не только слов, но и промежутков между ними — поисков, которые ничего не находят, — и показал, что корни монотонны и таблица считается за квадратичное время. Задача о порядке умножения матриц — классический пример из учебника Кормена, Лейзерсона, Ривеста и Штайна, по главе которого и написан multi_dot.

Задачи

Первая — распил бревна, где каждый распил стоит длину куска: самая прямая задача на отрезки. Во второй нужно расставить скобки так, чтобы выражение стало наибольшим, и одного максимума на отрезок не хватит.