Низ суфикса

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу
Suffix array
Тип Array
Смислили Manber & Myers (1990)
Time complexity

in big O notation

Просек Најгори случај
Време
Конструкција

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

Низови суфикса су представили Manber & Myers (1990) као једноставну, просторно ефикасну алтернативу суфикс дрвима. Независно су откривене од стране Gaston Gonnet у 1987 под именом PAT низ (Gonnet, Baeza-Yates & Snider 1992).

Дефиниција[уреди]

Нека је  стринг и нека је  означи подстринг од које је од  до .

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

Пример[уреди]

Узмите у обзир текст =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

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

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

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

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

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

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

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

Међутим, у одређеним приименама, просторни захтеви низова суфикса могу да буду превисоки. Анализирано у битовима, низ суфикса захтева  простора, а оригинални текст из алфабета величине  захтева само  битова. За људски геном са  and  низ суфикса би према томе окупирао 16 пута више меморије него сам геном.

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

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

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

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

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

  • минималну асимптотску комплексност 
  • лакоћу у простору, што значи мало или без радне меморије поред текста и низа суфикса
  • брзину у пракси

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

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

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

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

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

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

Примене[уреди]

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

    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)

Тражење обрасца подстринга  дужине  у стрингу  дужине  захтева  времена, уз то да једна компарација суфикса треба да упореди карактера. Manber & Myers (1990) описују како граница може да се побољша на  времена коришћењем LCP информација. Идеја је да поређење образаца не мора да поново упоређује одређене карактере, када се већ зна су део најдужег честог префикса обрасца и тренутног интервала претраживања. Abouelhoda, Kurtz & Ohlebusch (2004) су побољшали границу још даље и достигли време претраживања  познатог из суфикс дрвећа.

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

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

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

Референце[уреди]

Референце[уреди]

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