Biểu thức chính quy và các phương pháp trạng thái hữu hạn

Các kỹ thuật thực tế được xây dựng trên các ngôn ngữ chính quy — khớp mẫu bằng biểu thức chính quy và ánh xạ chuỗi-sang-chuỗi bằng bộ chuyển đổi trạng thái hữu hạn — xử lý hiệu quả việc mã hóa, chuẩn hóa và phân tích hình thái.

Definition

Các phương pháp trạng thái hữu hạn là các kỹ thuật xử lý ngôn ngữ trong đó các mẫu và ánh xạ được biểu thị dưới dạng biểu thức chính quy hoặc bộ tự động và bộ chuyển đổi trạng thái hữu hạn, đảm bảo nhận dạng hiệu quả theo thời gian tuyến tính.

Scope

Bao gồm các biểu thức chính quy như một ngôn ngữ mẫu trên các chuỗi, các bộ tự động trạng thái hữu hạn và bộ chuyển đổi như hiện thực hóa tính toán của chúng, và ứng dụng của chúng trong chuẩn hóa văn bản, mã hóa, chính tả và hình thái học tính toán. Nó bao gồm các phương pháp trạng thái hữu hạn có trọng số được sử dụng trong xử lý giọng nói và xử lý nông. Lý thuyết ngữ âm học đầy đủ và phân tích cú pháp sâu nằm ngoài phạm vi.

Core questions

• Làm thế nào các biểu thức chính quy có thể chỉ định và trích xuất các mẫu văn bản một cách chính xác?
• Làm thế nào các bộ chuyển đổi trạng thái hữu hạn ánh xạ các dạng bề mặt sang các phân tích từ vựng, như trong hình thái học?
• Tại sao các phương pháp trạng thái hữu hạn được ưu tiên cho việc mã hóa và chuẩn hóa?

Key concepts

• biểu thức chính quy
• bộ chuyển đổi trạng thái hữu hạn
• mã hóa
• chuẩn hóa văn bản
• phân tích hình thái
• hình thái học hai cấp
• bộ tự động có trọng số
• khoảng cách chỉnh sửa

Key theories

Các mô hình chính quy của hình thái học và ngữ âm học

Kết quả cho thấy các quy tắc viết lại ngữ âm học và các biến đổi hình thái có thể được biên dịch thành các bộ chuyển đổi trạng thái hữu hạn, làm cho việc phân tích và tạo ra trở thành một khuôn khổ hiệu quả duy nhất.

Sự tương đương của biểu thức chính quy và bộ tự động hữu hạn

Các biểu thức chính quy, ngữ pháp chính quy và bộ tự động trạng thái hữu hạn đều mô tả chính xác các ngôn ngữ chính quy, vì vậy một mẫu khai báo có thể được biên dịch thành một bộ nhận dạng hiệu quả.

History

Biểu thức chính quy đi vào điện toán từ công trình của Kleene và trở nên phổ biến trong các công cụ văn bản. Vào những năm 1980, hình thái học hai cấp của Koskenniemi và việc Kaplan và Kay biên dịch các quy tắc ngữ âm học thành bộ chuyển đổi đã thiết lập công nghệ trạng thái hữu hạn như một công cụ chủ lực của xử lý hình thái, một cách tiếp cận được củng cố trong cẩm nang của Beesley và Karttunen.

Debates

Các phương pháp trạng thái hữu hạn có thể mở rộng đến mức nào?

Các kỹ thuật trạng thái hữu hạn cực kỳ hiệu quả nhưng bị giới hạn ở các hiện tượng chính quy; cuộc tranh luận liên quan đến việc những nhiệm vụ xử lý ngôn ngữ nào vẫn được phục vụ tốt nhất bởi chúng so với các mô hình thống kê hoặc thần kinh phong phú hơn.

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

Tại sao sử dụng bộ chuyển đổi trạng thái hữu hạn thay vì chỉ một bảng tra cứu cho hình thái học?

Một bộ chuyển đổi mã hóa một cách nhỏ gọn các biến đổi có hệ thống và có thể phân tích hoặc tạo ra các dạng từ mà nó chưa từng thấy, trong khi một bảng chỉ lưu trữ các dạng được liệt kê rõ ràng trong đó.