Наименьшие достаточные множества как мера повторяемости

Основная информация

• ID статьи: 2506.05638
• Название: Smallest Suffixient Sets as a Repetitiveness Measure
• Авторы: Gonzalo Navarro (Университет Чили), Giuseppe Romana (Университет Палермо), Cristian Urbina (Университет Чили)
• Классификация: cs.FL (Формальные языки), cs.DS (Структуры данных), math.CO (Комбинаторика)
• Дата публикации: 29 октября 2025 г. (arXiv v2)
• Ссылка на статью: https://arxiv.org/abs/2506.05638

Аннотация

В данной работе исследуются свойства достаточных множеств (suffixient sets) как новых комбинаторных объектов для измерения повторяемости. Достаточные множества способны захватывать существенную информацию повторяющихся строк и поддерживают различные операции поиска по образцу при наличии механизма случайного доступа. Статья глубоко изучает размер χ наименьшего достаточного множества как меру повторяемости: позиционирует его среди известных мер, исследует его чувствительность к различным операциям над строками. Как побочный продукт исследования, авторы предлагают простой онлайн-алгоритм для вычисления наименьшего достаточного множества.

Исследовательский контекст и мотивация

1. Проблема, которую необходимо решить

С появлением крупномасштабных наборов похожих строк (таких как данные человеческого генома) возникает ключевая задача эффективного представления и запроса высоко повторяющихся строк. Например, европейский проект "1+ Million Genomes" нацелен на секвенирование более одного миллиона человеческих геномов, где исходные данные требуют примерно 750 ТБ дискового пространства, но благодаря высокой схожести между геномами можно сжать объем хранилища на два порядка величины.

2. Значимость проблемы

Понимание способов измерения повторяемости критично для:

• Разработки сжатых представлений с сохранением функций доступа и поиска
• Оценки пространственной эффективности различных схем сжатия
• Понимания взаимосвязей между различными мерами, что позволяет уточнить, какие функции поиска можно получить при каких затратах пространства

3. Ограничения существующих подходов

Предложено множество мер повторяемости, от абстрактных нижних границ до мер, связанных с конкретными компрессорами текста. Для недавно предложенного размера достаточного множества χ известно только:

• γ = O(χ) (γ — размер наименьшего string attractor)
• χ = O(r̄) (r̄ — количество равных букв серий в обратном BWT)

Однако более глубокое понимание χ как меры повторяемости все еще отсутствует, в частности:

• Точные отношения χ с другими мерами
• Чувствительность χ к операциям над строками
• Достижимость (reachability) χ

4. Исследовательская мотивация

Данная работа направлена на лучшую характеризацию χ как меры повторяемости, с особым акцентом на:

• Позиционирование χ в известной системе мер
• Исследование влияния операций обновления строк на χ
• Исследование сравнимости χ с мерами типа copy-paste
• Предоставление эффективного алгоритма вычисления χ

Основные вклады

1. Установление прямого отношения между χ и количеством серий BWT r: Доказано, что χ = O(r) (вместо предыдущего χ = O(r̄)), и на некоторых семействах строк доказано χ = o(v) (v — размер минимального словарного разбора), что устанавливает χ строго меньше r
2. Анализ чувствительности операций над строками:
   • Доказано, что χ растет на O(1) при добавлении/предварении одного символа
   • Доказано, что любая операция редактирования или ротация может увеличить χ на Ω(log n)
   • Доказано, что обращение строки может увеличить χ на Ω(√n)
3. Полная характеризация строк Фибоначчи: Полностью охарактеризованы единственные 2 наименьших достаточных множества размера 4 для строк Фибоначчи, и доказано, что все подстроки эпистурмовых слов удовлетворяют χ ≤ σ + 2
4. Несравнимость с мерами copy-paste: Доказано, что χ несравнима с большинством мер типа copy-paste (z, z_no, z_e, z_end, v, g, g_rl, c) — существуют семейства строк, где χ строго меньше, и семейства, где χ строго больше
5. Простой онлайн-алгоритм: Предложен исключительно простой онлайн-алгоритм, модифицирующий алгоритм построения суффиксного дерева Укконена, который вычисляет наименьшее достаточное множество за O(n) пространства и O(n) наихудшего времени

Подробное описание методов

Определение задачи

Основные определения:

1. Right-maximal подстрока: Подстрока x является right-maximal, если существуют по крайней мере два различных символа a, b ∈ Σ такие, что xa и xb оба являются подстроками w
2. Right-extension: Для каждой right-maximal подстроки x, её right-extensions — это подстроки вида xa, обозначаемые E_r(w)
3. Super-maximal extension: Right-extension, который не является суффиксом никакого другого right-extension, обозначаемый S_r(w), его размер обозначается sre(w)
4. Достаточное множество: Множество S ⊆ 1..n является достаточным множеством для w, если для каждого right-extension x ∈ E_r(w) существует j ∈ S такой, что x является суффиксом w1..j
5. Наименьшее достаточное множество: Достаточное множество S является наименьшим, если существует биекция pos: S_r(w) → S такая, что каждый x ∈ S_r(w) является суффиксом w1..pos(x)
6. Мера χ: Для w ∈ Σ* и $∉ F_w определяется χ(w) = |S|, где S — наименьшее достаточное множество w$

Теоретическая аналитическая база

1. Влияние добавления символа (ключевая лемма)

Лемма 2: Пусть w ∈ Σ*, c ∈ Σ, тогда:

sre(w) ≤ sre(wc) ≤ sre(w) + 2

Идея доказательства: Анализ возможных новых right-extensions после добавления c:

• Случай 1: xc уже появляется в w, или xa не появляется в w для любого a≠c → не создаются новые right-extensions
• Случай 2: Существуют a≠b такие, что xa и xb оба в w, но xc не в w → xc является новым right-extension
• Случай 3: x в w всегда следует за a≠c (поэтому xa не является right-extension) → xa и xc оба являются новыми right-extensions

Ключевое наблюдение:

• Случаи 1 и 2 вместе создают максимум 1 новый super-maximal right-extension
• В случае 3 для фиксированного a все новые right-extensions x₁a, x₂a, ..., x_ta образуют цепь суффиксов, только x_ta может быть super-maximal

Поэтому добавляется максимум 2 super-maximal right-extensions.

2. Отношение с количеством серий BWT r

Лемма 9: χ ≤ 2r

Идея доказательства:

• Пусть x_i — i-я циклическая ротация w$ в лексикографическом порядке
• Пусть u_i — наибольший общий префикс x_i и x_{i+1}
• Определим s(i) как циклический сдвиг, необходимый для получения w$ из x_i

Построение достаточного множества:

S = ∪_{i∈[1..|w|]} {s(i) + |u_i| + 1, s(i+1) + |u_i| + 1}

Используя свойства матрицы BWT: если BWTi = BWTi+1 = c, то существует j такой, что соответствующие позиции совпадают. Поэтому:

S = {s(i) + |u_i| + 1, s(i+1) + |u_i| + 1 | BWT[i] ≠ BWT[i+1]}

|S| ≤ 2r (r — количество равных букв серий в BWT).

3. Анализ чувствительности

Последовательности де Брейна (для нижних границ):

• k-порядковая двоичная последовательность де Брейна содержит все двоичные строки длины k ровно один раз
• Длина n = 2^k + (k-1)
• Лемма 5: sre(w) = 2^k = Ω(n) для любого w ∈ dB(k)

Нижняя граница Ω(log n) для операций редактирования (Лемма 6): Используется лексикографически минимальная последовательность де Брейна w = a^k b a^{k-2} b x a b^k a^{k-1}:

• Вставка: sre(w) - sre(w') = 2^k - 2
• Замена: sre(w) - sre(w') = 2^k - 3
• Удаление: sre(w) - sre(w') = 2^k - 4
• Ротация: sre(w) - sre(w') = 2^k - 2

Нижняя граница Ω(√n) для обращения (Лемма 7): Построение w_k = ∏_^{k-1} c a^i b a^{k-i-1} #_i a^i b a^{k-i-1} $_i:

• sre(w_k) - sre(w_k^R) = k - 1
• |w_k| = Θ(k²)
• Поэтому рост составляет Ω(√n)

4. Свойства эпистурмовых слов

Лемма 10: Для эпистурмова слова w над алфавитом размера σ любая подстрока wi..j удовлетворяет:

sre(w[i..j]) ≤ σ

Идея доказательства:

• Эпистурмово слово имеет максимум одну right-maximal подстроку каждой длины
• Right-extensions, заканчивающиеся на a ∈ Σ, образуют цепь суффиксов
• Всего σ таких цепей суффиксов
• Каждая цепь вносит максимум 1 super-maximal right-extension в подстроку

Следствие 3: Для любого эпистурмова слова w, χ(wi..j) ≤ σ + 2

Точная характеризация строк Фибоначчи (Лемма 11):

• F_1 = b, F_2 = a, F_k = F_F_
• Для k ≥ 6 единственные наименьшие достаточные множества F_k$ это:

  {f_{k+1}, f_{k-1}, f_{k-1}-1, p}, где p ∈ {f_{k-2}+1, 2f_{k-2}+1}
  

Разработка онлайн-алгоритма

Основная идея

Модификация алгоритма онлайн-построения суффиксного дерева Укконена с одновременным поддержанием наименьшего достаточного множества.

Ключевые моменты алгоритма

Расширение суффиксного дерева: Добавление меток на узлы суффиксного дерева, отмечающих позиции super-maximal right-extensions.

Обработка трёх случаев при добавлении символа c:

1. s имеет дочерний узел с меткой c (Случай 1):
   • Только спуск к новому s
   • Обновление меток не требуется
2. s имеет ≥2 дочерних узлов, без метки c (Случай 2):
   • Создание нового листового узла s (метка c)
   • Отметить дочерний узел s с меткой c
   • Снять отметку с дочернего узла s' с меткой c (если отмечен)
3. s имеет только один дочерний узел (метка a≠c) (Случай 3):
   • Отметить оба дочерних узла s (a и c)
   • Снять отметку с дочернего узла s' с меткой c (если отмечен)
   • Снять отметку с дочернего узла s'' с меткой a (если отмечен), где s'' — первый узел в цепи суффиксов с другим дочерним узлом b≠a

Сложность:

• Пространство: O(n)
• Время: O(n) (в трансдихотомной RAM-модели с целыми числами полиномиального размера)

Теорема 1: Существует алгоритм, обрабатывающий текст T слева направо, который после обработки префикса T1..n определяет наименьшее достаточное множество T1..n, используя O(n) пространства и O(n) наихудшего времени.

Экспериментальная установка

Примечание: Данная статья является теоретической работой, основные вклады которой — теоретические результаты и алгоритмы, без традиционного раздела экспериментальной оценки. "Экспериментами" в этой работе являются математические доказательства и конструктивные примеры для проверки теоретических результатов.

Методы теоретической верификации

1. Конструктивные доказательства: Через построение специфических семейств строк (таких как последовательности де Брейна, строки Фибоначчи) для доказательства плотности границ
2. Построение контрпримеров: Через конкретные примеры (как Example 1 с w_3) для демонстрации корректности теоретических результатов
3. Проверка кода: В благодарностях авторы упоминают использование кода Cenzato и др. для вычисления наименьших достаточных множеств, применяемого для выдвижения и проверки гипотез

Результаты исследования

Основные теоретические результаты

1. Отношение χ с известными мерами

Верхние границы:

• χ ≤ 2r (Лемма 9)
• χ = O(r)

Нижние границы:

• γ = O(χ) (известный результат 4)
• δ ≤ χ (известный результат 4)

Результаты разделения:

• Существуют семейства строк такие, что χ = o(v) (Следствие 4, строки Фибоначчи)
• Поскольку v = O(r), это означает, что χ строго меньше r

2. Сводка результатов чувствительности

3. Точные значения для специфических семейств строк

Эпистурмовы слова:

• χ(wi..j) ≤ σ + 2 (Следствие 3)

Строки Фибоначчи (k ≥ 6):

• χ(F_k) = 4
• Точная характеризация наименьших достаточных множеств (Лемма 11)

Последовательности де Брейна:

• sre(w) = 2^k = Ω(n) (Лемма 5)
• χ = Ω(n)

4. Сравнение с мерами copy-paste

Случаи, где χ строго меньше (строки Фибоначчи):

• χ = O(1)
• c = Ω(log n)
• Поэтому χ = o(µ) для всех µ ∈ {z, z_no, z_e, z_end, v, g, g_rl, c}

Случаи, где χ строго больше (последовательности де Брейна):

• χ = Ω(n)
• g = O(n/log n)
• Поэтому χ = Ω(g log n) (Следствие 5)
• χ = Ω(z_e · log n log log log n / (log log n)²) (Лемма 12)

Вывод (Следствие 6): χ несравнима с µ ∈ {z, z_no, z_e, z_end, v, g, g_rl, c}

Анализ конкретных случаев

Пример 1 (конкретный пример для Леммы 7):

Строка w_3 = cbaa#₀baa₀caba#₁aba₁caab#₂aab$₂

Super-maximal right-extensions:

1. baa и c
2. baa#₀ и baa₀; aba#₁ и aba₁; aab#₂ и aab$₂
3. ca и cb; caa и cab
4. aba и aab

Всего: sre(w_3) = 14

Обращённая строка w_3^R = ₂baa#₂baac₁aba#₁abac$₀aab#₀aabc

Super-maximal right-extensions:

1. baa и $₂
2. baa#₂ и baac; aba#₁ и abac; aab#₀ и aabc
3. ac$₀; ac$₁
4. aba и aab

Всего: sre(w_3^R) = 12

Проверка: sre(w_3) - sre(w_3^R) = 2 = k - 1 ✓

Связанные работы

1. Исследование мер повторяемости

Абстрактные меры нижних границ:

• δ: Мера сложности подстроки, maxₖ(|F_w(k)|/k)
• γ: Размер наименьшего string attractor 18
  • Известно γ = O(χ)
  • Остаётся открытым вопрос, является ли γ достижимой

Меры типа copy-paste:

• z: Размер разбора Лемпеля-Зива 20
• z_no: LZ-разбор без перекрытия источников фраз
• z_e: Размер жадного LZ-End разбора
• z_end: Размер минимального LZ-End разбора
• v: Размер минимального словарного разбора 28
• g: Размер минимальной контекстно-свободной грамматики
• g_rl: Размер грамматики с правилами длины серии
• c: Размер минимальной системы заплат
• b: Размер минимальной двусторонней макросхемы 32

Меры, связанные с BWT:

• r: Количество равных букв серий в BWT 3
  • Единственная известная достижимая и поддерживающая поиск мера, но неизвестно, поддерживает ли она доступ
  • Данная работа доказывает χ < r

2. Исследование чувствительности

Предыдущие исследования рассматривали чувствительность различных мер к операциям над строками:

• Akagi и др. 1: Чувствительность b, z, g к операциям редактирования
• Giuliani и др. 14,15: Чувствительность r к обращению и битовым изменениям
• Fici и др. 9,10: Чувствительность количества серий BWT к морфизмам
• Navarro и др. 29,30: Меры повторяемости на основе морфизмов

3. Достаточные множества

Оригинальные работы 4,6:

• Определение достаточных множеств и связанных концепций
• Доказательство γ = O(χ) и χ = O(r̄)
• Демонстрация поддержки поиска по образцу достаточными множествами

Алгоритмические работы 5:

• Эффективные алгоритмы вычисления наименьших достаточных множеств
• Начиная с компонентов суффиксного массива и суффиксного дерева
• Неонлайновые алгоритмы

Вклад данной работы:

• Более глубокая теоретическая характеризация
• Более простой онлайн-алгоритм
• Прямое построение из текста одновременно с построением суффиксного дерева

4. Эпистурмовы слова и строки Фибоначчи

Комбинаторный фон 8,16,21:

• Эпистурмовы слова: максимум одна right-maximal подстрока каждой длины
• Исследование right-special factors (т.е. right-maximal подстрок)
• Строки Фибоначчи как частный случай epistandard слов

Вклад данной работы:

• Связь достаточных множеств с теорией комбинаторных слов
• Полная характеризация наименьших достаточных множеств строк Фибоначчи
• Доказательство верхней границы χ для подстрок эпистурмовых слов

Заключение и обсуждение

Основные выводы

1. Позиционирование меры: χ установлена как мера, строго меньшая r, удовлетворяющая:
   • γ = O(χ) = O(r)
   • Существуют семейства строк такие, что χ = o(r)
2. Характеристики чувствительности:
   • Аддитивная чувствительность O(1) к добавлению/предварению символов (идеальное свойство)
   • Аддитивная чувствительность Ω(log n) к любым операциям редактирования
   • Аддитивная чувствительность Ω(√n) к обращению
3. Несравнимость с мерами copy-paste: χ ни всегда больше, ни всегда меньше, зависит от семейства строк
4. Эффективное онлайн-вычисление: Возможно вычисление за O(n) времени и пространства в онлайн-режиме

Ограничения

1. Достижимость неизвестна:
   • Остаётся открытым вопрос, является ли χ достижимой (т.е. можно ли представить строку в O(χ) пространстве)
   • Отношение с наименьшей известной достижимой мерой b неизвестно
2. Зависимость от механизма доступа:
   • Поддержка поиска достаточными множествами требует дополнительного механизма случайного доступа
   • В отличие от r, которая может напрямую поддерживать поиск
3. Плотность теоретических границ:
   • χ = O(r) имеет константный множитель 2, который может быть неплотным
   • Точные границы мультипликативной чувствительности остаются неясными
4. Практическая производительность:
   • Работа сосредоточена в основном на теоретических свойствах
   • Производительность на реальных данных требует дальнейшей экспериментальной проверки

Направления будущих исследований

Открытые проблемы, явно сформулированные в статье:

1. Проблема достижимости:
   • Доказательство b = O(χ) установит достижимость χ
   • Или доказательство того, что χ недостижима, одновременно докажет недостижимость γ
2. Отношение с δ:
   • Верно ли χ = O(δ log n)?
   • Является ли множитель Θ(log n) на последовательностях де Брейна плотным?
3. Мультипликативная чувствительность:
   • Верно ли sre(w')/sre(w) = O(1) для всех рассматриваемых операций над строками?
   • Существует ли константная граница для операции вставки?
4. Точное отношение с r:
   • Верно ли r = O(χ log χ)?
   • Если верно и χ имеет O(1) мультипликативную чувствительность к операциям над строками, это сделает известные нижние границы r плотными
5. Отношения с другими мерами:
   • Отношение χ с b (ключевая проблема достижимости)
   • Отношение χ с другими недавно предложенными мерами

Глубокая оценка

Преимущества

1. Прочные теоретические вклады

• Полная характеризация меры: Через анализ верхних и нижних границ и результаты разделения точно позиционирует χ в иерархии мер
• Плотные границы: Через конструктивные доказательства (последовательности де Брейна, строки Фибоначчи) демонстрирует плотность границ
• Многоаспектный анализ: Всестороннее исследование χ с точек зрения чувствительности, специальных семейств строк и отношений с другими мерами

2. Техническая инновативность

• Установление прямого отношения: Доказательство χ = O(r) вместо предыдущего χ = O(r̄) — это более естественная характеризация
• Тонкий анализ: Полная характеризация наименьших достаточных множеств строк Фибоначчи (Лемма 11) демонстрирует глубокие комбинаторные аналитические способности
• Элегантный алгоритм: Упрощение сложного вычисления достаточных множеств до элегантной модификации алгоритма Укконена

3. Ясность изложения

• Строгие определения: Все концепции имеют точные математические определения
• Подробные доказательства: Доказательства ключевых лемм имеют ясную логику, легко проверяются
• Богатые примеры: Конкретные примеры (как Example 1) помогают понять абстрактные концепции
• Наглядные диаграммы: Figure 1 ясно показывает отношения между мерами

4. Практическая ценность

• Онлайн-алгоритм: Онлайн-алгоритм O(n) времени и пространства имеет практическую ценность применения
• Теоретическое руководство: Глубокое понимание χ помогает разработке схем сжатия и индексирования на основе достаточных множеств
• Выбор меры: Предоставляет теоретическое обоснование для выбора подходящей меры повторяемости в практических приложениях

Недостатки

1. Отсутствие экспериментальной проверки

• Нет тестирования на реальных данных: Работа полностью теоретическая, без экспериментов на реальных данных (таких как геномные данные)
• Производительность алгоритма неизвестна: Хотя предоставлен алгоритм O(n), фактическое время выполнения и пространственные константы неизвестны
• Отсутствие сравнения с существующими инструментами: Нет подробного сравнения производительности с реализацией Cenzato и др. 5

2. Нерешённая проблема достижимости

• Ключевой вопрос остаётся открытым: Остаётся неясным, является ли χ достижимой — это центральный вопрос
• Отношение с b неизвестно: Невозможно определить отношение χ с наименьшей известной достижимой мерой
• Ограниченная практическая применимость: Если χ недостижима, её практическая ценность как меры будет ограничена

3. Некоторые границы могут быть неплотными

• Константный множитель: Константа 2 в χ ≤ 2r может быть неоптимальной
• Верхние границы чувствительности: Верхние границы в Лемме 8 относительно сложны, могут быть неплотными
• Мультипликативная чувствительность: Точные границы мультипликативной чувствительности не даны

4. Ограниченный диапазон анализа

• Специальные семейства строк: Анализ сосредоточен на последовательностях де Брейна, строках Фибоначчи и других специальных случаях
• Ограниченные общие результаты: Понимание свойств общих семейств строк ограничено
• Отсутствие анализа среднего случая: Основное внимание уделяется наихудшему случаю, анализ среднего случая отсутствует

Влияние

1. Вклад в область

• Теоретическое совершенствование: Заполняет пробел в теоретическом исследовании достаточных множеств
• Система мер: Обогащает теоретическую базу мер повторяемости
• Открытые проблемы: Предложенные проблемы будут направлять будущие исследования

2. Потенциальные приложения

• Алгоритмы сжатия: Предоставляет теоретическую основу для разработки новых алгоритмов сжатия
• Структуры индексирования: Достаточные множества могут использоваться для построения пространственно-эффективных индексов
• Биоинформатика: Потенциальное применение в сжатии и запросах геномных данных

3. Методологический вклад

• Парадигма онлайн-построения: Демонстрирует, как адаптировать классические алгоритмы суффиксного дерева к новым задачам
• Структура анализа чувствительности: Предоставляет методологический справочник для анализа чувствительности других мер

4. Ограничения

• Хорошая воспроизводимость: Теоретические результаты легко проверяются, описание алгоритма ясно
• Но детали реализации: Некоторые детали реализации (такие как конкретное поддержание меток) требуют дальнейшего уточнения
• Зависимость от предположений: Некоторые результаты зависят от трансдихотомной RAM-модели

Применимые сценарии

1. Идеальные сценарии применения

• Высоко повторяющиеся данные: Такие как геномные последовательности, системы контроля версий, файлы логов
• Требуется поиск по образцу: Достаточные множества естественно поддерживают определённые запросы поиска по образцу
• Онлайн-обработка: Данные поступают потоком, требуется инкрементальное обновление индекса

2. Неприменимые сценарии

• Случайные данные: χ на низко повторяющихся данных может быть близка к n, теряя преимущество
• Требуется точная гарантия пространства: Поскольку достижимость χ неизвестна, нельзя гарантировать реализацию в O(χ) пространстве
• Сложные запросы: Типы запросов, поддерживаемые достаточными множествами, ограничены

3. Сравнение с другими методами

• Сравнение с BWT (r): χ меньше, но требует дополнительного механизма доступа
• Сравнение с LZ (z): χ в некоторых случаях меньше (Фибоначчи), в других больше (де Брейн)
• Сравнение с грамматикой (g): Аналогично несравнима

Библиография

Ключевые ссылки

1. Оригинальные работы по достаточным множествам:
   • 6 Depuydt и др., "Suffixient sets", 2023
   • 4 Cenzato и др., "Suffixient arrays", 2025
2. Вычислительные алгоритмы:
   • 5 Cenzato и др., "On computing the smallest suffixient set", SPIRE 2024
   • 33 Ukkonen, "On-line construction of suffix trees", 1995
3. Обзоры мер повторяемости:
   • 25,26 Navarro, "Indexing highly repetitive string collections", ACM Computing Surveys 2021
   • 27 Navarro, "Indexing highly repetitive string collections", arXiv 2022
4. Связанные меры:
   • 18 Kempa & Prezza, "String attractors", STOC 2018
   • 3 Burrows & Wheeler, "BWT", 1994
   • 20 Lempel & Ziv, "LZ complexity", 1976
   • 28 Navarro и др., "Ordered parsings", IEEE TIT 2021
5. Исследования чувствительности:
   • 1 Akagi и др., "Sensitivity of string compressors", Information and Computation 2023
   • 15 Giuliani и др., "Bit catastrophes for BWT", Theory of Computing Systems 2025

Общая оценка: Это высококачественная теоретическая работа, проводящая глубокий и всесторонний анализ достаточных множеств как меры повторяемости. Основные вклады включают установление прямого отношения χ с r, анализ чувствительности, точную характеризацию специальных семейств строк и простой онлайн-алгоритм. Теоретический анализ работы строг, доказательства подробны, изложение ясно. Основные недостатки — отсутствие экспериментальной проверки и нерешённая проблема достижимости. Работа закладывает прочную основу для теоретического исследования достаточных множеств, предложенные открытые проблемы будут направлять будущие исследования. Рекомендуется, чтобы последующие работы сосредоточились на оценке производительности на реальных данных и решении проблемы достижимости.