BAB II TINJAUAN PUSTAKA 2.1
Tinjauan Empiris Penulis melakukan penelitian ini dengan terlebih dahulu mengkaji
beberapa publikasi penelitian yang sudah pernah dilakukan dalam kurun waktu lima tahun terakhir, diantaranya adalah sebagai berikut. a) Natural Language Interface to Database Using Semantic Matching. (Neelu Nihalani, 2011) Penelitian ini menggunakan aturan-aturan semantik pada preprocessor yang di-generate secara otomatis. Administrator juga dapat melakukan pengaturan terhadap aturan-aturan tersebut. Aturan semantik didapatkan dari WordNet yang berisi sinonim ataupun arti kata. Dengan menggunakan database Northwind peneliti berhasil membuat NLIDB yang performanya lebih baik dari pada Microsoft English Query. b) NaLIR (Natural Language Interface to Relational Database). (Fei Li, 2014) Pada penelitian ini, dikembangkan NLIDB yang interaktif dengan modul interactive communicator yang ditonjolkan. Modul tersebut memberikan pilihan-pilihan alternatif query kepada user saat ditemukan kesalahan saat memproses query input. c) Antarmuka Bahasa Alami Untuk Melakukan Query Terhadap Terjemahan Al-Quran. (Suwanto Raharjo, 2014) Penelitian
ini
menggunakan
aturan-aturan
produksi
untuk
menghasilkan SQL dari query bahasa alami. Aturan produksi tersebut digunakan untuk mencocokkan pola-pola sintaksis tertentu terhadap query Bahasa Indonesia yang diawali dengan kata tanya 5W 1H. d) Aplikasi Pengolah Bahasa Alami untuk Aplikasi Query Database. (Taryadi, 2010) Pada penelitian ini juga digunakan pola-pola aturan produksi untuk menghasilkan query SQL. aturan-aturan produksi yang digunakan masih sebatas perintah SELECT sederhana dengan sebuah tabel pada basis data yang digunakan. 7
8
Pada penelitian-penelitian sebelumnya, NLIDB yang memproses Bahasa Inggris sudah mampu melakukan translasi dengan baik menggunakan kaidahkaidah sintaksis dan semantik, bahkan dengan menggunakan lebih dari satu tabel pada basis datanya. Sementara, penelitian-penelitian dengan query Bahasa Indonesia masih banyak menggunakan aturan produksi ataupun pencocokan terhadap pola kalimat tertentu sehingga akan banyak ditemukan kesalahan output jika diberikan input query yang tidak sesuai dengan aturan pola yang telah disiapkan. Pada penelitian yang dilakukan penulis, digunakan aturan-aturan sintaksis dan semantik untuk mentranslasikan query Bahasa Indonesia menjadi SQL dengan memberikan opsi query input alternatif sebagai respon terhadap kesalahan input yang dilakukan user, sehingga SQL yang dihasilkan diharapkan lebih tepat dan output yang dihasilkan sistem sesuai dengan yang dimaksudkan oleh user. Tantangan yang dihadapi penulis dalam mengembangkan sistem NLIDB menggunakan Bahasa Indonesia adalah sebagai berikut. 1. Bidang NLP merupakan bidang yang sangat luas. Oleh karena itu, penelitian-penelitian mengenai NLIDB saat ini kebanyakan dibatasi pada domain-domain tertentu. Walaupun, beberapa penelitian menggunakan Bahasa Inggris sudah ada yang menggunakan basis data universal yang bisa bebas digunakan seperti NORTHWIND, namun tidak demikian dengan NLIDB yang menggunakan Bahasa Indonesia. Sistem NLIDB Bahasa Indonesia yang pernah dikembangkan oleh penelitian terdahulu masih
sebatas
menggunakan
domain-domain
tertentu
yang
dispesifikasikan sendiri. 2. Belum ada sistem NLIDB Bahasa Indonesia yang dapat digunakan oleh publik, sehingga tidak ada cara untuk membandingkan performa sistem yang dikembangkan penulis dengan sistem lainnya yang berbahasa Indonesia. 3. Metode pencarian kata dasar yang digunakan pada penelitian ini adalah dengan metode stemming. Sementara, metode-metode stemmer Bahasa Indonesia yang terkenal seperti Porter Stemmer ataupun algoritma NaziefAdriani belum mampu menghasilkan kata dasar yang 100% akurat.
9
Sedangkan, Indonesian Lemmatizer (Derwin Suhartono, 2014) yang memberikan akurasi yang lebih baik dari metode stemming, saat ini masih sedang dikembangkan. Akan tetapi, mengingat perintah-perintah yang digunakan pada penelitian yang dilakukan penulis terbatas pada perintah sederhana yang tidak terlalu banyak menggunakan kata berimbuhan yang kompleks, sehingga penulis memutuskan untuk menggunakan metode stemming. 4. Bahasa Indonesia sebenarnya sudah memiliki kamus sinonim ataupun arti kata seperti halnya WordNet dan Thesaurus pada Bahasa Inggris, namun masih dalam tahap penyempurnaan. Pada penelitian yang dilakukan penulis, daftar kelas kata dan sinonimnya disusun secara manual dengan acuan kamus Kamus Besar Bahasa Indonesia online (www.kbbi.web.id). Dengan melihat keterbatasan-keterbatasan yang ada saat ini, penulis melakukan pengujian performa sistem melalui referensi penelitian-penelitian sebelumnya yang menggunakan Bahasa Indonesia, yakni dengan mengujicobakan sejumlah dataset perintah Bahasa Indonesia kepada sistem yang sebelumnya sudah disusun goal SQLnya terlebih dahulu. Hasil dari pengujian tersebut berupa nilai precision dan recall. 2.2
Tinjauan Teoritis
2.2.1
Basis Data Basis data atau database didefinisikan sebagai kumpulan data yang
terintegrasi dan diatur sedemikian rupa sehingga data tersebut dapat dimanipulasi, diambil, dan dicari secara cepat (Budi Raharjo, 2011). Selain berisi data, basis data juga memiliki metadata, yakni berisi data penjelasan dari struktur basis data, seperti nama relasi (tabel), nama kolom (field), dan tipe data. Ada beberapa operasi dasar yang dapat dilakukan berkenaan dengan basis data (Fathansyah, 1999), antara lain: 1. Pembuatan basis data baru (create database) 2. Penghapusan basis data (drop database) 3. Pembuatan file/tabel baru ke suatu basis data (create table) 4. Penghapusan file/tabel dari suatu basis data (drop table)
10
5. Penambahan/pengisian data baru ke sebuah file/tabel (insert) 6. Pengambilan/pencarian data dari sebuah file/tabel (retrieve/search) 7. Pengubahan data dari sebuah file/tabel (update) 8. Penghapusan data dari sebuah file/tabel (delete). End-user biasanya hanya bisa melakukan poin nomor 5, 6, 7, dan 8 saja, selain itu perlu hak istimewa (seperti administrator) untuk melakukan poin nomor 1, 2, 3, dan 4. Pada penelitian ini, sistem NLIDB Bahasa Indonesia yang dikembangkan hanya mengolah perintah untuk mengambil/menampilkan data saja (poin 6). 2.2.2
Structured Query Language Structured Query Language (SQL) merupakan sebuah bahasa standar yang
digunakan untuk berinteraksi dengan basis data relasional (Budi Raharjo, 2011). Bahasa SQL dibutuhkan untuk dapat melaksanakan semua pekerjaan yang berhubungan dengan manipulasi, definisi, dan administrasi sebuah basis data. Untuk melihat informasi dengan kriteria tertentu dalam suatu database dengan menggunakan SQL, maka pemakai harus memahami struktur SQL, dimana setelah diolah dalam “SQL Engine”, informasi pada basis data dapat dikeluarkan sebagai hasil query seperti pada skema berikut: SQL
SQL Engine
Basis Data
Hasil query
Gambar 2.1 Alur mendapatkan informasi pada basis data Format penulisan SQL untuk menampilkan data adalah sebagai berikut. SELECT nama_tabel.nama_atribut FROM nam_tabel WHERE
;
SQL memiliki operator-operator dan fungsi-fungsi dasar seperti <, >, <=, >=, MIN, MAX, LIKE, NOT LIKE, BETWEEN, AND, OR, COUNT, dan lain sebagainya. Operator-operator tersebut digunakan untuk menspesifikasikan penyeleksian data. 2.2.3
Text Processing
2.2.3.1 Tokenizing Tokenizing adalah proses mensegmentasi/membagi suatu dokumen teks atau string kalimat menjadi token (serangkaian karakter yang merepresentasikan
11
kata) oleh tokenizer. Tokenizer membagi suatu string menjadi token-token berdasarkan karakter tertentu. Biasanya karakter spasi, tab, new row (white space character) yang dijadikan panduan segmentasi menjadi token. Selain itu, tanda baca (punctuation) juga dapat digunakan sebagai pemisah antar token, seperti tanda “-“. Berikut contoh tokenizing pada kalimat “surat masuk dari MIPA”. Input: surat masuk dari MIPA Output: [surat] [masuk] [dari] [MIPA] 2.2.3.2 Spell Check/Correction Spell checking atau spell correction merupakan suatu fitur tambahan yang dapat dimiliki oleh sebuah aplikasi temu kembali informasi di mana query yang diinputkan user akan dikoreksi pengejaan/penulisannya mengacu pada penulisan pada kamus. Jika terdapat kesalahan ejaan, aplikasi dapat memberikan peringatan bahwa terjadi kesalahan penulisan dan akan dicarikan alternatif penulisan yang mungkin dimaksudkan oleh pengguna. Situs pencarian Google menerapkan koreksi kesalahan query dengan memberikan alternatif query, seperti pada “Did you mean”. Tabel 2.1 Pseudocode Levenshtein Edit Distance No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Pseudocode Levenshtein Edit Distance function LevenshteinDistance(char s[1..m], char t[1..n]): declare int d[0..m, 0..n] set each element in d to zero for i from 1 to m: d[i, 0] := i for j from 1 to n: d[0, j] := j for j from 1 to n: for i from 1 to m: if s[i] = t[j]: d[i, j] := d[i-1, j-1] //no operation required else: d[i, j] := minimum(d[i-1, j] + 1, //a deletion d[i, j-1] + 1, //an insertion d[i-1, j-1] + 1) //a substitution return d[m, n]
Terdapat banyak metode untuk menangani kesalahan ejaan/penulisan ini, salah satu yang paling populer adalah Levenshtein Edit Distance (Vladimir Levenshtein, 1985). Levenshtein Edit Distance memberikan nilai/skor terhadap
12
tiap calon koreksi ejaan yang salah. Pseudocode Levenstein Edit Distance dapat dilihat pada Tabel 2.1. 2.2.3.3 Stemming Stemming merupakan proses mengembalikan token ke bentuk semula atau root word (kata dasar). Proses stemming biasanya dilakukan untuk mencari tahu arti kata ataupun kelas kata yang terdapat dalam kamus kata dasar. Terdapat aturan-aturan tertentu dalam proses stemming. Setiap bahasa memiliki aturan stemming yang berbeda-beda tergantung morfologi/pembentukan katanya. Sebagai contoh, dalam Bahasa Indonesia dikenal terdapat algoritma stemming Mirna Adriani dan Bobby Nazief. Algoritma tersebut memiliki aturan imbuhan dengan model sebagai berikut. [[[AW+]AW+]AW+] Kata-Dasar [[+AK][+KK][+P]] AW: Awalan AK: Akhiran KK: Kata ganti kepunyaan P: Partikel
Tanda kurung besar ([ ]) menandakan bahwa imbuhan tersebut opsional. Contoh stemming dengan algoritma M. Adriani dan B.Nazief: Input: “Perlihatkan nomor pendaftaran surat ini” Output: “Lihat nomor daftar surat ini” Tabel 2.2 merupakan algortima dari metode stemming M. Adriani dan B.Nazief (disadur dari laman https://liyantanto.wordpress.com): Tabel 2.2 Algoritma Stemming Nazief & Adriani No. Algoritma Stemming Nazief & Adriani 1. Pertama, cari kata yang akan di-stem pada kamus kata dasar. Jika ada di kamus, maka diasumsikan kata tersebut merupakan kata dasar, dan algoritma berhenti. 2. Eliminasi akhiran partikel, seperti “-lah”, “-kah”, “-pun”, dan akhiran kepemilikan, seperti “-ku”, “-mu”, atau “-nya” jika ada. 3. Eliminasi akhiran “-i”, “-an”, atau “-kan” jika ada. 4. Eliminasi awalan jika ada. 5. Melakukan recording. 6. Jika semua langkah sudah dilakukan namun kata tidak juga ditemukan dalam kamus, maka kata awal diasumsikan sebagai kata dasar. Proses selesai.
13
2.2.4
Natural Language Processing Natural language processing (NLP) atau pengolahan bahasa alami adalah
cabang ilmu kecerdasan buatan (artificial intelligence/AI) dengan ilmu linguistik (Pushpak, 2010). Yang menjadi perhatian dalam NLP adalah bagaimana membuat komputer/mesin mengerti bahasa alami manusia sehingga antara manusia dan komputer dapat berinteraksi dengan perantara bahasa alami, baik itu berupa teks ataupun pesan suara (speech). NLP banyak memberi kemudahan kepada manusia, diantaranya: aplikasi penerjemah bahasa (natural language translation), aplikasi question answering/personal assistant, peringkasan dokumen teks otomatis (tex summarization), dan masih banyak lagi. Secara garis besar, NLP terbagi menjadi dua bidang, yakni: Natural Language
Understanding
(NLU)
merupakan
bidang
yang
mengertikan
(understanding) input bahasa alami, dan Natural Language Generation (NLG) yang menyusun teks bahasa alami. Natural Language Processing Input bahasa alami
Komputer
Understanding
Output bahasa alami
Generation
Gambar 2.2 Dua Fase Utama NLP 2.2.4.1 NLP dalam Bahasa Indonesia Pengolahan bahasa alami mengenal beberapa tingkat pengolahan, yaitu: a) Fonetik dan fonologi Sering digunakan dalam sistem berbasis suara (speech based system). Berhubungan dengan suara yang menghasilkan kata yang dapat dikenali. b) Morfologi Pengetahuan tentang kata dan pembentukannya. Digunakan untuk membedakan satu kata dengan lainnya. c) Sintaksis Pembentukan kalimat oleh kata-kata yang saling berhubungan/berurutan. Pengaturan tata letak suatu kata dalam kalimat akan membentuk kalimat yang dapat dikenali.
14
d) Semantik Pemetaan dari struktur sintaksis yang mempelajari arti suatu kata dalam kalimat (belum mencangkup konteks dari kalimat tersebut). e) Pragmatik Pengetahuan pada tingkatan ini berkaitan dengan masing-masing konteks yang berbeda tergantung pada situasi dan tujuan pembuatan sistem. NLIDB Bahasa Indonesia yang dikembangkan dalam penelitian ini mengolah input berupa teks (tertulis), sehingga pengolahan NLP yang digunakan hanyalah morfologi, sintaksis, dan semantik. Terdapat sembilan kelas kata yang secara umum digunakan dalam Bahasa Indonesia (Abdul Chaer, 2008), yakni: 1. Kata benda (nomina) 2. Kata kerja (verba) 3. Kata sifat (adjektiva) 4. Kata kerja tambahan (adverbia) 5. Kata bilangan (numeralia) 6. Kata depan (preposisi) 7. Kata penghubung (konjungsi) 8. Kata ganti (pronomina) 9. Kata ungkapan (interjeksi) Namun, dalam penelitian ini, penulis tidak menggunakan kata ganti dan kata ungkapan karena kedua kelas kata tersebut tidak dapat diterapkan sebagai perintah untuk menyeleksi data pada basis data arsip surat. Kumpulan kata dapat membentuk frase. Secara sintaksis/gramatikal Bahasa Indonesia, terdapat beberapa kelas kata yang jika disatukan akan membentuk frase (Abdul Chaer, 2009), diantaranya adalah: 1. Frase nominal Nomina + nomina; nomina + verba; nomina + adjektiva; adverbial + nomina; numeralia + nomina. 2. Frase verbal Adverbia + verba; verba + nomina; verba + adjektiva.
15
3. Frase adjektival Adjektiva + nomina; adjektiva + adjektiva; adjektiva + adverbia; 4. Frase preposisional Preposisi + nomina. 5. Frase numeralia numeralia + nomina. Frase-frase tersebut akan membantu dalam menyusun kalimat dengan menggunakan pola-pola kalimat tertentu. Frase-frase ini juga menjadi landasan penyusunan aturan-aturan sintaksis dalam sistem NLIDB Bahasa Indonesia. Pada sistem NLIDB Bahasa Indonesia yang dikembangkan penulis, input sistem adalah berupa kalimat perintah dasar. Menurut Abdul Chaer (2009), Pola kalimat perintah dasar dalam Bahasa Indonesia menggunakan pola inversi, yang artinya predikat mendahului subjek. Pola kalimat inversi dapat berupa: P-S, P-SK, atau P-S-O-K. Di mana, subjek dan objek dapat disusun oleh kata nomina, frase preposisional, atau frase nominal. Sedangkan, predikat dapat disusun oleh kata kerja, kata sifat, kata kerja tambahan, frase verbal, frase numeralia, frase adjektiva, maupun frase adverbial. 2.2.4.2 Context-Free Grammar (CFG) Dalam bahasa, grammar adalah aturan-aturan yang menjelaskan bagaimana merangkai kata-kata menjadi kalimat. Context-Free Grammar (CFG/ Phrase-Structure Grammar/Backus-Naur Form) adalah suatu notasi matematis yang menyatakan aturan sebuah bahasa berdasarkan constituency (Ruli Manurung, 2008). CFG terdiri dari dua bagian, yakni: 1. Sehimpunan rule atau production, yang menyatakan bagaimana symbol dalam bahasa dikelompokkan. 2. Lexicon (daftar symbol/kata) Symbol-symbol dalam CFG terbagai dua kelas, yaitu: 1. Terminal symbols: symbol yang merepresentasikan kata dalam bahasa. 2. Non-terminal symbols: symbol yang merepresentasikan kelompok/ generalisasi terminal. Contoh CFG adalah sebagai berikut. Contoh rule:
Kal verba nomina
16
Contoh lexicon:
verba tampilkan; nomina surat
CFG secara simbolik dapat dutuliskan sebagai berikut (Altshuler, 2007). G = (N, Σ, P, S) dimana: N = himpunan non-terminal symbol Σ = himpunan terminal symbol (token) P = himpunan production / rule S = start symbol Rule (grammar) pada CFG biasanya ditulis dengan format Chomsky Normal Form (CNF), dimana terminal symbol ditulis di sisi kiri (left hand side) dan non-terminal symbol ditulis di sisi kanan (right hand side). Contoh penulisan grammar CNF: Aa A BC Untuk melakukan parsing terhadap suatu bahasa (berupa kalimat) dapat dilakukan dengan dua cara, yaitu top-down parsing dan bottom-up parsing. a) Top-down parsing adalah metode parsing yang berhaluan tujuan (goaldriven), dilakukan dari atas (start symbol) ke bawah. Contoh: Earley parsing. b) Bottom-up parsing adalah kebalikan dari top-down parsing yang dimulai dari bawah ke atas (data-driven). Contoh: CYK. Pada penelitian ini digunakan metode bottom-up parsing dengan algoritma Cocke-Younger-Kasami (CYK). CYK mampu mengenali apakah suatu CFG dapat dikategorikan sebagai bahasa atau tidak. CYK menggunakan grammar CNF secara langsung. Tabel 2. adalah algoritma dari CYK parsing. Tabel 2.3 Algoritma Cocke-Younger-Kasami (CYK) No. Algoritma CYK 1 Buat tabel n x n, dimana n adalah jumlah kata. 2 Untuk semua cell yang index baris dan kolomnya sama, inisialisasi dengan kelas kata (terminal symbol) yang diperoleh dari lexicon. 3 Mulai dari index kolom terkecil dan index baris = index kolom -1 4 Cari non-terminal symbol pada grammar daripada gabungan kelas kata dari index kolom sebelumnya dan index baris setelahnya.
17
5
Lakukan poin 3 dan 4 hingga mencapai cell root (index baris terkecil, index kolom terbesar). Jika cell root memiliki non-terminal symbol „Kal‟, maka dikatakan CFG tersebut sesuai dengan bahasa.
6 2.2.5
Natural Language Interface to Database (NLIDB) Natural Language Interfaces to Databases (NLIDB) adalah suatu sistem
yang mampu mentranslasikan perintah (senctence) bahasa alami manusia menjadi query basis data (Androutsopoulos dkk, 1995). Terdapat beberapa arsitektur NLIDB yang pernah dikembangkan di dunia, diantaranya adalah: a) Pattern-matching systems Pada arsitektur ini digunakan metode pattern-matching untuk menjawab pertanyaan/perintah user. Sebagai contoh: pattern:
… “capital” …
action:
Report CAPITAL of row where COUNTRY =
b) Syntax-based systems Pada arsitektur ini, inputan user di-parsing (dianalisis secara sintaksis), kemudian hasil dari parse tree langsung dipetakan ke bahasa query basis data.
Syntax-based
system
menggunakan
grammar
yang
dapat
mendeskripsikan kemungkinan struktur sintaksis pada pertanyaan user. Sebagai contoh: sistem grammar pada NLIDB LUNAR: S
NP
VP
NP
Det
N
Det
“what” | “which”
N
“rock”| “specimen” | “magnesium” | “radiation” | “light”
VP
V
V
“contains” | “emits”
N
Keterangan: (S) Sentence
(Det) Determiner
(NP) Noun Phrase
(VP) Verb Phrase
(N) Noun
(V) Verb
18
Gambar 2.3 Contoh parse tree NLIDB dapat memetakan parse tree di atas menjadi query basis data berikut. (for every X (is_rock X) (contains X magnesium) ; (printout X))
c) Semantic grammar systems Pada arsitektur semantic grammar systems, tanya-jawab masih dilakukan dengan mem-parsing input lalu memetakan parse tree ke query basis data. Perbedaannya terletak pada kategori grammar (node yang bukan leaf pada parse tree) tidak begitu sesuai dengan konsep sintaksis. Contoh semantic grammar: S Specimen_question | spacecraft_question Specimen_question Specimen Emits_info | Specimen Contains_info Specimen “which rock” | “which specimen” Emits_info “emits” Radiation Radiation “radiation” | “light” Contains_info “contains” Substance Substance “magnesium” | “calcium” Spacecraft_question Spacecraft Depart_info | Spacecraft Arrive_info Spacecraft “which vessel” | “which spacecraft” Depart_info “was launched on” Date | “departed on” Date Arrive_info “returns on” Date | “arrives on” Date
19
Gambar 2.4 Contoh semantic parse tree d) Intermediate representation languages system input bahasa alami
syntax rules
parser
lexicon
parse tree
semantic rules
semantic interpreter
world model
logical form linguistic front-end
Database query generator SQL
Database Management System
mapping to DB info domain-dependent knowledge
database
hasil kembalian
output
Gambar 2.5 Arsitektur Intermediate Representation Language System
Kebanyakan NLIDB saat ini menggunakan arsitektur ini. Pertama-tama pertanyaan bahasa alami ditransformasikan ke intermediate logical query (query peralihan). Query ini mengekspresikan arti dari pertanyaan user dalam high level world concepts yang tidak bergantung pada struktur basis data.
20
Kelebihan dan kekurangan NLIDB menurut Androutsopoulus adalah sebagai berikut. 2.2.5.1 Kelebihan NLIDB a) Pengguna (user) sistem NLIDB tidak perlu mempelajari bahasa query basis data (SQL, dll.) melainkan cukup melakukan perintah dengan bahasa alami. b) Perintah negasi (tidak, bukan, dll.) lebih mudah diekspresikan dalam bahasa alami dibandingkan dengan menggunakan antarmuka form. 2.2.5.2 Kekurangan NLIDB a) Perintah-perintah yang dapat dilakukan user bersifat terbatas dan user sulit mengetahui perintah seperti apa yang tidak boleh diinputkan ke sistem. b) Ketika sistem NLIDB tidak mengerti perintah user, seringkali sistem langsung menolak perintah tersebut sehingga user tidak mengetahui dengan jelas pada bagian mana dari inputan perintahnya yang salah/tidak diterima sistem. c) Bersifat domain-dependent yang artinya satu sistem hanya akan bekerja dengan baik pada satu kasus/domain tertentu. Jika digunakan pada domain lain biasanya akan sulit melakukan konfigurasi yang sesuai.
