← perfect_hashing/
[17] 2010 #564

Perfect Hash Families in Polynomial Time (slides)

—

Polinom Zamanında Mükemmel Hash Aileleri

Charles J. Colbourn
School of Computing, Informatics, and Decision Systems Engineering
Arizona State University

Mükemmel Hash Aileleri

Tanım

Bir mükemmel hash ailesi PHF(N; k, v, t), v sembolü üzerinde tanımlı N × k boyutunda bir dizidir; öyle ki her N × t alt dizide, en az bir satır farklı sembollerden oluşur.

Bir PHF(N; k, v, t)'nin var olduğu en küçük N değeri mükemmel hash ailesi sayısı olarak adlandırılır ve PHFN(k, v, t) ile gösterilir.

Örnek: PHF(6; 12, 3, 3)

0 1 2 2 1 2 2 0 1 1 0 0
0 2 1 0 2 2 2 1 0 1 2 1
1 0 0 2 2 2 1 1 2 1 0 2
2 0 1 1 2 0 2 0 1 1 2 1
2 0 2 1 2 1 0 2 2 1 1 0
2 0 1 2 1 1 2 2 0 1 2 1

Sabit v ve t için PHFN(k, v, t) değerinin log k gibi büyüdüğü iyi bilinmektedir (örneğin Mehlhorn 82, Fredman–Komlós 84, Blackburn–Wild 98'e bakınız).

Ancak belirli PHF'leri oluşturmak hâlâ zordur.

Ben neden ilgileniyorum (ve sizin neden ilgilenmeniz gerekir)?

Kapsama Dizileri

Tanım

N, k, t ve v pozitif tam sayılar olsun.

C, boyutu v olan bir alfabe Σ'dan alınan girişlere sahip N × k boyutunda bir dizi olsun; genellikle

Σ = {0, ..., v − 1}

alınır.

Dizi, aşağıdaki t‑yollu etkileşimi kapsar:

{(cᵢ, νᵢ) : 1 ≤ i ≤ t}

eğer C dizisinin en az bir ρ satırında, ρ satırı ve cᵢ sütunundaki giriş 1 ≤ i ≤ t için νᵢ değerine eşitse.

(ν₁, ..., νₜ), 1 ≤ i ≤ t için νᵢ ∈ Σ olacak şekilde bir t‑li ise ve (c₁, ..., cₜ)

tane sütun indeksinden oluşan bir demet ise

cᵢ ∈ {1, ..., k}

ve νᵢ ≠ νⱼ olduğunda cᵢ ≠ cⱼ koşulu sağlanıyorsa, o zaman

{(cᵢ, νᵢ) : 1 ≤ i ≤ t}

ifadesi bir t‑yollu etkileşimdir.

Dizi C, her t‑yollu etkileşimi kapsadığında kuvveti t olan bir kapsama dizisi CA(N; t, k, v) olur.

Örnek: CA(13; 3, 10, 2)

0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
1 1 0 1 0 0 0 0 1 1
0 1 1 0 1 0 1 0 0 1
0 0 0 1 1 1 0 0 0 0
1 1 0 0 1 0 0 1 0 0
0 1 0 1 1 1 0 1 1 0
1 0 0 1 0 1 0 0 0 0
1 1 1 0 0 1 1 0 0 1
1 0 0 1 0 0 1 0 0 0
0 0 0 1 1 1 0 1 0 0
0 0 1 1 1 0 1 0 0 0
1 1 1 0 1 0 0 0 1 1

Motivasyon: Yazılım Etkileşim Testi

Her biri basit bir işlevi yerine getirmesi amaçlanan yazılım, donanım ve ağ bileşenlerini birleştirerek büyük bir yazılım sistemi oluşturun.

Her bileşen doğru çalışsa bile, bileşen seçimleri arasındaki etkileşimler hatalara yol açabilir.

Her t‑yollu etkileşim en az bir çalıştırmada test edilir.

Teorem

Eğer bir PHF(s; k, m, t) ve bir CA(N; t, m, v) mevcutsa, o zaman bir CA(sN; t, k, v) da mevcuttur.

Şöyle olsun:

Aşağıdaki şekilde sN × k boyutunda C = (cᵢⱼ) dizisini elde edin:

Her 1 ≤ i ≤ s, 1 ≤ j ≤ N ve 1 ≤ ℓ ≤ k için

c_{(i−1)N + j, ℓ} = a_{j, b_{i,ℓ}}.

Mükemmel Hash Aileleri Oluşturma Yöntemleri

PHF oluşturmak için çeşitli yöntemler vardır:

Yöntemler ve Sınırlamalar

Hâlâ büyük bir zorluk vardır.

Bu nedenle PHF'leri açık biçimde oluşturan yöntemlere ihtiyaç vardır.

Rastgele Bir Yöntem

{1, ..., v}^{N×k} kümesinden bir dizi eşit olasılıkla rastgele seçin.

Herhangi bir t sütun kümesi için, ayrılmamış olma olasılığı

(1 − ∏_{i=1}^{t} (v + 1 − i) / v^t)^N

şeklindedir.

Buna göre ayrılmamış t sütun kümelerinin beklenen sayısı

(k choose t) · (1 − ∏_{i=1}^{t} (v + 1 − i) / v^t)^N

olur.

Rastgeleliği Ortadan Kaldırma: Stein–Lovász Yöntemi

Bir satır ile o satır tarafından ilk kez ayrılan bir t‑kümesi sütun seçmenin tüm olası yollarını iki farklı şekilde sayın.

Henüz ayrılmamış t‑kümelerinin sayısı σ olsun.

  1. Bir satır tarafından ayrılan t‑kümelerinin beklenen sayısı ψ ise, (satır, ayrılan sütun kümesi) çiftlerinin sayısı ψ v^k olur.
  2. Henüz ayrılmamış belirli bir T t‑kümesi için, onu ayıran satırların sayısı

v^{k−t} ∏_{i=1}^{t} (v + 1 − i)

şeklindedir.

Dolayısıyla bu tür çiftlerin sayısı

σ v^{k−t} ∏_{i=1}^{t} (v + 1 − i)

olur.

Hiperçizge Renklendirme

Herhangi bir aşamada, ayırt edilmesi gereken t‑kümelerinin kümesi k düğüm üzerinde t‑uniform bir hiperçizge oluşturur.

Kalan tüm t‑kümeleri bir sonraki satır tarafından ayrılacaksa, bu satır k düğümü v renkle renklendiren bir yapı oluşturmalıdır.

Her t‑kümesi polikromatik (gökkuşağı) olmalı, yani t farklı renk almalıdır.

Güçlü kromatik sayı, böyle bir renklendirme için gereken en az renk sayısıdır.

Ancak güçlü kromatik sayıyı hesaplamak genel durumda NP‑zor bir problemdir.

Ortalama Yeterince İyidir

Önemli bir gözlem: analiz, en iyi satırın seçilmesini gerektirmez—yalnızca en az ortalama kadar iyi olan bir satırın seçilmesi yeterlidir.

Şunları hesaplayabiliriz:

Böylece bir satırın ortalama kadar iyi olup olmadığını doğrulayabiliriz.

Yoğunluk

Bir kısmi satır R, aşağıdaki kümede yer alan bir vektördür:

({1, ..., v} ∪ {⋆})^k

Burada ⋆ “henüz belirlenmemiş” anlamına gelir.

⋆ girişlerini rastgele doldurursak, yeni ayrılan t‑kümelerinin beklenen sayısına R'nin yoğunluğu denir.

R → R′ olduğunda, R′ satırı R içindeki bir ⋆ işaretinin {1, ..., v} kümesinden bir değerle değiştirilmesiyle elde edilir.

Bir doldurma dizisi şu koleksiyondur:

R_k, ..., R_0

burada R_i tam olarak i adet yıldız içerir ve R_i → R_{i−1}.

Eğer yoğunluk bu dizi boyunca hiç azalmazsa, son satır R₀ daha önce ayrılmamış t‑kümelerinin en az ortalama kadarını ayırır.

Satırları Verimli Şekilde Oluşturma

Bir R_i kısmi satırını ele alalım.

Her sembol seçimi s için, diğer t−1 indeksleri seçmenin

(k−1 choose t−1)

yolunun tamamı üzerinde koşullu beklentilerin toplamı δ_s hesaplanır.

Toplamı en az ortalama olan bir s sembolü seçin.

Pratik Hususlar

t sabit olduğunda, ortalama kadar iyi bir satır oluşturmak k cinsinden polinom zaman gerektirir.

Ancak t üs içinde yer aldığından, pratikte t küçük olmalıdır.

Yöntem şu iki açıdan açgözlüdür:

Verimliliği, en iyi satırı zorunlu kılmak yerine ortalama bir satırı kabul etmesinden kaynaklanır.

Pratikte Yoğunluk

Deneysel grafikler, sütun sayısı arttıkça yoğunluk yönteminin davranışını göstermektedir.

Log(Sütun Sayısı)

Sonuç