Forum
Aktif konular
Üyeler
Kurallar
Arama
Edit Distance Maximum K Edit Distance Maximum K
-
İyi aksamlar,
İki string arasındaki mesafe ölçme işlemi için edit distance algoritmasını kullandık ve bunun c ile yazılması istenen ödevi var. Edit distance bilen bilir matris olusturuyosun ve harflerin aynı olup olmamasına göre işlemler yapıyorsun. Normalde her şeyi yaptım fakat hoca ödevde bir k sayısı istemiş ve bu k sayısına ulaşınca matrisi bitirmemiz gerekiyor yani en 2 kelime arasında en fazla k degisiklige izin vermiş gibi oluyor. Anlamayanlar için ödev: link
bu k sayısı algoritma da bir aptallığa neden oluyor zaten matirisin ilk satırını ya da sutununu yazdırırken k yı geciyosun cunku kelimenin boyutuna kadar gitmen gerekiyor matrisi olustururken. biraz kotu anlatmıs olabilirim ama durum bu. bilgisi olan müridler bi aydınlatırsa sevinirim. teşekkürler.
-
Up. İki stringi karsılastırıyoruz :d
-
anlamadigim nokta neden sorun olsun hocam?
simdi kullanicidan iki stringi alacaksin ve onlardan k degerini alacaksin. k degeri kadar degisim islemi yapacksin (Insertion,Deletion,Substitution (hocan match yazmis ama Substitution diye gecer))
bu islemi ayri bir dizide tutarsin ve k degerini gectiginde dongunu kirip bu diziyi ekranda gosterirsin. Buradaki k degeri her degisim yaptiginda olan bir deger anladigim kadariyla matrise yazmak degil..
yani hocanin orneginden yola cikarsak
do kelimesini redo ile karsilastirilmasinda;
r (Insert r, ε−>b)
re (Insert e, ε−>b)
red (Substitute d, a−>b ) (cost 0)
redo (Substitute o, a−>b ) (cost 0)
burada cost 2 olmasina ragmen 4 adim yapilmis oluyor ve k degeri de buradaki toplam islem sayisi oluyor. Yani yazilma ya da donusum degeri vs degil.
Cok emin degilsen hocaya sor bunu, cunku cok da acik yazmamis ama mantikli olan bu geliyor..
bu durumda atiyorum kullanici k degeri icin 3 vermisse ekranda gormemiz gereken red olmasi gerekiyor.
Ancak algoritmani farkli da kurabilirsin tabi ki ve o zaman gosterilen kelime farkli olabilir. Mesela once o sonra d yi substitute yaptin daha sonra e yi insert edebilirsin yani tersten de baslayabilirsin. (bu kisimdan %100 emin degilim yani cost u etkiler mi tersten baslaman.. ama matrise dizerken bence etkisi yok.. sadece kelime daha anlamsiz olabilir tersten baslandigi icin..)
unbalanced tarafından 20/Nis/16 02:55 tarihinde düzenlenmiştir -
levenshtein distance algoritması işini görebilirmi hocam?
-
TeRRoR bunu yazdı
levenshtein distance algoritması işini görebilirmi hocam?
hocam onlar ayni sey
-
@unbalancwd hocam sana guvenip dedigin sekilde yapiyorum. k yi islem sayisi kabul edicem eyvallah umarim dogrudur cunku en mantiklisi:)
@terror hocam birsuru kisinin kendi adiyla algoritmasi var ben hocanin dedigi sekilde yapmak zorundayim sonucta ayni seyler farkli yollar :)
-
sorumluluk almak istemem hocam :) hocana sor en iyisi. Ama baska bir sey olmasi pek mumkun gelmiyor bana. Ayrica
ED(A,B) dan kast ettigi her yapilan islem ve orada sart olarak ED(A,B) <=k demisse bu islemi demek istemis.
Substitution c(a−>b)
Deletion c(a−>ε)
Insertion c(ε−>b)
bak burda gordugun gibi bu degerler islemi temsil ediyor. Haliyle k da adim sayisi oluyor.
diger konuya gelince; edit distance yolun adidir ama asil adi levenshtein distance'dir da genel olarak edit distance olarak geciyor. Yaptigi is de iki string arasindaki mesafeyi bulma. Bunla ilgili farkli teoremler de vardir mutlaka ama sizin hocanizin istedigi levenshtein distance (edit distance) dir.
kolay gelsin
unbalanced tarafından 20/Nis/16 15:09 tarihinde düzenlenmiştir
Kısayol
Şikayet
Özel Mesaj
Alıntı yap
Cevapla