tailieunhanh - Báo cáo khoa học: "Parsing Non-Recursive Context-Free Grammars"

We consider the problem of parsing non-recursive context-free grammars, ., context-free grammars that generate finite languages. In natural language processing, this problem arises in several areas of application, including natural language generation, speech recognition and machine translation. We present two tabular algorithms for parsing of non-recursive context-free grammars, and show that they perform well in practical settings, despite the fact that this problem is PSPACEcomplete. | Parsing Non-Recursive Context-Free Grammars Mark-Jan Nederhof Faculty of Arts University of Groningen . Box 716 NL-9700 AS Groningen The Netherlands markjan@ Giorgio Satta Dip. di Elettronica e Informatica Universita di Padova via Gradenigo 6 A I-35131 Padova Italy satta@ Abstract We consider the problem of parsing non-recursive context-free grammars . context-free grammars that generate finite languages. In natural language processing this problem arises in several areas of application including natural language generation speech recognition and machine translation. We present two tabular algorithms for parsing of non-recursive context-free grammars and show that they perform well in practical settings despite the fact that this problem is PSPACE-complete. 1 Introduction Several applications in natural language processing require parsing of a large but finite set of candidate strings. Here parsing means some computation that selects those strings out of the finite set that are well-formed according to some grammar or that are most likely according to some language model. In these applications the finite set is typically encoded in a compact way as a context-free grammar CFG that is non-recursive. This is motivated by the fact that non-recursive CFGs allow very compact representations for finite languages since the strings derivable from single nonterminals may be substrings of many different strings in the language. Unfolding such a grammar and parsing the generated strings Secondary affiliation is the German Research Center for Artificial Intelligence DFKI . one by one then leads to an unnecessary duplication of subcomputations since each occurrence of a repeated substring has to be independently parsed. As this approach may be prohibitively expensive it is preferable to find a parsing algorithm that shares subcomputations among different strings by working directly on the nonterminals and the rules of the non-recursive CFG. In this .

• Báo cáo khoa học
• Parsing Non Recursive
• Context Free Grammars
• Mark Jan
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học