Memulihkan hutan parse dari pengurai Earley?

Saya baru-baru ini membaca tentang parser Earley dan berpikir itu adalah salah satu algoritma paling elegan yang pernah saya lihat sampai saat ini. Namun, algoritma dalam pengertian tradisionalnya adalah sebuah pengenal dan bukan pengurai, yang berarti bahwa ia dapat mendeteksi apakah suatu string cocok dengan CFG tertentu tetapi tidak menghasilkan pohon pengurai untuknya. Pertanyaan saya adalah bagaimana memulihkan bukan pohon parse , melainkan hutan parse dari semua parse yang mungkin dari string input yang diberikan.

Dalam "Teknik Parsing: Panduan Praktis" Grune dan Jacob, mereka mengilustrasikan suatu algoritma yang dapat digunakan untuk memulihkan hutan parse dari hasil pengenal Earley, tetapi didasarkan pada metode parsing Unger, yang runtime-nya adalah O (n ^{k + 1} ), di mana k adalah panjang dari produksi terpanjang dalam tata bahasa. Ini berarti bahwa runtime bukan polinomial dalam ukuran tata bahasa. Selain itu, makalah asli Earley tentang algoritme, yang menyarankan algoritme untuk memulihkan hutan parse, tidak benar (lihat, misalnya, halaman 762 artikel ini oleh Tomita), meskipun banyak sumber masih mengutipnya sebagai cara yang tepat untuk memulihkan hutan parse .

Pertanyaan saya adalah apakah mungkin, dalam waktu polinomial, untuk memulihkan hutan parse untuk string input yang diberikan. Saya telah menemukan makalah di sini yang menyediakan algoritme untuk menghasilkan representasi hutan parse ukuran kubik untuk parse apa pun menggunakan simulasi PDA, jadi ini sepertinya mungkin, tetapi saya belum menemukan cara untuk melakukan ini. Idealnya, saya ingin melakukan ini tanpa mengubah tata bahasa input ke CNF (yang memang akan menyelesaikan masalah), karena hutan parse yang dihasilkan akan sangat berantakan.

Terima kasih atas bantuan yang bisa Anda tawarkan!

Melakukan hal itu tentu saja tergantung pada representasi yang tepat untuk "hutan penuh" yang mewakili semua pohon parse untuk kalimat tertentu.

Saya pikir tempat yang ingin Anda cari adalah tesis Joshua Goodman (parsing inside out, Harvard, 1999). Pada dasarnya, idenya adalah Anda dapat mendefinisikan algoritma parsing di bawah semiring tertentu. Bergantung pada semiring, Anda akan dapat menghitung semua jenis jumlah dan struktur daripada pohon parse telanjang (sebagai pengenal atau sebagai pengurai). Satu semiring yang bisa Anda definisikan (yang dilakukan Goodman dalam tesisnya) adalah semiring di mana nilainya adalah kumpulan parsing. Saat Anda akhirnya menyelesaikan parsing kalimat, Anda akan mendapatkan semua pohon parse di node parse utama.

Sekali lagi, Anda harus berhati-hati agar memungkinkan melalui representasi yang tepat.

Ada kertas yang menjelaskan cara melakukannya:

Penguraian gaya SPPF dari Earley Recognisers oleh Elisabeth Scott

Ini menjelaskan cara membangun hutan parse binarized dalam waktu kubik.

Anda tidak pernah membutuhkan CNF. Ini memiliki kelemahan mengubah struktur tata bahasa. Tetapi Anda perlu memperkenalkan non-terminal perantara sehingga tidak ada sisi kanan lebih dari 2 (2-bentuk) karena panjang RHS menentukan kompleksitas. Upaya terbaik untuk menjelaskan hal itu secara intuitif adalah, jika ingatanku, sebuah makalah oleh Beau Shiel, "Observations on Context Free Parsing", yang diterbitkan pada tahun 1976 dalam konferensi lingistik komputasi. Algoritma Earley menggunakan 2-form secara implisit. Itu hanya tersembunyi di dalam algoritma. Mengenai pemulihan dan penanganan hutan parse, Anda harus melihat web di "parsing intersection forest". Ini sebenarnya sangat mudah. Banyak makalah di web, jika Anda mendapatkan (dari kutipan atau daftar isi) judul atau penulis untuk mencarinya secara langsung.

Sebenarnya, Anda bisa melakukan lebih banyak daripada CF, dan masih mendapatkan hutan parse dalam waktu polinomial. Pertanyaannya adalah, kadang-kadang: apa yang dapat Anda lakukan dengannya begitu Anda memilikinya?

