O(1) En Kötü Durum Erişim Süresi ile Seyrek Bir Tabloyu Saklama

Özet

m öğeden oluşan bir evrenden seçilmiş n öğelik bir kümenin temsil edilmesi için, n + o(n) alan kullanan ve üyelik sorgularını sabit zamanda gerçekleştirebilen bir veri yapısı açıklanmaktadır. Hem veri yapısı hem de sorgu algoritması uygulanması kolaydır.

Kategoriler ve Konu Tanımlayıcıları: E.1 [Veri Yapıları]: Tablolar; F.2.2 [Algoritmaların Analizi ve Problem Karmaşıklığı]: Sayısal Olmayan Algoritmalar ve Problemler—sıralama ve arama
Genel Terimler: Algoritmalar, Kuram
Ek Anahtar Sözcükler ve İfadeler: Hashing, karmaşıklık, seyrek tablolar

Aşağıdaki arama problemi ele alınmaktadır. m olası isimden oluşan bir U evreninden (m > n) seçilmiş n farklı isimden oluşan bir S kümesi, "q, S içinde mi ve eğer öyleyse T içinde nerede bulunabilir?" biçimindeki üyelik sorgularının verimli biçimde işlenmesine izin verecek şekilde bir T belleğinde saklanacaktır. S kümesinin statik olduğunu varsayıyoruz; dolayısıyla temel kaygılarımız S için gereken depolama alanı ve sorguların işlenmesi için gereken süredir. Hashing şemaları bu probleme O(n) depolama kullanarak ve sorgu başına ortalama Θ(1) zamanda sorgu yapılmasına izin vererek bir çözüm sağlar. Bu makalede, depolama için O(n) sınırını korurken bir sorgu için gereken en kötü durum süresine odaklanıyoruz.

Bu soru çeşitli makalelerde ele alınmıştır, örneğin [1]–[4]. Yao [4] bu problem için ilginç bir karmaşıklık modeli önermektedir. Yao’nun çerçevesinde S, U = {1, 2, ..., m} kümesinin kardinalitesi n olan bir alt kümesidir. T belleği her hücresinde U’dan bir öğe saklar ve bu hücrelere adresleri aracılığıyla rastgele erişilebilir. U içindeki bir q elemanı için yapılan sorgu, T içindeki bir hücreler dizisinin yoklanmasıyla işlenir. Bu yoklama dizisi uyarlanabilir olabilir: bir sonraki yoklanacak hücre tam olarak q ve daha önce yoklanan hücrelerin içerikleri tarafından belirlenir.

Sorgu süresi yoklanan hücre sayısı cinsinden ölçülür ve depolama T’nin boyutu (toplam hücre sayısı) olarak tanımlanır. Yao [4], m en azından n’e göre üstel olarak büyüdüğü sürece (m ≥ e^{2n} yeterlidir) depolama n + 1 ve en kötü durum sorgu süresi 2’nin aynı anda sağlanabileceğini gösterir. Yao ve Tarjan [3], O(n) depolama ve en kötü durum sorgu süresi O(log m / log n) değerlerinin genel olarak elde edilebileceğini gösterir. Dolayısıyla m, n’e göre polinomla sınırlıysa veya en azından n’e göre üstel olarak büyüyorsa doğrusal depolama ve sabit sorgu süresi aynı anda elde edilebilir. Ancak Yao’nun [4] belirttiği gibi m için bir ara aralık vardır; örneğin m = 2^{√n} durumunda doğrusal depolama ve sabit sorgu süresi olasılığı yukarıda alıntılanan sonuçlarla kesinleşmemiştir.

Bir sonraki bölümde tüm m ve n değerleri için doğrusal depolama ve sabit en kötü durum sorgu süresi sağlayan bir depolama tekniği açıklıyoruz. Sorgu algoritmasının uygulanması özellikle kolaydır ve m ile n’in göreli büyüklükleri ispatlarda rol oynamaz. Bölüm 3, geliştirdiğimiz yapıyı motive eden genel bir çerçeveyi tartışır. Bölüm 4’te sabit sorgu süresini korurken alan kullanımını n + o(n) değerine düşüren bir iyileştirme anlatılmaktadır. Bölüm 5 ise yöntemimizin bazı varyasyonlarını açıklar.

