Mükemmel Hash Fonksiyonu Aramasının Gayriresmî Bir Analizi

N. Cercone
School of Computing Science, Simon Fraser University
Burnaby, British Columbia, Kanada

M. Krause
MacDonald Dettwiler and Associates
3751 Shell Road
Richmond, British Columbia, Kanada

Özet

Mükemmel hash fonksiyonu aramasının kısa bir açıklaması sunulmakta ve ardından problemin gayriresmî bir analizi verilmektedir.

Burada formüle edildiği biçimiyle bu işlem O(N²) karmaşıklığına sahiptir. Aynı denetim, her anahtar için ilk ve son harf ayrıştırılıp sıralanarak, ardından N anahtarın bu ayrıştırılmış harf kümelerine göre sözlükbilimsel sıraya yerleştirilmesiyle de yapılabilir. Daha sonra, ayrıştırılmış harf grupları eşleşen komşu anahtarları karşılaştırmak için anahtarlar üzerinden tek bir geçiş yapılabilir. Bu prosedürün maliyeti esas olarak sözlükbilimsel sıralamanın maliyeti tarafından belirlenir ve bu sıralama N log₂ N ile orantılı sürede gerçekleştirilebilir.

Bu başlangıç sıralaması, ilk ve son harflerin görülme sıklığını sayar ve bunun için N anahtar üzerinde bir geçiş gerekir. Daha sonra her anahtarın frekanslarının toplamını hesaplamak için ikinci bir geçiş yapılır. Anahtarların bu toplamın azalan sırasına göre sıralanması — ki bu adımın baskın maliyetidir — N log₂ N ile orantılı zaman gerektirir.

1. Giriş

N adet anahtar kümesi ve boyutu r ≥ N olan bir hash tablosu verildiğinde, mükemmel bir hash fonksiyonu anahtarları hash tablosunda benzersiz adreslere eşler. Hash tablosu yükleme faktörü (LF), anahtar sayısının tablo boyutuna oranıdır: N/r. Minimal mükemmel hash fonksiyonu N anahtarı N adet bitişik konuma eşler ve LF değeri bire eşittir. Wiederhold [1], deterministik ve olasılıksal doğrudan erişim yöntemlerini ayırt eder. Mükemmel hash fonksiyonları deterministiktir ve çakışmalara izin vermez; böylece tek denemede erişimi garanti eder.

Mükemmel hash fonksiyonlarını bulmak zordur; neredeyse minimal çözümler kabul edilse bile bu durum geçerlidir. Knuth [2], en sık kullanılan 31 İngilizce kelimeyi 41 adrese eşlemek için kullanılan fonksiyonlardan yalnızca 10 milyonda birinin mükemmel hash fonksiyonu olduğunu tahmin etmektedir. Cichelli [3], aşağıdaki biçimde makineden bağımsız minimal mükemmel hash fonksiyonlarını hesaplamak için bir algoritma geliştirmiştir:

hash değeri = hash anahtarının uzunluğu + anahtarın ilk harfinin ilişkili değeri

anahtarın son harfinin ilişkili değeri

Cichelli’nin makineden bağımsız hash fonksiyonu algoritması, anahtarlar için iki aşamalı bir sıralama prosedürü içerir; bu prosedür ilişkili değerler için yapılacak aramanın boyutunu etkili biçimde azaltır. Ancak yine de 40’tan fazla anahtar içeren kümeler için hash fonksiyonları bulmak oldukça fazla hesaplama gerektirir. Cichelli’nin yöntemi ayrıca sınırlıdır; çünkü ilk ve son harfleri aynı olan ve aynı uzunluğa sahip iki anahtara izin verilmez.

2. Cichelli’nin Algoritması

Aşağıda Cichelli’nin mükemmel hash fonksiyonu algoritmasının bir taslağı verilmiştir.

Algoritma 0

