BAB I
PENDAHULUAN
A. Latar Belakang
Konsep dasar sistem temu balik informasi (STBI) adalah proses untuk
mengidentifikasi kecocokan (match) di antara permintaan (query) dengan representasi atau
indeks dokumen, kemudian mengambil (retrieve) dokumen dari suatu simpanan (file)
sebagai jawaban atas pemintaan tersebut. STBI pada prinsipnya bekerja berdasarkan ukuran
antara stilah query dengan istilah yang menjadi representasi dokumen.
Pengertian lain menyatakan bahwa STBI adalah proses yang berhubungan dengan
representasi, penyimpanan, pencarian, dan pemanggilan informasi yang relevan dengan
kebutuhan informasi yang diinginkan pengguna (Ingweson, 1992: 49). Pendapat ini
menunjukkan bahwa pada STBI terkandung sejumlah kegiatan yang meliputi proses
penyimpanan, penyediaan representasi, identifikasi, serta pencarian atau penelusuran
dokumen yang relevan pada suatu database, dalam rangka memenuhi kebutuhan informasi
dari pengguna. Tague-Sutcliffe (1996: 1) mengemukakan bahwa STBI adalah suatu proses
yang dilakukan untuk menemukan dokumen yang dapat memberikan kepuasan bagi
pengguna dalam memenuhi kebutuhan informasinya. Tujuan utama STBI adalah untuk
menemukan dokumen yang sesuai dengan kebutuhan informasi pengguna secara efektif dan
efisien, sehingga dapat memberikan kepuasan bagi pengguna. Dengan demikian sasaran akhir
dari STBI adalah kepuasan pemakai.
Secara teknis, tujuan STBI adalah mencocokkan (matching) term atau istilah yang
dibangun (query) dengan term atau indeks yang ada dalam dokumen, sehingga dengan
kecocokan tersebut maka dokumen-dokumen yang relevan akan terambil (retrived) dari
database. Dokumen relevan yang terambil tersebut itulah tujuan dari STBI. Smeaton (1990)
memformulasikan tujuan dari STBI ialah, terambilnya dokumen berdasarkan permintaan
pengguna dengan harapan bahwa content atau isi dari dokumen yang terambil tersebut
relevan dengan kebutuhan informasi pencari informasi.
B. Rumusan Masalah
1. Bagaimana Proses pencocokan pemanggilan sebuah dokumen?
2. Apa peran Inverted file didalam pemanggilan dokumen?
1
BAB II
PEMBAHASAN
A. Pencocokan Dokumen
Pencocokan (matching) adalah proses membandingkan antara istilah yang tercantum
dalam pertanyaan pemakai (query) dengan istilah yang tercantum dalam dokumen (Meadow,
1973:131). Pencocokan istilah (query) yang dimasukkan oleh pengguna dengan indeks
dokumen yang tersimpan dalam database dilakukan oleh mesin komputer. Komputer yang
melakukan proses pencocokan itu dalam waktu yang sangat singkat sesuai dengan kecepatan
memory dan processing yang dimiliki oleh komputer itu.
Pencocokan dokumen dihitung antara permintaan dengan setiap dokumen yang berbasis
algoritma pada sistem. Algoritma didasarkan pada kehadiran query term (s), term frequency,
tf/idf, pemenuhan logika boolean, atau bobot query. Setelah menghitung kesamaan setiap
dokumen dalam subset dari dokumen, sistem menyajikan daftar hasil pencarian kepada
pengguna. kecanggihan dari pencarian dokumen tergantung pada bagaimana sebuah sistem
memiliki kekayaan dokumen dan mekanisme pembobotan query.1
Untuk mencocokkan pertanyaan pemakai dengan dokumen, sekurang-kurangnya ada
dua macam fungsi pencocokan (matching-function) yaitu fungsi exact match dan fungsi
patrial match (Hasibuan, 1997: 2). :
1. Fungsi exact match adalah pencocokan di mana representasi suatu pertanyaan
persis sama atau harus sesuai dengan representasi dokumen, agar dokumen
tersebut dapat terambil (retrieved).
2. Sedangkan fungsi patrial match atau pencocokan sebagian yaitu representasi
pertanyaan hanya sebagian saja yang sama dengan representasi dokumen.
Pencocokan sebagian ini dikenal dengan pemenggalan (truncation).
Pencocokan membutuhkan representasi dokumen. Umumnya STBI didasarkan pada
representasi dokumen, karena representasi tersebut jauh lebih pendek atau lebih ringkas dari
dokumen aslinya. Representasi dapat berupa abstrak dan istilah indeks (Rowley, 1990: 6).
Abstrak adalah representasi dokumen yang jelas dan ringkas dengan mengikuti pola dan
penyusunan seperti aslinya. Sedangkan indeks adalah representasi dokumen yang bertujuan
1
Bab II,di unduh di [Link] hal. 32-33 tanggal 15 oktober 2017 pukul 16.00 WIB.
2
untuk menemukan kembali dokumen-dokumen yang telah disimpan dan diorganisir melalui
proses.2
B. Inverted file
Inverted file atau inverted index adalah mekanisme untuk pengindeksan kata dari
koleksi teks yang digunakan untuk mempercepat proses pencarian. Struktur inverted file
terdiri dari dua elemen, yaitu: kata (vocabulary) dan kemunculan (occurences). Kata-kata
tersebut adalah himpunan dari kata-kata yang ada pada teks, atau merupakan ekstraksi dari
kumpulan teks yang ada. Dan tiap kata terdapat juga informasi mengenai semua posisi
kemunculannya secara rinci. Jumlah dari posisi-posisi inilah yang dimaksudkan dengan nilai
kemunculan atau occurences. Posisi dapat merefer kepada posisi kata ataupun karakter. Hal
ini dapat dilihat dengan jelas dengan memperhatikan gambar 3.
Pada gambar 3 kata-kata dikonversikan menjadi karakter huruf kecil (lower-case).
Kolom vocabulary adalah kata-kata yang telah diekstraksi dari dari koleksi teks, sedangkan
occurences adalah posisi kemunculan pada teks. Struktur inverted file seperti ini masih secara
sangat sederhana sehingga berikutnya muncul beberapa masalah. Nilai kemunculan dari kata-
kata memerlukan ruangan (space) yang tidak sedikit, karena tiap kata muncul pada teks sekali
pada struktur occurences, sehingga ada ruangan ekstra atau dilambangkan dengan O(n).
Walaupun tidak semua kata diindekskan karena ada kata-kata stopword yang dibuang,
overhead yang muncul akibat penambahan indeks ini sampai mencapai 30% sampai dengan
40% dari ukuran besar koleksi teks. Sehingga untuk mengurangi kebutuhan ruangan yang
besar tersebut, maka digunakanlah teknik yang disebut block addressing. Teknik
2
Hasugian,[Link] informasi ilmiah secara online. Medan: jurnal studi perpustakaan dan
informasi, vol 2, juni 2006.(di unduh [Link] tanggal 11 oktober 2017, pukul 12.00 WIB) hal 3-
4.
3
pengindeksan ini sama seperti teknik klasik sebelumnya yang disebut full inverted indices,
karena tetap sama elemennya yaitu vocabulary dan occurences. Namun perbedaan yang ada
dan membuat teknik ini lebih unggul adalah pada pengalamatanya yang tidak satu-satu pada
tiap kata seperti yang dilakukan oleh teknik yang klasik, namun pengalamatannya
berdasarkan blok-blok tertentu yang sudah didefiniskan. Hal ini akan lebih jelas dengan
memperhatikan gambar 4.
Dengan teknik ini kebutuhan ruangan untuk membuat tambahan pengindeksan akan
lebih berkurang, karena dapat dipastikan bahwa jumlah blok akan lebih sedikit dibandingkan
dengan jumlah keseluruhan kata. Secara eksperimental hanya diperlukan 5% dari koleksi teks
untuk membuat tambahan pengindeksan dengan teknik ini. Sungguh efisien dalam
penggunaan ruangan atau space demand. Namun trade off yang terjadi adalah pada tiap kali
me-retriev kata maka yang akan di tunjuk adalah alamat blok kata tersebut. Sehingga harus
dilakukan literasi berikutnya pada blok tersebut untuk menemukan kata yang dimaksud. Tapi
trade off ini tidak perlu dikhawatirkan karena tidak begitu banyak berpengaruh terhadap
sistem karena hanya merupakan komputasi perbandinga sederhana jika dibandingkan efek
positif yang sangat baik karena mampu mengefisienkan ruangan yang dibutuhkan untuk
pengindeksan.3
1. Inverted index
Setiap istilah indeks dikaitkan dengan daftar inverted, yaitu :
a) Berisi daftar dokumen, atau daftar kata kejadian dalam dokumen, dan informasi
lainnya
3
Hikam,Ibnu. Penerapan Pohon Untuk Algoritma Pencarian Kata Pada Inverted File Dalam Sistem Temu Balik
Informasi (Di unduh di [Link] pada tanggal 12 Oktober pukul
17:08 WIB). hal, 3-4
4
b) Setiap entri disebut posting
c) Bagian dari postingan yang mengacu pada yang spesifik dokumen atau lokasi
disebut pointer
d) Setiap dokumen dalam koleksi tersebut diberi jumlah yang unik
e) Daftar dokumen biasanya dipesan atau dipanggil dengan nomor dokumen
(diurutkan menurut Nomor dokumen)4
C. Sistem Inverted File
Pencarian dilakukan dengan mencocokkan akar token dokumen yang tersimpan dalam
database. Jika Sesuai dengan kata kunci dari kata kunci yang dicari, maka seluruh dokumen
objek di dalam objek catatan dokumen token tersebut diambil untuk diproses dan ditampilkan,
penelitian ini tidak hanya menggunakan inverted file secara mekanisme, namun sebuah
sistem yang dirancang untuk mengatur file terbalik. Proses pengaturan disini termasuk apa
yang akan dilakukan saat melakukan insert inverted files, delete file terbalik, eksekusi kueri,
pengelola log, pengaturan, sumber informasi, dan pengindeksan. Sistem Inverted Files
System juga terbagi menjadi beberapapa kesesuai dengan proses yang dilakukan oleh
masing-masing paket. Hubungan antara masing-masing paket dijelaskan dalam use case
deskripsi Sistem Berkas Terbalik seperti pada gambar 5.
4
Cornell Education. Information Retrieval (diunduh di
[Link] pada tanggal
10 Oktober pukul 16:01 WIB). Hal, 3.
5
1. Hapus File Terbalik
a. Admin memilih dokumen yang akan dihilangkan.
b. Sistem menyimpan dokumen yang dipilih ke daftar file.
c. Admin mengaktifkan fungsi hapus
d. Sistem melakukan proses penguraian dokumen daftar yang akan dihapus ke token
koleksi
e. Sistem mencari posisi token yang terhapus dokumen dalam file terbalik
f. Sistem menghapus dokumen yang terkait ke token yang terkait dengan yang
terhapus dokumen dalam file terbalik
g. Sistem melakukan pembobotan ulang untuk setiap token
2. Setting
a. Admin menyiapkan file database yang ideal untuk mencocokkan aplikasi yang
dibuat
b. Admin menentukan IP Application Server.
c. Sistem membuat pengaturan untuk penampungan HTML dokumen yang akan
disimpan dalam database
d. Sistem mengonfigurasi lokasi folder penyimpanan dari file log Indeks
3. Pengindeksan
a. Indexer melakukan pengindeksan dengan mengolah hasil tahap pertama
pengindeksan dan perhitungan berat masing-masing token.
b. Indexer melakukan pemilahan database yang inverted file sesuai dengan berat
masing-masing inverted file
4. Memasukkan File Invert
a. Sistem melakukan penyisipan inverted file yang langsung dilakukan dengan
menyimpan dokumen di akhir daftar tertaut.
b. Sistem membaca setting ukuran yang inverted file dan metadata, berdasarkan
metadata ini, sistem menentukan nama file yang baru file database Selanjutnya,
inverted file akan dibuat oleh sistem pembaruan system metadata yang terkait
dengan autoexten dini proses.
6
c. Sistem menghitung ukuran inverted file itu ada di database Perhitungan ini sudah
selesai setiap kali sistem akan melakukan proses penyisipan untuk memastikan
kapasitas yang memadai dari database untuk menyimpan data.
d. Admin membuat database inverted file sebagai tempat untuk menampung
dokumen
5. Pelaksana Kueri
a. Sistem mengeksekusi query dengan melakukan query parsing tingkat rendah
b. Sistem melakukan pengambilan dokumen5
D. Penerapan Teori Pohon Pada Algoritma Pencarian
Algoritma pencarian pada inverted file terdiri dari tiga langakah umum, yaitu:
1. Vocabulary search, kata-kata yang ada pada query dicari pada vocabulary, dan
frase pun dipecah menjadi dua buah kata yang berbeda.
2. Retrieaval of occurrences, daftar kemunculan seluruh kata yang ditemukan di
retriev.
3. Manipulation of occurrences, nilai kemunculan diproses sebagai kombinasi
perhitungan similarity antara dokumen dengan query. Oleh karena itu, pencarian
pada inverted file selalu dimulai pada vocabulary. Maka membagi file ini menjadi
beberapa file yang terpisah merupakan ide yang baik, sehingga sebesar apapun
koleksi teks tersebut maka akan tetap tertampung atau dapat ditangani oleh
memori utama.
Suatu kata tunggal dapat dicari menggunaka beberapa macam struktur data yang sesuai
yang dapat mempercepat pencarian, seperti hashing, pohon, ataupun pohon binary. Dua yang
pertama dari struktur data tersebut memiliki biaya sebesar O(n), sedangkan untuk pohon
binary memiliki biaya sebesar O(log n).
5
Suhartono, Derwin. Electronic Document Management Using Inverted Files System (Di unduh di
[Link]
[Link]/articles/epjconf/abs/2014/05/epjconf_icas2013_00004/epjconf_icas2013_00004.html pada
tanggal 10 Oktober pukul 16:01 WIB). Hal, 3-4.
7
a. Pohon
Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit. Sekilas
mengenai pohon dapat secara jelas dipahami dengan memperhatikan gambar 5.
Karena definisi pohon tersebut diacu dari teori graf, maka sebuah pohon dapat
mempunyai sebuah simpul tanpa sebuah sisipun. Dengan kata lain, jika G = (V,E) merupakan
sebuah pohon, maka V tidak boleh berupa himpunan kosong, tetapi E boleh merupakan
himpunan kosong. Berdasarkan definisi tersebut, ada dua sifat penting pada pohon yaitu
terhubung dan tidak mengandung sirkuit. Terhubung artinya pada setiap pasang simpul pada
pohon terdapat lintasan yang menghubungkan. Tidak mengandung sirkuit berarti tidak
terdapat lebih dari satu lintasan yang menghubungkan setiap pasang simpul pada pohon.
Selain itu, dapat terlihat bahwa di dalam pohon, jumlah sisinya adalah jumlah simpul
dikurangi satu. Terlihat pula bahwa pohon hanya memerlukan dua buah warna untuk
mewarnai simpul-simpul di dalam pohon sedemikian rupa sehingga tidak ada dua buah
simpul bertetangga yang mempunyai warna sama. Dengan kata lain, ditinjau dari teori
pewarnaan graf, maka pohon mempunyai bilangan kromatik sama dengan 2.
b. Pohon Berakar
Pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah
sehingga menjadi graf berarah dinamakan pohon berakar. Akar mempunyai derajat-masuk
sama dengan nol dan simpul-simpul lainnya berderajat-masuk sama dengan satu. Simpul
yang mempunyai derajat-keluar sama dengan nol disebut daun atau simpul terminal. Simpul
yang tidak mempunyai derajat-keluar sama dengan nol disebut simpul dalam atau simpul
cabang. Setiap simpul di dalam pohon dapat dicapai dari akar dengan sebuah lintasan tunggal
(unik). Untuk lebih jelasnya perhatikan gambar 6.
8
Gambar 6 di atas (gambar pohon berakar dengan simpul a sebagai akar) akan
digunakan untuk menjelaskan terminologi pohn berakar.
Misalkan Anak (child) dan Orangtua (parent). d adalah sebuah simpul di dalam pohon
berakar. Simpul e dikatakan anak simpul d jika ada sisi dari simpul d ke simpul e. Dalam hal
ini, d merupakan orangtua dari e. Jadi simpul b, e, f, dan g tidak mempunyai anak.
Saudara Kandung (sibling). Simpul yang mempunyai orangtua yang sama dikatakan
merupakan saudara kandung satu sama lain. simpul b dan c merupakan saudara kandung satu
sama lain. Lintasan (path). Lintasan adalah runtunan simpul-simpul dari simpul awal sampai
simpul tujuan. Panjang lintasan adalah jumlah sisi yang dilalui dalam suatu lintasan.
c. Penerapan Struktur Data Pohon
Berikut akan dikaji penerapan pohon untuk pencarian kata pada inverted file.
Membangun dan mengelola inverted file adalah membutuhkan biaya proses yang relatif kecil.
Inverted file dengan struktur data pohon untuk pencarian kata pada prinsipnya dapat mencari
kata yang memiliki n karakter dengan biaya waktu O(n). Setiap kata pada vocabulary
disimpan dalam struktur pohon dan setiap kata memiliki nilai occurrences masing-masing.
Semua kata sudah tersusun rapi dan siap di retrieve. Jika suatu kata tidak diketemukan pada
vocabulary maka keterangan ini dapat dimasukkan kedalam pohon sebagai kata yang
occurrences-nya nol. Hal ini bisa dipahami secara jelas dengan mengamati gambar 7.
9
Dengan skema ini file disebut juga posting file. Pada file tersebut vocabulary
tersusun secara terurut menurut abjad. Dan untuk tiap kata, terdapat juga pointer untuk tiap
list nya. Hal ini memungkinkan vocabulary untuk disimpan pada memory pada tiap pencarian
di tiap kasus pencarian. Kemudian, nilai kemunculan dapat dengan segera diketahui dengan
hanya sedikit biaya tambahan saja. Namun mekanisme diatas tidak digunakan dalam praktek
koleksi teks yang berukuran besar karena indeks tidak cukup semuanya di masukkan kedalam
memori utama. Hal ini bisa saja disiasati dengan cara melakukan paging. Namun teknik
paging akan menurunkan performansi algoritma. Algoritma ini benar-benar memakan
resource memori untuk meload semua indeks pointer tiap list tiap kata, hal ini menyebabkan
memori utama mengalami exhausted. Untuk selanjutnya akan dikaji alternatif cara untuk
mengatasi hal ini dengan menggunakan struktur data pohon binary.
d. Penerapan Struktur Data Pohon Binary
Pohon binary adalah pohon yang tiap simpulnya berderajat sama yaitu dua. struktur
data ini akan dimanfaatkan untuk mengurangi penggunaan memori utama yang sangat
berlebihan pada struktur data sebelumnya. Sebelumnya indeks dibagi-bagi menjadi beberapa
bagian, misalkan terdapat Ii pada disk. Maka indeks-indeks parsial ini akan digabungkan
secara hierikal mengikuti struktur data pohon binary. Indeks I1 dan I2 digabungkan menjadi
indeks I1..2, Indeks I3 dan I4 digabungkan menjadi indeks I3..4 dan begitu seterusnya. Jika
semua telah digabungkan dengan cara tersebut indeks I1..2 akan digabungkan dengan I3..4
begitu pula yang lainnya mengikuti sampai tergabung seluruhnya. hal ini diilustrasikan pada
gambar 8.
10
Menggabungkan dua buah indeks berarti termasuk juga menggabungkan vocabulary
yang sudah terurut. Dengan struktur ini maka indeks yang ada akan lebih sedikit jumlahnya
yang logikanya sama dengan membadingkan posisi tiap kata menjadi beberapa blok. Karena
indeks parsial akan lebih kecil jumlahnya daripada jumlah keseluruhan indeks kata. Sehingga
dengan adanya operasi penggabungan ini maka untuk pencarian indeks yang memerlukan
penggabungan biayanya adalah konkatinasi dari biaya komputasi teknik sebelumnya yaitu
menjadi O(n1+n2). Biaya tambahan ini masih bisa ditolerir karena ada trade off yang sangat
signifikan yaitu mengurangi konsumsi memori utama sehingga tidak terjadi exhaust.6
6
Hikam,Ibnu. opcit. hal, 5-6.
11
BAB III
A. Kesimpulan
Konsep dasar sistem temu balik informasi (STBI) yaitu proses untuk mengidentifikasi
kecocokan (match) di antara permintaan (query) dengan representasi atau indeks dokumen,
kemudian mengambil (retrieve) dokumen dari suatu simpanan (file) sebagai jawaban atas
pemintaan tersebut. STBI pada prinsipnya bekerja berdasarkan ukuran antara stilah query
dengan istilah yang menjadi representasi dokumen. Secara teknis, tujuan STBI adalah
mencocokkan (matching) term atau istilah yang dibangun (query) dengan term atau indeks
yang ada dalam dokumen, sehingga dengan kecocokan tersebut maka dokumen-dokumen
yang relevan akan terambil (retrived) dari database. Dokumen relevan yang terambil tersebut
itulah tujuan dari STBI. Inverted file atau inverted index adalah mekanisme untuk
pengindeksan kata dari koleksi teks yang digunakan untuk mempercepat proses pencarian.
Struktur inverted file terdiri dari dua elemen, yaitu: kata (vocabulary) dan kemunculan
(occurences).
12