Sejak masa awal kelahiran kepustakawanan, indeks (index) dan pengindeksan (indexing, pembuatan indeks) selalu merupakan hal penting, sebab efisiensi penyimpanan buku dan dokumen hanya dapat dicapai jika ada cara paling singkat untuk menemukan kembali buku atau dokumen tersebut
ketika diperlukan. Selama masa yang amat lama, pembuatan indeks adalah monopoli manusia, dan dilakukan oleh profesi khusus, baik yang bernama pustakawan, dokumentalis, maupun arsiparis. Ketika terjadi “ledakan informasi” dan kecepatan pertumbuhan dokumen semakin tak terkendali, maka sulit sekali mengandalkan tenaga manusia untuk melakukan pengindeksan. Upaya menyerahkan pekerjaan ini ke mesin komputer pun menjadi semakin sering dilakukan dan melahirkan kajian teori maupun aplikasi yang akhirnya secara umum dikelompokkan sebagai bidang information retrieval.

Sebuah indeks secara sederhana adalah sebuah daftar berisi penunjuk (pointers). Lebih tepatnya lagi, indeks adalah sebuah daftar yang sistematis, mengandung istilah atau frasa (menyatakan pengarang, judul, konsep, dan sebagainya) yang dilengkapi dengan penunjuk ke isi satu atau serangkaian dokumen, ke lokasi istilah atau frasa itu dapat ditemukan. Indeks dan pengindeksan biasanya dikaitkan dengan pembuatan katalog dan klasifikasi. Namun, berbeda dari katalogisasi dan klasifikasi yang lebih berkonsentrasi pada “tentang apa”-nya dokumen (aboutness), maka pengindeksan lebih terkonsentasi pada ekstraksi atau pengambilan kata atau istilah yang ada di dalam dokumen di halaman tertentu, lalu menempatkannya dalam daftar indeks secara terstruktur. Struktur inilah yang memungkinkan sebuah buku “merujuk” pembacanya ke bagian-bagian dari teks yang relevan untuk keperluannya.

Jika kita membaca sebuah buku non-fiksi, terutama buku-buku ilmu pengetahuan yang ditulis secara serius, maka pada bagian belakang kita dapat menemukan daftar kata, istilah atau frasa diurut menurut abjad. Setiap kata, istilah atau frasa ini berisi informasi tentang nomor halaman. Jika seseorang ingin tahu di mana sebuah istilah muncul dalam pembahasan buku tersebut, maka orang itu tinggal melihat nomor halaman di sebelah istilah yang bersangkutan. Inilah yang kita namakan indeks, dan tugasnya juga amat sederhana: menunjukkan halaman di mana istilah itu dapat ditemukan. Kesederhanaan indeks di setiap buku menyebabkan buku itu ‘mudah digunakan’. Semakin sederhana, semakin memudahkan pembaca.

Pada jaman buku dan bahan tercetak non-elektronik, kegiatan pembuatan indeks dilakukan oleh manusia tanpa bantuan alat-alat otomatis (mesin ketik dianggap bukan alat otomatis). Ketika dokumen terbuat dari teks digital, maka muncul kemungkinan untuk membuat indeks yang serupa dengan cara ‘tradisional’ pertama di atas (membuat indeks dari isi dokumen) tetapi dengan bantuan mesin. Manusia tinggal memerintahkan komputer mengambil istilah dari tempat-tempat tertentu dalam sebuah dokumen. Perintah ini hanya dilakukan sekali, tetapi lalu dikerjakan secara konsisten oleh komputer berkali-kali, maka ini disebut otomatisasi. Lebih jauh lagi, muncul juga kemungkinan untuk menjadikan semua isi dokumen sebagai wakilnya, sehingga disebut full-text.

Ketika komputer digunakan untuk pembuatan indeks, maka terjadi sebuah revolusi kecil-kecilan. Sewaktu belum ada komputer, pengindeksan mutlak urusan manusia. Mesin tidak ikut campur. Ketika komputer hadir, pengindeksan dapat dilakukan dengan dua cara: intelektual atau mekanikal. Kegiatan menganalisis dan penerjemahan (translasi) dokumen yang akan diindeks merupakan kegiatan intelektual karena mencakup kegiatan mengidentifikasi dan memilih konsep-konsep penting yang tercakup dalam sebuah dokumen, sementara fase translasi sesungguhnya merupakan pekerjaan menjadikan konsep-konsep yang sudah dipilih itu menjadi indeks berdasarkan sebuah cara yang sudah ditetapkan sebelumnya.