Adım 1:
Her anahtarı diğerleriyle karşılaştır. Eğer iki anahtarın ilk ve son harfleri aynıysa ve uzunlukları eşitse, çatışma bildir ve dur; aksi halde devam et.

Adım 2:
Anahtarları, ilk ve son harflerin görülme sıklıklarının toplamı azalmayan sıraya göre düzenle.

Adım 3:
Anahtarları listenin başından itibaren yeniden düzenle; öyle ki bir anahtarın ilk ve son harfleri listede daha önce görünmüşse, bu anahtar listede sıradaki konuma yerleştirilir.

Adım 4:
Çözüme her seferinde bir kelime ekle ve her adımda hash değeri çatışması olup olmadığını kontrol et. Eğer bir çatışma oluşursa, önceki kelimeye geri dön ve onun ilişkili değerlerini değiştirerek hash tablosuna başarıyla yerleştirilmesini sağla; ardından bir sonraki kelimeyi ekle.

Şimdi Cichelli’nin algoritmasının karmaşıklığının gayriresmî bir analizini veriyoruz.

Adım 1:
Burada formüle edildiği biçimiyle bu işlem O(N²) karmaşıklığındadır. Aynı denetim, her anahtar için ilk ve son harfi ayrıştırıp sıralayarak ve ardından N anahtarı bu ayrıştırılmış harf kümelerine göre sözlükbilimsel sıraya koyarak da yapılabilir. Daha sonra, ayrıştırılmış harf grupları eşleşen komşu anahtarları karşılaştırmak için anahtarlar üzerinden tek bir geçiş yapılabilir. Bu prosedürün maliyeti esas olarak sözlükbilimsel sıralamanın maliyetine bağlıdır ve bu işlem N log₂ N ile orantılı sürede yapılabilir.

Adım 2:
Bu ilk sıralama, ilk ve son harflerin görülme sıklığını sayar ve bunun için N anahtar üzerinden bir geçiş gerekir. Ardından her anahtarın frekanslarının toplamını hesaplamak için ikinci bir geçiş yapılır. Anahtarların bu toplamın azalan sırasına göre sıralanması — bu adımın baskın maliyeti — N log₂ N ile orantılı zaman gerektirir.

Adım 3:
İkinci sıralama O(N²) bir sezgiseldir. Her anahtar yeni sıralamaya eklendikçe, eski sıralamadaki kalan anahtarlar taranarak hangilerinin hash değerlerinin artık belirlenmiş olduğu saptanır. Bu işlem (N−1)(N−2)/2 işlem gerektirebilir.

Adım 4:
İki sıralamanın arama alanını azaltma eğilimine rağmen, çoğu anahtar kümesi için bu algoritmanın geri izleme (backtracking) aşaması en maliyetli kısımdır. Ortalama durum karmaşıklığını hesaplamak zordur; Simon ve Khlane [4], ortalama bir aramanın toplam arama alanının yaklaşık yarısını kapsadığını tahmin eder ve bu da O(mˢ/2) gibi kabaca bir tahmine yol açar. Burada m her harf için değer alanının büyüklüğünü, s ise ilk veya son konumda görülen harf sayısını ifade eder.

Cichelli’nin algoritması, hash tanımlayıcısı olarak anahtar uzunluğunu ve ilk ile son harfleri (harf konumunu dikkate almadan) kullanır. Ayırt edilebilecek anahtar sayısı P·CH(A,2) ile sınırlıdır; burada P maksimum anahtar uzunluğunu, CH bilinen seçim fonksiyonunu, A ise alfabenin kardinalitesini gösterir. Tamsayı atama değerleri basit bir geri izleme süreciyle bulunur. Cichelli, ilişkili harf değerlerinin tanım kümesinin boyutu olan m’nin nasıl seçileceğine dair bir yöntem önermemiştir. Bu parametre önemlidir çünkü m, geri izleme arama ağacının dallanma faktörünü belirler.

