Nén mẫu biến cách tên tiếng Iceland bằng trie 3.27kB

(alexharri.com)

2 điểm bởi GN⁺ 2025-08-04 | Chưa có bình luận nào. | Chia sẻ qua WhatsApp

Xử lý biến cách cho tên riêng tiếng Iceland thay đổi theo ngữ cảnh thành 4 hình thức
Phát triển chức năng trả về trường hợp ngữ pháp phù hợp cho tên đầu vào thông qua thư viện JavaScript dựa trên dữ liệu
Việc lưu trữ tất cả tên trực tiếp gây ra cả tăng dung lượng và thiếu dữ liệu, nên giải quyết bằng cấu trúc trie và kỹ thuật nén
Nhờ nén trie, có thể suy diễn tự động dựa trên mẫu chung và đạt được cơ sở dữ liệu rất nhỏ bao phủ trên 80% dữ liệu
Trong điều kiện thông thường đạt độ chính xác trên 74%, đồng thời cung cấp phiên bản strict riêng cho khu vực công hoặc các trường hợp yêu cầu độ chính xác cao

Bối cảnh vấn đề

Khi hiển thị tên riêng trong giao diện tiếng Iceland, thường gặp khó khăn do sự biến tố (declension)
Tên tiếng Iceland có hình thức khác nhau theo 4 trường hợp ngữ pháp như chủ cách, tân cách, cách gián cách, cách sở hữu
Cơ sở dữ liệu thường lưu tên ở dạng chủ cách, nên khi ngữ cảnh cần dạng khác sẽ phát sinh vấn đề
Dùng sai dạng sẽ khiến câu văn nghe có vẻ không phải tiếng bản xứ hoặc lúng túng

Iceland mở dữ liệu DIM (Database of Icelandic Morphology) do Árnastofnun quản lý
Dữ liệu biến cách cho tên có thể được chuyển sang CSV theo định dạng Kristín’s Format (K-format)
Toàn bộ dữ liệu DIM có tới 7 triệu dòng và quá lớn, nhưng chỉ lọc ra 4.500 tên riêng được phê duyệt chính thức thì thu được thông tin biến cách cho hơn 3.600 tên
Với mỗi tên, có thể xây dựng dãy hình thức từ chủ cách đến sở hữu cách

Triển khai ban đầu bắt đầu với hàm applyCase để trả về hình thức phù hợp từ mảng biến đổi tên-theo-trường hợp
Tuy nhiên, cách tải mảng trực tiếp có dung lượng (30kB gzipped) lớn
Một hạn chế là không thể xử lý tên không có trong dữ liệu

Trích xuất tiền tố chung giữa 4 hình thức của mỗi tên rồi chỉ lưu tập hậu tố (suffix encoding) cho từng phần để giảm trùng lặp tối đa
Nhận thấy có rất nhiều tên cùng theo một mẫu biến cách

Với cấu trúc trie (chèn ngược theo hậu tố), tối ưu ánh xạ giá trị cho nhóm tên có mẫu tương tự
Dưới các mẫu chung của đuôi tên (name endings), thông tin biến cách chỉ cần lưu một lần, giúp dự đoán tốt cho tên mới

Khi các lá (leaf) trong một subtree có cùng giá trị, gán giá trị cho nút cha và xoá các nút con để nén cây
Nhờ đó giảm số nút tới 15.4%, kích thước thu gọn xuống 4.01kB
Với lần nén thứ hai, gộp các leaf anh em có cùng giá trị thành một nút, đạt 3.27kB

Khi nhập tên mới, có thể tự động biến cách dựa trên mẫu tương tự
Thực tế, với tên chưa biết trước đó, đạt 74% đúng và 26% lỗi; còn tỷ lệ lỗi theo người dùng thực tế chỉ 0.34%
Khi dữ liệu có tính quy luật (regularity) và tính bao quát (comprehensiveness) càng cao, hiệu quả nén và độ chính xác suy diễn tự động càng tăng

Cuối cùng, phát hành thư viện beygla dùng trie đã nén
Phát hành bản kích thước tối thiểu (4.46kB) và module strict tùy chỉnh, nghiêm ngặt và hoàn hảo hơn (15kB)
Phiên bản strict dành cho nơi cần 100% độ chính xác như tài liệu công; bản nhẹ có thể chọn cho ứng dụng web thông thường

Nén dữ liệu mẫu biến cách ngôn ngữ bằng trie có thể áp dụng cho tự động hóa xử lý tên riêng, địa chỉ và danh từ khác ở các ngôn ngữ có biến tố khác ngoài tiếng Iceland
Sự kết hợp giữa dữ liệu có tính quy luật cao và nén trie là giải pháp tối ưu hóa hiệu quả dữ liệu/vận hành cho tự động hóa xử lý biến tố hình thái

Trong quá trình phát triển beygla đã có nhiều phản hồi từ chuyên gia và các lần tối ưu hóa
Nén bổ sung trên trie giúp giảm dung lượng từ 3.43kB xuống 3.27kB

Đây là trường hợp thu gọn và tự động hóa bài toán biến cách tên tiếng Iceland bằng cấu trúc dữ liệu trie dựa trên mẫu
Có giá trị làm gợi ý về chiến lược xử lý dữ liệu thực tế khi cân bằng giữa dung lượng và độ chính xác