Суфиксен масив

Понякога е необходимо даден текст бързо да отговори на многобройни заявки - има ли даден подниз тук или не и ако има, колко често и на какви места се среща? Когато има наистина много такива заявки, важно е заявките да бъдат изпълнени бързо. За да направите това, обикновено се извършва известна повторна обработка на текста, за да се създаде някаква структура от данни, която улеснява търсенето в текста. Суфиксните масиви са една от възможните структури.

Малко теория

Нека са дадени T[1 .. m] - началният "текст" с дължина m и низът P[1 .. n] - същият подниз, който търсим. Ще кажем, че ω е префикс или началото на низ x, ако има низ y такъв, че x = ωy (конкатенация). Ще кажем, че ω е суфикс на низ x, ако съществува низ y такъв, че x = yω. Обърнете внимание, че както ω, така и y могат да бъдат празни низове. Например за низа "abcdeab" префиксите биха били: "", "a", "ab", "abc", ... , "abcdeab". И наставките ще бъдат: "", "b", "ab", "eab", ..., "abcdeab". Всеки суфикс е уникално определен с число - позицията, от която започва в низа. В низа "abcdeab" суфиксът "deab" започва от 4-та позиция, а суфиксът "bcdeab" от 2-ра позиция. За удобство текстовият суфикс T, започващ от s-та позиция, ще бъде означен като T[s .. m]. Така. Нека запишем всички суфикси на изходния текст, започвайки от 1-ва позиция, завършвайки с m-та. Нека T = "суфикс". След това сортираме суфиксите в таблицата в лексикографски ред. След това таблиците трябва да изглеждат така:

Сега можете да запишете получените стойности на s в масив. И получаваме масива Pos[1 .. m]. В този пример масивът Pos ще изглежда така:

Поз = [3, 4, 5, 1, 2, 6].

Защо имаме нужда от това? Както бе споменато по-горе, суфиксът е уникално определен от число - позиция, следователно, тъй като имаме нуждалексикографски сортирани суфикси, е удобно резултатът от сортирането да се съхранява в числова (като по-икономична) форма. Може би всичко е готово за търсене на подниза P. Двоичното търсене ще ни помогне с това.

Двоично търсене

Същността на двоичното търсене е проста. Нека ни бъде даден масив, сортиран във възходящ ред, например от числа. И ние търсим числото x. И нека вземем число от средата на масива. Това ще бъде y. Очевидно, ако x y, тогава е от дясната страна на масива. И накрая, ако x == y, тогава търсенето е приключило. На всяка стъпка зоната на търсене се намалява наполовина. Ако първоначално имаме масив от N = 2 ^ 20 елемента, то в 20 стъпки определено ще намерим желания елемент или две числа, между които той трябва да стои.

Двоичното търсене може да се приложи към лексикографски сортирани низове:

Това е донякъде опростен псевдокод, но разбира смисъла. Нека го оптимизираме. Първо, защо да запаметявам всяко намерено средно място? Ясно е, че намерените места са подредени.

Намерете imin и imax така, че T[Pos[imin] .. m] да е най-левият суфикс в сортирания масив, чийто префикс е P, а T[Pos[imax] .. m] да е най-десният суфикс, чийто префикс е P.

Съвсем очевидно е, че тъй като масивът Pos дефинира лексикографски сортирани суфикси, тогава за всеки imin ≤ i ≤ imax низът P ще бъде префиксът на суфикса T[Pos[i] .. m]. Следователно отговорът на въпроса на проблема (всички срещания на P в T) ще бъде част от масива Pos[imin .. imax].

Горният код ще се изпълни за O(n log m) време (припомнете си, че n е дължината на P). А именно, броят на рекурсивните извиквания е ограничен до log m и при всяка итерация ще се проверява за O(n) време дали P е префикс на T[Pos[middle] .. m] или не. Времето O(n log m) нараства линейно с дължината на необходимия низ P. Понякога е прекаленоскъпо удоволствие. Нека да оптимизираме допълнително.

mlr оптимизация

Какво не е много добро в горния код? Фактът, че P се сравнява всеки път в неговата цялост, докато в последните итерации големият префикс P може да бъде префиксът T[Pos[среден] .. m]. За да открие P T[Pos[средна] .. m], алгоритъмът ще премине през първите еднакви букви P и T[Pos[средна] .. m], докато намери място, където буквите се различават. Той ще работи с тези идентични букви при всяка следваща итерация.

Нека въведем нова функция lcp(str1, str2), която за два низа ще даде дължината на общия им префикс. Ако в самото начало на двоичното търсене направим следното: mlr = min(lcp(P, T[Pos[left] .. m]), lcp(P, T[Pos[right] .. m]), тогава по-късно първите mlr знаци на суфиксите в диапазона от Pos[left] до Pos[right] могат да бъдат "заковани" и могат да бъдат проверени само останалите опашки на низове. Това дава оценка на заявката време на работа като O(n + log m), което е малко по-добро.

Ruby Code

В езика Ruby всички тези идеи се изпълняват бързо. Не само ще напишем класа SuffixArray, но и ще се докоснем до класиката - ще тестваме работата по романа на Шолохов "Тихият Дон", за добро, страхотна е.

Всичко. Можеш да отидеш за кафе. Резултатът от програмата ще бъде:

Така доказахме от опит, че рубинът е много древен език, дори Шолохов го спомена поне 120 пъти. Първото число в горния отчет е времето, през което функцията е работила в потребителското пространство. Второто е колко време е работило ядрото на системата. Третият е аритметичният сбор от първите два. Последното нещо е колко тиктака на стенния часовник, тоест можете да зададете колко процесорът е бил разсеян от задачата да изпълни нашата програма към други задачи. Както можете да видите, заявките се изпълняват много бързо, но предварителната обработка отнема много време (тестработи на Celeron 2,40 GHz, 480 MB RAM). Една минута и половина за такава машина е неефективна. Трябва да подобрим резултатите.

Наистина, сортирането с вградения метод sort_by е, разбира се, добро, но само ако знаем малко за елементите, които се сортират. А това не е така. Ние сортираме суфиксите, всичките им дължини са различни и варират от 1 до max_search_size. Същността на оптимизираното сортиране е следната:

Сортирайте наставките по първата буква. Това може да се направи в O(m*Z), където Z е броят на буквите в азбуката.
Суфиксите с една и съща първа буква ще бъдат в една и съща кошница. Общо Z кошници. Наставката T[m .. m] трябва незабавно да бъде поставена в началото на вашата кошница.
Нека да преминем през масива Pos. За Pos[i] е вярно, че Pos[i] - 1 - суфиксът ще бъде първият в своята кофа. Поставяме го на мястото най-близо до началото на кошницата и отбелязваме това място като заето. Получаваме набор от кошници със суфикси, сортирани по първите две букви.
След това - преминете през Pos[i]. Вече за Pos[i] - 2 - суфикс е вярно, че той ще бъде на първо място в кошницата си. Поставяме го на мястото, което е най-близо до началото на кошницата, маркираме мястото като заето.
Получаваме набор от кошници със суфикси, сортирани по първите 4 знака.
и т.н. Целият процес на сортиране отнема O(m log2 m). И това вече е приемливо.

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