Хант-МекИлоријев алгоритам

У рачунарству, Хант-МекИлројев алгоритам тражи решење за проблем најдужег заједничког подниза. Био је један оф првих нехеуристичких алгоритама који је коришћен у дифф рутини. Чак и данас, варијације овог алгоритма се могу наћи у системима за контролу верзија, вики претраживачима, и молекуларно филогенетичком истраживачком софтверу.

Само истраживање које је пратило верзију Униx дифф рутине, коју је написао Даглас МекИлрој, објављено је 1976 под називом "Алгоритам за диференцијално упоређивање фајлова". На тези је радио и Џејмс V. Хант, који је направио оригиналан прототип diff рутине.^[1]

Алгоритам[уреди | уреди извор]

Хунт-МекИлројев алгоритам је модификација основне идеје тражења најдужег заједничког подниза. Алгоритам је модификован тако да има мању временску и просторну сложеност када ради са типичним уносима.

Основни алгоритам за тражење најдужег подниза[уреди | уреди извор]

Алгоритам[уреди | уреди извор]

Нека је А_и и-ти елемент првог подниза.

Нека је Б_ј ј-ти елемент другог подниза.

Нека је П_иј дужина најдужег заједничког подниза за првих и елемената првог подниза и првих ј елемената другог подниза.

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}}

Пример[уреди | уреди извор]

Нека су А и Б низови.

А се састоји из 3 елемента:

А₁ = а
А₂ = б
А₃ = ц

Б се састоји из 3 елемнта:

Б₁ = а
Б₂ = ц
Б₃ = б

Кораци које би алгоритам извршио при раду да нађе најдужи заједнички подниз су приказани у дијаграму слике. Алгоритам који ово ради је свеукупно 2 реда дугачак.

Сложеност[уреди | уреди извор]

Овај алгоритам има, за најгори случај, сложеност $O(mn)$ (погледати нотацију велико О)где је м број елемената у низу А и н број елемената у низу Б. Хант-МекИлројев алгоритам временску сложеност побољшава на $O(mn\log m)$ у најгорем случају а просторну сложеност на $O(mn)$ , где је за просечан случај још ефикаснији.

Неопходна поклапања[уреди | уреди извор]

к-кандидати[уреди | уреди извор]

Хант-МекИлројев алгоритам само разматра нешто што су аутори назвали к-кандидатима. К-кандидати су парови индекса (и,ј) такви да:

А_и = Б_ј
П_иј > маx(П_и-1,ј,П_и,ј-1)

Друга ставка претпоставља својства за к-кандидате:

Постоји заједнички подниз дужине к за првих и елемената у низу А и првих ј елемената у низу Б.
Не постоји заједнички подниз дужине к за мање од и елемената у низу А и мање од ј елемената у низу Б.

Повезивање к-кандидата[уреди | уреди извор]

Да би се направио најдужи заједнички подниз из скупа к-кандидата потребно је направити мрежу са елементима оба низа на осама. К-кандидати су означени на ивицама матрице. Подниз може да се формира тако што спајамо тачке пресека у координатама, где је било какво повећање у и, праћено повећањем у ј.

Ово је илустровано на дијаграму са десне стране.

Црне тачке су оне које би биле разматране од стране основног алгоритма, и црне линије су оне које врше повезивање кандидата дужине 3.

Црвене тачке су оне које се разматрају Хант-МекИлројевим алгоритмом и црвена линија је линија која формира подниз дужине 3.

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

^ Хунт, Јамес W.; МцИлроy, M. Доуглас (1976). „Ан Алгоритхм фор Дифферентиал Филе Цомпарисон” (ПДФ). Цомпутинг Сциенце Тецхницал Репорт. Белл Лабораториес. 41.

[1] Хунт, Јамес W.; МцИлроy, M. Доуглас (1976). „Ан Алгоритхм фор Дифферентиал Филе Цомпарисон” (ПДФ). Цомпутинг Сциенце Тецхницал Репорт. Белл Лабораториес. 41.

[1]