Информатика · объяснение и практика

Почему индекс ускоряет поиск ценой места и обновлений

Выбираем индекс для конкретного запроса, отличаем индексный поиск от полного просмотра и проверяем цену хранения и обновления вместо обещания ускорить любой SELECT.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Таблицы, базы данных и SQL · Учебная карта

Главная мысль

Индекс хранит дополнительную структуру для поиска по выбранным ключам. Он может сократить просмотр строк, но занимает место и требует поддержки при изменениях. Полезность определяется запросом, распределением данных и планом выполнения.

Что меняется при точном поиске

В таблице из многих учеников часто ищут запись по фамилии. Без подходящего индекса система может просмотреть все строки и сравнить каждую фамилию. Индекс по этому полю позволяет найти подходящую область и затем нужные строки. Если совпадений мало, работы может быть существенно меньше, чем при полном просмотре.

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

Почему составной индекс имеет порядок полей

Пусть часто выбирают учеников одного класса и сортируют по фамилии. Индекс (class_id, surname) упорядочивает записи сначала по классу, затем по фамилии внутри класса. Такой порядок может поддержать и фильтр, и сортировку. Для поиска только по фамилии тот же индекс не обязательно столь же полезен: первое поле не ограничено.

Нельзя составить один длинный индекс из всех полей и обещать, что он оптимален для любых запросов. Порядок условий, диапазоны, направления сортировки и требуемые столбцы влияют на план. Иногда покрывающий индекс позволяет получить результат без обращения к основной строке, но хранит больше данных. Это обмен между скоростью чтения, размером и стоимостью изменения.

Пример

В таблице 100000 строк, запрос по статусу возвращает 90000. Обязательно ли индекс по статусу быстрее полного просмотра?

Нет. Когда нужна большая часть таблицы, множество обращений через индекс может быть дороже последовательного просмотра. Решение проверяют планом и измерением на подходящих данных.

Как проверить реальную выгоду

При вставке, удалении или изменении индексируемого поля индекс тоже обновляется. Избыточные структуры увеличивают время записи и объём базы. Поэтому добавление индекса — не бесплатное улучшение. Проверяют типичные запросы, частоту записей, место и фактический план, например EXPLAIN QUERY PLAN в SQLite.

Даже используемый индекс не гарантирует заданные миллисекунды: влияют число совпадений, кеш, размер результата и устройство хранения. Поиск подстроки с ведущим шаблонным знаком может не использовать обычный упорядоченный индекс так, как поиск точного ключа. Нужно измерять именно обещанный пользователю режим. Индекс также не задаёт порядок результата без ORDER BY и не заменяет ограничения доступа: ускорение поиска и корректность данных остаются отдельными задачами.

От чтения к действию

А теперь — вы

Что лучше подтверждает полезность индекса для конкретного запроса?

Частые вопросы

Индекс автоматически запрещает одинаковые фамилии?

Нет. Для этого нужно отдельное ограничение уникальности, которое для фамилий обычно было бы неверным.

Каждый новый индекс бесплатен для записи?

Нет. Его нужно хранить и обновлять при соответствующих изменениях данных.

Углублённый разбор

LF-переход восстанавливает строку из преобразования BWT

Преобразование Бэрроуза — Уилера сохраняет текст в последнем столбце отсортированных циклических сдвигов. Восстановление использует стабильный порядок одинаковых букв: их ранги связывают последний столбец с первым. Один уникальный терминатор фиксирует исходное начало и превращает LF-переход в полный цикл.

Перед началом: Лексикографический порядок; Префиксный подсчёт.

Терминатор снимает неоднозначность вращения

Пусть T заканчивается единственным символом $, которого больше нет в тексте и который меньше всех обычных букв. Отсортируем все циклические сдвиги T и возьмём последний столбец L. Первый столбец F получается обычной сортировкой букв L. Если терминатора нет, для восстановления конкретного вращения потребовался бы дополнительный primary index; один L мог бы задавать только циклическую неоднозначность.

