Pole přípon

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. listopadu 2021; kontroly vyžadují 2 úpravy .

Pole přípon je lexikograficky seřazené pole všech přípon řetězce . Tuto datovou strukturu navrhli Eugene Myers a Udy Manber jako ekonomičtější alternativu ke stromu přípon z hlediska požadavků na paměť. Často se používá tam, kde je potřeba rychlé vyhledávání podřetězců, jako je Burrows-Wheeler Transform (BWT) a jako datová struktura ve vyhledávacím indexu .

Příklad

Zvažte řetězec "abracadabra" dlouhý 11 znaků.

abrakadabra 1 2 3 4 5 6 7 8 9 10 11

Seřazený seznam jeho přípon:

A abra abrakadabra akadabra adabra podprsenka brakadabra kadabra dabra ra racadabra

Pole přípon tohoto řetězce je {11,8,1,4,6,9,2,5,7,10,3}, protože přípona „a“ začíná 11. znakem, přípona „abra“ začíná 8. znak. go a tak dále, až k poslední příponě „racadabra“, která začíná třetím znakem původního slova.

Nyní pomocí tohoto pole můžete snadno najít všechny podřetězce. Pokud například potřebujete najít podřetězec „ab“, stačí najít všechny přípony, které začínají na „ab“. Seřazením podle abecedy jsou vedle sebe. Pomocí binárního vyhledávání najdeme 2. a 3. příponu „abra“ a „abracadabra“, které odpovídají 2. a 3. prvku pole přípon (8 a 1). To znamená, že hledaný podřetězec "ab" se vyskytuje na prvním a osmém znaku původního slova.

Konstrukce

Pole přípon lze sestavit se stromem přípon nebo bez něj tak, že se řetězec vloží do cyklické délky mocniny dvě a použije se na něj specifický algoritmus.

Prostřednictvím stromu přípon

Vytvoříme strom přípon pro řetězec T$. Kde T je text.
V tomto stromu přípon spouštíme hloubkové vyhledávání s prioritou výběru lexigraficky minimálních hran.
Při vyhledávání uvažujeme, že $ (sentinel) je lexikograficky nejmenší znak.
Příchod do listu dosáhne nějaké lexikograficky nejmenší přípony, která v tuto chvíli ještě není uvažována, jejíž hodnota v listu, počínaje indexem, musí být zapsána do aktuální buňky pole přípon.
Výsledkem je pole přípon pro celý text.

Složitost konstrukce je , řada zahrnuje konstrukci sufixového stromu a hloubkové prohledávání. $O(|T|)$

Hledat

Vyhledávání v poli přípon lze provést pomocí binárního vyhledávání. Jeho nejhorší hodnocení . Ale můžete zrychlit až . $O(n\log {m})$ $O(n+\log _{2}{m})$

Naivní binární vyhledávání

