Seni Hashing

Setelah mempelajari hashing, Anda mungkin perlu tahu tentang teknik-teknik khusus hashing. Teknik ini saya dapatkan melalui pengalaman, dan telah berkali-kali "menyelamatkan" peringkat tim pada kompetisi. Semoga berguna juga untuk Anda :)

Oh ya, selain rolling hash, nama-nama yang tercantum merupakan nama ciptaan saya. 

---

Rolling Hash

Teknik ini sangat umum digunakan. Saya mempelajarinya dari tutorial Topcoder.

Ceritanya adalah diberikan sebuah string S.
Bagaimana kita mendapatkan nilai hash dari semua substring S yang memiliki panjang k?
Fungsi hash yang digunakan pada rolling hash adalah menganggap string sebagai bilangan basis 26. Lebih umum lagi, basis ini sebenarnya boleh berapa saja. Misalkan basis yang dipilih adalah B.

Anggap S = "ayamxzc" dan k=4. Jika h[i] menyatakan nilai hash untuk S[i..i+k-1], maka bisa digambarkan nilai h[0] sampai h[3] sebagai berikut:

Jika kita sudah mengetahui nilai h[0], mencari nilai h[1] sebenarnya tidak perlu loop O(k) lagi. Terdapat k-1 karakter yang tumpang tindih antara h[0] dengan h[1], yaitu "yam". Dengan memanfaatkan fakta ini, sadari bahwa:

h[1] = (h[0] - a*B3)B + x*B0

Jadi mencari h[1] bisa dilakukan dalam O(1). Cukup "buang" karakter terkiri, lakukan "shift" dengan dikali B, lalu "masukkan" karakter terkanan. Setelah mendapat h[1], h[2] dan h[3] pun dapat dicari dengan cara serupa. Teknik inilah yang disebut dengan rolling hash.

Pada akhirnya seluruh tabel h[] dapat dicari dalam O(|S|).

Catatan:

• Berhubung h[i] bisa jadi sangat besar (lebih dari 64 bit integer), biasanya dilakukan modulo terhadap suatu bilangan prima besar (misalnya 10⁹+7). Jika dilakukan modulo, maka seluruh perhitungan h[i] harus dimodulo. Hati-hati terhadap operasi pengurangan pada rolling hash. Biasanya saya mendefinisikan fungsi MOD(a, b) yang menghitung a modulo b dengan benar, sekalipun a negatif:
  

  MOD(a,b) = ((a mod b) + b) mod b
  

• Basis yang saya gunakan umumnya adalah 31. Menurut gosip, operasi perkalian terhadap 31 sudah dioptimisasi oleh compiler. Menghitung x*31 dilakukan dengan cara ((x << 5) - x), yang hanya melibatkan operasi bitwise dan pengurangan. Ingat bahwa operasi penjumlahan/pengurangan lebih cepat dari perkalian. Kalau gosip ini benar, angka seperti 63, 127, 255 pun bisa digunakan.

---

Shifting Hash

Kadang-kadang, diperlukan operasi "shifting". Contoh:

• Diberikan dua string, yaitu S dan T
• Diketahui nilai hash untuk S dan T, misalkan nilainya adalah vS dan vT. Fungsi hash yang digunakan sama seperti penjelasan saya sebelumnya.
• Cari nilai hash untuk ST (S digabung dengan T)!

Tentu saja dapat dicari dalam O(|S|+|T|). Namun ada cara yang lebih cepat, yaitu cukup hitung:

vS*B|T| + vT

Jika digunakan fast modular exponentiation, kompleksitasnya menjadi hanya O(log |T|).

---

Partial Hash

Diberikan sebuah string S dan sejumlah pertanyaan berbunyi:

• Carikan saya nilai hash untuk S[i..j]

Perhatikan bahwa i dan j bisa sembarang bilangan, sehingga |S[i..j]| tidak konstan. Melakukan precomputation dengan rolling hash sekalipun membutuhkan waktu O(|S|²), meskipun pada akhirnya menjawab setiap pertanyaan dapat dilakukan dalam O(1).

Sekilas soal ini mengingatkan kita dengan partial sum. Dengan ide partial sum, kita dapat membuat partial hash.

Buat array p[] yang mana p[i] dirumuskan sebagai:

p[i] = hash(S[i..|S|-1])

Sebagai contoh:

Membuat tabel p[] dapat dilakukan dalam O(|S|). Salah satu caranya adalah dengan mencari dari belakang ke depan.

Kemudian jika diminta untuk mencari nilai hash untuk S[i..j], kita dapat menghitung p[i]-p[j+1], lalu melakukan "shift right". Misalkan untuk i=1 dan j=2:

Yang menjadi pertanyaan adalah: bagaimana melakukan "shift right"??
Seandainya saja kita bisa membagi p[1]-p[3] dengan B¹, urusan selesai. Namun ingat bahwa pembagian pada modulo arithmetic tidak bisa dilakukan sesederhana "membagi".

Pada modulo arithmetic, pembagian dapat dilakukan dengan mencari modular multiplicative inverse. Singkatnya, mencari:

\(\displaystyle \frac{a}{b} \mod c = a b^{-1} \mod c\)

Ketika b dan c koprima, diketahui:

\(\displaystyle b^{-1} \mod c = b^{c-2} \mod c \)

Ingat bahwa untuk modulo nilai hash, kita menggunakan bilangan prima. Jadi c selalu bilangan prima, yang mana selalu koprima dengan bilangan lainnya. Jadi operasi pembagian dengan B^x dapat dianggap sebagai operasi perkalian terhadap B^-x, yang setara dengan B^(c-2)x.

Jika Anda ingin tahu lebih lanjut tentang inverse modulo, kunjungi halaman berikut.

---

Tanpa Modulo

Seperti yang saya pernah ceritakan di teknik optimisasi konstanta, operasi modulo merupakan operasi yang sangat berat. Tidak jarang saya mendapat TLE padahal menurut perhitungan harusnya AC, dan penyebabnya adalah operasi modulo.

Terdapat sebuah trik yang biasa digunakan apabila nilai hash hanya dibutuhkan untuk memeriksa kesamaan string. Caranya adalah tidak perlu dimodulo. Nilai hash menjadi bisa overflow dan berantakan. Namun ingat bahwa seberantakan apapun nilai hash, ketika dua string identik, nilai hash keduanya selalu sama. Jadi dibiarkan saja overflow!!

Saya sudah pernah beberapa kali diselamatkan dengan teknik ini, terutama saat ICPC Jakarta selama beberapa tahun terakhir. Namun hati-hati, pembuat soal yang menyadari keberadaan teknik ini dapat membuat kasus uji untuk memunculkan collision dengan mudah. Jadi tetap waspada.

---

Tuple Hash

Sekalipun kita menggunakan modulo, tetap saja ada kemungkinan terjadinya collision. Untuk memperkecil peluang collision, biasanya orang membuat beberapa fungsi hash dengan variasi B dan modulo, kemudian nilai akhirnya adalah gabungan dari beberapa fungsi hash tersebut. Dengan cara ini, kalaupun salah satu fungsinya collision, masih ada fungsi lainnya yang menyelamatkan. Teknik ini secara efisien menurunkan peluang terjadinya collision.

Biasanya saya menggunakan 2 saja, dan sejauh ini aman-aman saja. Saya juga pernah menjumpai orang yang paranoid sampai membuat puluhan hash :')

---

Polymorphic Key

Kadang-kadang key yang diperlukan untuk hash bersifat polymorphic. Artinya, sebuah key bisa memiliki beberapa wujud. Contoh yang pernah saya hadapi:

• Rooted tree, yang mana struktur urutan child setiap node bisa bervariasi.
• String berotasi, yang artinya "abca" dianggap sama dengan "aabc" dan "caab"

Untuk kasus seperti ini, salah satu solusinya adalah dengan melakukan "normalisasi". Setiap wujud kita ubah menjadi sebuah wujud, sedemikian sehingga seluruh variasi yang sebenarnya sama memiliki wujud yang sama.

Contohnya, untuk kasus rooted tree, kita mulai dengan menjadikannya sebagai string. Ada cara pengkodean rooted tree menjadi string. Salah satunya adalah:

encode(T)
= '(' + encode(ch1) + encode(ch2) + ... + encode(chnChild) + ')', jika T bukan leaf
= '', jika T adalah leaf

Berikut contoh pengkodeannya:

Kemudian tinggal bagaimana kita membuat representasi "normal" dari sebuah tree. Perhatikan bahwa pengkodean ini bekerja secara rekursif. Ketika berada di suatu node, kita memiliki informasi pengkodean untuk setiap anak-anaknya, lalu hendak digabungkan menjadi satu. Sebagai contoh, misalkan anak-anak dari suatu node dikodekan menjadi:

1. (()())
2. (())
3. ((()())())

Apakah urutannya mau 1, 2, 3? Atau 3, 1, 2?
Cara yang saya sukai adalah dengan mengurutkannya secara leksikografis. Jadi urutan yang digunakan adalah 3, 1, 2. Dengan demikian, subtree pada node tersebut dikodekan menjadi
( + ((()())()) + (()()) + (()) + ) = (((()())())(()())(())).

Lakukan hal ini untuk seluruh bagian tree secara rekursif. Dengan strategi ini, dijamin wujud seperti apapun dari suatu rooted tree akan selalu berakhir dengan representasi string yang sama.

Setelah menjadi string, barulah rooted tree itu di-hash.
Bagi yang ingin mencoba, silakan kerjakan UVa 12489 - Combating cancer.

Cara normalisasi belum tentu semudah itu. Kadang-kadang, usaha melakukan normalisasi membutuhkan kompleksitas yang tinggi. Misalnya untuk kasus string berotasi. Salah satu ide normalisasi yang muncul adalah mencari rotasi yang leksikografis terkecil, baru di-hash. Namun mencari minimum lexicographic rotation secara naif membutuhkan waktu O(N²), dengan N adalah panjang string. Solusi yang lebih cepat adalah menggunakan suffix array untuk mencari minimum lexicographic rotation dalam O(N log N). Namun mendengar suffix array saja saya sudah tidak nafsu coding.

Ada sebuah trik yang dapat digunakan, yaitu mencoba seluruh kemungkinan bentuk string, di-hash, lalu nilai hash untuk string tersebut adalah nilai hash minimumnya. Untuk string S, terdapat |S| kemungkinan wujudnya. Untuk mencari semua kemungkinan nilai hash wujud-wujudnya, cukup gunakan rolling hash untuk string SS (digandakan), dengan panjang substring k=|S|.

Contoh, S = "abca". Maka SS = "abcaabca". Semua substring dari SS dengan panjang 4 karakter merupakan seluruh kemungkinan wujud rotasi dari S. Dengan rolling hash, pencarian dapat dilakukan dalam O(N)!

Perhatikan pula untuk kasus rooted tree, ketimbang membandingkan string untuk pengurutan, Anda dapat mencari nilai hash untuk tiap-tiap anak, urutkan, gabung, lalu hash. Kompleksitas mencari nilai hash dari suatu rooted tree menjadi lebih cepat tanpa pengurutan string.

---

Lazy Initialization

Suatu ketika, saya mengerjakan soal dengan strategi open hashing. Saya membuat "array of vector" untuk tabel hash dengan ukuran 989999 (prima < 10⁶). Karena soalnya multiple case, tabel ini harus dikosongkan untuk kasus uji yang baru. Sedihnya, banyaknya kasus uji bisa sampai puluhan ribu (walaupun masing-masing kasusnya kecil). Melakukan loop pada tabel untuk mengosongkan vektor satu per satu cukup lambat dan berisiko TLE.

Strategi yang kemudian saya gunakan adalah dengan menyimpan nomor kasus uji untuk setiap elemen pada vektor tabel open hashing. Misalkan saat ini program sedang mengerjakan kasus uji nomor T. Ketika dilakukan operasi read, periksa nomor kasus uji pada elemen yang ditemukan. Jika nomor ini kurang dari T, artinya dijamin elemen ini berikut elemen-elemen di belakangnya sudah kadaluarsa dan lakukan clear pada vector ini. Lakukan hal serupa untuk operasi update dan jangan lupa mencantumkan nomor kasus uji saat ini.

Intinya adalah nomor kasus uji menjadi penentu apakah data yang disimpan ini masih relevan atau tidak. Sekedar info, teknik ini juga bisa digunakan untuk tabel DP yang ukurannya sangat besar dan melakukan memset/fillchar mengakibatkan TLE.

---

---

Penutup

Mungkin masih ada teknik lainnya, tetapi semua yang saya ketahui sudah dituliskan di sini. Semoga berguna untuk kalian, terutama ketika menghadapi soal dan secara tak terduga dapat diselesaikan dengan hashing ;)