Конспект раздела: строки

Карта раздела

ЧТО ГОТОВИМ ЗАРАНЕЕ               ЧТО ПОЛУЧАЕМ
ничего                            наивный поиск: от n до n · m
хеш образца                       Рабин-Карп: n + m в среднем (худший n · m), ложных срабатываний около n / q
префикс-функцию образца           КМП: не больше 2n сравнений, текст можно читать потоком
таблицу переходов по образцу      автомат: ровно n обращений, память (m + 1) · k
таблицы сдвигов по образцу        Бойер-Мур: от n / m, часть текста не читается вовсе
бор всех образцов со ссылками     Ахо-Корасик: 2n переходов при любом числе образцов
суффиксный массив ТЕКСТА          запрос за m · log n, от длины текста почти не зависит
суффиксное дерево ТЕКСТА          запрос за m

ОДНА МЫСЛЬ НА ВЕСЬ РАЗДЕЛ: не выбрасывать то, что уже узнал о строке.
Наивный поиск после расхождения забывает всё. Остальные алгоритмы отличаются тем,
ЧТО ИМЕННО они помнят и за что этим платят.

Дерево решений: задача о строке - подходящий инструмент

Один образец, один текст?
    ├─ текст обычный, образец короткий        → встроенный поиск языка; внутри Хорспул или двусторонний
    ├─ данные с длинными повторами, чужой ввод → КМП или двусторонний: нужна гарантия
    ├─ текст приходит потоком, вернуться нельзя → КМП или автомат
    ├─ жёсткий предел времени на каждый символ → автомат
    └─ большой алфавит, длинный образец        → Бойер-Мур: прыжки

Образцов много, текст один?
    ├─ все одной длины                         → Рабин-Карп со множеством хешей
    └─ разной длины                            → Ахо-Корасик

Текст один и не меняется, запросов много?
    ├─ память дороже времени                   → суффиксный массив
    ├─ нужны повторы, общие подстроки          → суффиксный массив и LCP
    └─ нужен запрос за длину образца           → суффиксное дерево

Вопрос о началах слов (дополнение, самый длинный префикс)?
    └─ бор

Нужно, чтобы данные занимали меньше?
    ├─ длинные серии одного символа            → RLE
    ├─ повторяющиеся куски                     → LZ77 (gzip, zstd, xz)
    ├─ связный текст, время не важно           → BWT (bzip2) или контекстная модель
    └─ уже сжато или зашифровано               → ничего: закономерностей не осталось

Главные замеры раздела

задача	без приёма	с приёмом	во сколько
тысяча `a`, образец 499 `a` и `b`	наивный 250 500 сравнений	КМП 1 501	167
Z-функция тысячи `a`	по определению 499 500	с Z-блоком 999	500
10 000 латинских букв, образец 20	КМП 10 394 сравнения	Хорспул 760	14
10 000 символов из двух букв, образец 20	Хорспул 14 962	оба правила 5 659	2,6
сто образцов по 6, текст 10 000	сто проходов КМП 1 244 537	Ахо-Корасик 18 140	69
вывод вхождений, тот же текст	цепочка ссылок 32 280 узлов	выходные ссылки 325	99
запрос к тексту 10 000	КМП 12 455 сравнений	суффиксный массив: меньше 250	50
LCP тысячи `a`	по определению 499 500	Касаи 999	500
узлы для суффиксов текста 10 000	обычный бор 49 956 747	суффиксное дерево 16 267	3 071
сто символов, 95 `a` и 5 `b`	Хаффман 100 бит	арифметическое 30	3,3
журнал 826 символов, 6 608 бит	энтропия частот 3 578	LZ77 около 900	4
тот же журнал	LZ77 около 900	контекстная модель порядка 4: 672	1,3
серии в журнале	до BWT 775	после BWT 85	9
обратный BWT, 111 символов	сортировкой 811 415 шагов	LF-отображение 2 280	356

Что проверять в своём коде

