TBI18-TI15C-P4-MODEL BOOLEAN & ADVANCED BOOLEAN-KHAERUL IMAM

November 23, 2018
 |  No Comments

TEMU BALIK INFORMASI

MODEL BOOLEAN DAN ADVANCED BOOLEAN

Definisi Aljabar Boolean

Aljabar boolean merupakan aljabar yang berhubungan dengan variabel-variabel biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR dan NOT (komplemen). Fungsi boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logika, dan tanda kurung.

Suatu fungsi boolean bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boolean merupakan daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner.

Operasi – Operasi Yang Terdapat Pada Model Boolean

  1. Operasi AND

Operasi AND merupakan operasi boolean yang yang akan memghasilkan nilai 1 ketika dipasangkan dengan 1 pula.           Operasi AND dilambangkan dengan dot ( . ). Operasi ini hanya akan menghasilkan nilai benar jika kedua variabel bernilai benar, selain itu akan bernilai salah.

  1. Operasi OR

Operasi OR merupakan operasi yang hanya akan menghasilkan nilai benar(1) jika salah satu variabelnya bernilai benar(1) serta akan menghasilkan nilai salah jika kedua variabelnya bernilai salah. Operasi OR dilambangkan dengan plus (+).

  1. Operasi Turunan / Operasi logika NOR

Operasi NOR merupakan perpaduan dari operasi OR dan INVERS / NOT. Operasi NOR kan menghasilkan keluaran OR yang di inverskan. Operasi NOR mempunyai dua buah lambang yaitu lambang OR (+) dan INVERS / NOT ( ‘ ).

  1. Operasi logika NAND

Operasi NAND merupakan perpaduan dari operasi AND dan INVERS / NOT. Operasi NAND akan menghasilkan keluaran AND yang di inverskan. Operasi NAND mempunyai dua buah lambang yaitu lambang AND ( . ) dan INVERS / NOT ( ‘ ).

  1. Operasi logika EXOR

EXOR berarti exklusive OR berarti “yang satu atau yang satunya tapi tidak keduanya”. Operasi XOR akan menghasilkan keluaran 1(benar) jika jumlah masukan yang bernilai 1(benar) berjumlah ganjil. Operasi XOR merupakan hasil dari (a’.b) + (a.b’) atau biasa ditulis a    b. Tabel kebenaran untuk operasi XOR.

Definisi Model Boolean

Model penelusuran informasi dimana kita dapat membentuk query berdasarkan aturan Boolean dan dikombinasikan dengan operator AND, OR, dan NOT serta menggunakan tanda kurung untuk menentukan scope operator. Model Boolean ini berdasarkan teori himpunan dan aljabar Boolean.

Dokumen adalah himpunan dari istilah (term) dan query adalah pernyataan Boolean yang ditulis pada term. Istilah (term) dalam sebuah query dihubungkan dengan menggunakan operator AND, OR atau NOT. Pada proses penelusuran model Boolean, setiap kata dirubah ke dalam ekspresi Boolean sehingga menghasilkan sebuah aturan binary yang disebut incidence matrix. Sehingga variabel nilai bobot istilah indeks selalu bersifat biner (dua pilihan), yaitu nol atau satu. Jika  nilainya satu maka model Boolean menyimpulkan bahwa dokumen relevan terhadap sebuah permintaan (query). Selebihnya, kalau bernilai nol maka dokumen dianggap tidak relevan.

Untuk dapat melakukan proses penelusuran Booelan, keberadaan inverted index sangat diperlukan, karena index ini akan sangat membantu dalam proses penelusuran yang efektif.

Langkah melakukan inverted index :

  1. Kumpulkan dokumen untuk diindeks
  2. Lakukan pemisahan teks, mengubah setiap dokumen menjadi daftar token
  3. Lakukan proses linguistik, menghasilkan daftar token normalisasi, yang merupakan istilah pengindeksan
  4. Indeks dokumen yang terjadi pada setiap istilah dengan menciptakan sebuah indeks terbalik (inverted index), yang terdiri dari kamus dan posting

Beberapa langkah yang dapat dilakukan dalam Proses Booelan Retrieval ini antara lain:

  1. Lakukan indexing, dalam hal ini inverted index
  2. Temukan kata/term query didalam kamus dan daftar posting
  3. Lakukan operasi dari operator logika yang diinginkan dengan mencari irisan dari posting list

Contoh untuk memproses permintaan kata sambung berikut :

