Parse tree được sử dụng để biểu thị cấu trúc của một câu văn và thường được chia thành hai loại chính là Constituency Tree và Dependency Tree:

– Constituency Tree: Constituency Tree được hình thành dựa trên Constituency Grammar và biểu thị cấu trúc cú pháp của câu văn căn cứ theo một Context-free Grammars nhất định (Constituency thể hiện mối quan hệ giữa các đơn vị ngôn ngữ trong một câu văn. Các đơn vị ngôn ngữ này được gọi là Constituent, một Constituent có thể là một morpheme, word, phrase hoặc clause). Constituent Parse Tree được viết dưới dạng tree với Root là start symbol (thường là ‘S’), Leaves là các terminal và các node của tree là các non-terminal (tham khảo định nghĩa terminal và non-terminal tại bài tutorial về Context-free Grammars).

– Dependency Tree: khác với Constituency Tree, Dependency Tree không phân biệt giữa terminal với non-terminal và coi các từ trong câu là một node. Các node này được kết nối với nhau bằng một đường liên kết trực tiếp (directed link) để hình thành nên một graph (Các directed link có thể được đặt tên để biểu thị mối quan hệ giữa hai nodes). Graph này được coi là một tree với Root là từ trung tâm của câu (thông thường là động tự(Verb) trong câu)

Tương tụ như POS, việc tìm Parse Tree cũng gặp nhiều kho khăn do một câu có thể có nhiều Parse Tree khác nhau (Structural ambiguity). Ví dụ như cụm từ ‘old man and woman’ có thể hiểu là ‘old (man and woman)’ hoặc cũng có thể hiểu là ‘(old man) and (woman)’. Tuy nhiên để giải quyết vấn đề này, chúng ta có thể sử dụng một số thuật toán như CKY algorithm, Earley algorithm hoặc Chart parsing algorithm.

Về ứng dụng thực tế, Parse tree được sử dụng nhiều trong các hệ thống xử lý ngôn ngữ như được sử dụng để kiểm tra lỗi ngữ pháp của một tệp dữ liệu. Các câu văn mà không thể tìm được một Parse tree phù hợp tức là câu văn đó không đúng về mặt ngữ pháp. Ngoài ra Parse tree cũng được ứng dụng trong việc phân tích ngữ nghĩa (semantic analysis). Đây là một nhiệm vụ quan trọng trong bài toán trích xuất thông tin (Information Extraction) cũng như trong các hệ thống Hỏi-Đáp (Question Answering system). Ví dụ như ta sử dụng Parse tree để xác định các thành phần trong câu và mối quan hệ giữa các thành phần này để xác định người dùng muốn tìm kiếm thông tin về vấn đề gì để từ đó đưa ra câu trả lời hợp lý nhất.

Tháng Mười Hai 13, 2018
ITechSeeker