Связь одинаковых букв определяется их порядком появления: первая a в L соответствует первой a в F, вторая второй и так далее. После переноса последней буквы в начало оставшаяся часть строки сохраняет относительный лексикографический порядок среди строк с этой буквой. Это свойство стабильности является причиной обратимости, а не предположение, что все одинаковые буквы можно произвольно переставлять.

Формула LF использует один согласованный ранг

Используем индексы с0. Пусть C[c] — число символов текста, строго меньших c, а Occ(c,i) — число c в L[0:i), без позиции i. Тогда LF(i)=C[L[i]]+Occ(L[i],i). Полученная строка начинается на одну позицию раньше в циклическом тексте. Включительный префикс потребовал бы вычитания 1; смешение двух соглашений даёт неверную перестановку.

Чтобы восстановить T, начинаем со строки, у которой L[i]=$. Последовательно выписываем L[i] и заменяем i на LF(i), ровно |T| раз. Символы получаются в обратном порядке, начиная с терминатора; разворот даёт исходный T с $ в конце. У корректного BWT текста с единственным терминатором этот обход посещает все строки. Произвольная строка с одним $ не автоматически является корректным BWT одного такого текста: её LF-перестановка может иметь несколько циклов.

Обратимость не является обещанием сжатия сама по себе

BWT только переставляет символы и сохраняет их количества. Выигрыш сжатия возникает после последующих кодирующих стадий, которым полезны группы похожих контекстов. LF нужен и для восстановления, и для привязки индексных строк к позициям, но не меняет статистику частот букв. Проверка обратного преобразования должна независимо построить сдвиги восстановленного текста и получить тот же L; одного красивого вывода символов недостаточно.

Восстановление из пяти символов

Условие. Дан корректный BWT L=abca$ с порядком $<a<b<c. Восстановите исходный текст, включая терминатор.

  1. Первый столбец F=$aabc. Получаем C[$]=0,C[a]=1,C[b]=3,C[c]=4.
  2. Исключительные ранги одинаковых букв дают LF=[1,3,4,2,0]. В частности две a на позициях 0 и3 переходят в позиции 1 и2 первого столбца.
  3. Начинаем в i=4, где L[i]=$. Индексы идут 4→0→1→3→2→4, а выписанные символы равны $abac.
  4. Разворачиваем пять символов и получаем caba$. Независимая сортировка его циклических сдвигов даёт $caba,a$cab,aba$c,ba$ca,caba$; их последние буквы снова образуют abca$.

Ответ. Исходный текст caba$, LF-перестановка[1,3,4,2,0].

Проверка. Проверены полный пятишаговый цикл без раннего повторения, сохранение частот и независимое прямое BWT восстановленного текста. Терминатор расположен в конце ровно один раз.

Где легко ошибиться. Не смешивайте включительный и исключительный Occ и не забывайте разворачивать собранные LF-символы. Один LF-шаг двигается по исходному тексту назад.

Проверьте понимание

Какой текст восстанавливается из L=abca$ при указанных соглашениях?

Вопросы к этой главе

Почему нельзя сопоставить две буквы a в обратном порядке?

Это разрушает стабильность одинаковых начальных букв и соответствие соседних циклических сдвигов. Ранги, а не только сами символы, определяют правильный LF-переход.

Достаточно ли одного уникального $ для любого введённого L?

Нет. Нужно проверить корректность BWT либо восстановленный полный цикл и прямое преобразование. Например, LF может распасться на несколько циклов, что не соответствует одному тексту выбранной модели.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Johannes Fischer: Lecture8, Backwards Search and FM Indices

    Прочитаны BWT, стабильный LF-переход одинаковых букв, C и OCC, а также выборка позиций через LF. В источнике индексация 1-based с включительным OCC; здесь 0-based и префикс[0,i). Строка caba$ и её LF-цикл вычислены самостоятельно.

Обратный поиск FM-индекса сжимает интервал суффиксов

FM-индекс ищет образец, расширяя его справа налево и сужая интервал подходящих суффиксов. Для каждого шага нужны только BWT и подсчёты букв в префиксах. Размер интервала даёт число вхождений, а восстановление их позиций требует отдельной информации.

Перед началом: BWT и LF; Полуоткрытый интервал.

Одинаковый префикс образует непрерывный интервал суффиксов

Пусть текст T имеет уникальный минимальный терминатор $, а SA — лексикографический порядок его суффиксов. Все суффиксы, начинающиеся со слова P, стоят подряд. Храним их полуоткрытый интервал [l,r). Для пустого образца это весь [0,n). Буква L[i] в BWT показывает символ непосредственно перед началом суффикса SA[i], с циклическим соглашением у начала текста.

При добавлении буквы c слева нужны только те строки текущего интервала, у которых L[i]=c. Их LF-образы стоят подряд среди суффиксов, начинающихся с c. Так поиск длинного слова сводится к двум границам, а не к посимвольному сравнению с каждым суффиксом. Образцы здесь непустые и не содержат терминатора, чтобы циклическое соглашение не создавало запросов через конец текста.

Две операции rank обновляют обе границы

Определим C[c] как число символов текста, строго меньших c, и Occ(c,i) как количество c в L[0:i). Тогда для добавления c слева новый интервал равен [C[c]+Occ(c,l),C[c]+Occ(c,r)). Формула применяет один и тот же исключительный подсчёт к обеим границам. Число оставшихся строк r−l равно числу вхождений расширенного образца.

Если l=r, совпадений нет и дальнейшее расширение не может их создать. Нельзя продолжать из полного интервала, как будто поиск начался заново. Если буквы c вообще нет в алфавите текста, ответ также пустой; реализация может обработать это до обращения к таблице C. Проход по образцу идёт в обратном порядке: обычный левый проход этой формулой искал бы другое слово.

Подсчёт и выдача координат имеют разные расходы

При rank за O(1) время counting составляет O(|P|). Хранение полных префиксных счётчиков для каждой буквы требует места, поэтому сжатые индексы используют битовые последовательности и структуры rank. Для locating нужны значения SA или их выборка: LF уменьшает исходную позицию на1, позволяя дойти до сохранённой опоры. Сам размер интервала ещё не сообщает, в каких координатах текста найдены вхождения, и не должен выдаваться за готовый список позиций.

Два шага для ta

Условие. Для T=tactaca$ используйте SA=[7,6,4,1,5,2,3,0] и BWT L=acttaac$. Найдите интервал образца ta обратным поиском.

  1. Алфавит упорядочен $<a<c<t. Частоты дают C[$]=0,C[a]=1,C[c]=4,C[t]=6. Начальный интервал[0,8).
  2. Сначала читаем последнюю букву a. Occ(a,0)=0,Occ(a,8)=3, поэтому интервал становится[1,4).
  3. Добавляем t слева. В L[0:1) нет t, а в L[0:4) их2. Значит получаем[6+0,6+2)=[6,8).
  4. Две строки SA в этом интервале имеют старты 3 и0. Действительно суффиксы taca$ и tactaca$ начинаются с ta; число вхождений равно 2.

Ответ. Интервал[6,8), число вхождений 2, позиции 0 и3.

Проверка. Независимое скользящее сравнение всех окон длины 2 находит старты 0,3. Прямая сортировка суффиксов подтверждает SA и BWT; обе операции rank пересчитаны подсчётом символов префикса.

Где легко ошибиться. Не включайте правую границу r в Occ и не проходите образец слева направо. Полуоткрытый интервал и исключительный префикс должны использоваться согласованно на каждом шаге.

Проверьте понимание

Сколько вхождений ta в tactaca$ даёт найденный FM-интервал?

Вопросы к этой главе

Почему интервал не хранит порядок позиций в исходном тексте?