ПОИСК
граница цикла i + m <= n, а не <            последняя позиция не теряется
перекрывающиеся вхождения                   после находки k = π[m − 1], а не 0
откат - цикл, а не одна проверка            aaab: 0 1 2 0, а не 0 1 2 1
хеш: остаток неотрицателен, степень x^(m−1), совпадение хешей ПРОВЕРЯЕТСЯ
таблица Хорспула без последней позиции      иначе сдвиг ноль и вечный цикл
сдвиги двух правил - максимум, не сумма

МНОГО ОБРАЗЦОВ
ссылки считаются обходом в ширину; сыновья корня ссылаются на корень
слова, кончающиеся не в своём узле, - через выходные ссылки
число вхождений может превысить длину текста

ИНДЕКСЫ
суффикс сравнивается с образцом по первым m символам
позиции из массива не упорядочены по тексту
текст с символом конца, который меньше всех и встречается один раз

СЖАТИЕ
ссылка LZ77 копируется по одному символу; расстояние - от конца
распаковщик LZW знает особый случай; обе стороны ведут модель одинаково
ни одному возможному исходу не даётся нулевая доля
размер результата распаковки ограничен

Объясни своими словами

Почему наивный поиск квадратичен на aaaa… и почти линеен на обычном тексте.
Что доказывает совпадение хешей в алгоритме Рабина-Карпа и что - несовпадение.
Что такое грань и почему при расхождении КМП берёт π[k − 1].
Откуда оценка 2n у КМП, у Z-функции, у алгоритма Ахо-Корасика и у алгоритма Касаи - и почему это одно и то же рассуждение.
Чем автомат отличается от КМП, если общая цена у них одного порядка.
Почему длинный образец Бойер-Мур ищет быстрее короткого и на каких данных это перестаёт работать.
Зачем узлу бора пометка конца слова.
Почему ссылки в боре считают по уровням.
Почему вхождения образца стоят в суффиксном массиве подряд.
Как из LCP получить число различных подстрок.
Почему нельзя сжать любой файл и что такое энтропия «для модели».
Как ссылка LZ77 с длиной больше расстояния превращается в серию.
Откуда у арифметического кодирования дробные биты.
Почему BWT можно развернуть и почему сам он ничего не сжимает.

Куда это ведёт

Строки были последним разделом, где данные - это последовательность символов без внутреннего смысла. Дальше предмет - числа, и у них смысл есть: делимость, остатки, простота. Многое из этого раздела там отзовётся. Хеш по модулю потребует понимать, что такое модуль и почему он простой. Арифметика на числах длиной во всё сообщение - как в арифметическом кодировании - получит честную цену. А идея «подготовь таблицу один раз, потом отвечай быстро» вернётся в решете и в быстром возведении в степень.

Изображения и видео

Задача	Механизм	Что проверить
Выбрать точность изображения	Метрики, цветность, квантование	Одинаковая шкала, класс данных и важная область
Представить пространственную избыточность	ДКП или многоуровневые полосы	Нормировка, границы, переданные коэффициенты
Восстановить целые без потерь	RCT, 5/3, полный набор данных	Обратимость всех стадий, округление вниз и диапазоны
Проверить 9/7	Четыре lifting-шага и нормировка	Ошибки арифметики и квантования раздельно
Повысить приоритет области	Зависимости ROI и разрядный сдвиг	Маска по поддержкам фильтра, достаточный порог
Использовать похожие кадры	Предсказание, вектор и остаток	Общая реконструкция, цена режима и параметров
Сменить режим опоры	Skip, intra, PB, resampling, поля	Доступность данных, время и согласованная выборка
Назначить порядок вычислений	Граф кадров и слоёв	Опоры, допустимый префикс, буфер и задержка
Изменить объектную сцену	Событие, состояние и отрисовка	Ресурсы, обработчик, время и порядок наложения
Проверить совместимость	Контейнер, кодек, профиль и параметры	Реально требуемые инструменты и ресурсы

Преобразование само по себе не удаляет информацию. Проверяй намеренную потерю точности отдельно от корректности передачи. Последующие предсказания должны использовать согласованную реконструкцию. Дескриптор MPEG-7 помогает описать содержание, но не обязан содержать все данные для восстановления пикселов.