Mükemmel Hashleme İçin Grafik Kuramsal Engeller

George Havas ve Bohdan S. Majewski

Mükemmel hash fonksiyonları üretmek için yarı‑rastgele graflara dayanan bir dizi algoritma yayımlanmıştır. Bunlar arasında Sager’ın mincycle algoritması, Fox ve arkadaşlarının bunun üzerinde yaptığı bir değişiklik ve son olarak Czech, Havas ve Majewski tarafından geliştirilen olasılıksal yöntemler bulunmaktadır. Bu algoritmaların her biri, grafın iki parçalı olması veya çevrimsiz olması gibi farklı özelliklerinden yararlanır. Bu makalede bu özelliklerin önemini biçimsel olarak gerekçelendiriyoruz. Ayrıca bazı yöntemlerin başarısız olma nedenlerini de gösteriyoruz.

Özellikle bir grafın çevrimsiz olmasının, sıralamayı koruyan mükemmel hash fonksiyonları bulmada kritik bir rol oynadığını gösteriyoruz. Bu, algoritmaların gerçekten bir mükemmel hash fonksiyonu bulması için yeterli fakat gerekli olmayan bir koşuldur. Çeşitli yayımlanmış yöntemlerin başarısız olduğu ve bunu yaparken üstel zaman harcadığı bazı örnekler sunuyoruz. Son olarak, grafik özellikleri üzerine yaptığımız değerlendirmelere dayanarak mükemmel hash fonksiyonları üretmek için bir başka yöntem öneriyoruz.

Bir hash fonksiyonu

h : W → I

şeklinde bir fonksiyondur ve W ⊂ U anahtar kümesini I tamsayı aralığına, örneğin [0, k − 1] aralığına eşler; burada k > 0dır. U, W içindeki anahtarların seçildiği evrendir:

U = {0, . . . , u − 1}

Hash fonksiyonu, verilen bir anahtar için, o öğenin saklanması veya geri getirilmesi amacıyla bir adres (I aralığından bir tamsayı) hesaplar. Öğelerin saklandığı depolama alanı hash tablosu olarak adlandırılır. Aynı adresin hesaplandığı anahtarlar eşanlamlılar (synonyms) olarak adlandırılır.

Eşanlamlıların varlığı nedeniyle, iki anahtarın aynı adrese eşlenmesi durumunda çakışma (collision) adı verilen bir durum ortaya çıkabilir. Çakışmaları çözmek için çeşitli yöntemler bilinmektedir.

Bir mükemmel hash fonksiyonu, şu biçimde bir enjeksiyondur:

h : W → I

burada W ve I yukarıda tanımlanan kümelerdir ve k ≥ m koşulu sağlanır. Eğer k = m ise, h bir minimal mükemmel hash fonksiyonudur. Tanımın da ima ettiği gibi, bir mükemmel hash fonksiyonu W kümesindeki her anahtarı hash tablosunda benzersiz bir adrese dönüştürür. Hiçbir çakışma oluşmadığından, her öğe tablodan tek bir erişimle elde edilebilir.

Eğer W kümesinden herhangi iki anahtar wi ve wj için i < j olması h(wi) < h(wj) sonucunu doğuruyorsa, hash fonksiyonu sıralamayı koruyan (order preserving) özelliğe sahiptir. Başka bir deyişle, giriş kümesindeki göreli sıralama hash tablosunda korunur.

Minimal mükemmel hash fonksiyonları, programlama dillerindeki ayrılmış sözcükler, işletim sistemlerindeki komut adları, doğal dillerde sık kullanılan kelimeler vb. gibi statik bir kümeden öğelerin bellek açısından verimli biçimde saklanması ve hızlı biçimde geri getirilmesi için kullanılır. Mükemmel hashleme hakkında bir genel bakış [GBY91, §3.3.16] içinde verilmiştir ve alan [LC88, HM92] çalışmalarında incelenmiştir.

E‑posta: havas@cs.uq.oz.au
Yazar kısmen Australian Research Council A49030651 numaralı araştırma desteğiyle desteklenmiştir.

E‑posta: bohdan@cs.uq.oz.au

Mükemmel veya minimal mükemmel hash fonksiyonları kurmak için farklı zaman karmaşıklıklarına sahip çeşitli algoritmalar sunulmuştur. Bazıları, muhtemelen en önemlileri, W kümesini bir grafa eşlemeye dayanır; daha sonra bu graf işlenerek bir mükemmel hash fonksiyonu elde edilir.

Bunlar şunları içerir:

• Sager’ın mincycle algoritması [Sag85]
• Fox, Heath, Chen ve Daoud tarafından yapılan değişiklikler [FCHD88, FHC89, FCDH91, FHCD92]
• Czech ve Majewski yöntemi [CM92]
• Czech, Havas, Majewski ve Wormald tarafından geliştirilen olasılıksal yöntemler [CHM92, MWCH92]

Ünlü FKS şeması [FKS84] bile özel bir çevrimsiz graf türünün kurulması ve kodlanması yöntemi olarak görülebilir.

Bu makalede bu yöntemleri inceliyoruz. Özellikle algoritmalar tarafından kullanılan grafların özelliklerine odaklanıyoruz. İki parçalı olma veya çevrimsiz olma gibi özelliklerin mükemmel ve sıralamayı koruyan mükemmel hash fonksiyonlarıyla ilişkili önemini biçimsel olarak gerekçelendiriyoruz. Ayrıca bazı yöntemlerin başarısız olmasının grafik kuramsal bir nedenini belirliyoruz.

Sager’ın, Fox ve arkadaşlarının ve Czech ile Majewski’nin yöntemlerinin başarısız olduğu ve üstel zamanda çalıştığı örnekler sunuyoruz. Son olarak, grafik özellikleri üzerine yaptığımız değerlendirmelere dayanarak mükemmel hash fonksiyonları üretmek için bir başka yöntem öneriyoruz.