Он упорядочен по суффиксам, а не по числовым стартам. В примере SA[6:8]=[3,0]; для привычной выдачи координат их можно отдельно отсортировать, но counting этого не требует.

Можно ли ответить на новый образец без изменения индекса?

Да. Индекс зависит только от фиксированного текста, а каждый запрос заново сужает полный интервал. Изменение самого текста потребовало бы обновления или перестроения структуры, что не входит в этот статический поиск.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Johannes Fischer: Lecture8, Backwards Search

    Прочитано обновление интервала назад по образцу и различие counting/locating. Наша формула использует полуоткрытые интервалы и исключительный префикс Occ, согласованный отдельно с1-based источником. Текст tactaca$ и два шага для ta проверены прямыми суффиксами.

Волновое дерево отвечает rank иselect без отдельного индекса для каждого символа

Волновое дерево хранит многосимвольную последовательность через несколько уровней битовых разбиений. Запрос rank спускается по дереву с помощью префиксных подсчётов битов, а select проходит обратный путь. Так операции для всего алфавита сводятся к двум операциям над битовыми последовательностями.

Перед началом: Префиксные количества и полуинтервал; Стабильное разбиение последовательности.

Биты направляют символы, сохраняя их взаимный порядок

Упорядоченный алфавит делят на две части. В корне записывают ноль для символа левой части и единицу для правой. Затем из исходной последовательности стабильно выделяют два подпотока и повторяют процесс рекурсивно, пока лист не соответствует одному символу. Стабильность означает сохранение исходного порядка внутри каждой части.

На каждом уровне хранится не более n битов для последовательности длины n, а высота сбалансированного дерева равна O(log σ). Битовые индексы rank/select требуют отдельной поддержки. При постоянном времени этих базовых операций один запрос к исходному алфавиту занимает O(log σ); простая учебная реализация с явными префиксными массивами может расходовать больше битов, чем компактные теоретические варианты.

Rank преобразует длину префикса при спуске

Определим rank_c(k) как количество c среди первых k символов, то есть в S[0:k]. Для нужного символа выбираем соответствующее ребро с битом b и заменяем k количеством b среди первых k битов текущего узла. Полученное число является длиной нужного подпотока внутри исходного префикса.

Повторяя операцию до листа c, получаем искомое количество. Пустой префикс даёт нуль, полный — общую частоту. Для диапазона [l,r) ответ равен rank_c(r)−rank_c(l). Нельзя использовать исходный k на всех уровнях: после стабильного отбора длина подпотока обычно меньше.

Select восстанавливает исходную позицию снизу вверх

Пусть требуется позиция j-го символа c, где номер вхождения j начинается с единицы, а индекс позиции — с нуля. В листе берём номер j. Если лист пришёл по биту b, находим позицию j-го b в родительском битовом векторе. Для следующего подъёма превращаем её в порядковый номер, прибавляя единицу.

Так продолжаем до корня; последняя нулевая позиция и есть ответ. Соглашения о номерах особенно важны: rank принимает длину полуоткрытого префикса, select — положительный номер вхождения. Проверка rank_c(pos+1)=j и rank_c(pos)=j−1 связывает обе операции и быстро обнаруживает ошибку на единицу.

Два уровня для трёхбуквенной последовательности

Условие. Постройте волновое дерево для S=cbacabbac с разбиением {a,b}|{c}, затем {a}|{b}. Найдите rank_b(8), число b на [2,8) и позицию третьей b.

  1. Корневой битовый вектор равен 100100001. Левый стабильный подпоток равен baabba, его битовый вектор по a|b равен 100110. Правый лист хранит три появления c.
  2. Среди первых восьми корневых битов шесть нулей. Поэтому rank_b(8) переходит в rank₁(6) левого узла, что равно трём.
  3. Для первых двух исходных символов корневая проекция имеет длину один; первый левый бит равен единице. Значит, rank_b(2)=1 и на диапазоне [2,8) находится 3−1=2 буквы b.
  4. Третья единица в левом векторе стоит на нулевой позиции четыре. Это пятый элемент левого подпотока. Пятый ноль корня стоит на позиции шесть исходной строки.
  5. Прямое перечисление позиций b в S даёт 1,5,6. Оно подтверждает rank_b(8)=3, диапазонный ответ два и select_b(3)=6.

