Minimal Mükemmel Karma Fonksiyonları Oluşturmak İçin En İyi Algoritma

George Havas
Bilgisayar Bilimleri Bölümü, Key Centre for Software Technology
University of Queensland, St. Lucia, Queensland 4072, Australia

Zbigniew J. Czech
Bilgisayar Bilimleri Enstitüsü, Silesia University of Technology
44-100 Gliwice, Poland

Bohdan S. Majewski
Bilgisayar Bilimleri Bölümü, Key Centre for Software Technology
University of Queensland, St. Lucia, Queensland 4072, Australia

Özet

Sıra koruyan minimal mükemmel karma fonksiyonları üretmek için yeni bir algoritma sunulmaktadır. Algoritma olasılıksaldır ve rastgele grafiklerin oluşturulmasını içerir. Beklenen doğrusal zaman kullanır ve karma fonksiyonunu temsil etmek için doğrusal sayıda sözcük gerektirir; dolayısıyla sabit katsayılar dışında en iyi düzeydedir.

Anahtar Kelimeler: Veri yapıları, olasılıksal algoritmalar, algoritma analizi, hashing, rastgele grafikler

1 Giriş

Her biri sıralı bir alfabe (\Sigma) üzerindeki sembollerin sonlu bir dizgesi olan (m) adet sözcükten oluşan (W) kümesini ele alalım. Bir karma fonksiyonu

h : W → I

şeklinde tanımlanan ve sözcükler kümesi (W)'yi belirli bir tamsayı aralığı (I)'ye eşleyen bir fonksiyondur; örneğin ([0, k−1]), burada (k) bir tamsayıdır ve genellikle (k ≥ m) olur. Karma fonksiyonu, verilen bir sözcük için, o öğenin saklanması veya geri getirilmesi amacıyla bir adres ((I) aralığından bir tamsayı) hesaplar. Öğelerin saklandığı depolama alanına karma tablosu denir. Aynı adresin hesaplandığı sözcükler eşanlamlılar (synonyms) olarak adlandırılır. Eşanlamlıların varlığı nedeniyle iki öğenin aynı adrese sahip olduğu çakışma (collision) adı verilen bir durum ortaya çıkabilir. Çakışmaları çözmek için çeşitli yöntemler bilinmektedir.

Mükemmel bir karma fonksiyonu

h : W → I

şeklinde bir enjeksiyondur; burada (W) ve (I) yukarıda tanımlandığı gibidir ve (k ≥ m) koşulu sağlanır. Eğer (k = m) ise, (h)'nin bir minimal mükemmel karma fonksiyonu olduğu söylenir. Tanımdan anlaşılacağı üzere, mükemmel bir karma fonksiyonu (W) kümesindeki her sözcüğü karma tablosunda benzersiz bir adrese dönüştürür. Çakışma oluşmadığı için her öğe tablodan tek bir erişimle elde edilebilir.

Bir karma fonksiyonu, girdileri önceden belirlenmiş bir sıraya göre karma tablosuna yerleştiriyorsa sıra koruyucudur.

Minimal mükemmel karma fonksiyonları, programlama dillerindeki ayrılmış sözcükler, işletim sistemlerindeki komut adları, doğal dillerde sık kullanılan sözcükler gibi statik bir kümeden öğelerin bellek açısından verimli biçimde saklanması ve hızlı erişimi için kullanılır.

Mükemmel karma üzerine genel bir bakış [18], §3.3.16'da verilmiştir ve alan [25]'te incelenmiştir. Bazı yeni bağımsız gelişmeler [13, 14, 16]'da görülmektedir. Mükemmel veya minimal mükemmel karma fonksiyonları oluşturmak için farklı zaman karmaşıklıklarına sahip çeşitli algoritmalar sunulmuştur; bunlar arasında [3, 4, 5, 6, 7, 8, 17, 10, 11, 20, 22, 30] yer alır.

1985 yılında Sager grafik temelli mincycle algoritmasını [28] önermiştir. Yazar mincycle algoritmasının karmaşıklığının O(m) olduğunu ileri sürmüştür. Bu algoritmaya dayalı olarak başka çözümler de geliştirilmiştir [13, 14, 15, 16]; bunların zaman performansı esas olarak deneysel kanıtlara dayanmaktadır.

Biz rastgele grafiklere dayanan ve şu biçimde minimal mükemmel karma fonksiyonları bulmayı amaçlayan yeni bir algoritma sunuyoruz:

h(w) = g(f₁(w)) + g(f₂(w)) mod m

burada (f₁) ve (f₂) dizgeleri tamsayılara eşleyen fonksiyonlardır ve (g) tamsayıları ([0, m−1]) aralığına eşleyen bir fonksiyondur.

Beklenen zaman karmaşıklığının (O(m)) olduğunu gösteriyoruz. Üretilen fonksiyonu saklamak için gereken alan (O(m \log m)) bittir; bu da sıra koruyan minimal mükemmel karma fonksiyonları için en iyi düzeydedir (bkz. [21]).

Şu problemi ele alalım. Verilen yönsüz bir grafik için

G = (V, E), |E| = m, |V| = n

şu fonksiyonu bulun:

g : V → [0, m−1]

öyle ki

h : E → [0, m−1]

fonksiyonu bir bijeksiyon olsun. Başka bir deyişle, köşelere değerler atayarak her kenar için uç noktalarına karşılık gelen değerlerin toplamının kenar sayısına göre modunun ([0, m−1]) aralığında benzersiz bir tamsayı olmasını istiyoruz.

Keyfi grafikler ele alındığında bu problem her zaman çözülebilir değildir. Ancak grafik (G) çevrimsiz (acyclic) ise, her köşe için değerleri bulmak üzere çok basit bir yöntem kullanılabilir.

Her kenarla (h(e) ∈ [0, m−1]) olacak şekilde benzersiz bir sayı ilişkilendirin. (G)'nin her bağlı bileşeni için bir (v) köşesi seçin. Bu köşe için (g(v) = 0) olarak ayarlayın. Grafiği bir derinlik öncelikli arama (veya graf üzerinde herhangi bir standart arama) kullanarak, (v) köşesinden başlayarak dolaşın. Eğer (w) köşesine (u) köşesinden ulaşılıyorsa ve

e = (u, w)

kenarı ile ilişkilendirilen değer (h(e)) ise

g(w) = (h(e) − g(u)) mod m

olarak ayarlayın.

Yukarıdaki yöntemi (G)'nin her bileşeni için uygulayın. Sözde kod Fig. 2'de verilmiştir. Yöntemin doğruluğunu göstermek için fonksiyon (g)'nin değerinin her köşe için tam olarak bir kez hesaplandığını göstermek yeterlidir. (G) çevrimsiz ise bu özellik açıkça sağlanır.

Bu grafik probleminin çözümü, minimal mükemmel karma fonksiyonu üretme algoritmamızın ikinci bölümünü oluşturur ve atama adımı olarak adlandırılır.

Artık minimal mükemmel karma fonksiyonu üretmek için yeni algoritmayı sunmaya hazırız. Bir (w) sözcüğünün uzunluğunu (|w|) ile ve i'inci karakterini (w[i]) ile gösteriyoruz. Algoritma iki adımdan oluşur: eşleme (mapping) ve atama (assignment).

Eşleme adımında

G = (V, E)

grafiği oluşturulur; burada

V = {0, … , n−1}

ve (n) değeri daha sonra belirlenir, ayrıca

E = {(f₁(w), f₂(w)) : w ∈ W}.

(W)'yi ([0, n−1]) aralığına eşleyen iki bağımsız rastgele fonksiyon olacak şekilde tasarlanan yardımcı fonksiyonlar (f₁) ve (f₂) tanımlıyoruz.

Bunun çeşitli yolları vardır. Burada fonksiyonları şu şekilde seçiyoruz:

f₁(w) = ( Σ T₁(i, w[i]) ) mod n
f₂(w) = ( Σ T₂(i, w[i]) ) mod n

