TAILIEUCHUNG - Báo cáo khoa học: "Quasi-Destructive Graph Unification"

Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90% of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possible. We have developed a scheme to attain these two elements without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. . | Quasi-Destructive Graph Unification Hideto Tomabechi Carnegie Mellon University ATR Interpreting Telephony 109 EDSH Pittsburgh PA 15213-3890 Research Laboratories tomabech-f-@ Seika-cho Sorakugun Kyoto 619-02 JAPAN ABSTRACT Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90 of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms 1 elimination of excessive copying by only copying successful unifications 2 Finding unification failures as soon as possible. We have developed a scheme to attain these two elements without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. We found that parsing relatively long sentences requiring about 500 top-level unifications during a parse using our algorithm is approximately twice as fast as parsing the same sentences using Wroblewski s algorithm. 1. Motivation Graph unification is the most expensive part of unification-based grammar parsing systems. For example in the three types of parsing systems currently used at ATR1 all of which use graph unification algorithms based on Wroblewski 1987 unification operations consume 85 to 90 percent of the total cpu time devoted to a The number of unification operations per sentence tends to grow as the grammar gets larger and more complicated. An unavoidable paradox is that when the natural language system gets larger and the coverage of linguistic phenomena increases the writers of natural language grammars tend to rely more on deeper and more complex path equations cycles and frequent reentrancy to lessen the complexity of writing the grammar. As a result we have seen that the number of unification operations increases rapidly as the coverage of the grammar grows in contrast to the parsing algorithm itself which does not seem to Visiting Research Scientist. Local email address tomabech .

• Báo cáo khoa học
• Quasi Destructive
• Graph Unification
• Hideto Tomabechi Carnegie Mellon
• 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