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

Дефиниција 
Нека је  ниска и нека  означава подниску од  у распону од  до .

Суфиксни низ  од  је сада дефинисан да буде низ целих бројева који пружају почетне позиције наставака од  у лексикографском поретку. То значи да, унос  садржи почетну позицију -тог најмањег суфикса у  и тако за све : .

Пример 

Ниску  ћемо индексирати као:

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

Ове суфиксе сортирамо:

Суфиксни низ  садржи стартне позиције ових сортираних суфикса:

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

Тако на пример,  садржи вредност , и стога односи се на суфикс који почиње на позицији  у , што је суфикс .

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

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

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

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

Суфиксни низови су уведенi од стране Манбера и Мајерса (1990) у циљу побољшања просторних захтева суфиксних стабала: Суфиксни низови смештају  целих бројева. Под претпоставком да цео број захтева 4 бајта, суфиксни низ захтева  бајтова укупно. То је знатно мање од  бајтова који се захтевају пажљивом имплементацијом суфиксног стабла. 
Међутим, у појединим апликацијама, просторни захтеви суфиксних низова и даље могу бити превисоки. Анализирано у битовима, суфиксни низ захтева  простора, док оригинални текст преко азбуке величине  захтева само  битова.
За људски геном са  и  суфиксни низ би стога заузимао око 16 пута више меморије него сам геном.

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

Наиван приступ за изградњу суфиксног низа је да се користи неки од алгоритама сортирања заснованих на поређењу. Ови алгоритми захтевају  поређења суфикса, али поређење суфикса ради у  времену, тако да је укупно време извршавања путем овог приступа је .

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

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

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

Већина алгоритама за изградњу суфиксног низа су засновани на једном од следећих приступа:
 Алгоритми са дуплирањем префикса су засновани на стратегији . Идеја је да се пронађу префикси који поштују лексикографски редослед суфикса. Процењује се дужина дуплираног префикса у свакој итерацији алгоритма док је префикс јединствен и пружа ранг придруженог суфикса.
 Рекурзивни алгоритми прате приступ алгоритама за изградњу суфиксних стабала по  за рекурзивно сортирање подскупа суфикса. Овај подскуп се онда користи за закључивање суфиксног низа преосталих суфикса. Оба од ових суфиксних низова се онда спајају и чине коначни суфиксни низ.
 Алгоритми за индуковано копирање су слични рекурзивним алгоритмима у смислу да они користе већ сортирани подскуп да подстакну брзо сортирање преосталих суфикса. Разлика је у томе што ови алгоритми фаворизују итерацију изнад рекурзије за сортирање изабраних подскупова суфикса. Истраживање ових разноликих група алгоритама је објављено од стране .

Познат рекурзивни алгоритам за целобројне азбуке је DC3 / изобличење алгоритам . Он ради у линеарном времену и успешно се користи као основа за паралелне и алгоритме за изградњу суфиксног низа са екстерном меморијом.

Најновији рад  предлаже алгоритам за ажурирање суфиксног низа текста који је измењен уместо поновне изградње новог суфиксног низа од нуле. Чак и ако је теоретски у најгорем случају временска комплексност , чини се да се добро показују у пракси: експериментални резултати аутора показали су да је њихова имплементација динамичких суфиксних низова генерално ефикаснија од поновне изградње када се убацује разуман број слова у оригинални текст.

Апликације 

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

    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)
		
Проналажење подниске обрасца  дужине  у нисци  дужине  узима  времена, с обзиром да за једно поређење суфикса треба да упоредите  знакова.  описују како се ова граница може побољшати до  времена користећи информације из LCP низа. Идеја је да поређење обрасца не мора поново да упореди одређене знакове, када је већ познато да су део најдужег заједничког префикса за узорак и тренутни интервал претраге.  су побољшали границу још даље и постигли време потраге за  као што је познато из суфиксних стабала.

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

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

Референце

Литература

Спољашње везе 
 Suffix Array in Java
 Suffix sorting module for BWT in C code
 Suffix Array Implementation in Ruby
 Suffix array library and tools
 Project containing various Suffix Array c/c++ Implementations with a unified interface
 A fast, lightweight, and robust C API library to construct the suffix array
 Suffix Array implementation in Python

