Utótag fa

Az utótagfa olyan fa , amely valamilyen karakterlánc összes utótagját tartalmazza (és csak azokat). Lehetővé teszi, hogy megtudja, hogy a w karakterlánc szerepel -e az eredeti t karakterláncban O (|w|) időben , ahol |w| a w karakterlánc hossza .

A szerkezet alapvető definíciói és leírása

$\Sigma$ a szimbólumok nem üres véges halmaza , az ábécé. Az ábécé egy (esetleg üres) karaktersorozatát r , s és t betűk jelölik . egy fordított karakterlánc. Az egyes karaktereket x, y vagy z betűk jelölik. - üres sor. $t^{{-1}}$ $\varepsilon$
Az ábécé szimbólumai az a , b, … betűk . Míg az ábécé méretét állandónak tekintjük. |t| a t karakterlánc hosszát jelöli . mind m, és . hosszúságú karakterláncok . $\Sigma ^{m}$ $\Sigma ^{*}=\bigcup \limits _{{i=0}}^({\infty }}\Sigma ^{i}$ $\Sigma ^{+}=\Sigma ^{*}\backslash \{\varepsilon \}$

A t karakterlánc w előtagja egy olyan karakterlánc, amelyben wv = t valamilyen (esetleg üres) v karakterláncra . Egy előtagot megfelelőnek nevezünkha |v| 0. $\neq$

A t karakterlánc w utótagja egy olyan karakterlánc, amelyben vw = t valamilyen (esetleg üres) v karakterláncra . Egy utótagot megfelelőnek nevezünk, ha |v| 0. Például a "substring" karakterlánchoz a "sub" a saját előtagja, a "gyűrű" a saját utótagja. $\neq$

A t karakterlánc w részkarakterláncát jobboldali ágnak nevezzük , ha t úgy ábrázolható, mint egyes karakterláncok és x y betűk esetén . A bal oldali ágat hasonlóan határozzuk meg. Például az "eabceeabcd" esetén az "abc" részkarakterlánc a jobb oldali ág, mivel mindkét előfordulásánál a t -ben különböző karakterek vannak tőle jobbra, de ugyanaz a részkarakterlánc nem bal ág, mert ugyanaz a karakter " e". $uwxv$ $u'wyv'$ $te, v, u'$ $v'$ $\neq$

$\Sigma ^{+}$ - Tree T egy gyökeres fa , amelynek éleit a következő szekvenciák jelölik . Az ábécé minden a karakteréhez a T fa minden csomópontjához legfeljebb egy él tartozik, amelynek címkéje a karakterrel kezdődik . A t és s közötti éleket v címkével jelöljük . $\Sigma ^{+}$ $t\longrightarrow _{v}s$

Legyen k a T -fa egyik csomópontja , ekkor az útvonal(k) egy karakterlánc, amely az összes élcímke összefűzése a gyökértől k -ig . Meghívjuk azt a w helyet , amelyre az útvonal( ) = w . $\Sigma ^{+}$ $\overline {w}$ $\overline {w}$

Mivel minden ág egyedi, ha path( t ) = w , a t csomópontot jelölhetjük ki . Egy csomópont részfáját jelöli . A T -fában szereplő szavakat egy halmaz adja, amelyet szavakkal ( T ) jelölünk. A w szó akkor és csak akkor szerepel a halmazszavakban ( T ), ha létezik olyan v karakterlánc (esetleg üres), amely a T fa csomópontja . $\overline {w}$ $\overline {w}$ $T_{{\overline {w))}$ $\Sigma ^{+}$ $\overline {wv}$

