NATURAL LANGUAGE PROCESSING

NATURAL LANGUAGE PROCESSINGPendahuluan

Perkembangan teknologi sudah mencapai tahap interaksi dan komunikasi manusia dan mesin.

Dasar Teori

Riset ini dilaksanakan dengan tujuan untuk menerjemahkan kalimat dalam bahasa inggris ke dalam struktur kalimat berbahasa Indonesia, jadi yang ditekankan dalam riset ini lebih banyak pada struktur kalimatnya dan bukan hanya pada sintaks kalimat saja. Dalam riset ini kamu memakai beberapa referensi sebagai dasar percobaannya. Referensi tersebut memuat komponen-komponen yang digunakan dalam riset, antara lain : Metode parsing kalimat.

Membuat link grammar.

Algoritma parsing dan link grammar.

Seperti yang telah diketahui bahwa susunan kalimat bahasa inggris sedikit berbeda dengan bahasa Indonesia, maka dari itu dengan riset ini kami mencoba mengatasi permasalahan tersebut. Software yang kami buat ditulis dalam bahasa pemrograman C# dengan compiler yaitu Visual Studio .NET 2003.

Langkah Kerja

Dalam riset ini yang menjadi input adalah kalimat dalam bahasa inggris yang kemudian akan diolah dengan mekanisme yang telah didefinisikan dan akan menghasilkan keluaran berupa kalimat dalam bahasa Indonesia yang memakai kaidah tatacara penulisan yang benar.

Software ini menggunakan algoritma parsing yang oleh pengarangnya disebut Robust Parsing Algorithm. Algoritma ini digunakan untuk mencari hubungan pola antar kata dalam kalimat.

Langkah-langkah kerja :

1. Memberi index pada tiap kata.

2. Mengenali jenis dan kategori tiap kata. Misalkan, (word+Ving,+V1,V2,V3,+to,etc)

3. Mencocokkan dengan pola bahasa inggris.

4. pola bahasa inggris di translate ke dalam pola bahasa Indonesia.

5. terjemahkan ke bahasa Indonesia.

Jadi, akhirnya

Setiap kata memiliki disjunct, yang didalamnya terdapat konektor-konektor kata.

Kata yang memiliki konektor sejenis(sama) ( linking

((left)(right)) ((left)(right)) ((left)(right))

Konektor : right ( left

Left ( right Disjunct dikelompokkan menurut jenis katanya.

Seperti : noun, verb, adjective, adverb , dll

Mapping dari hubungan konektor ke pola bahasa inggris

{ = optional

_____________________________

S ( S- = subject

S+ = predikat Nominative pronoun (kata ganti orang) : (he she it)

GI ( GI+ = modaling

GI- = V-ing

O ( Accousative pronoun (kata ganti objek) : O- not S+ (him me)

O+ = transitif verb

O- = noun

_____________________________

I ( I+ = keterangan V (modals)

I- = V

T ( kata didahului have

T+ = have

T- = V3V ( kalimat pasif, identifikasi dengan be, been

V+ = be, been

V- = past participle (have done)SI ( S P dibalik

SI- = S

SI+ = PD ( determiner

Singular noun : wajib

Plural noun : optional

D - = noun

D + = determiner

TO ( to (complex verb (CV))

TO+ = verb, followed by to inf

TO- dan I+ => to

TH ( CV memakai that

CL ( CV memakai clause

:: TH & CL sangat berkaitan.

TH+ = verb followed by that + clause

TH- = that

CL+ = that or verb followed by clause

CL- = complete clause

R ( CV memakai question

R+ = verb followed by question

R- = question word

AI ( verb memakai adjective

AI + = verb foolowed by adjective

AI - = adjective word

A ( kata sifat (adjective), hubungannya dengan noun

A+ = adjective

@A- = nouns

J ( preposisi, hubungannya dengan noun

J+ = preposition

J- = nouns

EV ( preposisi, hubungannya dengan verb (biasanya disertai klausa)

@EV+ = verb

EV- = preposition

EX ( hampir sama dengan EV, tetapi posisinnya dibalik

EX+ = adverb

@EX- = verb

M ( disebelah kirinya ada preposisi (noun)

@M+ = nouns

Mp - = preposition

__________________________________

CL ( konjungsi dengan subject suatu klausa.

CL+ = conjunction (because, while, before, etc)

CL- = nouns and pronoun

CO ( pada CL tetapi terhubung pada subject kalimat inti.

CO + = conjunction

CO - = nouns (subject)

X ( konjungsi dengan koma

X+ = conjunction

X - = comma

B ( relative clause, noun menjadi object. Menghubungkan noun (Bx) dengan transitive verb.

Disjunct dipake untuk membuat pola dan parsing.

Cara menuliskan disjunct :

D = (A- or ( )) & D- & (B+ or ( )) & (O- or S+)

( A-D- B+ O- = ((A,D,O) (B))

A-D- B+ S+ = ((A,D) (S,B))

A-D- ( ) O- = ((A,D,O) ( ))

A-D- ( ) S+ = ((A,D) (S))

( ) D- B+ O- = ((D,O) (B))

( ) D- B+ S+ = ((D) (S,B))

( ) D- ( ) O- = ((D,O) ( ))

( ) D- ( ) S+ = ((D) (S))

( jumlah total 8 disjunct

contoh dalam kalimat :

John chased the dog angrily.

John

J- (J) ( )

O- (O) ( )

S+ CO- CL-=> (CL,CO) (S)

S+ SI-

(SI) (S)

S+

( ) (S)

chased

@EX- S- O+ @EV+

(S,@EX) (O,@EV)

@EX- T- O+ @EV+ =>(T,@EX) (O,@EV)

@EX- V- @EV+

(V,@EX) (@EV)

@EX- MV- @EV+

(MV,@EX) (@EV)

the

determiner D+

( ) (D+)

dog

@A+ Ds- @M- Ss+

(@M,Ds) (@A,Ss)

@A+ Ds- @M- SIis-

=>(SIs,@M,Ds) (@A)

@A+ Ds- @M- O-

(O,@M,Ds) (@A)

@A+ Ds- @M- J-

(J,@M,Ds) (@A)

angrily

(EV) ( )

(EX) ( )

Implementasi Pruning

Pruning adalah mekanisme untuk mengeliminasi konektor yang tidak diperlukan. Dengan mekanisme pruning maka dari disjunct-disjunct tersebut dipilih disjunct mana yang dapat dipakai dari kata tersebut dengan identifier berupa status. Disjunt adalah sekumpulan konektor yang dipakai dalam suatu pola kalimat untuk menggambarkan relasi antar kata.

A. Pruning

B. Power Pruning

Power pruning adalah proses penyeleksian disjunct (bukan hanya konektor) dari kata-kata yang akan diterjemahkan.

Langkah langkah :

a. mencacah sampai tidak ada perubahan status.

b. mencacah 2 x , ke kanan dan ke kiri.

c. mencacah disjunct-disjunct tiap kata yang mempunyai match.

d. mencacah konektor dalam 1 disjunct.

e. mencacah kata-kata tetangga/sebelahnya sampai match-nya ditemukan, sementara itu posisi match tsb dicatat (indexing).

f. mencacah semua konektor di kata tetangga yang sedang di-test.ALGORITMA PARSING

Setelah proses pruning kemudian di-parsing untuk mencari kecocokan atau linkage kata dalam kalimat.

Seharusnya bagian ini adalah gambar diagram algoritma parsing konektor.

Linkage :

John

chased

the

dog

angrily

(S) (S,@EX) (O,@EV) (D) (O,@M,Ds) (@A) (EV) ( )

Natural Language Processing

Proses yang dilakukan oleh software

Flowchart

Referensi :

[1] D. D. K. Sleator and D. Temperley. Parsing English with a link grammar. Technical Report CMU-CS-91-196, School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburg, PA 15213, 1991.

[2]J. Lafferty, D. D. K. Sleator and D. Temperley. Grammatical Trigrams : A Probabilistic Model of Link Grammar. Technical Report CMU-CS-92-181, School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburg, PA 15213, 1992.

[3]D. Grinberg, J. Lafferty and D. D. K. Sleator. A Robust Parsing Algorithm for link grammar. Technical Report CMU-CS-95-125, School of Computer Science, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburg, PA 15213, 1995.

Ya

Ya

Tidak

Tidak

Ambil 1 set disjunct dari 1 kata

( matrik 2 dimensi)

Ambil 1 konektor

( variable ) = conn

+ ?

Ambil sebelah kiri

Ambil sebelah kanan

Index out of bound

Index out of bound

Index cocok

Index cocok

Catat posisi

Catat posisi

Coret status

Ya

Ya

Habis?

Selesai

Habis?

Ya

Ya

Start

Inisialisasi matrik 3 dimensi

( input )

Ambil 1 disjunct

( array )

Pruning

Parsing

Mapping

pola / struktur

Cross mapping

Translate

Input Kalimat

1

L

R

5

4

3

2

W3

Match?

If yes

Then end

Match?

4

3

2

1

L

R

W3

Match?

If yes

Then end

Match?

2

3

4

L

R

W1

Match?

end

Match?

end

Match?

If yes

Then end

4

3

2

1

L

R

W3

Match?

Match?

end

Match?

end

1

2

3

L

R

W1

1

2

3

L

R

W2

Match?

end

Match?

end

3

4

5

L

R

W2

Match?

end

Match?

end

3

4

5

W1

R

L

Match?

If yes

then end

1

2

3

4

5

R

L

W1

Match?

If yes

then end

Match?

2

Match?

5

4

3

W1

R

L

Match?

end

Match?

end

R

W1

5

4

3

2

L

Match?

end

4

L

R

W1

Match?

end

Match?

end

2

3

Match?

Match?

1

L

R

5

4

3

2

W2

D

O

EV

S

Kata 4

Kata 3

Kata 2

Kata 1

Disjunct 3

Disjunct 2

Disjunct 1

R ( L

L ( R

Kata 4

Kata 3

Kata 2

Kata 1

Konektor

kanan

Konektor

kiri

..

..

..

Konektor

kanan

Konektor

kiri

..

..

..

Konektor

kanan

Konektor

kiri

..

..

..

Konektor

kanan

Konektor

kiri

..

..

..

Atribut status matriks disjunct.

(Ya dan tidak)

John

chased

the

dog

angrily

4

5

3

2

1