Salah satu tujuan dari artikel terakhir yang Anda sebutkan adalah untuk menunjukkan bahwa algoritma yang kompleks (seperti GLR) tidak harus membeli apa pun dalam waktu atau ruang, dan dapat mengubah hutan parse Anda.

Satu komentar tentang mengajar. Saya pikir Earley, seminal seperti itu, terlalu rumit untuk mengajar, dan dapat digantikan oleh algoritma yang lebih sederhana dengan konten pendidikan yang pada dasarnya sama. Mengajar adalah tentang konsep atau teknologi. Dalam algoritma Earley, konsep-konsep penting disembunyikan dalam kerumitan detail, dan dari sudut pandang teknologi itu sudah ketinggalan zaman. Itu adalah karya yang bagus, tetapi itu tidak berarti itu adalah pendekatan pedagogis terbaik.

Mungkin ada lebih banyak informasi dalam literatur linguistik komputasi daripada di saluran ilmu komputer yang biasa. Saya tidak memiliki buku Ceriel-Grune-Jacobs, tetapi saya akan terkejut jika mereka tidak memiliki semua referensi yang tepat (walaupun saya tidak yakin tentang kriteria seleksi mereka).

Lengkapi setelah permintaan dalam komentar (7 Juli 2013)

Pelengkap ini memperhatikan keberadaan algoritma yang lebih sederhana daripada Earley.

Seperti yang saya katakan, mencari web di "parsing forest persimpangan" harus dengan cepat memberi Anda referensi, dari mana Anda dapat menggali lebih jauh.

Gagasan dasarnya adalah bahwa semua jalur yang diurai dengan konstruksi hutan bersama tidak lain adalah konstruksi persimpangan lama Bar Hillel, Perles dan Shamir untuk bahasa reguler dan bahasa bebas konteks, menggunakan otomat terbatas dan tata bahasa bebas konteks. Dengan tata bahasa CF, Anda menerapkan konstruksi ke robot sepele yang hanya mengenali string input Anda. Itu semuanya. Hutan bersama hanyalah tata bahasa untuk persimpangan. Ini terkait dengan tata bahasa asli melalui homomorfisme, hanya mengenali string yang diberikan, tetapi dengan semua pohon parse tata bahasa asli hingga homomorfisma itu (yaitu, penggantian nama sederhana dari non-terminal).

Tata bahasa yang dihasilkan mengandung banyak hal yang tidak berguna, non-terminal dan aturan, yang tidak dapat dijangkau dari aksioma (tidak dapat ditemukan dalam string yang berasal dari simbol awal) atau yang tidak produktif (tidak dapat diturunkan ke terminal tali).

Kemudian, Anda harus membersihkannya dengan kuas yang baik di bagian akhir (mungkin panjang tetapi sederhana secara algoritmik), atau Anda dapat mencoba meningkatkan konstruksinya sehingga bulu yang tidak terlalu berguna untuk disikat pada akhirnya.

Sebagai contoh, konstruksi CYK persis seperti itu, tetapi diatur sedemikian rupa sehingga semua aturan dan non-terminal yang dibuat produktif, meskipun banyak yang tidak dapat dijangkau. Ini diharapkan dari teknik bottom-up.

Teknik top-down (seperti yang berbasis LR (k)) akan menghindari aturan yang tidak terjangkau dan non-terminal, tetapi akan membuat yang tidak produktif.

Banyak menyikat sebenarnya dapat dicapai dengan penggunaan pointer yang memadai, saya pikir, tapi saya belum melihat ini sejak lama.

Semua algoritma yang ada benar-benar mengikuti dasarnya model itu. Jadi itu benar-benar inti masalah, dan itu sangat sederhana. Lalu mengapa menguburnya dalam kompleksitas?

Banyak "optimisasi" diusulkan dalam literatur yang sering didasarkan pada keluarga LR (k), LL (k) konstruksi parser, mungkin dengan beberapa faktor statis dari konstruksi ini (Earley tidak memiliki anjak statis). Ini sebenarnya bisa diterapkan pada semua teknik yang dikenal, termasuk parser yang diutamakan lama. Saya menempatkan "optimisasi" di antara tanda kutip karena biasanya tidak jelas apa yang Anda optimalkan, atau bahkan apakah Anda benar-benar mengoptimalkannya, atau apakah manfaat peningkatannya sebanding dengan kompleksitas tambahan parser Anda. Anda akan menemukan sedikit data objektif, formal atau eksperimental, pada ini (ada beberapa), tetapi banyak lagi klaim. Saya tidak mengatakan bahwa tidak ada yang menarik. Ada beberapa ide cerdas.

Sekarang, setelah Anda tahu ide dasarnya, "optimisasi" atau perbaikan sering dapat diperkenalkan secara statis (mungkin secara bertahap) dengan membuat otomat push-down dari tata bahasa, mengikuti jenis teknik konstruksi parser yang Anda minati, dan kemudian menerapkannya. konstruksi lintas-produk untuk persimpangan dengan robot itu (hampir sama dengan melakukannya pada tata bahasa) atau ke tata bahasa yang berasal dari robot itu.

Kemudian Anda bisa memperkenalkan lonceng dan peluit, tetapi itu kebanyakan detail teknologi.

Philosophiæ Naturalis Principia Mathematica dari Isaac Newton dikabarkan merupakan bagian besar fisika dan matematika. Saya tidak berpikir itu ada dalam daftar bacaan banyak siswa. Semua hal lain dianggap sama, saya tidak berpikir itu sangat berguna untuk mengajarkan algoritma Earley, meskipun itu adalah bagian sejarah yang penting. Siswa sudah cukup belajar. Dengan risiko ditembak jatuh oleh banyak orang, saya pikir hal yang sama juga terjadi pada kertas Knuth LR (k). Ini adalah bagian yang luar biasa dari analisis teoretis, dan mungkin bacaan penting bagi ahli teori. Saya sangat ragu bahwa itu sangat penting untuk membangun parser mengingat keadaan teknologi saat ini, baik perangkat keras dan perangkat lunak. Waktu sudah lewat ketika parsing adalah bagian penting dari waktu kompilasi, atau ketika kecepatan kompiler adalah masalah kritis (saya tahu satu perusahaan yang meninggal karena kompilasi biaya sekitar 30 tahun yang lalu). Spesialis parsing mungkin ingin mempelajari pengetahuan khusus itu di beberapa titik, tetapi rata-rata siswa dalam ilmu komputer, pemrograman atau teknik tidak membutuhkannya.

Jika siswa harus menghabiskan lebih banyak waktu untuk penguraian, ada ekstensi lain yang mungkin lebih berguna dan lebih formatif, seperti yang digunakan dalam linguistik komputasi. Peran pertama pengajaran adalah mengekstraksi ide-ide sederhana yang membentuk pengetahuan ilmiah, bukan untuk memaksa siswa untuk menderita apa yang harus diderita para ilmuwan penelitian (mahasiswa doktoral terkecuali: itu adalah ritus perikop :-).

Lisensi CC BY-SA 3.0 dari penulis

Makalah yang menjelaskan bagaimana membangun hutan parse biner dalam waktu kubik (disebutkan dalam posting oleh Angelo Borsotti) adalah: "Parsing SPPF-Style Dari Earley Recognizers" oleh Elizabeth Scott. Anda dapat menemukannya di sini: http://dx.doi.org/10.1016/j.entcs.2008.03.044

Dalam tulisan ini pembangunan hutan parse dikemas bersama (SPPF) dijelaskan yang mewakili semua pohon parse yang mungkin. Sub tree dibagi jika memungkinkan, dan node yang sesuai dengan derivasi berbeda dari substrat yang sama dari nonterminal yang sama digabungkan.

Saya ingin mengulangi jawaban di atas dengan menyarankan Anda membaca makalah ini:

http://dx.doi.org/10.1016/j.entcs.2008.03.044

Saya ingin memenuhi syarat dengan mengatakan bahwa saya telah mengimplementasikan algoritma dalam makalah ini dan saya percaya ada kesalahan. Secara khusus, kalimat pertama dari paragraf kedua dari bagian 4. Label pendahulu yang Anda buat untuk apa yang akan Earley tentukan pada fase "pemindaian" harus menunjuk dari p ke q dan bukan sebaliknya.

Secara khusus, baris berikut:

Tetapkan E0 sebagai item (S :: = · α, 0). Untuk i> 0 inisialisasi Ei dengan menambahkan item p = (A :: = αai · β, j) untuk setiap q = (A :: = α · aiβ, j) ∈ Ei − 1 dan, jika α =, menciptakan sebuah pointer pendahulu berlabel i - 1 dari q ke p

Harus membaca "dari p ke q" dan bukan "dari q ke p"

Saya mengimplementasikan algoritma seperti yang dinyatakan sebelumnya, yang memberi saya kesalahan pada beberapa test case buatan tangan, yang diperbaiki setelah saya mengubah arah pointer di sini.