Ответ. rank_b(8)=3; на [2,8) две b; третья b находится в нулевой позиции 6.

Проверка. Индексы 1,5,6 дают независимый линейный контроль. Для pos=6 выполняются rank_b(7)=3 и rank_b(6)=2, что проверяет согласование rank и select.

Где легко ошибиться. Не сортируйте подпотоки по буквам после разбиения. Стабильный порядок необходим, чтобы префиксные количества и обратные select-переходы соответствовали исходным позициям.

Проверьте понимание

Чему равен rank_b(8) при указанном полуоткрытом соглашении?

Вопросы к этой главе

Зачем дерево, если можно хранить отдельный битовый вектор каждой буквы?

Отдельные векторы требуют порядка nσ битов до сжатия. Иерархическое разбиение распределяет символы по O(log σ) уровням и совместно обслуживает весь алфавит.

Что возвращает rank_b(8): позицию или количество?

Количество b в первых восьми символах. Позицию конкретного вхождения возвращает select; смешение этих интерфейсов даёт неверные границы даже при правильных битовых данных.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • G. Navarro: Wavelet Trees for All, §2

    Прочитан §2: стабильные подпоследовательности, битовые rank и обратный подъём select. Индексирование источника переведено в явно указанные нулевые позиции и длины префиксов. Девятисимвольный пример и все запросы проверены отдельно; энтропийные варианты хранения не реализуются.

SA-IS: суффиксы сортируются наведением из LMS-позиций

Суффиксный массив можно строить, не сравнивая каждый длинный суффикс со всеми остальными. SA-IS выделяет особые переходы типов суффиксов, уменьшает задачу до них, а затем распространяет найденный порядок на соседние стартовые позиции. Для корректности важны и направление каждого прохода, и край корзины, куда помещается новый индекс.

Перед началом: Лексикографический порядок суффиксов; Стабильная сортировка по первому символу и корзины.

Типы определяются справа налево

Конечная строка над упорядоченным целочисленным алфавитом с единственным минимальным терминатором; индексы начинаются с нуля.

Суффикс позиции i имеет тип S, если он меньше следующего суффикса, и тип L, если больше. Это определяется без сравнения длинных строк: при sᵢ<sᵢ₊₁ ставим S, при большем символе L, а при равенстве наследуем тип справа. Минимальный единственный терминатор в конце получает S. Позиция LMS — начало S-типа сразу после L-типа.

LMS-подстрока идёт от одной LMS-позиции до следующей включительно; терминатор является отдельной последней подстрокой. Одинаковые блоки сравнивают с учётом символов, типов и достижения следующей LMS-границы. Им присваивают одинаковое имя, различным — имена по порядку. Последовательность имён в исходном порядке задаёт сокращённую задачу; при повторениях имён её рекурсивно сортируют.

Два прохода используют противоположные края корзин

Корзина символа содержит все начинающиеся им суффиксы; её размер равен количеству этого символа. Зная точный порядок LMS-суффиксов, расставляем их в хвосты соответствующих корзин, проходя список в обратном порядке. Затем сканируем массив слева направо: для встреченного j>0 предшественника j−1 типа L помещаем в текущую голову его корзины и сдвигаем голову вправо.

После этого головы больше не используются, хвосты восстанавливаются. При проходе справа налево предшественники типа S помещаются в текущие хвосты, которые сдвигаются влево. Ранее размещённые LMS-позиции могут перезаписываться корректно. Направления обеспечивают нужный порядок уже обработанных продолжений; произвольная перестановка проходов или использование головы для обоих типов этого свойства не сохраняет.

