indexing - lecturer.ukdw.ac.idlecturer.ukdw.ac.id/budsus/pdf/genap12/twm/minggu8.pdf · •...

4/2/13

1

INDEXING Budi Susanto (v1.01)

Text dan Web Mining - Budi Susanto TI UKDW 1

Tujuan • Memaham pengertian dari information retrieval • Memahami pembentukan struktur inverted index

• Memahami tentang kebutuhan index terhadap adanya query frase

• Memahami kebutuhan index terhadap query wildcard


4/2/13

2

Buku Acuan • Manning, C. D., Raghavan, P., Chutze, H. (2008).

Introduction to Information Retrieval. Cammbridge University Press, New York, Chapter 1, 2, dan 3.


Definisi IR •  Information Retrieval (IR) is finding material (usually

documents) of an unstructured nature (usually text) that satisfies an information need from within large collections (usually stored on computers). - Manning (2008) •  IR dapat mencakup bentuk masalah data dan informasi selain

disebutkan pada definisi di atas. •  Misalnya beberapa format dokumen memiliki suatu struktur header,

body, dan footer. •  Sering disebut dengan semistructure data.


4/2/13

3

Contoh Masalah IR •  Terdapat sekumpulan dokumen berita dari berbagai

macam kelompok berita. • Kemudian ingin ditemukan dokumen berita apa saja yang

berisi kata •  badai AND topan AND NOT tsunami.

• Solusi: •  Cara paling sederhana adalah melakukan pemindaian secara linier

terhadap seluruh dokumen. •  Proses ini sering disebut sebagai grepping. •  Apa masalahnya?


Contoh Masalah IR • Dengan kemampuan komputer saat ini, ada kebutuhan

yang lebih terhadap pencarian: •  mampu memproses kumpulan dokumen sangat besar secara

cepat; •  memungkinkan operasi-operasi pencocokan yang fleksibel; •  Memungkinkan melakukan pemeringkatan terhadap hasil

pencarian.

• Salah satu cara untuk menghindari pemindaian linier adalah membuat sebuah index terhadap seluruh dokumen.


4/2/13

4

Contoh incidence matrix


Antony and Cleopatra Julius Caesar The Tempest Hamlet Othello Macbeth

Antony 1 1 0 0 0 1

Brutus 1 1 0 1 0 0

Caesar 1 1 0 1 1 1

Calpurnia 0 1 0 0 0 0

Cleopatra 1 0 0 0 0 0

mercy 1 0 1 1 1 1

worser 1 0 1 1 1 0

1 if play contains word, 0 otherwise

Contoh pencarian • Sehingga untuk menemukan dokumen terhadap query:

•  Brutus AND Caesar AND NOT Calpurnia

• Dilakukan operasi boolean:

• 110100 AND 110111 AND 101111 = 100100.


4/2/13

5

Model Pencarian Klasik


Corpus

TASK

Info Need

Query

Verbal form

Results

SEARCH ENGINE

Query Refinement

Get rid of mice in a politically correct way

Info about removing mice without killing them

How do I trap mice alive?

mouse trap

Misconception?

Mistranslation?

Misformulation?

Terminologi • Kebutuhan informasi

•  Topik dimana ingin diketahui lebih oleh pemakai

• Query •  Sesuatu yang pemakai sampaikan kepada komputer dalam rangka

mencoba untuk mengkomunikasikan kebutuhan informasi.

• Dokumen Relevan •  Dikatakan relevan ketika pemakai mempersepsikan bahwa

dokumen tersebut mengandung informasi yang berkaitan dengan kebutuhan informasi mereka.


4/2/13

6

Dasar Evaluasi IR • Untuk menilai efektifitas sebuah sistem IR (kualitas hasil

pencarian), pada umumnya digunakan: •  Precision

•  Berapa bagian dari hasil kembalian adalah relevan dengan kebutuhan informasi?

•  Recall •  Berapa bagian dari dokumen relevan dalam koleksi yang dikembalikan

oleh sistem?


Dasar Inverted Index • Daripada menyimpan secara biner (slide 6) untuk semua

term (vocabulary – kumpulan term), sebaiknya cukup disimpan dokumen apa saja yang mengandung masing-masing term.


Brutus

Calpurnia

Caesar 1 2 4 5 6 16 57 132

1 2 4 11 31 45 173

2 31

174

54 101

Dictionary Postings

4/2/13

7

Struktur Data untuk Dictionary

• Array. Contoh:

char* Postings[50];

•  dimana Postings berupa struct atau class


Struktur Data untuk Dictionary • Hashtables

•  Setiap term di-hash menjadi sebuah integer. •  Contoh fungsi hash:


http://en.wikipedia.org/w/index.php?title=File:Hash_table_5_0_1_1_1_1_1_LL.svg&page=1

/* Peter Weinberger's */ int hashpjw(char *s) { char *p; unsigned int h, g; h = 0; for(p=s; *p!='\0'; p++){ h = (h<<4) + *p; if (g = h&0xF0000000) { h ^= g>>24; h ^= g; } } return h % 211; }

4/2/13

8

Struktur Data untuk Dictionary


Root a-m n-z

a-hu hy-m n-sh si-z

aardvark!

huygens!

sickle!

zygot!

15

Binary Search Tree

Struktur Data untuk Dictionary • B+ Tree


a-hu hy-m

n-z

4/2/13

9

Pembentukan Inverted Index


Tokenisasi

Normalisasi

Indexer Inverted index

Kompulan dokumen

Inverted index harus disimpan dalam struktur list yang dinamis.

Contoh Indexer


I did enact Julius Caesar I was killed

i' the Capitol; Brutus killed me.

Doc 1

So let it be with Caesar. The noble

Brutus hath told you Caesar was ambitious

Doc 2

Tokenisasi dan Normalisasi

4/2/13

10

Contoh Indexer

Sorting

• Diurutkan berdasar term • Kemudian diurutkan

berdasar docID


Contoh Indexer

Dictionary dan Postings

• Beberapa term sama dalam dokumen tunggal di gabungkan.

• Dipisahkan ke dalam Dictionary dan Postings.

•  Informasi tambahan, seperti frekuensi kemunculan term, disimpan.


4/2/13

11

Contoh Query • Dicari: Brutus AND Calpurnia • Proses:

1.  Temukan Brutus dalam dictionary. 2.  Ambil postings yang terkait. 3.  Temukan Calpurnia dalam dictionary. 4.  Ambil postings yang terkait. 5.  Lakukan operasi interseksi antara dua daftar postings.

•  Interseksi adalah memilih item dari dua list yang sama.


Algoritma Interseksi


4/2/13

12

Contoh Interseksi


Latihan #1 1.  Gambarkan inverted index untuk

Doc 1 new home sales top forecasts

Doc 2 home sales rise in july

Doc 3 increase in home sales in july

Doc 4 july new home sales rise


4/2/13

13

Latihan #2 •  Terdapat kumpulan dokumen berikut: Doc 1 breakthrough drug for schizophrenia Doc 2 new schizophrenia drug Doc 3 new approach for treatment of schizophrenia Doc 4 new hopes for schizophrenia patients 1.  Gambarkan incidence matrix untuk kumpulan dokumen

tersebut 2.  Gambarkan inverted index untuk kumpulan dokumen

tersebut. 3.  Apa hasil kembalian untuk query berikut:

a.  schizophrenia AND drug b.  for AND NOT(drug OR approach)


Ingest • Menurut Kowalski, G. (2010), proses awal dalam suatu

sistem information retrieval disebut sebagai ingest. •  Ingest merupakan proses yang menerima item-item yang

akan disimpan dan diindex dalam sistem dan melakukan preprocessing. •  Pull atau crawling. •  Tokenisasi •  Deteksi kemiripan dan atau duplikasi •  Stemming dan atau normalisasi lain •  Ekstraksi entitas (information extraction) •  Pemrosesan metadata


4/2/13

14

Query Frase • Saat ini sistem IR harus juga mampu menerima query

dalam bentuk frase. •  Contoh: “Universitas Kristen Duta Wacana” atau “UKDW

Yogyakarta” •  Sehingga jika ada dokumen berisi “Duta Wacana adalah satu-satunya

universtas kristen terbaik di Yogyakarta” tidak akan ditemukan.

•  Frase dalam query biasanya ditulis dalam tanda petik ganda (“).

• Dengan query frase, diperlukan struktur index yang sedikit berbeda.


Biword Index • Sebuah pengindex yang akan membangun dictionary

berdasar setiap pasangan dua kata yang muncul dalam tiap dokumen.

• Contoh: universitas kristen duta wacana, • Akan diindex membentuk dictionary:

•  universitas kristen •  kristen duta •  duta wacana


4/2/13

15

Biword Index • Sehingga penanganan query yang panjang, seperti:

•  universitas duta wacana yogyakarta

• Akan dibagi menjadi: •  “universitas duta” AND “duta wacana” AND “wacana yogyakarta”

• Kelemahan: •  Bisa memberikan false positif.

•  Tanpa melakukan pengujian terhadap seluruh dokumen, kita tidak dapat memverifikasi apakah query tersebut memang mewakili frase yang sebenarnya.


Extended Biword • Memparsing teks dan melakukan POST. •  Term-term akan dikenali sebagai Nouns (N) dan artikel/

preposisi (X).

• Dengan demikian, maka setiap string berpola NX*N merupakan bentukan dari dictionary.

• Contoh: universitas di yogyakarta

• Akan diparsing menjadi N X N, sehingga index yang dicari adalah: •  universitas yogyakarta


4/2/13

16

Positional Index • Dalam postings, simpan posisi setiap term dimana term

tersebut muncul:

<term, number of docs containing term; doc1: posiBon1, posiBon2 … ; doc2: posiBon1, posiBon2 … ; etc.>


Contoh Positional Index


4/2/13

17

Positional Intersect Algorithm


Wildcard Queries • Contoh wildcard query:

•  yogya* : menemukan semua dokumen yang berisi sembarang kata berawalan yogya.

•  Dengan B+Tree dapat cukup dilakukan dengan mencari semua node yang berada di bawah node yogya.

•  yogya ≤ w < yogyb

•  Bagaimana dengan query: *arta ?

•  Perlu dipelihara B+ tree tambahan yang menyimpan backward dari semua kata.

•  Bagaimana dengan query: yo*arta?


4/2/13

18

Permuterm Index • Menggunakan karakter khusus, misal $, untuk menandai

akhir sebuah term. •  Contoh: ukdw akan tersimpan sebagai ukdw$.

• Dibangun sebuah permuterm index yang berisi berbagai bentuk rotasi tiap term. •  kdw$u, dw$uk, w$ukw

• Query wildcard •  X lookup on X$ •  X* lookup on $X* •  *X lookup on X$* •  *X* lookup on X* •  X*Y lookup on Y$X*


K-gram index • Menghasilkan enumerasi semua k-grams (deretan k-

karakter) dari tiap kata yang muncul. • Contoh enumerasi dari kalimat “ukdw yogyakarta” dengan

3-gram adalah: •  $uk, ukd, kdw, dw$, $yo, yog, ogy, gya, yak, aka, art, rta, ta$

• Setiap postings akan berisi semua term yang berisi k-gram dari dictionary.


mo

on

among

$m mace

along

amortize

madden

among

4/2/13

19

k-gram index • Semua query yang dikenakan terhadap k-gram index

akan dilakukan proses enumerasi serupa dengan pembentukan index.

• Contoh: yo*arta akan diubah menjadi •  $yo AND art AND rta AND ta$


Spelling Correction •  Terdapat dua prinsip dasar :

1.  Pilih salah satu yang paling mendekati dari query yang salah ejaan. •  Didasarkan pada dictionary index.

3.  Ketika terdapat dua atau lebih kemunculan term yang benar, maka dipilih yang paling umum digunakan.

• Bentuk pembetulan ejaan •  Isolated-term

•  Pembetulan terhadap masing-masing kata •  Context-sensitive

•  Pembetulan berdasar kata-kata yang ada di sekitarnya.


4/2/13

20

Isolated-Term • Menggunakan dasar lexicon dimana pembetulan ejaan

berasal. •  Standar lexicon

•  Misalnya Kamus bahasa •  Index lexicon

•  Terdapat dua metode: •  Edit distance •  K-gram


Edit Distance (Levenshtein distance)


• Diberikan dua buah string, S1 dan S2, pilih kata yang memiliki jumlah operasi konversi paling kecil.

•  Jenis operasi yang dilakukan: •  Insert, delete, replace

4/2/13

21

Contoh


u n v e r s i t a 0 1 2 3 4 5 6 7 8 9

u 1 0 1 2 3 4 5 6 7 8 n 2 1 0 1 2 3 4 5 6 7 i 3 2 1 1 2 3 4 4 5 6 v 4 3 2 1 2 3 4 5 6 7 e 5 4 3 2 1 2 3 4 5 6 r 6 5 4 3 2 1 2 3 4 5 s 7 6 5 4 3 2 1 2 3 4 i 8 7 6 5 4 3 2 1 2 3 t 9 8 7 6 5 4 3 2 1 2 a 10 9 8 7 6 5 4 3 2 1 s 11 10 9 8 7 6 5 4 3 2

Latihan


j o g j a k a t a

y

o

g

y

a

k

a

r

t

a

4/2/13

22

K-gram • Enumerasikan semua n-gram dalam string query

sebagaimana terhadap lexicon. • Gunakan index n-gram untuk mengambil semua lexicon

yang cocok dengan n-gram query. •  Threshold dengan jumlah n-gram yang cocok.


Contoh tri-gram • Sebagai contoh term november

•  nov, ove, vem, emb, mbe, ber.

• Query adalah december. •  dec, ece, cem, emb, mbe, ber.

•  Terdapat 3 trigram yang overlap. • Bagaimana caranya agar overlap tersebut

dinormalisasikan menjadi sebuah nilai overlap?


4/2/13

23

Jaccard coefficient • X dan Y adalah himpunan n-gram. Maka JC adalah

• Contoh:

•  JC untuk q=bord dan term=boardroom •  2/(8+3-2)


YXYX ∪∩ /

TERIMA KASIH Budi Susanto


indexing - lecturer.ukdw.ac.idlecturer.ukdw.ac.id/budsus/pdf/genap12/twm/minggu8.pdf · •...

Documents