Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde, özellikle metin işlemenin yoğun olduğu, arama motoru gibi uygulamalarda dosyaların veya web sitelerinin birbirine olan benzerliğini bulmak için kullanılan bir algoritmadır.

Algoritmaya alternatif olarak klasik hash fonksiyonları kullanılabilir. Yani, örneğin iki sayfasnın ayrı ayrı hash değerleri alınıp bu değerleri karşılaştırmak mümkündür. Ancak simhash algoritması, bu yönteme göre daha fazla hız ve performans sunar.

Sim hash algoritması, iki dosyayı birer vektör olarak görür ve bu vektorler (yöney, vector) arasındaki cosinüs (cosine) bağlantısını bulmaya çalışır.

Yoneykosinus

Yukarıdaki şekilde temsil edildiği üzere iki dokümanın ayrı ayrı birere vektör olması durumunda, aralarında cos (x) olarak gösterilen bir açı ile bağlantı bulunması mümkündür.

Algoritma, öncelikle işlediği metindeki kelimelerin ağırlıklarını (weight) çıkarmakta ve buna göre kelimeleri sıralamaktadır.

Sıralanan her kelimeye, b uzunluğunda, yegane (unique) değer döndüren bir fonksiyon kullanılır. Örneğin her kelime için farklı bir hash sonucu döndüren fonksiyon kullanılır.

b boyutundaki bir vektörün ağırlık değeri hesaplanırken, her kelimedeki 1 değeri için +1 ve 0 değeri için -1 değeri ağırlığa eklenir.

Son olarak üretilen ağırlık vektöründeki + değerler 1, 0 ve – değerler ise 0 olarak çevirilir.

Örnek

Yukarıdaki algoritmanın çalışmasını bir örnek üzerinden anlatalım. Algoritmanın üzerinde çalışacağı metin aşağıdaki şekilde verilmiş olsun:

www bilgisayar kavramları com bilgisayar kavramlarının anlatıldığı bir bilgisayar sitesidir ve com uzantılıdır

Yukarıdaki bu metni, algoritmanın anlatılan adımlarına göre işleyelim:

İlk adımımız, algoritmadaki kelimelerini ağırlıklarının çıkarılmasıdır. Bu adımı çeşitli şekillerde yapmak mümkündür ancak biz örneğimizde kolay olması açısından kelime frekanslarını (tekrar sayısı, frequency) kullanacağız. Buna göre metindeki kelimelerin tekrar sayılarına göre sıralanmış hali aşağıda verilmiştir:

bilgisayar 3 com 2 kavramları 1 kavramlarının 1 anlatıldığı 1 bir 1 www 1 sitesidir 1 ve 1 uzantılıdır 1

Yukarıda geçen her kelime için bir parmak izi (fingerprint) değeri üretiyoruz. Bu değerin özelliği, kelimeler arasında yegane (unique) bir değer bulmaktır. Bu değer, herhangi bir hash fonksiyonu üzerinden de üretilebilir. Biz örneğimizde kolalık olması açısından her kelime için rast gele bir değer kendimiz atayacağız. Ancak gerçek bir uygulamada rast gele değerlerin kullanılması mümkün değildir. Bunun sebebi, aynı kelimenin tekrar gelmesi halinde yine aynı değerin üretilmesi zorunluluğudur. Bu yazıdaki amaç algoritmayı anlatmak olduğu için birer hash sonucu olarak rast gele değerler kullanılacaktır.

bilgisayar 10101010 com 11000000 kavramları 01010101 kavramlarının 10100101 anlatıldığı 11101110 bir 01011111 www 11110001 sitesidir 10101110 ve 00001111 uzantılıdır 00100010

3. adımda, yukarıdaki değerleri topluyoruz. Toplama işlemi sırasında 1 değerleri için +1 ve 0 değerleri için -1 alıyoruz.

10101010
11000000
01010101
10100101
11101110
01011111
11110001
10101110
00001111
00100010
——–
2 0 2 -4 0 2 2 0

Son olarak, yukarıdaki değerleri ikilik tabana çeviriyoruz: 10100110 bu değer bizi simhash sonucumuz olarak bulunuyor.

Örneğin yeni bir dosyayı daha işlemek istediğimizde, bu dosyadaki kelime yoğunluğuna göre yukarıda bulduğumuz simhash değerine yakın bir değer çıkmasını bekleriz.

Diyelim ki yeni bir dosyada da sadece “bilgisayar kavramları com” yazıyor olsun. Bu yazının sim hash değerini bularak karşılaştırmaya çalışalım:

bilgisayar 10101010 com 11000000 kavramları 01010101

10101010
11000000
01010101
———
1 1 -1 -1 -1 1 1 1

Değerin ikilik tabana çevrilmiş hali : 11000111

Orjinal dokümandan çıkardığımız simhash değeri ile farklı olan bit sayısı 3’tür. Bunun anlamı yukarıdaki bilgisayar kavramları com yazısının orjinal yazıya 3 mesafesinde yakın olduğudur.

Yorumlar

  1. Kaan Arikan

    Merhaba Hocam,

    Oncelikle sitenizden siklikla faydalaniyorum, cok tesekkur ederim.

    Arama motorlariyla alakali bir sunum hazirliyorum ve Simhash algoritmasi icin sizin bu yazinizi okuyordum. Anlamadigim kisim neden kelimelerin agirliklarini aldiginiz. Zannediyorum ki kelimelerin fingerprint degerlerinin agirliklarla bir iliskisi var. Eger dogruysa lutfen bir kac cumleyle bana bunu aciklayabilir misiniz? Eger aralarinda bir iliski yoksa o zaman kelime agirliklarinin rolu nedir?

    Tesekkur ederim,
    Kaan Arikan.

  2. Şadi Evren ŞEKER

    Evet yazıda o kısım biraz zayıf kalmış. Kelime yoğunluklarını, simhash’in yakınlık ilişkisindeki başarısını göstermek için anlatmaya başlamışım ve biraz zayıf kalmış sanırım o bağlantı.

    Durum kısaca şöyle. Simhash için kelime yoğunluğu almak gerekmez. Kelime yoğunluğunun simhash için herhangi bir etkisi yoktur.

    Yazıda kelime yoğunluğunun alınma sebebi, en sondaki simhashin benzeme oranını inceledğimiz ‘bilgisayar kavramlari com’ örneğinin daha yoğun geçen kelimelerden oluştuğu için daha yakın sonuç üreteceğini göstermek. Ama sanırım çok açık yazamamışım.

    İlginiz için teşekkür ederim en kısa sürede o kısmı biraz daha açık yazmaya çalışacağım.

Bir cevap yazın

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