Низ суфикса

Suffix array
Тип	Array
Смислили	Manber & Myers 1990
Time complexity in big O notation
Просек	Најгори случај

У рачунарској науци, низ суфикса је сортирани низ свих суфикса стринга. То је структура података која се користи, између осталог, у индексима комплетног текста, алгоритми за компресију података унутар поља биоинформатике.^[1]

Низови суфикса су представили Manber & Myers 1990 као једноставну, просторно ефикасну алтернативу суфикс дрвима. Независно су откривене од стране Gaston Gonnet у 1987 под именом PAT низ.^[2]

Дефиниција[уреди | уреди извор]

Нека је $S=S[1]S[2]...S[n]$ стринг и нека је $S[i,j]$ означи подстринг од $S$ које је од $i$ до $j$ .

Низ суфикса $A$ од $S$ је сада дефинисан као низ целих бројева који дају стартне позиције суфиксима од $S$ у лексикографском реду. Ово значи, да улаз $A[i]$ садржи стартну позицију од $i$ -тог најмањег суфикса у $S$ и тако за свако $1<i\leq n$ : $S[A[i-1],n]<S[A[i],n]$ .

Пример[уреди | уреди извор]

Узмите у обзир текст $S$ =banana$ да је индексиран:

Текст се завршава специјалним стражарским знаком $ који је посебан и лексикографски мањи од било ког другог карактера. Текст има следеће суфиксе:

Suffix	i
banana$	1
anana$	2
nana$	3
ana$	4
na$	5
a$	6
$	7

Суфикси могу бити поређани у растућем поретку:

Suffix	i
$	7
a$	6
ana$	4
anana$	2
banana$	1
na$	5
nana$	3

Низ суфикса $A$ садржи стартне позиције ових сортираних суфикса: Низ суфикса са суфиксаима исписаним вертикално испод ради јасноће: На пример, $A[3]$ садржи вредност 4, и премда реферира на суфикс који почиње на позицији 4 унутар $S$ , што је суфикс ana$.

Повезаност са суфикс дрвима[уреди | уреди извор]

Низви суфикса су уско повезани са суфикс дрвима:

Низови суфикса могу да се конструишу извођењем прелаза прво у дубину на дрвету суфикса. Низ суфикса одговара ознакама листова датим у реду у коме су посећене током проласка, ако су ивице посећене у лексикографском реду њиховог првог карактера.
Суфикс дрво може да се конструише у линеарном времену коришћењем комбинације суфикса и ЛЦП низа. За опис алгоритма, погледајте одговарајући део у LCP array чланку.

Показано је да сваки алгоритам суфикс дрвета може систематски да се замени са алгоритмом који користи суфикс низове који има додатне информације (као ЛЦП низ) и решава исти проблем у истој временској комплексности.^[3] Предности низова суфикса над дрвима суфикса су побољшани просторни захтеви, једноставнији алгоритми у линеарном времену (тј., у поређењу са Уконеновим алгоритмом) и побољшана локалност кеша.^[1]

Просторна ефикасност[уреди | уреди извор]

Низове суфикса су увели Manber & Myers 1990 да би побољшали захтеве простора суфикс дрвећа: Низови суфикса чувају $n$ целих бројева. Претпостављајући да цео број захтева 4 бајта, низ суфикса захтева $4n$ бајтова укупно. Ово је драстично мање од $20n$ бајтова који су потребни за имлементацију прецизног дрвета суфикса.^[4]

Међутим, у одређеним приименама, просторни захтеви низова суфикса могу да буду превисоки. Анализирано у битовима, низ суфикса захтева ${\mathcal {O}}(n\log n)$ простора, а оригинални текст из алфабета величине $\sigma$ захтева само ${\mathcal {O}}(n\log \sigma )$ битова. За људски геном са $\sigma =4$ and $n=3.4\times 10^{9}$ низ суфикса би према томе окупирао 16 пута више меморије него сам геном.

Оваква одступања су покренула тренд према компресованим низовима суфикса и BWT-заснованим целотекстуалним индексима као што је FM-index. Ове структуре података захтевају само простор унутар величине текста или чак и мање.

Конструкциони алгоритми[уреди | уреди извор]

Суфикс дрво може да се направи у ${\mathcal {O}}(n)$ и може бити конвертован у низ суфикса прелажењем дрвета прво у дубину такође у ${\mathcal {O}}(n)$ , тако да постоје алгоритми који могу да изграде низ суфикса у ${\mathcal {O}}(n)$ .

Наивни приступ за изградњу низа суфикса је коришћењем алгоритма за сортирање који је заснован на поређењу. Ови алгоритми захтевају ${\mathcal {O}}(n\log n)$ суфикс поређења, али поређење суфикса ради у ${\mathcal {O}}(n)$ времену, тако да је укупно време овог приступа ${\mathcal {O}}(n^{2}\log n)$ .

Напреднији алгоритми узимају у корист чињеницу да суфикси који требају да се сортирају нису арбитрарни стрингови него су повезани међуобно. Ови алгоритми теже да достигну следеће циљеве:^[5]