Редукция объясняет сложность, но не отменяет предварительный этап

Полный SA-IS сначала наведением сортирует LMS-блоки, даёт им имена, решает сокращённую задачу и только затем выполняет окончательное наведение. Простая расстановка неупорядоченных LMS-позиций не означает, что готов порядок всех LMS-суффиксов. Их число не превосходит половины длины, поскольку соседними такие позиции быть не могут.

Линейные проходы и рекурсия размера не более n/2 дают линейное время при подходящем целочисленном алфавите и линейной подготовке корзин. Предварительное сравнение или сжатие произвольных строковых символов может иметь отдельную стоимость. Ниже все четыре коротких LMS-блока различны, поэтому их порядок можно показать непосредственно, а рекурсия завершается без неоднозначных имён.

Окончательное наведение на abacabad$

Условие. Для строки abacabad$ при $<a<b<c<d постройте типы, LMS-порядок и окончательный суффиксный массив. Позиции нумеруются 0,…,8.

  1. Типы позиций равны S,L,S,L,S,L,S,L,S. LMS-позиции 2,4,6,8 задают блоки aca,aba,ad$,$. Их порядок $<aba<aca<ad$ даёт имена (2,1,3,0) в исходном порядке и LMS-суффиксы (8,4,2,6).
  2. Корзины занимают позиции: $ — 0, a — 1…4, b — 5…6, c — 7, d — 8. Посадка LMS по хвостам даёт [8,пусто,4,2,6,пусто,пусто,пусто,пусто].
  3. Левый проход наводит L-позиции 7,3,1,5. Массив становится [8,пусто,4,2,6,1,5,3,7]. Уже размещённые S-позиции пока не считаем окончательным порядком всех a-суффиксов.
  4. Правый проход по восстановленным хвостам наводит S-предшественники 6,2,4,0 и даёт [8,0,4,2,6,1,5,3,7]. Теперь каждый индекс встречается ровно один раз.

Ответ. Суффиксный массив равен [8,0,4,2,6,1,5,3,7]. Первым после терминатора идёт полный текст с позиции 0, а не первый LMS-блок.

Проверка. Независимое прямое сравнение строк даёт порядок $,abacabad$,abad$,acabad$,ad$,bacabad$,bad$,cabad$,d$. Это проверяет результат отдельно от механики корзин.

Где легко ошибиться. Лексикографический порядок LMS-блоков и LMS-суффиксов совпадает без дальнейшей работы только при различных именах. Повторённые блоки требуют сокращённой задачи.

Проверьте понимание

С какой позиции начинается первый a-суффикс после терминатора в итоговом массиве разобранной строки abacabad$?

Вопросы к этой главе

Зачем явно добавлять уникальный минимальный терминатор?

Он задаёт последний S-суффикс и минимальный LMS-блок, завершает сравнения и не повторяется внутри текста. Его индекс входит в построенный массив; для поиска по исходной строке его потом учитывают отдельно.

Этот массив уже считает разные подстроки?

Нет. Здесь решена задача построения порядка суффиксов. Подсчёт подстрок дополнительно использует LCP соседей и исключение терминатора; это следующий потребитель индекса, а не этап SA-IS.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Кратчайшая уникальная подстрока через соседние LCP

Для поиска короткого уникального идентификатора фрагмента недостаточно сосчитать разные подстроки: нужно исключить каждое повторное вхождение выбранной строки. Суффиксный массив позволяет сделать это локально. Самый длинный повторяющийся префикс данного суффикса определяется максимумом двух соседних LCP. Следующая длина уже уникальна, если она помещается до конца исходного текста.

Перед началом: Суффиксный массив и соседние LCP; Различие числа вхождений и числа разных строк.

Два соседа ограничивают все остальные суффиксы

Один конечный текст без добавленного терминатора; уникальность означает ровно одно вхождение, включая перекрывающиеся.

