Какой вопрос решают
Насколько отличаются две строки, если вставка, удаление и замена стоят по единице? Например, насколько изменился документ. Для коротких строк точная динамическая программа проста; для длинных квадратичная таблица дорога.
Заявлен единый случайный алгоритм, оценивающий расстояние с множителем 1+ε за ожидаемое N^(1+o(1)) для каждой фиксированной ε. Это не совместная эффективная оценка при ε, убывающей с N.
Почему выбрано: Очень распространённая задача, но особенно важно не продать асимптотику как ускорение библиотечного diff.
До и после
Классическая динамика решает точную задачу; введение сопоставляет новый результат с условной трудностью сильно субквадратичного точного решения и более грубыми приближениями. Эти ограничения не доказывают превосходство нового алгоритма на коротких, похожих или структурированных строках.
Это сопоставление по введению рукописи. Независимый исчерпывающий обзор приоритета не выполнен.
Точное утверждение и условия
121-01, теорема 1.1, PDF с. 3: явные целочисленные строки общей длины N, символы полиномиальной величины и O(log N)-битовое слово. При рациональной ε∈(0,1) выдаётся целая оценка ED≤D̂≤(1+ε)ED с вероятностью ≥2/3. Для одинаковых строк точный ноль. Временная оценка — максимум ожидаемого времени по входам при каждой фиксированной ε. Требование вывести последовательность правок не входит в утверждение.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Загрузка локального эксперимента…
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Организовать подзадачи выравнивания по масштабам и получить начальные оценки.
Уточнять дорогостоящие области с бюджетом ошибки и контролировать потерю относительно оптимального пути.
Ограничить ожидаемое число вычислений; для недостаточно больших N разрешён точный запасной алгоритм с огромным порогом переключения.
Что известно о проверке
Scope notes описывают заявленную теорему приближения. Без исходников не проверены ни вычислительная модель, ни переход от формальной оценки к коду.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Стенд маршрутизации задач между точным DP, полосовым методом и существующими приближениями. Сначала измерять реальные режимы строк; экспериментальная реализация новой конструкции — следующий, гораздо более дорогой этап.
Ограничения переноса
Нет гарантии малого полинома от 1/ε, практического порога или готового edit script. Байты, Unicode-кодовые точки и пользовательские символы могут давать разные расстояния. Взвешенные правки — другая задача.
Планы проверки: Профилировщик расстояния редактирования.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
121-01 · An Almost-Linear Approximation Scheme for Edit Distance
Реальный охват: Просмотрены PDF с. 1–4: Аннотация, теорема, история и начало архитектуры. Полный объём PDF: 46 с.
math_sources/math_research_07_of_08/preprints/An-Almost-Linear-Approximation-Scheme-for-Edit-Distance-September-24-2026/paper.pdfSHA-256: 7ecda63faaa7d6a3ff36852775a6a015a8d832ace341a534af86a375d1d89807Каталог: context/CONTENTS.md, строка 2970. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 2963. Структурированные заметки · Журнал внешней сверки.