Ha a w karakterlánc szerepel a szavakban( T ), w = uv , a T fa egyik csomópontja, akkor a párt w linkpárnak nevezzük a T fához képest . Ha u a leghosszabb előtag, azaz egy hivatkozáspár, akkor kanonikus linkpárnak nevezzük . Majd írunk . Egy helyet explicitnek mondunk, ha |v| = 0, és egyébként implicit. $\overline {u}$ $(\overline {u},v)$ $(\overline {u},v)$ $(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$

$\Sigma ^{+}$ -A T fát , amelyben minden él egyetlen szimbólummal van megjelölve, atominak nevezzük (ehhez minden hely explicit). A T - fát , amelyben minden csomópont vagy gyökér, vagy levél vagy ág csomópontja, kompaktnak nevezzük . $\Sigma ^{+}$

Az atomfát (nyalábnak) is nevezik . Az atomfát és a kompakt fát a bennük található szavak egyedileg határozzák meg. $\Sigma ^{+}$ $próbálkozz$ $\Sigma ^{+}$

A t karakterlánc utótagfája egy -fa, amelyben a szavak( T ) = { w | w a t } részszava. Egy t karakterlánc esetén az atomi utótagfát ast( t ), a kompakt utótagfát cst( t )-vel jelöljük. $\Sigma ^{+}$

A t karakterlánc fordított előtag fája a karakterlánc utótagfája . $t^{{-1}}$

A beágyazott utótag egy olyan utótag, amely valahol máshol szerepel a t karakterláncban. A leghosszabb beágyazott utótagot a t karakterlánc aktív utótagjának nevezzük .

Utótagfák tulajdonságai

Lemma. A w helye akkor és csak akkor egyértelmű egy kompakt utótagfában, ha w a t nem beágyazott utótagja , vagy w jobboldali ág.

Bizonyíték. . Ha explicit, akkor lehet levél, vagy ágcsúcs, vagy gyökér (ebben az esetben a w is a t beágyazott utótagja ). $\Jobb nyíl$ $\overline {w}$ $w=\varepsilon$

Ha levél, akkor t utótag is . Tehát nem lehet beágyazott utótag, mert különben valahol máshol jelenne meg a t karakterláncban : v a t utótagja úgy, hogy w a v előtagja . Ez a csomópont nem lehet levél. $\overline {w}$ $\létezik$

Ha egy elágazó csomópont, akkor legalább két kimenő élnek kell lennie különböző címkékkel. Ez azt jelenti, hogy két különböző u , v utótag létezik , hogy w az u előtagja , w pedig a v előtagja , ahol v = wxs , u = , x . Ezért w jobb ág. $\overline {w}$ $\overline {w}$ $wx's'$ $\neq x'$

$\Bal nyíl$ . Ha w a t nem beágyazott utótagja , akkor levélnek kell lennie. Ha w jobboldali ág, akkor két u és v utótag van , u = wxs , v = , x , akkor w egy elágazó csomópont. A lemma bebizonyosodott . $wx's'$ $\neq x'$

Most már könnyen belátható, hogy miért található meg a válasz arra a kérdésre, hogy a w szó benne van- e a t karakterláncban O(|w|) időben : csak azt kell ellenőrizni, hogy w hely (explicit vagy implicit) a cst( t ).

Az élcímkéknek a karakterláncban lévő pozícióra kell mutatniuk, hogy az utótagfa O(n) memóriát használjon . Az élcímke (p, q) részkarakterláncot vagy üres karakterláncot jelent, ha p > q. $t_{p}\ldots t_{q}$

Ukkonen bevezeti a nyitott élek elnevezést a levelekre végződő élekre. A nyitott élcímkék (p, ) $\infty$ helyett (p, |t|) , ahol a hossz mindig nagyobb, mint |t| . $\infty$

Legyen T egy -fa. Legyen egy T csomópont , v a leghosszabb w utótag , amely egyben T csomópont is . A tól - ig címkézetlen élt utótag hivatkozásnak nevezzük . Ha v = w , akkor atomnak nevezzük . $\Sigma ^{+}$ $\overline {aw}$ $\overline {v}$ $\overline {aw}$ $\overline {v}$

Nyilatkozat. Az ast( t ) és a cst( t$ ), ahol $ t , minden utótag hivatkozás atomi. $\nem bent$

Bizonyíték. A $ szimbólumot őr szimbólumnak nevezik . Az első rész (az ast( t )-hoz) a definícióból következik, mivel a helyek explicitek. A második rész bizonyításához (cst( t ) eset) meg kell mutatnunk, hogy minden csomóponthoz tartozik cst( t ) csomópont is. Ha egy csomópont cst( t ), akkor vagy levél, vagy elágazó csomópont. Ha egy levél, akkor az aw nem a t beágyazott utótagja . A védőszimbólumnak köszönhetően a lemmából az következik, hogy minden utótag (beleértve a gyökeret, az üres utótagot is) explicit, mivel csak a gyökér beágyazott utótag. Ezért w egy levél vagy egy gyökér. Ha egy elágazó csomópont, akkor aw jobb oldali elágazás, akárcsak w . Ezért a helyet a lemma határozza meg. Az állítás bebizonyosodott. $\overline {aw}$ $\overline {w}$ $\overline {aw}$ $\overline {aw}$ $\overline {w}$

Amint ebből a bizonyításból következik, az őr szimbólum minden utótagnál garantálja a levelek meglétét. Egy ilyen karakternél nem lehetnek beágyazott utótagok az üresen kívül. Ha kihagyjuk az őr karaktert, akkor egyes utótagok beágyazódhatnak, és helyük implicitté válik.

Utótag fa memóriakövetelményei

Nyilatkozat. Egy kompakt utótag fa olyan formában ábrázolható, amely O(n) memóriát igényel.

Bizonyíték. Az utótag fa utótagonként legfeljebb egy levelet tartalmaz (pontosan egy gyámjellegű). Minden belső csomópontnak elágazó csomópontnak kell lennie, tehát egy belső csomópontnak legalább két gyermeke van. Minden ág legalább eggyel növeli a levelek számát, így legfeljebb n belső csomópontunk van, és legfeljebb n levelünk van .

Az élcímkék karakterláncainak megjelenítéséhez indexelést használunk a forráskarakterláncon, a fent leírtak szerint. Minden csomópontnak legfeljebb egy szülője van, így az élek teljes száma nem haladja meg a 2n -t .

Hasonlóképpen minden csomópontnak legfeljebb egy utótag hivatkozása van, ekkor az utótag hivatkozások száma szintén 2n -re korlátozódik . Az állítás bebizonyosodott.

Példaként egy 2n-1 csomópontot tartalmazó utótagfára tekintse meg a szó fáját . A t karakterlánc atomi utótagjának fa mérete O( ) . $a^{n}\$$ $n^{2}$

Fa építése lineáris időben. mcc algoritmus . (McCreight's Algorithm)

Az mcc algoritmus egy üres fával indul, és a leghosszabbtól kezdve utótagokat ad hozzá. Az mcc algoritmus nem on-line algoritmus, vagyis a teljes sorra szükség van a működéséhez. A helyes működés megköveteli, hogy a karakterláncot a többitől eltérő speciális karakter fejezze be, így egyetlen utótag sem lehet másik utótag előtagja. A fa minden utótagja egy levélnek felel meg. Az algoritmushoz meghatározzuk - az aktuális utótagot ( lépésben ), ( fej ) - az utótag legnagyobb előtagját , amely egyben egy másik utótag előtagja is , ahol . ( farok ) definíció szerint . $suf_{i}$ $én$ $fej_{i}$ $suf_{i}$ $suf_{j}$ $j<i$ $farok_{i}$ $suf_{i}-head_{i}$

Az mcc algoritmus kulcsgondolata a és a közötti kapcsolat . $fej_{i}$ $fej_{{i-1}}$

Lemma. Ha hol van az ábécé egy betűje, egy karakterlánc (lehet üres), akkor egy előtag . $head_{{i-1}}=aw$ $a$ $w$ $w$ $fej_{i}$

Bizonyíték. Hadd . Ekkor létezik olyan , , amely egyszerre előtagja és előtagja is . Akkor egy előtag , és ezért a fej előtagja . A lemma bevált. $head_{{i-1}}=aw$ $j$ $j<i$ $ó$ $suf_{{i-1}}$ $suf_{{j-1}}$ $w$ $suf_{i}$ $suf_{j}$ $w$ $fej_{i}$

Ismerjük a helyét , és ha van utótag-hivatkozásunk, gyorsan a fejelőtag helyére ugorhatunk anélkül , hogy meg kellene találnunk az utat a fa gyökerétől. Előfordulhat azonban, hogy a hely nem egyértelmű (ha a hely nem volt explicit az előző lépésben), és előfordulhat, hogy az utótag hivatkozás még nincs beállítva a csomóponthoz . McCray megoldása két lépésben talál egy csomópontot : „újraszkennelés” és „letapogatás”. A csomóponttól felfelé haladunk a fán, amíg nem találunk egy utótag hivatkozást, követjük azt, majd újra beolvassuk a hely elérési útját (ami egyszerű, mert tudjuk, hogy a hossza és a hely létezik, így nem kell a teljes élt olvasnunk a fán lefelé mozgó címkék esetén csak a kezdőbetűket és a szavak hosszát tudjuk ellenőrizni). $head_{{i-1}}=aw$ $w$ $fej_{i}$ $\overline {w}$ $\overline {head_{{i-1}}}$ $\overline {head_{{i-1}}}$ $\overline {head_{i}}$ $\overline {head_{{i-1}}}$ $w$ $w$

Az ábra ezt az elképzelést mutatja be. Ahelyett, hogy megpróbálna megtalálni a gyökértől a csomópontig vezető útvonalat , az algoritmus a következőre ugrik , követi az utótagot , újra beolvassa a (esetleg implicit) hely elérési útját, és karakterről karakterre haladva meg kell keresni az elérési utat . $f$ $a$ $d$ $e$ $f$

Az algoritmus három részből áll.

1. Először is meghatározza az előző fej szerkezetét, megkeresi a következő elérhető utótag hivatkozást, és követi azt.

2. Ezután újra beolvassa az előző fej azon részét, amelynek hossza ismert (ez a rész neve ). $\beta$

3. Végül az algoritmus beállítja az utótag hivatkozását , megvizsgálja a többit (névvel ), és új levelet ad hozzá . $fej_{{i-1}}$ $fej_{i}$ $\gamma$ $farok_{i}$

Ha nincs hely, az újrakeresés második fázisában létrejön egy elágazó csomópont . Ebben az esetben a vizsgálat nem szükséges, mert ha hosszabb lenne, mint , akkor jobb oldali ág lenne, de a lemma szerint ez is jobb ág, tehát a csomópontnak már léteznie kell. A csomópont a harmadik fázisban jön létre, ha a hely még nem egyértelmű. $w$ $fej_{i}$ $\alpha \beta$ $\alpha \beta \gamma$ $\alpha \beta$ $\overline {\alpha \beta }$ $\overline {head_{i}}$

1. algoritmus (mcc, McCreight) Bemenet: string t 1: T : = üres fa; 2: fej 0 := ;

\epsilon

3: n := hossz(t) ; 4: for i := 1-től n -ig csináld 5: keress , , olyat, hogy

\chi

\alpha

\beta

a. fej i-1 = ,

\chi \alpha \beta

b. ha az i-1 csomópont őse nem a gyökér ( gyökér ) , jelölje , ellenkező esetben c. és ( | fej i-1 |=0)

\overline {\chi \alpha }

|\alpha |=0

|\chi |\leq 1

|\chi |=0\Baljobbra nyíl

6: ha ( >0) , akkor 7: kövesd az utótag hivatkozást a csomóponttól a -ig ;

|\alpha |

\overline {\chi \alpha }

\overline {\alpha }

8: end if 9: := Rescan( ) ;

\overline {\alpha \beta }

\overline {\alpha },\beta

10: utótag hivatkozás beállítása től 11-ig: ( , tail i ) := Vizsgálat ( , suf i - );

\overline {head_{{i-1}}}

\overline {\alpha \beta }

\overline {head_{{i}}}

\overline {\alpha \beta }

\alpha \beta

12: a farok i -nek megfelelő levél hozzáadása ; 13: vége for

Vegye figyelembe, hogy ha akkor és ugyanolyan gyorsan felismerhető, mint az utótag hivatkozást követve az algoritmus 7. sora szerint. $|\alpha |=0$ $\overline {\alpha }=gyökér$

Az Újrakeresési eljárás helyet keres . Ha a hely még nem egyértelmű, egy új csomópont kerül hozzáadásra. Ez az eset akkor fordul elő, ha a fejet ( ) teljes egészében nézzük: ha a fej hosszabb (és a csomópont már definiált), akkor kettőnél több utótagból kell állnia, és egyben a bal oldali ága is . A hely csak akkor lehet explicit, ha az adott csomópont már elágazó csomópont, és ha nem volt bal oldali ág , akkor hosszabbnak kell lennie, mert hosszabb előtagot találtak. $\alpha \beta$ $\overline {\alpha \beta }$ $fej$ $\alpha \beta$ $t$ $\overline {\alpha \beta }$ $\alpha \beta$ $fej_{{i-1}}$

A Scan eljárás megkeresi a fa mélységét, és visszaadja a pozíciót.

1. eljárás Rescan(n, ) Bemenet : csomópont n , 1. sor: i :=1;

\beta

\beta

2: míg én | | do 3: keresse meg az e=n n' élt , w 1 = 1 ;

\leq

\beta

{{\stackrel {w}{\longrightarrow }}}

\beta

4: ha i +| w |>| |+1 majd 5: k :=| -i +1 ;

\beta

\beta

6: e él felosztása új m csomóponttal és n m és m n' élekkel ;

{{\stackrel {w_{1}\ldots w_{k}}{\longrightarrow }}}

{{\stackrel {w_{{k+1}}\ldots w_{{|w|}}}{\longrightarrow }}}

7: return m ; 8: vége, ha 9: i := i +| w |; 10: n := n' ; 11: end while 12: return n' ; 2. eljárás Scan(n, ) Bemenet : csomópont n , 1. sor: i :=1;

\gamma

\gamma

2: míg van él e = n n' , w 1 = i do 3: k :=1;

{{\stackrel {w}{\longrightarrow }}}

\gamma

4: míg w k = i és k | w | do 5: k := k +1;

\gamma

\leq

6: i := i +1; 7: vége, míg 8: ha k >| w | akkor 9: n := n' ; 10: else 11: e él felosztása új m csomóponttal és n m és m n' élekkel ;

{{\stackrel {w_{1}\ldots w_{{k-1}}}{\longrightarrow }}}

{{\stackrel {w_{{k}}\ldots w_{{|w|}}}{\longrightarrow }}}

12: return ( m , i ,..., );

\gamma

\gamma _{{|\gamma |}}

13: end if 14: end while 15: return ( n , i ,..., );

\gamma

\gamma _{{|\gamma |}}

Fa építése lineáris időben. ukk algoritmus . (Ukkonen algoritmusa)

Az az algoritmus, amelyet Esko Ukkonen egy utótagfa lineáris időben történő felépítésére talált ki, valószínűleg a legegyszerűbb ezen algoritmusok közül. Az egyszerűség abból adódik, hogy az algoritmus kezdetben egy egyszerű, de nem hatékony módszernek tekinthető, amely néhány "józan ész" megvalósításával a legrosszabb körülmények között is eléri a legjobb algoritmusok szintjét a futási idő tekintetében. Ugyanez történik a PDF-ben ábrákkal .

Az algoritmus és a megvalósítás részletes leírása C++ nyelven : cs.mipt.ru (oroszul) és marknelson.us (angolul)

Az Ukkonen algoritmushoz szükségünk van

1) Implicit utótag fák 2) Az algoritmus általános leírása 3) Algoritmus optimalizálás

