From 94bf2bc9ad748d554b71575c9de2e3544a14f928 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 12 Jan 2009 22:02:24 +0100 Subject: [PATCH] Suffixove stromy: drobny uklid v dnesnich zmenach rekurzivniho algoritmu. --- 10-suffix/10-suffix.tex | 21 +++++++++++---------- 1 file changed, 11 insertions(+), 10 deletions(-) diff --git a/10-suffix/10-suffix.tex b/10-suffix/10-suffix.tex index d3590c7..7bb902c 100644 --- a/10-suffix/10-suffix.tex +++ b/10-suffix/10-suffix.tex @@ -169,33 +169,34 @@ V si mírnì zneu¾ívat notaci a pou¾ívat symbol $\sigma_k$ i jejich pøepis do~abecedy pùvodní. \:Zavoláme algoritmus rekurzivnì na slovo $\sigma_0\sigma_1$, èím¾ získáme $A_{01}$ a $L_{01}$. +(Suffixy slova $\sigma_0\sigma_1$ odpovídají suffixùm slov $\sigma_0$ a~$\sigma_1$.) \:Spoèítáme pole $P_0$ a $P_1$, která nám budou øíkat, kde se v~$A_{01}$ vyskytuje který suffix slov $\sigma_0$ a~$\sigma_1$. Tedy $A_{01}[P_0[i]]=i$, $A_{01}[P_1[i]] = i+\vert\sigma_0\vert$. Jinými slovy, $P_0$ a~$P_1$ budou èásti inverzní permutace k~$A_{01}$. V¹imnìte si, ¾e platí $P_i[x] < P_j[y]$ právì tehdy, kdy¾ $\sigma_i[x:{}] < \sigma_j[y:{}]$, tak¾e -suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle dovedeme porovnávat v~konstantním èase. +suffixy slov $\sigma_0$ a~$\sigma_1$ od této chvíle umíme porovnávat v~èase~$\O(1)$. -\:Vytvoøíme~$A_2$: Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$, +\:Vytvoøíme~$A_2$ (suffixové pole pro~$\sigma_2$): Jeliko¾ $\sigma_2[i:{}] = \sigma[3i+2:{}] = \sigma[3i+2]\sigma[3i+3:\nobreak{}\nobreak] = \sigma[3i+2]\sigma_0[i+1:{}]$, odpovídá lexikografické poøadí suffixù $\sigma_2[i:{}]$ poøadí dvojic $(\sigma[3i+2],P_0[i+1])$. Tyto dvojice ov¹em mù¾eme setøídit dvìma prùchody pøihrádkového tøídìní. \:Slijeme $A_{01}$ a~$A_2$ do~$A$: sléváme dvì setøídìné posloupnosti, tak¾e staèí umìt jejich prvky v~konstantním èase porovnat: $$\eqalign{ -\sigma_0[i:{}] < \sigma_2[k:{}] \Leftrightarrow{} &\sigma[3i:{}] < \sigma[3k+2:{}] \cr - \Leftrightarrow{} &\sigma[3i]\,\sigma_1[i:{}] < \sigma[3k+2]\,\sigma_0[k+1:{}],\cr -\sigma_1[i:{}] < \sigma_2[k:{}] \Leftrightarrow{} &\sigma[3i+1:{}] < \sigma[3k+2:{}] \cr +\sigma_0[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i:{}] < \sigma[3j+2:{}] \cr + \Leftrightarrow{} &\sigma[3i]\,\sigma_1[i:{}] < \sigma[3j+2]\,\sigma_0[j+1:{}],\cr +\sigma_1[i:{}] < \sigma_2[j:{}] \Leftrightarrow{} &\sigma[3i+1:{}] < \sigma[3j+2:{}] \cr \Leftrightarrow{} &\sigma[3i+1]\,\sigma[3i+2]\,\sigma_0[i+1:{}] < \cr - &\sigma[3k+2]\,\sigma[3k+3]\,\sigma_1[k+1:{}].\cr + &\sigma[3j+2]\,\sigma[3j+3]\,\sigma_1[j+1:{}].\cr }$$ Poka¾dé tedy porovnáme nejvý¹e dvì dvojice znakù a pak dvojici suffixù slov $\sigma_0$ a $\sigma_1$, k~èemu¾ nám pomohou pole $P_0$ a~$P_1$. \:Dopoèítáme $L$: - \::Pokud v~$A$ sousedí suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_{0,1}$, + \::Pokud v~$A$ sousedí suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_{0,1}$, sousedí tyto dva suffixy i v~$A_{01}$, tak¾e jejich LCP najdeme pøímo v~$L$. - \::Setkají-li se dva suffixy ze~$\sigma_2$, v¹imneme si, ¾e + \::Setkají-li se dva suffixy slova~$\sigma_2$, v¹imneme si, ¾e $\sigma_2[i:{}] = \sigma[3i+2:\nobreak{}] = \sigma[3i+2]\,\sigma_0[i+1:{}]$. ${\rm LCP}(\sigma_2[i:{}],\sigma_2[j:{}])$ je tedy buïto~0 (pokud $\sigma[3i+2]\ne\sigma[3j+2]$), nebo $1+3\cdot{\rm LCP}(\sigma_0[i+1:{}],\sigma_0[j+1:{}])$, pøípadnì toté¾ zvý¹ené @@ -203,8 +204,8 @@ k~ Pøitom ${\rm LCP}(\sigma_0[p:{}],\sigma_0[q:{}])$ spoèítáme pomocí~$L$. Je to toti¾ minimum intervalu v~$L$ mezi indexy $P_0[p]$ a~$P_0[q]$. To zjistíme v~konstantním èase pomocí struktury pro intervalová minima. - \::Pokud se setká suffix ze~$\sigma_{0,1}$ se suffixem ze~$\sigma_2$, staèí - tyto suffixy pøepsat podobnì jako v~6.~kroku a problém tak opìt pøevést + \::Pokud se setká suffix slova~$\sigma_{0,1}$ se suffixem slova~$\sigma_2$, staèí + tyto suffixy pøepsat podobnì jako v~6.~kroku a problém tím opìt pøevést na výpoèet LCP dvou suffixù slov~$\sigma_{0,1}$. \endalgo -- 2.39.2