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 Obě strany příští revize | ||
mgr-szz:in-pos:2-pos [2019/06/13 09:29] lachmanfrantisek |
mgr-szz:in-pos:2-pos [2019/06/13 09:59] lachmanfrantisek Boyer-Moore |
||
---|---|---|---|
Řádek 421: | Řádek 421: | ||
<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> | ||