Implicit utótag fák.

Ukkonen algoritmusa implicit utótagfák sorozatát építi fel, amelyek közül az utolsót valódi S karakterlánc utótagfává alakítja .

Неявное суффиксное дерево строки S — это дерево, полученное из суффиксного дерева S$ удалением всех вхождений терминального символа $ из меток дуг дерева, удалением после этого дуг без меток и удалением затем вершин, имеющих меньше двух детей. Неявное суффиксное дерево префикса S[l..i] строки S аналогично получается из суффиксного дерева для S[l..i]$ удалением символов $, дуг и вершин, как описано выше.

Bármely S karakterlánc implicit utótagfájának kevesebb levele lesz, mint az S$ karakterlánc utótagfájának, akkor és csak akkor, ha az S utótagjai közül legalább az egyik egy másik utótag előtagja. A $ terminált hozzáadtuk az S végéhez, hogy elkerüljük ezt a helyzetet. A valódi utótagfa meghatározásakor ez nagyon fontos szempont. Ha azonban az S olyan karakterrel végződik, amely sehol máshol nem szerepel az S-ben, akkor az S implicit utótagfában minden utótaghoz tartozik egy levél, és ezért valódi utótag fa.

Bár az implicit utótagfának nem minden utótaghoz van levele, az összes S utótagot kódolja – mindegyiket az implicit utótagfa gyökeréből származó útvonal karakterei ejtik ki. Ha azonban ez az út nem végződik levéllel, akkor nem lesz jelző, amely az út végét jelzi. Így maguk az implicit utótagfák valamivel kevésbé informatívak, mint a valódiak. Csak Ukkonen algoritmusának segédeszközeként használjuk őket, hogy valódi utótagfát kapjunk S-hez.

Az algoritmus általános leírása.

Построить дерево T1 for i from 1 to m - 1 do begin {фаза i + 1} for j from 1 to i + 1 begin {продолжение j} найти в текущем дереве конец пути из корня с меткой S[j..i]. Если нужно, продолжить путь, добавив символ S(i + 1), обеспечив появление строки S[j..i + 1] в дереве, end; end;

Ukkonen algoritmusa egy implicit T i utótagfát épít az S karakterlánc minden S[l..i] előtagjához, T 1 -től kezdve, és i-t eggyel növeli, amíg T m fel nem épül . Az S valódi utótag fája T m -ből származik , és az egész feladat O(m) időt vesz igénybe. Ukkonen algoritmusát úgy fogjuk elmagyarázni, hogy először bemutatunk egy módszert, amellyel minden fa O(m³) idő alatt épül fel, majd optimalizáljuk ennek a módszernek a megvalósítását úgy, hogy a deklarált sebességet elérjük.

Az utótag folytatásának három szabálya.

Ahhoz, hogy ezt az általános leírást algoritmussá alakítsuk, pontosan meg kell határoznunk az utótag folytatását. Legyen S[j..i] = β az S[1..i] utótagja. A j folytatásban, amikor az algoritmus megtalálja a β végét az aktuális fában, folytatja a β-t annak biztosítására, hogy a βS(i + 1) utótag jelen legyen a fában. Az algoritmus a következő három szabály egyike szerint működik.

