Hant-MekIlorijev algoritam

U računarstvu, Hant-MekIlrojev algoritam traži rešenje za problem najdužeg zajedničkog podniza. Bio je jedan of prvih neheurističkih algoritama koji je korišćen u diff rutini. Čak i danas, varijacije ovog algoritma se mogu naći u sistemima za kontrolu verzija, viki pretraživačima, i molekularno filogenetičkom istraživačkom softveru.

Samo istraživanje koje je pratilo verziju Unix diff rutine, koju je napisao Daglas MekIlroj, objavljeno je 1976 pod nazivom "Algoritam za diferencijalno upoređivanje fajlova". Na tezi je radio i Džejms V. Hant, koji je napravio originalan prototip diff rutine.^[1]

Algoritam

Hunt-MekIlrojev algoritam je modifikacija osnovne ideje traženja najdužeg zajedničkog podniza. Algoritam je modifikovan tako da ima manju vremensku i prostornu složenost kada radi sa tipičnim unosima.

Osnovni algoritam za traženje najdužeg podniza

Algoritam

Neka je A_i i-ti element prvog podniza.

Neka je B_j j-ti element drugog podniza.

Neka je P_ij dužina najdužeg zajedničkog podniza za prvih i elemenata prvog podniza i prvih j elemenata drugog podniza.

P_{ij}={\begin{cases}0&{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\1+P_{i-1,j-1}&{\mbox{ if }}A_{i}=B_{j}\\max(P_{i-1,j},P_{i,j-1})&{\mbox{ if }}A_{i}\neq B_{j}\\\end{cases}}

Primer

Neka su A i B nizovi.

Tabela koja pokazuje rekurzivne korake osnovnog algoritma za nalaženje najdužeg zajedničkog podniza.

A se sastoji iz 3 elementa:

A₁ = a
A₂ = b
A₃ = c

B se sastoji iz 3 elemnta:

B₁ = a
B₂ = c
B₃ = b

Koraci koje bi algoritam izvršio pri radu da nađe najduži zajednički podniz su prikazani u dijagramu slike. Algoritam koji ovo radi je sveukupno 2 reda dugačak.

Složenost

Ovaj algoritam ima, za najgori slučaj, složenost $O(mn)$ (pogledati notaciju veliko O)gde je m broj elemenata u nizu A i n broj elemenata u nizu B. Hant-MekIlrojev algoritam vremensku složenost poboljšava na $O(mn\log m)$ u najgorem slučaju a prostornu složenost na $O(mn)$ , gde je za prosečan slučaj još efikasniji.

Neophodna poklapanja

k-kandidati

Hant-MekIlrojev algoritam samo razmatra nešto što su autori nazvali k-kandidatima. K-kandidati su parovi indeksa (i,j) takvi da:

A_i = B_j
P_ij > max(P_i-1,j,P_i,j-1)

Druga stavka pretpostavlja svojstva za k-kandidate:

Postoji zajednički podniz dužine k za prvih i elemenata u nizu A i prvih j elemenata u nizu B.
Ne postoji zajednički podniz dužine k za manje od i elemenata u nizu A i manje od j elemenata u nizu B.

Povezivanje k-kandidata

Dijagram koji pokazuje kako k-kandidati smanjuju vreme i prostor potrebno za nalaženje najdužeg zajedničkog podniza.

Da bi se napravio najduži zajednički podniz iz skupa k-kandidata potrebno je napraviti mrežu sa elementima oba niza na osama. K-kandidati su označeni na ivicama matrice. Podniz može da se formira tako što spajamo tačke preseka u koordinatama, gde je bilo kakvo povećanje u i, praćeno povećanjem u j.

Ovo je ilustrovano na dijagramu sa desne strane.

Crne tačke su one koje bi bile razmatrane od strane osnovnog algoritma, i crne linije su one koje vrše povezivanje kandidata dužine 3.

Crvene tačke su one koje se razmatraju Hant-MekIlrojevim algoritmom i crvena linija je linija koja formira podniz dužine 3.

Vidi još

Reference

^ Hunt, James W.; McIlroy, M. Douglas (1976). „An Algorithm for Differential File Comparison” (PDF). Computing Science Technical Report. Bell Laboratories. 41.

[1] Hunt, James W.; McIlroy, M. Douglas (1976). „An Algorithm for Differential File Comparison” (PDF). Computing Science Technical Report. Bell Laboratories. 41.

[1]