Пусть суффикс с началом i занимает ранг k. Обозначим через L и R длины общих префиксов с непосредственными левым и правым соседями; на отсутствующей стороне ставим ноль. Любой набор строк с фиксированным префиксом занимает непрерывный интервал лексикографического порядка. Поэтому если этот префикс встречается у другого суффикса слева или справа, он встречается и у ближайшего соседа на той стороне.

Следовательно, h=max(L,R) — максимальная длина префикса, повторяющегося ещё где-нибудь. Длины до h неуникальны. Префикс длины h+1 уникален, поскольку совпадение с ещё одним суффиксом заставило бы одного из соседей иметь больший LCP. Это утверждение относится к отдельному началу i, а не к произвольной подстроке, покрывающей заданную позицию.

Конец текста может запретить единственный кандидат

Кандидат h+1 допустим только при h+1≤n−i. Если весь суффикс встречается как префикс более длинного суффикса, увеличить длину уже нельзя. Для такого начала уникального фрагмента нет. Терминатор не должен искусственно делать его уникальным: добавленный служебный символ не является частью исходного идентификатора.

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

Цена индекса оплачивается повторными запросами

Если SA и LCP уже построены, все длины кандидатов получаются одним линейным проходом. Само построение индекса имеет свою стоимость и память, а изменение текста обычно требует обновления структуры. Для одного короткого текста простой перебор может быть удобнее, но при многих анализах фиксированного корпуса массивы используются повторно.

Уникальность здесь буквальная и локальна выбранному тексту. Она не обещает уникальности во внешнем корпусе и не учитывает приближённые совпадения, регистр или нормализацию символов, если их не задали заранее. Перекрывающиеся вхождения считаются отдельными: два равных фрагмента с разными началами уже нарушают условие.

Все буквы повторяются, но трёхсимвольные метки уже уникальны

Условие. Найдите глобально кратчайшую уникальную подстроку текста aabbabbaa. При равной длине выберите самое левое начало. Служебный символ конца не добавляется.

  1. Суффиксный массив равен [8,7,0,4,1,6,3,5,2]. Для начала 0 соседние совпадения имеют длины 2 и 1, поэтому кандидат имеет длину 3 и равен aab.
  2. Для начал 6 и 3 максимальные соседние LCP также равны 2. Они дают уникальные baa и bab длины 3. Начала 1,2,4,5 требуют соответственно длины 5,4,5,4.
  3. Суффикс из 7 равен aa и целиком встречается с начала 0; его требуемая длина 3 выходит за конец. Суффикс из 8 равен a и также не имеет допустимого уникального продолжения.
  4. Минимальная допустимая длина равна 3. Среди трёх подходящих начал 0,3,6 выбираем 0, получая aab. Каждая односимвольная и двухсимвольная подстрока текста имеет повторное вхождение.

Ответ. Ответ при выбранном правиле — aab с начала 0, длина 3. Другие минимальные уникальные строки — bab и baa.

Проверка. Независимый подсчёт всех срезов даёт частоты aa=2, ab=2, bb=2, ba=2. Все буквы также повторяются; aab встречается ровно один раз. Это непосредственно исключает длины 1 и 2 без использования SA.

Где легко ошибиться. Не принимайте h+1 за существующую длину без проверки конца суффикса. Уникальность за счёт добавленного терминатора не даёт допустимой подстроки исходного текста.

Проверьте понимание

Какова длина глобально кратчайшей уникальной подстроки aabbabbaa в разобранном примере?

Вопросы к этой главе

Почему для подсчёта разных подстрок хватало левого соседа, а здесь нужны оба?

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

Решает ли формула задачу о кратчайшем уникальном фрагменте, покрывающем заданную позицию?

Непосредственно нет. Она отвечает для фиксированного начала. Покрывающий фрагмент может начинаться раньше заданной позиции; для таких запросов требуется дополнительный выбор среди начал.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться