Mükemmel Hash Fonksiyonlarının Dengeli Aileleri ve Uygulamaları

Noga Alon¹*, ve Shai Gutner²**

¹ Matematik ve Bilgisayar Bilimleri Okulları, Tel-Aviv University, Tel-Aviv, 69978, İsrail
noga@math.tau.ac.il

² Bilgisayar Bilimleri Okulu, Tel-Aviv University, Tel-Aviv, 69978, İsrail
gutner@tau.ac.il

* Araştırma kısmen Israel Science Foundation tarafından sağlanan bir hibe ve Tel Aviv University’deki Hermann Minkowski Minerva Center for Geometry tarafından desteklenmiştir.
** Bu makale, yazarın Tel Aviv University’de Prof. N. Alon ve Prof. Y. Azar danışmanlığında yazdığı doktora tezinin bir bölümünü oluşturmaktadır.

Abstract

Mükemmel hash fonksiyonlarının oluşturulması iyi incelenmiş bir konudur. Bu makalede bu kavram aşağıdaki tanımla genelleştirilmektedir. [n]’den [k]’ya fonksiyonlardan oluşan bir aileye, eğer her S ⊆ [n], |S| = k için S üzerinde 1-1 olan fonksiyonların sayısı bazı T > 0 sabiti için T/δ ile δT arasında ise, δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi denir. Mükemmel hash fonksiyonları ailesinin standart tanımı, k büyüklüğündeki her S kümesi için S üzerinde 1-1 olan en az bir fonksiyonun bulunmasını gerektirir. Dengeli aileler kavramında ise, bu tür her S için 1-1 fonksiyonların sayısının (δ’nin 1’e yakın seçilmesiyle) neredeyse aynı olmasını isteriz.

Temel sonucumuz şudur: herhangi bir δ > 1 sabiti için, büyüklüğü 2^{O(k log log k)} log n olan bir δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi, 2^{O(k log log k)} n log n zamanında oluşturulabilir. Color-coding tekniğini kullanarak açık (explicit) yapılarımızı grafiklerdeki çeşitli sayma problemleri için yaklaşık algoritmalar geliştirmede uygulayabiliriz. Özellikle, n düğümlü bir grafikte k ≤ O(log n / log log log n) için hem k uzunluğundaki basit yolların hem de k boyutundaki basit çevrimlerin sayısını yaklaşık hesaplayan deterministik polinom zamanlı bir algoritma gösteriyoruz. Yaklaşım, istenen herhangi sabit bağıl hata sınırına kadar yapılabilir.

Anahtar kelimeler: altgraf yaklaşık sayımı, color-coding, mükemmel hashing.

Bu makale, mükemmel hash fonksiyonlarının dengeli ailelerinin açık yapılarıyla ilgilenmektedir. Mükemmel hash fonksiyonları konusu, daha genel bir çerçeve olan k-kısıtlama problemleri kapsamında geniş biçimde incelenmiştir (bkz. örn., [3], [13]). Bu problemler, problem alanından seçilen herhangi k eleman için belirli bir koşullar kümesinin en az bir kez sağlanmasını gerektiren varoluşsal bir yapıya sahiptir.

Mükemmel hash fonksiyonlarının tanımını genelleştiriyor ve mükemmel hash fonksiyonlarının dengeli aileleri adını verdiğimiz yeni, basit fakat kullanışlı bir kavram sunuyoruz.

1. Introduction

Yeni tanımımızın amacı, yapılara daha fazla yapı kazandırmaktır. Açık yapılarımız, [5]’te sunulan color-coding yöntemi ile birlikte, büyük bir graf içinde sabit bir altgrafın kaç kez ortaya çıktığının yaklaşık hesaplanması problemlerine uygulanmaktadır. Özellikle basit yolların ve basit çevrimlerin sayımına odaklanıyoruz.

Son zamanlarda color-coding yöntemi, hesaplamalı biyolojide ilginç uygulamalar bulmuştur ([17], [18], [19], [12]); özellikle protein etkileşimleri içinde sinyal iletim yollarının tespit edilmesinde. Bu problem, yönsüz ve kenar ağırlıklı bir graf kullanılarak biçimlendirilir ve amaç k uzunluğunda en küçük ağırlıklı yolu bulmaktır. Sonuçlarımızın bu durumda uygulanması, k uzunluğundaki en küçük ağırlıklı yolların sayısını deterministik olarak yaklaşık hesaplamak içindir.

Perfect Hash Functions

Bir (n, k)-mükemmel hash fonksiyonları ailesi, [n]’den [k]’ya fonksiyonlardan oluşan bir ailedir ve her S ⊆ [n], |S| = k için ailede S üzerinde 1-1 olan bir fonksiyon bulunur. Mükemmel hash fonksiyonlarının açık yapılarıyla ilgili geniş bir literatür vardır. [5]’te açıklanan yapı ( [11] ve [16]’yı takip ederek ) 2^{O(k)} log n büyüklüğündedir.

Bilinen en iyi açık yapı e^k k^{O(log k)} log n büyüklüğündedir ve bu değer bilinen alt sınır olan Ω(e^k log n / √k) ile oldukça yakındır [15].

Finding and Counting Paths and Cycles

Bu makalede sunulan graf algoritmalarının temelleri [5]’te atılmıştır. Orada iki ana rastgeleleştirilmiş algoritma sunulmaktadır.

G = (V, E) grafında bulunan k − 1 uzunluğundaki basit yönlü veya yönsüz bir yol, yönlü durumda 2^{O(k)} |E| beklenen zamanında, yönsüz durumda ise 2^{O(k)} |V| beklenen zamanında bulunabilir.

G = (V, E) grafında bulunan k boyutundaki basit yönlü veya yönsüz bir çevrim, ya 2^{O(k)} |V| |E| ya da 2^{O(k)} |V|^ω beklenen zamanında bulunabilir; burada ω < 2.376 matris çarpımının üstel katsayısıdır. Bu algoritmaların rastgelelikten arındırılması ek olarak log |V| çarpanı getirir.

Çift uzunluklu çevrimler için, [20]’de her sabit k ≥ 2 için yönsüz bir graf içinde 2k boyutunda basit bir çevrimi bulmak için O(|V|^2) zamanlı bir algoritma olduğu gösterilmiştir. Belirli uzunluktaki çevrimlerin tespiti için geliştirilmiş algoritmalar [6] ve [21]’de sunulmuştur.

[6]’daki ilginç bir sonuç, bu makalede ele alınan sorularla ilişkili olarak, boyutu en fazla 7 olan çevrimlerin sayısını hesaplayan O(|V|^ω) zamanlı bir algoritmadır.

Flum ve Grohe, yönlü ve yönsüz graflarda k uzunluğundaki yolların ve çevrimlerin sayısını tam olarak sayma probleminin, parametre olarak k alındığında, #W[1]-tam olduğunu göstermiştir [10]. Bu sonuç, büyük olasılıkla, herhangi hesaplanabilir f : ℕ → ℕ fonksiyonu ve sabit c için, n boyutlu bir graf içinde k uzunluğundaki yolların veya çevrimlerin tam sayısını hesaplayan f(k) n^c biçiminde bir algoritmanın bulunmadığını ima eder.

Bu durum, bu büyüklüklerin yaklaşık hesaplanması problemini gündeme getirir. Arvind ve Raman, büyük bir graf içinde sınırlı ağaç genişliğine sahip sabit bir altgrafın kopyalarının sayısını yaklaşık hesaplamak için rastgeleleştirilmiş sabit-parametre izlenebilir bir algoritma elde etmiştir [7]. Bu çalışmada onların ortaya koyduğu, bu problem için deterministik yaklaşık sayım algoritmasının varlığına ilişkin açık soruyu olumlu şekilde yanıtlıyoruz.

Basitlik açısından, yolların ve çevrimlerin yaklaşık sayımı için algoritmalar veriyoruz. Bu sonuçlar, aynı yaklaşımın [5]’teki yöntemle birleştirilmesiyle, sınırlı ağaç genişliğine sahip altgrafların yaklaşık sayımı problemine kolayca genişletilebilir. Deterministik algoritmalarımızdaki temel yeni bileşen, burada tanıtılan ve basit olmasına rağmen oldukça yararlı görünen bir kombinatoryal kavram olan dengeli mükemmel hash fonksiyonları ailelerinin kullanılmasıdır.

Balanced Families of Perfect Hash Functions

[n]’den [k]’ya fonksiyonlardan oluşan bir aileye, eğer her S ⊆ [n], |S| = k için S üzerinde 1-1 olan fonksiyonların sayısı bazı T > 0 sabiti için T/δ ile δT arasında ise, δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi denir.

Dengeli mükemmel hash fonksiyonları aileleri, mükemmel hash fonksiyonlarının klasik kavramının doğal bir genellemesidir.

Açık yapılarımızı desteklemek amacıyla, ayrıca dengeli splitter adı verilen daha da genelleştirilmiş bir kavram tanımlıyoruz (tanım için Bölüm 2’ye bakınız). Bu kavram, [15]’te tanımlanan sıradan splitter kavramının bir genellemesidir.

Our Results

Makalenin ana odağı, dengeli mükemmel hash fonksiyonları ailelerinin açık yapıları ve bunların uygulamalarıdır.

Öncelikle farklı türde dengeli splitter’ların büyüklükleri için yapıcı olmayan üst sınırlar veriyoruz. Daha sonra bu sınırları yapıcı algoritmalarla elde edilen değerlerle karşılaştırıyoruz.

Temel sonucumuz, her 1 < δ ≤ 2 için aşağıdaki büyüklüğe sahip bir δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesinin açık yapısıdır:

2^{O(k log log k)} (δ − 1)^{-O(log k)} log n.

Bu yapıyı sağlayan prosedürün çalışma süresi

2^{O(k log log k)} (δ − 1)^{-O(log k)} n log n + (δ − 1)^{-O(k / log k)}.

Dengeli mükemmel hash fonksiyonları ailelerinin yapıları, graflardaki çeşitli sayma problemlerine uygulanabilir. Özellikle, büyük bir graf içinde küçük bir altgrafın kaç kez ortaya çıktığını yaklaşık hesaplayan deterministik algoritmalar tanımlıyoruz.

Yaklaşım her zaman 1’e keyfi derecede yakın yapılabilen çarpımsal bir faktör doğruluğundadır.

Herhangi 1 < δ ≤ 2 için:

• G = (V, E) grafında k − 1 uzunluğundaki basit yolların sayısı, δ çarpımsal faktör doğruluğuyla şu zamanda yaklaşık hesaplanabilir

  2^{O(k log log k)} (δ − 1)^{-O(log k)} |E| log |V| + (δ − 1)^{-O(k / log k)}.

• k boyutundaki basit çevrimlerin sayısı, δ çarpımsal faktör doğruluğuyla şu zamanda yaklaşık hesaplanabilir

  2^{O(k log log k)} (δ − 1)^{-O(log k)} |E| |V| log |V| + (δ − 1)^{-O(k / log k)}.

Techniques

Farklı türde küçük boyutlu dengeli splitter’ların varlığını göstermek için olasılıksal argümanlar kullanıyoruz (kesin tanımları bir sonraki bölümde verilmiştir).

Bir dengeli splitter oluşturmak için doğal bir rastgeleleştirilmiş algoritma, yeterince büyük sayıda bağımsız rastgele fonksiyon seçmektir. Bazı durumlarda koşullu olasılıklar yönteminin, uygun seçilmiş bir potansiyel fonksiyon üzerinde uygulanarak bu süreci verimli biçimde rastgelelikten arındırabileceğini gösteriyoruz.

k-wise bağımsız rastgele değişkenler barındıran küçük olasılık uzaylarının yapıları da iyi bölme özellikleri elde etmek için doğal bir araçtır.

Hata düzeltici kodların kullanımı, [n]’den [l]’ye fonksiyonlardan oluşan ve l değeri k²’den çok daha büyük olan bir aile bulmak istediğimiz durumlarda yararlıdır; bu durumda her S ⊆ [n], |S| = k için fonksiyonların neredeyse tamamının S üzerinde 1-1 olması gerekir.

Dengeli splitter’lar farklı şekillerde birleştirilebilir ve ana yapımız üç tür splitter’ın bileştirilmesiyle elde edilmektedir.

Yaklaşık sayım algoritmalarımızı elde etmek için dengeli mükemmel hash fonksiyonları ailelerinin açık yapıları ile color-coding tekniğini birlikte kullanıyoruz.

2. Balanced Families of Perfect Hash Functions

Bu bölümde dengeli mükemmel hash fonksiyonları aileleri ve dengeli splitter kavramlarını resmi olarak tanımlıyoruz.

[n] ile {1, ..., n} kümesini gösterelim. Herhangi k için, 1 ≤ k ≤ n olmak üzere, [n]’in k elemanlı altkümelerinin ailesi

C(n, k)

ile gösterilir.

k mod l ile, k = ql + r olacak şekilde bazı tamsayı q için 0 ≤ r < l koşulunu sağlayan tek r tamsayısını ifade ederiz.

Definition 1

1 ≤ k ≤ n ve δ ≥ 1 olsun. [n]’den [k]’ya fonksiyonlardan oluşan bir aileye, eğer bazı T > 0 gerçek sabiti için her S ∈ C(n, k) kümesi için S üzerinde 1-1 olan fonksiyonların sayısı inj(S) şu koşulu sağlıyorsa, δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi denir:

T/δ ≤ inj(S) ≤ δT.

Definition 2

1 ≤ k ≤ n ve δ ≥ 1 olsun ve H, [n]’den [l]’ye fonksiyonlardan oluşan bir aile olsun.

S ∈ C(n, k) kümesi için split(S) ile, S kümesini eşit büyüklükte parçalara ayıran h⁻¹(j) ∩ S, j = 1, ..., l biçimindeki bölmeleri sağlayan h ∈ H fonksiyonlarının sayısını gösteririz.

l sayısı k’yı bölmediğinde iki durumu ayırırız:

• Eğer k ≤ l ise, split(S) S üzerinde 1-1 olan fonksiyonların sayısı olarak tanımlanır.
• Aksi halde, k > l ise, ilk k mod l parçanın boyutunun ⌈k/l⌉ ve kalan parçaların boyutunun ⌊k/l⌋ olmasını isteriz.

H ailesine, eğer bazı T > 0 gerçek sabiti için her S ∈ C(n, k) kümesi için

T/δ ≤ split(S) ≤ δT

koşulu sağlanıyorsa, δ-dengeli (n, k, l)-splitter denir.

Yukarıdaki tanımlar aşağıdaki basit bileşim lemmalarını ifade etmemizi sağlar.