Contoh Kalimat : Brutus AND Calpurnia

Lakukan inverted index :

  1. Brutus Cari di Kamus
  2. Ambil posting nya
  3. Calpurnia Cari di Kamus
  4. Ambil posting nya
  5. Perpotongan (bagian yang sama) dari daftar dua posting

Operasi perpotongan (intersection)

adalah satu hal penting: kita perlu memotong daftar postingan sehingga dapat dengan cepat menemukan dokumen yang mengandung kedua istilah. (Operasi ini kadang-kadang disebut sebagai penggabungan daftar posting: nama ini mencerminkan sedikit berlawanan menggunakan istilah penggabungan algoritma untuk keluarga umum algoritma yang menggabungkan daftar diurutkan beberapa oleh interleaved memajukan pointer melalui masing-masing, di sini kita menggabungkan daftar dengan operasi logika AND.)

Algoritmanya untuk perpotongan dua daftar posting, p1 dan p2 :

INTERSECT(p1, p2)

  1.  answer ← h i
  2.  while p1 6= NIL and p2 6= NIL
  3.  do if docID(p1) = docID(p2)
  4.  then ADD(answer, docID(p1))
  5.  p1 ←next(p1)
  6.  p2 ←next(p2)
  7.  else if docID(p1) < docID(p2)
  8.  then p1 ←next(p1)
  9.  else p2 ←next(p2)
  10.  return answer

Untuk memproses query yang lebih rumit dapat dilakukan optimasi query. Optimasi Query adalah proses pemilihan bagaimana mengatur pekerjaan menjawab query sehingga jumlah pekerjaan yang harus dilakukan oleh sistem lebih sedikit. Unsur utama untuk query Boolean ini adalah urutan daftar postingan yang diakses.

Algoritma untuk query kata penghubung yang mengembalikan set dokumen yang berisi setiap istilah dalam daftar istilah masukan:

INTERSECT(ht1, . . . , tni)

  1.  terms ← SORTBYINCREASINGFREQUENCY(ht1, . . . , tni)
  2.  result ←postings( f irst(terms))
  3.  terms ←rest(terms)
  4.  while terms 6= NIL and result 6= NIL
  5.  do result ← INTERSECT(result, postings( f irst(terms)))
  6.  terms ←rest(terms)
  7.  return result

Model Boolean tidak melakukan pengambilan peringkat. Namun, model ini masih dijadikan pilihan utama untuk search engine dengan memasukkan tambahan seperti operator kedekatan panjang. Sebuah operator kedekatan adalah cara menentukan bahwa dua istilah dalam query harus terjadi dekat satu sama lain dalam dokumen, dimana kedekatan dapat diukur dengan membatasi jumlah kata intervensi yang diizinkan atau dengan mengacu pada unit struktural seperti kalimat atau paragraf .

Beberapa Keuntungan & Kerugian dari Model Boolean

Keuntungan menggunakan model Boolean :

  1. Model Boolean merupakan model sederhana yang menggunakan teori dasar himpunan sehingga mudah diimplementasikan.
  2. Model Boolean dapat diperluas dengan menggunakan proximity operator dan wildcard operator.
  3. Adanya pertimbangan biaya untuk mengubah software dan struktur database, terutama pada sistem komersil.

Kerugian menggunakan Model boolean :

  1. Model Boolean tidak menggunakan peringkat  dokumen yang terambil. Dokumen yang terambil hanya dokumen yang benar-benar sesuai dengan pernyataan boolean/query yang diberikan sehingga dokumen yang terambil bisa sangat banyak atau bisa sedikit. Akibatnya ada kesulitan dalam mengambil keputusan
  2. Teori himpunan memang mudah, namun tidak demikian halnya dengan pernyataan Boolean yang bisa kompleks. Akibatnya pengguna harus memiliki pengetahuan banyak mengenai query dengan boolean agar pencarian menjadi efisien
  3. Tidak bisa menyelesaikan partial matching pada query.

Untuk mengatasi masalah ini, maka dikembangkan operasi pembobotan dokumen berdasarkan frekuensi kemunculan istilah (term) pada dokumen tersebut. Model Boolean juga dikombinasikan dengan content-based navigation dengan menggunakan konsep lattice, dimana shared term dari dokumen yang terambil sebelumnya digunakan untuk memperbaiki dan meng-expand query.

ADVANCED BOOLEAN

Sumber Referensi :

download ppt nya disini : ppt4

Temu Balik Informasi