burada (T₁) ve (T₂), bir sözcükteki her karakter ve her karakter konumu için mod (n) rastgele tamsayılar içeren tablolardır.

(T₁) ve (T₂) tabloları için gereken alan (O(\log n)) bittir; çünkü her giriş ([0, n−1]) aralığında bir sayıdır ve gerçekte sabit sayıda giriş vardır (anahtarların uzunluğuna ve karakter kümesinin boyutuna bağlıdır). (n) bir bilgisayar sözcüğüne sığdığı sürece bu (O(1)) sözcüktür.

Eğer (n) alfabe boyutundan küçük değilse, her (w[i]) karakterini bir sayı olarak ele alarak başka uygun bir eşleme fonksiyon çifti elde ederiz:

f_k(w) = ( Σ T_k(i) · w[i] ) mod n

Bu fonksiyonlar daha az alan kullanılarak saklanabilir; ancak yaygın makine mimarilerinde karma fonksiyonu değerlendirme süresi daha uzun olur (çünkü tablo erişimleri çarpma işlemleriyle değiştirilir). Aslında uygun fonksiyonları tek bir rastgele sayı ile bile tanımlayabiliriz; fakat bu durumda hesaplama süresi daha da artar. Ancak (m) arttıkça alan gereksinimimiz esas olarak (g) fonksiyonunu saklamak için gereken alan tarafından belirlendiğinden, bu tür değerlendirmeler yalnızca küçük (m) değerleri için önemlidir.

Amacımız, grafik (G)'nin çevrimsiz olmasını sağlayacak şekilde (T₁) ve (T₂) değerlerini bulmaktır. Bunu gerçekleştirmek için kolay bir deterministik yöntemimiz olmadığı için tabloları rastgele biçimde tekrar tekrar üretiriz; çevrimsiz bir grafik elde edene kadar bu işlem sürdürülür (bkz. Fig. 1).

Çevrimsiz bir grafik elde edildiğinde atama adımı yürütülür. Minimal mükemmel karma fonksiyonu üretme işleminin bu bölümün başında tanımlanan probleme indirgenebileceğine dikkat edin. Çevrimsiz bir grafikte her

e = (u, v) ∈ E

kenarı benzersiz olarak şu özelliğe sahip bir (w) sözcüğüne karşılık gelir:

f₁(w) = u, f₂(w) = v.

Basitçe

h(e = (f₁(w), f₂(w))) = i − 1

olarak ayarlarız; burada (w), (W)'nin i'inci sözcüğüdür. Daha sonra her (v ∈ V) için (g) fonksiyonunun değerleri atama adımıyla hesaplanır. (h) fonksiyonu (W) için minimal mükemmel karma fonksiyonudur.

Karma fonksiyonunun değerlendirilmesi hızlı ve sabit zamanda yapılır; temelde iki standart karma hesaplamasından biraz fazlasını içerir. Sözde kod Fig. 3'te verilmiştir.

Figure 1: Eşleme Adımı

repeat
  initialize E := ∅
  randomly generate tables T1, T2

  for w ∈ W loop
      u := (Σ T1(j, w[j])) mod n
      v := (Σ T2(j, w[j])) mod n
      add edge (u, v) to graph G
  end loop

until G is acyclic

Figure 2: Atama Adımı

procedure traverse(u : vertex)
  visited[u] := TRUE

  for w ∈ neighbours(u) loop
      if not visited[w] then
          g(w) := (h(e = (u, w)) − g(u)) mod m
          traverse(w)
      end if
  end loop
end traverse

visited[v ∈ V] := FALSE

for v ∈ V loop
  if not visited[v] then
      g(v) := 0
      traverse(v)
  end if
end loop

Figure 3: Karma Fonksiyonunun Değerlendirilmesi

function h(w : string) : integer
  u := (Σ T1(j, w[j])) mod n
  v := (Σ T2(j, w[j])) mod n
  return (g(u) + g(v)) mod m
end

3 Karmaşıklık Analizi

Bu bölümde algoritmanın beklenen zaman karmaşıklığının sözcük sayısına göre doğrusal olduğunu gösteriyoruz.

Grafikteki kenarların üretilme tekniği nedeniyle aralarında bir miktar bağımlılık vardır. Ancak eşleme fonksiyonlarının getirdiği yüksek derecedeki rastgelelik nedeniyle, m kenarlı grafiklerin eşit olasılıkla rastgele üretildiği varsayımı oldukça doğru sonuçlar verecektir; özellikle de grafiklerimiz oldukça seyrek olduğundan. Bu nedenle teorik analizimizde bundan sonra bu varsayımı kullanıyoruz.

Ayrıca alfabe boyutunu ve maksimum anahtar uzunluğunu sabit kabul ediyoruz; bu, herhangi bir belirli uygulama alanı için makul bir varsayımdır. (Gerçekte m değeri alfabe boyutunun maksimum anahtar uzunluğunun kuvveti ile sınırlıdır, ancak bu pratikte bir kısıtlama değildir.)

Algoritmanın ikinci adımı olan atama

O(m + n)

zamanda çalışır.

Eşleme adımının her yinelemesinde şu işlemler gerçekleştirilir:

(i) rastgele tamsayı tablolarının üretilmesi;
(ii) kümedeki her sözcük için yardımcı fonksiyon değerlerinin hesaplanması;
(iii) oluşturulan (G) grafiğinin çevrimsiz olup olmadığının test edilmesi.

(i) işlemi, (W) kümesindeki bir sözcüğün maksimum uzunluğu ile alfabe boyutunun çarpımıyla orantılı bir zaman alır; bu da sabittir. (ii) ve (iii) işlemleri sırasıyla (O(m)) ve (O(m+n)) zaman gerektirir. Dolayısıyla tek bir yinelemenin karmaşıklığı (O(m+n))'dir.

Şimdi eşleme adımındaki beklenen yineleme sayısının uygun bir (n) seçimiyle sabit yapılabileceğini gösteriyoruz. (p_a), (m) kenarlı ve (n) köşeli çevrimsiz bir grafik elde etme olasılığını göstersin.

(X), gereken yineleme sayısını temsil eden bir rastgele değişken olsun. (X)'in ortalaması, yani eşleme adımında gerçekleştirilen beklenen yineleme sayısı

E(X) = 1 / p_a

ve varyansı

(1 − p_a) / p_a²

dır.

Ayrıca yineleme sayısının (k)'yı aşma olasılığı

(1 − p_a)^k

şeklindedir.

Bir yinelemede çevrimsiz grafik elde etme olasılığını yüksek yapmak için oldukça seyrek grafiklerle çalışmamız gerekir. Bu nedenle

n = c m

olacak şekilde bir sabit (c) seçiyoruz.

Ayrıntılı olasılıksal argümanlar [26]'da verilmiştir. Kısaca, (m) kenarlı ve (n = cm) köşeli rastgele etiketli grafikler için (n → ∞) iken, uzunluğu (k) olan çevrimlerin beklenen sayısı

1 / (2k c^k)

değerine yaklaşır.

Bu sonuçtan, (c > 2) için çevrimsiz bir grafik elde etme olasılığının sabit bir değere yaklaştığı görülür. Bu nedenle

n > 2m

seçiyoruz.

Örneğin

n = 3m

olduğunda, büyük (m) değerleri için beklenen yineleme sayısı yaklaşık 1.3'e yaklaşır. Dolayısıyla eşleme adımının karmaşıklığı (O(m+n)), tüm algoritmanın karmaşıklığı da (O(m+n))'dir.

(n = cm) olduğundan algoritmanın karmaşıklığı sözcük sayısı (m) açısından doğrusaldır.

Fonksiyonlar (f₁) ve (f₂) üzerinde küçük bir değişiklik yaparak algoritmanın performansını biraz iyileştirebiliriz; böylece self‑loop oluşmaz. Bunun bir yolu

f₁(w) ≠ f₂(w)

koşulunu sağlayacak şekilde tanımı değiştirmektir; başka bir yol ise iki parçalı (bipartite) grafikler üretmektir. (W) içindeki sözcüklerin özel özellikleri dikkate alınarak başka iyileştirmeler de yapılabilir.

4 Basit Bir Örnek

İlk üç karaktere kısaltılmış 12 ay adından oluşan kümeyi ele alalım. i'inci ayın (i ∈ {1,…,12}) karma tablosunda (i−1)'inci konumda tutulacağı şekilde bir minimal mükemmel karma fonksiyonu kurmak istiyoruz.

(c = 2) seçiyoruz; dolayısıyla (n = 25). Ayrıca anahtarların ikinci ve üçüncü karakterlerinin her anahtar için benzersiz olduğunu fark ediyoruz; bu nedenle (T₁) ve (T₂) tablolarının tanımını her tabloda yalnızca iki satır olacak şekilde sınırlandırıyoruz.

Bu tabloları saklamak için gereken alan

2 × 2 × 26 = 104 bayt

tır.

Eşleme adımında rastgele üretilen (T₁) ve (T₂) tablolarının içeriklerinin Fig. 4(a)'da gösterildiği gibi olduğunu, kullanılmayan harflerin ise çıkarıldığını varsayalım.

Buna göre her anahtar için ona karşılık gelen kenarı hesaplarız. Böylece:

f₁(jan) := (T₁(2,a) + T₁(3,n)) mod 25 = (11 + 1) mod 25 = 5

f₂(jan) := (T₂(2,a) + T₂(3,n)) mod 25 = (5 + 7) mod 25 = 12

f₁(feb) := (13 + 9) mod 25 = 22

f₂(feb) := (21 + 9) mod 25 = 5

f₁(mar) := (11 + 1) mod 25 = 12

f₂(mar) := (5 + 17) mod 25 = 22

Son kenar bir çevrimi (5, 12, 22) kapatmıştır ve mevcut (T₁) ve (T₂) tablo içerikleriyle kalan anahtarlar için kenarları hesaplamaya devam etmenin bir anlamı yoktur.

Figure 4: Eşleme tablolarının içerikleri: (a) ilk yineleme sırasında; (b) ikinci yineleme sırasında.

algorithm [2] to do so. This results in a theoretically inferior solution, as the best set union algorithms have worst-case complexity O(n + m α(n, n)), where α(n, n) is the functional inverse of Ackermann's function. However, linear time performance of set union algorithms is expected on the average [24, 2, 31], and, as the authors of [2] point out, “for all practical purposes, α(m, n) is a constant no larger than four.”

Çevrim nedeniyle eşleme işlemi tekrar edilmelidir. İkinci yinelemede üretilen T tablolarının içerikleri Fig. 4(b)'de gösterilmiştir. Bu kez eşleme işlemi Fig. 5'te gösterilen çevrimsiz bir grafiğe yol açar.

Atama adımında her bağlı bileşen için bir köşe seçer ve ona 0 değerini veririz. Daha sonra bileşen üzerinde standart bir arama gerçekleştirerek diğer köşelere karşılık gelen değerleri hesaplarız.

0 köşesinden başlarız, dolayısıyla g(0) := 0. Önce sağ dalı incelediğimizi varsayalım. Buna göre

g(17) := (1 − g(0)) mod 12 = 1,

g(?) := (8 − g(17)) mod 12 = 7,

g(18) := (4 − g(?)) mod 12,

g(7) := (5 − g(?)) mod 12 = 10.

Daha sonra 0 köşesine döndükten sonra sol dalı inceleriz. Burada

g(13) := (6 − g(0)) mod 12 = 6,

g(4) := (0 − g(13)) mod 12 = 6,

g(22) := (3 − g(4)) mod 12

olarak ayarlanır.

Böylece en büyük bileşen için atama adımı tamamlanır. Aynı yöntem kalan bileşenlere uygulanır. Şu değerlerin uygun olduğu kolayca görülebilir:

g(8) = 0,

g(10) = 10,

g(1) = 1,

g(11) = 0,

g(21) = 2,

g(14) = 0,

g(16) = 7,

g(20) = ?

Bu aşama karma fonksiyonunun üretim sürecini tamamlar.

Şimdi örneğin nov için karma tablo adresini hesaplamak üzere

f₁(nov) := (7 + 1) mod 25 = 8

ve

f₂(nov) := (11 + 24) mod 25 = 10

hesaplanır.

Buna göre nov için karma tablo adresi

(g(8) + g(10)) mod 12 = (0 + 10) mod 12 = 10

olur.

Ek bir işlem yapmadan ayrıca nov anahtarının yılın 10 + 1 = 11'inci ayı olduğunu da elde etmiş oluruz.

Figure 5: Eşleme adımının ikinci yinelemesinde elde edilen grafik.

5 Deneysel Sonuçlar

Yeni algoritma, herhangi bir özel iyileştirme yapılmadan C dilinde gerçekleştirildi. Tüm deneyler, SunOS işletim sistemi çalıştıran bir Sun SPARCstation 2 üzerinde yürütüldü. Sonuçlar Tablo 1’de özetlenmiştir.

Algoritma için üretilen tabloda yer alan bir giriş şu şekilde elde edilmiştir: belirtilen her m (kelime sayısı) için 250 rastgele kelime kümesi seçilmiştir. Tablo girişleri bu 250 denemenin ortalamalarını temsil eder.

Kelimeler, bir sözlükte bulunan 24.682 kelime arasından seçildi. Sözlük, standart Unix sözlüğünden 3 karakterden kısa, 18 karakterden uzun veya harf dışı karakterler içeren tüm kelimelerin çıkarılmasıyla elde edildi. Her deney için kelimeler shuffling [23] kullanılarak seçildi. m > 24.682 olduğunda, yapay rastgele kelime kümeleri üretildi.

m, iterations, mapping, assignment ve total değerleri sırasıyla kelime sayısını, eşleme adımındaki ortalama yineleme sayısını, eşleme adımı için geçen süreyi, atama adımı için geçen süreyi ve algoritmanın toplam çalışma süresini ifade eder. Tüm süreler saniye cinsindendir.

Deneysel sonuçlar kuramsal değerlendirmeleri tamamen desteklemektedir. Ayrıca yeni algoritmanın zaman gereksinimleri oldukça düşüktür. Ortalama yineleme sayısının, kuramın gösterdiği gibi yaklaşık 8/3’e eşit olduğuna dikkat edin. Benzer şekilde, mapping, assignment ve total süreleri m ile yaklaşık doğrusal biçimde artmaktadır.

[16]’da verilen zamanlama sonuçlarıyla yapılan karşılaştırma, bu algoritmanın orada verilenden çok daha hızlı olduğunu göstermektedir. Örneğin, onların algoritması bir Sequent makinesi üzerinde 524.288 anahtar için minimal perfect hash function üretmek amacıyla 763.07 saniye sürmüştür.

Algoritmanın gerçekleştirilmesinde grafiklerin kenar yönelimli bir gösterimini kullandık [11]. Bu yaklaşım, kenarları köşe çiftleri olarak değil, tamsayılarla temsil edilen somut nesneler olarak ele almamıza olanak sağladı. Bu nedenle algoritmanın alan karmaşıklığı da kelime sayısına göre doğrusaldır ve sabit katsayısı oldukça küçüktür.

Tablo 1: Deneysel sonuçlar

• m = 512, iterations = 1.704, mapping = 0.037, assignment = 0.010, total = 0.047
• m = 1024, iterations = 1.684, mapping = 0.052, assignment = 0.020, total = 0.072
• m = 2048, iterations = 1.776, mapping = 0.095, assignment = 0.037, total = 0.132
• m = 4096, iterations = 1.676, mapping = 0.160, assignment = 0.067, total = 0.236
• m = 8192, iterations = 1.668, mapping = 0.320, assignment = 0.142, total = 0.463
• m = 16384, iterations = 1.680, mapping = 0.628, assignment = 0.293, total = 0.921
• m = 24682, iterations = 1.688, mapping = 0.950, assignment = 0.444, total = 1.394
• m = 32768, iterations = 1.636, mapping = 1.353, assignment = 0.587, total = 1.940
• m = 65536, iterations = 1.656, mapping = 2.718, assignment = 1.198, total = 3.916
• m = 131072, iterations = 1.676, mapping = 5.448, assignment = 2.416, total = 7.864
• m = 262144, iterations = 1.768, mapping = 11.273, assignment = 4.813, total = 16.087
• m = 524288, iterations = 1.736, mapping = 22.493, assignment = 10.414, total = 32.907

6 Sonuçlar

Sıralamayı koruyan minimal perfect hash function üretmeye yönelik yeni bir algoritma geliştirilmiştir. Algoritmanın beklenen zaman karmaşıklığı O(m)’dir; dolayısıyla algoritma zaman açısından optimaldir. Alan karmaşıklığı da optimal olup, n bir kelime içine sığdığı sürece c m log m + O(1) log n bit ya da c m + O(1) kelime biçimindedir.

Dikkat edilirse W’nin i’inci kelimesi hash tablosunun (i − 1)’inci konumuna yerleştirilir; dolayısıyla üretilen hash fonksiyonu girişteki kelimelerin sırasını korur. Bu durum, kelimelerin istenilen biçimde düzenlenmesine olanak tanır ve bazı uygulamalarda yararlı olabilir.

Üretilen fonksiyon hızlı bir şekilde hesaplanabilir ve onu depolamak için gereken alan m(2 + ε), ε > 0 kadar küçük yapılabilir. Kapsamlı deneysel sonuçlar kuramsal sonuçları doğrulamıştır. Ayrıca, yeni algoritmanın zaman gereksinimlerinin, çok büyük kümeler için bile oldukça düşük olduğunu göstermiştir.

7 Teşekkür

Acyclic graph üretme olasılığının hesaplanmasına yardımcı olduğu için University of Melbourne’dan Nick Wormald’a teşekkür ederiz. Ayrıca sunumun iyileştirilmesine katkı sağlayan değerli yorumları için anonim hakemlere de teşekkür ederiz.

İkinci yazar kısmen Australian Research Council A40030651 numaralı proje tarafından desteklenmiştir.

Kaynaklar

[1] B. Bollobás. Random Graphs. Academic Press, London, Orlando, San Diego, New York, Toronto, Montreal, Sydney, Tokyo, 1985.

[2] B. Bollobás ve I. Simon. Ayrık küme birleştirme algoritmalarının beklenen davranışı üzerine. 17th Annual ACM Symposium on Theory of Computing (STOC'85) içinde, sayfa 224–231, Mayıs 1985.

[3] M. D. Brain ve A. L. Tharp. Büyük kelime kümeleri için near‑perfect hashing. Software—Practice and Experience, 11:667–678.

[4] M. D. Brain ve A. L. Tharp. Seyrek matris paketleme kullanarak perfect hashing. Information Systems, 15(3):281–290.

[5] N. Cercone, J. Boates ve M. Krause. Perfect hash fonksiyonlarını bulmaya yönelik etkileşimli bir sistem. IEEE Software, 2(6):38–53, 1985.

[6] C. C. Chang. Sıralı bir minimal perfect hashing şemasının incelenmesi. Communications of the ACM, 27(4):384–387, Nisan 1984.

[7] C. C. Chang ve R. C. T. Lee. Harf yönelimli bir minimal perfect hashing şeması. The Computer Journal, 29(3):277–281, Haziran 1986.

[8] R. J. Cichelli. Minimal perfect hash fonksiyonlarını basit hale getirme. Communications of the ACM, 23(1):17–19, Ocak 1980.

[9] Z. J. Czech ve B. S. Majewski. O(m) zamanda bir minimal perfect hashing fonksiyonu üretme. Archiwum Informatyki.

[10] M. Dietzfelbinger ve F. Meyer auf der Heide. Yeni bir evrensel hash fonksiyonları sınıfı ve gerçek zamanda dinamik hashing. 17th International Colloquium on Automata, Languages and Programming (ICALP'90) içinde, LNCS 443.

[11] J. Ebert. Kenar yönelimli grafik algoritmaları için çok yönlü bir veri yapısı. Communications of the ACM, 30(6):513–515, Haziran 1987.

[12] P. Erdős ve A. Rényi. Rastgele grafiklerin evrimi üzerine. Publicationes Mathematicae, 5:17–61, 1960.

[13] E. Fox, Q. F. Chen, A. Daoud ve L. Heath. Sıralamayı koruyan minimal perfect hash fonksiyonları ve bilgi erişimi. ACM Transactions on Information Systems, 9(2):281–308.

[14] E. Fox, Q. F. Chen ve L. Heath. LEND ve minimal perfect hash fonksiyonları oluşturmak için daha hızlı algoritmalar. Teknik Rapor TR‑92‑2, Virginia Polytechnic Institute and State University.

[15] E. Fox, L. Heath ve Q. F. Chen. Minimal perfect hash fonksiyonlarını bulmak için O(n log n) algoritması. Teknik Rapor TR‑89‑10, Virginia Polytechnic Institute and State University.

[16] E. A. Fox, L. S. Heath, Q. Chen ve A. M. Daoud. Büyük veritabanları için pratik minimal perfect hash fonksiyonları. Communications of the ACM, 35(1):105–121.

[17] M. L. Fredman, J. Komlós ve E. Szemerédi. O(1) en kötü durum erişim süresiyle seyrek bir tabloyu depolama. Journal of the ACM, 31(3):538–544, Temmuz 1984.

[18] G. H. Gonnet ve R. Baeza‑Yates. Handbook of Algorithms and Data Structures. Addison‑Wesley.

[19] M. Gori ve G. Soda. Cichelli’nin perfect hashing yaklaşımına cebirsel bir yaklaşım. BIT, 29(1):205–214.

[20] G. Haggard ve K. Karplus. Minimal perfect hash fonksiyonlarını bulma. ACM SIGCSE Bulletin, 18:191–193.

[21] G. Havas ve B. S. Majewski. Minimal perfect hashing için optimal algoritmalar. Teknik Rapor 234, University of Queensland.

[22] G. Jaeschke. Reciprocal hashing: minimal perfect hashing fonksiyonları üretmek için bir yöntem. Communications of the ACM, 24(12):829–833, Aralık 1981.

[23] D. E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison‑Wesley.

[24] D. E. Knuth ve A. Schönhage. Basit bir eşdeğerlik algoritmasının beklenen doğrusal davranışı. Theoretical Computer Science, 6:281–315, 1978.

[25] T. G. Lewis ve C. R. Cook. Dinamik ve statik iç tablolar için hashing. Computer, 21:45–56, 1988.

[26] B. S. Majewski, N. C. Wormald, Z. J. Czech ve G. Havas. Minimal perfect hash fonksiyonları için bir üreteç ailesi. Teknik Rapor 16, DIMACS, Rutgers University.

[27] T. J. Sager. Minimal perfect hash fonksiyonları üretmek için yeni bir yöntem. Teknik Rapor CSc‑84‑15, University of Missouri‑Rolla.

[28] T. J. Sager. Minimal perfect hash fonksiyonları için polinom zamanlı bir üretici. Communications of the ACM, 28(5):523–532, Mayıs 1985.

[29] R. E. Tarjan ve J. Van Leeuwen. Küme birleştirme algoritmalarının en kötü durum analizi. Journal of the ACM, 31(2):245–281, Nisan 1984.

[30] V. G. Winters. Polinom zamanda minimal perfect hashing. BIT, 30(2):235–244.

[31] A. C. Yao. Yol sıkıştırma algoritmalarının beklenen performansı üzerine. SIAM Journal on Computing, 14:129–133, Şubat 1985.