2. Temel Temsil ve Sorgu Algoritması

Bu bölümde küme temsil yöntemimizin arkasındaki ana fikri doğrusal depolama ve sabit sorgu süresi sağlayan bir teknikle gösteriyoruz.

U = {1, ..., m} olsun. Tartışmayı basitleştirmek için p = m + 1 sayısının asal olduğunu varsayıyoruz. a mod b gösterimiyle 1 ≤ x < b koşulunu sağlayan ve x ≡ a (mod b) olan tekil tamsayı x’i ifade ediyoruz. Aşağıdaki lemmaya ihtiyaç duyuyoruz.

Lemma 1

|W| = r olan W ⊆ U verilsin ve k ∈ U ile s ≥ r olsun. Tanım:

B(s, W, k, j) = |{ x | x ∈ W ve (kx mod p) mod s = j }|

burada 1 ≤ j ≤ s.

Başka bir deyişle, B(s, W, k, j) değeri

x → (kx mod p) mod s

fonksiyonunun, x yalnızca W içinde dolaşırken j değerini kaç kez aldığıdır. O halde aşağıdaki koşulu sağlayan bir k ∈ U vardır:

∑_{j=1}^{s} B(s, W, k, j)^2 < r^2 / s.

İspat

Şunu gösteriyoruz:

∑{k=1}^{p−1} ∑{j=1}^{s} B(s, W, k, j)^2 < (p − 1) r^2 / s.

Bu toplam, x, y ∈ W, x ≠ y, 1 ≤ k < p olmak üzere

(kx mod p) mod s = (ky mod p) mod s

koşulunu sağlayan (k, {x, y}) çiftlerinin sayısıdır.

x ≠ y için {x, y} çiftinin bu niceliğe katkısı, yukarıdaki eşitliği sağlayan k değerlerinin sayısından fazla olamaz ve bu sayı ≤ 2(p − 1)/s değerini aşmaz. Olası (r choose 2) adet {x, y} seçimi üzerinde toplama yaptığımızda, toplamın gerçekten (p − 1) r^2 / s ile sınırlı olduğu sonucuna ulaşırız ve ispat tamamlanır. □

Sonuç 2

Aşağıdaki eşlemenin W üzerinde bire bir olduğu bir k′ ∈ U vardır:

x → (k′x mod p) mod r^2

İspat

s = r^2 seçilirse, Lemma 1 tüm j değerleri için B(r^2, W, k′, j) ≤ 1 sağlayan bir k′ verir. □

|S| = n olacak şekilde S ⊆ U verildiğinde, S kümesini temsil etme tekniğimiz şu şekilde çalışır.

T[0] hücresindeki k içeriği, S kümesini n blok W_j, 1 ≤ j ≤ n olacak biçimde aşağıdaki fonksiyonun değerine göre ayırmak için kullanılır:

f(x) = (kx mod p) mod n.

T belleğinde karşılık gelen T_j bloklarına işaretçiler T[j] konumlarında sağlanır, 1 ≤ j ≤ n.

Daha açık olarak, Sonuç 1’i sağlayan bir k seçilir (W = S ve r = n olacak şekilde), böylece

∑ |W_j|^2 < 3n.

W_j için ayrılan T_j bloğunun alanı

|W_j|^2 + 2

kadardır.

Alt küme W_j, bu alan içinde Sonuç 2 tarafından sağlanan mükemmel hash fonksiyonu kullanılarak çözülür (W = W_j ve r = |W_j| olacak şekilde). T_j bloğunun ilk konumunda |W_j| saklanır ve ikinci konumunda Sonuç 2 tarafından verilen k′ değeri saklanır. Her x ∈ W_j elemanı

((k′x mod p) mod |W_j|^2) + 2

konumunda saklanır.

Üyelik Sorgusu

q için bir üyelik sorgusu şu şekilde gerçekleştirilir:

1. k = T[0] olarak ayarlanır ve j = (kq mod p) mod n hesaplanır.
2. T[j] erişilerek T içindeki T_j bloğuna işaretçi elde edilir ve bu işaretçi kullanılarak T_j bloğunun ilk iki konumundaki |W_j| ve k′ değerlerine erişilir.
3. T_j bloğunun ((k′q mod p) mod |W_j|^2) + 2 hücresine erişilir; q ancak ve ancak bu hücrede bulunuyorsa S içindedir.

Bir sorgu beş yoklama gerektirir ve Sonuç 1’deki k seçimimiz T’nin boyutunun en fazla 6n olduğunu garanti eder.

Örnek

m = 30, p = 31, n = 6,
S = {2, 4, 5, 15, 18, 30}

30 için bir sorgu şu şekilde işlenir:

1. k = T[0] = 2,
   j = (30 · 2 mod 31) mod 6 = 5.
2. T[5] = 16 ve T[16] ile T[17] hücrelerinden 5. bloğun iki elemanı olduğunu öğreniriz.

S için temsilin oluşturulması için gereken süre en kötü durumda O(mn) kadar kötü olabilir; çünkü k değerini bulmak uygun bir değer elde edilene kadar birçok olası değerin denenmesini gerektirebilir. Ancak T’nin boyutunu sabit bir katsayı kadar artırarak temsilin rastgele beklenen O(n) zamanda oluşturulabileceğini ve bunun m ile S’den bağımsız olduğunu gösterebiliriz. Bunun için Sonuç 1 ve 2’nin aşağıdaki varyantlarını kullanırız.

Sonuç 3

U içindeki k değerlerinin en az yarısı için

∑_{j=1}^{r} B(r, W, k, j)^2 < 5r.

İspat

Denklem (1) kullanılır ve bir dizideki terimlerin en fazla yarısının dizinin ortalama değerinin iki katını aşabileceği gerçeğinden yararlanılarak sonuç elde edilir. □

Sonuç 4

Aşağıdaki eşleme

x → (k′x mod p) mod 2r^2

U içindeki k′ değerlerinin en az yarısı için W üzerinde bire birdir.

İspat

Denklem (1)’de s = 2r^2 seçilir ve U içindeki k′ değerlerinin en az yarısı için

∑ B(2r^2, W, k′, j)^2 < 1

olduğu sonucuna ulaşılır; bu da sonucu doğrular. □

Sonuç 3 ve 4 kullanılarak, n boyutundaki bir S kümesini daha önce olduğu gibi temsil ederiz; ancak artık S’nin bir W_j bloğunu saklamak için 2|W_j|^2 + 2 alan ayırırız. Bunun kazancı, belirli bir k (veya k′) seçiminin uygun olma olasılığının 1/2’den büyük olmasıdır. k (veya k′) seçimleri uygun değerler bulunana kadar rastgele yapılır.

Yöntemlerimizi biraz değiştirerek en kötü durum oluşturma süresini O(n^3 log m) olarak garanti edebiliriz.

Lemma 2

S içindeki hiçbir elemanı bölmeyen ve bu elemanları mod q altında farklı kalan sınıflarına ayıran q < n^2 log m olacak bir asal sayı vardır.

İspat

S = {x₁, ..., x_n} için

t = ∏_{i<j} (x_i − x_j)

tanımlansın.

Açıktır ki log |t| ≤ (n^2) log m. Asal sayı teoremi

log(∏_{q ≤ x} q) = x + o(x)

verdiğinden, t’yi bölmeyen bir q < n^2 log m asalının var olduğu sonucuna ulaşırız. Bu asal q lemmayı sağlar. □

Şu şekilde ilerleriz. Eğer m < n^2 log n ise O(nm) = O(n^3 log m) olur. Eğer m > n^2 log n ise O(nq) zamanda Lemma 2’yi sağlayan bir q asalı elde edilir ve T[−1] konumunda saklanır. T’nin geri kalanı daha önceki gibi tanımlanır; ancak x ∈ S elemanının saklanacağı konum, x yerine x mod q hash değeri kullanılarak belirlenir; böylece U fiilen daha küçük bir evrenle değiştirilmiş olur:

U′ = {1, ..., q − 1}, burada q ≤ n^2 log m.

