Pratik Bir Minimal Mükemmel Hashleme Yöntemi⋆

Fabiano C. Botelho¹, Yoshiharu Kohayakawa² ve Nivio Ziviani¹

¹ Bilgisayar Bilimleri Bölümü, Federal Univ. of Minas Gerais, Belo Horizonte, Brezilya
{fbotelho, nivio}@dcc.ufmg.br

² Bilgisayar Bilimleri Bölümü, Univ. of São Paulo, São Paulo, Brezilya
yoshi@ime.usp.br

Özet

Rastgele graflara dayanan yeni bir algoritma öneriyoruz; bu algoritma minimal mükemmel hash fonksiyonları h oluşturmak için kullanılır. n anahtardan oluşan bir küme için algoritmamız h fonksiyonunu beklenen O(n) zamanda üretir. Herhangi bir x anahtarı için h(x) değerinin hesaplanması iki bellek erişimi gerektirir ve h fonksiyonunun tanımı 1.15n kelime yer kaplar. Bu durum, Czech, Havas ve Majewski tarafından önerilen önceki bir minimal mükemmel hashleme düzenine göre alan gereksinimini %55 seviyesine düşürmektedir.

Basit bir sezgisel yöntem, zaman karmaşıklığındaki sabitin biraz kötüleşmesi pahasına alan gereksinimini 0.93n kelimeye kadar daha da azaltır. Büyük ölçekli deneysel sonuçlar sunulmaktadır.

U anahtarların evreni olsun. h : U → M ifadesi, U evrenindeki anahtarları M = [0, m − 1] = {0, 1, . . . , m − 1} tamsayı aralığına eşleyen bir hash fonksiyonunu göstersin. S ⊆ U, U içinden seçilmiş n anahtardan oluşan bir küme olsun. x ∈ S anahtarı verildiğinde, hash fonksiyonu h, bir hash tablosunda x anahtarının saklanması veya geri alınması için [0, m − 1] aralığında bir tamsayı hesaplar.

Statik olmayan anahtar kümeleri için kullanılan hashleme yöntemleri, S kümesini saklayan veri yapıları oluşturmak ve “x ∈ S?” üyelik sorgularını beklenen O(1) zamanda desteklemek için kullanılabilir. Ancak bu yöntemler, tabloda kullanılmayan konumlar nedeniyle belirli miktarda boşa harcanan alan içerir ve iki anahtar aynı tablo konumuna hashlendiğinde çakışmaları çözmek için ek zaman gerektirir.

Statik anahtar kümeleri için, bir tabloda herhangi bir anahtarı tek bir sorgulama ile bulmayı sağlayan bir fonksiyon hesaplamak mümkündür; bu tür hash fonksiyonlarına mükemmel denir. Bir anahtar kümesi S verildiğinde, h : U → M hash fonksiyonunun S için bir mükemmel hash fonksiyonu olduğunu, eğer h fonksiyonu S üzerinde bire bir ise söyleriz; yani S içindeki anahtarlar arasında çakışma yoktur: x ve y S içinde ve x ≠ y ise, h(x) ≠ h(y) olur. Çakışma olmadığı için her anahtar tablodan tek bir erişimle alınabilir.

Eğer m = n ise, yani tablo S ile aynı boyuta sahipse, o zaman h bir minimal mükemmel hash fonksiyonudur. Minimal mükemmel hash fonksiyonları boşa harcanan alan ve zaman sorununu tamamen ortadan kaldırır.

⋆ Bu çalışma kısmen GERINDO Projesi—hibe MCT/CNPq/CT-INFO 552.087/02-5, CAPES/PROF Bursu (Fabiano C. Botelho), FAPESP Proj. Tem. 03/09925-5 ve CNPq Hibe 30.0334/93-1 (Yoshiharu Kohayakawa) ve CNPq Hibe 30.5237/02-0 (Nivio Ziviani) tarafından desteklenmiştir.

1 Giriş

