Thuật·toán tách từ

Thuật toán tách từ
Tác giả: Lưu Tuấn Anh.

Nội dung

1. Các hướng tiếp cận
2. Các phương pháp được sử dụng
3. Ứng dụng bài toán tách từ
4. Thuật toán phổ biến
5. Một số vấn đề mở rộng

Tách từ là một quá trình xử lý nhằm mục đích xác định ranh giới của các từ trong câu văn, cũng có thể hiểu đơn giản rằng tách từ là quá trình xác định các từ đơn, từ ghép… có trong câu. Đối với xử lý ngôn ngữ, để có thể xác định cấu trúc ngữ pháp của câu, xác định từ loại của một từ trong câu, yêu cầu nhất thiết đặt ra là phải xác định được đâu là từ trong câu. Vấn đề này tưởng chừng đơn giản với con người nhưng đối với máy tính, đây là bài toán rất khó giải quyết.

Chính vì lý do đó tách từ được xem là bước xử lý quan trọng đối với các hệ thống Xử Lý Ngôn Ngữ Tự Nhiên, đặc biệt là đối với các ngôn ngữ thuộc vùng Đông Á theo loại hình ngôn ngữ đơn lập, ví dụ: tiếng Trung Quốc, tiếng Nhật, tiếng Thái, và tiếng Việt. Với các ngôn ngữ thuộc loại hình này, ranh giới từ không chỉ đơn giản là những khoảng trắng như trong các ngôn ngữ thuộc loại hình hòa kết như tiếng Anh…, mà có sự liên hệ chặt chẽ giữa các tiếng với nhau, một từ có thể cấu tạo bởi một hoặc nhiều tiếng. Vì vậy đối với các ngôn ngữ thuộc vùng Đông Á, vấn đề của bài toán tách từ là khử được sự nhập nhằng trong ranh giới từ.

1. Các hướng tiếp cận

Một cách tổng quát có thể thấy rằng bài toán tách từ có 3 phương pháp tiếp cận chính :
· Tiếp cận dựa vào từ điển cố định.
· Tiếp cận dựa vào thống kê thuần túy.
· Tiếp cận dựa trên cả hai phương pháp trên.

2. Các phương pháp được sử dụng

· So khớp từ dài nhất (Longest Matching)
· So khớp cực đại (Maximum Matching)
· Mô hình Markov ẩn (Hidden Markov Models- HMM)
· Học dựa trên sự cải biến (Transformation-based Learning – TBL)
· Chuyển đổi trạng thái trọng số hữu hạn (Weighted Finite State Transducer – WFST)
· Độ hỗn loạn cực đại (Maximum Entropy – ME)
· Máy học sử dụng vectơ hỗ trợ (Support Vector Machines)
.Trường xác xuất có điều kiện (CRFs)
Ngoài ra còn có thể kết hợp những phương pháp trên

3. Ứng dụng bài toán tách từ

Bài toán tách từ là bài toán cơ bản đầu tiên trong các bài toán đặt ra cho xử lý ngôn ngữ sau :
o Phân tích hình thái (morphological analysis)
· Phân tích phụ tố
· Nhận diện tên riêng
· Nhận diện ranh giới ngữ
o Phân tích ngữ pháp (PARSER)
· Gán nhãn từ loại
· Gán nhãn ranh giới ngữ
· Gán nhãn quan hệ cú pháp
o Xử lý văn bản
· Kiểm lỗi chính tả
· Kiểm lỗi văn phạm
· Phân loại văn bản
· Tóm tắt văn bản
· Hiểu văn bản
· Khai thác văn bản

Tài nguyên hỗ trợ:
· Từ điển tiếng Việt
· Ngữ liệu tiếng Việt được tách từ hỗ trợ quá trình huấn luyện

4. Thuật toán phổ biến

Đối với tiếng Nhật, thuật toán phổ biến nhất là “Trọng số cực tiểu” : qui về bài toán đồ thị như sau :
1. Tạo ra 2 đỉnh ảo là start, và end (đầu và cuối câu).
2. Lần lượt so sánh các đoạn với độ dài bất kì với 1 từ điển ngôn ngữ có sẵn.
3. Các đoạn có xuất hiện trong từ điển sẽ tạo thành 1 đỉnh mới trên đồ thị.
4. Trọng số giữa 2 đỉnh (2 đoạn phải liên tiếp nhau trong câu) được tính theo công thức f(i,j) với i,j là 2 từ.
5. Tìm đường đi từ đỉnh start đến đỉnh end có trọng số nhỏ nhất trên đồ thị đó.

Trong bước 4, công thức f(i,j) thường được tính theo giá trị uni-gram(khả năng xuất hiện của 1 từ) và bi-gram(khả năng 2 từ xuất hiện liên tiếp nhau). Ngoài ra còn có thể có thêm 1 số yếu tố khác như từ loại, khả năng liên kết từ loại, … cũng được sử dụng trong hàm f.
Trước đây, các giá trị này (trừ uni-gram và bi-gram được lấy từ cách thông kê corpus) thường được đánh giá bằng tay (do người thực hiện).  Nhưng với sự phát triển của lý thuyết máy học như Markov ẩn, CRFs, … các giá trị này thường được tính 1 cách tự động.
Trong bước 5, thuật toán tìm đường đi từ đỉnh start đến đỉnh end thường sử dụng thuật toán Viterbi với độ phức tạp thuật toán O(n) với n là độ dài câu cần tách.

5. Một số vấn đề mở rộng

Đối với tiếng Việt,có 1 công cụ tách từ được phát triển trong đề tài VLSP http://www.loria.fr/~lehong/tools/vnTokenizer.php
Độ chính xác đạt 97%.
Theo như tôi được biết, với các công cụ tương tự cho tiếng Nhật, độ chính xác lên đến 99% (JUMAN, Mecab). Như thế chúng ta vẫn còn rất nhiều việc phải làm.

Ngoài ra, có 1 vấn đề nảy sinh trong khi tách từ là việc xuất hiện các từ mời (các từ không được định nghĩa trong từ điển).
Đây là 1 vấn đề không thể bỏ qua khi ngôn ngữ là luôn luôn thay đổi và sinh ra các từ mới, trong khi từ điển (dành cho xử lý ngôn ngữ tự nhiên) không thể cập nhật hết được.
Các nghiên cứu đối với tiếng Nhật và tiếng Trung đã xử lý vấn đề này khá tốt. Với sự gần gũi về ngữ pháp và đặc điểm ngôn ngữ, ta có thể ứng dụng những nghiên cứu đó đối với tiếng Việt.

Nguồn:

http://viet.jnlp.org/kien-thuc-co-ban-ve-xu-ly-ngon-ngu-tu-nhien/thuat-toan-tach-tu-tokenizer/thuat-toan-tach-tu

Advertisements

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

%d bloggers like this: