BAB I
PENDAHULUAN
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.
1.
Bagaimana Proses pencocokan pemanggilan sebuah dokumen?
2.
Apa peran Inverted file didalam pemanggilan dokumen?
BAB II
PEMBAHASAN
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 untuk menemukan kembali dokumen-dokumen yang telah
disimpan dan diorganisir melalui proses.[2]
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.
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 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.
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]
Setiap istilah indeks dikaitkan dengan daftar
inverted, yaitu :
a) Berisi
daftar dokumen, atau daftar kata kejadian dalam dokumen, dan informasi lainnya
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]
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.
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.
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 dokumen[5]
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).
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.
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.
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.
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]
BAB III
PENUTUP
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).
[1]
Bab II,”di unduh di http://library.binus.ac.id.
hal. 32-33 tanggal 15 oktober 2017 pukul 16.00 WIB.
[2]
Hasugian,Jonner.”penelusuran informasi ilmiah secara online. Medan: jurnal
studi perpustakaan dan informasi, vol 2, juni 2006.(di unduh http://puslit2.petra.ac.id tanggal 11
oktober 2017, pukul 12.00 WIB) hal 3-4.
[3]
Hikam,Ibnu. “Penerapan Pohon Untuk Algoritma Pencarian Kata Pada Inverted File
Dalam Sistem Temu Balik Informasi” (Di unduh di http://informatika.stei.itb.ac.id/makalah2008.pdf pada tanggal 12 Oktober pukul 17:08 WIB). hal,
3-4
[4]
Cornell Education. “Information Retrieval” (diunduh di http://www.cs.cornell.edu/courses/cs4300/2013fa/lectures/inverted-indexes-4pp.pdf
pada
tanggal 10 Oktober pukul 16:01 WIB). Hal, 3.
[5]
Suhartono, Derwin. “Electronic Document Management Using Inverted Files System” (Di
unduh di https://www.epj-conferences.org/articles/epjconf/abs/2014/05/epjconf_icas2013_00004/epjconf_icas2013_00004.html pada
tanggal 10 Oktober pukul 16:01 WIB). Hal, 3-4.
[6]
Hikam,Ibnu. opcit. hal, 5-6.
Komentar
Posting Komentar