Bu yöntemi kullanarak mükemmel bir hash fonksiyonu bulmak için gereken sürenin, problem kümesindeki anahtar sayısından çok anahtarlar arasındaki ortak harf ilişkilerine bağlı olarak büyük ölçüde değiştiğini gözlemledik (Krause [5]). Cichelli’nin algoritması çözüm uzayında nispeten az bilgiye dayalı kapsamlı bir aramaya dayandığından, bir çözüm bulmanın maliyeti oldukça yüksek olabilir. Bu durum, algoritmanın uygulanabileceği problem kümesi boyutunu sınırlamaktadır.

Şimdi problemin doğasına ilişkin gayriresmî bir analiz sunuyoruz. Bu analiz, Cichelli stratejisinin sınırlamalarını aşmaya yönelik bazı yöntemlere işaret ederken aynı zamanda onun avantajlarını korumamıza olanak tanır.

3. Problemin Gayriresmî Bir Analizi

Dört alt problem tanımlıyoruz:

Hash fonksiyonunda kullanılacak anahtarların biçimsel özelliklerinden oluşan bir küme seçmek.
Olası çözümler uzayını aramak için bir yöntem seçmek.
Arama yönteminin performansını artırmak için arama değişkenlerini sıralamak.
Çözümün makul bir minimalite derecesine sahip olmasını sağlayacak yöntemler bulmak.

Hash Tanımlayıcılarının Seçilmesi

Bir anahtar, A alfabesinden semboller içeren ve uzunluğu P’den büyük olmayan bir dizidir. A üzerinde sözlükbilimsel bir sıralama tanımlı olduğunu varsayıyoruz. Olası anahtarların uzayı T, verilen P ve A tarafından belirlenir.

Eğer T = card(T) ve A = card(A) ise

T = Aᴾ + Aᴾ⁻¹ + ... + A = Σ Aⁱ (1 ≤ i ≤ P)

= A(Aᴾ − 1)/(A − 1) = Θ(Aᴾ)

A büyüdükçe. A keyfi derecede büyüdüğünde, A/(A−1) sınırı 1’e yaklaşır ve sonuçtaki Aᴾ⁻¹ çarpanı Aᴾ’e indirgenir. Böylece T, A’ya göre polinomik ve P’ye göre üstel bir hızla büyür. Örneğin A = 26 küçük Latin harfi ve P = 6 için; T ≈ 26⁶ = 3.2 × 10⁸.

Anahtarlarda Harf Sırası

Hash tanımlayıcısı olarak kullanılan özellik kümesi sıralı olmadığında ayırt edilebilecek anahtar sayısı CH(A+i−1, i) ifadesiyle verilir (1 ≤ i ≤ P). Burada CH(n,m) bilinen seçim fonksiyonudur ve şu şekilde tanımlanır:

CH(n,m) = n! / (m!(n−m)!)

Eğer A = 26 ve P = 6 ise anahtar uzayının büyüklüğü

Σ CH(A+i−1, i), (1 ≤ i ≤ P)

= CH(26,1) + CH(27,2) + ... + CH(31,6)

= 906,091 ≈ 9 × 10⁵.

Bu sayıyı, aynı A ve P değerleri için harflerin ortaya çıkış sırası dikkate alındığında ayırt edilebilen 3.2 × 10⁸ anahtarla karşılaştırın. Sıralama dikkate alınmadığında bu örnek anahtar uzayında yalnızca yaklaşık her 350 anahtardan biri ayırt edilebilir.

Hash Tanımlayıcıları

Algoritma 1’i öneriyoruz; bu algoritma, aynı uzunluktaki anahtarların her alt kümesi için, bir anahtar içindeki harflerin ortaya çıkış sırası göz ardı edildiğinde her anahtarı ayırt eden en küçük harf konumları kümesini otomatik olarak seçen bir prosedürü içerir [5]. Her harfin konumundan bağımsız olarak yalnızca bir ilişkili değeri olduğundan, bir anahtarın hash adresi seçilen konumlardaki harflerin birleşimi tarafından belirlenir.

Farklı (sırasız) harf alt kümelerinin sayısı, aynı maksimum uzunluğa sahip anahtar uzayından çok daha küçüktür; bu nedenle Algoritma 1 aracılığıyla işlenebilecek anahtar uzayı alt kümelerinin sayısı sınırlıdır. Mükemmel hash fonksiyonunun aranmasını ve daha sonra kullanılmasını mümkün olduğunca basit tutmak için, uzunluğu P olan anahtarlarda her bir verilen anahtarı ayırt eden en küçük P harf konumu alt kümesini seçiyoruz.

Yalnızca bir harf konumu kullanılarak ayırt edilebilecek anahtar sayısının üst sınırı A’dır. İki harf konumu seçildiğinde teorik olarak A² anahtar ayırt edilebilir; ancak bu yalnızca ab ≠ ba olduğu durumda geçerlidir. Algoritma 1’de bu ayrım yapılmaz ve bu da iki harf konumu seçildiğinde tanınabilecek farklı anahtar sayısını A(A−1)/2’ye düşürür.

[6]’da algorithm cbk olarak adlandırılan Algoritma 3, hash fonksiyonu için özellikler kümesini seçerken insan yargısına etkileşimli biçimde dayanır. Ayrıca harflerin ortaya çıkış konumunu da dikkate alır ve bu nedenle mümkün olan en yüksek ayırt etme gücüne sahiptir.

İlişkili Harf Değerlerinin Atanması

Anahtarları hash tablosuna eşleyen harflere tamsayı değerleri atamasının verimli biçimde aranması, kabul edilebilir bir çözümün makul sürede bulunabilmesi için gereklidir. Arama uzayını Şekil 1’de gösterildiği gibi bir ağaç olarak düşünürsek, kökten (aramadaki başlangıç durumu) üstel sayıda olası çözüme kadar polinom maliyetli bir yol bulunduğunu görürüz.

Şekil 1’de üç anahtardan oluşan bir küme vardır (N = 3), seçilmiş konumlardan iki harf vardır (s = 2) ve en büyük ilişkili değer ikidir (m = 3, M = {0,1,2}). Harflere yapılabilecek farklı tamsayı atamalarının sayısı mˢ’tir; bu da ağacın yaprak düğümlerinin sayısıdır.

Ağacın birinci derinliğinde ‘a’ harfine bir değer atanır ve bu değer ‘aa’ anahtarının hash adresini belirler. İkinci derinlikte ‘b’ harfine bir değer atanması ‘bb’ ve ‘ab’ anahtarlarının hash adreslerini belirler. Amaç, arama ağacının mümkün olduğunca küçük bir kısmını üretirken kabul edilebilir bir çözüme götüren bir yol bulmaktır; yani klasik bir geri izleme aramasıdır.

Küçük arama uzayı örneğinde anahtar kümesi (aa, ab, bb), L = 2, M = N = 3 ve harf sırası ⟨a, b⟩’dir. Yaprak düğümler mˢ = 3² = 9 olası ilişkili değer kombinasyonudur. Minimal çözümler ⟨0,1⟩, ⟨1,0⟩, ⟨1,2⟩ ve ⟨2,1⟩; minimal olmayanlar ise ⟨0,2⟩ ve ⟨2,0⟩’dır.

Değişken Sıralamasının Önemi

Mükemmel hash fonksiyonu araması için geri izleme ölçütü — buna Q yüklemi diyelim — şu şekilde tanımlanabilir: ⟨a₁,...,aₙ⟩ değişkenlerine ⟨x₁,...,xₙ⟩ değerlerinin atanması verildiğinde

Q(x₁,...,xₙ) = Yanlış, eğer K kümesinde i ≠ j olacak şekilde kᵢ ve kⱼ mevcutsa ve her iki anahtar için seçilen konumlardaki tüm harfler ⟨a₁,...,aₙ⟩ içinde bulunuyor ve H(Kᵢ) = H(Kⱼ) ise;

= Doğru, aksi durumda.

Q(x₁,...,xₙ) doğru olduğunda, ⟨x₁,...,xₙ⟩ artık H değeri tanımlanmış olan K içindeki anahtar alt kümesi için (seçilen konumlardaki tüm harfleri değer atanmış olanlar) bir mükemmel hash fonksiyonunu temsil eder. Geri izleme koşulu Q(x₁,...,xₙ), hiçbir iki anahtarın aynı hash adresine sahip olmamasını gerektirir. Yüklemi verimli biçimde test edebilmek için, seçilen harfleri daha önce değer atanmış olan anahtarlar tarafından hangi adreslerin dolu olduğunu kaydettiğimiz olası hash adreslerinden oluşan bir dizi tutarız. Hiç harf değeri atanmadığında Q boş biçimde doğrudur.

Q(x1, ..., xi−1) koşulunun sağlandığını varsayalım: çözümü Q(x1, ..., xi−1, xi) biçimine genişletmek iki adım içerir: (1) ai değişkenine xi değeri atanır; ve (2) hash adresleri a1, ..., ai içinde bulunan harflere bağlı olan “yeni” anahtarların hash adresleri hesaplanmalı ve hash tablosunun mevcut durumu ile karşılaştırılmalıdır. Eğer di, ai harfinin değer atanacak son seçilmiş harf olduğu anahtar sayısını gösteriyorsa, harflerin her sıralaması genel olarak ⟨d1, ..., ds⟩ biçiminde farklı bir değer vektörü üretir. Bu di değerlerinin toplamı (1 ≤ i ≤ s) problem kümesindeki anahtar sayısı olan N’dir. Bir değişken için bir sonraki deneme değerinin üretilmesine birim maliyet atarsak, tüm ağacı üretmenin maliyeti ağaçtaki düğüm sayısına eşittir.

Derinliği s ve dallanma faktörü m olan tam bir ağaçtaki düğüm sayısı, kökün seviye 0’da olduğu durumda, ağacın her seviyesindeki düğümlerin toplamıdır:

C = Σ m^i, 0 ≤ i ≤ s = (m^(s+1) − 1) / (m − 1) = O(m^(s+1)) = O(m^s) m → ∞ iken

Uygulamamızda s, değer atanacak harf sayısını; m ise her değişkenin tanım kümesindeki değer sayısını temsil eder, M = [0 ... m−1].

Bu nedenle m’nin seçimi kritiktir; çünkü ilişkili değerlerin seçildiği tanım kümesinin büyüklüğü arama ağacının dallanma faktörünü belirler. Eğer m çok küçük seçilirse problem kümesi için çözüm bulunamayabilir; m’nin değerini yeterince büyük, örneğin sonsuz olarak ayarlarsak bir çözümün varlığı garanti edilir, ancak minimal çözümün ilk bulunan çözüm olmasını beklemek için bir neden yoktur. Pratikte m’yi N olarak ayarlayarak etkileyici sonuçlar elde ettik; ancak verilen bir anahtar kümesi için m’nin en uygun değerini belirleyen analitik bir yöntem bilmiyoruz.

Mevcut kısmi çözümün Q’yu sağlayıp sağlamadığını belirlemek için, çözümü j’inci harfe genişletme girişiminin her birinde dj adet test yapılmalıdır. Ağacın j derinliğindeki her düğüme dj+1 maliyeti atayabiliriz; bu maliyet aj için bir sonraki değerin üretilmesi maliyeti ile dj kez hash adresini test etmenin (birim) maliyetinin toplamıdır. Eğer cj = dj + 1 olarak tanımlanırsa, ağaçtaki her düğümü ziyaret etmenin maliyeti şu olur:

WCT = Σ (cj * m^j), 0 ≤ j ≤ s

Buna ağırlıklı maliyet ağacı (WCT) diyoruz. Değişkenlerin her sıralaması (muhtemelen farklı) bir WCT değeri belirler; WCT değerini en küçük yapan değişken sıralamasını en iyi sıralama olarak kabul ederiz.

Arama Değişkenlerinin Sıralanması

s adet arama değişkeni a1, ..., as verildiğinde en iyi sıralama nedir? B = ⟨a1, ..., as⟩ permütasyonunu ele alalım ve D(B) = ⟨d1, ..., ds⟩ olarak tanımlayalım; burada di, ai değer atandığında hash adresleri yeni belirlenen anahtar sayısını verir. C(B) = ⟨c1, ..., cs⟩ ise her di değerine bir eklenmiş hâlidir; böylece ci, ağacın i seviyesindeki herhangi bir düğümü ziyaret etmenin maliyetini temsil eder.

C(B)’yi, WCT’yi oluşturan m^i terimleri serisinin (0 ≤ i ≤ s) katsayı vektörü olarak ele alırız:

WCT = Σ (ci * m^i), 0 ≤ i ≤ s = c0 + c1m + ... + csm^s

Başlangıç terimi, c0 bir (birim zaman maliyeti) olarak tanımlandığında, arama ağacının kök düğümünü üretmenin maliyetidir. Toplam maliyetteki her terimde bulunan m katsayısının, kökten uzaklığı arttıkça üstel olarak büyüdüğüne dikkat edin.

WCT’nin incelenmesi, katsayılara cs, cs−1, ..., c2, c1 sırasına göre mümkün olan en küçük değerleri atamak istediğimizi gösterir; burada cs mümkün olduğunca küçük ve c1 mümkün olduğunca büyük olmalıdır. ds = 0 olamaz, çünkü en az bir anahtarın sıralamadaki son harfi, kendisine değer atanacak son harf olmak zorundadır. Bulabileceğimiz en iyi durum, frekans sayısı bir olan bir as harfidir; böylece yalnızca tek bir anahtarın belirleyici değeri olabilir ve cs’ye iki değeri verilmiş olur.

Arama ağacının büyüklüğünü tanımlayan polinomda m^s teriminin, kalan terimlerin toplamından daha büyük olduğunu gösterebiliriz [5]. m^s ağacın maliyetine en fazla katkıyı yapacağından, WCT’deki katsayısının s! olası değişken permütasyonları arasında ortaya çıkan en küçük değer olması gerekir. Bu nedenle, en az bir benzersiz harf oluşumuna sahip bir anahtar bulmak isteriz; çünkü yalnızca böyle bir harf sıralamada en sona gelebilir ve yine de karma tablosuna tek bir anahtar yerleştirebilir.

Bu gözleme dayanan harfler için sezgisel bir sıralama stratejisi, harfleri frekanslarına göre azalmayan düzende sıralar; böylece a1 en yüksek görülme sıklığına, as ise en düşük görülme sıklığına sahip olur. Bu düzenlemenin genellikle, önce anahtarların harf frekanslarının toplamına göre sıralanması ve ardından her anahtardan daha önce ortaya çıkmamış harflerin görülme sıklığına göre azalan sırayla seçilmesi durumunda ortaya çıktığını görürüz. İkinci sıralama, maliyet denkleminin m çarpanlarının katsayılarını küçük çarpanlar için artırma ve büyük m çarpanları için azaltma etkisine sahiptir.

Arama değişkenlerinin en uygun sıralaması, Bmin = ⟨a1, a2, ..., as⟩, WCT’nin en küçük olduğu sıralamadır. Harflerin tüm s! permütasyonlarını üretseydik, en uygun sıralamanın D(B)’nin ve dolayısıyla C(B)’nin en büyük sözlük sıralama değerine sahip olduğu sıralama olduğunu görürdük.