1. szabály. Az aktuális fában a β útvonal egy levélben végződik. Ez azt jelenti, hogy az út a β-vel jelölt gyökértől valamilyen "levél" ív (a levélben lévő ív) végéig tart. A fa megváltoztatásakor adja hozzá az S(i + 1) szimbólumot ennek a levélívnek a címkéjének végére.

2. szabály. A β karakterlánc végétől induló út nem kezdődik S(i + 1)-el, de legalább egy út indul onnan. Ebben az esetben új levélívet kell létrehozni, a β végétől kezdve, S(i + 1) szimbólummal jelölve. Ebben az esetben, ha β az íven belül végződik, új csúcsot kell létrehozni. Az új levélív végén lévő levél j számot kap. Így a 2. szabályban két eset lehetséges.

3. szabály. A β karakterlánc végétől induló út az S(i + 1) szimbólummal kezdődik. Ebben az esetben a βS(i + 1) karakterlánc már az aktuális fában van, tehát semmit sem kell tenni (implicit utótagfában az utótag végét nem kell kifejezetten megjelölni).

Keresés az utótagfában

Adott legyen a szöveg, és jöjjön egy sor minta a bemenetre. Miután Ukkonen algoritmussal utótagfát építettünk a szövegből, az egyes minták a következőképpen kereshetők:

A bejövő minták szimbólumai szerint a bejárást addig végezzük a megszerkesztett utótagfában, amíg vagy a minta szimbólumai el nem fogynak, vagy a következő egyezés lehetetlenné válik.
1. Hagyja, hogy a minta szimbólumok elfogyjanak.
  1. Ekkor a részfa minden levelének az utolsó egyezés pontjától kezdve a száma a minta kezdeti pozíciója a szövegben.
  2. Mostantól meg lehet találni a minta k kezdőpozícióját úgy, hogy a részfát az illeszkedő útvonal végétől lineáris bejárással, például mélység- vagy szélesség-először kereséssel bejárjuk, és feljegyezzük a talált levélszámokat.
  3. Ez a pozíciók számából származó vonalra működik, mivel minden belső csúcsnak legalább két gyermeke van, és az útvonal mentén lévő levelek száma arányos a bejárt ívek számával.
2. A második esetben, amikor nincs új egyezés, akkor nincs minta a szövegben.
3. Ha csak egy előfordulást kell találni, akkor módosítani kell az előfeldolgozást, minden csúcsba beírva a részfa legkisebb levelének számát.

Általánosított utótag fa

Az utótagfát sztringek halmazára lehet építeni karakterlánc-összefűzéssel vagy anélkül. ${\displaystyle S_{1},S_{2},\dots ,S_{n))$

Karakterlánc összefűzése

Minden sor végére különféle őrszemeket (az ábécén kívüli karaktereket) adunk.
Kössük össze őket egybe.
Ezen a vonalon utótagfát építünk.
Ebben a fában a levélszámok számpárokat tartalmaznak, ahol az első a húrnak , a másik pedig a benne lévő kiindulási helyzetnek felel meg. $S_{i}$

Ez a megközelítés problémás a szintetikus utótagok jelenléte miatt, de ezt úgy oldják meg, hogy az ívekben az utótagpár második indexét a levélcsúcsokra redukáljuk.

Karakterlánc-összefűzés nélkül

Ebben az algoritmusban nem lesznek szintetikus utótagok.