Myšlenka hledání je taková, že pokud se vzor vyskytuje v textu, pak všechny přípony začínající v poli přípon budou umístěny vedle sebe. $P$ $Pos$
Spustíme binární vyhledávání v poli přípon a najdeme nejmenší index : nezačíná na a největší index : nezačíná ani jedním . $P$ $Pos$ $i$ $Pos(i-1)$ $P$ $já'$ $Pos(i'+1)$ $P$
Poté vzorek přichází v polohách až . $Pos(i)$ $Pos(i')$
Pokud existuje mnoho předpon vzoru, skóre klesne na . $O(n\log {m})$

Jednoduché zrychlení

$L$ , — hranice intervalu vyhledávání. Na začátku , . $R$ $L=1$ $R=m$
Pamatujeme si délku předpon , , shodující se s předponou . $Pos(L)$ $Pos(R)$ $P:l,r$
$mlr=min(l,r)$ .
Při dalším srovnání na pozici začneme zpracovávat znaky nikoli od první pozice, ale od . $M={\frac {L+R}{2))$ $mlr(l,r)+1$
Obvykle pracovní doba , ale nejhorší pracovní doba je stále . $O(n+\log {m})$ $O(n\log {m})$

Akcelerace pomocí LCP

Největší společná předpona ( angl. Largest Common Prefix ) - pro dva řetězce , - délka největší shodné předpony. $S_{1}$ $S_{2}$ $LCP(S_{1},S_{2})$

V tomto algoritmu budeme předpokládat, že pro libovolné dvě přípony se počítá pro . Funkce se vypočítá ve fázi předběžného zpracování při vytváření stromu. Následující tvrzení je také pravdivé : $LCP$ $O(1)$ $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$

Díky této funkci můžete optimalizovat binární vyhledávání pole přípon.

Lemma : Pokud se první znaky přípony shodují na levém a pravém okraji ( respektive indexy pole přípon) , pak bude stejný počet znaků odpovídat všem příponám v segmentu . $L$ $R$ $k$ $[L,R]$

$L=1$ , , , . Možné jsou následující případy $R=|T|$ $l=LCP(P,L)$ $r=LCP(P,R)$
1. $l=r$ .
  1. Porovnejte příponu in se vzorem na pozici . $M={\frac {L+R}{2))$ $l+1$
  2. Přípona je lexikograficky větší nebo rovna a na pozici v příponě došlo k neshodě (pokud existuje lexikografická shoda a , považujeme ji za rovnou ), změníme hranice hledání: . $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M,R=R,l=i-1$
  3. Jinak změňte okraje takto: . $L=L,R=M,r=i-1$
2. $l>r$ . kontrolujeme . $LCP(L,M),M={\frac {L+R}{2))$
  1. $LCP(L,M)>l$ . V tomto případě za pozicí v koncovce on position , následuje řada stejných znaků jako v , které neodpovídají vzoru (pokud by odpovídaly, bylo by jich více). Takže musíte změnit hranice následovně: . $l$ $M$ $L$ $l$ $L=M,R=R,l=l$
  2. $LCP(L,M)<l$ , to znamená, že za pozicí v sufixu následuje pozice neshoda s některými znaky prefixu a většina shody se vzorem je obsažena v segmentu - to znamená , že zde rozhodně nebude výskyt vzor v segmentu. Okraje musíte změnit následovně: . $LCP(L,M)$ $M$ $L$ $L$ $[M,R]$ $L=L,R=M,r=LCP(L,M)$
  3. $LCP(L,M)=l$ to znamená, že v segmentu se první znaky ve všech příponách shodují a není možné okamžitě určit, do kterého podsegmentu přejít. Chcete-li to vyřešit, je nutné porovnat se vzorem znaky následující za pozicí v příponě . Pokud je lexikograficky menší nebo roven a existuje neshoda na -té pozici (pokud existuje lexikografická shoda a, pak považujeme za rovné ), změníme hranice následovně:, ,; jinak ( lexikograficky větší): , ,. $[L,M]$ $l$ $P$ $l$ $M$ $M$ $P$ $i$ $M$ $P$ $i$ $|P|+1$ $L=M$ $R=R$ $l=i-1$ $M$ $R=M$ $L=L$ $r=i-1$
3. $l<r$ . Zkontrolujeme a porovnáme s jako v předchozím kroku, ale změníme na a na . $LCP(R,M),M={\frac {L+R}{2))$ $r$ $L$ $R$ $l$ $r$
Algoritmus funguje tak dlouho, dokud se nestane rovnost . To znamená, že existuje segment náhody. Pokud invariant není splněn , pak v textu není žádný vzor jako podřetězec. $l$ $r$ $|P|$ $L<P<R$

Taková superakcelerace dává čas , protože se provádějí iterace nad polem přípon. $O(|P|+\log _{2}{|T|})$ $\log _{2}{|T|}$

Související algoritmy

Kasaiův algoritmus pro konstrukci pole největších společných předpon.

Viz také

příponový strom

Odkazy

Literatura

Gasfield D. Řetězce, stromy a posloupnosti v algoritmech: Informatika a výpočetní biologie / Per. z angličtiny. I. V. Romanovský. - 2. vyd. - Petrohrad. : Něvský dialekt, 2003. - 654 s.
Smith B. Metody a algoritmy pro výpočty na řetězcích = Computing Patterns in Strings. - M. : Williams, 2006. - 496 s. - ISBN 5-8459-1081-1 , 0-201-39839-7.

Struny
Míry podobnosti řetězců	Vzdálenost Damerau - Loewenstein Levenshteinská vzdálenost Hammingova vzdálenost Podobnost Jaro-Winkler
Hledání podřetězců	Boyer-Mooreův algoritmus Algoritmus Boyer-Moore-Horspool Knuth-Morris-Prattův algoritmus Rabin-Karpův algoritmus funkce předpony Z-funkce Algoritmus Aho - Korasik
palindromy	palindromový strom Manažerův algoritmus
Sekvenční zarovnání	Algoritmus Needleman-Wunsha Smith-Watermanův algoritmus
Struktury přípon	Pole přípon Přípona automat příponový strom předponový strom
jiný	rozebrat Shoda vzorů Největší společná podsekvence Největší společný podřetězec