Toplam oluşturma süresi O(nq) = O(n^3 log m) ile sınırlıdır.

Yukarıda açıklanan şema aşağıdaki genel çerçeve içinde ifade edilebilir.

T[0] içindeki k değeri U üzerinde n renkli bir renklendirme oluşturur:

x → (kx mod p) mod n.

Yao’nun iki yoklamalı yöntemi de benzer şekilde X = {C_k} biçiminde indekslenmiş bir n-renklendirme ailesine dayanır; burada |X| ≤ m ve her S ⊆ U, |S| = n için S üzerinde bire bir olan bir C_k vardır. Yao bu tür bir X ailesine ayırıcı sistem adını verir.

Yao’nun yöntemiyle S kümesi T içinde şu şekilde saklanır: T[0] içine k konularak C_k renklendirmesi çağrılır ve x ∈ S elemanı, C_k altındaki rengi j ise T[j] içine yerleştirilir. Böyle bir X ailesi varsa bu yaklaşım çalışır. |X| ≤ m kısıtı, elemanlarının T[0]’ın izin verilen aralığıyla indekslenmesinden kaynaklanır.

Basit bir sayma argümanı en az

(m)/(m/n)^n

adet renklendirmenin bir ayırıcı sistem için gerekli olduğunu gösterir; buradan

m > n^n / n!

sonucunu elde ederiz.

R. Graham olasılıksal bir argüman kullanarak eğer

m ≥ n^{n+2} / n! ≈ e^n

ise bir ayırıcı sistem X’in var olduğunu gösterir.

m = exp(o(n)) olduğunda Yao’nun yöntemini genişletmek için T[0] tarafından oluşturulan renklendirme altında çakışmaların kaçınılmaz olduğunu kabul ederiz. S’nin tek renkli bloklarına bin diyerek, bu binlerin içindeki elemanları ayırmak için ikincil renklendirmeler kullanmaya çalışırız. Eğer bir binin boyutu b yeterince küçükse, yani b ≤ log m, o zaman bu bin, b boyutlu alt kümeler için bir ayırıcı sistem içeren X′ ailesinden seçilen bir b-renklendirme ile çözülebilir.

Bir olasılıksal argüman ayrıca m ≥ n olan tüm durumlar için |X| ≤ m olacak şekilde n-renklendirmelerden oluşan bir X ailesinin var olduğunu ve her S ⊆ U, |S| = n için S’yi boyutu ≤ log n ≤ log m olan binlere ayıran bir C ∈ X renklendirmesinin bulunduğunu gösterir. Dolayısıyla Yao’nun modeli altında O(1) sorgu süresi ve O(n) depolama kullanan tablo saklama şemalarının var olduğu sonucuna ulaşırız. Ancak m ≥ n olan tüm durumlar için bu doğrultuda açık biçimde kurulmuş bir saklama şemaları sınıfı geliştiremedik. Bin boyutlarının tekdüze olarak log m ile sınırlı olduğu bu tür saklama şemalarına L∞ şemaları adını veriyoruz.

Yao’nun iki yoklamalı yöntemine tekrar dönersek, tabloda daha fazla alan kullanma olasılığını ele alırız; yani bir n boyutlu S kümesinin elemanlarını tamamen çözmek için t ≥ n olacak şekilde t-renklendirmeler kullanırız. Yine sayma ve olasılıksal argümanlar kullanılarak |X| ≤ m olacak şekilde t-renklendirmelerden oluşan bir X ailesinin var olduğu gösterilebilir; bu aile n boyutlu tüm S kümelerini çözebilir, yeter ki m yaklaşık olarak en az exp(n^2 / t) olsun; bu da yaklaşık olarak en iyi olası sınırdır. Dolayısıyla t = n^2 seçilerek m üzerindeki tüm kısıtlar kaldırılabilir.

n^2 renk kullanmak, yani n^2 alan kullanmak, başlangıç problemimiz açısından oldukça verimsizdir; ancak b boyutlu binleri çözmek için b^2 renk kullanmak makuldür, yeter ki ∑ b^2 küçük olsun. Olasılıksal argümanlar gerçekte |X| = m olan n-renklendirme ailelerinin neredeyse tamamının

