Minimal Mükemmel Karma Fonksiyonlarını Bulma

Gary Haggard
Bilgisayar Bilimleri Bölümü
University of Maine at Orono

Kevin Karplus
Bilgisayar Bilimleri Bölümü
Cornell University

ÖZET

Kapsamlı arama yapmadan minimal mükemmel karma fonksiyonları bulmak için bir sezgisel yöntem verilmiştir. İzlenen prosedür, sözlük için bir dizi grafik (veya hiper grafik) modeli oluşturmak ve ardından minimal mükemmel karma fonksiyonunun kurulmasında kullanılmak üzere bu modellerden birini seçmektir. Bu fonksiyonun kurulumu, grafiğin köşelerini numaralandırmak için kullanılan bir geri izleme algoritmasına dayanır. Grafik modelinin dikkatli seçimi, arama için harcanan süreyi sınırlar.

181 kelimeye kadar olan sözlükler için iyi sonuçlar elde edilmiştir. Aynı teknikler kullanılarak 667 kelimeye kadar olan kümeler için minimal olmayan mükemmel karma fonksiyonları bulunmuştur.

Minimal mükemmel bir karma fonksiyonu, (K) kümesinden (n) ardışık tam sayıya bire bir eşlemedir. Bu makale, yaklaşık 180 kelimeye kadar olan kümeler için bu tür fonksiyonları hızlı biçimde bulmaya yönelik bir yöntem sunar. Aynı teknikler daha büyük kümelere uygulanarak mükemmel karma fonksiyonları bulunabilir (yine bire bir eşleme, ancak (n > |K|)).

Sıradan karma fonksiyonlarının hesaplanması ucuzdur ve iyi karma fonksiyonları aileleri literatürde tanımlanmıştır [CW]. Mükemmel bir fonksiyon bulunana kadar rastgele karma fonksiyonlarını inceleme yaklaşımı denenmiştir [SP], ancak mükemmel karma fonksiyonları çok seyrek olduğu için (n) büyük olduğunda (n) boyutlu kümelerde bu yaklaşım uygulanabilir değildir ((n^{|K|}) olası karma fonksiyonu içinde yalnızca (n!/(n-|K|)!) tanesi mükemmeldir).

Cichelli minimal mükemmel karma fonksiyonlarını bulmak için bir yöntem sunmuştur [C]. Yalnızca şu biçimdeki karma fonksiyonları ele alınmıştır

h(word) = g(first letter) + g(last letter) + length(word)

Bu biçimde mükemmel karma fonksiyonu bulunmayan birçok yararlı kelime kümesi vardır. İlk ve son harf için farklı fonksiyonlar kullanmak ya da diğer harf konum çiftlerini dikkate almak bile yeterli değildir.

Örneğin, PASCAL ayrılmış sözcüklerinin ve önceden tanımlı tanımlayıcılarının tam listesi şu altı sözcüğü içerir:

CASE, ELSE, PAGE, READ, REAL, TRUE ve TYPE.

Sager [Sa], gerekli fonksiyonlar için geri izleme aramasına hazırlanmak amacıyla farklı bir ara işlem kullanan Cichelli yöntemine yönelik bir iyileştirme önermektedir. Bizim yöntemimiz Cichelli’nin yaklaşımını genelleştirir ve geri izleme aramasına hazırlanmak için Sager’e göre daha esnek bir ara işleme adımı kullanır.

Şu biçimdeki karma fonksiyonlarını arıyoruz

h(word) = length(word) + (\sum g_i(a_i(word)))

burada (a_i(word)), kelimenin uzunluğuna bağlı olarak kelimeden bir harf seçer ve (g_i(letter)) tablo araması ile hesaplanır. Burada açıklanan yöntem, Pascal’ın ayrılmış sözcükleri ve önceden tanımlı tanımlayıcılarından oluşan 76 kelimelik sözlüğün özel bir işlem gerektirmeden kurulmasına olanak tanır.

GİRİŞ

Şekil 1

Hiçbir iki seçici fonksiyon CASE, ELSE, PAGE, READ, REAL, TRUE ve TYPE sözcüklerini birbirinden ayıramaz.

Arama iki bölümden oluşur.

İlk olarak, şu vektörün

(length, a₁, …, aₘ)

her kelimeyi benzersiz biçimde tanımlamasını sağlayacak seçici fonksiyonlar ararız. Bu vektörler, köşeleri (a_i) tarafından seçilen harfler olan m-parçalı bir hiper grafiğin kenarları olarak düşünülebilir. Kelime uzunluğu kenar için bir etiket olarak tutulur.

İkinci olarak, her kelimenin 1, 2, …, n içindeki farklı bir tam sayıya eşlenmesini sağlayacak (g_i(letter)) değerlerini ararız; burada n kelime kümesinin büyüklüğüdür. Yani hiper grafiğin her köşesine bir değer atanır ve kenar etiketinin değeri ile köşelerdeki değerlerin toplamı, her hiper kenar için (1..n) aralığında farklı bir tam sayı olur.

Derecesi bir olan köşelere bağlı kenarlar istenen herhangi bir karma değerine atanabilir; çünkü bu köşe, diğer köşe değerlerinden bağımsız bir değer alabilir. Böylece köşe atama problemi, yalnızca o kenara özgü bir köşe içeren tüm kenarların silinmesiyle basitleştirilebilir. Azaltılmış grafikte yeni derece‑bir köşeler oluşabilir ve bu da daha fazla kenarın silinmesine izin verir. Bu süreç tekrarlandığında sonunda derecesi bir olan hiçbir köşesi olmayan bir grafik elde edilir.

Kaldırılan kenarlara (ağaç kenarları adını veriyoruz), azaltılmış grafikteki tüm kenarlara değer atandıktan sonra kaldırılma sıralarının tersine göre karma değerleri atanır.

Küçük kümelerde ağaç kenarları grafiğin önemli bir bölümünü oluşturur ve minimal mükemmel karma fonksiyonları çoğu zaman elle bulunabilir. Örneğin, ay kısaltmaları için:

JAN, FEB, MAR, APR, MAY, JUN, JUL, AUG, SEP, OCT, NOV ve DEC

ikinci ve üçüncü harflerin seçilmesi yalnızca ağaç kenarları içeren bir grafik verir (bkz. Şekil 2). Rastgele olarak

JAN = 1 … DEC = 12

seçilirse, köşe değerlerini Şekil 3’te gösterildiği gibi atayabiliriz.

Şekil 2

Ay adlarının kısaltmalarının ikinci ve üçüncü harfleri için grafik.

Şekil 3

Ay adlarının kısaltmaları için köşe atamaları.

Seçici Fonksiyon Araması

Seçici fonksiyonlardan (kelimeler içindeki harf konumlarının seçimi) oluşan bir küme, sabit bir fonksiyon ailesinden seçilen fonksiyon kümeleri üzerinde sınırlı bir arama yapılarak belirlenir. Biz 27 farklı seçici fonksiyondan oluşan bir aile kullanıyoruz, ancak aileye yeni fonksiyonlar kolayca eklenebilir.

Her seçici fonksiyon kümesi için bir kelime hiper grafiği kurulur. Hiçbir iki kelime aynı uzunluk etiketiyle aynı kenara eşlenmiyorsa, seçici fonksiyon kümesi kabul edilir ve köşe değerlerinin atanmasına başlanır.

Eğer tüm kümeler kelimelerin özdeş kenarlara eşlenmesine izin veriyorsa, en iyi birkaç küme tutulur ve bunlardan yeni ve daha büyük kümeler üretilir. Bir seçici fonksiyon kümesinden, ailede olup kümede henüz bulunmayan bir fonksiyon eklenerek daha büyük bir küme elde edilir.

Önce boş kümeyi ele alırız: kelimeler yalnızca uzunluklarına göre ayrılabiliyor mu? Daha sonra boş kümenin tüm genişletmelerini inceleriz: herhangi bir tek seçici fonksiyon yeterli mi? En iyi birkaç seçici fonksiyon hatırlanır ve bu en iyi fonksiyonlardan birini içeren tüm seçici fonksiyon çiftleri denenir.

Bu işlem daha yüksek boyutlar için devam eder. (k) adet seçici fonksiyondan oluşan en iyi birkaç küme hatırlanır ve hatırlanan kümelerden birini içeren (k+1) fonksiyonlu tüm kümeler denenir. Uygun bir küme bulunana kadar ya da kümelerin boyutu çok büyüyene kadar seçici fonksiyon kümeleri denenir.

Bir seçici fonksiyon kümesinin kalitesi şu ölçütlerin ağırlıklı toplamı ile değerlendirilir:

• farklı kenarların sayısı
• ağaç kenarlarının sayısı
• kelime hiper grafiğindeki köşe sayısı

Bunlar arasında ağaç kenarı sayısı daha önemlidir. Kullanılan ağırlıklar hakkında daha fazla ayrıntı için bkz. [KH].

Köşe Değeri Ataması

Seçici fonksiyonlar belirlendikten sonra kelime hiper grafiğinin tüm köşelerine değer atanmalıdır. Ağaç kenarları kaldırılabilir ve karşılık gelen köşelere, diğer köşeler değer aldıktan sonra ters sırayla değer verilir.

Grafiğin ana kısmı için köşe ataması şu şekilde ilerler:

1. Bir köşe seç.
2. Eğer geçerli bir atama yoksa geri izleme yap ve önceki bir seçimi değiştir.
3. Aksi halde köşeye mümkün olan en küçük geçerli değeri ata (köşe değeri kısıtlanmamışsa 0).
4. Tüm köşelere değer atanana kadar 1–3 adımlarını tekrarla.

En basit geri izleme düzeni, köşelerin sabit bir sıralamasını kullanmak ve bir çakışma oluştuğunda en son yapılan seçimi geri almaktır. Bu düzen küçük grafikler için iyi çalışır (örneğin [C]’deki grafikler), ancak daha büyük grafiklerde uzun sürebilir. Hem köşe seçimini hem de geri izlemeyi hızlandırmak için sezgisel yöntemler eklenmiştir.

Köşe Seçimi Sezgiselleri

