Longest Common Subsequence Algoritması yada Türkçe'ye En Uzun Ortak Küme Algoritması olarak çevirebileceğimiz algoritma, farklı kelimeler arasında benzerlik bulmada en çok kullanılan algoritmalardan biridir. Artık günümüzde hemen her platformda çıkan yazım denetleyicilerin(spell checker) yapımında da kullanılmaktadır.
Yazım denetleyiciler, Whatsapp'ta veya sosyal medyada, akıllı telefonlarda ki hemen her klavye uygulamasında yer alan kelime önerilerini gerçekleştiren yazılımlardır. Bu yazıda Longest Common Subsequence Algoritması'nın çalışma prensibi ve Longest Common Subsequence Algoritması c kodu yer alacaktır.
Longest Common Subsequence Algoritması
Kullanıcıya girdiği kelimeye yakın bir kelime önerirken Longest Common Subsequence algoritması, Türkçe adından da anlaşılacağı üzere kelimelerin en uzun ortak alt kümesini bulmaktadır. En uzun ortak alt kümeden kasıt, ardışık olmaksızın sıralı şekilde gelen ortak harflerin sayısıdır.
Hemen bu söylediğimize bir örnek verelim. Türkçe'de ki en çok yanlış yazılan kelimelerden biri olan "ekşi" kelimesini ele alalım ve kullanıcının "eşki" girdiğini varsayalım. Bu iki kelime arasındaki en uzun ortak küme aşağıdaki gibi bulunur:
E K Ş İ
E Ş K İ
E - Ş - İ /* İlk harf E her ikisinde de ortak ve sonrasında Ş ve İ harfleri
sıra ile gelmektedir. */
E - K - İ /* Yukarıdakine bir alternatif olarak E, K ve İ harfleri de
ardışık olmaksızın sıralı şekilde her iki kelimede de ortaktır.*/
/*- Burada iki farklı örnek yazılabilmesinin sebebi E-K-İ ve E-Ş-İ alt
kümelerinin uzunluklarının eşit olmasıdır.*/
Yukarıdaki örnekte "ekşi" ve "eşki" kelimelerinin en uzun ortak küme boyutunun 3 olduğunu gördük. Bir spell checker yazılımında girilen kelime veri tabanındaki kelimelerle karşılaştırılır ve en uzun ortak kümelerinin uzunluğu bulunur. En uzun ortak kümeye sahip elemanlar kullanıcıya önerilir.
Aşağıdaki longest common subsequence algoritması için farklı örnekler yer almaktadır:
/*
Algoritma -- Algorithm --> 8 (A-L-G-O-R_I-T-M)
Kitap -- Katip --> 3 (K-I-P veya K-T-P veya K-A-P)
Yabbadabbadoo --> Abracadabra --> 7 (A-B-A-D-A-B-A)
*/
Longest Common Subsequence Algoritması C Kodu
En uzun ortak küme algoritması c kodu aşağıdaki gibidir:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int max(int, int);
int main(){
char *w1, *w2;
int j, i, **matrix;
system("clear");
w1 = (char *)malloc(20*sizeof(char));
w2 = (char *)malloc(20*sizeof(char));
printf("Word 1: "); scanf("%s", w1);
printf("Word 2: "); scanf("%s", w2);
matrix = (int **)malloc(20*sizeof(int *));
for(i=0; i<20; i++){
matrix[i] = (int *)malloc(20*sizeof(int));
}
for(i=0; i
}
for(i=0; i
}
for(i=1; i<=strlen(w1); i++){
for(j=1; j<=strlen(w2); j++){
if(w1[i-1] == w2[j-1]){
matrix[i][j] = matrix[i-1][j-1] + 1;
}else{
matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1]);
}
}
}
printf("\nLongest Common Subsequence between %s and %s = %d\n\n", w1, w2, matrix[strlen(w1)][strlen(w2)]);
return 0;
}
int max(int x, int y){
if(x < y)
return x;
else
return y;
}
Yukarıdaki c kodu parçası, kullanıcı tarafından girilen iki kelime arasındaki en uzun ortak kümenin uzunluğunu bulmaktadır. Bunun içinde bir uzaklık matrisi kullanır. Long common subsequence algoritmasında uzaklık matrisi oluşturabilmek için aşağıdaki adımlar izlenir:
-- Kelimelerin uzunluklarının bir fazlası kadar satır ve sütun sayısına sahip bir tam sayı matrisi oluşturulur. (Bir kelimeyi satırlara diğer bir kelimeyi sütunlara aşağıdaki resimdeki gibi yerleştirdiğimizi varsayalım.)
-- "BDCB" ve "BACDB" harflerinden oluşan keliemeleri bir matrisin satır ve sütunlarını oluşturacak şekilde yerleştirin.
-- İlk satır ve ilk sütunun bütün elemanlarına 0 verin.
-- 1. satır 1. sütundan itibaren her bir eleman eğer bulunduğu noktadaki harfler eşit ise bir üst satırdaki aynı sütunda bulunan eleman ve bir önceki sütundaki aynı satırda yer alan elemandan hangisi büyükse ona eşit olmalıdır.
--Eğer o noktadaki elemanlar birbirine eşit değil ise bu seferde bir üst satırdaki bir önceki sütunda yer alan elemanın bir fazlasına eşitlenmelidir.
Bu maddeye (1,1) ve (1,2) noktaları için örnek verelim(Matrisin (0,0) noktasından başladığını unutmayın). (1,1) noktasında b harfi her iki kelime içinde ortak o zaman bir üst satırdaki bir önce gelen sütuna yani (0,0) noktasındaki değerin 1 fazlasına eşit olmalıdır. ((0,0) + 1 = 0 + 1 = 1)
(1,1) noktası 1 değerine eşit oldu. (1,2) için bakalım. B ve D harfleri birbirine eşit değil bu yüzden (1,1) ve (0,2) noktalarından değeri büyük olan elemanı (1,2) noktasına atayacağız. (1,2) değeri (1,1) noktasındaki 1 değerine eşit olur. Bu kural için genel fonksiyon aşağıdaki gibidir:
i=0 yada j=0 --> matris(i)(j) == 0
Kelime1(i) = Kelime2(j) --> matris(i)(j) = matris(i-1)(j-1) + 1
Kelime1(i) != Kelime2(j) --> matris(i)(j) = max(matris(i-1)(j), matris(i)(j-1))
-- Bu işlem son satır son sütuna kadar devam ettirilir ve son satır son sütundaki eleman iki kelime arasındaki en uzun ortak kümenin boyutuna eşit olur.
Yukarıda verilen longest common subsequence c kodu için ekran görüntüleri aşağıdaki gibidir:
Longest Common Subsequence Algoritması (En Uzun Ortak Küme) ile ilgili bütün sorularınızı bu yazının altına yorum olarak bırakabilirsiniz.
Kaynak