Kegiatan mekanikal merupakan kegiatan yang mencakup pengurutan menurut abjad dan pembuatan format entri indeks. Kalau komputer digunakan baik untuk kegiatan intelektual maupun mekanikal, maka itu artinya automatic indexing (pengindeksan secara otomatis). Kalau komputer hanya digunakan untuk mekanikal sementara manusia untuk yang intelektual, maka namanya automated indexing (pengindeksan yang diotomatiskan). Automatic indexing biasanya bergantung kepada berbagai algoritma yang antara lain paling populer adalah keyword frequencies, yaitu cara mengindeks berdasarkan kata-kata yang paling banyak muncul dalam satu dokumen.

Penggunaan komputer dalam pengindeksan kini telah menjadi bagian yang tak terpisahkan dari semua sistem information retrieval. Di dalam sistem ini ada dua berkas (file) besar; yang pertama untuk tempat semua dokumen digital, dan yang kedua berisi indeks untuk dokumen itu. Berkas kedua ini bisa kita anggap halaman belakang sebuah buku. Seperti halnya buku tercetak, maka ‘halaman digital’ ini juga berisi istilah-istilah yang datang dari dokumen yang tersimpan di berkas pertama. Istilah-istilah ini diambil sesuai dengan teknik pengindeksan. Untuk setiap istilah, terdapat rujukan ke lokasi di mana istilah itu terdapat di dokumennya. Kumpulan istilah indeks inilah yang di dalam bidang komputer disebut sebagai inverted file (diterjemahkan secara bebas menjadi ‘berkas sungsang’). Sebagian besar sistem IR saat ini mengandalkan prinsip sederhana yang ditiru dari teknologi cetak ini. Namun di balik kesederhanaan prinsip ini, terdapat kerumitan kegiatan komputasi yang muncul karena pada dasarnya komputer hanya dapat bekerja sesuai program. Sampai saat ini, program komputer tetap tidak dapat menggantikan seluruh proses pikir otak manusia.

Ketika seorang pencari informasi memulai langkah pencariannya dengan memasukkan beberapa istilah sebagai sebuah pertanyaan atau permintaan informasi (query), maka komputer mencari padanan istilah yang diminta ini di berkas sungsang. Kalau berkas itu mengandung istilah yang dicari, maka komputer akan menggunakan rujukan lokasi yang terdapat bersama istilah itu untuk menuju ke dokumennya. Kalau suatu istilah merujuk ke lebih dari satu dokumen, maka komputer akan ‘menemukan’ atau ‘menembak’ (hits) semua dokumen-dokumen yang ada. Dengan cara ini, maka sebenarnya komputer menemukan dokumen yang dicari secara tidak langsung, atau disebut juga indirect file access.

Teknologi komputer memungkinkan manusia menambahkan berbagai informasi, selain lokasi dokumen, untuk menyertai setiap istilah indeks. Kalau indeks sebuah buku hanya bisa mengandung nomor halaman yang dirujuk, maka berkas-sungsang dapat berisi informasi tentang field (ruas) di mana sebuah istilah dapat ditemukan, frekuensi keberadaan istilah itu di dalam keseluruhan koleksi dokumen, jarak (proximity) antara satu istilah dengan istilah lainnya, dan sebagainya. Tentu saja, semakin banyak informasi yang terkandung di dalam sebuah berkas-sungsang maka semakin besarlah ruang yang diperlukan untuk menampungnya. Semakin besar berkas-sungsang, semakin lama pula proses yang diperlukan komputer untuk menemukan sebuah istilah. Dalam kondisi ini, maka kenyamanan pemakai akan bergantung sekali kepada kemajuan dalam teknologi perangkat keras, terutama yang berkaitan dengan kecepatan pemrosesan (processor), daya tampung memori, dan transfer data.

Untuk memahami persoalan pengindeksan berbantuan komputer ini, kita juga perlu mengetahui proses pencarian atau pencocokan istilah yang dilakukan komputer di berkas-sungsang. Cara paling sederhana bagi komputer untuk menemukan sebuah istilah adalah dengan cara berurutan (sequential). Anggaplah istilah-istilah pengindeksan itu sebagai sebuah daftar panjang yang diurut menurut abjad. Program komputer akan ‘berjalan’ mengecek setiap istilah, mulai dari istilah pertama di awal daftar, sampai istilah terakhir yang ada di berkas-sungsang. Jika permintaan informasinya mengandung berbagai istilah (misalnya dua istilah ‘Indonesia’ AND ‘korupsi’), maka program akan mencari satu persatu dan memeriksa dokumen yang dirujuk kedua istilah itu bersama-sama. Semakin panjang daftarnya, semakin lama proses pencariannya. Semakin rumit permintaan informasinya, semakin lama lagi proses pencariannya.

Kelemahan cara penelusuran secara berurutan ini kemudian diperbaiki dengan berbagai cara yang akan dijelaskan secara ringkas berikut ini.

Alphabetical chain

Cara pertama mengatasi problem pencarian sequential adalah dengan pencarian yang memakai prinsip alphabetical chain, atau matarantai-alfabet. Prinsipnya sama dengan cara kita menggunakan kamus. Misalnya, kalau kita ingin mencari arti kata programming di kamus Inggris-Indonesia, tentu kita tidak akan secara bodoh mencari mulai dari alfabet A, bukan? Kita langsung ‘melompat’ ke huruf P dan bahkan juga langsung menuju kata-kata yang dimulai dengan ‘prog’ dan melewatkan semua kata-kata sebelumnya. Cara pencarian ini lumayan lebih cepat daripada cara sebelumnya, tetapi tetap menyisakan masalah. Jika daftar indeks memiliki banyak kata yang serupa (misalnya programme, programmable, programming), maka terjadilah apa yang disebut densely populated area (wilayah dalam daftar indeks yang padat berisi istilah serupa). Jika komputer harus mencari di wilayah ini, maka programnya juga harus dibuat agar bisa bolak-balik di wilayah ini sampai semua kemungkinan telah dicoba. Artinya, proses pencarian juga bisa sama lambatnya dengan proses yang sequential.

Binary search

Untuk mempercepat pencarian di daftar indeks, komputer perlu mengurangi langkah penelusuran. Salah satu cara yang dipakai untuk mengurangi langkah itu adalah dengan binary search yang membagi dua daftar setiap kali melakukan pencarian (itu sebabnya disebut binary yang artinya kira-kira adalah ‘belah dua’ atau ‘bagi dua’). Jika dalam proses sequential komputer menelusur dari awal sampai akhir dan dalam proses alphabetical chain komputer menelusur mulai dari kata yang alfabetnya dipakai di awal, maka binary search langsung membagi dua seluruh daftar dan mencari di setengah daftar. Proses pembagian ini dapat dilakukan berkali-kali.

Untuk jelasnya, mari kita lihat contoh sederhana, jika sebuah indeks berisi 10 istilah (tentu saja, ini jumlah yang sangat kecil, karena hanya sebagai contoh) sebagai berikut:

Communication computation computational computer data dictionary information informetrics network software

Perhatikanlah bahwa daftar indeks di atas sudah diurut menurut abjad. Masing-masing istilah berada di sebelah istilah lainnya berdasarkan posisi alfabet. Misalnya, ada orang yang ingin mencari dokumen tentang ‘network’. Dalam sistem yang memakai binary search maka komputer langsung membagi dua daftar di atas, dan melakukan penghitungan matematis untuk memperkirakan di mana letak istilah ‘network’ berada. Ketika daftar di atas dibagi dua, maka istilah yang terletak di tengah adalah ‘data’ (posisi nomor 5 di dalam daftar yang berisi 10 kata). Komputer langsung melakukan penghitungan matematis dan ‘berpikir’: di mana kah kata ‘network’, sebelum atau setelah kata ‘data’?

Dari segi alfabet, jelas bahwa ‘network’ berada setelah ‘data’. Itu sebabnya, komputer lalu mengabaikan empat kata sebelum ‘data’, dan daftar yang harus ditelusurnya kini jadi lebih pendek, yaitu:

dictionary information informetrics network software

Setelah membelah daftar menjadi dua, dan membuang setengah bagian yang tidak diperlukan, komputer melakukan lagi langkah yang sama, yaitu membagi dua daftar yang kini hanya berisi 5 istilah di atas. Di dapatlah kata ‘informetrics’ sebagai kata yang ada di posisi tengah. Komputer lalu ‘berpikir’ lagi: di mana kah kata ‘network’, sebelum atau setelah kata ‘informetrics’? Dari segi alfabetis, sekali lagi jelas bahwa ‘network’ berada setelah ‘informetrics’. Maka komputer membuang lagi setengah dari daftar yang sedang diperiksanya, sehingga sekarang tinggal dua kata:

network software

Nah, kini daftarnya menjadi sangat pendek, dan komputer dengan cepat dapat menemukan kata ‘network’.

Binary search tree

Salah satu problem utama dari cara pencarian binary di atas adalah pada keharusan pembuatan program yang dapat melakukan penghitungan matematis untuk menentukan titik-tengah dari sebuah daftar. Penghitungan ini dilakukan setiap kali komputer diperintahkan oleh pemakai untuk mencari sebuah istilah di dalam daftar indeks. Tentu saja, dari segi pemrograman dan pemrosesan komputer, kegiatan penghitungan ini akan sangat dipengaruhi oleh kompleksitas pertanyaan, ukuran indeks, dan kecepatan perangkat keras. Semakin rumit pertanyaannya, dan semakin besar jumlah indeks yang terkandung dalam sebuah berkas-sungsang, maka semakin banyaklah kegiatan penghitungan yang harus dilakukan. Artinya, semakin lambatlah proses kerja komputernya.

Untuk menambah kecepatan pencarian, maka diciptakan cara yang meniru tabiat sebuah pohon (maka disebutlah cara ini binary search tree). Sebuah pohon memiliki cabang, dan setiap cabang bercabang lagi, demikian seterusnya sampai ke puncak pohon. Dengan perhitungan matematis, maka dapatlah dibuat sebuah berkas-sungsang yang setiap istilah indeksnya mengandung nilai, sedemikian rupa sehingga selalu ada dua cabang untuk setiap istilah. Pencabangan menjadi dua ini sebenarnya sama dengan membagi dua berkas seperti di cara binary search, tetapi kali ini komputer tidak perlu melakukan pembagian dan penghitungan titik-tengah setiap kali melakukan pencarian. Komputer cukup memulai pencarian di awal indeks, yang dalam hal ini dianggap sebagai pangkal sebuah pohon, lalu tinggal mengikuti percabangan ‘pohon’ itu sampai bertemu dengan istilah yang dicari. Artinya, program komputer tidak dibuat untuk melakukan penghitungan berkali-kali, melainkan cukup sekali saja. Waktu yang dihemat dan efisiensi yang dapat dicapai dengan cara ini menjadi lumayan banyak.

Balanced tree (B-tree)

Jika cara binary search tree mengandalkan metode pencabangan-dua (setiap istilah indeks mempunyai dua ‘anak’ istilah yang berdekatan), maka cara lain lagi yang dianggap lebih mempercepat proses pencarian adalah balanced tree alias B-tree. Dengan cara ini, setiap istilah indeks diberi nilai sedemikian rupa sehingga cabangnya tidak hanya dua, tetapi bisa berapa saja. Hal ini memengaruhi tidak saja kecepatan pencarian, tetapi juga pengorganisasian berkas-sungsang secara keseluruhan. Di semua cara pengindeksan yang diuraikan di atas, maka setiap kali ada penambahan istilah (karena jumlah dokumen bertambah, dan istilah baru selalu muncul) komputer yang menggerakkan sistem IR selalu harus melakukan reorganisasi berkas-sungsang. Kadang-kadang proses reorganisasi atau pembaruan (updating) ini memakan banyak waktu sebab susunan bekas-sungsang itu sendiri tidak memungkinkan penambahan secara cepat. Dalam berkas-sungsang yang sequential maupun alphabetical-chain, penambahan istilah indeks seringkali berarti mengulang kembali seluruh proses pembuatan daftar indeks. Jika daftar indeks itu mengandung 1 juta istilah, maka proses penambahan ini pasti akan sangat memakan sumberdaya komputasi, dan akhirnya menghambat kinerja sistem secara keseluruhan.

Pengindeksan yang menggunakan cara b-tree memungkinkan proses reorganisasi secara lebih cepat dan efisien, karena setiap penambahan istilah baru tidak perlu mengganggu susunan yang sudah ada, dan karena setiap istilah indeks boleh punya cabang sebanyak mungkin. Logikanya, komputer tidak perlu menyusun kembali sebuah berkas-sungsang setiap kali ada istilah baru masuk. Cukup dengan memberikan nilai baru kepada istilah yang baru masuk, lalu menempatkannya pada posisi yang berkaitan dengan istilah lain sesuai dengan dekat-jauhnya nilai istilah-istilah tersebut. Dalam sistem yang memakai b-tree, maka setiap penambahan istilah baru hanya membutuhkan pergeseran-pergeseran posisi indeks di dalam berkas-sungsang, tidak memerlukan penulisan-ulang atau penyusunan-ulang.

TRIES

TRIES diambil dari kata ‘retrieval’ dan diperkenalkan sebagai sebuah model struktur data di tahun 1960an. Pada dasarnya, tries adalah sebuah cara untuk mengelola istilah pengindeksan, bukan cara menelusur. Namun, cara pengelolaan ini tentu saja memengaruhi kinerja penelusuran berkas-sungsang dalam sebuah sistem IR. Secara ringkas dapat dikatakan, tries merupakan cara menyimpan daftar indeks sebagai serangkaian karakter/huruf dan cara merujukkan istilah ke lokasi di memori komputer. Sama dengan binary search tree dan B-tree, sistem yang menggunakan tries juga mengandalkan metode pencabangan. Dalam prakteknya, sistem yang menggunakan tries memerlukan daya tampung yang amat besar, karena setiap istilah dan cabang-cabangnya memerlukan lokasi khusus di memori komputer. Semakin besar jumlah istilah dan semakin rumit percabangannya, maka semakin besar pula dibutuhkan daya tampung memori. Lalu, sebagaimana semua cara pengindeksan yang sudah diuraikan di atas, ukuran besar sebuah berkas-sungsang sangat memengaruhi proses penambahan atau pembaruan .

Di antara cara-cara yang sudah diuraikan secara ringkas di atas, maka yang paling populer dan dianggap paling efisien untuk kondisi perangkat keras komputer saat ini adalah cara B-tree. Pengembangan terus dilakukan, terutama dalam upaya mempercepat proses pembaruan berkas agar sebuah sistem dapat terus mengikuti pertumbuhan jumlah informasi digital yang luar biasa pesat.

Selain dengan sistem yang memakai berkas-sungsang dan pencarian-tidak-langsung (indirect access), para ilmuwan juga terus mengembangkan berbagai teknik baru, misalnya yang mengabaikan fungsi berkas-sungsang agar dapat melakukan pencarian langsung ke dokumen koleksi. Namun pengertian ‘langsung’ di sini juga tidak berarti komputer mencari satu-per-satu dokumen dari awal koleksi sampai akhir koleksi. Ini terlalu muskil dilakukan secara efisien jika jumlah koleksinya mencapai jutaan. Melainkan, saat ini terus dilakukan percobaan dengan memanfaatkan prinsip pencarian berdasarkan pola (pattern matching). Dengan cara ini, maka komputer tidak menelusur daftar indeks, melainkan membuat sebuah pola berdasarkan istilah-istilah yang dimasukkan oleh pemakai ketika pemakai memulai pencariannya. Lalu, pola inilah yang langsung dipakai oleh komputer untuk memayar (scanning) koleksi untuk menemukan dokumen yang mengandung pola istilah yang sama.

Teknik lain yang sedang terus dikembangkan adalah hashing yaitu sebuah teknik yang memanfaatkan lokasi (atau alamat, address) di dalam memori komputer untuk menemukan sebuah dokumen di dalam koleksi (harvesting). Dengan teknik ini, sebuah program komputer melakukan konversi karakter yang ada di sebuah teks menjadi tabel nilai yang membentuk apa yang disebut bit patterns. Untuk setiap huruf yang ada dalam daftar alfabet, komputer dapat mengenakan nilai. Gabungan dari huruf adalah kata, dan dengan demikian dapat dihitung menjadi nilai pula. Selanjutnya gabungan dari kata adalah kalimat, sehingga juga dapat diberi nilai. Dengan teknik transformasi numerik ini, maka keseluruhan sistem IR dapat dibuat lebih sederhana dan proses komputasi dapat lebih cepat.