минималну асимптотску комплексност $\Theta (n)$
лакоћу у простору, што значи мало или без радне меморије поред текста и низа суфикса
брзину у пракси

Један од првих алгоритама који су постигли све циљеве је SA-IS алгоритам који су направили Nong, Zhang & Chan 2009. Алгоритам је такође једноставан (< 100 LOC) и може бити надограђен да истовремено конструише ЛЦП низ.^[6] SA-IS алгоритам је један од најбржих познатих алгоритама за конструкцију низа суфикса. Пажљива имплементација implementation by Yuta Mori Архивирано на сајту Wayback Machine (26. јул 2014) превазилази већину других линеарних или супер-линеарних приступа конструкцији.

Поред временских и просторних захтева, алгоритми за конструкцију низова суфикса такође варирају у зависности од алфабета који подржавају: константни алфабети су алфабети чија је величина везана за константу, целобројни алфабети где су карактери цели бројеви у распону зависном од $n$ и генерални алфабети где су само поређења карактера дозвољена.[6]

Већина алгоритама за конструкцију низова суфикса је засновано на следећим приступима:^[5]

Алгоритми дуплирања префикса су засновани на стратегији Karp, Miller & Rosenberg 1972. Идеја је да се нађу префикси који поштују лексикографско слагање суфикса. Претпостављена дужина префикса се дуплира у свакој итерацији алгоритма док префикс не постане посебан и донесе ранг повезаног суфикса.
Рекурзивни алгоритми прате приступ алгоритама конструкције суфикс дрвета које је направио Farach 1997 да би рекурзивно сортирали подсет суфикса. Подсет се онда користи да закључи низ суфикса за преостале суфиксе. Оба од ових низова суфикса се спајају да би израчунали коначни низ суфикса.
Алгоритми за индуковано копирање су слични рекурзивним алгоритмима у смислу да користе већ сортиран подсет да индукује брзо сортирање преосталих суфикса. Разлика је у томе што ови алгоритми служе итерацију над рекурзијом да би сортирали означени подсет суфикса. Анкета ове разнолике групе алгоритама је спојена од стране Puglisi, Smyth & Turpin 2007.

Познати рекурзивни алгоритам за целобројне алфабете је DC3 / skew алгоритам који су направили Kärkkäinen & Sanders (2003). Ради у линеарном времену и успешно је коришћен као базична паралела^[7] и екстерна меморија^[8] алгоритама за конструкцију низова суфикса.

Скорашњи рад Salson et al. (2009) предлаже алгоритам за обнављање низа суфикса текста који је едитован уместо да се ствара нови низ суфикса од почетка. Чак и у теоретској временској комплексности је брзина ${\mathcal {O}}(n\log n)$ , изгледа да ради добро у пракси: експериментални резултати аутора су показали да је њихова имплементација динамичких низова суфикса генерално ефикаснија него поновно прављење убацивања неколико слова у оригинални текст.

Примене[уреди | уреди извор]

Низ суфикса стринга може бити коришћен као индекс да се брзо лоцира свака појава обрасца подстринга $P$ унутар стринга $S$ . Проналажење сваке појаве обрасца је еквивалентно тражењу сваког суфикса који почиње са подстрингом. Захваљујући лексикографском распоређивању, ови суфикси се групишу заједно у низ суфикса и могу да се ефиксано пронађу уз два бинарна претраживања. Прво претраживање лоцира почетну позицију интервала, а друга одређује позицију краја:

    def search(P):
        l = 0; r = n
        while l < r:
            mid = (l+r) / 2
            if P > suffixAt(A[mid]):
                l = mid + 1
            else:
                r = mid
        s = l; r = n
        while l < r:
            mid = (l+r) / 2
            if P < suffixAt(A[mid]):
                r = mid
            else:
                l = mid + 1
        return (s, r)

Тражење обрасца подстринга $P$ дужине $m$ у стрингу $S$ дужине $n$ захтева ${\mathcal {O}}(m\log n)$ времена, уз то да једна компарација суфикса треба да упореди $m$ карактера. Manber & Myers (1990) описују како граница може да се побољша на ${\mathcal {O}}(m+\log n)$ времена коришћењем LCP информација. Идеја је да поређење образаца не мора да поново упоређује одређене карактере, када се већ зна су део најдужег честог префикса обрасца и тренутног интервала претраживања. Abouelhoda, Kurtz & Ohlebusch (2004) су побољшали границу још даље и достигли време претраживања ${\mathcal {O}}(m)$ познатог из суфикс дрвећа.

Алгоритми за сортирање суфикса могу да се користе за израчунавање Burrows–Wheeler transform (BWT). BWT захтева сортирање свих цикличних пермутација стринга. Ако се овај стринг завршава посебним карактером који је лексикографски мањи од свих других (тј., $), онда ред сортиране ротиране BWT матрице кореспондира реду суфикса у низу суфикса. BWT премда може да буде израчуната у линеарном времену прво конструишући низ суфикса текста, а затим дедуковањем BWT стринга: $BWT[i]=S[A[i]-1]$ .

