Obousměrný algoritmus shody řetězců - Two-way string-matching algorithm - Wikipedia

TřídaAlgoritmus prohledávání řetězců
Datová strukturaŽádný tětiva s objednanou abecedou
Nejhorší případ výkonNa)
Nejlepší případ výkonNa)
Nejhorší případ složitost prostoruO (1)

v počítačová věda, obousměrný algoritmus shody řetězců je efektivní algoritmus prohledávání řetězců na které lze pohlížet jako na kombinaci vpřed Algoritmus Knuth – Morris – Pratt a zpětně běžící Algoritmus vyhledávání řetězců Boyer – Moore. Maxime Crochemore a Dominique Perrin vynalezli tento algoritmus v roce 1991.[1] Doba předzpracování je lineární k velikosti jehly. Má lineární výkon v nejhorším případě při 2n-m srovnání.[2] Breslauer má dvě vylepšení s menším počtem srovnání: jedno s konstantním prostorem a n + podlaha (1 + eps / 2 × (n − m)) srovnání, druhé s logem (m) prostor a n + podlaha ((n − m) / 2) srovnání.[3]

Stejně jako u KMP a BM algoritmy využívají posuny založené na částečně se opakujících periodách ve vzoru. Dělá to však prostřednictvím rozdělení (kritické faktorizace) jehly na dvě poloviny, takže z předzpracování je třeba si pamatovat pouze jednu hodnotu.

Algoritmus je považován za poměrně efektivní v reálných podmínkách, je vhodný pro mezipaměť a obsahuje operace, které lze nahradit funkcemi knihovny. Je vybrán jako glibc (a odvozený newlib; str-two-way.h) a musl algoritmus pro rodinu podřetězcových funkcí memmem a strstr.[4][5][6] Stejně jako u nejpokročilejších algoritmů pro vyhledávání řetězců však existuje tendence k bodu zvratu ve velikosti kupky sena i jehly, před kterým je naivní kvadratická implementace (memchr-memcmp) efektivnější.[7] Glibc poskytuje Breslauerův algoritmus v obou formách.[6]

Kritická faktorizace

Než definujeme kritickou faktorizaci, měli bychom definovat:[1]

  • Faktorizace: řetězec je považován za faktorizovaný, když je rozdělen na dvě poloviny. Předpokládejme řetězec X je rozdělena na dvě části (u, v), pak (u, v) se nazývá faktorizace X。
  • Doba: období p pro řetězec X je definována jako hodnota taková, že pro jakékoli celé číslo 0 < i ≤ |X| - p, X[i] = X[i + p]. Jinými slovy, "p je období X pokud dvě písmena X na dálku p vždy se shodují. "Minimální doba X je kladné celé číslo označené jako p (x).
  • A opakování w v (u, v) je podřetězec z X takové, že:
    • w je přípona u nebo naopak;
    • w je předpona proti nebo naopak;
    Jinými slovy, w dochází na obou stranách řezu s možným přetečením na obou stranách. Každá faktorizace triviálně má alespoň jedno opakování, řetězec vu.[2]
  • A místní období je délka opakování v (u, v). Nejmenší místní období v (u, v) je označen jako r (u, v). Pro jakoukoli faktorizaci 0 < r (u, v) ≤ |X|.
  • A kritická faktorizace je faktorizace (u, v) z X takhle r (u, v) = p (x). Pro jehlu délky m v seřazené abecedě lze vypočítat v 2m srovnání výpočtem lexikograficky větší ze dvou uspořádaných maximálních přípon definovaných pro řád ≤ a ≥.[6]

Algoritmus

Algoritmus začíná kritickou faktorizací jehly jako kroku předzpracování. Tento krok vytvoří index (počáteční bod) periodické pravé poloviny a období tohoto úseku. Výpočet přípony zde následuje autorovu formulaci. Alternativně jej lze vypočítat pomocí jednoduššího Duvalův algoritmus, což je pomalejší, ale také lineární čas.[8]

Zkratka pro inverzi.funkce cmp (a, b) -li a> b vrátit se 1    -li a = b vrátit se 0    -li a vrátit se -1funkce maxsuf (n, rev) l ← len (n) p ← 1 aktuálně známé období.    k ← 1 index pro testování období, 0     j ← 0 index pro testování maxsuf. větší než max.    i ← -1 navrhovaný počáteční index maxsuf        zatímco j + k -li rev cmpv ← -cmpv invertovat srovnání        -li cmpv <0 Přípona (j + k) je menší. Období je zatím celá předpona.            j ← j + k k ← 1 p ← j - i jinak pokud cmpv = 0 Jsou stejné - měli bychom pokračovat.            -li k = p Dokončili jsme kontrolu tohoto úseku p. resetovat k.                j ← j + p k ← 1 jiný                k ← k + 1 jiný            Přípona je větší. Začněte odsud.            i ← j j ← j + 1 p ← 1 k ← 1 vrátit se [i, p]funkce crit_fact (n) [idx1, per1] ← maxsuf (n, false) [idx2, per2] ← maxsuf (n, true) -li idx1> idx2 vrátit se [idx1, per1] jiný        vrátit se [idx2, per2]

Porovnání pokračuje tak, že se nejprve shoduje pro pravou stranu a poté pro levou stranu, pokud se shoduje. Přeskakování v lineárním čase se provádí pomocí tečky.

funkce shoda (n, h) nl ← len (n) hl ← len (h) [l, p] ← crit_fact (n) P ← {} sada zápasů.         Porovnejte příponu.    Použijte funkci knihovny, jako je memcmp, nebo napište vlastní smyčku.    -li h [0] ... h [l] = h [p] ... h [l + p] P ← {} pos ← 0 s ← 0 DĚLAT. Přinejmenším vložte skip.

Reference

  1. ^ A b Crochemore, Maxime; Perrin, Dominique (1. července 1991). „Obousměrné shody řetězců“ (PDF). Deník ACM. 38 (3): 650–674. doi:10.1145/116825.116845.
  2. ^ A b "Obousměrný algoritmus".
  3. ^ Breslauer, Dany (květen 1996). "Ukládání srovnání v algoritmu Crochemore-Perrin pro porovnávání řetězců". Teoretická informatika. 158 (1–2): 177–192. doi:10.1016/0304-3975(95)00068-2.
  4. ^ „musl / src / string / memmem.c“. Citováno 23. listopadu 2019.
  5. ^ „newlib / libc / string / memmem.c“. Citováno 23. listopadu 2019.
  6. ^ A b C „glibc / string / str-two-way.h“.
  7. ^ „Eric Blake - Re: PATCH] Zlepšit výkon memmemu“. Newlib mailing list.
  8. ^ Adamczyk, Zbigniew; Rytter, Wojciech (květen 2013). "Poznámka k jednoduchému výpočtu maximální přípony řetězce". Journal of Discrete Algorithms. 20: 61–64. doi:10.1016 / j.jda.2013.03.002.