∑ b^2 = O(n)

özelliğini sağladığını gösterir; bu, m ≥ n olan tüm durumlar ve n boyutlu her S kümesi için geçerlidir. Bu da doğrusal alan ve sabit sorgu süresine sahip tablo saklama şemalarının başka bir sınıfını sağlar; bunlara L2 şemaları adını veriyoruz. Açık L∞ şemaları kurmadaki zorlukların aksine, Bölüm 2’deki yapı açık bir L2 şemaları sınıfı sağlar.

Bu bölümde sabit sorgu süresini korurken depolama kullanımını n + o(n) değerine nasıl düşürebileceğimizi gösteriyoruz. Önce bir taslak sunuyoruz.

Bölüm 2’deki veri yapımız S’nin önce n bloğa ayrılmasını, ardından bu blokların veri yapısının ikinci seviyesinde çözülmesini içerir. İyileştirmemiz ise S’nin daha fazla sayıda g(n) bloğa (aşağıda belirlenecek) ayrılmasıyla başlar; bunların en fazla n tanesi boş değildir.

Birden fazla eleman içeren bloklar ikinci seviyede daha önce olduğu gibi çözülür. Ancak birden fazla eleman içeren blok sayısı çok az olacaktır ve bunları çözmek için gereken toplam alan yalnızca o(n) kadardır. Tek elemanlı bir bloğun elemanı doğrudan veri yapısının ilk seviyesinde saklanır.

Veri yapısının ilk seviyesi için gereken alanı g(n) değerinden n + o(n) değerine düşürmek amacıyla yardımcı bir veri yapısı kullanırız (aşağıda açıklanacaktır).

4. İyileştirme

O(1) En Kötü Durum Erişim Süresi ile Seyrek Bir Tabloyu Saklama

burada (Y_j), (1 \le j \le g(n)) ve (B(g(n), S, k, j) \ge 2) olan tüm (j) değerleri üzerindeki toplamı ifade eder.

S kümesi aşağıdaki fonksiyonun değerlerine göre bloklara ayrılır:

f(x) = (kx mod p) mod g(n).

g(n) öyle seçilecektir ki (n / g(n) = o(1)) olsun; bu nedenle denklem (4), iki veya daha fazla elemanı olan blokları (Bölüm 2’deki yöntem kullanılarak) çözmek için gereken toplam alanın o(n) olduğunu gösterir.

q için bir üyelik sorgusu işlenirken önce

j = (kq mod p) mod g(n)

sayısı hesaplanır; bu değer q ∈ S ise q’nun ait olması gereken S bölmesindeki W_j bloğunu belirler. Bu blokların en fazla n tanesi boştur değildir. Boş olmayan her W_j bloğu için T içinde bir hücre ilişkilendiririz ve burada şu bilgilerden biri saklanır:

• (a) |W_j| = 1 ise W_j’nin tek öğesi, veya
• (b) |W_j| ≥ 2 ise W_j’nin çözüldüğü veri yapısının ikinci seviyesine bir işaretçi.

Ayrıca (a) veya (b) durumunun hangisinin geçerli olduğunu belirtmek için bir etiket biti kullanırız. (Bu etiket bitleri (O(n / \log m) = o(n)) kelime içinde paketlenebilir.)

Bu yaklaşım, bir W_j bloğunun boş olup olmadığını belirlemek ve boş değilse W_j ile ilişkili hücreyi ve etiket bitini bulmak için yardımcı bir veri yapısı gerektirir. Bu yardımcı veri yapısının tasarımı Tarjan ve Yao [3] tarafından verilen benzer bir yapının küçük bir değişikliğidir.

Boş olmayan W_j bloklarıyla ilişkili hücreler artan j sırasına göre ardışık biçimde yerleştirilir. T′, bu hücrelerin bulunduğu T bölümünü göstersin.

Aralığı şu şekilde böleriz:

I = [1, g(n)]

