https://buraksenyurt.com/Burak Selim Şenyurt - Algoritma2023-12-04T13:46:55+00:00Matematik Mühendisi Bir Bilgisayar Programcısının NotlarıBurak Selim SenyurtBlogEngine.Net Syndication Generatorhttps://buraksenyurt.com/opml.axdBurak Selim SenyurtMatematik Mühendisi Bir Bilgisayar Programcısının Notlarıtr-TRBurak Selim Şenyurt0.0000000.000000https://buraksenyurt.com/post/Blockchain-Eliptik-Egri-Sifreleme-AlgoritmasıBlockchain Eliptik Eğri Şifreleme Algoritması2018-07-24T07:00:00+00:00bsenyurt<p><img style="float: right;" src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_intro.gif" alt="" />Merhaba Arkadaşlar,</p>
<p>Matematik tek evresenl dil olarak varoluşumuzdan bu yana yaşamın içerisinde. Onun diğer bilimlere olan pozitif etkisi tartışılamaz. Bugün ulaştığımız noktada teknoloji sınırlarını zorlarken yüz yıllar öncesinden ispat edilmiş pek çok teoremin uygulanabilirliklerine de rastlıyoruz. Doğruyu söylemek gerekrise 1999 yılında ilk işe başladığımdan beri matematik'ten epey uzakta sadece kod yazmaktayım. Belki de bugün .Net Core'un Linux üzerinde koşturulup bir Cloud platformuna taşınması da önemli bir mevzu. Lakin o hayranlık duyduğumuz fikirlerin arkasında, çok fazla ilişmediğimiz<em>(belki de bakmaya korktuğumuz)</em> güçlü bir matematik var. Bende büyük bir cesaretle o fikirlerden birisinin arkasında olan matematiği bir nebze olsun anlamak istedim. Matematik kesin kuralları olan bir dil olduğu içi, yazdığım şeyleri doğru telafüz etmem gerekiyor. Eğer basit bir şekilde anlatabilirsem, konuyu da anlamış sayılırm<em>(Son gün notu: Basitleştiremedi)</em></p>
<p>Geçtiğimiz iki hafta boyunca neredeyse her gün yarım saatimi ayırdığım ve anlamak için çaba sarf ettiğim bir konu oldu. Blockchain'in kullandığı Elliptic Curve Cryptography(ECC) algoritmasının nasıl çalıştığını öğrenmek. Araştırmalarıma başladığımda olayın içerisinde matematiğin bilgisayar şifreleme teknikleri üzerine kullanılan bir çok teorisine denk geldim. 1993 yılında girdiğim Matematik Mühendisliği bölümünde okurken gördüğüm pek çok konu burada da yer alıyordu. Ama zaman içerisinde hepsini unutmuşum. İkinci ve üçüncü dereceden denklemler, eliptik eğriler, asal sayılar, gruplar, sonlu alanlar<em>(Finite Fields)</em>, Fermat'nın küçük teoremi<em>(Little Theorem)</em>, modüler aritmetik, ayrık logaritma problemi<em>(discrete logarithm problem), </em>double and add algoritması, euclid vs... Aslında her şey Blockchain sisteminde yer alan eliptik eğri denklemine ait grafik gösterimin, gerçek sayılar ile ifade edileninden çok daha farklı olduğunu öğrenmemle başladı diyebilirim.</p>
<p>Örneğin Bitcoin, secp256k1 isimli ve aşağıdaki eşitlikle ifade edilen eliptik eğri denklemini kullanmakta. secp256k1' deki sec, Standards for Efficent Cryptography anlamına gelirken 256 değeri asal sayının kaç bit olduğunu ifade etmektedir. Sonlara doğru bu kavramları anlayacağım/anlatabileceğim diye umut ediyorum.</p>
<p><strong>y<sup>2</sup>=x<sup>3</sup>+7</strong></p>
<p>Gerçek sayılar için olan gösterimi şöyle;</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_2.gif" alt="" /></p>
<p>Toplam eleman sayısı asal olacak şekilde oluşturulmuş bir sonlu alan dizilimi için olan gösterimi ise şu şekilde;</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_3.gif" alt="" /></p>
<p>Merak uyandırdı değil mi? Öyleyse ilk konumuz ile başlayalım.</p>
<h1>Eliptik Eğriler</h1>
<p>Eliptik eğri denklemlerine geçmeden önce bir kaç basit denklemi de hatırlamamız lazım. Doğrusal, ikinci dereceden ve üçüncü dereceden denklemleri ve x,y düzlemindeki gösterimlerini görünce sizler de hatırlayacaksınız?</p>
<p><strong>y=ax+b , doğru denklemi</strong></p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_4n.gif" alt="" /></p>
<p><strong>y=ax<sup>2</sup>+bx+c , parabol denklemi</strong></p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_5.gif" alt="" /></p>
<p><strong>y=ax<sup>3</sup>+bx<sup>2</sup>+cx+d , 3ncü dereceden denklem</strong></p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_6.gif" alt="" /></p>
<p>ve tabii konumuz olan eliptik eğri denklemi.</p>
<p><strong>y<sup>2</sup>=x<sup>3</sup>+ax+b</strong></p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_7.gif" alt="" /></p>
<p>Yukarıdaki şekilde denkleme ait bir kaç farklı örnek görmektesiniz. Her ne kadar ben çok iyi çizemesemde, özellikle x ekseni özelinde simetriklik olduğunu söyleyebiliriz. Bazı hallerde iki ayrı eğri ve bazı hallerde de bu iki eğrinin birleştiği grafikler söz konusu. <strong>y<sup>2</sup></strong> den kaynaklı bir durum olduğu aşikar. Eliptik eğrilerin enteresan bir özelliği de vardır. Eğri üzerinde olduğu bilinen iki koordinat söz konusu olduğunda, bu koordinatların x değerleri birbirinden farklı olmak şartıyla, her iki koordinatın toplamından yine eğri üzerine denk düşen 3ncü bir koordinatı bulmamız mümkündür. Bulunuş şekli matematik severler için hayranlık uyandırıcıdır. Aşağıdaki şekille konuyu anlatmaya çalışayım.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_8.gif" alt="" /></p>
<p>Şekilde M<sub>3 </sub>noktasını bulunuşu ifade edilmektedir. Olay şöyle başlar. Eğri üzerinden bilinen iki nokta referans alınır. x değerleri birbirlerinden farklı olan iki nokta. Bu noktaların üstünden geçen bir doğru çizilir. Çizilen doğru eğriyi 3ncü bir noktada daha kesecektir<em>(örneğimizdeki P noktası)</em> Bu noktanın iz düşümü de simetrik taraftaki bir noktaya denk gelmektedir<em>(örneğimizdeki M<sub>3</sub>)</em> İşte teoriye göre M<sub>1</sub> ve M<sub>2</sub> noktalarının toplamı M<sub>3</sub> noktasını elde etmemizi sağlamaktadır. Tabii toplam dediğimiz olay biraz daha farklı. Noktayı bulmak için aşağıdaki gibi sıralanmış bir formül takımından yararlanılır.</p>
<blockquote>
<p>3ncü noktanın bulunmasında ilk iki noktanın sıralı olması şart değildir. Sadece eğri üzerinde olduğu bilinen iki noktanın üzerinden geçen doğrunun kestiği üçüncü noktanın x düzlemindeki iz düşümü önemlidir.</p>
</blockquote>
<p>Eğri denklemimiz : <strong>y<sup>2 </sup>= x<sup>3 </sup>+ ax + b</strong></p>
<p><strong>M1 = (x1,y1) , M2 = (x2,y2), M1 + M2 = (x3,y3)</strong></p>
<p><em>x1 ve x2 eşit olmadığı sürece</em></p>
<p>Eğim <strong>s = (y<sub>2</sub> - y<sub>1</sub>) / (x<sub>2</sub> - x<sub>1</sub>)</strong></p>
<p><strong>x<sub>3</sub> = s<strong><sup>2</sup></strong><sup> </sup>- <strong>x<sub>2</sub> - x<sub>1</sub></strong></strong></p>
<p><strong>y<sub>3</sub> = s(x<sub>1</sub> - x<sub>3</sub>) - y<sub>1</sub></strong></p>
<p>Kafamızı çok fazla bulandırmadan 3ncü nokta bulmanın nasıl yapıldığını basit bir örnekle inceleyelim.</p>
<p>y<sup>2</sup>=x<sup>3</sup>+5x+7<br />P<sub>1</sub> = (2,5) , P<sub>2</sub> = (3,7) => P<sub>3</sub> = ?<br /><br />5<sup>2</sup>= 25 = 2<sup>3</sup>+(5*2)+7 <em>(P<sub>1</sub> noktası eğri üzerinde)</em><br />7<sup>2</sup>= 49 = 3<sup>3</sup>+(5*3)+7 <em>(P<sub>2</sub> noktası eğri üzerinde)<br /></em><br />s = (7 - 5) / (3 - 2) = 2 <em>(Eğimi bulduk)</em><br />x<sub>3</sub> = 2<sup>2</sup><sup> </sup>- 2 - 3 = -1<br />y<sub>3</sub> = 2(2 - (-1) ) - 5 = -1<br /><br />P<sub>3</sub> = (-1,1) <br />1<sup>2</sup>= 1 = -1<sup>3</sup>+(5*(-1))+7 <em>(P<sub>3</sub> noktası eğri üzerinde)</em></p>
<p>Şimdi örnekte neler oldu anlamaya çalışalım. Denklem ortada. İki tane noktamız var. Öncelikle bu noktaların eğri üzerinde olup olmadıklarının sağlamasını yapıyoruz<em>. </em>Sonrasında eğim değerini(s) bulmamız gerekiyor. Eğim bulunduktan sonra bu değerden yararlanarak x<sub>3</sub> bilinmeyenini ve x<sub>3</sub>'ü de işin içerisine katarak y<sub>3</sub> değerini hesaplıyor ve 3ncü noktanın koordinatlarını bulmuş oluyoruz. Son aşamada yine x<sub>3</sub>,y<sub>3</sub> noktasının eliptik eğri üzerinde olup olmadığının sağlamasını gerçekleştiriyoruz. Bunu program kodu ile de deneyimleyebiliriz. Özellikle Python gibi diller bu tip matematiksel işlemler için kolaylıklar sunmakta. </p>
<pre class="brush:py;auto-links:false;toolbar:false" contenteditable="false">p1=(2,5)
p2=(3,7)
def isOnCurve(p):
"""
p1 egri ustunde mi bakalim
"""
(x,y)=p1
return y**2 == x**3+(5*x)+7
def findSlope(p1,p2):
"""
p1 ve p2den yararlanarak egimi buluyoruz
"""
(x1,y1)=p1
(x2,y2)=p2
s=(y2-y1)/(x2-x1)
return s
def findThirdPoint(p1,p2,s):
"""
p1 ve p2den yararlanip 3ncu noktanin bulunmasi
"""
(x1,y1)=p1
(x2,y2)=p2
x3=s**2-x2-x1
y3=s*(x1-x3)-y1
return (x3,y3)
print p1,"is on curve?",isOnCurve(p1)
print p2,"is on curve?",isOnCurve(p2)
print findSlope(p1,p2)
print findThirdPoint(p1,p2,findSlope(p1,p2))</pre>
<p>Python tarafına aşina olmayanlar için bile okunması oldukça kolay bir kod parçası görmektesiniz. x,y koordinatlarını işaret eden noktaları tuple tipi ile işaret etmekteyiz. Bu bir noktanın x ve y değerlerini taşırken veya elde ederken işlerimizi kolaylaştırmakta. isOnCurve fonksiyonu parametre olarak verilen noktanın eğri üzerinde olup olmadığını kontrol ediyor. findSlope metodu ile tahmin edeceğiniz üzere eğim değerini buluyoruz. findThirdPoint fonksiyonu p1 ve p2 parametrelerinden yararlanılarak p3ün yani 3ncü noktanın bulunmasında kullanılmakta. Kodu Visual Studio Code üzerinde geliştirebilirsiniz. Şahsen ben, öyle yaptım.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_12.gif" alt="" /></p>
<h1>Eliptik Eğrilerin Gruplar ile İlişkisi</h1>
<p>Eliptik eğriler ile matematik grupları arasında yakın ilişki vardır. Özellikle asallık söz konusu ise. Bunları bir eliptik eğri için düşündüğümüzde şunları söyleyebiliriz. </p>
<ul>
<li>G'yi noktaların olduğu bir grup olarak düşünürsek iki noktanın toplamı (P<sub>1</sub> + P<sub>2</sub> = P<sub>3</sub>) yine G'nin içinde yer alacaktır<em>(Kapalılık özelliği)</em></li>
<li>P<sub>1</sub> + P<sub>2</sub> + P<sub>3</sub> = 0 aynı hat üzerinde 3 nokta söz konusu olduğunda toplam sonucu 0 olarak çıkar<em>(Tabii noktaların hiçbirisi 0 olmayacak)</em></li>
<li>Grubun mutlaka şu eşitliği sağlayan bir birim elemanı vardır ki eliptik eğriler için 0 olduğunu söyleyebiliriz. P<sub>1</sub> + 0 = 0 + P<sub>1</sub> = P<sub>1</sub></li>
<li>Her bir noktanın x ekseninde bir simetrisi vardır. </li>
<li>Eğer değişebilirlik ( P<sub>1</sub> + P<sub>2</sub> = P<sub>2</sub> + P<sub>1</sub> ) söz konusu ise bu grup Abelian<em>(Değişmeli diyebiliriz)</em> olarak isimlendirilir<em>(Abelian olmanın avantajları nelerdir halen araştırıyorum sevgili okur)</em></li>
</ul>
<p>Grup olma özellikleri biraz sonra kriptografinin zorluğunu ortaya koyarken değer kazancak. Bu nedenle eliptik eğri kriptografisine geçmeden önce sonlu alanlara, asal sayılar nezninde de uğramamız gerekiyor.</p>
<h1>Sonlu Alanlar</h1>
<p>Artık eliptik eğrilerin nasıl bir denklem ile ifade edildiğini biliyoruz. Yazının başında Blockchain tarafından kullanılan denklemin grafiğini hatırlarsanız gerçek sayılar yerine toplam eleman sayısı bir asal sayı ile ifade edilen eliptik eğrinin söz konusu olduğunu belirtmiştik. Peki ne olaki bu sonlu alanlar<em>(Finite Fields)</em> Aşağıdaki gibi ifade edilen bir sayı dizisi olduğunu düşünelim<em>(Aslında bizler için 0dan başlayan 13 elemanlı bir tamsayı dizisi)</em></p>
<p><strong>F<sub>13</sub> = {0, 1, 2, 3, … 12}</strong></p>
<p>Bu dizilimin en önemli yanı 13 elemandan oluşması. 13 asal bir sayı. Dizinin bir diğer önemli özelliği de <span style="text-decoration: underline;">modüler aritmetik</span> denklik kuramına göre içerideki iki sayının toplamının yine içerideki bir elemanı veriyor olması. Üstelik bu sadece toplama değil, çıkarma, çarpma ve bölme işlemleri için de geçerli bir durum. Sadece bölme işleminde kafaların biraz karışabildiği bir senaryo var ki burada da işin içerisine Fermat'nın Küçük Teorim<em>(Fermat's Little Theorem)</em> girmekte.</p>
<p>Toplama, çıkartma ve çarpma işlemlerine örnekler;</p>
<p>4 + 5 = 9 % 13 = 9 (Dizi içerisinde)<br />8 + 11 = 19 %13 = 6 (Dizi içerisinde)<br />8 - 12 = (-4) % 13 = 4 (Dizi içerisinde)<br />9 - 4 = 5 % 13 = 5 (Dizi içerisinde)</p>
<p>Gelelim bölme işlemine...</p>
<p>2 / 3 = 2 * 3<strong><sup>-</sup></strong><sup>1 </sup>= 2 * 3<sup>11</sup><sup> </sup>= 354.294 % 13 = 5 (Dizi içerisinde)<br />3 / 12 = 3 * 12<strong><sup>-</sup></strong><sup>1 </sup>= 3 * 12<sup>11 </sup>= 2.229.025.112.064 % 13 = 10 (Dizi içerisinde)</p>
<p>İşlemler biraz tuhaf geldi değil mi? Özellike -1 üs değerinin eşitliğin devamında 13-2 şeklinde ifade edilmesi. Burada az önce bahsettiğimiz küçük teorimin büyük bir önemi var. Fermat'a göre p bir asal sayı, a bir tamsayı ve a ile p aralarında asal<em>(p, a'nın bir çarpanı olamaz)</em> iken</p>
<p>2<sup>11 </sup>- 2 = 2046 % 11 = 0 </p>
<p>gibi bir işlem'den bahsedilebilir. Modüler aritmetik notasyonuna göre ifade şudur.</p>
<p>a<sup>p </sup>≡ a (mod p)</p>
<p>Buradan hareketle teoremin ispatı sırasında kullanılan Euler teoremine göre de</p>
<p>a<sup>p-1 </sup>≡ 1 (mod p)</p>
<p>dir. Henüz ispatını araştıramamış olsam da bu denkliklerden yola çıkılarak şu ifadenin de doğru olduğu söylenmekte.</p>
<p>a<sup>p-2 </sup>≡ a<sup>-1 </sup>≡ 1/a (mod p)</p>
<p>Böylece bir bölme işleminin modüler aritmetik enstürmanlarına göre yine dizi içerisindeki bir elemanı işaret ettiğini görmüş oluyoruz.</p>
<h1>Eliptik Eğrideki Ayrık Logaritma Problemi</h1>
<p>Gelelim yukarıda anlattıklarımızı kullanarak neler yapabileceğimize bakmaya. Bir eliptik eğri üzerinde bir başlangıç noktası seçtiğimizi düşünelim. P olarak isimlendirelim<em>(Sonradan Generator Point adına kavuşacak)</em> Buna göre P'nin 1 katını, 2katını, 3katını ekleyerek devam edelim. Artık elimizde bir nokta grubu var ve onu şöyle ifade edebiliriz.</p>
<p>{0, P, 2P, 3P, 4P, 5P,... (n-1)P}</p>
<p>Çarpan olarak ele alınan n'nin gizli bir anahtar olduğunu düşündüğümüzde her ne kadar sP=Q değerini bulmak kolay olsa da P ve Q'yi bilip s'yi bulmaya çalıştığımız durumda bu o kadar da kolay olmayacaktır. Çünkü 0 ile n-1 arasındaki tüm olası değerleri göz önüne alıp eşitliğin sağlanıp sağlanmadığını anlamamız gerekir. Bunun sebebi ayrık logaritma problemi ile açıklanmaktadır. </p>
<blockquote>
<p><strong>Discrete Logarithm Problem</strong></p>
<p>Aşağıdaki işlemi düşünelim.</p>
<p> 3<sup>29 </sup>mod 17 ≡ 12</p>
<p>Burada 12 değerine ulaşmak kolay. Fakat soru şu;</p>
<p>3<sup>x </sup>mod 17 ≡ 12</p>
<p>Burada x değerini nasıl bulabiliriz? Aslında 3ün olası üslerini taramak söz konusu eşitlikteki uygun x değerini bulmak için yeterli. Küçük bir asal sayı için bu çok büyük sorun teşkil etmeyecektir. Sorun 17 sayısı yerine çok çok çok büyük bir asal sayı geldiğinde ortaya çıkmaktadır. Teorikte mümkün ama pratiğe dökülmesi için asal değere göre dünyadaki işlemci gücünün tamamına sahip olsak bile çok uzun yıllar sürebilecek bir problem söz konusu<em>(Uzmanların dilinden) </em></p>
</blockquote>
<p>Tekrar P noktalarından oluşan grubumuza dönelim. Buradaki çarpan hesaplamaları için Double and Add algoritmasından yararlanılabilir.</p>
<blockquote>
<p><strong>Double and Add algorithm</strong></p>
<p>Double and Add algoritmasında noktanın çarpanının ikilik sayı sistemindeki ifadesinden yararlanılır. Şöyle başlayalım. 19 asal sayısının ikilik sistemdeki karşılğı </p>
<p>10011</p>
<p>şeklindedir.</p>
<p>Bunu üssel gösterimle ifade etmek istersek şu eşitliği de yazabiliriz.</p>
<p>19 = 10011 = 1.2<sup>4</sup> + 0.2<sup>3</sup> + 0.2<sup>2 </sup>+ 1.2<sup>1 </sup>+ 1.2<sup>0 </sup></p>
<p>Buna göre bir noktanın 19 ile çarpımını da şu şekilde ifade etmemiz mümkün hale gelir.</p>
<p>19P = 2<sup>4</sup>P + 2<sup>1</sup>P + 2<sup>0</sup>P</p>
<p>Oluşan eşitliğe göre Double and Add algoritması şöyle işletilir.</p>
<p>P noktasını al.</p>
<p>Bunu 2ye katla(double). Bu sayede 2P değerini elde ederiz.</p>
<p>2P yi P ile topla(add) Böylece 2<sup>1</sup>P + 2<sup>0</sup>P değerini yakalarız.</p>
<p>...</p>
<p>Bu şekilde ikiye katlama ve toplama işlemlerinin tekrar edilmesi yoluyla sonuca ulaşabiliriz. Siz örneğin 151 sayısı için bu denkliği sağlamaya çalışarak konuyu pekiştirebilirsiniz. İpucu olarak başlangıçı veriyorum;</p>
<p>151 = 10010111 = 1.2<sup>7</sup> + 0.2<sup>6</sup> + 0.2<sup>5 </sup>+ 1.2<sup>4 </sup>+ 0.2<sup>3 </sup>+ 1.2<sup>2 </sup>+ 1.2<sup>1 </sup>+ 1.2<sup>0 </sup>= 2<sup>7 </sup>+ 2<sup>4 </sup>+ 2<sup>2 </sup>+ 2<sup>1 </sup>+2<sup>0</sup></p>
</blockquote>
<p> </p>
<p>Bir nokta grubu için tam sayı ile çarpma işlemini ele aldığımıza göre P grubu için şöyle bir örnek yapalım.</p>
<p>Denklemimiz <strong>y<sup>2 </sup>= x<sup>3 </sup>+ 2x + 3<br /></strong>Sonlu alandaki toplam sayı adedi <strong>17</strong> (asaldır dikkat edin)<br />Başlangıç noktamız<strong> P(3,6)<br /></strong>Buna göre P'yi kendisi ile toplaya toplaya aşağıdaki dizilimi elde edebiliriz. </p>
<p>0P = 0<br />1P = (3,6)<br />2P = (12,2)<br />3P = (15,5)<br />4p = (14,2)<br />5P = (8,2)<br />6P = (8,15)<br />7P = (14,15)<br />8P = (15,12)<br />9P = (12,15)<br />10P = (3,11)<br />11P = (∞,∞)<br />12P = (3,6)<br />13P = (12,2)<br />14P =(15,5)<br />...</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_11.gif" alt="" /></p>
<p>Bir şey dikkatinizi çekti mi? Toplamda denklemi sağlayan 22 adet (x,y) noktası söz konusu iken biz 11 elemanlı bir alt grup elde ettik ve bu grubun tekrar eden bir döngü içerisinde olduğunu görmekteyiz. Buradaki hesaplamalar için aşağıdaki örnek kod parçasını da kullanabiliriz. Fonksiyonları ve kullanım şekillerini anlamaya çalışın. İçeride bir de uzatılmış Euclid algoritması olarak isimlendirilmiş bir kısım var.</p>
<pre class="brush:py;auto-links:false;toolbar:false" contenteditable="false">import collections
EllipticCurve = collections.namedtuple('EliptikEgri', 'name p a b g')
params = EllipticCurve(
'y^2=x^3+ax+b', #denklem
p=17, #toplam nokta sayisi
a=2, #denklem a degeri
b=3, #denklem b degeri
g=(3,6) #generator noktasi
)
def ReverseOfMod(n, p):
"""
n mod p isleminin tersini dondurur.
egim hesaplamasi isleminde p1 = p2 ve p1 != p2 durumlari icin gerekli
"""
if n == 0:
raise ZeroDivisionError('division by zero')
if n < 0:
# n ** -1 = p - (-n) ** -1 (mod p)
return p - ReverseOfMod(-n, p)
# Uzatilmis Euclid Algoritmasi uygulanir (Extended Euclidean Algorithm)
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = p, n
while r != 0:
d = old_r // r
old_r, r = r, old_r - d * r
old_s, s = s, old_s - d * s
old_t, t = t, old_t - d * t
gcd, x, y = old_r, old_s, old_t #gcd-greates common divisor - ebob
return x % p
def FindNegativePoint(p):
"""
negatif noktayi bulur
"""
if p is None:
return None
x, y = p
result = (x, -y % params.p)
return result
def Add(p1, p2):
"""
grup yasasindaki kriterlere gore p1+p1 islemini gerceklestirir
"""
if p1 is None:
# 0 + p2 = p2 durumu
return p2
if p2 is None:
# p1 + 0 = p1 durumu
return p1
x1, y1 = p1
x2, y2 = p2
if x1 == x2 and y1 != y2:
return None
if x1 == x2:
# p1==p2 durumu
m = (3 * x1 * x1 + params.a) * ReverseOfMod(2 * y1, params.p)
else:
# p1!=p2 durumu
m = (y1 - y2) * ReverseOfMod(x1 - x2, params.p)
x3 = m * m - x1 - x2
y3 = y1 + m * (x3 - x1)
result = (x3 % params.p,-y3 % params.p)
return result
def Multiply(n, p):
"""
n * P islemini gerceklestirir
"""
if n < 0:
return Multiply(-n, FindNegativePoint(p))
result = None
nextP = p
while n:
if n & 1:
result = Add(result, nextP)
nextP = Add(nextP, nextP)
n >>= 1
return result
for i in range(0,17):
print i,Multiply(i,(3,6))</pre>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2018/02/ecc_13.gif" alt="" /></p>
<p>Nokta sahası sonlu uzunlukta ve çok doğal olarak alt grup da öyle. Ancak denklem ve asal sayı değeri dikkatli seçilirse çok büyük bir grubun elde edilmesi söz konusu olabilir. Öyle ki geri çevirlemeye çalışıldığında bu inanılmaz derecede zor olur.</p>
<h1>Bitcoin Cephesi(secp256k1)</h1>
<p>Onlar Blockchain'in bu kriptografi kuramını göz önüne alarak aşağıdaki parametreleri içeren bir eğri tanımlamışlar. </p>
<p>Denklem : <strong>y<sup>2</sup>=x<sup>3</sup>+7<br /></strong>Sonlu alan asal sayı değeri <strong>(p)</strong> = 2<sup>256 </sup>-2<sup>32 </sup>- 2<sup>9 </sup>-2<sup>8 </sup>-2<sup>7 </sup>-2<sup>6 </sup>- 2<sup>4 </sup>- 1 <br />Giriş noktası<strong> G</strong>=( 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 )<br />Bir gruptaki asal nokta sayısı <strong>n</strong> = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141</p>
<p>Dikkat edileceği üzere nokta ve asal sayı değerleri oldukça büyük. Bu da ayrık logaritma probleminin getireceği sorunun çözümünü oldukça zorlaştırır nitelikte. Her şeyden önce ortada 256bitlik bir asal sayı var. Bunun bir sonucu da en iyimser tahminle ortada 2<sup>256 </sup>olası gizli anahtarın olması ki herhangibirini tespit edebilmek için var olanlarından mümkün olduğunca çoğunu bilmek gerekiyor. Bunu anlatmak çok zor ama trilyonlarca yıl alabilecek bir zaman ortaya çıktığı söyleniyor(Teorik olarak)</p>
<p>Peki yazılımcı olarak biz bu değerleri kullanarak ne yapabiliriz? Aslında seçeceğimiz bir private key değeri ile public key üretebilir sonra bu iki anahtar bilgisinden yararlanarak dijital bir imza oluşturarak belgelerimizi kriptolayabiliriz. Bu amaçla kullanılabilecek pek çok kütüphane var. Hatta <a href="https://blog.todotnet.com/2018/02/public-private-keys-and-signing/" target="_blank">şu adreste güzel bir kod örneği</a> de bulunmakta. İnceleyip denemenizi öneririm.</p>
<h1>Sonuç</h1>
<p>Eliptik Eğri denklemi Blockchain ve ondan türeyen pek çok yapı tarafından asimetrik şifre üretilip transaction'ların imzalanması maksadıyla kullanılmakta. Asitmerik şifrelemede public ve private olmak üzere iki anahtar söz konusu. Public Key herkes tarafından görülebilir bir bilgi ama private key tahmin edeceğiniz üzere kişiye özel. Private key değeri kullanılarak public key değerinin elde edilmesi mümkün. Bu değeri elde ederken yukarıdaki eliptik eğri denkleminden yararlanılmakta. Ancak public key değerini kullanarak private key bilgisine oluşturmak en azından önümüzdeki birkaç milyon yüz yıl(belki de fazlası) için mümkün değil. Blockchain bir transaction'ı imzalarken private key ile oluşturulmuş bir hash değeri kullanıyor. Hash bilgisinin geriye döndürülerek private key içeriğinin bulunması zaten mümkün değil lakin public key değerine sahip olan birisi kendi ürettiği private key'leri kullanarak oluşturacağı hash'leri karşılaştırmaya çalışabilir. Lakin burada onu bekleyen şey Eliptik Eğri Dijital Kriptografi Algoritması<em>(Elliptic Curve Digital Signature Algorithm)</em> oluyor; ki bu konu şu an için beni aşmakta. Kaynaklar arasında daha fazla kaybolmadan hatırladığım eski matematik denklemlerimi bir kenara bırakıyor ve hepinize mutlu günler diliyerek istirahata çekiliyorum.</p>
<h1>Kaynaklar</h1>
<p><a href="https://eng.paxos.com/blockchain-101-foundational-math" target="_blank">Blockchain 101 - Foundational Math</a><br /><a href="https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography" target="_blank">Blockchain 101 - Elliptic Curve Cryptography</a><br /><a href="https://tr.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/congruence-modulo" target="_blank">Modulo Denklik<br /></a><a href="http://mathworld.wolfram.com/EllipticCurve.html" target="_blank">MathWorl - Elliptic Curve</a><br /><a href="https://learncryptography.com/cryptocurrency/51-attack" target="_blank">Learn Cryptography - CryptoCurrency(51 Attack)</a><br /><a href="https://www.johannes-bauer.com/compsci/ecc/" target="_blank">Johannes Bauer - ECC</a><br /><a href="http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/" target="_blank">Andrea Corbellini - Elliptic Cure Cryptography - A Gentle Introduction<br /></a><a href="http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/" target="_blank">Andrea Corbellini - Elliptic Cure Cryptography - Finite Fields and Discrete Logarithms<br /></a><a href="http://scialert.net/fulltext/?doi=jse.2007.1.12" target="_blank">Implementation of Elliptic Curve Digital Signature Algorithm<br /></a><a href="https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/modk-mul.html" target="_blank">Elliptic Curve Scalar Multiplaction Calculator<br /></a><a href="https://en.bitcoin.it/wiki/Secp256k1" target="_blank">BitcounWiki</a></p>2018-07-24T07:00:00+00:00cryptographyblockchainelliptic curve cryptographygroup lawmodular arithmeticfinite setsdistrict logarithmlogarithmExtended Euclidean AlgorithmmatematikbsenyurtBlockchain ve onu baz alarak günümüzün popüler ilgi alanlarından birisi haline gelen BitCoin, kriptolamada Elliptic Curve Cryptography(ECC) olarak adlandırılan bir algoritmayı kullanmakta. Bu yazımızda temel matematik bilgilerimizi işin içerisine katıp, Fermat'nın Little Therorem'ine uğrayacak, Modüler aritmetik'ten yararlanıp, grup kavramı ve eliptik eğriler üzerinden geçerek algoritmanın temel dayanak noktalarını öğrenmeye çalışacağız.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=110ec920-9ff1-4380-bc7b-c98c1657937b9https://buraksenyurt.com/trackback.axd?id=110ec920-9ff1-4380-bc7b-c98c1657937bhttps://buraksenyurt.com/post/Blockchain-Eliptik-Egri-Sifreleme-Algoritmas%C4%B1#commenthttps://buraksenyurt.com/syndication.axd?post=110ec920-9ff1-4380-bc7b-c98c1657937bhttps://buraksenyurt.com/post/floyd-warshall-algoritmasi-ile-en-kisa-yolu-bulmakFloyd-Warshall Algoritması ile En Kısa Yolu Bulmak2016-04-23T12:00:00+00:00bsenyurt<p><img style="float: right;" src="https://buraksenyurt.com/image.axd?picture=/2016/04/FWa_6.gif" alt="" />Merhaba Arkadaşlar,</p>
<p>Uzun zamandır algoritmalar üzerinde çalışmadığımı fark ettim. İşlerin biraz olsun hafiflediği şu vakitlerde de bir tanesini inceleyeyim dedim. Derken kendimi <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" target="_blank"><strong>Floyd-Warshall</strong> algoritmasını</a> anlamaya çalışırken buldum. Söz konusu algoritma <strong>Graph</strong> yapılarında boğumlar arasındaki en kısa yolların bulunmasında kullanılmaktadır.</p>
<p>Gerçek hayat örnekleri düşünüldüğünde <strong>Regular Expression</strong>, <strong>Network Routing</strong>, <strong>Dynamic Programming</strong>, yönsüz graph'ların iki parçalı graph'lar dönüştürülmesi ve daha bir çok alanda kullanıldığına şahit oluruz. Algoritmanın matematiksel çalışmasına bakıldığında boğumların birbirlerine olan yakınlıklarını ele alan matrisleri kullandığını görürüz.</p>
<p>Aslında konuyu eğlenceli olabileceğini düşündüğüm bir senaryo üzerinden ele alırsak çok daha iyi olur. Bu anlamda aşağıdaki grafiği göz önüne alalım. <em>(Grafiğin oluşmasında <a href="https://www.quora.com/What-is-an-intuitive-explanation-of-the-Floyd-Warshall-algorithm" target="_blank">Quora</a>'nın bana çok güzel fikir verdiğini ifade etmek isterim)</em></p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2016/04/FWa_1nn.gif" alt="" /></p>
<p>Biz evimizde oturuyoruz ve örneğin Haldun Taner sahnesine gideceğiz. Normal şartlarda direkt bir güzergah kullanırsak 5 km yol gitmemiz gerekiyor. Diğer yandan önce Capitol'e, oradan Burhan Felek'e ve oradan'da Haldun Taner'e geçersek toplamda 4 km yol katediyoruz. 1 km kazancımız var bu güzergahı takip edersek. Eğer önce Burhan Felek'e oradan Haldun Taner'e geçersek de 7 km yol kat edeceğiz. Senaryoyu biraz daha geliştirelim. Diyelim ki evden Burger House'a gideceğiz. Karnımız acıkmış. Doğrudan gidersek 4 km yol almamız lazım. Farklı güzergahlar da tercih edebiliriz. Örneğin Haldun Taner üzerinden geçersek 9km, Okul üzerinden geçersek 24km yol. Bunun gibi bir yerden diğer bir yere giderken pek çok güzergah ve mesafe belirlenebilir.</p>
<p>İşte <strong>Floyd-Warshall</strong> algoritması bir boğumdan diğer bir boğuma gitmek için kullanılabilecek en kısa yolların çıkartılmasında devreye girerek karar vermemizi kolaylaştırır. <span style="line-height: 1.8;">Şimdi yukarıdaki senaryoyu biraz daha bilimsel hale getirip lokasyonlar arasındaki en kısa </span><span style="line-height: 1.8;">mesafeleri</span><span style="line-height: 1.8;"> bulmaya çalışalım. Öncelikle boğumlarımıza aşağıdaki gibi numaralar verelim ve ilk olarak yakınlık matrisimizi oluşturalım. <em>(Yakınlık matrisinin ilk versiyonu boğumların komşu boğumlar ile arasındaki mesafelerini tanımlamaktadır)</em></span></p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2016/04/FWa_2n.gif" alt="" /></p>
<p>Matrisimizin ilk hali aşağıdaki gibi olacaktır.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2016/04/FWa_3.gif" alt="" /></p>
<p>Bu matris bize ne söylüyor acaba?</p>
<p>Bazı hücrelerde sonsuzluk sembolü, bazı hücrelerde ise sıfır değeri var. İki boyutlu bu matris boğumların en yakın diğer boğuma olan mesafelerini göstermekte. Bir boğumun kendisiyle arasındaki mesafe 0, doğrudan bağlı olmadığı bir boğumlar arasındaki mesafe ise sonsuz sembolü ile işaret edilmekte. Örneğin n1 boğumundan n3 ve n4 boğumlarına doğrudan bir hat olmadığı için sonsuz sembolü kullanıldı. Algoritmanın becerisi sonsuz sembollerini eritmek ve hatta sayısal değer alan hücrelerde olabilecek daha kısa mesafeler var ise bunları matris üzerinde güncellemektir.</p>
<p>Örneğin n1'den n3'e direkt gidişimiz olmadığından sonsuz olarak işaretlenmiş durumda. Oysa ki n1->n2->n3 şeklinde bir ulaşım var. Yani n2 üzerinden geçiş yaparak n3'e varabiliriz. Elbette n3'e varmak için n6 üzerinden de hareket edebiliriz. Yani n1->n6->n3 şeklinde bir güzergah da söz konusu olabilir. Hatta n1->n5->n4->n3 şeklinde de gidebiliriz.</p>
<p>İşte matrisimizi bu şekilde algoritma içerisinde işleterek nihai haline getirmemiz gerekiyor. Tahmin edeceğiniz üzere bu, çok da uğraşmak isteyeceğimiz türden bir iş değil :) Bu yüzden zaten kod yolu ile ilgili algoritmayı çalıştırmayı tercih etmekteyiz. Aşağıda algoritmanın kullanımına ilişkin bir kod parçası yer almaktadır.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Linq;
namespace FloydWarshallCode
{
class Program
{
static void Main(string[] args)
{
double[][] proximityMatrix = PrepareFirstState();
Solve(ref proximityMatrix);
Dump(proximityMatrix);
}
public static void Solve(ref double[][] matrix)
{
int size = matrix.Count();
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
for (int k = 0; k < size; k++)
{
matrix[j][k] = Math.Min(matrix[j][k], matrix[j][i] + matrix[i][k]);
}
}
}
}
private static double[][] PrepareFirstState()
{
double[][] matrix = new double[6][]{
new double[6],
new double[6],
new double[6],
new double[6],
new double[6],
new double[6]
};
matrix[0][0] = 0;
matrix[0][1] = 5;
matrix[0][2] = double.PositiveInfinity;
matrix[0][3] = double.PositiveInfinity;
matrix[0][4] = 16;
matrix[0][5] = 8;
matrix[1][0] = 5;
matrix[1][1] = 0;
matrix[1][2] = 1;
matrix[1][3] = double.PositiveInfinity;
matrix[1][4] = double.PositiveInfinity;
matrix[1][5] = 2;
matrix[2][0] = double.PositiveInfinity;
matrix[2][1] = 1;
matrix[2][2] = 0;
matrix[2][3] = 1;
matrix[2][4] = double.PositiveInfinity;
matrix[2][5] = 6;
matrix[3][0] = double.PositiveInfinity;
matrix[3][1] = double.PositiveInfinity;
matrix[3][2] = 1;
matrix[3][3] = 0;
matrix[3][4] = 4;
matrix[3][5] = 5;
matrix[4][0] = 16;
matrix[4][1] = double.PositiveInfinity;
matrix[4][2] = double.PositiveInfinity;
matrix[4][3] = 4;
matrix[4][4] = 0;
matrix[4][5] = 4;
matrix[5][0] = 8;
matrix[5][1] = 2;
matrix[5][2] = 6;
matrix[5][3] = 5;
matrix[5][4] = 4;
matrix[5][5] = 0;
return matrix;
}
public static void Dump(double[][] matrix)
{
int size = matrix.Count();
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
Console.Write("{0}\t", matrix[i][j]);
}
Console.WriteLine();
}
}
}
}</pre>
<p>Console uygulamasının 3 önemli fonksiyonu vardır. İlk olarak makalemizin başında bahsettiğimiz yakınlık matrisinin birinci versiyonunu hazırlayan basit bir metod bulunur. Pek tabii gerçek hayat senaryolarında ilgili matrisin belli bir Graph kaynağından otomatik olarak hazırlanması söz konusudur. Uygulamayı çalıştırdığımızda aşağıdaki ekran görüntüsünde yer alan sonuç matrisini elde ederiz.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2016/04/FWa_4.gif" alt="" /></p>
<p>Buna göre bir noktadan bir noktaya gidilebilecek en kısa mesafeler bulunmuştur. Örneğin <strong>n3 noktasından n5 noktasına gitmek istediğimizde en kısa güzergah 5km</strong> <strong>uzunluğunda olup n3->n4->n5 rotası</strong> şeklindedir. Diğer alternatif yollara bakıldığında gerçekten de en kısa mesafenin bu olduğu açıkça görülebilir.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2016/04/FWa_5.gif" alt="" /></p>
<p>Görüldüğü üzere <strong>Floyd-Warshal,</strong> <strong>Graph</strong> tabanlı veri kümelerinde boğumlar arası en kısa mesafelerin buluması için kullanılabilecek basit ve hızlı algoritmalardan birisidir. Konu hakkında internet üzerinden de ulaşabileceğiniz bir çok kaynak mevcut. Bunları inceleyerek algoritmayı çalışma sistematiğini anlamaya çalışmanızı öneririm. Gerçek hayat vakalarına bakılmasında da yarar olduğu kanısındayım. Böylece geldik bir makalemizin daha sonuna. Tekrardan görüşünceye dek hepinize mutlu günler dilerim.</p>2016-04-23T12:00:00+00:00algorithmsc#regular expressionnetwork routingdynamic programmingfloydWarshallbsenyurtUzun zamandır algoritmalar üzerinde çalışmadığımı fark ettim. İşlerin biraz olsun hafiflediği şu vakitlerde de bir tanesini inceleyeyim dedim. Derken kendimi Floyd-Warshall algoritmasını anlamaya çalışırken buldum. Söz konusu algoritma Graph yapılarında boğumlar arasındaki en kısa yolların bulunmasında kullanılmaktadır.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=f8870eeb-fa47-4636-9618-04b3f4bf9e5e4https://buraksenyurt.com/trackback.axd?id=f8870eeb-fa47-4636-9618-04b3f4bf9e5ehttps://buraksenyurt.com/post/floyd-warshall-algoritmasi-ile-en-kisa-yolu-bulmak#commenthttps://buraksenyurt.com/syndication.axd?post=f8870eeb-fa47-4636-9618-04b3f4bf9e5ehttps://buraksenyurt.com/post/Decimal-to-Binary-to-HexadecimalDecimal to Binary to Hexadecimal2014-12-21T17:00:00+00:00bsenyurt<p><a href="https://buraksenyurt.com/pics/Pierre_de_Fermat_Pul.jpg"><img style="display: inline; margin-left: 0px; margin-right: 0px;" title="Pierre_de_Fermat_Pul" src="/pics/Pierre_de_Fermat_Pul_thumb.jpg" alt="Pierre_de_Fermat_Pul" width="320" height="196" align="right" /></a> Merhaba Arkadaşlar,</p>
<p><span style="font-style: italic; color: #ff0000;">[İlk Draft Tarihi : 2012-08-01]</span></p>
<p>Bundan bir kaç sene önce ünlü matematikçi <strong>Fermat’</strong> nın son teoreminin nasıl ispat edildiğinin anlatıldığı bir kitabı okumuştum. 1670 yılında ortaya çıkan ve Fermat tarafından o zaman ispat edildiği öne sürülen ama bildiğim kadarı ile kanıt bulunamayan teorem ancak <strong>1995</strong> yılında <strong>Andrew Wiles</strong> tarafından kanıtlanabilmiştir. </p>
<p>Söz konusu teoremin ispatı sırasında(<a href="http://tr.wikipedia.org/wiki/Fermat%27n%C4%B1n_son_teoremi" target="_blank">bununla ilişkili olarak wikiden bilgi alabilirsiniz</a>) arada ispat edilmek zorunda kalınan başka teoremler de ortaya çıkmıştı. Kitabın içerisinde altın orandan tutunda, <strong>Şimuya-Taniyama konjöktörünün</strong> çözümlenmesine kadar pek çok konuya yer verilmişti. Şimdi haklı olarak bunları niye söylüyorsun diyeceksiniz?</p>
<p>Görünen o ki evrenin hemen her alanında matematiğin izlerine rastlamaktayız. İşin gerçeği bildiğimiz tüm bilimler illaki bir ucundan da olsa matematiğe bulaşmak zorunda kalmıştır/kalmaktadır/kalacaktır. Söz gelimi bilgisayar bilimlerini göz önüne alalım. Bilgisayar bilimleri deyince işin içerisine elektronikten tutunda yazılıma kadar geniş bir alan girmektedir. Hatta kapalı ve açık devre ile başlayan ampüllerin zaman içerisinde <strong>1</strong> ve<strong> 0’</strong> lar olarak anıldığı ve karşımıza anlamlı, işlenebilir veri olarak çıktığı bir durum da söz konusudur.</p>
<p><strong>1 </strong>ve <strong>0</strong>’ lar dediğimiz de ise çok basit olarak matematikteki sayı sistemlerine değinmemiz kaçınılmazdır. <strong>İkili(Binary)</strong> sayı sistemi aslına bakıldığında makinanın anlayabileceği tek kavram olarak görünmektedir. Sonuç itibariyle devrelerin çalıştığı sinyaller göz önüne alındığında <strong>open</strong> ve <strong>close</strong> durumlarının oluşması gerekir. Makinenin dip noktasından daha yukarılara doğru çıktığımızda ise karşımıza <strong>ondalık(decimal), sekizli(octal)</strong> ve hatta <strong>16lık(Hexadecimal)</strong> sayı sistemleri çıkmaktadır. Bu sayı sistemleri arasında belirgin farklılıklar vardır elbette. Her şey <strong>byte</strong> seviyesinde düşünüldüğünde<strong> 8bitlik 1ler</strong> ve <strong>0lar</strong> dizisine dönüşüyor olsa da, verilerin saklanması gerektiği durumlarda diğer sayı sistemleri ve özellikle <strong>hexadecimal</strong> yapı oldukça ön plana çıkabilmektedir.</p>
<p>İlk olarak biraz matematik diyeceğiz ve <strong>binary</strong>, <strong>decimal</strong> ile <strong>hexadecimal</strong> sayı sistemlerini göz önüne alıyor olacağız. Aşağıdaki şekilde çok basit olarak bu sayı sistemlerindeki temel değerlerin karşılıkları gösterilmektedir.</p>
<p><a href="https://buraksenyurt.com/pics/decbinhex.png"><img style="display: inline;" title="decbinhex" src="/pics/decbinhex_thumb.png" alt="decbinhex" width="521" height="560" /></a></p>
<p>Bilindiği üzere <strong>decimal</strong> sayılar <strong>0dan 9a</strong> kadardır. <strong>Binary</strong> sayıların sadece <strong>1 </strong>ve <strong>0</strong> olduğunu biliyoruz. Diğer yandan <strong>Hexadecimal</strong> sayılar <strong>0dan 9a kadar</strong> decimal sayılar şeklinde iken sonrasında <strong>A,B,C,D,E </strong>ve <strong>F </strong>olarak devam etmektedirler. Özellikle bir ondalıklı sayının ikili düzendeki ifadesine baktığımızda hane sayısı oldukça fazla olan rakam dizileri ile karşılaşmamız normaldir. Ancak hexadecimal düzene baktığımızda ise ondalıklı sayılara göre daha az haneden oluşan diziler söz konusu olmaktadır. Söz gelimi <strong>100000000</strong>, <strong>9 hanelidir</strong> ve binary karşılığı <strong>27 rakamdan</strong> oluşmaktadır. Oysaki bu sayının <strong>hexadecimal</strong> karşılığı <strong>7</strong> hanedir. Hiç yoktan 2 hane 2 hanedir. Bir kum tanesi olarak düşünüldüğünde bir anlam ifade etmeyebilir ama bir kamyon dolusu kum düşünüldüğün daha büyük bir kazançta sağlayabilir <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /></p>
<blockquote>
<p>Tabi burada hane sayısının azalmasının veya fazla olmasının, makine seviyesinde bakıldığında bir anlam ifade etmediğini vurgulamamız gerekiyor. Nitekim makine seviyesinde herşey mutlak suretle 1 ve 0 olarak ifade edilmek durumundadır.</p>
</blockquote>
<p>Peki matematiksel olarak bu sayı sistemleri arasındaki dönüşümler nasıl yapılabilir? Özellikle ondalıklı sistemdeki sayıların ikili düzende ifade edilmesi veya hexadecimal’ e çevrilmesi nasıl gerçekleştirilmektedir?</p>
<p>Burada olayı biraz kağıt kalem kullanarak ve basit bölme ve üst alma işlemleri yaparak ele almamız gerekmektedir. Örneğin <strong>78</strong> sayısının <strong>ikili</strong> düzendeki karşılığını bulalım ve ters dönüşümünü de sağlayalım. İşte örnek çalışma;</p>
<p><a href="https://buraksenyurt.com/pics/WP_000153.jpg"><img style="display: inline;" title="WP_000153" src="/pics/WP_000153_thumb.jpg" alt="WP_000153" width="319" height="405" /></a> </p>
<p>Yazımın kötü olmasından dolayı gerçekten çok üzgünüm. Dikkat edileceği üzere ikili sisteme dönüştürme işlemi için <strong>sayının sürekli olarak 2’ye</strong> <strong>bölünmesi</strong> <strong>ve kalan 1 ve 0 ların</strong> <strong>ters sırada birleştirilmesi</strong> söz konusudur. İkili sayı sisteminde ifade edilen rakamların, ondalık sisteme dönüştürülmesinde ise, <strong>2üzeri0 dan başlayaraktan 2nin katları ile 1 ve 0ların çarpımı sonucu elde edilen ifadelerin toplanması </strong>söz konusudur.</p>
<p>Peki <strong>78</strong> sayısının <strong>hexadecimal</strong> karşılığı nasıl bulunabilir? ve tabi <strong>hexadecimal</strong> bir sayının <strong>ondalık</strong> sistemdeki karşılığı nasıl hesaplanır? Yine kağıt kaleme sarılırsak işlemin çok daha basit olduğunu görebiliriz.</p>
<p><a href="https://buraksenyurt.com/pics/WP_000155.jpg"><img style="display: inline;" title="WP_000155" src="/pics/WP_000155_thumb.jpg" alt="WP_000155" width="320" height="440" /></a> </p>
<p>Görüldüğü üzere bir ondalıklı sayının ikili sisteme dönüştürülmesindeki felsefenin aynısı burada da geçerlidir. Tek yapılması gereken 16ya bölme ve kalanları değerlendirmedir. Tabi kalanarın 1 ve 0 değil, <strong>0 ile 15 aralığında olması</strong> önemlidir. <strong>9dan sonraki rakamlarda(10,11,12,13,14,15) sırasıyla A,B,C,D,E ve F harflerine</strong> yer verilmektedir. Bir <strong>hexadecimal</strong> ifadenin ondalıklı sayıya çevrilmesinde ise <strong>16üzeri0</strong> ile başlayan katlı sistem devreye girer. İlgili katlar sayının veya harfin karşılık geldiği<em>(örneğin Enin karşılığı olan 12)</em> değer ile çarpılır ve genel toplam alınarak ondalık sayı karşılığı bulunur.</p>
<p>Teorem bu kadar basit olduğuna göre bir sayının ikili veya 16lı sayı sistemine çevrilmesi için gerekli kodları geliştirebilirsiniz. Bu iyi bir antrenman olacaktır <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /> Ama çok da şart değildir. Nitekim <strong>Convert</strong> tipinin ilgili <strong>static</strong> metodları <strong>base</strong> parametresi ile ilgili dönüşümlere izin vermektedir. Aşağıdaki örnek kod parçasını bu anlamda göz önüne alabiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
namespace NumberSystems
{
class Program
{
static void Main(string[] args)
{
int number1 = 78;
string number1Binary = Convert.ToString(number1, 2);
string number1Hexadecimal = Convert.ToString(number1, 16);
Console.WriteLine("Decimal to Binary/Hexadecimal\n{0}\t=\t{1}\n{2}\t=\t{3}\n"
,number1
,number1Binary
,number1
,number1Hexadecimal
);
int number2 = Convert.ToInt32(number1Binary, 2);
int number3 = Convert.ToInt32(number1Hexadecimal, 16);
Console.WriteLine("Binary/Hexadecimal to Decimal\n{0}\t=\t{1}\n{2}\t=\t{3}\n"
, number1Binary
, number2
, number1Hexadecimal
, number3
);
}
}
}</pre>
<p>Convert tipinin static <strong>ToString</strong> ve <strong>ToInt32</strong> metodlarına verilen ikinci parametrelere dikkat edelim. Bu parametreler ile sayısal taban belirtilmektedir. <strong>Binary</strong> düzen için <strong>2</strong>, <strong>Hexadecimal</strong> düzen için ise <strong>16</strong>. Kodun çalışma zamanı çıktısı ise aşağıdaki gibi olacaktır.</p>
<p><a href="https://buraksenyurt.com/pics/decbinhex2.png"><img style="display: inline;" title="decbinhex2" src="/pics/decbinhex2_thumb.png" alt="decbinhex2" width="231" height="140" /></a> </p>
<p>Şimdi olayı biraz daha ilginç bir hale getirelim ne dersiniz? Önce örnek kodumuz…</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace NumberSystems
{
class Program
{
static void Main(string[] args)
{
string fileDecimal = Path.Combine(Environment.CurrentDirectory, "Decimal.txt");
string fileBinary = Path.Combine(Environment.CurrentDirectory, "Binary.txt");
string fileHexadecimal = Path.Combine(Environment.CurrentDirectory, "Hexadecimal.txt");
List<int> numbers = GetRandomNumbers(100000000, 900000000, 1000000);
WriteToFile(fileDecimal, numbers, BaseType.Decimal);
WriteToFile(fileBinary, numbers, BaseType.Binary);
WriteToFile(fileHexadecimal, numbers, BaseType.Hexadecimal);
}
private static List<int> GetRandomNumbers(int initialValue, int lastValue, int arrayLength)
{
List<int> numbers = new List<int>();
Random random = new Random();
for (int i = 0; i < arrayLength; i++)
{
numbers.Add(random.Next(initialValue, lastValue));
}
return numbers;
}
private static void WriteToFile(string fileName, List<int> numbers, BaseType baseType)
{
StringBuilder builder = new StringBuilder();
for (int i = 0; i < numbers.Count; i++)
{
builder.AppendLine(Convert.ToString(numbers[i], (int)baseType));
}
File.WriteAllText(fileName, builder.ToString());
}
}
public enum BaseType
{
Binary = 2,
Decimal = 10,
Hexadecimal = 16
}
}</pre>
<p>Öncelikle bu kod parçasında ne yaptığımıza bir bakalım.</p>
<p><strong>GetRandomNumbers</strong> isimli metodumuz belirtilen <strong>integer</strong> değer aralığında bizim belirttiğimiz sayıda rastege sayı üretmekte ve bunları generic bir <strong>List<int></strong> koleksiyonu içerisinde geriye döndürmektedir. <strong>WriteToFile</strong> isimli metodumuz ise bu rastgele sayı listesini alıp fiziki bir text dosyasına kayıt etmektedir. <strong>WriteToFile</strong> metodunun üçüncü parametresi <strong>BaseType</strong> <strong>enum</strong> sabiti tipindendir. Bu sabite dikkat edecek olursak<strong> Binary, Decimal</strong> ve <strong>Hexadecimal </strong>sayı tabanı sistemlerini işaret edecek şekilde oluşturulmuştur. İlgili <strong>Enum </strong>sabitinin sayısal değeri, <strong>Convert.ToString </strong>metodunun ikinci parametresi olarak kullanılmaktadır. <strong>Main </strong>metodu içerisinde yazdığımız test kodları, ondalıklı sayıların <strong>decimal, binary </strong>ve <strong>hexadecimal </strong>düzende tutulduğu <strong>text </strong>dosyalarının üretimini üstlenmektedir. Kodun yazılış biçiminden ziyade, kullanılan senaryo gereği üretilen dosya boyutlarının ne olduğu daha çok önemlidir. İşte bu denemenin sonuçları.</p>
<p><a href="https://buraksenyurt.com/pics/decbinhex3.png"><img style="display: inline;" title="decbinhex3" src="/pics/decbinhex3_thumb.png" alt="decbinhex3" width="385" height="138" /></a></p>
<p>Mutlaka dikkatinizi çekmiştir ki, <strong>Binary</strong> dosya boyutu <strong>30</strong> megabyte ile haklı bir liderliği üstlenmektedir <img title="Smile" src="/editors/tiny_mce3/plugins/emotions/img/smiley-smile.gif" alt="Smile" border="0" /> Her ne kadar <strong>Decimal</strong> ile <strong>Hexadecimal</strong> arasında çok büyük bir fark olmadığı gözüksede, sayı dizisinin boyutunun arttırılması halinde durum biraz daha farklılık gösterebilmektedir. Bu amaçla test sonuçlarını biraz daha sağlıklı irdelemek adına kodumuzu biraz daha değiştirelim.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Text;
namespace NumberSystems
{
class Program
{
static void Main(string[] args)
{
string fileDecimal = Path.Combine(Environment.CurrentDirectory, "Decimal.txt");
string fileBinary = Path.Combine(Environment.CurrentDirectory, "Binary.txt");
string fileHexadecimal = Path.Combine(Environment.CurrentDirectory, "Hexadecimal.txt");
for (int i = 5; i < 9; i++)
{
int length = (int)Math.Pow(10, i);
Console.WriteLine(length);
List<int> numbers = GetRandomNumbers(10000000, 90000000, length);
WriteToFile(fileDecimal, numbers, BaseType.Decimal);
WriteToFile(fileBinary, numbers, BaseType.Binary);
WriteToFile(fileHexadecimal, numbers, BaseType.Hexadecimal);
Console.WriteLine("---");
}
}
private static List<int> GetRandomNumbers(int initialValue, int lastValue, int arrayLength)
{
List<int> numbers = new List<int>();
Random random = new Random();
for (int i = 0; i < arrayLength; i++)
{
numbers.Add(random.Next(initialValue, lastValue));
}
return numbers;
}
private static void WriteToFile(string fileName, List<int> numbers, BaseType baseType)
{
StringBuilder builder = new StringBuilder();
Stopwatch watcher = new Stopwatch();
for (int i = 0; i < numbers.Count; i++)
{
builder.AppendLine(Convert.ToString(numbers[i], (int)baseType));
}
watcher.Start();
File.WriteAllText(fileName, builder.ToString());
watcher.Stop();
FileInfo fi=new FileInfo(fileName);
Console.WriteLine(
"{0}\tSize:{1}\tProcess Time:{2}"
,Path.GetFileName(fileName)
,fi.Length.ToString()
,watcher.ElapsedMilliseconds.ToString()
);
}
}
public enum BaseType
{
Binary = 2,
Decimal = 10,
Hexadecimal = 16
}
}</pre>
<p>Bu sefer 10un katları şeklinde arka arkaya denemeler yapıyoruz. Her denemede <strong>binary</strong>, <strong>decimal</strong> ve <strong>hexadecimal</strong> dosyalardan birer tane üretmekteyiz. Sonuçları daha sağlıklı irdelemek adınaysa ekrana üretilen dosyanın adını, boyutunu, test için kullanılan eleman sayısını ve son olarakta yazma işlemi sırasında geçen süreleri çıkartmaktayız. Her test sırasında farklı sayılar ile çalışılıyor olasa teste tabi tutulan eleman sayısı belirleyici kriter olduğundan bu durumu göz ardı edebiliriz. Uygulamanın çalışma zamanındaki çıktısı aşağıdaki gibi olacaktır.</p>
<p><a href="https://buraksenyurt.com/pics/decbinhex6.png"><img style="display: inline;" title="decbinhex6" src="/pics/decbinhex6_thumb.png" alt="decbinhex6" width="313" height="240" /></a></p>
<p>Tabi söz konusu istatistikleri Excel üzerine grafik haline getirdiğimizde durumu biraz daha net bir biçimde analiz edebiliriz. İlk olarak üretilen dosya boyutlarına bir bakalım.</p>
<p><a href="https://buraksenyurt.com/pics/decbinhex7.png"><img style="display: inline;" title="decbinhex7" src="/pics/decbinhex7_thumb.png" alt="decbinhex7" width="503" height="481" /></a> </p>
<p>İlk başlarda çok fazla fark görülmüyor olsa da, eleman sayısının çok daha fazlalaştırılması halinde özellikle binary düzende saklanan veri kümesinin toplam boyutunun belirgin ölçüde yükseldiği gözlenmekte. Dosyalara yazma sürelerine ait istatistikler de aşağıdaki gibi özetlenebilir.</p>
<p><a href="https://buraksenyurt.com/pics/decbinhex8.png"><img style="display: inline;" title="decbinhex8" src="/pics/decbinhex8_thumb.png" alt="decbinhex8" width="503" height="467" /></a></p>
<p>Aslında en hızlı üretim biçimi decimal içerikli dosyalarda söz konusudur. Ancak hız ve boyut kriterlerine baktığımızda Hexadecimal olarak veriyi saklamanın daha uygun olduğu sonucuna varılabilir. Tabi şu durum da gözden kaçırılmamlıdır. <strong>Decimal </strong>içerikleri <strong>Hexadecimal </strong>olarak saklamak ve bu saklanan içeriği tekrardan <strong>decimal </strong>olarak göstermek istediğimizde yazma ve okuma işlemleri yapılması gerektiği ve bunlar için uygulamaya ek süreler yükleneceği de ortadadır. Yine de bazı bilimsel ve matematiksel uygulamalarda, çok büyük boyutlu decimal içeriklerin fiziki olarak saklanması gerektiği durumda Hexadecimal çevirmeler düşünülebilir. Böylece geldik bir yazımızın daha sonuna. Tekrardan görüşünceye dek hepinize mutlu günler dilerim.</p>
<p><a href="https://buraksenyurt.com/pics/2012%2f2%2fNumberSystems.zip">NumberSystems.zip (25,96 kb)</a></p>2014-12-21T17:00:00+00:00c#sayı sistemleribinaryhexadecimaloctaldecimalconvertbsenyurtGörünen o ki evrenin hemen her alanında matematiğin izlerine rastlamaktayız. İşin gerçeği bildiğimiz tüm bilimler illaki bir ucundan da olsa matematiğe bulaşmak zorunda kalmıştır/kalmaktadır/kalacaktır. Söz gelimi bilgisayar bilimlerini göz önüne alalım. Bilgisayar bilimleri deyince işin içerisine elektronikten tutunda yazılıma kadar geniş bir alan girmektedir. Hatta kapalı ve açık devre ile başlayan ampüllerin zaman içerisinde 1 ve 0’ lar olarak anıldığı ve karşımıza anlamlı, işlenebilir veri olarak çıktığı bir durum da söz konusudur.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=f4e70a82-9d65-4243-a585-b1faf6d1df946https://buraksenyurt.com/trackback.axd?id=f4e70a82-9d65-4243-a585-b1faf6d1df94https://buraksenyurt.com/post/Decimal-to-Binary-to-Hexadecimal#commenthttps://buraksenyurt.com/syndication.axd?post=f4e70a82-9d65-4243-a585-b1faf6d1df94https://buraksenyurt.com/post/Recursive-Fibonacci-Neden-YavasRecursive Fibonacci Neden Yavaş?2013-06-07T00:40:00+00:00bsenyurt<p>Merhaba Arkadaşlar,</p>
<p>Okulda<strong> “Algoritma ve Veri Yapıları”</strong> dersinde ya da <strong>C#</strong> benzeri nesne yönelimli<em>(Object Oriented)</em> bir dili öğrenmeye başladığımız ilk zamanlarda, karşımıza muhakkak <strong>Recursive</strong> fonksiyonlar çıkmıştır<em>(Çıkmaya da devam edecektir)</em>. Hatta en meşhur olanları da, bir sayının <strong>faktöryelinin</strong> <strong>(6!=6x5x4x3x2x1=720 ve 0!=1)</strong> bulunması veya <strong>Fibonacci</strong> sayı dizisinin<strong>(0,1,1,2,3,5,8,13,21,34…, Fn=(Fn-1(+(Fn-2))</strong> ardışıl olarak ekrana yazdırılmasıdır.</p>
<p><strong>Recursive</strong> fonksiyonları ilk etapta anlamakta güçlük çeksek de, matematik ile bağdaşdırmakta zorlansak da, pek çok noktada hayat kurtaran ve gerekli olan metodlar olduklarını biliriz. Örneğin strateji oyunlarında, ikili<em>(Binary) </em>ağaç aramalarında, doğal dil işleme metodolojilerinde, <strong>Hanoi</strong> kuleleri gibi popüler problemlerin çözümünde ve daha pek çok yerde <strong>Recursive</strong> fonksiyonellikler söz konusudur.</p>
<p>&<iframe src="https://www.youtube.com/embed/aiCwI8pGLs8" width="560" height="315" frameborder="0" allowfullscreen="allowfullscreen"></iframe></p>
<p>Biz bu görsel dersimizde, <strong>Fibonacci</strong> sayı dizisinin <strong>Recursive</strong> fonksiyonlar ile elde edilmesi halinde sistemin neden ve nasıl yavaşladığını anlamaya çalıştık. Ardından da iteratif bir yaklaşım üzerinde durarak basit bir çıkarımda bulunduk.</p>
<p>Faydalı olması dileğiyle <img class="wlEmoticon wlEmoticon-winkingsmile" style="border-style: none;" src="http://www.buraksenyurt.com/pics/wlEmoticon-winkingsmile_206.png" alt="Winking smile" /></p>2013-06-07T00:40:00+00:00recursiverecursive functionsözyinelemeli fonksiyonlarfibonaccifactorialtree viewiterationperformancemathmathematicalgorithmsalgoritmahanoi towersc# temelleribsenyurtOkulda “Algoritma ve Veri Yapıları” dersinde ya da C# benzeri nesne yönelimli(Object Oriented) bir dili öğrenmeye başladığımız ilk zamanlarda, karşımıza muhakkak Recursive fonksiyonlar çıkmıştır(Çıkmaya da devam edecektir). Hatta en meşhur olanları da, bir sayının faktöryelinin (6!=6x5x4x3x2x1=720 ve 0!=1) bulunması veya Fibonacci sayı dizisinin(0,1,1,2,3,5,8,13,21,34…, Fn=(Fn-1(+(Fn-2)) ardışıl olarak ekrana yazdırılmasıdır.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=47d8db7f-d797-4895-b5a4-28cef41581283https://buraksenyurt.com/trackback.axd?id=47d8db7f-d797-4895-b5a4-28cef4158128https://buraksenyurt.com/post/Recursive-Fibonacci-Neden-Yavas#commenthttps://buraksenyurt.com/syndication.axd?post=47d8db7f-d797-4895-b5a4-28cef4158128https://buraksenyurt.com/post/Levenshtein-Distance-AlgoritmasiLevenshtein Distance Algoritması2012-07-01T23:05:00+00:00bsenyurt<p><a href="https://buraksenyurt.com/pics/artcl_11_4.jpg"><img style="margin: 4px 0px; display: inline; float: right;" title="artcl_11_4" src="/pics/artcl_11_4_thumb.jpg" alt="artcl_11_4" width="300" height="199" align="right" /></a>Merhaba Arkadaşlar,</p>
<p>Bir süredir yazılım dünyasında sıklıkla kullanılan basit algoritmalara merak salmış durumdayım. Bazıları kafayı yedirtecek cinsten olsalarda arada sırada bunları değerlendirmekte ve paslanan dimamızı açmaya çalışmakta yarar olduğu kanısındayım.</p>
<p>Aslına bakarsanız bilgisayar bilimlerinde uygulanabilen, gerçekten çok işe yarayan ve onları keşfedenleri saygıyla hatırlamamız gereken algoritmalar mevcut. Örneğin bunlardan birisi olan <a href="http://en.wikipedia.org/wiki/Vladimir_Levenshtein">Levenshtein Distance</a> algoritması ve mucidi <strong>Vladimir Levenshtein</strong> <img class="wlEmoticon wlEmoticon-winkingsmile" style="border-style: none;" src="/pics/wlEmoticon-winkingsmile_79.png" alt="Winking smile" /></p>
<p>Bu algoritma bizlere, özellikle arama motorlarında da kullanılabilen bir model sunmaktadır. Son kullanıcıların aradıkları kelimeleri tam olarak belirleyemedikleri veya kestiremedikleri durumlarda, öneri olarak sunulan kelimelerin tespit edilmesi sırasında ele alınan bir algoritmadır. Örneğin ben <strong>Google</strong> sitesindeki arama kutucuğunda kendi ismimi eksik karakterler ile yazdığımda, <strong>google</strong> daha önceden yapmış olduğu indekslenmiş içeriklere göre bir öneri de bulunmuştur<em>(Bunu mu demek istediniz kısmı)</em> Aşağıdaki şekilde bu durum açık bir şekilde görülmektedir.</p>
<p><a href="https://buraksenyurt.com/pics/artcl_11_1.png"><img style="background-image: none; margin: 4px 0px; padding-left: 0px; padding-right: 0px; display: inline; padding-top: 0px; border: 0px;" title="artcl_11_1" src="/pics/artcl_11_1_thumb.png" alt="artcl_11_1" width="375" height="190" border="0" /></a></p>
<p>Arama motorları dışında, özellikle imla kontrolü yapan uygulamalarda da<em>(Söz gelimi <strong>Microsoft Outlook</strong> veya <strong>Microsoft Word’</strong> ün <strong>Spell Checking</strong> mekanizmalarında)</em> bu algoritmanın kullanımına sıklıkla şahit olmaktayız.</p>
<p>Biz bu yazımızda söz konusu algoritmanın kullanılması için gerekli olan temel fonksiyonu, sıklıkla yaptığımız üzere bir <strong>Extension Method</strong> olarak geliştirmeye ve test etmeye çalışıyor olacağız. Ancak kodlama kısmına geçmeden önce algoritmanın nasıl çalıştığına ve işlediğine bakmamızda yarar olacağı kanısındayım.</p>
<p>Aslında algoritma temel olarak iki kelimenin birbirlerine olan benzerliklerini ölçümlemek amacıyla kullanılmaktadır. Sonuç tek bir sayısal değerdir ve iki kelimeden birinin diğerine dönüştürülebilmesi için gerekli olan işlem sayısını ya da maliyetini vermektedir. Çok doğal olarak bu sayınının düşük olması arzu edilen neticedir. Nitekim daha az değişiklik anlamına gelmektedir. Çok doğal olarak bir kelimenin, bir öneri kelime kümesi içerisindekiler ile karşılaştırılması sonucu ortaya çıkan sayısal değerlerden en küçüğü veya küçükleri, sonuca ulaşılması ve doğru önerilerde bulunulması açısından önemlidir.</p>
<p>Peki bu yakınlık değeri nasıl hesaplanmaktadır? <img class="wlEmoticon wlEmoticon-smile" style="border-style: none;" src="/pics/wlEmoticon-smile_27.png" alt="Smile" /> Bunun için kelimeler arası iki boyutlu bir matris dizisi kullanılır. Lakin söz konusu matrisin içereceği değerlerin tespiti çok da kolay değildir. Dilerseniz aşağıdaki Excel görüntüsünde yer alan örneklemelere bir bakalım ve algoritmayı daha yakından tanımaya çalışalım.</p>
<p><a href="https://buraksenyurt.com/pics/artcl_11_3.png"><img style="background-image: none; margin: 4px 0px; padding-left: 0px; padding-right: 0px; display: inline; padding-top: 0px; border: 0px;" title="artcl_11_3" src="/pics/artcl_11_3_thumb.png" alt="artcl_11_3" width="536" height="464" border="0" /></a></p>
<p>Bu grafikte, 5 farklı örnek ile 10 kelimenin birbirleri ile yakınlıklarının<strong> Levensthein Distance</strong> algoritmasına göre nasıl hesap edildiği gösterilmektedir. İlk olarak <strong>rest</strong> kelimesinin <strong>test</strong> kelimesi ile olan yakınlığı bulunmaya çalışılmıştır. Aslına bakarsanız bu iki kelime arasında sadece<strong> 1 işlem</strong> yaparak sonuca ulaşılabilir. Bu işleme göre <strong>rest kelimesindeki r harfi yerine, t harfinin gelmesi</strong> yeterlidir. Matris içerisinde yer alan sayılar o andaki sütuna veya satıra kadar olan harf topluluklarının birbirleri ile eş düşmeleri için gerekli işlem sayılarını içermektedir.</p>
<p>Şimdi de <strong>google</strong> ve <strong>yahoo!</strong> kelimelerinin yakınlık hesabını göz önüne alalım. Normal şartlarda iki kelime içerisinde ortak olan<strong> 2 “o”</strong> harfi bulunmaktadır ancak yerleri farklıdır. Diğer harfler ise zaten birbirlerinde yoktur. Bu nedenle<strong> 6 işlemlik bir operasyon yapılması</strong> gerekmektedir.</p>
<p>Peki sayılar tam olarak nasıl yerleştirilmekte veya okunmaktadırlar? Hemen <strong>Samantha</strong> ile <strong>Sam’</strong> in karşılaştırılmasını ele alalım. Şimdi <strong>0 indisli</strong> olacak şekilde <strong>1nci sütun</strong> ve <strong>1inci satırı</strong> göz önüne alalım. 1nci sütunda <strong>“s”</strong> harfi ve 1nci satırda yine <strong>“s”</strong> harfi bulunmaktadır. Dolayısıyla o anki karşılaştırmada, her iki harfte aynı olduğunda bir işlem yapılmasına gerek yoktur. Dolayısıyla <strong>işlem maliyeti 0dır</strong>. Şimdi <strong>2ncü sütuna</strong> ve<strong> 1nci satıra</strong> bakalım. 2nci sütuna kadar olan kısımda <strong>“sa“</strong> hecesi oluşmuştur. Satır tarafında ise sadece <strong>“s” </strong>harfi bulunmaktadır. Dolayısıyla eşleştirme için satır kısmındaki <strong>“s”</strong> harfine bir de <strong>“a”</strong> harfinin eklenmiş olması gerekir. Ki bu da <strong>1 işlem maliyeti</strong> olarak ifade edilmektedir.</p>
<p>Durumu biraz daha öteleyelim. 5 numaralı örnekte yer alan <strong>puzzle</strong> ve <strong>pzzel</strong> kelimelerinin karşılaştırılmasında <strong>5nci sütun</strong> ve <strong>4ncü satıra</strong> bakalım. 5nci sütuna kadar <strong>puzz</strong> kelimesi 4ncü satıra kadar da <strong>pzz</strong> kelimesi söz konusudur.<strong>pzz</strong>’ un <strong>puzz</strong> kelimesine benzemesi için araya bir <strong>“u”</strong> harfinin konulması yeterlidir. Diğer kısımlar satır ve sütun bazında da eşleşmektedir. Bu yüzden buradaki <strong>işlem maliyeti değeri 1</strong> dir. Ancak yine 0 indisli baktığımızda ve <strong>7nci sütun</strong> ve<strong> 6ncı satıra</strong> kadar olan kısımda <strong>puzzle</strong> ve <strong>pzzel</strong> kelimeleri göz önüne alındığında ise; pzzel’ dan puzzle’a geçmek istenildiğinde ilk olarak araya bir<strong> “u”</strong> harfi konulur.</p>
<p>p<strong><sup>u</sup></strong>zzel</p>
<p>Ardından <strong>“el” </strong>hecesinde<strong> e’ nin l yerine, l’ nin e yerine</strong> geçmesi gerekir.</p>
<p>p<strong><sup>u</sup></strong>zz<strong><sup>le</sup></strong></p>
<p>Dolayısıyla toplamda <strong>3 işlem maliyeti</strong> söz konusu olmuştur.</p>
<p>Bu algoritma gereği iki kelime arasındaki yakınlık derecesi, matrisin sağ alt hücresindeki sayısal değer ile ifade edilmektedir. Buna göre <strong>puzzle</strong> ile <strong>pzzel</strong> kelimeleri arasındaki mesafe <strong>3 işlem</strong> <strong>operayonu </strong>ile ölçülürken, bu <strong>Samantha</strong> ve <strong>Sam</strong> kelimeleri arasında <strong>5</strong> işlemlik bir maliyet oluşması söz konusudur<em>(Samantha’ dan <strong>antha</strong> kısmının atılması nedeni ile 5 işlemlik bir maliyet oluşmaktadır)</em></p>
<p>Algoritmayı biraz kavradığımıza göre dilerseniz bunu <strong>C#</strong> tarafında bir <strong>Extension</strong> <strong>Method</strong> içerisine dahil edelim ve test uygulamamıza çıkalım. Bu amaçla aşağıdaki örnek Console uygulamasını göz önüne alabiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
namespace UsingLevenshtein
{
class Program
{
static void Main(string[] args)
{
TestMethod("rest", "test");
TestMethod("google", "yahoo!");
TestMethod("mike", "mayk");
TestMethod("samantha", "sam");
TestMethod("puzzle", "pzzel");
}
private static void TestMethod(string Source,string Target)
{
int[,] matrix3 = new int[Source.Length, Target.Length];
int distance3 = Source.FindLevenshteinDistance(Target, out matrix3);
Console.WriteLine("{0} vs {1}\nDistance : {2}\n",Source,Target, distance3);
WriteToConsole(matrix3);
}
static void WriteToConsole(int[,] Matrix)
{
for (int i = 0; i < Matrix.GetLength(0); i++)
{
for (int j = 0; j < Matrix.GetLength(1); j++)
{
Console.Write("\t{0} ", Matrix[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}
}
public static class StringExtensions
{
// Genişletme metodu, karşılaştırma matrisini de out parametresi olarak döndürmektedir.
public static int FindLevenshteinDistance(this string Source, string Target,out int[,] Matrix)
{
int n = Source.Length;
int m = Target.Length;
Matrix = new int[n + 1, m + 1]; // Hesaplama matrisi üretilir. 2 boyutlu matrisin boyut uzunlukları ise kaynak ve hedef metinlerin karakter uzunluklarına göre set edilir
if (n == 0) // Eğer kaynak metin yoksa zaten hedef metnin tüm harflerinin değişimi söz konusu olduğundan, hedef metnin uzunluğu kadar bir yakınlık değeri mümkün olabilir
return m;
if (m == 0) // Yukarıdaki durum hedefin karakter içermemesi halinde de geçerlidir
return n;
// Aşağıdaki iki döngü ile yatay ve düşey eksenlerdeki standart 0,1,2,3,4...n elemanları doldurulur
for (int i = 0; i <= n;i++)
Matrix[i, 0] = i;
for (int j = 0; j <= m; j++)
Matrix[0, j] = j;
// Kıyaslama ve derecelendirme operasyonu yapılır
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
int cost = (Target[j - 1] == Source[i - 1]) ? 0 : 1;
Matrix[i, j] = Math.Min(Math.Min(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1), Matrix[i - 1, j - 1] + cost);
}
return Matrix[n, m]; // sağ alt taraftaki hücre değeri döndürülür
}
}
}</pre>
<p>Uygulamamız içerisinde dikkat edeceğiniz üzere <strong>Excel</strong> tablosunda yer alan kelimelere ait bir test işlemi gerçekleştirilmektedir.<strong>FindLevenshteinDistance </strong>isimli metodumuz bir genişletme fonksiyonu olarak herhangibir <strong>string</strong> tipine uygulanabilecek şekilde tasarlanmıştır. Bununla birlikte söz konusu metod hem <strong>Levenshtein</strong> <strong>Distance</strong> matrisini, hemde yakınlık derecesini döndürmektedir. Uygulama içerisinde kelimeler arası testi kolaylaştırmak adına <strong>TestMethod</strong> isimli bir fonksiyon da ele alınmıştır. Programın çalışma zamanındaki çıktısı ise aşağıdaki gibi olacaktır.</p>
<p><a href="https://buraksenyurt.com/pics/artcl_11_2.png"><img style="background-image: none; margin: 4px 0px; padding-left: 0px; padding-right: 0px; display: inline; padding-top: 0px; border: 0px;" title="artcl_11_2" src="/pics/artcl_11_2_thumb.png" alt="artcl_11_2" width="459" height="759" border="0" /></a></p>
<p>Artık bundan sonrasında yapılması gereken, bir text kutucuğuna girilen metni, bir metin kümesi içerisinde söz konusu algoritmaya göre aramak ve yakınlık derecesi, bir başka deyişle operasyon işlem maliyeti en düşük olan kelime veya kelimeleri kullanıcıya sunmaya çalışmaktan ibarettir. Dilerseniz bu konuyu bir düşünün ve uygulamaya çalışın <img class="wlEmoticon wlEmoticon-winkingsmile" style="border-style: none;" src="/pics/wlEmoticon-winkingsmile_79.png" alt="Winking smile" /> Tekrardan görüşünceye dek hepinize mutlu günler dilerim.</p>
<p><a href="https://buraksenyurt.com/pics/2011%2f12%2fUsingLevenshtein.zip">UsingLevenshtein.zip (15,85 kb)</a></p>2012-07-01T23:05:00+00:00c#levenshtein distancealgoritmaextension methodsbsenyurtAslına bakarsanız bilgisayar bilimlerinde uygulanabilen, gerçekten çok işe yarayan ve onları keşfedenleri saygıyla hatırlamamız gereken algoritmalar mevcut. Örneğin bunlardan birisi olan Levenshtein Distance algoritması ve mucidi Vladimir Levenshtein Winking smile...https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=6fbdc82d-c361-4376-9046-d4ffecf83c6d4https://buraksenyurt.com/trackback.axd?id=6fbdc82d-c361-4376-9046-d4ffecf83c6dhttps://buraksenyurt.com/post/Levenshtein-Distance-Algoritmasi#commenthttps://buraksenyurt.com/syndication.axd?post=6fbdc82d-c361-4376-9046-d4ffecf83c6d