Lemma 1

Herhangi k < l için, H büyüklüğü N olan açık bir δ-dengeli (n, k, l)-splitter ve G büyüklüğü M olan açık bir γ-dengeli (l, k)-mükemmel hash fonksiyonları ailesi olsun.

H ve G kullanılarak büyüklüğü NM olan açık bir δγ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi elde edilebilir.

İspat. H’deki her fonksiyon G’deki her fonksiyonla bileştirilir ve istenen sonuç elde edilir.

Lemma 2

Herhangi k > l için, H büyüklüğü N olan açık bir δ-dengeli (n, k, l)-splitter olsun. Her j = 1, ..., l için G_j büyüklüğü M_j olan açık bir γ_j-dengeli (n, k_j)-mükemmel hash fonksiyonları ailesi olsun; burada

• j ≤ k mod l için k_j = ⌈k/l⌉
• aksi halde k_j = ⌊k/l⌋.

Bu yapılar kullanılarak büyüklüğü N ∏{j=1}^{l} M_j olan açık bir (δ ∏{j=1}^{l} γ_j)-dengeli (n, k)-mükemmel hash fonksiyonları ailesi elde edilebilir.

İspat. [k] kümesini I₁, ..., I_l olmak üzere l ayrık aralığa böleriz; burada her j = 1, ..., l için I_j aralığının boyutu k_j’dir. G_j’yi [n]’den I_j’ye fonksiyonlar ailesi olarak düşünürüz. Her h ∈ H ve g_j ∈ G_j (j = 1, ..., l) kombinasyonu için, x ∈ [n] elemanını g_{h(x)}(x)’e eşleyen yeni bir fonksiyon tanımlarız.

3. Probabilistic Constructions

Aşağıdaki iki sonucu kullanacağız: Chernoff sınırının bir varyantı (bkz. örn., [4]) ve Stirling formülünün sıkı bir biçimi olan Robbins formülü [9].

Claim

Y karşılıklı bağımsız gösterge rastgele değişkenlerinin toplamı olsun ve μ = E[Y] olsun. Tüm 1 ≤ δ ≤ 2 için

Pr[μ/δ ≤ Y ≤ δμ] > 1 − 2e^{−(δ−1)² μ / 8}.

Robbins formülü şu eşitsizliği verir

√(2π) n^{n+1/2} e^{−n + 1/(12n+1)} < n! < √(2π) n^{n+1/2} e^{−n + 1/(12n)}.

Şimdi δ-dengeli (n, k, l)-splitter’lar için k = l, k < l ve k > l durumlarına ait sonuçları veriyoruz.

Theorem 1

Herhangi 1 < δ ≤ 2 için aşağıdaki büyüklüğe sahip bir δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi vardır:

O( e^k √k log n / (δ − 1)² ).

İspat. M adet rastgele fonksiyon seçilir. Belirli bir S ∈ C(n, k) kümesi için, S üzerinde 1-1 olan fonksiyonların beklenen sayısı tam olarak pM’dir. Chernoff sınırına göre, en az bir S kümesi için S üzerinde 1-1 olan fonksiyonların sayısının gerekli aralıktan sapma olasılığı küçüktür.

Theorem 3

Herhangi k ≥ 2 ve 1 < δ ≤ 2 için aşağıdaki büyüklüğe sahip bir δ-dengeli (n, k, 2)-splitter vardır:

O( k √k log n / (δ − 1)² ).

İspat (özet).

M = ⌈8(k ln n + 1) / (p(δ − 1)²)⌉

olarak alınır; burada p, rastgele bir fonksiyonda istenen bölmenin elde edilme olasılığını gösterir. Robbins formülünden 1/p = O(√k) olduğu çıkar. M adet bağımsız rastgele fonksiyon seçilir ve Theorem 1’in ispatındaki gibi ilerlenir.

4. Explicit Constructions

Bu makalede açık yapı terimini, gerekli fonksiyon ailesinin tüm elemanlarını toplam fonksiyon boyutuna göre polinom zamanda listeleyen bir algoritma için kullanıyoruz. Bu terimin diğer tanımları hakkında tartışma için [15]’e bakınız.

δ-dengeli (n, k, l)-splitter’lar için üç durumun sonuçlarını veriyoruz: k = l, k < l ve k > l.

Theorem 4

Herhangi 1 < δ ≤ 2 için aşağıdaki büyüklüğe sahip bir δ-dengeli (n, k)-mükemmel hash fonksiyonları ailesi

O( e^k √k log n / (δ − 1)² )

deterministik olarak şu süre içinde oluşturulabilir:

C(n, k) · e^k k^{O(1)} n log n / (δ − 1)².

İspat. p = k! / k^k alınır ve

M = ⌈16(k ln n + 1) ...⌉

seçilir.