Köşe seçimi sezgisel yöntemleri en zor köşeleri önce seçmeye çalışır; böylece gerekli geri izlemeler mümkün olan en erken noktada tetiklenir.

Emin, atanmamış köşe sayısı en az olan kenarların kümesi olarak tanımlansın (tüm köşeleri atanmış kenarlar hariç). Bulunan en iyi köşe seçimi sezgiseli, Emin içindeki kenarlarda en fazla sayıda kenara sahip köşeler arasından, Emin içindeki kenarlar için kısmi toplam aralığı en geniş olan köşeyi seçmektir.

Bu sezgisel yöntem bir veya iki boyutlu hiper grafiklerde iyi çalışır, ancak daha yüksek boyutlarda o kadar etkili değildir.

Yalnızca bir köşe değeri atanmamış olan kenarlar köşe değerlerini etkiler. Bunlara neredeyse tamamlanmış kenarlar denir. Eğer grafikte neredeyse tamamlanmış kenar yoksa, seçilen köşeye rastgele bir değer atanır.

Geri İzleme Sezgiselleri

Geri izleme sezgiselleri köşe seçimi sezgisellerinden daha karmaşıktır. Başarılı olan karma fonksiyonu aramaları nadiren geri izleme yapar, bu nedenle sezgiseller onları fazla etkilemez. Uzun süren aramalar ise zamanlarının neredeyse tamamını geri izleme yaparak geçirir.

Üç farklı çakışma türü geri izlemeyi tetikleyebilir:

• Kenar çakışmaları: iki farklı neredeyse tamamlanmış kenarın aynı değere sahip olması.
• Too‑big çakışmaları: neredeyse tamamlanmış kenarlar için kısmi toplam aralığının, kullanılmayan kenar değerleri aralığından daha büyük olması.
• No‑fit çakışmaları: her köşe atamasının, bazı neredeyse tamamlanmış kenarların mevcut tamamlanmış bir kenarla çakışmasına yol açması.

Kenar çakışmaları için, çakışan kenarların kısmi toplamları farklı olana kadar köşe değerleri geri alınır. En son geri alınan köşeye daha büyük bir değer atanır ve köşe ataması tekrar ileri doğru devam eder.

Too‑big çakışmaları için, kaldırılan köşe en küçük kısmi toplama sahip kenarda bulunup en büyük kısmi toplama sahip kenarda bulunmayana kadar veya neredeyse tamamlanmış kenarların kısmi toplamlarının sığacağı bir köşe ataması yapılabilene kadar köşe değerleri geri alınır.

No‑fit çakışmaları için, neredeyse tamamlanmış bir kenarın bazı köşeleri kaldırılana kadar köşe değerleri geri alınır. Kısmi toplamı en yüksek olan neredeyse tamamlanmış kenar dışlanır; çünkü köşeleri için daha büyük atamalar yapmak çakışmayı çözme olasılığı düşük bir durumdur.

Geri izleme sezgiselleri ve farklı çakışmaların ortaya çıkma istatistikleri hakkında daha fazla ayrıntı için bkz. [KH].

Çalışma Süresi

Çalışma süresinin kuramsal analizi zordur; çünkü kelime kümeleri için ikna edici bir modele sahip değiliz. Deneysel olarak programımız bir VAX 11‑780 üzerinde başarılı bir arama için yaklaşık

0.06 × (kelime sayısı)¹·⁵

CPU saniyesi harcamaktadır. Süre, minimal mükemmel bir karma fonksiyonunun mu yoksa yalnızca mükemmel bir karma fonksiyonunun mu arandığına bağlı görünmemektedir.

Başarısız aramalar çok daha uzun sürer ve tamamlanana kadar çalıştırılmalarına izin verilmemiştir.

KAYNAKLAR

[C] Richard J. Cichelli. “Minimal Perfect Hash Functions Made Simple.” Communications of the ACM, 23(1), Ocak 1980.

[CW] J. Lawrence Carter ve Mark N. Wegman. “Universal Classes of Hash Functions.” Proceedings of the 9th Annual ACM Symposium on Theory of Computing, Mayıs 1977, s. 106–112.

[KH] Kevin Karplus ve Gary Haggard. Finding Minimal Perfect Hash Functions. Cornell Computer Science Technical Report TR84‑637, Eylül 1984.

[Sa] T. J. Sager. “A Polynomial Time Generator for Minimal Perfect Hash Functions.” Communications of the ACM, 28(5), Mayıs 1985, s. 523–532.

[SP] R. Sprognoli. “Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets.” Communications of the ACM, 20(11), Kasım 1977, s. 841–850.

Bu materyalin tamamının veya bir bölümünün ücret alınmadan kopyalanmasına, kopyaların doğrudan ticari kazanç amacıyla yapılmaması veya dağıtılmaması, ACM telif hakkı bildiriminin ve yayının başlığının ve tarihinin kopyalarda yer alması ve kopyalamanın Association for Computing Machinery izniyle yapıldığının belirtilmesi koşuluyla izin verilir. Bunun dışındaki kopyalama veya yeniden yayımlama işlemleri için ücret ve/veya özel izin gereklidir.