Yazan : Şadi Evren ŞEKER

Hunt-Mcilroy algoritması, en uzun ortak küme (longest common subsequence) problemini çözmek için geliştirilen bir algoritmadır. Algoritmanın en önemli özelliği, linux ve unix türevi işletim sistemlerinde kullanılan diff komutuna temel oluşturmasıdır. Algoritma sezgisel olmayan (non-heuristic) özelliktedir. Algoritma ayrıca günümüzde versiyon takip sistemlerinde, wiki motorlarında ve moleküler biyoloji alanlarında kullanılmaktadır.

Unix üzerinde gelen diff komutunun ilke versiyonu olan ve Douglas Macllroy tarafından yazılan 1976 yılındaki algoritmanın James W. Hunt tarafından geliştirilmiş halidir.

Algoritmanın açıklandığı makalede (James W. Hunt and M. Douglas McIlroy (June 1976). “An Algorithm for Differential File Comparison”. Computing Science Technical Report, Bell Laboratories 41.) aşağıdaki şekilde anlatılmaktadır (yorum ve açıklamalar tarafımdan eklenmiştir):

Örnek olarak aldığımız iki dizgi bulunsun:

GCACGCTG

GACGCGCG

Bu dizgilerden ilkine A ve ikincisine B ismini verelim. Buna göre

Ai için i = 1,2,3,…m ve

Bj için j = 1,2,3,…n olarak tanımlı iki sayı kümesi olsun. Yani A dizgisinin uzunluğu m ve B dizgisinin uzunluğu n olarak kabul edilsin ve i ve j harfleri de bu dizgideki anlık olarak bakılan harfin kaçıncı harf olduğunu göstersin.

Bu şartlar altında bir Pij matrisi tanımlanabilir ve bu matris aşağıdaki şartları sağlayacaktır:

Pi0 = 0 , i = 0 , 1, 2, 3 … m

P0j = 0, j = 0, 1, 2,3, … n

Yani matrisin satır başlarına A dizgisinin birer harfini ve sütun başlarına da B dizgisinin sütun başlarını yerleştiriyoruz (veya tam tersi).

Ardından algoritmamız aşağıdaki şekilde geri kalan matris elemanlarını dolduruyor:

Bu formüle göre, her eleman için satır ve sütun başlıklarına bakılacak ve şayet eşitlerse diyagondaki bir önceki değer 1 arttırılacak, değillerse satır veya sütunda bir önceki değerden büyük olan kopyalanacaktır.

Bu durumu aşağıdaki masfuf(matris) üzerinden gösterelim:

ilk olarak, yukarıda görüldüğü üzere matrisin ilk satır ve sütununa 0 değerini yerleştirdik.

Ardından yukarıda görüldüğü üzere ilk satırı oluşturuyoruz. Buradaki kural gayet basit, şayet satır ve sütun harfleri eşitse, diyagondaki değer 1 arttırılıyor. Yukarıdaki şekilde, yeni satırda, satır ve sütunun eşit olduğu hücreler mavi olarak gösterilmiştir. Ayrıca bu eşitlik durumlarının diyagon değerleri de mavi olarak gösterilmiştir. Görüldüğü üzere bütün diyagon değerleri 0 olduğu için eşitlik durumları 1 olarak atanmıştır.

Diğer hücreler ise üst veya sol komşu değerinden büyük olanı alacaktır. Burada en solda 1 olduğu için hepsi 1 almıştır.

Yeni eklenen satırda, satır ve sütun değerlerinin eşit olduğu tek bir durum vardır. Buradaki diyagon değeri ise 1 olduğundan yeni değer olarak 2 yazılmıştır. Bu hücreden sonraki bütün hücrelerde sol değer (2) yukarıdaki değerden (1) büyük olduğu için 2 olarak yazılmıştır.

Tablonun tamamının doldurulmuş hali yukarıdaki şekildedir. Bu tablodaki sağ alt köşeden (iki dizginin karşılaştırılmasının bittiği hücre) başlanarak en yüksek değerler izlenirse aşağıdaki gibi bir şekil çıkacaktır:

Buna göre iki dizginin karşılaştırılma sonucu aşağıdaki şekilde yorumlanmalııdr:

GCACGCTG--
G-ACGC-GCG

Görüldüğü üzere Hunt Mcllory algoritması iki dizgi arasındaki yaslama işlemini (string alignment) tamamlamıştır ve toplam 4 harfte atlama önermektedir.

Algoritmanın önemli özelliklerinden birisi de işlenen durumu tabloda tutarak dinamik programlama (dynamic programming) kullanıyor olmasıdır.

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir