Ekspresi Reguler dan Metode Keadaan-Terbatas

Teknik praktis yang dibangun di atas bahasa reguler — pencocokan pola dengan ekspresi reguler dan pemetaan string-ke-string dengan transduser keadaan-terbatas — yang menangani tokenisasi, normalisasi, dan analisis morfologi secara efisien.

Definition

Metode keadaan-terbatas adalah teknik pemrosesan bahasa di mana pola dan pemetaan diekspresikan sebagai ekspresi reguler atau automata dan transduser keadaan-terbatas, menjamin pengenalan waktu linear yang efisien.

Scope

Mencakup ekspresi reguler sebagai bahasa pola di atas string, automata keadaan-terbatas dan transduser sebagai realisasi komputasionalnya, serta penerapannya pada normalisasi teks, tokenisasi, ejaan, dan morfologi komputasional. Ini mencakup metode keadaan-terbatas berbobot yang digunakan dalam pemrosesan ucapan dan pemrosesan dangkal. Teori fonologi penuh dan penguraian sintaksis mendalam berada di luar cakupan.

Core questions

• Bagaimana ekspresi reguler dapat menentukan dan mengekstrak pola tekstual secara tepat?
• Bagaimana transduser keadaan-terbatas memetakan bentuk permukaan ke analisis leksikal, seperti dalam morfologi?
• Mengapa metode keadaan-terbatas lebih disukai untuk tokenisasi dan normalisasi?

Key concepts

• ekspresi reguler
• transduser keadaan-terbatas
• tokenisasi
• normalisasi teks
• analisis morfologi
• morfologi dua tingkat
• automata berbobot
• jarak edit

Key theories

Model reguler morfologi dan fonologi

Hasil bahwa aturan penulisan ulang fonologi dan alternasi morfologi dapat dikompilasi menjadi transduser keadaan-terbatas, menjadikan analisis dan generasi sebagai kerangka kerja tunggal yang efisien.

Ekuivalensi ekspresi reguler dan automata terbatas

Ekspresi reguler, tata bahasa reguler, dan automata keadaan-terbatas semuanya menggambarkan secara tepat bahasa reguler, sehingga pola deklaratif dapat dikompilasi menjadi pengenal yang efisien.

History

Ekspresi reguler masuk ke komputasi dari karya Kleene dan menjadi umum dalam alat teks. Pada tahun 1980-an, morfologi dua tingkat Koskenniemi dan kompilasi aturan fonologi Kaplan dan Kay ke dalam transduser menetapkan teknologi keadaan-terbatas sebagai tulang punggung pemrosesan morfologi, sebuah pendekatan yang dikonsolidasikan dalam buku pegangan Beesley dan Karttunen.

Debates

Sejauh mana metode keadaan-terbatas dapat diskalakan?

Teknik keadaan-terbatas sangat efisien tetapi terbatas pada fenomena reguler; perdebatan menyangkut tugas pemrosesan bahasa mana yang paling baik dilayani olehnya dibandingkan model statistik atau saraf yang lebih kaya.

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

Mengapa menggunakan transduser keadaan-terbatas daripada hanya tabel pencarian untuk morfologi?

Transduser secara ringkas mengkodekan alternasi sistematis dan dapat menganalisis atau menghasilkan bentuk kata yang belum pernah dilihatnya, sedangkan tabel hanya menyimpan bentuk yang secara eksplisit tercantum di dalamnya.