TAILIEUCHUNG - Báo cáo khoa học: "A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices"

Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. | A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices Matthew Skala School of Computer Science University of Waterloo mskala@ Victoria Krakovna Janos Kramar Dept. of Mathematics University of Toronto vkrakovna jkramar @ Gerald Penn Dept. of Computer Science University of Toronto gpenn@ Abstract Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding which represents join failure using the zero vector to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits resulting in a smaller vector size. A constraint solver is used to construct the encoding and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques. 1 Introduction The use of bit vectors is almost as old as HPSG parsing itself. Since they were first suggested in the programming languages literature Ait-Kaci et al. 1989 as a method for computing the unification of two types without table lookup bit vectors have been attractive because of three speed advantages The classical bit vector encoding uses bitwise AND to calculate type unification. This is hard to beat. Hash tables the most common alternative involve computing the Dedekind-MacNeille completion DMC at compile time if the input type hierarchy is not a bounded-complete partial order. That is exponential time in the worst case most bit vector methods avoid explicitly computing it. With large type signatures the table that indexes unifiable pairs of types may be so large that it pushes working parsing memory into swap. This loss of locality of reference costs time. Why isn t everyone using bit

• Báo cáo khoa học
• A Generalized Zero Preserving Method
• Compact Encoding
• Concept Lattices
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Mô hình 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 loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• 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 ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• 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
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball