TAILIEUCHUNG - Báo cáo khoa học: "Factoring Synchronous Grammars By Sorting"

Synchronous Context-Free Grammars (SCFGs) have been successfully exploited as translation models in machine translation applications. When parsing with an SCFG, computational complexity grows exponentially with the length of the rules, in the worst case. In this paper we examine the problem of factorizing each rule of an input SCFG to a generatively equivalent set of rules, each having the smallest possible length. Our algorithm works in time O(n log n), for each rule of length n. This improves upon previous results and solves an open problem about recognizing permutations that can be factored. . | Factoring Synchronous Grammars By Sorting Daniel Gildea Computer Science Dept. University of Rochester Rochester NY 14627 Giorgio Satta Dept. of Information Eng g University of Padua I-35131 Padua Italy Hao Zhang Computer Science Dept. University of Rochester Rochester NY 14627 Abstract Synchronous Context-Free Grammars SCFGs have been successfully exploited as translation models in machine translation applications. When parsing with an SCFG computational complexity grows exponentially with the length of the rules in the worst case. In this paper we examine the problem of factorizing each rule of an input SCFG to a generatively equivalent set of rules each having the smallest possible length. Our algorithm works in time O n log n for each rule of length n. This improves upon previous results and solves an open problem about recognizing permutations that can be factored. 1 Introduction Synchronous Context-Free Grammars SCFGs are a generalization of the Context-Free Grammar CFG formalism to simultaneously produce strings in two languages. SCFGs have a wide range of applications including machine translation word and phrase alignments and automatic dictionary construction. Variations of SCFGs go back to Aho and Ullman 1972 s Syntax-Directed Translation Schemata but also include the Inversion Transduction Grammars in Wu 1997 which restrict grammar rules to be binary the synchronous grammars in Chiang 2005 which use only a single nonterminal symbol and the Multitext Grammars in Melamed 2003 which allow independent rewriting as well as other tree-based models such as Yamada and Knight 2001 and Galley et al. 2004 . When viewed as a rewriting system an SCFG generates a set of string pairs representing some translation relation. We are concerned here with the time complexity of parsing such a pair according to the grammar. Assume then a pair with each string having a maximum length of N and consider an SCFG G of size G with a bound of n nonterminals in the right-hand side .

• Báo cáo khoa học
• Factoring Synchronous Grammars By Sorting
• Daniel Gildea
• Long Papers
• 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