Komputer kemudian juga dapat melakukan dua hal yang pada dasarnya dilakukan juga sebelum ada komputer, yaitu derivative indexing dan assignment indexing, dengan penjelasan ringkas sebagai berikut:
• Derivative indexing – istilah untuk indeks diambil langsung dari teks dokumen, disebut juga synonym for keyword indexing karena indeks diambil langsung dari kata kunci dan tidak ada daftar kosakata sebagai acuannya (atau di kalangan teknisi biasa disebut ‘tidak ada controlled vocabulary-nya’). Pengindeksan tanpa controlled vocabulary ini disebut juga free indexing.
• Assignment indexing – istilah untuk indeks diberikan dari luar. Kalau istilah ini datang dari controlled vocabulary disebut descriptor, walaupun controlled vocabulary-nya bukan thesaurus. Kalau istilah datang dari luar controlled vocabulary (mungkin istilahnya baru muncul) maka disebut identifier.
Semua yang dijelaskan di atas terjadi pada lingkungan digital yang berbentuk teks atau tulisan. Dalam lingkungan yang berbentuk lain, misalnya gambar atau audio, maka prinsip-prinsipnya mungkin sama, yaitu bahwa ada suatu mekanisme pengindeksan, namun persoalannya menjadi lebih rumit karena gambar atau suara memiliki karakteristik yang lebih kaya daripada teks. Dari segi persepsi manusia, sebuah teks memiliki sifat yang sederhana karena bisa dengan mudah dikenali batas-batasnya. Kata dan kalimat sudah jelas batas-batasnya. Gambar dan suara mengandung banyak batas (nada, intonasi, warna, sudut pandang, ritme, gradasi). Eksperimen dalam pengindeksan gambar dan musik masih terus berlangsung (lihat juga pembahasan tentang image retrieval)

Sementara itu, pengindeksan teks juga menghadapi tantangan baru, yaitu lingkungan hypertext dengan ciri khasnya, yaitu teks saling berkaitan dan saling merujuk sehingga membentuk struktur beragam (hyperstructured). Ini sekarang jadi fenomena biasa dalam bentuk milyaran halaman di Internet yang berisi teks yang saling merujuk satu sama lainnya. Untuk jenis teks dari Internet ini, sebenarnya setiap link atau hyperlink adalah sebuah indeks, sebab indeks pada dasarnya adalah sesuatu yang merujuk ke sesuatu yang lain, agar sesuatu yang lain itu bisa ‘ditemukan’. Di dunia Internet, indeks seperti ini mengandung dua hal sekaligus: istilah yang digunakan sebagai indeks, dan mekanisme penemuan lokasi teks yang dirujuknya (locator mehcanism). Berdasarkan hal ini, maka muncul ciri-ciri spesifik dari halaman-halaman di Internet, yaitu:

  • Indeks ‘tertanam di dalam”, atau menjadi bagian langsung dari, dokumen.
  • Indeks dan locators bersatu menjadi satu unit, bukan sendiri-sendiri.
  • Hirarki subjek yang biasanya tercipta dalam pengindeksan tradisional (misalnya jika sebuah entri memiliki sub-entri) tidak akan terjadi di hyperlink, karena tidak ada link yang menjadi ‘bawahan’ atau ‘atasan’ dari link lainnya.
  • Hanya link yang merujuk ke isi dokumen (content-based links) di dalam sebuah hyperstructure yang dapat dianggap sebagai indeks, sementara link navigasi (seperti “next page” atau “kembali ke halaman muka“ atau “top of document”) bukan tergolong indeks.
  • Penulis dokumen menjadi pengindeks ketika mereka menentukan link, sehingga bisa saja penulis menetapkan “click here” sebagai indeks dan link, padahal kalau orang yang lain harus mengindeks, maka mungkin digunakan istilah lain.
  • Lebih sedikit ada kemungkinan “salah istilah” karena yang menulis indeks adalah penulisnya, bukan pengindeks luar.