λ = (δ − 1)/4 olarak tanımlayalım; açıkça 0 < λ ≤ 1/4’tür. [n]’den [k]’ya M adet bağımsız rastgele fonksiyon seçildiğini düşünelim. Bu seçim algoritmanın ilerleyen kısmında rastgelelikten arındırılacaktır.

Her S ∈ (\binom{[n]}{k}) için

[ X_S = \sum_{i=1}^{M} X_{S,i}, ]

tanımını yaparız; burada (X_{S,i}), i’inci fonksiyonun S üzerinde 1–1 olması durumunda 1 değerini alan gösterge rastgele değişkenidir. Aşağıdaki potansiyel fonksiyonu ele alalım:

[ \Phi = \sum_{S \in \binom{[n]}{k}} \left(e^{\lambda(X_S - pM)} + e^{\lambda(pM - X_S)}\right). ]

Beklenen değeri şu şekilde hesaplanabilir:

[ E[\Phi] = \binom{n}{k}\left(e^{-\lambda pM} \prod_{i=1}^{M} E[e^{\lambda X_{S,i}}] + e^{\lambda pM} \prod_{i=1}^{M} E[e^{-\lambda X_{S,i}}]\right). ]

Şimdi (E[\Phi]) için bir üst sınır veriyoruz. Tüm (u) değerleri için (1 + u \le e^u) ve tüm (u \ge 0) için (e^{-u} \le 1 - u + u^2/2) olduğundan şu sonucu elde ederiz:

[ pe^{-\lambda} + (1 - p) \le e^{p(e^{-\lambda}-1)} \le e^{p(-\lambda + \lambda^2/2)}. ]

(\epsilon = e^{\lambda} - 1) olarak tanımlayalım, yani (\lambda = \ln(1 + \epsilon)). Böylece

[ pe^{\lambda} + (1 - p) = 1 + \epsilon p \le e^{\epsilon p}. ]

Tüm (0 \le u \le 1) için (e^u \le 1 + u + u^2) olduğundan şu sonucu elde ederiz:

[ \frac{e^{\epsilon}}{1+\epsilon} = e^{e^{\lambda}-1-\lambda} \le e^{\lambda^2}. ]

Şu sonuca varırız:

[ E[\Phi] \le 2\binom{n}{k} e^{\lambda^2 pM} \le e^{2(k \ln n + 1)}. ]

Deterministik Oluşturma

Şimdi (E[\Phi]) değerinin hâlâ son üst sınırı sağlaması için (M) adet fonksiyon bulmaya yönelik deterministik bir algoritma açıklıyoruz. Bu işlem koşullu olasılıklar yöntemi kullanılarak gerçekleştirilir.

Algoritma (M) fazdan oluşacaktır ve her faz (n) adımdan meydana gelir. (j) fazının (i). adımında algoritma, (j). fonksiyonun (i). değerini belirler. Olası (k) değer arasından, açgözlü bir seçim yaparak (E[\Phi]) değerini mümkün olduğunca azaltan değeri seçeriz.

Algoritmanın herhangi bir adımında, potansiyel fonksiyonun koşullu beklentisinin tam değeri şu sürede hesaplanabilir:

[ \binom{n}{k} k^{O(1)}. ]

Tüm (M) fonksiyon belirlendikten sonra, her (S \in \binom{[n]}{k}) kümesi için

[ e^{\lambda(X_S - pM)} + e^{\lambda(pM - X_S)} \le e^{2(k \ln n + 1)} ]

koşulu sağlanır.

Tüm (1 \le u \le 2) için (1/u \le 1 - (u - 1)/2) olduğu gerçeğini kullanarak istenen sonucu elde ederiz:

[ \frac{pM}{\delta} \le X_S \le \delta pM. ]

Teorem 5

Herhangi bir (1 < \delta \le 2) için, (\delta)-dengeli bir ((n, k, \lceil 2k^2/(\delta-1) \rceil))-splitter

[ k^{O(1)} n \log n ]

zamanında oluşturulabilir.

Alfabe ([q]) üzerinde (n) kod sözcüğüne sahip ve normalize edilmiş Hamming uzaklığı en az

[ 1 - \frac{2}{q} ]

olan bir hata düzeltme kodunun açık bir oluşturmasını ele alalım.

Uzunluğu (O(q^2 \log n)) olan bu tür açık kodlar mevcuttur. Kodun her indeksi ([n]) kümesinden ([q]) kümesine bir fonksiyona karşılık gelir. Eğer (M) ile kodun uzunluğunu (ki aslında splitter'ın boyutudur) gösterirsek, her (S \in \binom{[n]}{k}) için iyi bölmelerin sayısı en az

[ -2(k \ln n + 1) \le \lambda(X_S - pM) \le 2(k \ln n + 1) ]

olur.

(\lambda = (\delta - 1)/4) olduğunu hatırlayalım. (M) ve (p) değerleri yerine konulduğunda

[ (\delta - 1)^{O(1)} ]

değeri elde edilir ve oluşturma işlemi

[ k^{O(1)} n \log n ]

zamanında gerçekleştirilebilir.

Son eşitsizlik şu gerçekten elde edilir:

[ 1 - \frac{(u - 1)}{2} \ge \frac{1}{u} \quad \text{tüm } 1 \le u \le 2 \text{ için}. ]

Neredeyse k-Bağımsız Rastgele Değişkenler

Bir sonraki oluşturma için, neredeyse (k)-kat bağımsız rastgele değişken dizilerini destekleyen küçük olasılık uzaylarını kullanıyoruz.

Rastgele Boolean değişkenlerinden oluşan (X_1, \ldots, X_n) dizisi, herhangi bir (k) konum için

[ i_1 < \cdots < i_k ]

ve herhangi bitler (\alpha_1, \ldots, \alpha_k) için

[ \left| \Pr[X_{i_1} = \alpha_1, \ldots, X_{i_k} = \alpha_k] - 2^{-k} \right| \le \epsilon ]

koşulu sağlanıyorsa ((\epsilon, k))-bağımsız olarak adlandırılır.

Boyutu

[ 2^{O(k + \log(1/\epsilon))} \log n ]

olan örnek uzayları, bu tür (n) değişkeni destekleyecek şekilde

[ 2^{O(k + \log(1/\epsilon))} n \log n ]

zamanında oluşturulabilir.

Teorem 6

Herhangi bir (k \ge l) ve (1 < \delta \le 2) için, boyutu

[ 2^{O(k \log l - \log(\delta - 1))} \log n ]

olan bir (\delta)-dengeli ((n, k, l))-splitter

[ 2^{O(k \log l - \log(\delta - 1))} n \log n ]

zamanında oluşturulabilir.

İspat

Boyutu

[ 2^{O(k \log l - \log(\delta - 1))} \log n ]

olan açık bir olasılık uzayı kullanıyoruz. Bu uzay

[ n \lceil \log_2 l \rceil ]

rastgele değişkeni destekler ve bu değişkenler

[(\epsilon, k \lceil \log_2 l \rceil)]-bağımsızdır,

burada

[ \epsilon = 2^{-k \lceil \log_2 l \rceil - 1}(\delta - 1). ]

([n]) kümesinin her elemanına (\lceil \log_2 l \rceil) rastgele değişken bağlarız ve ona

[ [2^{\lceil \log_2 l \rceil}] ]

kümesinden bir değer atarız.

Eğer (l) sayısı 2'nin bir kuvveti değilse,

[ [2^{\lceil \log_2 l \rceil}] \setminus [l] ]

kümesindeki tüm elemanlar sabit bir keyfi fonksiyon ile ([l]) kümesine eşlenir.

Bundan, her

[ S \in \binom{[n]}{k} ]

kümesi için iyi bölmelerin sayısının gerekli sınırları sağladığı ve bir (T > 0) sabitinin var olduğu sonucu çıkar.

Sonuç 1

Herhangi sabit (c > 0) için,

[(1 + c^{-k})]-dengeli bir ((n, k, 2))-splitter

boyutunda

[ 2^{O(k)} \log n ]

olacak şekilde

[ 2^{O(k)} n \log n ]

zamanında oluşturulabilir.

Teorem 6'da (l = k) seçildiğinde, boyutu

[ 2^{O(k \log k - \log(\delta - 1))} \log n ]

olan (\delta)-dengeli bir ((n, k)) mükemmel hash fonksiyonları ailesi elde edilir ve bu aile

[ 2^{O(k \log k - \log(\delta - 1))} n \log n ]

zamanında oluşturulabilir.

Eğer (k = O(\log n / \log \log n)) ise, herhangi sabit (1 < \delta \le 2) için aile boyutu (n)'in polinomudur.

Teorem 7

(1 < \delta \le 2) için, boyutu

[ 2^{O(k \log \log k)} (\delta - 1)^{-O(k/\log k)} \log n ]

olan bir (\delta)-dengeli ((n, k)) mükemmel hash fonksiyonları ailesi

[ 2^{O(k \log \log k)} (\delta - 1)^{-O(k/\log k)} n \log n ]

zamanında oluşturulabilir.

Özellikle, herhangi sabit (1 < \delta \le 2) için boyut

[ 2^{O(k \log \log k)} \log n ]

ve oluşturma zamanı

[ 2^{O(k \log \log k)} n \log n ]

olur.

5. Yolların ve Çevrimlerin Yaklaşık Sayımı

Tanım 3. Bir algoritma, her giriş (x) için çıktısı (ALG(x)) şu koşulu sağlıyorsa bir sayma problemini (\delta \ge 1) çarpanıyla yaklaşık olarak hesaplar:

[ \frac{N(x)}{\delta} \le ALG(x) \le \delta N(x), ]

burada (N(x)), (x) girdisi için sayma probleminin tam değeridir.

Color-coding tekniği yolların ve çevrimlerin yaklaşık sayımında kullanılır.

(G = (V, E)) yönlü veya yönsüz bir graf olsun. Algoritmalarımızda dengeli ((|V|, k)) mükemmel hash fonksiyonları aileleri kullanıyoruz. Her fonksiyon grafın düğümlerinin bir renklendirmesini tanımlar. Bir yol üzerindeki her düğüm farklı bir renk alıyorsa bu yol renkli olarak adlandırılır.

Amacımız her renklendirmede renkli yolların tam sayısını hesaplamaktır.

Teorem 8

Herhangi bir (1 < \delta \le 2) için, (G=(V,E)) grafındaki uzunluğu (k-1) olan basit (yönlü veya yönsüz) yolların sayısı

[ 2^{O(k \log \log k)} (\delta - 1)^{O(\log k)} |E| \log |V| + (\delta - 1)^{-O(k/\log k)} ]

zamanında (\delta) çarpanı içinde yaklaşık olarak hesaplanabilir.

İspat (Taslak)

Teorem 7'de verilen (\delta)-dengeli ((|V|, k)) mükemmel hash fonksiyonları ailesini kullanıyoruz. Her fonksiyon düğümleri (k) renk ile renklendirir.

Her (k) elemanlı (S \subseteq V) kümesi için, (S) üzerinde bire bir olan fonksiyonların sayısının

[ T/\delta \quad \text{ve} \quad \delta T ]

arasında olduğunu sağlayan bir (T > 0) sabiti vardır.

Her renklendirme için dinamik programlama kullanarak renkli yolların tam sayısını (k) fazda hesaplarız.

(i). fazda, her (v \in V) düğümü ve

[ C \subseteq {1, \ldots, k} ]

olacak şekilde (|C| = i) koşulunu sağlayan her alt küme için, (C) renklerini kullanarak (v)'de biten uzunluğu (i-1) olan renkli yolların sayısını hesaplarız.

Her ((u,v) \in E) kenarı için, bunun uzunluğu (i-1) olan bir renkli yolun son kenarı olup olamayacağını kontrol ederiz. (i-2). fazdan elde edilen sayımları kullanarak (i). faz için değerleri güncelleriz.

1. fazın başlatılması basittir. (k). fazdan sonra, her düğümde biten uzunluğu (k-1) olan renkli yolların tam sayısını biliriz.

Her renklendirmeyi işlemek

[ 2^{O(k)} |E| ]

zaman alır.

Sonuçları tüm renklendirmeler üzerinde toplar ve (T) değerine böleriz. Yönsüz graflar için ayrıca 2'ye böleriz.

Teorem 9

Herhangi bir (1 < \delta \le 2) için, (G=(V,E)) grafındaki (k) boyutlu basit çevrimlerin sayısı

[ 2^{O(k \log \log k)} (\delta - 1)^{O(\log k)} |E||V| \log |V| + (\delta - 1)^{-O(k/\log k)} ]

zamanında (\delta) çarpanı içinde yaklaşık olarak hesaplanabilir.

İspat (Taslak)

Yine Teorem 7'deki (\delta)-dengeli ((|V|, k)) mükemmel hash fonksiyonları ailesini kullanıyoruz.

Her renklendirme ve her (s \in V) düğümü için, Teorem 8'deki algoritmayı çalıştırarak (s)'den her (v) düğümüne uzunluğu (k-1) olan renkli yolların sayısını hesaplarız.

Eğer ((v,s)) kenarı varsa, bu bir çevrimi tamamlar ve sonucu sayıya ekleriz.

Sonuçları tüm renklendirmeler ve tüm ((s,v)) çiftleri üzerinde toplarız. Nihai değer (kT)'ye bölünür ve graf yönsüz ise ayrıca 2'ye bölünür.

Sonuç 2

Herhangi bir sabit (c > 0) için, aşağıdaki iki değeri yaklaşık hesaplayan deterministik polinom zamanlı bir algoritma vardır:

• uzunluğu (k) olan basit yolların sayısı
• boyutu (k) olan basit çevrimlerin sayısı

her

[ k \le O\left(\frac{\log n}{\log \log \log n}\right) ]

için, (n) düğümlü bir graf üzerinde, çarpan

[ 1 + (\ln \ln n)^{-c \ln \ln n} ]

içinde.

6. Sonuç Notları

• Color-coding çerçevesindeki diğer algoritmalar da sayma problemlerini ele alacak şekilde genelleştirilebilir.
• Bu yaklaşımı hızlı matris çarpımı teknikleriyle birleştirerek belirli uzunluktaki çevrimlerin sayısını yaklaşık olarak hesaplamak mümkündür.
• (k) düğümlü bir orman (F) verildiğinde, (G) grafındaki (F)'e izomorf alt grafların sayısı önceki çalışmalara benzer özyinelemeli bir algoritma kullanılarak yaklaşık hesaplanabilir.
• Ağırlıklı graflar için, uzunluğu (k-1) olan minimum veya maksimum ağırlıklı yolların sayısı ve ayrıca boyutu (k) olan çevrimlerin sayısı yaklaşık olarak hesaplanabilir.
• Tüm sonuçlar, yollar ve çevrimlerden sınırlı ağaç-genişliğine sahip keyfi küçük alt graflara doğal biçimde genişletilebilir.

Dengeli bir ((n,k)) mükemmel hash fonksiyonları ailesinin tanımında, her (|S| = k) olacak şekilde (S \subseteq [n]) için (S) üzerinde bire bir olan fonksiyonların sayısının (T) değerine yakın olduğunu sağlayan bir (T > 0) sabiti vardır.

(T) değeri, bu tür fonksiyonların tekdüze dağılım altında beklenen sayısına zorunlu olarak eşit değildir. Özellikle, Teorem 7'nin oluşturmasında (T) değeri bu beklentiye asimptotik olarak bile eşit değildir.

Kaynaklar

1. Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.M.: Sahte-rastgele graflar aracılığıyla asimptotik olarak iyi düşük oranlı hata düzeltme kodlarının oluşturulması. IEEE Transactions on Information Theory 38(2), 509 (1992).

2. Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Neredeyse k-kat bağımsız rastgele değişkenlerin basit oluşturulması. Random Structures & Algorithms 3(3), 289–304 (1992).

3. Alon, N., Moshkovitz, D., Safra, S.: k-kısıtlamaları için kümelerin algoritmik oluşturulması. ACM Transactions on Algorithms 2(2), 153–177 (2006).

4. Alon, N., Spencer, J.H.: The Probabilistic Method, 2. baskı. Wiley (2000).

5. Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM 42(4), 844–856 (1995).

6. Alon, N., Yuster, R., Zwick, U.: Verilen uzunluktaki çevrimleri bulma ve sayma. Algorithmica 17(3), 209–223 (1997).

7. Arvind, V., Raman, V.: Bazı parametreli sayma problemleri için yaklaşık algoritmalar. In: ISAAC 2002, LNCS 2518, ss. 453–464. Springer (2002).

8. Azar, Y., Motwani, R., Naor, J.: Küçük örnek uzayları kullanarak olasılık dağılımlarının yaklaşık gösterimi. Combinatorica 18(2), 151–171 (1998).

9. Feller, W.: An Introduction to Probability Theory and Its Applications, Cilt I, 3. baskı. Wiley (1968).

10. Flum, J., Grohe, M.: Sayma problemlerinin parametreli karmaşıklığı. SIAM Journal on Computing 33(4), 892–922 (2004).

11. Fredman, M.L., Komlós, J., Szemerédi, E.: En kötü durumda O(1) erişim süresine sahip seyrek bir tablonun saklanması. Journal of the ACM 31(3), 538–544 (1984).

12. Höffner, F., Wernicke, S., Zichner, T.: Sinyal iletim yolu tespitini kolaylaştırmak için color-coding üzerinde algoritma mühendisliği. In: Sankoff, D., Wang, L., Chin, F. (eds.) APBC 2007. Proceedings of 5th Asia-Pacific Bioinformatics Conference, Hong Kong, China, January 15–17, 2007. Advances in Bioinformatics and Computational Biology, cilt 5, ss. 277–286. Imperial College Press, London (2007).

13. Koller, D., Megiddo, N.: Verilen kısıtları sağlayan küçük örnek uzaylarının oluşturulması. SIAM Journal on Discrete Mathematics 7(2), 260–274 (1994).

14. Naor, J., Naor, M.: Small-bias olasılık uzayları: verimli oluşturma yöntemleri ve uygulamalar. SIAM Journal on Computing 22(4), 838–856 (1993).

15. Naor, M., Schulman, L. J., Srinivasan, A.: Splitter'lar ve neredeyse en iyi deterministikleştirme. In: 36th Annual Symposium on Foundations of Computer Science, ss. 182–191 (1995).

16. Schmidt, J. P., Siegel, A.: Oblivious k-probe hash fonksiyonlarının uzamsal karmaşıklığı. SIAM Journal on Computing 19(5), 775–786 (1990).

17. Scott, J., Ideker, T., Karp, R. M., Sharan, R.: Protein etkileşim ağlarında sinyal iletim yollarını tespit etmek için verimli algoritmalar. Journal of Computational Biology 13(2), 133–144 (2006).

18. Sharan, R., Ideker, T.: Biyolojik ağ karşılaştırması yoluyla hücresel mekanizmaların modellenmesi. Nature Biotechnology 24(4), 427–433 (2006).

19. Shlomi, T., Segal, D., Ruppin, E., Sharan, R.: QPath: protein–protein etkileşim ağında yol sorgulamak için bir yöntem. BMC Bioinformatics 7, 199 (2006).

20. Yuster, R., Zwick, U.: Çift uzunluklu çevrimleri daha da hızlı bulma. SIAM Journal on Discrete Mathematics 10(2), 209–222 (1997).

21. Yuster, R., Zwick, U.: Dikdörtgensel matris çarpımı ve dinamik programlama kullanarak kısa yönlü çevrimleri tespit etme. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ss. 254–260. ACM Press, New York (2004).