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/12 22:15] lachmanfrantisek oprava <math> |
mgr-szz:in-pos:2-pos [2019/06/13 09:59] lachmanfrantisek Boyer-Moore |
||
---|---|---|---|
Řádek 190: | Řádek 190: | ||
=== Rozděl a panuj === | === Rozděl a panuj === | ||
- | - Problém rozděl na podproblémy. | + | - Problém rozděl na podproblémy (stejného typu). |
- Vyřeš podproblémy. | - Vyřeš podproblémy. | ||
- Z řešení podproblému sestav řešení problému. | - Z řešení podproblému sestav řešení problému. | ||
Řádek 263: | Řádek 263: | ||
^ Operace ^ Seznam ^ Binární halda ^ Binomiální halda ^ Fibonacciho halda ^ | ^ Operace ^ Seznam ^ Binární halda ^ Binomiální halda ^ Fibonacciho halda ^ | ||
| MAKE_HEAP | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | | | MAKE_HEAP | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | | ||
- | | MINIMUM | <math>\Theta(n)</math> | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | | + | | MINIMUM | <math>\Theta(n)</math> | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | |
| INSERT | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | <math>\Theta(1)</math> | | | INSERT | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | <math>\Theta(1)</math> | | ||
| UNION | <math>\Theta(1)</math> | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | | | UNION | <math>\Theta(1)</math> | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | | ||
Řádek 272: | Řádek 272: | ||
* amortizovaná složitost | * amortizovaná složitost | ||
- | == Binomiální halda == | + | <box 100% blue|Binomiální halda> |
* Na rozdíl od **binární haldy** tvořena lesem binomiálních stromů. | * Na rozdíl od **binární haldy** tvořena lesem binomiálních stromů. | ||
Řádek 278: | Řádek 278: | ||
{{https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png}} | {{https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png}} | ||
+ | </box> | ||
- | == Fibonacciho halda == | + | <box 100% blue|Fibonacciho halda> |
* zobecnění binární haldy | * zobecnění binární haldy | ||
Řádek 308: | Řádek 309: | ||
{{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}} | {{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}} | ||
+ | </box> | ||
</box> | </box> | ||
Řádek 323: | Řádek 325: | ||
* ekvivalence konečných automatů | * ekvivalence konečných automatů | ||
- | == Reverzní stromy (Reversed trees) == | + | <box 100% blue|Reverzní stromy (Reversed trees)> |
* Každá množina reprezentována stromem. | * Každá množina reprezentována stromem. | ||
Řádek 339: | Řádek 341: | ||
* Ke každému vrcholu asociujeme hloubku stromu jehož je kořenem. | * Ke každému vrcholu asociujeme hloubku stromu jehož je kořenem. | ||
* MAKE_SET konstantní složitost | * MAKE_SET konstantní složitost | ||
- | * UNION, FIND_SET O(\log n) | + | * UNION, FIND_SET <math>\mathcal{O}(\log n)</math> |
+ | </box> | ||
- | == Plytké stromy (Shallow threaded trees) == | + | <box 100% blue|Plytké stromy (Shallow threaded trees)> |
* Množinu reprezentujeme jako spojovaný seznam, první prvek je reprezentantem. | * Množinu reprezentujeme jako spojovaný seznam, první prvek je reprezentantem. | ||
Řádek 349: | Řádek 352: | ||
* MAKE_SET, FIND_SET konstantní složitost | * MAKE_SET, FIND_SET konstantní složitost | ||
* WEIGHTED_UNION <math>\mathcal{O}(\log n)</math> amortizovaná složitost | * WEIGHTED_UNION <math>\mathcal{O}(\log n)</math> amortizovaná složitost | ||
+ | </box> | ||
- | + | <box 100% blue|Stromy s kompresí (Trees with path compresion)> | |
- | == Stromy s kompresí (Trees with path compresion) == | + | |
* FIND_SET: Při postupu zpět napojíme vrcholy na cestě přímo na kořen. | * FIND_SET: Při postupu zpět napojíme vrcholy na cestě přímo na kořen. | ||
* Posloupnost m operací UNION, FIND_SET a MAKE_SET, z toho n operací MAKE_SET má složitost <math>O(m . \alpha(n))</math> | * Posloupnost m operací UNION, FIND_SET a MAKE_SET, z toho n operací MAKE_SET má složitost <math>O(m . \alpha(n))</math> | ||
+ | </box> | ||
Řádek 362: | Řá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 378: | Řádek 381: | ||
| Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>O((n-m+1)m)</math> | | | Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>O((n-m+1)m)</math> | | ||
- | * Průměrná složitost je výrazně lepší. | + | * Očekávaná složitost je výrazně lepší. |
- | === Karp-Rabin === | + | <box 100% blue|Karp-Rabin> |
* Řetězce chápeme jako čísla v desítkové soustavě. | * Řetězce chápeme jako čísla v desítkové soustavě. | ||
- | * Problém nalezení posunu redukujeme na hledání správného ciferného rozkladu. | + | * Vzorek i jednotlivé podřetězce hašujeme (pomocí Hornerova schématu) a porovnáváme tyto haše. |
+ | * Při posunutí o jednu pozici jsme schopni přepočíst haš v konstantním čas. | ||
- Příprava: <math>\Theta(m)</math> | - Příprava: <math>\Theta(m)</math> | ||
- | - Výpočet reprezentace hledaného řetězce přes Hornerovo schéma. | + | - Vypočteme haš hledaného řetězce. |
- | - Výpočet reprezentace prvního podřetězce přes Hornerovo schéma. | + | - Vypočteme haš prvního podřetězce. |
- Výpočet: <math>O((n-m+1)m)</math> | - Výpočet: <math>O((n-m+1)m)</math> | ||
- | - Výpočet dalších podřetězců | + | - Porovnáme haš vzorku a haš aktuálního podřetězce. (Pokud je roven, porovnáme řetězce a případně uložíme nalezenou pozici.) |
+ | - Posuneme se o jednu pozici v prohledávaném textu a přepočteme haš (v konstantním čase). | ||
+ | - Porovnáváme a posouváme se dokud jsme nedosáhli <math>(m-1)</math>-té pozice od konce. Poté vrátíme všechny nalezené pozice. | ||
- | === Užití konečných automatů === | + | * Očekávaná složitost pro //c// nálezů: <math>\mathcal{O}((n-m+1) + cm)</math> |
+ | * ➕ vhodné pro delší vzorky s malým počtem očekávaných nálezů | ||
+ | </box> | ||
+ | <box 100% blue|Užití konečných automatů> | ||
* Pro daný vzorek zkonstruujeme konečný automat. | * Pro daný vzorek zkonstruujeme konečný automat. | ||
* 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 100% blue|KMP> | ||
+ | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme **prefixovou funkci** pro vzorek. | ||
+ | * 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> | ||
- | === KMP === | + | <box 100% blue|Boyer-Moore> |
- | + | * Postupujeme zleva doprava a porovnáváme vzorek a text zprava. | |
- | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme prefixovou funkci. | + | * Při neshodě můžeme využít dvě pravidla pro přeskočení pozic (vybereme větší skok): |
- | * FIXME: podrobnosti | + | * **Heuristika špatného znaku** |
- | + | * nejbližší další pozice znaku z textu ve vzorku | |
- | === Boyer-Moore === | + | * symbol se nevyskytuje ve vzorku => posun o i pozic |
- | + | * **Heuristika dobrého suffixu** | |
- | * Porovnáváme vzorek a text zprava doleva. | + | |
- | * Pro posun vzorku vůči textu používáme dvě heuristiky: | + | |
- | * Heuristika špatného znaku | + | |
- | * 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> | ||
===== Zdroje: ===== | ===== Zdroje: ===== | ||
* slidy IV003 (verze 2016) | * slidy IV003 (verze 2016) |