• bir yazı eşleştirme (string matching) algoritmasıdır.
    dijital dökümanlarda intihal tespitinde kullanılmaktadır.
    özel bir hash fonksiyonu kullanarak çok efektif sonuçlar alınmaktadır.

    örneğin elimizde bir tane pattern olsun cheribum
    bu pattern'i çok uzun bir dökümanda aramak istiyoruz "...cheradsafdagcherasdsafdgcheribumsadfadgfs...."

    pattern'deki harfleri dökümanda tek tek karşılaştırmaktansa (şu şekilde)
    "cheribum" != "cheradsa" (eşit değil, bir karakter sağa kaydır)
    "cheribum" != "heradsaf" (eşit değil, bir karakter sağa kaydır)
    "cheribum" != "eradsafd" (eşit değil, bir karakter sağa kaydır)
    ...

    patterni ve dökümandaki karakterleri bir hash fonksiyonuna sokar ve bu fonksiyon değerlerini karşılaştırır (şu şekilde)

    hash(cheribum) = 37 (değerleri sallıyorum)
    hash(cheradsa) = 45 ( 37'ye eşit değil, bir karakter sağa kaydır, tekrar hash hesapla)
    hash(heradsaf) = 43 ( 37'ye eşit değil, bir karakter sağa kaydır, tekrar hash hesapla)
    ...
    hash(cheribum) = 37 (hash değerleri eşit, kelimeleri kontrol et)
    "cheribum" == "cheribum" (bulduk )

    şimdi hash olayının güzelliği nedir?
    verdiğim örnekte "cheribum" 8 karakterli oldukça kısa bir pattern. eğer bu pattern 1.000 karakterden oluşsaydı ve 10 milyon karakterlik bir dökümanda arama yapacak olsaydık, karakterleri teker teker eşleştirmek çok masraflı bir iş olacaktı.
    örneğin: 999 karakter eşleşiyor ancak son karakter farklı (o kadar emek boşa gitti, 1.000 karakter eşleşinceye kadar devam).

    hash fonksiyonunda ise:
    [1:1000] (ilk 1.000 karakter)
    [2:1001] (sağa kaydır, sonraki 1.000 karakter) olsun.
    kaydırma işlemini tek hamlede yapabiliyoruz, cünkü ortadaki 998 karakter aynı (1.000 tane karakteri tek tek karşılaştırmaya gerek kalmadı).

    esen kalın.

    --- spoiler ---

    hash = (karakterin ascii değeri) *( asal sayı) ^ (karakterin bulunduğu indis)

    örnek:
    ascii değerleri; a = 97, b = 98, r = 114.
    hash("abr") = (97 × 101^2) + (98 × 101^1) + (114 × 101^0) = 999,509

    --- spoiler ---
  • belirtilen hash fonksiyonu (rolling hash) tarafından hesaplanan sonuca bir önceki elemanı çıkarıp bir sonraki elemanı ekleme ile sıradaki hash'i hesaplayabilmemiz işlemine dayanır.

    örneğin string için s diyelim, hash fonksiyonumuz da aşağıdaki 3. derece polinom olsun

    p(x) = s[0] + s[1] * x + s[2] * x^2 + s[3] * x^3

    genellersek:

    k polinomun derecesi

    pi(x) = s[i] * x ^ (k - 3) + s[i+1] * x ^ (k-2) + s[i+2] * x ^ (k-1) + s[i+3] * x ^ k

    bir sonraki hash'i bulmak icin bir önceki hash değerini kullanabiliriz

    pi+1(x) = (pi(x) - s[i]) / x + s[i + k] * x ^ k

    aradığımız substring'in hash'ini bir köşeye koyup, yukarıdaki özelliğin yardımıyla text içerisinde adım adım substring hash'lerini hesaplamaya başlarsak hızlı bir şekilde eşleşme yakalayabiliriz.
  • bir text içindeki bir alt metni aramak için geliştirilmiş algoritma patternidir.burada aranacak string deger tum metinde text olarak değil de aranan metnin hash degerine göre arama yapılıp daha performanslı bir search işlemi gerceklestirilmesini sağlar.
hesabın var mı? giriş yap