Низови
Индекси подниске
Структуре података за рад са нискама
У информатици , суфиксни низ је сортирани низ свих суфикса ниске . То је једноставна , али моћна структура података која се користи , између осталог , у тексту пуном индекса , при компресији података и алгоритмима из области биоинформатике . Суфиксни низови су уведени од стране Манбера и Мајерсакао једноставна и по простору ефикасна алтернатива суфиксних стабала . Она су независно откривена од стране Гонет , Баеза-Иатес , Снајдерпод именом ПАТ низ . Дефиниција Нека је ниска и нека означава подниску од у распону од до \ . Суфиксни низ од је сада дефинисан да буде низ целих бројева који пружају почетне позиције наставака од у лексикографском поретку . То значи да , унос садржи почетну позицију -тог најмањег суфикса у и тако за све \ : \ . Пример Ниску ћемо индексирати као : Текст се завршава са посебним терминирајућим словом $ који је јединствен и лексикографски мањи од било ког другог карактера . Текст има следеће суфиксе : Ове суфиксе сортирамо : Суфиксни низ садржи стартне позиције ових сортираних суфикса : Комплетан низ са суфиксима : Тако на пример , садржи вредност , и стога односи се на суфикс који почиње на позицији у , што је суфикс \ . Пребацивање у суфиксна стабла Суфиксни низови су тесно повезани са суфиксним стаблима : Суфиксни низови могу бити конструисани проласком по дубини DFS кроз суфиксно стабло . Суфиксни низ одговара обележјима листова који се добију у редоследу којим су они посећени током пролаза , ако су рубови посећени у лексикографским редоследу њиховог првог карактера . Суфиксно стабло може бити изграђено у линеарном времену коришћењем комбинације суфикса и LCP низа . Показано је да се сваки алгоритам за суфиксна стабла може систематски заменити са алгоритмом који користи суфиксни низ унапређен са додатним информацијама ( као што је LCP низ ) и решава исти проблем за исту временску сложеност . Предности суфиксних низова у односу на суфиксна стабла обухватају побољшање просторне сложености , једноставнија изградња алгоритма у линеарном времену ( нпр. у односу на Уконенов алгоритам ) и побољшање локализације кеша . Просторна ефикасност Суфиксни низови су уведенi од стране Манбера и Мајерсау циљу побољшања просторних захтева суфиксних стабала : Суфиксни низови смештају целих бројева . Под претпоставком да цео број захтевабајта , суфиксни низ захтева бајтова укупно . То је знатно мање од бајтова који се захтевају пажљивом имплементацијом суфиксног стабла . Међутим , у појединим апликацијама , просторни захтеви суфиксних низова и даље могу бити превисоки . Анализирано у битовима , суфиксни низ захтева простора , док оригинални текст преко азбуке величине захтева само битова . За људски геном са и суфиксни низ би стога заузимао окопута више меморије него сам геном . Алгоритми за конструкцију Наиван приступ за изградњу суфиксног низа је да се користи неки од алгоритама сортирања заснованих на поређењу . Ови алгоритми захтевају поређења суфикса , али поређење суфикса ради у времену , тако да је укупно време извршавања путем овог приступа је \ . Напреднији алгоритми користе чињеницу да суфикси који треба да буду сортирани нису произвољне ниске , али су међусобно повезани . Ови алгоритми настоје да постигну следеће циљеве : минимална асимптотска сложеност лаган у простору , што значи мало или нимало радне меморије поред текста и колико је потребно самом суфиксном низу брз у пракси Један од првих алгоритама за постизање свих циљева је SA-IS алгоритам аутора Нонг , Жанг , Цан Алгоритам је такође прилично једноставан ( <линија кода ) и може се повећати да истовремено изгради и LCP низ . SA-IS алгоритам је један од најбржих познатих алгоритама за изградњу суфиксног низа . Пажљива имплементација од Јута Мори надмашује већину других линеарних или супер-линеарних приступа изградње . Поред временских и просторних захтева , алгоритми за изградњу суфиксног низа се такође разликују по азбуци коју подржавају : константа азбука где је величина азбуке везана сталном , целобројном азбуком где су карактери цели бројеви у опсегу у зависности од и опште азбуке где су дозвољена само поређења карактера . Већина алгоритама за изградњу суфиксног низа су засновани на једном од следећих приступа : Алгоритми са дуплирањем префикса су засновани на стратегији \ . Идеја је да се пронађу префикси који поштују лексикографски редослед суфикса . Процењује се дужина дуплираног префикса у свакој итерацији алгоритма док је префикс јединствен и пружа ранг придруженог суфикса . Рекурзивни алгоритми прате приступ алгоритама за изградњу суфиксних стабала по за рекурзивно сортирање подскупа суфикса . Овај подскуп се онда користи за закључивање суфиксног низа преосталих суфикса . Оба од ових суфиксних низова се онда спајају и чине коначни суфиксни низ . Алгоритми за индуковано копирање су слични рекурзивним алгоритмима у смислу да они користе већ сортирани подскуп да подстакну брзо сортирање преосталих суфикса . Разлика је у томе што ови алгоритми фаворизују итерацију изнад рекурзије за сортирање изабраних подскупова суфикса . Истраживање ових разноликих група алгоритама је објављено од стране \ . Познат рекурзивни алгоритам за целобројне азбуке је DC3 / изобличење алгоритам \ . Он ради у линеарном времену и успешно се користи као основа за паралелне и алгоритме за изградњу суфиксног низа са екстерном меморијом . Најновији рад предлаже алгоритам за ажурирање суфиксног низа текста који је измењен уместо поновне изградње новог суфиксног низа од нуле . Чак и ако је теоретски у најгорем случају временска комплексност , чини се да се добро показују у пракси : експериментални резултати аутора показали су да је њихова имплементација динамичких суфиксних низова генерално ефикаснија од поновне изградње када се убацује разуман број слова у оригинални текст . Апликације Суфиксни низ ниске може да се користи као индекс да брзо лоцирате сваку појаву подниске обрасца у нисци \ . Проналажење сваког појављивања узорка је еквивалентно проналажењу сваког суфикса који почиње са подниском . Захваљујући лексикографским поретку , ови суфикси ће бити груписани заједно у суфиксном низу и могу се наћи ефикасно са две бинарне претраге . Прва претрага лоцира почетну позицију интервала , а друга одређује крајњу позицију : def search( P ) : l = 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 ) Проналажење подниске обрасца дужине у нисци дужине узима времена , с обзиром да за једно поређење суфикса треба да упоредите знакова. описују како се ова граница може побољшати до времена користећи информације из LCP низа . Идеја је да поређење обрасца не мора поново да упореди одређене знакове , када је већ познато да су део најдужег заједничког префикса за узорак и тренутни интервал претраге. су побољшали границу још даље и постигли време потраге за као што је познато из суфиксних стабала . Алгоритми за сортирање суфикса могу да се користе за рачунање Бароуз-Вилер трансформације ( БВТ ) . БВТ захтева сортирање свих цикличних пермутација низа . Ако се ова ниска завршава са посебним терминирајућим карактерима који су лексикографски мањи од свих других карактера ( тј . , $ ) , онда поредак сортиране ротиране матрице БВТ одговара редоследу суфикса у суфиксном низу . БВТ се стога може израчунати у линеарном времену , прво изградњом суфиксног низа текста и затим закључењем БВТ ниске : \ . Суфиксни низови се такође могу користити за тражење подниске у машинском преводу заснованом на примерима , захтевајући много мање простора него пуна табела фраза која се користи у статистичком машинском превођењу . Многе додатне апликације суфиксног низа захтевају LCP низ \ . Референце Литература Спољашње везе Suffix Array in Java Suffix sorting module for BWT in C code Suffix Array Implementation in Ruby Suffix array library and tools Project containing various Suffix Array c / c++ Implementations with a unified interface A fast , lightweight , and robust C API library to construct the suffix array Suffix Array implementation in Python Низови Индекси подниске Структуре података за рад са нискама