analisis leksikal & katahenti (lexical analysis & stoplists)

ANALISIS LEKSIKAL & KATAHENTI

(LEXICAL ANALYSIS & STOPLISTS)

Bagaimana pemprosesan teks? Apa yang akan terjadi jika perkataan diambil sepenuhnya

sebagaimana ia ujud dalam sesuatu dokumen? Bagaimana pula dengan tanda punctuation, capitalization,

dll.? Bagaimana dengan kesilapan ejaan? Bagaimana dengan bentuk plural vs. singular dalam

perkataan Bahasa Inggeris dan pengulangan kata dalam bahasa Melayu?

Informationneed

Index

Pra-proses

Hurai

Koleksi

pangkat

kueri

text inputBagaiman kueri dijana? Bagaimana

teks diproses?

Pemprosesan Teks

Pendekatan umum operasi teksPemprosesan ke atas dokumen dan kueri adalah berdasarkan kaedah yang sama

Analisis Leksikal bagi Teks

Analisis leksikal ialah proses menukarkan satu input strim aksara kepada perkataan atau token. (proses penyatuan huruf-huruf ke dalam bentuk perkataan-perkataan atau token (sekumpulan huruf-huruf yang memberi sesuatu makna)

Ia merupakan perkara pertama yang dilakukan dalam proses pengindeksan automatik (automatic indexing) dan pemprosesan query.

Pengindeksan automatik ialah proses penilaian item dalam maklumat untuk menghasilkan senarai indeks sebutan.

Analisis leksikal menghasilkan calon indeks sebutan yang seterusnya akan diproses dan dimasukkan ke dalam indeks.

Pemprosesan query adalah suatu aktiviti yang melibatkan penganalisaan query dan membandingkannya dengan indeks untuk mencapai item yang relevan.

Dalam pengindeksan automatik, calon indeks akan dibandingkan dengan katahenti.

Analisis Leksikal bagi Teks

Analisis Leksikal untuk Pengindeksan Automatik

Keputusan yang pertama perlu dibuat dalam merekabentuk penganalisa leksikal untuk sistem pengindeksan automatik ialah: Apakah item yang dipertimbangkan sebagai perkataan atau token dalam skema pengindeksan?

Perkara yang perlu dipertimbangkan: Digits Tanda selang (hyphens) Tanda bacaan lain (punctuations) Case letters

Analisis Leksikal untuk Pemprosesan Query Merekabentuk suatu penganalisa leksikal untuk

pemprosesan query adalah sama seperti pengindeksan automatik.

Ia bergantung kepada penganalisa leksikal untuk pengindeksan automatik kerana sebutan gelintaran query mesti sepadan dengan sebutan indeks.

Analisis Leksikal untuk Pemprosesan Query Walaubagaimanapun, penganalisa leksikal query mesti

membezakan:• 1.pengoperasi (operator) seperti pengoperasi Boolean,

pengoperasi pangkasan dan cantasan.• 2.penunjuk pengumpulan (grouping indicators) seperti

tanda “ “ dan ( ).• 3.mengenalpasti kurungan, tanda ‘&’,~ dan ^

(pengoperasi boolean) adakah sebahagian dari analisis leksikal

Senarai perkataan yang ditapis semasa pengindeksan automatik kerana ia menghasilkan satu senarai indeks yang kurang berguna dipanggil katahenti (stoplist) atau kamus negatif.

Contoh senarai Kata henti :

Bahasa Malaysia dan Bahasa Inggeris

Kata Henti (Stop Word)

1.Jika katahenti dijadikan indeks sebutan:

• query yang mengandungi sebutan ini akan menyebabkan hampir semua item dalam pangkalan data akan dicapai walaupun ia tidak relevan.

• katahenti mengambil bahagian yang besar dalam sesebuah teks dokumen.

• penghindaran katahenti diperingkat awal pengindeksan akan mencepatkan proses, menjimatkan ruang storan, dan tidak mencacatkan keberkesanan capaian.


Perlaksanaan katahenti

Terdapat dua kaedah pengimplementasian bagi menapis senarai perkataan katahenti

• Lakukan pemeriksaan pada output penganalisa leksikal dan buang perkataan kata henti

• Buangkan kata henti sebagai sebahagian dalam analisis leksikal (cth Finite State Machine)


Pembangunan senarai katahenti Langkah utama dalam pendekatan berasaskan kekerapan

diaplikasikan pada pangkalan data teks (popovic 1991)• Semua perkataan dari teks korpus akan diambil (extracted)• Perkataan ini akan dipangkat berdasarkan kekerapan

keujudannya• Perkataan yang paling kerap merupakan perkataan

penghubung atau dikatakan sebagai perkataan fungsi dan dianggap sebagai perkataan kata henti

• Dari situ senarai kata henti akan dibentuk, Ia digunakan sebagai perkataan yang akan dibunag dalam proses analisis berikutnya.

• Perkataan akan diisih dalam susunan abjad • Perbandingan akan dibuat jika terdapat perkataan yang sama

ujud dakn ianya akan dibuang.

Implimentasipublic static java.util.Vector

GetStopWordsFromFile(Configuration config) Read in stop words from configuration file Parameters:

config - Configuratin object Returns:

a Vector of stop words

public ToStripStopWords()Boolean isStopWord()

Cantasan (Stemming)

Satu teknik untuk meningkat pencapaian di dalam capaian maklumat dimana terdapat kepelbagaian morfologi atau pembentukan kata pada sesuatu perkataan yang ingin dicapai.

Contoh: jika perkataan “cantasan” ialah sebahagian daripada query, maka pengguna juga berminat dengan variasi lain seperti “cantas” dan “pencantasan”.

Algorithma cantasan adalah satu prosedur berkomputer yang akan mengurangkan atau mencantas semua perkataan kepada kata akar yang sama .

Cantasan juga dilakukan untuk mengelakkan saiz fail indeks menjadi terlalu besar, kerana satu kata dasar (stem) boleh mewakil beberapa sebutan. Juga dapat meningkatkan keupayaan kepada sistem capaian dokumen.

Perkataan boleh dicantas semasa proses pengindeksan atau semasa proses capaian. • Kebaikan cantasan semasa proses pengindeksan adalah

dapat meningkatkan kecekapan dan kemampatan fail indeks. • Keburukannya ialah maklumat tentang perkataan yang penuh

akan hilang atau ruangan storan tambahan diperlukan untuk menyimpan kedua-duanya iaitu yang telah dicantas atau yang belum dicantas.

Cantasan (Stemming)

Conflation Methods

Manual Automatik (stemmers)

Jadual pencarian (table lookup) Kepelbagaian Terkemudian (successor variety) n-gram Pembuangan imbuhan (affix removal)

Penilaian Ketepatan (correctness) Kecekapan capaian (retrieval effectiveness)

Jadual pencarian (Lookup Table)

Menyimpan senarai indeks sebutan dalam satu jadual bersama dengan kata dasar (kata tercantas).

Sebutan Kata dasar (Sebutan tercantas)engineering engineer

engineered engineerengineer engineer

Sebutan daripada query boleh diindeks dan boleh dicantaskan melalui lookup table. Pencarian ini akan lebih pantas jika pokok-B (B-tree) atau jadual cincangan digunakan.

Kepelbagaian terkemudian (Successor Variety)

Definasi (successor variety of a string)bilangan huruf yang berbeza bagi satu huruf yang diikuti oleh huruf yang lain di dalam satu perkataan pada kandungan teks yang sama.

contohkandungan teks : able, axle, accident, ape, about

successor variety bagi apple1st: a diikuti oleh 4 (b, x, c, p)2nd: ap diikuti oleh (e)

Successor Variety

IdeaThe successor variety of substrings of a term will decrease as more characters are added until a segment boundary is reached, i.e., the successor variety will sharply increase.

ExampleTest word: READABLECorpus:ABLE, BEATABLE, FIXABLE, READ,

READABLE, READING, RED, ROPE, RIPE

Prefix Successor Variety LettersR 3 E, O, IRE 2 A, DREA 1 DREAD 3 A, I, SREADA 1 BREADAB 1 LREADABL 1 EREADABLE 1 blank

The successor variety stemming process

Tentukan kepelbagaian terkemudian bagi satu perkataan. Penggunaan kaedah berikut untuk penemberengan (segment)

perkataan • cutoff method• peak and plateau method• complete word method• entropy method

Pilih satu sebagai kaedah bagi cantasan

1. Cut off method• Sempadan ditentukan berdasar ketetapan nilai cutoff

(ditentukan oleh pembangun) bagi successor variety

• Jika nilai kecil : tersalah potong, jika nilai besar, nilai potong akan terlebih sasar

The successor variety stemming process : Penemberengan (segmentation)

2. peak and plateau method• Pisahkan perkataan bagi nilai successor variety bilamana

nilai pada huruf tertentu lebih besar dari huruf jujukan sebelum dan selepas

READ | ABLE

Contoh Test word: READABLECorpus:ABLE, BEATABLE, FIXABLE, READ,

READABLE, READING, RED, ROPE, RIPE




3. complete word method• Pemisahan dibuat jika tembereng (segment) adalah perkataan

yang lengkap dalam pangkalan data korpus (READ)

4. entropy methodTest word: READABLECorpus: ABLE, APE, BEATABLE, FIXABLE, READ,

READABLE, READING, READS, RED, ROPE, RIPE


Test word: READABLECorpus: ABLE, APE, BEATABLE, FIXABLE, READ,

READABLE, READING, READS, RED, ROPE, RIPE

i

ijz

aj i

iji

DD

DD

H

2

''

''

log

The successor variety stemming process : Penemberengan (segmentation)en

trop

y m

etho

d

Di mana merupakan perkataan yang bermula dengan jujukan dan ialah bilangan perkataan yang mempunyai successor j

iD

ijD

Guna nilai cutoff bagi menentukan sempadan

• Bagi i = 2, = RE, = 5• Bagi j = ‘A’, = 4• Bagi j = ‘D’, = 1

iD

ijD

ijD

54log

54

51log

51

ijH

22.008.014.0

Diagrampasangan huruf yang berjujukan

Shared diagram method (Adamson and Boreham, 1974)• Pengiraan dikira berdasarkan diantara pasangan term

where A: the number of unique diagrams in the first word, B: the number of unique diagrams in the second, C: the number of unique diagrams shared by A

and B

S CA B

2

Pencantas n-gram (n-gram Stemmer)

Pencantas n-gram (n-gram Stemmer)

Berdasarkan conflating method untuk sebutan yang dipanggil metod perkongsian digram. Digram ialah turutan pasangan abjad. Trigram dan n-gram boleh digunakan.

Contoh:statistics => st ta at ti is st ti is csdigram unik = at cs ic is st ta ti statistical => st ta at ti is st ti ic ca aldigram unik = al at ca ic is st ta ti

Pencantas n-gram (n-gram Stemmer) Contoh

statistics st ta at ti is st ti ic csunique diagrams at cs ic is st ta ti

statistical st ta at ti is st ti ic ca alunique diagrams al at ca ic is st ta ti

S CA B

2 2 67 8

0 80* .

Oleh “statistics” mengandungi 9 digram, yang 7 adalah unik; dan “statistical” mengandungi 10 digram, yang mana 8 adalah unik. Kedua-dua perkataan berkongsi 6 unik digram.

Pencantas Kata Imbuhan/Tambahan (Affix Removal Stemmer) Prosedur

Pencantas kata imbuhan, menyingkir kata awalan, kata apitan (BM) dan akhir daripada satu sebutan menghasilkan kata dasar atau kata tercantas.

Contoh: Bentuk jamak (BI)Jika perkataan diakhiri dengan “ies” tetapi bukan “eies” atau “aies”

maka “ies” “y” Jika perkataan diakhiri dengan “es” tetapi bukan “aes”, “ees”, atau “oes”

maka “es” “e” Jika perkataan diakhiri dengan “s”, tetapi bukan “us” atau “ss”

maka “s” NULL Kesamaran

Pencantas Kata Imbuhan/Tambahan (Affix Removal Stemmer) Dalam algoritma Porter hanya petua yang pertama yang sepadan

digunakan.

Kebanyakkan pencantas yang digunakan mencantas seberapa banyak perkataan yang boleh sehingga tiada abjad yang boleh dicantas lagi berdasarkan petua tertentu.

Walaubagaimanapun terdapat dua kemungkinan 1.Kurang cantasan2.Terlebih cantasan

Contoh perkataan “computability”, bila dicantas menghasilkan “comput” yang tidak akan sepadan dengan “compute”.

Pencantas Kata Imbuhan/Tambahan (bebas konteks vs sensitif konteks)

• Bebas konteks : membuang semua imbuhan berdasarkan kepada senarai petua imbuhan

• Sensitif konteks : mengambilkira huruf lain yang terlibat di dalam sesuatu perkataan. Contoh :

AxC AyC, e.g., ki ky

• Padanan separa (partial matching)Di dalam padanan separa, hanya n huruf permulaan pada perkataan yang telah dicantas digunakan untuk dibuat perbandingan

• Versi berbezaLovins, Slaton, Dawson, Porter, …

Stemming: Porter Algorithm Rule format:

• (condition on stem) suffix1 -> suffix2

• In case of conflict, prefer longest suffix match “Measure” of a word is m in:

• (C) (VC)m (V)• C = sequence of one or more consonants• V = sequence of one or more vowels• Examples:

• tree C(VC)0V • troubles C(VC)2

Stemming: Porter Algorithm Step 1a: remove plural suffixation

• SSES -> SS (caresses)• IES -> I (ponies)• SS -> SS (caress)• S -> (cats)

Step 1b: remove verbal inflection• (m>0) EED -> EE (agreed, feed)• (*v*) ED -> (plastered, bled)• (*v*) ING -> (motoring, sing)

Stemming: Porter Algorithm Step 1b: (contd. for -ed and -ing rules)

• AT -> ATE (conflated)• BL -> BLE (troubled)• IZ -> IZE (sized)• (*doubled c & ¬(*L v *S v *Z)) -> single c (hopping,

hissing, falling, fizzing)• (m=1 & *cvc) -> E (filing, failing, slowing)

Step 1c: Y and I• (*v*) Y -> I (happy, sky)

Stemming: Porter Algorithm Step 2: Peel one suffix off for multiple suffixes

• (m>0) ATIONAL -> ATE (relational)• (m>0) TIONAL -> TION (conditional, rational)• (m>0) ENCI -> ENCE (valenci)• (m>0) ANCI -> ANCE (hesitanci)• (m>0) IZER -> IZE (digitizer)• (m>0) ABLI -> ABLE (conformabli) - able (step 4)• …• (m>0) IZATION -> IZE (vietnamization)• (m>0) ATION -> ATE (predication)• …• (m>0) IVITI -> IVE (sensitiviti)

Stemming: Porter Algorithm Step 3

• (m>0) ICATE -> IC (triplicate)• (m>0) ATIVE -> (formative)• (m>0) ALIZE -> AL (formalize)• (m>0) ICITI -> IC (electriciti)• (m>0) ICAL -> IC (electrical, chemical)• (m>0) FUL -> (hopeful)• (m>0) NESS -> (goodness)

Stemming: Porter Algorithm Step 4: Delete last suffix

• (m>1) AL -> (revival) - revive, see step 5• (m>1) ANCE -> (allowance, dance)• (m>1) ENCE -> (inference, fence)• (m>1) ER -> (airliner, employer)• (m>1) IC -> (gyroscopic, electric)• (m>1) ABLE -> (adjustable, mov(e)able)• (m>1) IBLE -> (defensible,bible)• (m>1) ANT -> (irritant,ant)• (m>1) EMENT -> (replacement)• (m>1) MENT -> (adjustment)• …

Stemming: Porter Algorithm Step 5a: remove e

• (m>1) E -> (probate, rate)• (m>1 & ¬*cvc) E -> (cease)

Step 5b: ll reduction• (m>1 & *LL) -> L (controller, roll)

Stemming: Porter Algorithm Misses (understemming)

• Unaffected:• agreement (VC)1VCC - step 4 (m>1)• adhesion

• Irregular morphology:• drove, geese

Overstemming• relativity - step 2

Mis-stemming• wander C(VC)1VC

1. Vowels are a, e, i, o, u, and y if preceded by a consonant [C](VC)m[V

Measure Examples

m=0m=1m=2

TR, EE, TREE, Y, BYTROUBLE, OATS, TREES, IVYTROUBLES, PRIVATE, OATEN

2. *<X> - the stem ends with a given letter X

3. *v* - the stem contains a vowel

4. *d - the stem ends in a double consonant

5. *o - the stem ends with a consonant-vowel-consonant sequence, where the final consonant is not w, x, or y.

Porter’s Algorithm

Algorithma yang dibangunkan terbahagi kepada 2 bahagian1.Prosedur Asas Pemangkas

Periksa setiap term pada kamus katakar. Jika tidak ujud proses berikut dijalankan

i. Peraturan imbuhan awalan (awalan +)ii. Peraturan imbuhan awalan dan akhiran ( awalan + akhiran)iii.Peraturan imbuhan akhiran ( + akhiran )iv.Peraturan imbuhan apitan ( + apitan + )

Pangkasan lebih tepat dan katakar betul penggunaan pendekatan sensitive-konteks sebagai penambahan kekangan pada prosedur asas

1. Kekangan kuantitatif : minima panjang setelah dipangkas dikenalpasti Panjang 2 imbuhan awalan dan imbuhan akhiran Panjang 3 apitan dan cantuman imbuhan awalan dan

akhiran

FAtimah’s Algorithm

Peraturan pengekodan semula (2. Algorithma yang dibangunkan)

• Ejaan dan penyesuaian peraturan digunakan bagi meningkat ketepatan pemangkasan.

• Ia tidak dilakukan oleh peraturan morpologi tapi oleh aturcara sendiri.

• Contoh

Huruf mula pada katakar yang akan dihilangkan

Imbuhan awalan yang berkaitan Contoh

fkpst

mem, pemmeng, pengmem, pemmeny, peny

men, pen


Algorithma pemangkas Bahasa Melayu (Fatimah , 1995) Langkah 1 : Dapatkan perkataan / term yang berikutnya sehingga

perkataan yang terakhir Langkah 2 : Periksa perkataan berdasarkan kamus, jika ada maka

perkataan itu adalah katakar, pergi langkah 1. Langkah 3: Dapatkan peraturan yang selanjutnya, jika tiada

peraturan yang sesuai maka perkataan tersebut dianggap sebagai katakar, pergi langkah 1

Langkah 4 : Guna peraturan pada perkataan bagi mendapatkan perkataan terpangkas.

Langkah 5 : Periksa perkataan yang dipangkas dengan perkataan di dalam kamus, jika perlu, guna pengkodan semula bagi mendapatkan ejaan yang diterima. Periksa kamus semula.

Langkah 6 : Jika perkataan yang dipangkas ada di dalam kamus, maka perkataan yang dipangkas adalah katakar dan pergi ke langkah pertama, jika tidak pergi ke langkah ketiga.


analisis leksikal & katahenti (lexical analysis & stoplists)

Documents