Низови суфикса могу такође да се користе за тражење подстрингова у Example-Based Machine Translation, тражећи много мање простора него пуна phrase table која се користи у Statistical machine translation.

Много додатних примена низова суфикса захтева LCP array. Неке од ових су описани у application section.

Референце[уреди | уреди извор]

Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). „Replacing suffix trees with enhanced suffix arrays”. Journal of Discrete Algorithms. 2: 53—86. doi:10.1016/S1570-8667(03)00065-0.
Manber, Udi; Myers, Gene (1993). „Suffix Arrays: A New Method for On-Line String Searches”. SIAM Journal on Computing. 22 (5): 935—948. doi:10.1137/0222058.
Manber, Udi; Myers, Gene (1993). „Suffix Arrays: A New Method for On-Line String Searches”. SIAM Journal on Computing. 22 (5): 935—948. S2CID 5074629. doi:10.1137/0222058.
Kurtz, Stefan (1999). „Reducing the space requirement of suffix trees”. Software: Practice and Experience. 29 (13): 1149—1171. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O.
Algorithms in Bioinformatics. Lecture Notes in Computer Science. 2452. 2002. стр. 449. ISBN 978-3-540-44211-0. S2CID 5138708. doi:10.1007/3-540-45784-4.
Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). „A taxonomy of suffix array construction algorithms”. ACM Computing Surveys. 39 (2): 4. S2CID 2653529. doi:10.1145/1242471.1242472.
Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). „Linear Suffix Array Construction by Almost Pure Induced-Sorting”. 2009 Data Compression Conference. стр. 193—202. ISBN 978-0-7695-3592-0. S2CID 14123069. doi:10.1109/DCC.2009.42.
Fischer, Johannes . Inducing the LCP-Array. Algorithms and Data Structures. Lecture Notes in Computer Science. . doi:10.1007/978-3-642-22300-6 32 Проверите вредност параметра |doi= (помоћ). Недостаје или је празан параметар |title= (помоћ). . 2011. стр. 374. ISBN 978-3-642-22299-3. Недостаје или је празан параметар |title= (помоћ)
Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). „Dynamic extended suffix arrays”. Journal of Discrete Algorithms. 8 (2): 241—257. doi:10.1016/j.jda.2009.02.007.
Burkhardt, Stefan; Kärkkäinen, Juha . Fast Lightweight Suffix Array Construction and Checking. Combinatorial Pattern Matching. Lecture Notes in Computer Science. . doi:10.1007/3-540-44888-8 5 Проверите вредност параметра |doi= (помоћ). Недостаје или је празан параметар |title= (помоћ). . 2003. стр. 55. ISBN 978-3-540-40311-1. Недостаје или је празан параметар |title= (помоћ)
Farach, M. (1997). „Optimal suffix tree construction with large alphabets”. Proceedings 38th Annual Symposium on Foundations of Computer Science. стр. 137—143. ISBN 0-8186-8197-7. S2CID 123355749. doi:10.1109/SFCS.1997.646102.
Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). „Rapid identification of repeated patterns in strings, trees and arrays”. Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72. стр. 125—136. S2CID 16652988. doi:10.1145/800152.804905.
Kärkkäinen, Juha; Sanders, Peter . Simple Linear Work Suffix Array Construction. Automata, Languages and Programming. Lecture Notes in Computer Science. . doi:10.1007/3-540-45061-0 73 Проверите вредност параметра |doi= (помоћ). Недостаје или је празан параметар |title= (помоћ). . 2003. стр. 943. ISBN 978-3-540-40493-4. Недостаје или је празан параметар |title= (помоћ)
Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). „Better external memory suffix array construction”. ACM Journal of Experimental Algorithmics. 12: 1—24. S2CID 12296500. doi:10.1145/1227161.1402296.
Kulla, Fabian; Sanders, Peter (2007). „Scalable parallel suffix array construction”. Parallel Computing. 33 (9): 605—612. doi:10.1016/j.parco.2007.06.004.

Спољашње везе[уреди | уреди извор]

[FOOTNOTEAbouelhodaKurtzOhlebusch2002-1] а ^б Abouelhoda, Kurtz & Ohlebusch 2002.

[FOOTNOTEGonnetBaeza-YatesSnider1992-2] Gonnet, Baeza-Yates & Snider 1992.

[FOOTNOTEAbouelhodaKurtzOhlebusch2004-3] Abouelhoda, Kurtz & Ohlebusch 2004.

[FOOTNOTEKurtz1999-4] Kurtz 1999.

[FOOTNOTEPuglisiSmythTurpin2007-5] а ^б Puglisi, Smyth & Turpin 2007.

[FOOTNOTEFischer2011-6] Fischer 2011.

[FOOTNOTEKullaSanders2007-7] Kulla & Sanders 2007.

[FOOTNOTEDementievKärkkäinenMehnertSanders2008-8] Dementiev et al. 2008.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]