Суфиксни низ — разлика између измена

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 9. јануар 2014. у 00:58

У информатици, суфиксни низ је сортирани низ свих суфикса ниске. То је једноставна, али моћна структура података која се користи, између осталог, у тексту пуном индекса, при компресији података и алгоритмима из области биоинформатике.^[1] Суфиксни низови су уведени од стране Манберa и Мајерса (1990) као једноставна и по простору ефикасна алтернатива суфиксних стабала. Она су независно откривена од стране Гонет, Баеза-Иатес, Снајдер (1992) под именом ПАТ низ.

Дефиниција

Нека је $S=s_{1},s_{2},...,s_{n}$ ниска и нека $S[i,j]$ означава подниску од $S$ у распону од $i$ до $j$ .

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

Пример

Ниску $S=banana\$$ ћемо индексирати као:

i	1	2	3	4	5	6	7
S[i]	b	a	n	a	n	a	$

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

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$ садржи стартне позиције ових сортираних суфикса:

i	1	2	3	4	5	6	7
A[i]	7	6	4	2	1	5	3

Комплетан низ са суфиксима:

1	$	a	a	a	b	n	n
2		$	n	n	a	a	a
3			a	a	n	$	n
4			$	n	a		a
5				a	n		$
6				$	a
7					$

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

Пребацивање у суфиксна стабла

Суфиксни низови су тесно повезани са суфиксним стаблима:

Суфиксни низови могу бити конструисани проласком по дубини DFS кроз суфиксно стабло. Суфиксни низ одговара обележјима листова који се добију у редоследу којим су они посећени током пролаза, ако су рубови посећени у лексикографским редоследу њиховог првог карактера.
Суфиксно стабло може бити изграђено у линеарном времену коришћењем комбинације суфикса и LCP низа.

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

Просторна ефикасност

Суфиксни низови су уведенi од стране Манбера и Мајерса (1990) у циљу побољшања просторних захтева суфиксних стабала: Суфиксни низови смештају $n$ целих бројева. Под претпоставком да цео број захтева 4 бајта, суфиксни низ захтева $4n$ бајтова укупно. То је знатно мање од $20n$ бајтова који се захтевају пажљивом имплементацијом суфиксног стабла. ^[3] Међутим, у појединим апликацијама, просторни захтеви суфиксних низова и даље могу бити превисоки. Анализирано у битовима, суфиксни низ захтева ${\mathcal {O}}(n\log n)$ простора, док оригинални текст преко aзбуке величине $\sigma$ захтева само ${\mathcal {O}}(n\log \sigma )$ битова. За људски геном са $\sigma =4$ и $n=3.4\times 10^{9}$ суфиксни низ би стога заузимао око 16 пута више меморије него сам геном.

Алгоритми за конструкцију

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

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

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

Један од првих алгоритама за постизање свих циљева је SA-IS алгоритам аутора Нонг, Жанг, Цан (2009). Алгоритам је такође прилично једноставан (< 100 линија кода) и може се повећати да истовремено изгради и LCP низ. ^[5] SA-IS алгоритам је један од најбржих познатих алгоритама за изградњу суфиксног низа. Пажљива имплементација од Јута Мори надмашује већину других линеарних или супер-линеарних приступа изградње.

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

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

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

Познат рекурзивни алгоритам за целобројне азбуке је DC3 / изобличење алгоритам Kärkkäinen & Sanders (2003). Он ради у линеарном времену и успешно се користи као основа за паралелне и алгоритме за изградњу суфиксног низа са екстерном меморијом.

Најновији рад 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)$ као што је познато из суфиксних стабала.

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

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

Белешке

^ ^а ^б Abouelhoda, Kurtz & Ohlebusch 2002.
^ Abouelhoda, Kurtz & Ohlebusch 2004.
^ Kurtz 1999.
^ ^а ^б Puglisi, Smyth & Turpin 2007.
^ Fischer 2011.
^ Burkhardt & Kärkkäinen 2003.

Референце

Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). „Replacing suffix trees with enhanced suffix arrays”. Journal of Discrete Algorithms. 2: 53. doi:10.1016/S1570-8667(03)00065-0.
Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. стр. 319—327.
Manber, Udi; Myers, Gene (1993). „Suffix arrays: a new method for on-line string searches”. SIAM Journal on Computing. 22: 935—948. doi:10.1137/0222058.
Gonnet, G.H; Baeza-Yates, R.A; Snider, T (1992). „New indices for text: PAT trees and PAT arrays”. Information retrieval: data structures and algorithms.
Kurtz, S (1999). „Reducing the space requirement of suffix trees”. Software-Practice and Experience. 29 (13): 1149. doi:10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O.
Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002). „Algorithms in Bioinformatics”. Lecture Notes in Computer Science. 2452: 449. ISBN 978-3-540-44211-0. doi:10.1007/3-540-45784-4_35. |chapter= игнорисан (помоћ)
Puglisi, Simon J.; Smyth, W. F.; Turpin, Andrew H. (2007). „A taxonomy of suffix array construction algorithms”. ACM Computing Surveys. 39 (2): 4. doi:10.1145/1242471.1242472.
Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). „2009 Data Compression Conference”: 193. ISBN 978-0-7695-3592-0. doi:10.1109/DCC.2009.42. |chapter= игнорисан (помоћ)
Fischer, Johannes (2011). „Algorithms and Data Structures”. Lecture Notes in Computer Science. 6844: 374. ISBN 978-3-642-22299-3. doi:10.1007/978-3-642-22300-6_32. |chapter= игнорисан (помоћ)
Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). „Dynamic extended suffix arrays”. Journal of Discrete Algorithms. 8 (2): 241. doi:10.1016/j.jda.2009.02.007.
Burkhardt, Stefan; Kärkkäinen, Juha (2003). „Combinatorial Pattern Matching”. Lecture Notes in Computer Science. 2676: 55. ISBN 978-3-540-40311-1. doi:10.1007/3-540-44888-8_5. |chapter= игнорисан (помоћ)
Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972). „Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72”: 125. doi:10.1145/800152.804905. |chapter= игнорисан (помоћ)
Farach, M. (1997). „Proceedings 38th Annual Symposium on Foundations of Computer Science”: 137. ISBN 0-8186-8197-7. doi:10.1109/SFCS.1997.646102. |chapter= игнорисан (помоћ)
Kärkkäinen, Juha; Sanders, Peter (2003). „Automata, Languages and Programming”. Lecture Notes in Computer Science. 2719: 943. ISBN 978-3-540-40493-4. doi:10.1007/3-540-45061-0_73. |chapter= игнорисан (помоћ)
Dementiev, Roman; Kärkkäinen, Juha; Mehnert, Jens; Sanders, Peter (2008). „Better external memory suffix array construction”. Journal of Experimental Algorithmics. 12: 1. doi:10.1145/1227161.1402296.
Kulla, Fabian; Sanders, Peter (2007). „Scalable parallel suffix array construction”. Parallel Computing. 33 (9): 605. doi:10.1016/j.parco.2007.06.004.

Спољашњи линкови

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

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

[FOOTNOTEKurtz1999-3] Kurtz 1999.

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

[FOOTNOTEFischer2011-5] Fischer 2011.

[FOOTNOTEBurkhardtKärkkäinen2003-6] Burkhardt & Kärkkäinen 2003.

[1]

[2]

[3]

[4]

[5]

[6]