Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze Následující verze Obě strany příští revize | ||
mgr-szz:in-pos:2-pos [2019/06/13 08:15] lachmanfrantisek |
mgr-szz:in-pos:2-pos [2019/06/13 09:59] lachmanfrantisek Boyer-Moore |
||
---|---|---|---|
Řádek 365: | Řádek 365: | ||
==== Algoritmy pro práci s řetězci ==== | ==== Algoritmy pro práci s řetězci ==== | ||
- | <note tip>Podrobněji viz http://statnice.dqd.cz/home:inf:in17</note> | + | <note tip>Některé algoritmy (naivní, Karp-Rabin, automaty) jsou podrobněji rozepsány zde: http://statnice.dqd.cz/home:inf:in17</note> |
Algoritmy pro: | Algoritmy pro: | ||
Řádek 405: | Řádek 405: | ||
* Využití sufixové funkce <math>\sigma</math> určující délku nejdelšího prefixu vzorku, který je sufixem slova. | * Využití sufixové funkce <math>\sigma</math> určující délku nejdelšího prefixu vzorku, který je sufixem slova. | ||
* <math>\delta(q, a) = \sigma(P[1] ... P[q] a)</math> | * <math>\delta(q, a) = \sigma(P[1] ... P[q] a)</math> | ||
- | * Existuje procedura s <math>O(m|\Sigma|)</math> | + | * Tato metoda v <math>\mathcal{O}(m^3 \times \mid\Sigma\mid)</math>. |
+ | * Existuje procedura s <math>\mathcal{O}(m \times \mid\Sigma\mid)</math>. | ||
* Text zpracujeme konečným automatem. <math>\Theta(n)</math> | * Text zpracujeme konečným automatem. <math>\Theta(n)</math> | ||
</box> | </box> | ||
<box 100% blue|KMP> | <box 100% blue|KMP> | ||
- | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme prefixovou funkci. | + | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme **prefixovou funkci** pro vzorek. |
- | * FIXME: podrobnosti | + | * Postupně pro každou pozici ve vzorku určíme délku největšího podvzorku, který je zároveň prefixem i sufixem dosud zpracované části vzorku. |
+ | * <math>\mathcal{O}(m)</math> | ||
+ | * Samotný výpočet pak probíhá obdobně jako naivní prohledávání, ale při neshodě (nebo nalezení vzorku) se: | ||
+ | * na textu nevracíme | ||
+ | * na vzorce posuneme na pole dle prefixové funkce | ||
+ | * <math>\mathcal{O}(n)</math> | ||
</box> | </box> | ||
<box 100% blue|Boyer-Moore> | <box 100% blue|Boyer-Moore> | ||
- | * Porovnáváme vzorek a text zprava doleva. | + | * Postupujeme zleva doprava a porovnáváme vzorek a text zprava. |
- | * Pro posun vzorku vůči textu používáme dvě heuristiky: | + | * Při neshodě můžeme využít dvě pravidla pro přeskočení pozic (vybereme větší skok): |
- | * Heuristika špatného znaku | + | * **Heuristika špatného znaku** |
- | * symbol se nevyskytuje ve vzorku => posun o i pozic | + | * nejbližší další pozice znaku z textu ve vzorku |
- | * Heuristika dobrého suffixu | + | * symbol se nevyskytuje ve vzorku => posun o i pozic |
+ | * **Heuristika dobrého suffixu** | ||
* najdeme nejpravější výskyt u = T[j+i+1...m-1], před kterým je symbol různý od a | * najdeme nejpravější výskyt u = T[j+i+1...m-1], před kterým je symbol různý od a | ||
* => posun o i-r pozic (r = index znaku různého od a) | * => posun o i-r pozic (r = index znaku různého od a) | ||
* nenajdeme nejdelší řetězec v, který je současně prefixem i sufixem P | * nenajdeme nejdelší řetězec v, který je současně prefixem i sufixem P | ||
* => posun vzorku o m-|v| pozic | * => posun vzorku o m-|v| pozic | ||
+ | * Tabulky pro heuristiky si lze ze vzorku předpočítat před samotným výpočtem. <math>\mathcal{O}(m \times |\Sigma|)</math> | ||
+ | * Vyhledávání <math>\mathcal{O}(m \times n)</math>, ale očekávaně výrazně lepší. | ||
+ | * nejlepší případ: <math>\mathcal{O}(\frac{n}{m})</math> | ||
</box> | </box> | ||