NLP - Analisis Tingkat Kata
Dalam bab ini, kita akan memahami analisis tingkat dunia dalam Pemrosesan Bahasa Alami.
Ekspresi Reguler
Ekspresi reguler (RE) adalah bahasa untuk menentukan string pencarian teks. RE membantu kita untuk mencocokkan atau menemukan string atau kumpulan string lain, menggunakan sintaks khusus yang disimpan dalam pola. Ekspresi reguler digunakan untuk mencari teks di UNIX dan MS WORD dengan cara yang identik. Kami memiliki berbagai mesin pencari yang menggunakan sejumlah fitur RE.
Properti Ekspresi Reguler
Berikut ini adalah beberapa sifat penting RE -
Ahli matematika Amerika Stephen Cole Kleene meresmikan bahasa Ekspresi Reguler.
RE adalah rumus dalam bahasa khusus, yang dapat digunakan untuk menentukan kelas string sederhana, urutan simbol. Dengan kata lain, kita dapat mengatakan bahwa RE adalah notasi aljabar untuk mengkarakterisasi sekumpulan string.
Ekspresi reguler membutuhkan dua hal, satu adalah pola yang ingin kita cari dan lainnya adalah kumpulan teks yang perlu kita cari.
Secara matematis, Ekspresi Reguler dapat didefinisikan sebagai berikut -
ε adalah Ekspresi Reguler, yang menunjukkan bahwa bahasa tersebut memiliki string kosong.
φ adalah Ekspresi Reguler yang menunjukkan bahwa ini adalah bahasa kosong.
Jika X dan Y adalah Ekspresi Reguler, lalu
X, Y
X.Y(Concatenation of XY)
X+Y (Union of X and Y)
X*, Y* (Kleen Closure of X and Y)
juga ekspresi reguler.
Jika sebuah string diturunkan dari aturan di atas maka itu juga akan menjadi ekspresi reguler.
Contoh Ekspresi Reguler
Tabel berikut menunjukkan beberapa contoh Ekspresi Reguler -
| Ekspresi Reguler | Set Reguler |
|---|---|
| (0 + 10 *) | {0, 1, 10, 100, 1000, 10000,…} |
| (0 * 10 *) | {1, 01, 10, 010, 0010,…} |
| (0 + ε) (1 + ε) | {ε, 0, 1, 01} |
| (a + b) * | Ini akan menjadi himpunan string a dan b dengan panjang berapa pun yang juga termasuk string nol yaitu {ε, a, b, aa, ab, bb, ba, aaa …….} |
| (a + b) * abb | Ini akan menjadi kumpulan string a dan b yang diakhiri dengan string abb yaitu {abb, aabb, babb, aaabb, ababb, ………… ..} |
| (11) * | Ini akan ditetapkan terdiri dari bilangan genap 1 yang juga menyertakan string kosong yaitu {ε, 11, 1111, 111111, ……….} |
| (aa) * (bb) * b | Ini akan menjadi kumpulan string yang terdiri dari bilangan genap a diikuti dengan bilangan ganjil yaitu {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..} |
| (aa + ab + ba + bb) * | Ini akan menjadi string a dan b dengan panjang genap yang dapat diperoleh dengan menggabungkan kombinasi apapun dari string aa, ab, ba dan bb termasuk null yaitu {aa, ab, ba, bb, aaab, aaba, …………. .} |
Set Reguler & Properti Mereka
Ini dapat didefinisikan sebagai himpunan yang mewakili nilai ekspresi reguler dan terdiri dari properti tertentu.
Properti set reguler
Jika kita melakukan penyatuan dua set reguler maka set yang dihasilkan juga akan menjadi regula.
Jika kita melakukan perpotongan dua himpunan biasa maka himpunan yang dihasilkan juga akan beraturan.
Jika kita melakukan komplemen pada set reguler, maka set yang dihasilkan juga akan biasa.
Jika kita melakukan selisih dua set biasa, maka set yang dihasilkan juga akan biasa.
Jika kita melakukan pembalikan himpunan biasa, maka himpunan yang dihasilkan juga akan beraturan.
Jika kita mengambil closure dari set biasa, maka set yang dihasilkan juga akan jadi regular.
Jika kita melakukan penggabungan dua set reguler, maka set yang dihasilkan juga akan menjadi reguler.
Automata Negara Hingga
Istilah automata, berasal dari kata Yunani "αὐτόματα" yang berarti "bertindak sendiri", adalah bentuk jamak dari otomat yang dapat didefinisikan sebagai perangkat komputasi gerak sendiri abstrak yang mengikuti urutan operasi yang telah ditentukan secara otomatis.
Sebuah robot yang memiliki jumlah status terbatas disebut Finite Automaton (FA) atau Finite State automata (FSA).
Secara matematis, sebuah robot dapat diwakili oleh 5-tupel (Q, Σ, δ, q0, F), di mana -
Q adalah himpunan keadaan yang terbatas.
Σ adalah seperangkat simbol yang terbatas, yang disebut alfabet robot.
δ adalah fungsi transisi
q0 adalah status awal dari mana input diproses (q0 ∈ Q).
F adalah himpunan keadaan akhir dari Q (F ⊆ Q).
Hubungan antara Finite Automata, Tata Bahasa Reguler dan Ekspresi Reguler
Poin berikut akan memberi kita pandangan yang jelas tentang hubungan antara automata hingga, tata bahasa reguler, dan ekspresi reguler -
Seperti yang kita ketahui bahwa automata keadaan hingga adalah fondasi teoritis dari pekerjaan komputasi dan ekspresi reguler adalah salah satu cara untuk menggambarkannya.
Kita dapat mengatakan bahwa ekspresi reguler apa pun dapat diterapkan sebagai FSA dan FSA apa pun dapat dijelaskan dengan ekspresi reguler.
Di sisi lain, ekspresi reguler adalah cara untuk mencirikan jenis bahasa yang disebut bahasa reguler. Oleh karena itu, kami dapat mengatakan bahwa bahasa reguler dapat dijelaskan dengan bantuan FSA dan ekspresi reguler.
Tata bahasa reguler, tata bahasa formal yang dapat berupa reguler kanan atau reguler kiri, adalah cara lain untuk mengkarakterisasi bahasa reguler.
Diagram berikut menunjukkan bahwa automata hingga, ekspresi reguler, dan tata bahasa reguler adalah cara yang setara untuk mendeskripsikan bahasa reguler.
Jenis Otomatisasi Keadaan Hingga (FSA)
Otomatisasi keadaan hingga terdiri dari dua jenis. Mari kita lihat apa saja tipenya.
Otomatisasi Hingga Deterministik (DFA)
Ini dapat didefinisikan sebagai jenis otomatisasi terbatas dimana, untuk setiap simbol masukan kita dapat menentukan keadaan mesin akan bergerak. Ini memiliki jumlah keadaan terbatas itulah sebabnya mesin disebut Deterministic Finite Automaton (DFA).
Secara matematis, DFA dapat diwakili oleh 5-tupel (Q, Σ, δ, q0, F), di mana -
Q adalah himpunan keadaan yang terbatas.
Σ adalah seperangkat simbol yang terbatas, yang disebut alfabet robot.
δ adalah fungsi transisi di mana δ: Q × Σ → Q.
q0 adalah status awal dari mana input diproses (q0 ∈ Q).
F adalah himpunan keadaan akhir dari Q (F ⊆ Q).
Sedangkan secara grafis, DFA dapat diwakili oleh diagraph yang disebut diagram keadaan dimana -
Negara bagian diwakili oleh vertices.
Transisi ditunjukkan dengan label arcs.
Keadaan awal diwakili oleh empty incoming arc.
Keadaan akhir diwakili oleh double circle.
Contoh DFA
Misalkan DFA menjadi
Q = {a, b, c},
Σ = {0, 1},
q 0 = {a},
F = {c},
Fungsi transisi δ ditunjukkan pada tabel sebagai berikut -
| Kondisi saat ini | Status Berikutnya untuk Input 0 | Status Berikutnya untuk Input 1 |
|---|---|---|
| SEBUAH | Sebuah | B |
| B | b | SEBUAH |
| C | c | C |
Representasi grafis dari DFA ini adalah sebagai berikut -
Otomatisasi Hingga Non-deterministik (NDFA)
Ini dapat didefinisikan sebagai jenis otomatisasi terbatas di mana untuk setiap simbol input kita tidak dapat menentukan status ke mana mesin akan bergerak, yaitu mesin dapat berpindah ke kombinasi status apa pun. Ini memiliki jumlah status yang terbatas, itulah sebabnya mesin ini disebut Non-deterministic Finite Automation (NDFA).
Secara matematis, NDFA dapat direpresentasikan dengan 5-tuple (Q, Σ, δ, q0, F), dimana -
Q adalah himpunan keadaan yang terbatas.
Σ adalah seperangkat simbol yang terbatas, yang disebut alfabet robot.
δ: -adalah fungsi transisi di mana δ: Q × Σ → 2 Q .
q0: -adalah keadaan awal dari mana setiap input diproses (q0 ∈ Q).
F: -adalah himpunan keadaan akhir / keadaan Q (F ⊆ Q).
Sedangkan secara grafis (sama seperti DFA), NDFA dapat direpresentasikan oleh diagraph yang disebut state diagrams dimana -
Negara bagian diwakili oleh vertices.
Transisi ditunjukkan dengan label arcs.
Keadaan awal diwakili oleh empty incoming arc.
Keadaan akhir diwakili oleh ganda circle.
Contoh NDFA
Misalkan NDFA menjadi
Q = {a, b, c},
Σ = {0, 1},
q 0 = {a},
F = {c},
Fungsi transisi δ ditunjukkan pada tabel sebagai berikut -
| Kondisi saat ini | Status Berikutnya untuk Input 0 | Status Berikutnya untuk Input 1 |
|---|---|---|
| SEBUAH | a, b | B |
| B | C | a, c |
| C | b, c | C |
Representasi grafis NDFA ini adalah sebagai berikut -
Penguraian Morfologis
Istilah penguraian morfologis berkaitan dengan penguraian morfem. Kita dapat mendefinisikan penguraian morfologis sebagai masalah mengenali bahwa sebuah kata dipecah menjadi unit-unit bermakna yang lebih kecil yang disebut morfem yang menghasilkan semacam struktur linguistik untuknya. Misalnya, kita bisa membagi kata rubah menjadi dua, rubah dan -es . Kita dapat melihat bahwa kata rubah , terdiri dari dua morfem, satu adalah rubah dan lainnya adalah -es .
Dalam arti lain, kita dapat mengatakan bahwa morfologi adalah studi tentang -
Pembentukan kata-kata.
Asal kata.
Bentuk tata bahasa dari kata-kata.
Penggunaan prefiks dan sufiks dalam pembentukan kata.
Bagaimana part-of-speech (PoS) suatu bahasa terbentuk.
Jenis Morfem
Morfem, unit pembawa makna terkecil, dapat dibagi menjadi dua jenis -
Stems
Susunan kata
Batang
Ini adalah unit makna inti dari sebuah kata. Kita juga dapat mengatakan bahwa itu adalah akar kata. Misalnya, dalam kata rubah, batangnya adalah rubah.
Affixes- Seperti namanya, kata tersebut menambahkan beberapa arti dan fungsi tata bahasa tambahan pada kata. Misalnya, pada kata foxes, imbuhannya adalah - es.
Selanjutnya, imbuhan juga dapat dibagi menjadi empat jenis berikut -
Prefixes- Seperti namanya, awalan mendahului batang. Misalnya, pada kata unbuckle, un adalah awalannya.
Suffixes- Seperti namanya, akhiran mengikuti batang. Misalnya, dalam kata kucing, -s adalah sufiks.
Infixes- Sesuai namanya, infiks disisipkan di dalam batang. Misalnya, kata cupful, dapat dijadikan jamak sebagai cupful dengan menggunakan -s sebagai infiks.
Circumfixes- Mereka mendahului dan mengikuti batangnya. Ada sangat sedikit contoh pengunaan dalam bahasa Inggris. Contoh yang sangat umum adalah 'A-ing' di mana kita dapat menggunakan -A sebelum dan -ing mengikuti batang.
Susunan kata
Urutan kata akan ditentukan dengan penguraian morfologis. Sekarang mari kita lihat persyaratan untuk membangun parser morfologi -
Kamus
Persyaratan pertama untuk membangun pengurai morfologi adalah leksikon, yang mencakup daftar batang dan imbuhan beserta informasi dasar tentangnya. Misalnya, informasi seperti apakah stemnya adalah nomina stem atau verba stem, dll.
Morfotaktik
Ini pada dasarnya adalah model pemesanan morfem. Dalam pengertian lain, model menjelaskan kelas morfem mana yang dapat mengikuti kelas morfem lain di dalam sebuah kata. Misalnya, fakta morfotaksisnya adalah bahwa morfem jamak bahasa Inggris selalu mengikuti kata benda, bukan sebelumnya.
Aturan ortografi
Aturan ejaan ini digunakan untuk memodelkan perubahan yang terjadi dalam sebuah kata. Misalnya, aturan untuk mengubah y menjadi ie pada kata seperti city + s = cities bukan citys.