Суффиксные деревья и массивы: Продвинутый поиск подстрок
Когда вы нажимаете Ctrl+F в текстовом редакторе, чтобы найти слово в документе, алгоритм последовательно сканирует текст, сравнивая символы. Это работает быстро для коротких файлов, но если вам нужно найти подстроку в геноме человека размером 3 гигабайта или найти плагиат в миллионе книг? Обычные методы потерпят крах. В дискретной математике и алгоритмике эта проблема решается с помощью мощнейших индексных структур: суффиксных деревьев и суффиксных массивов.
Суффиксное дерево (Suffix Tree) — это сжатое префиксное дерево (Trie), содержащее все возможные суффиксы заданного текста. Представьте слово "БАБАН". Его суффиксы: "БАБАН", "АБАН", "БАН", "АН", "Н". Если построить из этих строк дерево, то любая подстрока исходного текста гарантированно будет являться префиксом одного из этих суффиксов, а значит, ее можно будет найти, просто спускаясь от корня дерева вниз.
Главное чудо суффиксного дерева заключается в его математической сложности. Построить такое дерево наивным способом требует времени O(N^2), что неприемлемо для длинных текстов. Однако в 1995 году Эско Укконен разработал невероятный онлайн-алгоритм (Алгоритм Укконена), который строит суффиксное дерево за строго линейное время O(N). Это значит, что проиндексировать Войну и Мир можно за доли секунды за один проход по тексту.
После того как дерево построено, поиск любой подстроки длины M занимает время O(M), и это время абсолютно не зависит от длины самого текста! Дерево также легко решает сложнейшие комбинаторные задачи на строках, например, поиск самой длинной общей подстроки у двух разных файлов (базовый алгоритм для поиска плагиата или сравнения двух версий исходного кода).
К сожалению, суффиксные деревья требуют огромного объема оперативной памяти (до 20 байт на каждый символ текста). Чтобы решить эту инженерную проблему, математики придумали Суффиксный массив (Suffix Array) — это просто лексикографически (по алфавиту) отсортированный массив указателей на все суффиксы строки. Он занимает в 4-5 раз меньше памяти. В паре с дополнительной структурой, называемой LCP-массивом (Longest Common Prefix), суффиксный массив позволяет решать все те же задачи, что и дерево, с той же невероятной скоростью, и именно он используется сегодня в ядре большинства систем полнотекстового поиска и баз данных биоинформатики.