Graflar, verilen bir anahtar kümesi için hash tabloları oluştururken, özellikle bu tabloların mükemmel olması gerektiğinde, son derece etkili bir araçtır. Bu yaklaşımı izleyen bazı yöntemlere kısaca bakalım.

Şekil 1: FKS yöntemi. W kümesindeki anahtarlar birincil düğümlere eşlenir. Aynı birincil düğüme eşlenen anahtarlar, bir yıldız yapısı oluşturan benzersiz düğümlere eşlenir. Ortaya çıkan G grafı, W için hash tablosu T’yi tanımlar.

Graf kullanan en erken yöntem Fredman, Komlós ve Szemerédi tarafından yayımlanmıştır [FKS84]. Her ne kadar algoritmalarını grafik kuramı terimleriyle ifade etmemiş olsalar da, bunu yapmak kolaydır.

İlk adımda, m anahtardan oluşan bir küme, derecesi 1 olan bir polinom kullanılarak m birincil düğüme eşlenir:

f1(x) = (kx mod u) mod m

Aynı birincil düğüme eşlenmiş her anahtar grubu için ikinci seviyede bir polinom seçilir:

f2,i(x) = (k'i x mod u) mod 2^(b_i^2)

burada b_i grubun büyüklüğüdür ve 0 ≤ i < m koşulu geçerlidir. İkinci fonksiyon, gruptaki her anahtarı benzersiz bir düğüme eşler. Ortaya çıkan yapı çevrimsiz bir graftır ve Şekil 1’de gösterildiği gibi yıldız biçimli ağaçların birleşiminden oluşur.

Fredman, Komlós ve Szemerédi ortaya çıkan grafı verimli biçimde kodlayan bir yapı sunar ve yapının boyutunu belirleyen düğüm sayısının 11m değerini aşmadığını kanıtlar. m birincil düğüm ikinci seviye polinomların parametrelerini saklamak zorunda olduğundan, yapının toplam boyutu 13m olur.

Fredman, Komlós ve Szemerédi kodlamanın boyutunu azaltmaya olanak tanıyan bazı iyileştirmelerden de bahseder.

FKS’den önemli ölçüde daha az alan kullanan sonraki dört yöntem benzer yaklaşımlar kullanır. Önce bir anahtar kümesi açık biçimde bir grafa eşlenir. Daha sonra, farklı yöntemler kullanarak yazarlar aşağıdaki problemi çözmeye çalışır; biz buna mükemmel atama problemi adını veriyoruz.

Verilen yönsüz bir graf için

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

şu fonksiyonu bulun:

g : V → [0, m − 1]

öyle ki aşağıdaki biçimde tanımlanan fonksiyon

h : E → [0, m − 1]

h(e = (u, v) ∈ E) = (α(e) + g(u) + g(v)) mod m

bir bijeksiyon olsun. α fonksiyonu kenar e’yi bir sabite eşler.

Başka bir ifadeyle, problem düğümlere değerler atanmasını ister; böylece her kenar için uç noktalarına atanan değerlerin toplamı (bir sabit ile birlikte), kenar sayısına göre mod alınarak [0, m − 1] aralığında benzersiz bir tamsayı verir.

Bu yöntemlerin her biri tarafından üretilen bir mükemmel hash fonksiyonu n + O(1) kelime içinde saklanabilir.

Şekil 2: Graf tabanlı bir yöntemle mükemmel hash fonksiyonu hesaplanması. Giriş kümesi W, G grafına eşlenir ve bu graf bazı işlemlerden sonra W anahtarları için hash tablosu T’yi üretir.

Sager’ın mincycle algoritması üç adımdan oluşur.

1. adımda W kümesi bağımlılık grafı (dependency graph) adı verilen bir G grafına eşlenir. Sager düğüm sayısını m/3’ten büyük en küçük 2 kuvvetinin iki katı olarak seçer. Bağımlılık grafı her zaman iki parçalı olacak şekilde oluşturulur. Graf çevrimler içerebilir. Pratikte, yoğunluğu ve Sager tarafından kullanılan eşleme fonksiyonlarının düşük kalitesi nedeniyle, kenarların çoğu bir veya daha fazla çevrimin parçasıdır.

Bir sonraki bölümde göreceğimiz gibi çevrimler, mükemmel atama probleminin çözülemez olmasına neden olabilir ve kesinlikle çözümü zorlaştırır.

Atama problemine çözüm bulmak için Sager, mümkün olan tüm g fonksiyonlarını denemek amacıyla tam kapsamlı arama (exhaustive search) prosedürü kullanır. Aramayı hızlandırmak için algoritmanın ikinci adımında bağımlılık grafının kenarlarına belirli bir sıralama uygulanır. Bu düzenleme, arama prosedürünün mükemmel atama problemini çözmeye çalıştığı sırayı belirler.

Arama başarıyla sonuçlanabilir veya tüm mümkün g fonksiyonları incelendikten sonra başarısızlık rapor edebilir. Sager, sıralama adımının tam kapsamlı aramanın polinom zamanda çalışmasına neden olduğunu savunur. Ancak atama problemine bir çözüm bulunamadığında algoritması üstel zamanda çalışır; çünkü mümkün fonksiyonların sayısı üstel büyüklüktedir.

Fox, Heath, Chen ve Daoud [FHCD92] Sager’ın yöntemine üç önemli değişiklik getirir. Eski fonksiyonlara göre rastgele fonksiyonları daha iyi taklit eden daha iyi eşleme fonksiyonları kullanılır. Sonuç olarak eşleme adımı rastgele grafa daha yakın bir graf oluşturur.

Fox ve arkadaşları grafın iki parçalı özelliğini korur, ancak bunun önemini ayrıntılı biçimde açıklamaz. Sıralama adımı, daha düşük kalitede sonuç üretmesine rağmen makul performans sağlayan daha az zaman harcayan bir yöntem kullanır.

Arama adımında yazarlar, hash tablosunda anahtarların olası bir düzenini belirleyen rastgele “probe sequence”lar üreten olasılıksal bir algoritma kullanır. Fox ve arkadaşlarının algoritması, [FHCD92] içinde tanımlanan biçimiyle, mükemmel atama problemine bir çözüm bulunamadığında üstel zamanda çalışır. Yazarlar, daha sonra tartışılacak olan ve üstel zamanlı aramayı önleyebilecek bir değişiklikten bahseder.

Fox, Heath, Chen ve Daoud düğüm sayısını yaklaşık olarak 0.6m olarak seçer.

Czech ve Majewski [CM92] sıralama adımı için başka bir sezgisel yöntem önerir. Ayrıca tam kapsamlı aramayı değiştirerek verimliliği artırmak amacıyla geri izleme budaması (backtrack pruning) kullanırlar. Bunun dışında yöntemleri Sager ve Fox ve arkadaşlarının yöntemleriyle aynı yolu izler.

Czech, Havas ve Majewski [CHM92] tüm e ∈ E için α(e) = 0 olacak şekilde ayarlar ve G grafının çevrimsiz olmasını şart koşar. n = cm ve c > 2 olduğunda çevrimsiz bir eşleme elde etme olasılığının sıfırdan farklı sabit bir değer olduğunu gösterirler. Dolayısıyla bu işlem olasılıksal bir algoritma ile doğrusal zamanda yapılabilir.

Ayrıca çevrimsiz graflar için doğrusal zamanda g fonksiyonunu bulma yöntemi de sunarlar. G’nin çevrimsiz olması sayesinde ortaya çıkan mükemmel hash fonksiyonu sıralamayı koruyan ve minimal hale getirilebilir.

[MWCH92] çalışmasında yöntemlerini hipergraflara genişletirler. Bu, hash fonksiyonunu değerlendiren programın boyutunun standart graflar durumunda elde edilen programın boyutunun yaklaşık %58’i kadar olmasına olanak tanır.

FKS ve CHM yöntemlerinde kullanılan grafların her iki durumda da çevrimsiz olmasına rağmen bu yöntemlerin eşdeğer olmadığını vurgulamak gerekir. Fredman ve arkadaşları G içindeki her kenar için benzersiz bir düğüm bulunmasını gerektirir. CHM yönteminde bu durum söz konusu değildir ve bu nedenle anahtarları ayırt etmek için g fonksiyonu gibi yardımcı bir araca ihtiyaç duyarız.

CHM yöntemindeki grafların daha yüksek yoğunluğu, ortaya çıkan mükemmel hash fonksiyonunun boyutunda önemli bir küçülme sağlar. Ayrıca çevrimsizlik özelliğinin korunması yöntemi oldukça esnek hale getirir.

Dolayısıyla farklı araştırmacılar mükemmel bir hash fonksiyonu bulma hedeflerine ulaşmak için farklı özelliklerden yararlanır. Bu makalede ele aldığımız soru şudur: bu özellikler ne kadar önemlidir? Bazıları zayıflatılabilir mi ya da bunlardan daha kapsamlı biçimde yararlanarak ek bir kazanç elde edilebilir mi?

Mükemmel Atama Problemi Her Zaman Çözülebilir Değildir

Fredman, Komlós ve Szemerédi yöntemlerinin çalışacağının garanti olduğunu kanıtlamıştır (yöntemlerinin önemli bir dezavantajı nispeten büyük alan gereksinimidir). Bu nedenle biz mükemmel atama problemine odaklanıyoruz.

Bu problem, şaşırtıcı olmayacak şekilde, her zaman çözülemez. Bu bölümde çözümün bulunmadığını kanıtladığımız bazı sonsuz graf sınıflarına örnekler veriyoruz. Basitlik açısından tüm e ∈ E için α(e) = 0 olduğunu varsayıyoruz.

Atama problemine çözüm bulunmayan bir graf için çok basit bir örnek tek çevrimli graf C_{4j+2}, j > 1’dir. Böyle bir graf 4j + 2 kenara ve 4j + 2 düğüme sahiptir. Kenarlara 0 ile m − 1 = 4j + 1 arasındaki sayılar atanır.

Dolayısıyla kenarlara atanan değerlerin toplamı

(4j + 2)(4j + 1)/2 = (2j + 1)(4j + 1)

olur.

Bu sayı açıkça tektir. Öte yandan her düğüm iki kenara komşudur. Dolayısıyla kenar değerlerinin toplamı

Σ_{ {v,u} ∈ E } (g(u) + g(v)) mod m
= (2 Σ_{v ∈ V} g(v)) mod m

olur ve bu değer çift sayı olmak zorundadır — bu da bir çelişkidir.

Başka bir sonsuz aile ise 8k + 5 düğümlü tam graflar tarafından oluşturulur, k > 0. Yine parite argümanı kullanılarak kenarlara 0 .. m − 1 değerleri atanıp uygun bir g fonksiyonu bulunmasının mümkün olmadığı gösterilebilir.

Yukarıdaki örneklerin özü aşağıdaki teoremle ifade edilebilir.

Teorem 1

m = 4j − 2 kenara sahip (j > 0) ve tüm düğümleri çift dereceye sahip olan herhangi bir G grafı için atama problemine çözüm yoktur.

İspat

Kenarlara atanan değerlerin toplamını ele alalım:

Σ_{ {v,u} ∈ E } (g(v) + g(u)) mod m

Eğer kenar sayısı çift ise, yani m = 2k, ve G grafındaki tüm düğümlerin dereceleri çift ise, yukarıdaki toplamın çift olması açıktır. Öte yandan bu toplam şu değere eşit olmalıdır:

m(m − 1)/2 = k(2k − 1)

Atama probleminin çözülemez olması için son ifadenin tek olması gerekir; yani k tek olmalıdır: k = 2j − 1. Böylece

m = 4j − 2

elde edilir ve bu tür m değerleri için her zaman bir parite uyuşmazlığı ortaya çıkar.

Belirli kenar değerleri verilmiş bir çevrim için atama probleminin çözülebilir olup olmadığını doğrulamak amacıyla zarif bir test kurulabilir.

Verilen bir çevrim

C_k = (v1, v2, . . . , vk)

olsun.

Çevrim C_k’nin kenarlarına

t1, t2, . . . , tk

değerleri atanmış olsun; {v_j, v_{j+1}} kenarı t_j değerini alsın.

v1 düğümü için

π(v1) = ⟨ i1_1, i1_2, . . . , i1_k ⟩

biçiminde 0 ile k − 1 arasındaki sayıların herhangi bir permütasyonunu oluşturun.

v2 düğümü için

π(v2) = ⟨ i2_1, i2_2, . . . , i2_k ⟩

permütasyonunu şu şekilde hesaplayın:

i2_j = (t1 − i1_j) mod k

v_p düğümü için, 1 < p ≤ k + 1, şu permütasyonu oluşturun:

π(v_p) = ⟨ (t_{p−1} − i^{p−1}_1) mod k, ... , (t_{p−1} − i^{p−1}_k) mod k ⟩

Çevrim için atama problemine bir çözüm vardır eğer bir j için

i^{k+1}_j = i^1_j

sağlanıyorsa.

Tüm süreci geriye doğru izlediğimizde, aşağıdaki koşulu sağlayan bir j varsa çevrimin çözüme sahip olduğunu görürüz:

(t_k − t_{k−1} + ... + (−1)^{k−1} t_1 + (−1)^k i_j) mod k = i^1_j

Son koşulun hem yeterli hem de gerekli olduğunu göstermek için, C_k çevriminin i‑inci düğümüne g(v_i) değerinin atandığını varsayalım.

Kenarlar üzerindeki değerler

(g(v_i) + g(v_{i mod (k+1)})) mod m = t_i

şeklindedir (m > k ve 1 ≤ i ≤ k). Şu gözlemi yaparız:

g(v_{i mod (k+1)}) = t_i − g(v_i) (mod m), 1 ≤ i ≤ k

Özellikle şu eşitliğe sahibiz:

            j−1
            Σ
 g(v_j) =   (−1)^{j−1−p} t_p + (−1)^{j+1} g(v_1)  (mod m)
           p=1

2 ≤ j ≤ k için.

Yukarıdaki ifadeyi kullanarak g(v_k) değerini

(g(v_k) + g(v_1)) = t_k  (mod m)

denklik içinde yerine koyarsak şu elde edilir:

            k−1
            Σ
 (−1)^{k−1−p} t_p + (−1)^{k+1} g(v_1) + g(v_1) = t_k  (mod m)
           p=1

böylece

        k
        Σ
        (−1)^{k−p} t_p  (mod m)

Dolayısıyla, pratik bir sonucu ve etkili uygulamaları elde etmek için kullanılan aşağıdaki teknik sonuca sahibiz:

Teorem 2

Bir çevrim C_k = (v1, v2, ..., vk) ve bir tamsayı m için, her köşeyi [0, m − 1] aralığında bir sayıya eşleyen bir g fonksiyonu vardır; öyle ki {v_p, v_{p+1}} kenarı için

(g(v_p) + g(v_{p+1})) mod m = t_p,

burada her t_p [0, m − 1] aralığında bir sayıdır; ancak ve ancak j ∈ [0, m − 1] olacak şekilde bir tamsayı için.

Sonuç 3

Şöyle olsun

x = Σ_{p=1}^{k} (−1)^{k−p} t_p,

burada t_p ∈ {0, ..., m − 1} (1 ≤ p ≤ k) değerleri bazı C_k çevriminin kenarlarına atanmış değerlerdir.

• Eğer k çift ise, ancak ve ancak x ≡ 0 (mod m) olduğunda atama problemine bir çözüm vardır.
• Eğer k tek ise, ancak ve ancak x çift olduğunda veya hem x hem de m tek olduğunda bir çözüm vardır.

Yukarıdaki sonuç hızlı ve kolay bir test sağlar. Ne yazık ki t_p değerlerinin son koşulu sağlayacak şekilde nasıl seçileceğine dair bir yöntem sunmaz. Çift uzunluklu çevrimlerle başa çıkmanın, bir bakıma, tek uzunluklu çevrimlere göre daha zor olduğuna dikkat edin. Ancak çift uzunluklu bir çevrim için alternatif toplam koşulu sağlandıktan sonra, köşelere değer atamak çok daha kolaydır. Çevrimsiz grafikler için sunulan yönteme benzer bir prosedür kullanılabilir (bkz. [CHM92]). Tek uzunluklu çevrimler için ise alternatif toplam koşulunu sağlamak çok daha kolaydır, fakat bu durumda köşeler için en fazla iki geçerli atama vardır.

Sonuç 3, tek çevrimli grafikler durumu için Teorem 1’in başka bir kanıtını sağlar. Öncelikle herhangi bir alternatif toplamın iki parçaya ayrılabileceğini fark ederiz: pozitif kısım P ve negatif kısım N. Herhangi bir toplamdan farklı bir toplam elde etmek için, pozitif kısımdaki en az bir elemanı negatif kısımdaki başka bir elemanla değiştirmemiz gerekir. Bu elemanlara sırasıyla π ve ν diyelim. Başlangıç toplamı P − N’ye eşittir; değiştirilmiş toplam ise

P − N + 2(ν − π)

değerine eşit olacaktır.

Dolayısıyla minimum değişim 2’ye eşit olmalı ya da 2’nin bir katı olmalıdır.

Şimdi tek çevrimli bir grafik C_{4j+2} için maksimum toplamı ele alalım. Maksimum alternatif toplam

(6j + 2)(2j + 1)/2 − (2j + 0)(2j + 1)/2 = (2j + 1)^2.

Bu toplam tektir. Dolayısıyla 4j + 2 ile bölünemez. Ayrıca bu toplamı yalnızca pozitif ve negatif kısımlar arasında eleman değiştirerek değiştirebildiğimiz için, diğer tüm toplamlar da tek olacaktır. Sonuç olarak bunların hiçbiri 4j + 2 ile bölünemez. Dolayısıyla Sonuç 3’e göre m = k ve k = 4j + 2 olduğunda tek çevrimli grafikler için çözüm yoktur.

Gerçekte bunu yapmaya çalışmadan, {0, 1, ..., k − 1} tamsayılarının herhangi bir permütasyonu için alternatif toplamın her zaman ya tek (k = 4j + 2 veya k = 4j + 3 ise) ya da her zaman çift (k = 4j veya k = 4j + 1 ise) olması gerektiği gerçeğini keşfetmiş olduk.

Aslında Teorem 2’nin daha güçlü bir sürümünü kanıtlayabiliriz. Bunu yapmadan önce grafik kuramından bazı tanımlara ihtiyacımız vardır.

v1’den v_i’ye bir yol, şu dizidir:

P = v1, e1, v2, e2, ..., e_{i−1}, v_i

Burada köşeler ve kenarlar sırayla gelir ve 1 ≤ j < i için e_j kenarı v_j ve v_{j+1} köşelerine bitişiktir. Eğer v1 = v_i ise P’ye çevrim denir.

Basit bir grafikte (öz-ilmek veya çoklu kenar içermeyen bir grafik) bir yol veya çevrim

v1, e1, v2, e2, ..., e_{i−1}, v_i

daha basit biçimde köşeler dizisi v1, ..., v_i ile ifade edilebilir.

Bir yolda her köşe yalnızca bir kez görünüyorsa bu diziye basit yol denir. Eğer her köşe yalnızca bir kez görünür, fakat v1 = v_i ise P’ye basit çevrim denir. Biz yalnızca basit yollar ve çevrimlerle ilgilendiğimiz için bunlar kısaca yazılır ve "basit" sözcüğü varsayılır.

Bir grafik, farklı herhangi iki köşesini birleştiren bir yol varsa bağlıdır. Bir bağlı grafik G’de bir v köşesi, v ve ona bitişik tüm kenarlar silindiğinde elde edilen grafik bağlı değilse, bir kesme noktası olarak adlandırılır. G grafiği bağlı olup hiçbir kesme noktası içermiyorsa iki bağlıdır; yani G’de herhangi iki köşe en az iki farklı yol ile bağlanmıştır.

İki çevrim, C1 ve C2, toplanarak C3 = C1 ⊕ C2 olacak şekilde bir toplam çevrim oluşturabilir; burada ⊕ işlemi halka-toplamıdır. İki grafiğin halka-toplamı

G1 = (V1, E1) ve G2 = (V2, E2)

için elde edilen grafik

(V1 ∪ V2, (E1 ∪ E2) − (E1 ∩ E2))

şeklindedir.

Tüm çevrimler kümesi halka-toplamı işlemine göre kapalıdır ve çevrim uzayını oluşturur. Bir grafiğin çevrim temeli, grafikteki bağımsız çevrimlerin maksimal bir kümesi ya da tüm çevrimlerin bağımlı olduğu minimal bir çevrim kümesidir. Başka bir deyişle, bir çevrim temelindeki hiçbir çevrim, diğer çevrimlerin herhangi bir alt kümesi toplanarak elde edilemez.

Bir grafiğin yayılma ağaçlarından elde edilebilen özel çevrim temelleri vardır. G grafiğinin bir yayılma ormanı F olsun. G’nin geri kalan kenarlarının her biri F’e eklendiğinde elde edilen çevrimler kümesi, F’e göre G’nin temel çevrim kümesini oluşturur.

Yukarıdaki teoremden aşağıdaki sonucu kolayca çıkarırız.

Teorem 4

G = (V, E) iki bağlı bir grafik olsun ve m = |E| > 2 kenar olsun. Her kenar e ∈ E için t_e ∈ [0, m − 1] değeri atanmış olsun. B, G’nin bir çevrim temeli olsun ve ek olarak B’deki her çevrim G’de seçilmiş bir köşeden, örneğin v1’den, geçsin.

Eğer j ∈ [0, m − 1] olacak şekilde bir tamsayı varsa ve B’deki her çevrim C_k için

C_k = (e1, e2, ..., e_k),

(Σ_{p=1}^{k} (−1)^{k−p} t_{e_p} + (−1)^k j) ≡ j (mod m)

sağlanıyorsa, o zaman

g : V → {0, ..., m − 1}

şeklinde bir fonksiyon vardır ve her e = {u, v}, e ∈ E kenarı için

(g(u) + g(v)) mod m = t_e

olur.

İspat

Yukarıdaki sonuç tümevarım ile kolayca gösterilebilir. Teorem 2’ye göre G yalnızca bir çevrimden oluşuyorsa doğrudur. B’nin i > 1 çevrim içerdiği durumda doğru olduğunu varsayalım. B’ye yeni bir çevrim ekleyelim; bu çevrim en az bir kenarı, fakat B’deki bir çevrimle en fazla bir yolu ortak paylaşsın.

Aşağıdaki tartışmada dikkatimiz yalnızca yukarıda belirtilen özelliğe sahip çevrimlerle sınırlıdır. Bunu yaparken genellik kaybı olmaz; çünkü başka bir çevrimle birden fazla ayrık yolu ortak paylaşan bir çevrim, her biri yalnızca başka bir çevrimle tek bir yol paylaşan birkaç çevrim ile modellenebilir. Yeni bir çevrimin bir temel çevrimle yalnızca bir köşe ortak paylaştığı durum basittir; bu nedenle analizimizde ele alınmamıştır.

Eğer toplam testi yeni çevrim için başarısız olursa G grafiği için atama problemine çözüm yoktur. Dolayısıyla toplam testinin doğru olduğunu varsayalım. G grafiğinin atama problemine çözümü yoktur ancak ve ancak B’ye ait olmayan ve toplam testini sağlamayan bir çevrim varsa.

Bunun imkânsız olduğunu göstermek için Şekil 3’teki grafiği ele alalım.

Şekil 3: C3 = C1 ⊕ C2 için alternatif toplam

C1 ve C2 çevrimleri temel çevrimlerdir; C3 çevrimi C1 ve C2’nin toplanmasıyla elde edilebilir.

C1 için alternatif toplam

s1 = Σ_{k=0}^{p−1} (−1)^k t_{p−k}

ve C2 için alternatif toplam

s2 = Σ_{k=0}^{q−j−1} (−1)^k t_{q−k} + Σ_{k=0}^{i−1} (−1)^{q−j+k} t_{i−k}.

C3 için alternatif toplam

s3 = Σ_{k=0}^{p−i−1} (−1)^k t_{p−k} + Σ_{k=j+1}^{q} (−1)^{p−i−1+k−j} t_k.

Eğer C1 çevriminin uzunluğu tek ve C2 çevriminin uzunluğu çift ise s3 = s1 + s2 olur. Sonuç 3 ve Teorem 4’ün ifadesinden biliyoruz ki s1 ya çifttir ya da m ile aynı paritye sahiptir ve s2 m’nin bir katıdır. C3 çevrimi tek uzunluklu olmalıdır ve doğal olarak s1 + s2 ya çifttir ya da m ile aynı paritye sahiptir.

Eğer her iki çevrimin uzunlukları aynı paritye sahipse, o zaman s3 = s1 − s2 olur ve yine s3 üzerindeki koşul sağlanır. Ayrıca çift/tek kombinasyonunun (s3 = s1 + s2) C3’ün alternatif toplamı üzerindeki koşulu koruduğunu görmek de kolaydır. Dolayısıyla bir temeldeki tüm çevrimler toplam testini geçiyorsa, temele ait olmayan herhangi bir çevrim de geçecektir.

Örnek

Şekil 4’teki grafiği ele alalım. v1 köşesine dayalı çevrim temeli, altta gösterilen üç çevrimden oluşur. Kenarlara verilen değerler için köşelere uygun değerlerin bulunup bulunamayacağını doğrulamak için üç temel çevrim için alternatif toplamları hesaplamamız gerekir. Bunlar

6 − 3 + 5 − 0 = 8,

6 − 1 + 2 − 5 + 0 = 2,

6 − 1 + 4 − 7 + 0 = 2.

Teorem 4 kullanılarak, üç çevrim için de uygun j değerinin 1 veya 5 olduğu hemen görülür. Dolayısıyla Şekil 4’teki grafik için uygun bir atama bulunduğu sonucuna varırız.

Hatta böyle bir atamayı elde etmek için bir yöntem de verebiliriz. Önce g(v1) değerini j olarak belirleriz. Daha sonra grafikte, örneğin derinlik öncelikli arama kullanarak, v1 köşesinden başlayan normal bir arama gerçekleştiririz. Yeni bir u köşesine her ulaştığımızda ve bu köşeye e = {v, u} kenarı üzerinden gelmişsek

g(u) := (t_e − g(v)) mod m

değerini atarız.

Bu yöntem çevrimsiz grafikler için verilen yöntemin doğrudan bir uyarlamasıdır (bkz. [CHM92]). Bu yöntemle Şekil 4’teki grafik için g fonksiyonunu kolayca bulabiliriz.

B’deki her çevrimin belirli bir köşeden geçmesi gerekliliği tek uzunluklu çevrimlerden kaynaklanır. Her biri için yalnızca permütasyonun bir konumda uyuşması yetmez; ayrıca iki farklı çevrim için iki permütasyonun aynı konumda uyuşması gerekir.

Bunu sağlamanın bir yolu tüm çevrimlerin en az bir ortak köşeye sahip olmasını sağlamaktır; böylece hepsi için başlangıç permütasyonu aynı olur.

Bir grafik iki parçalı ise, yani tüm çevrimleri çift uzunlukludur, o zaman yalnızca çevrimlerine odaklanmamız yeterlidir. Her çevrim için alternatif toplam koşulu sağlandıktan sonra, herhangi bir çevrime ait olmayan kenarlara değerleri serbestçe atayabilir ve yine de atama problemini çözebiliriz.

Bu durum, aşağıdaki teoremde ifade edilir. Önceki iki teorem ve sonuçtan kolayca çıktığı için burada ispat verilmemiştir.

Teorem 5

G = (V1 ∪ V2, E) m = |E| kenarlı iki parçalı bir grafik olsun. Her e ∈ E ⊆ V1 × V2 kenarına t_e ∈ [0, m − 1] aralığında benzersiz bir değer atanmış olsun.

G’nin her iki bağlı bileşeni H_i için ve her çevrim

C_k = (e1, e2, ..., e_k) ∈ B_i,

burada B_i, H_i’nin bir çevrim temeli olmak üzere,

Σ_{p=1}^{k} (−1)^{k−p} t_{e_p} ≡ 0 (mod m)

sağlanıyorsa ve G çoklu kenar içermiyorsa, G için atama problemine bir çözüm vardır.

4 Sonuçlar

Teorem 5, Sager [Sag85], Fox ve diğerleri [FHCD92] ile Czech ve Majewski [CM92] algoritmalarının iki parçalı grafikler kullanmasını gerekçelendirir. Bu algoritmaların tümü çevrimsel kenarları diğer kenarlardan bağımsız olarak ele alır. Eğer grafik iki parçalıysa, tüm çevrimsel bileşenler için mükemmel atama problemine bulunan bir çözüm, bağımlılık grafiğinin çevrimsiz kısımlarına kolayca genişletilebilir.

Grafikte tek uzunluklu çevrimler varsa bunu yapmak imkânsız olabilir. Bu nedenle mükemmel bir hash fonksiyonu bulma süreci iki parçalı grafikler kullanıldığında büyük ölçüde basitleşir. Aksi durumda tüm yapının birlikte ele alınması gerekir.

Sıralamayı koruyan hash fonksiyonları durumunda, çevrimsizlik h fonksiyonunun sıralamayı koruması için yeterli bir koşuldur. Çevrimlerin varlığında bu özellik garanti edilemez. Bazı grafikler (örneğin K4) bazı atamalara direnç gösterirken diğerlerine izin verir. Diğer bazıları ise, C6 basit bir örnek olabilir, mükemmel atama problemi için hiçbir çözüm kabul etmez.

Bazı atamalar için çözülemez olan grafikler sınıfı, atama problemi için hiçbir çözümü olmayan grafikler sınıfından çok daha geniştir. Bir grafiğin kenarlarına keyfi sayılar atanamaması, onu sıralamayı koruyan mükemmel hash fonksiyonu üretmeye uygun grafikler sınıfından çıkarır.

Olasılıksal yöntem [CHM92], bu tür grafikleri reddederek, eşleme adımının çıktısı olan grafik için atama problemini her zaman çözebilir.

Şekil 5: Sager, Fox ve diğerleri ile Czech ve Majewski yöntemlerinin kesin olarak başarısız olacağı bir bağımlılık grafiği örneği. Kenarlar üzerindeki sayılar mümkün olan en küçük atamayı verir.

Teorem 1’e göre, bağımlılık grafiğindeki kenar sayısı 4j − 2 ise (j > 0) ve tüm köşelerin dereceleri çift ise, atama problemi için çözüm yoktur. Bu durum, Sager [Sag85], Fox ve diğerleri [FHCD92] ile Czech ve Majewski [CM92] yöntemlerinin kesin olarak başarısız olacağı bağımlılık grafikleri kurmamıza olanak verir.

Böyle bir örnek, m = 18 kenar ve n ≈ 0.6m = 10 köşe ile, Şekil 5’te verilmiştir. Bu örnek üzerinde Sager [Sag85] ile Czech ve Majewski [CM92] tarafından belirtilen yöntemlere benzer şekilde kapsamlı bir arama gerçekleştirdik. Bu arama, grafikte atama problemi için çözüm olmadığını keşfetmeden önce 16,259,364 yineleme gerçekleştirdi.

Yukarıda belirtilen algoritmalardaki kapsamlı arama prosedürünün gerçekleştirdiği yineleme sayısı için bir üst sınır

Σ_{i=1}^{m−n+p(G)} m!/(m−i)!

şeklindedir; burada p(G), bağımlılık grafiği G’nin bağlı bileşenlerinin sayısıdır.

Ayrıca bu grafik için en uygun mükemmel eşlemeyi de bulduk; bu eşleme Şekil 5’te gösterilmiştir. Eşleme, 18 kenarı [0, 18] aralığındaki 19 elemanlı aralığa eşler. Şekil 5’teki grafiğin herhangi bir çevrimi için verilen atamanın önceki bölümdeki teoremlerde belirtilen koşulları sağladığını doğrulamak kolaydır.

Şimdi eşleme adımında üretilen bir bağımlılık grafiğinin Teorem 1 ile karakterize edilen grafikler sınıfına ait olma olasılığını inceleyelim. Bundan sonra kenar sayısının m çift olduğunu fakat 4’e bölünmediğini varsayacağız.

Soruyu şu şekilde yeniden formüle edebiliriz: rastgele bir grafiğin her bağlı bileşeninin bir Euler çevrimine sahip olma olasılığı nedir? Bu tür grafiklere çift grafikler denir.

Çift grafikler R. Read [Rea62] tarafından sayılmıştır. Onun yaklaşımını her parçada r köşe olacak şekilde toplam n = 2r köşeli iki parçalı grafiklere uyarladığımızda, çift grafiklerin sayısının aşağıdaki ifade ile verildiğini elde ederiz.

İki parçalı grafikler için:

E(G_b) = 2^{−2r} Σ_{s=0}^{r} Σ_{t=0}^{r} Σ_{j=0}^{s(r−t)+t(r−s)} (−1)^j C(s(r−t)+t(r−s), j) C(st + (r−s)(r−t), m−j)

Öz-ilmeksiz iki parçalı çoklu grafikler için:

E(G'b) = 2^{−2r} Σ{s=0}^{r} Σ_{t=0}^{r} Σ_{j=0}^{s(r−t)+t(r−s)} (−1)^j C(s(r−t)+t(r−s)+j−1, j)

× C(st + (r−s)(r−t) + m − j − 1, m − j)

Yukarıdaki ifade, 18 kenar ve 10 köşeye sahip 1,479,792,175 adet çift iki parçalı çoklu grafik bulunduğunu hesaplamamıza olanak verir. Dolayısıyla Şekil 5’teki grafiği bulmak görece kolay bir görevdi. Bununla birlikte çift iki parçalı çoklu grafikler, 18 kenar ve 10 köşeli tüm iki parçalı çoklu grafiklerin yalnızca yaklaşık %0.42’sini oluşturur.

E(G'_b) için makul bir genel yaklaşım formülü bulamadık. Ancak 2r ≤ m için şu gözlemi yapıyoruz:

E(G'_b) / C(r^2 + m − 1, m) ≈ 2^{−2r+2}.

Bu yaklaşım aşağıdaki basit argümanla gerekçelendirilebilir. Her parçada r köşe bulunan iki parçalı bir grafikte belirli bir v köşesinin derecesinin d olma olasılığı

Pr(dg(v) = d) = C(m, d) (1/r)^d (1 − 1/r)^{m−d}.

Dolayısıyla bu derecenin çift olma olasılığı

Pr(dg(v) mod 2 = 0) = Σ_{d≥0} C(m, 2d) (1/r)^{2d} (1 − 1/r)^{m−2d}.

(x + y)^m = Σ_{k=0}^{m} C(m, k) x^k y^{m−k} olduğuna göre, x = 1/r ve y = (1 − 1/r) ile ayrıca x = −1/r ve y = (1 − 1/r) seçilip iki denklem toplandığında

(1/r + (1 − 1/r))^m + (−1/r + (1 − 1/r))^m

= 2 Σ_{k≥0} C(m, 2k) (1/r)^{2k} (1 − 1/r)^{m−2k}

= 1 + (1 − 2/r)^m.

Dolayısıyla

Pr(dg(v) mod 2 = 0) = (1 + (1 − 2/r)^m) / 2.

2 adet çift dereceye sahip olma olasılığı vardır. Ancak, iki parçalı bir grafikte her bir parçadaki r − 1 tepe noktasının dereceleri sabitlendiğinde, her bir parçadaki son tepe noktasının derecesi belirlenmiş olur. (Aslında herhangi bir tepe noktasının derecesini ‘sabitlemek’, kalan tepe noktaları için olasılıkları değiştirir. Ancak yeterince kenar bulunduğu sürece, yukarıdaki argüman makul bir yaklaşık sonuç verir.)

Bunun bir sonucu olarak, Sager [Sag85], Fox, Heath, Chen ve Daoud [FHCD92] ile Czech ve Majewski [CM92] tarafından önerilen algoritmaların iddia edilen polinom zaman karmaşıklıkları doğru değildir. Bu algoritmaların beklenen zaman karmaşıklığı polinomik değil, O(n^{n/2n}) düzeyindedir. Çift dereceli grafikler, ne kadar seyrek olursa olsun, bu algoritmalar için hâlâ fazlasıyla yaygındır.

Yukarıdaki sorunu ortadan kaldıran basit bir çözüm olasılıksal bir yaklaşımla sağlanabilir. Algoritmanın iddia edilen karmaşıklığı örneğin n^k olsun (k sabit bir değer olmak üzere). Algoritma, arama adımında gerçekleştirilen işlem sayısını saymalıdır. Bu sayı örneğin n^{2k} değerini aşar aşmaz algoritma eşleme adımına geri döner ve bazı parametreleri değiştirerek yeni bir bağımlılık grafiği üretir.

Çift dereceli grafiklerin yol açtığı sorunun deneysel gözlemlerle tespit edilmesinin çok düşük bir olasılık olduğunu belirtmek gerekir. Fox ve arkadaşları m ≥ 32 için deneysel veriler sunmaktadır. 32 anahtar için, bu olgunun gözlemlenmesine %50 olasılıkla rastlayabilmek için yaklaşık çeyrek milyon deney yapılması gerekirdi.

Bu bölümde minimal mükemmel hash fonksiyonları üretmek için yeni bir algoritma öneriyoruz. Bazı ayrıntıların hâlâ netleştirilmesi gerektiğinden, algoritma açık bir problem olarak sunulmaktadır.

Aşağıdaki algoritmayı ele alalım. Verilen bir G grafiği için, G'nin kenarlarına herhangi bir sırayla 0 ile m − 1 arasında m adet sayı ata. Bir sonraki adımda, G'nin bir çevrim tabanını öyle oluştur ki her çevrim benzersiz bir kenara sahip olsun (bu tür bir çevrim tabanı genellikle temel çevrim kümesi olarak adlandırılır). Taban içindeki çevrimlerden, dönüşümlü toplamı bu bölümde belirtilen koşulları sağlamayan bir çevrimi bul. Benzersiz kenara atanması durumunda dönüşümlü toplam koşullarını sağlayacak en küçük v > m değerini bul. Bu minimum değerin diğer kenarlara atanmış herhangi bir sayıya eşit olmaması gerekir. Böyle bir çevrim bulunamayıncaya kadar tüm süreci tekrarla. Yukarıdaki yöntemle hesaplanan değerleri kullanarak grafik için atama problemini çöz.

Soru: G grafiğindeki herhangi bir kenar üzerindeki en büyük değer nedir? Eğer m kenarlı ve n = m / log m tepe noktalı bir grafikte tüm sayıların m ile sınırlı olması bekleniyorsa, yukarıda belirtilen algoritma O(m) bit kullanan bir mükemmel hash fonksiyonu üretmek için kullanılabilir. Böyle bir süreci tamamlamak için gereken süre, bir çevrim tabanındaki çevrimlerin toplam uzunluğuyla orantılıdır.

5 Bir başka algoritma

Kaynaklar

[CHM92]
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, Ekim 1992.

[CM92]
Z.J. Czech ve B.S. Majewski. O(m²) zamanda minimal mükemmel bir hash fonksiyonu üretmek. Archiwum Informatyki Teoretycznej i Stosowanej, 4:3–20, 1992.

[FCDH91]
E. Fox, Q.F. Chen, A. Daoud ve L. Heath. Sıra koruyan minimal mükemmel hash fonksiyonları ve bilgi erişimi. ACM Transactions on Information Systems, 9(3):281–308, Temmuz 1991.

[FCHD88]
E. Fox, Q.F. Chen, L. Heath ve S. Datta. Mükemmel hash fonksiyonları bulmak için daha maliyet etkin bir algoritma. Teknik Rapor TR-88-30, Virginia Polytechnic Institute and State University, Blacksburg, VA, Eylül 1988.

[FHC89]
E. Fox, L. Heath ve Q.F. Chen. Minimal mükemmel hash fonksiyonları bulmak için O(n log n) algoritması. Teknik Rapor TR-89-10, Virginia Polytechnic Institute and State University, Blacksburg, VA, Nisan 1989.

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

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

[GBY91]
G.H. Gonnet ve R. Baeza-Yates. Algoritmalar ve Veri Yapıları El Kitabı. Addison-Wesley, Reading, Mass., 1991.

[HM92]
G. Havas ve B.S. Majewski. Minimal mükemmel hashleme için optimal algoritmalar. Teknik Rapor 234, The University of Queensland, Key Centre for Software Technology, Queensland, Temmuz 1992.

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

[MWCH92]
B.S. Majewski, N.C. Wormald, Z.J. Czech ve G. Havas. Minimal mükemmel hash fonksiyonları üreten bir üreteç ailesi. Teknik Rapor 16, DIMACS, Rutgers University, New Jersey, ABD, Nisan 1992.

[Rea62]
R.C. Read. Etiketli düğümler üzerindeki Euler grafikleri. Canadian Journal of Mathematics, 14:482–486, 1962.

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