En uygun sıralamaya, s! permütasyondan çok daha azını inceleyerek yaklaşabiliriz. Bu, Slingerland ve Waugh [7] tarafından önerildiği gibi ikinci sıralamanın şu şekilde iyileştirilmesiyle gerçekleştirilir: “eşit frekans sayımlarına sahip her kelime alt listesi, en büyük ikinci sıralama etkisini gösterecek, yani listenin geri kalanından en fazla kelimeyi ‘ortaya çıkaracak’ kelimeler önce gelecek şekilde sıralanmalıdır”.

Bu durum modelimiz tarafından açıklanır; çünkü yeniden sıralama sürecinin her aşamasında, mevcut frekans toplamı en yüksek olan anahtarlar arasından, yeni harfi en fazla sayıda karma adresini belirleyecek olan bir sonraki anahtarı seçeriz. Bu strateji, küçük m çarpanlarının katsayılarını artırma ve böylece büyük m çarpanlarının katsayılarını azaltma eğilimi gösterir; bu da sonuç olarak WCT’yi düşürür.

WCT’nin yalnızca aradığımız ağacın büyüklüğünü gösterdiğini unutmayın; yalnızca tek bir kabul edilebilir çözüm aradığımız durumda en kötü durum karmaşıklığının bir ölçüsüdür. Geri izleme yaklaşımının en büyük değeri şudur: eğer tüm kısmi çözümlerin geçerliliğini test edersek ve ⟨x1, ..., xi⟩ biçimindeki bir kısmi çözümün Q’yu sağlamadığını bulursak, xi köküne sahip alt ağacı budayabilir ve i seviyesinde reddedilen bir değer için başlangıç bölümü ⟨x1, x2, ..., xi⟩ olan m^(s−i) tam ve kısmi çözümün üretilmesini önleyebiliriz.

Neyse ki, bir ai harfinin görülme sıklığı, ai harfinin diğer anahtarlarla çakışabilecek bir anahtarda bulunma olasılığını tahmin etmek için mükemmel bir sezgisel değerdir.

Genel olarak şu sonuca varabiliriz: derinlik öncelikli aramada dinamik olarak gerçekleştirilebilen ve bir arama değişkeninin tanım kümesindeki bazı değerleri değerlendirme dışı bırakmamıza olanak tanıyan herhangi bir polinom maliyet analizi, üzerinde çalışmaya değerdir; çünkü ortadan kaldırdığımız her potansiyel değer için üstel olarak büyüyen bir alt ağaç budanacaktır.

Unutmayın, ideal geri izleme araması hiç geri izleme yapmayan aramadır. Bu performans düzeyine ulaşmak için arama, aramanın herhangi bir aşamasında yapılan bir seçimin sonunda kabul edilebilir olacağının bilindiği şekilde düzenlenmelidir. Böyle bir stratejiyi [5]’te sunduk.

Kaynaklar

Wiederhold, G. (1977). Database Design. McGraw Hill, New York.
Knuth, D. (1973). The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Massachusetts.
Cichelli, R. (1980). Minimal Perfect Hash Functions Made Simple. CACM, 23, 17–19.
Simon, H., and Kadane, J. (1976). Problems of Computational Complexity in Artificial Intelligence. In J. F. Traub (ed.), Algorithms and Complexity, Academic Press, New York, 281–299.
Krause, A. M. (1982). Perfect Hash Function Search with Application to Computer Lexicon Design. M.Sc. thesis, Computing Science, Simon Fraser University, Burnaby, B.C.
Cercone, N. (1987). Finding and Applying Perfect Hash Functions. Applied Math Letters, 1(1), 25–29.
Slingerland, J., and Waugh, M. (1981). On Cichelli’s Algorithm for Finding Minimal Perfect Hash Functions. CACM, 24(5), 322.

An Informal Analysis of Perfect Hash Function Search