Utótagfa felépítése a karakterlánchoz . $S_{1}\$$
Keressük a húr első meccseit . $l$ ${\displaystyle S_{1},S_{2))$
Az utótag fában a -ra kiegészítjük a -t . $S_{1}$ $S_{2}[l+1\dots n]\$$
Így tovább a következő sorokhoz.

Figyelembe kell venni, hogy a különböző íveken lévő tömörített címkék más-más sztringre vonatkozhatnak, ezért az íveken három számot kell tárolni.

Két karakterlánc utótagja megegyezhet, de ugyanakkor egyetlen utótag sem lesz másik utótag előtagja (az őrszem miatt). A levél ezután az utótag összes húrjára és kezdeti pozíciójára mutat.

Összehasonlítás kulcsfákkal

A minták megtalálásának problémájának megoldására létezik az Aho-Korasik algoritmus. Megtalálja az összes előfordulást - a minták teljes hossza, T - a szöveg hossza, k - az előfordulások száma. $O(P+T+k),P$

Aszimptotikus módon az összes előfordulás megtalálása egy utótagfában ugyanannyi időt vesz igénybe. De tény, hogy Aho-Korasik memóriát használ a kulcsfához , időt az építkezéshez és időt a kereséshez . De az utótag fa memóriát , időt - szerkesztést és keresést foglal el. $O(P)$ $O(P)$ $O(T)$ $O(T)$ $O(T)$ $O(P)$

Vagyis ha sok a minta és több, mint a szöveg, akkor az utótag fa kicsi, de sokáig tart a keresés. Egyébként az Aho-Korasik, amikor a minták rövidek és a szöveg nagyobb, kevesebb memóriát foglal, de az utótagfát gyorsabban keresi.

Így az egyik vagy a másik közötti választás a határidőtől vagy a memóriától függ.

Lásd még

Irodalom

Gasfield D. Húrok, fák és sorozatok az algoritmusokban: Informatika és számítási biológia / Per. angolról. I. V. Romanovszkij. - 2. kiadás - Szentpétervár. : Nyevszkij-dialektus, 2003. - 654 p.
Smith B. Methods and algoritms for computing on strings = Computing Patterns in Strings. - M. : Williams, 2006. - 496 p. - ISBN 5-8459-1081-1 , 0-201-39839-7.
Okulov S. M. Algoritmusok karakterláncok feldolgozására. - M. : Binom, 2013. - 255 p. - ISBN 978-5-9963016-2-1 .

Linkek

Fa (adatstruktúra)
Bináris keresőfa Fa (gráfelmélet) fa szerkezet
Bináris fák	bináris fa T-fa
Önkiegyensúlyozó bináris fák	AA fa AVL fa Vörös-fekete fa Splay fa fa bírságokkal karteziánus fa Fibonacci fa B-fa T-fa
B-fák	2-3-fa B⁺-fa B*-fa B x -fa UB fa 2-3-4 fa (a,b)-fa táncoló fa
előtag fák	utótag fa Tömörített előtag fa hármas keresőfa
A tér bináris particionálása	k-dimenziós fa VP fa
Nem bináris fák	Quadtree oktfa Ritka Voxel Octree exponenciális fa PQ fa
A tér felosztása	R-fa Hilbert R-fa R+-fa R*-fa X-fa M-fa Fenwick fa Szegmens fa
Más fák	halom hash fa ujjfa metrikus fa Bevonat fa BK-fa Kétláncú fa iDistance Link-vágott fa LSM fa
Algoritmusok	Szélesség első keresés Mélységi első keresés DSW algoritmus átívelő fa protokoll

Húrok
Karakterlánc hasonlósági mértékek	Távolság Damerau és Loewenstein között Levenshtein távolság Hamming távolság Jaro-Winkler hasonlóságok
Substring keresés	Boyer-Moore algoritmus Boyer-Moore-Horspool algoritmus Knuth-Morris-Pratt algoritmus Rabin-Karp algoritmus előtag funkció Z-függvény Algoritmus Aho - Korasik
palindromák	palindromfa Menedzser algoritmusa
Sorozat-igazítás	Needleman-Wunsha algoritmus Smith-Waterman algoritmus
Utótag szerkezetek	Utótag tömb Utótag automata utótag fa előtag fa
Egyéb	elemzése Mintaillesztés A legnagyobb közös sorozat Legnagyobb közös részkarakterlánc