I aralığı, boyutu ((g(n) / n)^2) olan (n^2 / g(n)) adet alt aralığa bölünür. (I) içindeki (n^2 / g(n)) adet alt aralığın her biri (a) için, (B[a]) adlı bir taban adresi ilişkilendirilir; bu adres, (j \in a) için boş olmayan (W_j) kümeleriyle ilişkili (T') içindeki hücrelerden hemen önceki konumun adresidir.

Bu taban adresleri, boyutu (n^2 / g(n) = o(n)) olan bir tabloda saklanır. İkinci bir tablo olan (A[j]), (j \in I), ofsetleri saklamak için kullanılır:

• (W_j = \varnothing) ise (A[j] = 0),
• aksi halde (j \in a) için (B[a] + A[j]), (W_j) ile ilişkili (T') içindeki adrestir.

(A[j]) en fazla ((g(n) / n)^2 + 1) olası değer alabildiğinden, (j \in I) için tüm (A[j]) tablosu

O(g(n) log(g(n) / n) / log n)

adet (T) hücresine sığdırılabilir.

(g(n) = n (\log n)^{1/2}) seçildiğinde, (A[j]) tablosu için ortaya çıkan alan gereksinimi (o(n)) olur ve böylece veri yapımız için toplam alan gereksinimi

n + o(n)

olur.

Bölüm 2'nin sonunda, (S) için gösterimin oluşturulması için gereken süreye ilişkin yapılan açıklamalar burada da geçerlidir ve aynı şekilde uygulanır.

Burada sunulan sonuçlar, aşağıdaki eşlemeyi

x ↦ ⌊(kx mod p) · s / p⌋

şunun yerine koyarsak da geçerliliğini korur:

(kx mod p) mod s.

Muhtemelen başka birçok uygun eşleme de bulunabilir. Özellikle büyük sayıların çarpılması sakıncalı görülüyorsa ilgi çekici olabilecek başka bir eşleme aşağıdaki gibidir.

(U)'nun, (s) asal sayı olmak üzere (d) boyutlu (s)-tabanlı vektörlerden oluşan küme olduğunu varsayalım. (U) içinde iki vektör verildiğinde

k = (k₁, ..., k_d) ve x = (x₁, ..., x_d)

(k · x) ile aşağıdaki iç çarpımı ifade ederiz:

k · x = Σ k_i x_i mod s.

Buna göre Lemma 1'in benzeri aşağıdaki eşleme için de geçerlidir:

x ↦ k · x.

Bu eşleme büyük sayılarla çarpma gereksinimini ortadan kaldırır ve ayrıca "kısa" (x) değerleri için (Hamming ağırlığı küçük olan (x)) (k · x) değerinin daha hızlı hesaplanabilmesi gibi ek bir avantaj sağlar. Ancak veri yapımız bu tür eşlemelerin çeşitli biçimlerini gerektirir.

Lemma 1'de (W = S), (s = g(n)) ve (r = n) seçildiğinde, bazı (k \in U) için

Σ B(g(n), S, k, j)² = o(n)

olduğunu elde ederiz.

(x ≥ 2) için (x² = O(x)) olduğundan, eşitlik (3) aşağıdakini ima eder:

Σ B(g(n), S, k, j)² = O(n g(n)).

5. Varyasyonlar

((s) sınırlı bir parametredir), bu da (U) içindeki elemanların farklı gösterimleri (farklı (s) değerlerine sahip) arasında dönüşüm yapmanın kolay olmasını gerektirir. Ayrıca gösterimler arasında geçiş yapılırken Hamming ağırlığının yaklaşık olarak korunmasını da isteriz.

Bunu gerçekleştirmenin açık bir yolu, bu gösterimler için bir blok kod yaklaşımı kullanmaktır; ikili kodlu ondalık (binary coded decimal) bunun bir örneğidir.

Kaynaklar

1. Jaeschke, G. Reciprocal hashing: A method for generating minimal perfect hashing functions.
2. Sprugnoli, R. Perfect hashing functions: A single probe retrieving method for static sets. Commun. ACM 20, 11 (Kas. 1977), 841–850.
3. Tarjan, R. E., and Yao, A. C.-C. Storing a sparse table. Commun. ACM 21, 11 (Kas. 1979).

Fredman, M. L., Komlós, J., and Szemerédi, E. Commun. ACM 24, 12 (Ara. 1981), 829–833.