Minimal mükemmel hash fonksiyonları, statik kümelerden öğelerin bellek açısından verimli biçimde saklanması ve hızlı geri alınması için yaygın biçimde kullanılır. Buna doğal dillerdeki kelimeler, programlama dillerindeki veya etkileşimli sistemlerdeki ayrılmış kelimeler, Web arama motorlarındaki evrensel kaynak konumları (URL'ler) ya da veri madenciliği tekniklerindeki öğe kümeleri örnek verilebilir.

Bu makalenin amacı minimal mükemmel hash fonksiyonları oluşturmanın yeni bir yolunu açıklamaktır. Algoritmamız, Czech, Havas ve Majewski tarafından önerilen yöntemle [4] çeşitli özellikleri paylaşır. Özellikle algoritmamız da rastgele grafların G = (V, E) oluşturulmasına dayanır; burada E, hash fonksiyonunu üretmek istediğimiz anahtar kümesi S ile bire bir karşılık içindedir.

Algoritmamız ile onların yöntemi arasındaki iki temel fark şöyledir:

1. Biz |V| = cn ve |E| = |S| = n olan rastgele graflar G = (V, E) üretiriz; burada c = 1.15 olup bu nedenle G yüksek olasılıkla çevrimler içerir. Onlar ise daha fazla tepe sayısına sahip olacak şekilde çevrimsiz rastgele graflar üretir: |V| = cn, |E| = |S| = n ve |V| ≥ 2.09n.
2. Onlar sıra koruyan minimal mükemmel hash fonksiyonları üretirken, bizim algoritmamız sırayı korumaz (bir mükemmel hash fonksiyonu h, S içindeki anahtarlar belirli bir sıraya göre düzenlenmişse ve h bu sırayı hash tablosunda da koruyorsa sıra koruyandır).

Dolayısıyla algoritmamız, sıra korumayan fonksiyonlar üretme pahasına alan gereksinimini iyileştirir.

Algoritmamız verimlidir ve h fonksiyonunun son derece ekonomik bir tanımını elde edecek şekilde ayarlanabilir. [4]'teki algoritma gibi bizim algoritmamız da n anahtardan oluşan bir küme için h fonksiyonunu beklenen O(n) zamanda üretir. h fonksiyonunun tanımı 1.15n bilgisayar kelimesi gerektirir ve h(x) değerini hesaplamak 1.15n tamsayıdan oluşan bir diziye iki erişim gerektirir.

Ayrıca alan gereksinimini 1.15n kelimeden 0.93n kelimeye düşüren bir sezgisel yöntem de türetiyoruz. Düzenimiz oldukça pratiktir: ortalama uzunluğu 63 bayt olan 100 milyon URL içeren bir koleksiyon için minimal mükemmel hash fonksiyonu üretmek, standart bir PC üzerinde çalışan algoritmamızla ortalama 811 saniye sürmektedir.

Czech, Havas ve Majewski [5], mükemmel hashleme üzerine en önemli kuramsal sonuçların kapsamlı bir incelemesini sunar. Aşağıda bu sonuçların bazılarını gözden geçiriyoruz.

2 İlgili Çalışmalar

Fredman, Komlós ve Szemerédi [10], anahtar sayısıyla doğrusal büyüklükte tablo boyutlarına sahip (m = O(n)) ve sabit zamanda değerlendirilebilen, alan açısından verimli mükemmel hash fonksiyonları oluşturmanın mümkün olduğunu göstermiştir.

Onların hesaplama modelinde, U evreninin bir elemanı tek bir makine kelimesine sığar ve aritmetik işlemler ile bellek erişimlerinin maliyeti birim kabul edilir. FKS modelindeki rastgeleleştirilmiş algoritmalar beklenen O(n) zamanda bir mükemmel hash fonksiyonu oluşturabilir: bu durum bizim algoritmamız ve [4, 14] çalışmalarında da geçerlidir.

Minimal mükemmel hash fonksiyonları üretmek için birçok yöntem eşleme, sıralama ve arama (MOS) yaklaşımını kullanır; bu adlandırma Fox, Chen ve Heath [9] tarafından yapılmıştır. MOS yaklaşımında minimal mükemmel hash fonksiyonunun oluşturulması üç adımda gerçekleştirilir:

1. Eşleme adımı – anahtar kümesini orijinal evrenden yeni bir evrene dönüştürür.
2. Sıralama adımı – anahtarları, hash değerlerinin anahtarlara atanma sırasını belirleyen ardışık bir düzene yerleştirir.
3. Arama adımı – anahtarlara hash değerleri atamayı dener.

Bizim algoritmamız ve [4]'te sunulan algoritma MOS yaklaşımını kullanır.

Pagh [14], minimal mükemmel hash fonksiyonları oluşturmak için rastgeleleştirilmiş algoritmalardan oluşan bir aile önermiştir. Ortaya çıkan fonksiyonun biçimi

h(x) = (f(x) + d g(x)) mod n,

şeklindedir; burada f ve g evrensel hash fonksiyonlarıdır ve d, f fonksiyonunun yol açtığı çakışmaları çözmek için kullanılan bir yer değiştirme değerleri kümesidir. Pagh, f ve g ile ilgili bir dizi koşul tanımlamış ve bu koşullar sağlandığında minimal mükemmel hash fonksiyonunun beklenen O(n) zamanda hesaplanabileceğini ve (2 + ε)n bilgisayar kelimesinde saklanabileceğini göstermiştir.

Dietzfelbinger ve Hagerup [6], [14]'ü geliştirerek alan gereksinimini (2 + ε)n yerine (1 + ε)n bilgisayar kelimesine düşürmüştür; ancak onların yaklaşımında f ve g, ek gereksinimleri karşılayan bir hash fonksiyonları sınıfından seçilmelidir.

[14, 6] çalışmalarından farklı olarak bizim algoritmamız, ek gereksinimlere sahip olması gerekmeyen bir evrensel hash fonksiyonları sınıfından rastgele seçilen iki evrensel hash fonksiyonu h₁ ve h₂ kullanır.

[4]'teki çalışma, sıra koruyan minimal mükemmel hash fonksiyonları üretmek için verimli ve pratik bir algoritma sunar. Bu yöntem |V| = cn ve |E| = n olan çevrimsiz rastgele grafların G = (V, E) oluşturulmasını içerir ve c ≥ 2.09 koşulu sağlanır.

Onlar, G çevrimsiz olduğunda sıra koruyan minimal mükemmel hash fonksiyonunun optimal zamanda bulunabileceğini göstermiştir. Çevrimsiz bir graf üretmek için her x ∈ S anahtarı için iki tepe h₁(x) ve h₂(x) hesaplanır. Böylece her S kümesine karşılık gelen bir graf vardır:

G = (V, E),

burada

V = {0, 1, . . . , t}

ve

E = { {h₁(x), h₂(x)} : x ∈ S }.

G grafının çevrimsiz olmasını garanti etmek için algoritma, karşılık gelen graf çevrimsiz olana kadar h₁ ve h₂ fonksiyonlarını evrensel hash fonksiyonları ailesinden tekrar tekrar seçer.

Havas ve arkadaşları [11], |V(G)| = cn ve c > 2 olduğunda G grafının çevrimsiz olma olasılığının

p = e^{1/c} (c − 2)/c

olduğunu kanıtlamıştır.

c = 2.09 için bu olasılık p ≈ 0.342 olur ve çevrimsiz bir graf elde etmek için beklenen yineleme sayısı 1/p ≈ 2.92'dir.

3 Algoritma

Minimal mükemmel hash fonksiyonu h'nin nasıl oluşturulacağını gösterelim.

İki yardımcı rastgele fonksiyon kullanıyoruz

h₁, h₂ : U → V,

burada V = [0, t − 1] ve uygun şekilde seçilmiş bir t = cn tamsayısıdır; burada n = |S|.

V üzerinde

G = G(h₁, h₂)

şeklinde bir rastgele graf kuruyoruz; bu grafın kenar kümesi

{ {h₁(x), h₂(x)} : x ∈ S }

şeklindedir.

Anahtar kümesi S içindeki her anahtar için G grafında bir kenar bulunur.

Aşağıda, rastgele graf G'nin 2‑çekirdeği ile ilgileneceğiz; yani en az 2 minimum dereceye sahip olan G'nin en büyük altgrafı (bkz. örn. [1, 12]). Bağlamımızdaki önemi nedeniyle 2‑çekirdeğe G'nin kritik altgrafı diyoruz ve Gcrit ile gösteriyoruz.

Gcrit içindeki tepe ve kenarlara kritik denir. Ayrıca

• Vcrit = V(Gcrit)
• Ecrit = E(Gcrit)

tanımlarını yaparız.

Buna ek olarak

• Vncrit = V − Vcrit, G içindeki kritik olmayan tepeler kümesini ifade eder
• Vscrit ⊆ Vcrit, en az bir kritik olmayan komşuya sahip kritik tepeler kümesini ifade eder
• Encrit = E(G) − Ecrit, G içindeki kritik olmayan kenarlar kümesidir

Son olarak

Gncrit = (Vncrit ∪ Vscrit, Encrit)

ifadesi G'nin kritik olmayan altgrafını gösterir.

Kritik olmayan altgraf Gncrit, G'nin “çevrimsiz kısmına” karşılık gelir. Şu ilişki geçerlidir:

G = Gcrit ∪ Gncrit.

Daha sonra G grafının tepeleri için uygun bir

g : V → ℤ

etiketlemesi oluştururuz. Her v ∈ V(G) için g(v) değerini şu koşulu sağlayacak biçimde seçeriz:

h(x) = g(h₁(x)) + g(h₂(x)) (x ∈ S)

ifadesi S için minimal mükemmel hash fonksiyonu olsun.

Daha sonra göreceğiz ki Gcrit içindeki kenar sayısı

½ |E(G)|

değerinden fazla değilse, bu g etiketlemesi doğrusal zamanda bulunabilir.

Şekil 1 algoritmanın sözde kodunu sunmaktadır.

procedure GenerateMPHF (S, g)

1. Eşleme (S, G)
2. Sıralama (G, Gcrit, Gncrit)
3. Arama (G, Gcrit, Gncrit, g)

Şekil 1. Minimal mükemmel hash fonksiyonu oluşturma algoritmasının ana adımları

GenerateMPHF(S, g) yordamı girdi olarak anahtar kümesi S'yi alır ve g etiketlemesini üretir. Yöntem eşleme, sıralama ve arama yaklaşımını kullanır.

3.1 Eşleme Adımı

Mapping(S, G) yordamı girdi olarak anahtar kümesi S'yi alır ve iki yardımcı fonksiyon üreterek

G = G(h₁, h₂)

rastgele grafını üretir:

h₁, h₂ : U → [0, t − 1].

h₁ ve h₂ fonksiyonları şu şekilde oluşturulur. S kümesindeki anahtar uzunlukları için bir üst sınır L belirleriz. hⱼ (j = 1,2) fonksiyonunu tanımlamak için L × Σ boyutunda rastgele tamsayılardan oluşan bir tableⱼ tablosu üretiriz.

Uzunluğu |x| ≤ L olan bir x ∈ S anahtarı ve j ∈ {1, 2} için

hⱼ(x) = ( Σ_{i=1}^{|x|} tableⱼ[i, x[i]] ) mod t

olarak tanımlarız.

Rastgele graf G = G(h₁, h₂), tepe kümesi V = [0, t − 1] ve kenar kümesi

{ {h₁(x), h₂(x)} : x ∈ S }

olan bir graftır.

G'nin basit olması gerekir; yani döngüler veya çoklu kenarlar içermemelidir.

• Bir döngü, bazı x ∈ S için h₁(x) = h₂(x) olduğunda oluşur. Bunu doğrudan şu şekilde çözeriz:

  h₂(x) = (2h₁(x) + 1) mod t.

• Eğer yine bir döngü bulunursa yeni bir (h₁, h₂) çifti üretiriz.

• Bir çoklu kenar oluştuğunda işlemi iptal eder ve yeni bir (h₁, h₂) çifti üretiriz.

Eşleme Adımının Analizi

Öncelikle rastgele graflar hakkında bazı gerçekleri ele alalım. |V| = t ve |E| = n olan G = (V, E) grafı, tüm

C(t,2) choose n

grafların eşit olasılıkla seçildiği G(t, n) uniform modelinde bir rastgele graftır.

G(t, n) modelinin incelenmesi Erdős ve Rényi'nin klasik çalışmalarına [7, 8, 13] kadar uzanır (modern bir inceleme için bkz. [1, 12]).

d = 2n/t

ifadesi G'nin ortalama derecesi olsun. Eğer d > 1 ise (eşdeğer olarak c < 2, çünkü t = cn), neredeyse her G grafının büyüklüğü

(1 + o(1)) b t

olan bir dev bileşen içerdiği iyi bilinir; burada

b = 1 − T/d

ve 0 < T < 1 şu denklemin tek çözümüdür:

T e^{-T} = d e^{-d}.

G'nin diğer tüm bileşenleri O(log t) tepe içerir. Ayrıca dev bileşene ait olmayan 2‑çekirdek içindeki tepe sayısı neredeyse kesin olarak o(t) mertebesindedir.

Pittel ve Wormald [15], dev bileşenin 2‑çekirdeği için ayrıntılı sonuçlar sunar. tableⱼ tabloları (j ∈ {1,2}) rastgele olduğundan G = G(h₁, h₂) de rastgele bir graftır. Bu nedenle G'nin G(t, n) modelinden seçildiğini varsayarız.

[15]'i izleyerek Gcrit grafının tepe ve kenar sayıları

|V(Gcrit)| = (1 + o(1))(1 − T) b t

|E(Gcrit)| = (1 + o(1)) [ (1 − T)b + b(d + T − 2)/2 ] t

şeklindedir ve bu durum neredeyse kesin olarak gerçekleşir.

dcrit = 2|E(Gcrit)| / |V(Gcrit)|

ifadesi Gcrit'in ortalama derecesi olsun. dcrit'in sabit olduğu durumla ilgileniyoruz.

g : V → ℤ etiketlemesini doğrusal zamanda bulabilmek için

|E(Gcrit)| ≤ ½ |S| = n/2

koşulunun sağlanması gerekir.

Kritik adım, t = cn ifadesindeki c değerini öyle belirlemektir ki

|E(Gcrit)| ≤ ½ |E(G)|

olsun.

Deneysel ve kuramsal sonuçlar uygun değerin yaklaşık olarak

c ≈ 1.15

olduğunu göstermektedir.

Tablo 2. Farklı c Değerleri için |E(Gcrit)| ≤ n/2 Olasılığı

Ampirik sonuçlar, c ≥ 1.15 olduğunda |E(Gcrit)| ≤ n/2 olasılığının n büyüdükçe 1'e yaklaştığını göstermektedir.

Şimdi kısaca, t = cn ve c = 1.15 için basit bir graf G = G(h₁, h₂) elde etmek için gereken beklenen yineleme sayısının sabit olduğunu savunuyoruz.

p, döngü veya çoklu kenar içermeyen bir rastgele graf üretme olasılığı olsun. Eğer p pozitif bir sabit ile aşağıdan sınırlanmışsa, böyle bir graf elde etmek için gereken beklenen yineleme sayısı

1/p = O(1)

olur.

p değerini tahmin etmek için, büyüklüğü

C(t,2) ≈ c² n² / 2

olan bir evrenden bağımsız olarak n nesne çekildiğinde n farklı nesne elde etme olasılığını tahmin ederiz.

n → ∞ iken e^{-(n^2)/(t^2)} → e^{-1/c^2} > 0 olduğundan beklenen yineleme sayısı e^{1/c^2} = 2.13 olur (burada c = 1.15). Beklenen yineleme sayısı O(1) olduğundan eşleme adımı O(n) zaman alır.

3.2 Sıralama Adımı

Ordering (G, Gcrit, Gncrit) yordamı girdi olarak G grafını alır ve G'yi iki altgraf olan Gcrit ve Gncrit'e böler; böylece

G = Gcrit ∪ Gncrit

olur.

Bunun için yordam, derece 1 olan tüm tepeleri işlem tamamlanana kadar yinelemeli olarak kaldırır.

Şekil 2(a), 9 tepe ve 8 kenardan oluşan örnek bir grafı göstermektedir; burada her tepenin derecesi yanında belirtilmiştir. Bu graf üzerinde sıralama adımı uygulandığında Şekil 2(b)'de gösterilen 5 tepeli graf elde edilir. Derecesi 0 olan tüm tepeler kritik olmayan tepelerdir, diğerleri ise kritik tepelerdir.

Vscrit içindeki tepeleri belirlemek için v ∈ V(Gcrit) olan ve Adj(v) kümesinde yer alan komşularından en az biri V(Gncrit) içinde bulunan tüm v tepelerini toplarız; Şekil 2(b)'deki 8 numaralı tepe buna bir örnektir.

Sıralama Adımının Analizi

Sıralama adımının zaman karmaşıklığı

O(|V(G)|)

( bkz. [5] ). |V(G)| = t = cn olduğundan, sıralama adımı O(n) zaman alır.

3.3 Arama Adımı

Arama adımında temel kısım mükemmel atama problemidir: şu şekilde bir

g : V(G) → Z

fonksiyonu bulunmalıdır ki

h : E(G) → Z

fonksiyonu

h(e) = g(a) + g(b)
(e = {a, b})

şeklinde tanımlandığında, E(G)'den [0, n − 1] aralığına bir bijeksiyon olsun (n = |S| = |E(G)| olduğunu hatırlayın).

Amacımız, G = G(h1, h2) grafının köşeleri için g : V → Z etiketlemesini bulmaktır; öyle ki S kümesindeki x ve y anahtarları için

g(h1(x)) + g(h2(x)) ≠ g(h1(y)) + g(h2(y)).

Başka bir deyişle, her kenara uç noktalarındaki etiketlerin toplamını atarsak, bu değerlerin tümü birbirinden farklı olmalıdır. Ayrıca tüm g(h1(x)) + g(h2(x)) toplamlarının (x ∈ S) 0 ile |E(G)| − 1 = n − 1 arasında olmasını isteriz; böylece S ile [0, n − 1] arasında bir bijeksiyon elde edilir.

Searching (G, Gcrit, Gncrit, g) yordamı, giriş olarak G, Gcrit ve Gncrit'i alır ve her v ∈ V(G) köşesi için log₂|V(G)| + 1 bitlik uygun bir değer bulur; bu değerler g dizisinde saklanır.

Bu adım önce G grafının kritik altgrafı Gcrit (G'nin 2‑çekirdeği) içindeki köşeler için, ardından Gncrit içindeki köşeler için gerçekleştirilir (Gncrit, G'nin “çevrimsiz kısmını” içeren kritik olmayan altgrafıdır). g değerlerinin atamasının önce Gcrit içindeki köşelerde yapılmasının nedeni, yeniden atamaları mümkün olduğunca erken çözmektir (bu tür yeniden atamalar Gcrit içindeki çevrimlerin sonucudur).

Kritik Köşelere Değer Atanması

Gcrit içindeki köşelerin etiketleri g(v) (v ∈ V(Gcrit)), açgözlü bir strateji izlenerek artan sırada atanır; burada kritik köşeler v, Gcrit üzerinde yapılan bir genişlik öncelikli aramaya göre teker teker ele alınır.

Eğer g(v) için aday bir x değeri yasaklıysa (yani g(v) = x yapılması iki kenarın aynı toplamı üretmesine neden olacaksa), g(v) için x + 1 denenir. Bu duruma yeniden atama adı verilir.

AE, E(Gcrit) içindeki kenarlara atanmış adreslerin kümesi olsun. Başlangıçta:

AE = ∅

x, g(v) için aday değer olsun. Başlangıçta x = 0.

Şekil 2(b)'deki Gcrit altgrafı dikkate alınarak, Gcrit içindeki köşelere değer atanmasının adım adım bir örneği Şekil 3'te sunulmuştur.

Başlangıçta bir v köşesi seçilir, g(v) = x ataması yapılır ve x değeri x + 1 olarak güncellenir. Örneğin 8 numaralı köşenin seçildiğini varsayalım. g(8) = 0 ataması yapılır ve x değeri 1 olur.

8 köşesinin komşuluk listesi izlenerek atanmamış 0 köşesine ulaşılır. Bu noktada, geçici Y değişkeninde 0 köşesinin x değeri atanmış tüm komşulukları toplanır ve Y = {8} olur.

Ardından tüm u ∈ Y için g(u) + x ∉ AE olup olmadığı kontrol edilir. Çünkü

g(8) + 1 = 1 ∉ AE,

bu durumda g(0) = 1 yapılır, x değeri 2'ye artırılır ve

AE = AE ∪ {1} = {1}.

Daha sonra 3 köşesine ulaşılır, g(3) = 2 yapılır, x değeri 3 olur ve

AE = AE ∪ {2} = {1, 2}.

Ardından 4 köşesine ulaşılır ve Y = {3, 8}. Çünkü

g(3) + 3 = 5 ∉ AE

ve

g(8) + 3 = 3 ∉ AE,

bu durumda g(4) = 3 yapılır, x değeri 4 olur ve

AE = AE ∪ {3, 5} = {1, 2, 3, 5}.

Son olarak 7 köşesine ulaşılır ve Y = {0, 8}. Çünkü

g(0) + 4 = 5 ∈ AE,

x değeri 5'e artırılır. Çünkü

g(8) + 5 = 5 ∈ AE,

x değeri tekrar 6'ya artırılır. Bu iki yeniden atama Şekil 3'te oklarla gösterilmiştir.

Çünkü

g(0) + 6 = 7 ∉ AE

ve

g(8) + 6 = 6 ∉ AE,

bu durumda g(7) = 6 yapılır ve

AE = AE ∪ {6, 7} = {1, 2, 3, 5, 6, 7}.

Böylece algoritma tamamlanır.

Kritik Olmayan Köşelere Değer Atanması

Gncrit çevrimsiz olduğundan, Gncrit içindeki kenarlara hangi sırayla adreslerin atanacağını belirleyebiliriz; bu da bu adımın standart bir derinlik öncelikli arama algoritmasıyla kolayca çözülmesini sağlar.

Dolayısıyla Gncrit içindeki köşelere değer atanırken, Gcrit içindeki köşelere değer atanması sırasında kullanılmayan adreslerin bıraktığı boşluklardan yararlanılır. Bunun için derinlik öncelikli aramaya Vscrit içindeki köşelerden başlanır; çünkü bu kritik köşeler için g değerleri zaten atanmıştır ve değiştirilemez.

Şekil 2(b)'deki Gncrit altgrafı dikkate alınarak, Gncrit içindeki köşelere değer atanmasının adım adım bir örneği Şekil 4'te gösterilmiştir.

Şekil 4(a) algoritmanın başlangıç durumunu göstermektedir. Kritik köşe 8, kritik olmayan komşulara sahip tek köşedir. Önceki örnekte {0, 4} adresleri kullanılmamıştı. Kullanılmayan ilk adres 0 ve 8 köşesinden ulaşılan 1 köşesi alınarak

g(1) = 0 − g(8) = 0

atanır.

1 köşesinden ulaşılan tek köşe 2 köşesidir. Kullanılmayan adres 4 alınarak

g(2) = 4 − g(1) = 4

atanır.

Bu süreç UnAssignedAddresses listesi boşalana kadar tekrarlanır.

Arama Adımının Analizi

Şunları göstereceğiz:

1. Bir kenara atanan en büyük değer en fazla n − 1'dir (yani minimal mükemmel hash fonksiyonu elde edilir).
2. Eğer Gcrit içindeki kenar sayısı en fazla (1/2)|E(G)| ise, mükemmel atama problemi (g'nin belirlenmesi) beklenen O(n) zamanda çözülebilir.

Kritik olmayan köşelere değer atanması derinlik öncelikli arama algoritmasıyla doğrusal zamanda çözülebildiğinden, analizde kritik köşelere değer atanmasına odaklanıyoruz.

I(v), g(v) için aday değer x'in kaç kez artırıldığını göstersin. Nt, aday değer x'in artırıldığı toplam sayıyı göstersin. Dolayısıyla

Nt = Σ I(v)

burada toplam tüm v ∈ V(Gcrit) için alınır.

Basitlik açısından Gcrit'in (G'nin 2‑çekirdeğinin) bağlı olduğunu varsayalım.

Her kenarın ya bir ağaç kenarı ya da bir geri kenar olması şu sonucu verir.

Teorem 1. G = Gcrit ∪ Gncrit grafındaki geri kenarların sayısı Nbedges

Nbedges = |E(Gcrit)| − |V(Gcrit)| + 1.

Bir Kenara Atanan En Büyük Değer

Teorem 2.

Amax ≤ 2|V(Gcrit)| − 3 + 2Nt.

İspat (Özet). Kritik köşelere g değerlerinin atanması 0'dan başlar ve her kenar e daha önce verilen şekilde h(e) etiketi alır. V(Gcrit) içindeki her v köşesi için g değeri yalnızca bir kez atanır.

Biraz düşününce şu görülür:

max_v g(v) ≤ |V(Gcrit)| − 1 + Nt.

Ayrıca iki farklı köşe farklı g değerleri alır. Dolayısıyla

Amax ≤ (|V(Gcrit)| − 1 + Nt) + (|V(Gcrit)| − 2 + Nt)

≤ 2|V(Gcrit)| − 3 + 2Nt.

Varsayım

Varsayım 1. |E(Gcrit)| ≤ n/2 ve |V(G)| = 1.15n olan rastgele bir G grafı için, e ∈ E(Gcrit) kenarına atanan en büyük değer Amax en fazla n − 1 olduğundan, her zaman minimal mükemmel hash fonksiyonu üretmek mümkündür.

Şimdilik Nt ≤ Nbedges olduğunu varsayalım. O halde Teorem 1 ve 2'den:

Amax ≤ 2|V(Gcrit)| − 3 + 2Nt

≤ 2|V(Gcrit)| − 3 + 2Nbedges

≤ 2|V(Gcrit)| − 3 + 2(|E(Gcrit)| − |V(Gcrit)| + 1)

≤ 2|E(Gcrit)| − 1.

Varsayıma göre |E(Gcrit)| ≤ n/2 olduğundan Amax ≤ n − 1 elde edilir.

Algoritmanın matematiksel analizinde açık kalan nokta şu eşitsizliği kanıtlamaktır:

Nt ≤ Nbedges.

Deneysel Kanıt

c = 1.15 için beklenen değerler dikkate alındığında:

• |V(Gcrit)| ≈ 0.401n
• |E(Gcrit)| ≈ 0.501n

Teorem 1'e göre:

Nbedges = 0.501n − 0.401n + 1 = 0.1n + 1.

S'nin farklı büyüklükleri için algoritmanın 10.000 çalıştırılması sırasında elde edilen en büyük Nt değeri aşağıda gösterilmiştir.

Nt'nin en büyük değeri her zaman Nbedges = 0.1n + 1 değerinden küçük olmuş ve n ≥ 1,000,000 için 0.059n değerine yaklaşmıştır.

Zaman Karmaşıklığı

Şimdi tüm kritik köşeler v ∈ V(Gcrit) için g(v) belirleme işleminin zaman karmaşıklığının

O(|V(Gcrit)|) = O(n)

olduğunu göstereceğiz.

Her atanmamış v köşesi için, daha önce değer atanmış komşu köşelerden oluşan Y kümesini toplamak amacıyla Adj(v) komşuluk listesi dolaşılmalıdır. Daha sonra Y içindeki her köşe için mevcut aday değer x'in yasaklı olup olmadığı kontrol edilir. Son olarak v ile u arasındaki kenar (tüm u ∈ Y için) uç noktalarının toplamına karşılık gelen adresle ilişkilendirilir.

Gcrit'in ortalama derecesi

dcrit = 2|E(Gcrit)| / |V(Gcrit)|

olsun.

Zaman karmaşıklığı

C(|V(Gcrit)|) = Σ_{v ∈ V(Gcrit)} ( |Adj(v)| + (I(v) × |Y|) + |Y| )

≤ Σ_{v ∈ V(Gcrit)} (2 + I(v)) |Adj(v)|

= 4|E(Gcrit)| + O(Nt dcrit).

çünkü

dcrit ≈ 2 × 0.501n / 0.401n ≈ 2.499

(sabit bir değerdir), dolayısıyla O(|E(Gcrit)|) = O(|V(Gcrit)|) elde edilir.

Nt ≤ Nbedges varsayımı altında şu sonuca ulaşırız:

C(|V(Gcrit)|) = O(|E(Gcrit)|) = O(|V(Gcrit)|).

|V(Gcrit)| ≤ |V(G)| ve |V(G)| = cn olduğundan, kritik köşelerde g değerini belirlemek için gereken süre O(n)'dir.

4 Deneysel Sonuçlar

Deneyler hem önerilen algoritma hem de Czech, Havas ve Majewski tarafından geliştirilen ve CHM algoritması olarak adlandırılan algoritma [4] ile gerçekleştirilmiştir.

Her iki algoritma da C dilinde uygulanmış olup şu adreste mevcuttur:

http://cmph.sf.net

Veri kümesi, Web'den toplanmış 100 milyon URL içeren bir koleksiyondan oluşmaktadır. Bir URL'nin ortalama uzunluğu 63 bayttır. Tüm deneyler Linux 2.6.7 çalıştıran, 2.4 GHz işlemciye ve 4 GB RAM'e sahip bir bilgisayarda gerçekleştirilmiştir.

Algoritmaların Temel Özellikleri

| Algorithm | c | |E(G)| | |V(G)| = |g| | |E(Gcrit)| | Graph G | Order preserving | |---|---|---|---|---|---|---| | Our algorithm | 1.15 | n | cn | 0.5|E(G)| | cyclic | no | | CHM algorithm | 2.09 | n | cn | 0 | acyclic | yes |

G grafındaki köşe sayısı bizim algoritmamız için 1.15n, CHM algoritması için 2.09n'dir. Bu durum, fonksiyonun saklanması için gereken alanı bizim algoritmamızda CHM algoritmasının gerektirdiği alanın %55'ine düşürür.

Zaman Ölçümleri

Tüm süreler saniye cinsindedir. Değerler 50 denemenin ortalamasıdır.

Yeni algoritmanın eşleme adımı daha hızlıdır; çünkü G grafını oluşturmak için beklenen yineleme sayısı bizim algoritmamızda 2.13, CHM algoritmasında ise 2.92'dir.

Bizim algoritmamızın ürettiği graf 1.15n köşe içerirken, CHM algoritmasının grafı 2.09n köşe içerir; bu da eşleme adımını daha hızlı hale getirir.

Bizim algoritmamızdaki sıralama adımı, CHM algoritmasında G grafının çevrimsiz olup olmadığını kontrol etmek için gereken süreye yaklaşık olarak eşittir. CHM algoritmasının arama adımı daha hızlıdır; ancak toplam çalışma süresi ortalama olarak yaklaşık %58 daha hızlıdır.

Deneysel sonuçlar teorik analizi güçlü biçimde desteklemektedir. Özellikle her iki algoritma için de arama adımı belirgin biçimde doğrusal davranış göstermektedir.

Son olarak bir sezgisel yöntem, bellek gereksinimini 1.15n kelime ile 0.93n kelime arasında herhangi bir değere düşürebilir. Bu sezgisel yöntem, mümkün olduğunda x + 1 denemeden önce yeniden atamalara neden olmuş x değerleri kümesini yeniden kullanır.

Alt sınır c = 0.93 deneysel olarak elde edilmiştir. Her n değeri için (n = 10^5, 5×10^5, 10^6, 2×10^6) 10.000 rastgele graf üreterek yapılan denemelerde, c = 0.93 için her zaman h üretmeyi başardık, ancak c = 0.92 için hiçbir zaman başarılı olamadık.

Tablo 5. Bizim algoritmamız ve CHM algoritması için zaman ölçümleri

Pratik Bir Minimal Mükemmel Hash Yöntemi

c değerinin azaltılması, G grafını oluşturmak için gereken yineleme sayısının artmasına yol açar. Örneğin c = 1 ve c = 0.93 için analitik beklenen yineleme sayıları sırasıyla 2.72 ve 3.17'dir (n = 12,500,000 için yineleme sayıları c = 1 için 2.78, c = 0.93 için 3.04'tür). Tablo 6, n = 12,500,000 için bir fonksiyon oluşturmanın toplam sürelerini göstermektedir; süre c = 1.15 için 86.31 saniye (Tablo 5'e bakınız) iken, c = 1 için 101.74 saniyeye ve c = 0.93 için 102.19 saniyeye yükselir.

Tablo 6. c = 1.00 ve c = 0.93 için ayarlanmış algoritmamızın zaman ölçümleri

Algoritmamızı ayrıca Pagh [14] ile Dietzfelbinger ve Hagerup [6] tarafından önerilen algoritmalarla karşılaştırdık. Yazarlar bize kaynak kodlarını gönderdi. Onların uygulamasında anahtar kümesi rastgele tamsayılardan oluşmaktadır. Adil bir karşılaştırma yapmak için uygulamamızı, h fonksiyonunu rastgele tamsayılardan oluşan bir kümeden üretilecek şekilde değiştirdik. 10⁶ rastgele tamsayıdan oluşan bir küme için minimal mükemmel hash fonksiyonu üretme süreleri bizim algoritmamız, Pagh algoritması ve Dietzfelbinger–Hagerup algoritması için sırasıyla 2.7 s, 4 s ve 4.5 s olmuştur. Buna göre algoritmamız ortalama olarak Pagh algoritmasından %48, Dietzfelbinger ve Hagerup algoritmasından ise %67 daha hızlıdır. Bu kazanç farklı büyüklükteki kümeler için de korunmuştur.

Bizim algoritmamız, elde edilen fonksiyonu saklamak için kn (k ∈ [0.93, 1.15]) kelime gerektirir; Pagh algoritması kn (k > 2) kelime, Dietzfelbinger ve Hagerup algoritması ise kn (k ∈ [1.13, 1.15]) kelime gerektirir. Fonksiyonların üretilme süresi k değerine ters orantılıdır.

5 Sonuç

Statik kümeler için minimal mükemmel hash fonksiyonları oluşturmak amacıyla verimli olan ve oldukça ekonomik bir temsil sağlayacak şekilde ayarlanabilen pratik bir yöntem sunulmuştur.

Kaynaklar

1. B. Bollobás. Random Graphs, Cambridge Studies in Advanced Mathematics serisinin 73. cildi. Cambridge University Press, Cambridge, ikinci baskı, 2001.

2. B. Bollobás ve O. Pikhurko. İkili farkları birbirinden farklı olacak şekilde belirlenmiş tamsayı kümeleri. European Journal of Combinatorics. Yayınlanacaktır.

3. T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein. Introduction to Algorithms. MIT Press, ikinci baskı, 2001.

4. Z. J. Czech, G. Havas ve B. S. Majewski. Minimal mükemmel hash fonksiyonları üretmek için optimal bir algoritma. Information Processing Letters, 43(5):257–264, 1992.

5. Z. J. Czech, G. Havas ve B. S. Majewski. Mükemmel hashing üzerine temel çalışma. Theoretical Computer Science, 182:1–143, 1997.

6. M. Dietzfelbinger ve T. Hagerup. Daha az alan kullanan basit minimal mükemmel hashing. The 9th European Symposium on Algorithms (ESA) içinde, Lecture Notes in Computer Science serisi 2161. cilt, sayfa 109–120, 2001.

7. P. Erdős ve A. Rényi. Rastgele graflar üzerine I. Publ. Math. Debrecen, 6:290–297, 1959.

8. P. Erdős ve A. Rényi. Rastgele grafların evrimi üzerine. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17–61, 1960.

9. E. A. Fox, Q. F. Chen ve L. S. Heath. Minimal mükemmel hash fonksiyonları oluşturmak için daha hızlı bir algoritma. Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval içinde, sayfa 266–273, 1992.

10. M. L. Fredman, J. Komlós ve E. Szemerédi. En kötü durumda O(1) erişim süresiyle seyrek bir tabloyu saklama. J. ACM, 31(3):538–544, Temmuz 1984.

11. G. Havas, B. S. Majewski, N. C. Wormald ve Z. J. Czech. Grafikler, hipergrafikler ve hashing. 19th International Workshop on Graph-Theoretic Concepts in Computer Science içinde, sayfa 153–165. Springer Lecture Notes in Computer Science, cilt 790, 1993.

12. S. Janson, T. Łuczak ve A. Ruciński. Random Graphs. Wiley-Interscience, 2000.

13. P. Erdős ve A. Rényi. Rastgele bir grafın bağlantılılık gücü üzerine. Acta Mathematica Scientia Hungary, 12:261–267, 1961.

14. R. Pagh. Hash and displace: Minimal mükemmel hash fonksiyonlarının verimli değerlendirilmesi. Workshop on Algorithms and Data Structures içinde, sayfa 49–54, 1999.

15. B. Pittel ve N. C. Wormald. Bağlantılı grafikleri içten dışa sayma. Journal of Combinatorial Theory. Yakında yayımlanacak.