Nén mẫu biến cách tên tiếng Iceland bằng trie 3.27kB
(alexharri.com)- 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
Thu thập và làm sạch dữ liệu
- 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
Cấu trúc cơ bản của thư viện
- 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
Loại bỏ trùng lặp và trích xuất mẫ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
Áp dụng trie cho việc khớp mẫu
- 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
Quá trình nén và tối ưu hóa trie
- 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
Hiệu năng và khả năng tổng quát hóa của trie
- 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
Triển khai thực tế và ứng dụ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
Kết luận và khả năng mở rộ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
Ghi chú/Lời cảm ơn
- 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
Tóm tắt
- Đâ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
1 bình luận
Ý kiến Hacker News
Khi mới học tiếng Tây Ban Nha ở thời trung học, tôi từng dùng phần mềm trên Windows kiểu đổ ra hàng loạt động từ nguyên mẫu và thì, rồi mình phải nhập đúng dạng chia tương ứng. Nhờ kiểu luyện đó mà các quy tắc ngữ pháp ngấm vào người và tôi trở nên khá thành thạo. Nhưng khi học tiếng Nga thì cách biến cách đột nhiên trở nên rất khó, và tôi tìm mãi vẫn không thấy ứng dụng nào có thể giải thích hay cho luyện theo kiểu tương tự. Không biết có ai biết ứng dụng nào cho mục đích này không (web hoặc macOS/iOS)
Có một bộ thẻ Anki dùng phương pháp gọi là "KOFI(Konjugation First)". KOFI nghĩa là học hết các mẫu chia trước khi học ngôn ngữ. Sau khi học tiếng Pháp, tôi thấy kỹ năng chia chưa ổn nên đã thử cách này về sau; dù nói sai ngữ pháp thì giao tiếp hằng ngày vẫn không vấn đề gì, nhưng đó không phải mức tôi mong muốn. Mục tiêu của phương pháp này là nắm toàn bộ các mẫu biến đổi trong thời gian ngắn trước khi học ngôn ngữ. Tôi muốn một ngày nào đó áp dụng nghiêm túc cho một ngôn ngữ mới. Nhưng hứng thú với tiếng Pháp của tôi giảm dần nên cuối cùng bỏ dở. Liên kết bộ thẻ Anki liên quan
Khi học tiếng Nga, tôi từng viết một script kết hợp module Python spaCy với mô-đun lớn dành cho tiếng Nga để làm lemmatization theo ngữ cảnh và trích xuất thẻ ngữ pháp. Nhưng khi trình độ tiếng Nga của tôi thực sự tiến bộ, điều hiệu quả hơn nhiều lại là ngừng cố gắng phân rã logic các biến thể, và thay vào đó tích lũy trong đầu một thư viện các mẫu (bao gồm cả ngoại lệ) thông qua trải nghiệm sử dụng và lặp lại. Nhân tiện, “ngữ cảnh” ở đây là nghĩa trong câu
Khi tự học tiếng Tây Ban Nha 25 năm trước, tôi dùng một từ điển Tây Ban Nha/Anh. Các động từ nguyên mẫu được gắn chỉ số số học để phân nhóm theo cùng mẫu chia. Ở phần đầu từ điển có bảng chia đầy đủ theo mọi thì của động từ đại diện cho từng nhóm. Động từ bất quy tắc có chỉ số riêng, và tương tự cũng được gom nhóm với các động từ bất quy tắc giống nhau (ví dụ: tener, detener). Mọi động từ đều được sắp gọn vào vài chục mẫu riêng biệt. Tôi cũng từng nghĩ đến chuyện làm phần mềm quiz tận dụng hệ thống này nhưng rốt cuộc không làm. Tôi tự hỏi liệu mẫu reverse-string trie được nhắc trong bài có thể dùng cho kiểu phân loại này không
Để học biến cách tiếng Nga, tôi từng có ý tưởng làm flashcard với tổ hợp giới từ + tính từ + danh từ để tăng tốc độ ghi nhớ. Trước đó tôi đã học tiếng Latin, mà biến cách tiếng Latin thì tôi không kỳ vọng có thể thuộc nhanh (trừ phi là tu sĩ chăng?), còn tiếng Nga thì tôi rất muốn nắm thật nhanh. Nhưng cuối cùng nó cũng không thành dự án
Tôi đang dùng ConjuGato trên iOS để luyện chia động từ tiếng Tây Ban Nha. Ở chế độ game, ứng dụng đưa ra động từ nguyên mẫu/thì/ngôi và mình phải nhớ ra dạng chia. Có thể luyện riêng động từ bất quy tắc nên khá hiệu quả để học các ngoại lệ
Với 800 cái tên bị thiếu thông tin biến cách trong cơ sở dữ liệu, có vẻ cách giải quyết trực quan nhất là tự điền tay các dạng biến cách. Với người bản ngữ thì vài giờ là xong, và ngay cả với những tên hoàn toàn xa lạ thì ít nhất cũng có thể đoán ra dạng không quá kỳ cục một cách rõ ràng. Hoặc bảo LLM làm thì cũng rất rẻ. Mã hóa kết quả rồi phân phối dưới cấu trúc trie như thế này vẫn là ý hay. Chỉ là không cần dùng trie luôn như bộ suy đoán biến cách
Xử lý thêm nhiều tên hơn là điều đáng làm—đó là phần DIM cần tiếp tục được bổ sung. Ở Iceland, danh sách tên được cho phép thường xuyên có tên mới thêm vào nên lúc nào cũng sẽ có khoảng trống. Cá nhân tôi không đủ tự tin để tự thêm dữ liệu, và mỗi lần xem lại kết quả của 100 tên chưa được xác minh thì thường có vài trường hợp khiến tôi nghĩ “cái này đúng chứ nhỉ?”. Tôi nhiều lần tra các tên tương tự trong DIM và nghĩ “mình sẽ không biến cách như vậy đâu”. Vì thế tôi xem dữ liệu DIM là “nguồn chân lý” được duy trì bởi chuyên gia ngôn ngữ
Làm tay thì tốt, nhưng với các tên không có trong danh sách chính thức (ví dụ tên nước ngoài) thì vẫn có giới hạn. Tôi cũng sống ở một quốc gia có danh sách tên tập trung, nhưng có thể xin ngoại lệ, và những người sinh ra trước khi danh sách tồn tại hoặc người nhập cư thì có thể có tên không nằm trong đó. Trong đủ kiểu tình huống chồng chéo như vậy, khả năng “dự đoán một dạng biến cách tương đối hợp lý” vẫn rất hữu ích
Tôi không thấy bằng chứng nào cho rằng LLM dự đoán biến cách tốt hơn trie (nếu ví dụ thực tế đó không có trong dữ liệu huấn luyện của LLM thì tìm web có lẽ còn tốt hơn)
Tự dưng tôi tò mò không biết các LLM hiện tại đã học sẵn những mẫu kiểu này chưa
Tôi không chắc Rails có tự xử lý chuyện này không, nhưng trước đây nó từng làm mấy trò phép thuật như thế khá tốt. Tôi từng xem source code của pluralise, và trong đó thậm chí còn mã hóa cả quy tắc số nhiều bất quy tắc của tiếng Wales
Một ý tưởng tối ưu là thay vì để trie ánh xạ trực tiếp tới chính chuỗi hậu tố, hãy tạo một mảng các hậu tố duy nhất rồi để trie trỏ tới chỉ số trong mảng đó. Ví dụ:
Rồi tham chiếu chỉ số như sau:
Tôi thử trực tiếp bằng Claude Code thì ở trạng thái gzip lại tăng thêm 100 byte (3456 -> 3556), còn kích thước trước nén chỉ giảm 20%. Có vẻ bản thân gzip đã tối ưu khá tốt cho các mẫu lặp rồi
Tiến thêm một bước nữa thì có thể đưa chính các hậu tố vào trie, rồi nhận diện các subtree giống nhau để khử trùng lặp. Nếu dùng gzip, chắc hẳn sẽ có cách tối ưu thông minh tận dụng mảng hậu tố. Nếu dùng định dạng tối ưu nhị phân thì có thể còn tốt hơn
Cá nhân tôi cứ có cảm giác phải có một lời giải ma thuật nào đó để xử lý dưới <1kb khi chưa nén. Ví dụ lập một danh sách regex tối giản có thể phân loại tên chính xác 100%? Một bloom filter cực lớn? Hay dùng đặc trưng chuyên biệt thay vì băm thông thường?
Nghe như một bài toán phỏng vấn ác mộng. Dùng trie theo kiểu đảo ngược (ngược chuỗi) là thứ cả đời chắc chỉ cần đến đúng một lần, nhưng dùng được lần đó thì trông như phù thủy vậy
Thay vì làm việc này trong JS, có lẽ có thể để cơ sở dữ liệu trả về mọi tổ hợp name-case, rồi khi hiển thị chỉ chọn cái cần dùng. Tức là xử lý ở lớp bản địa hóa. Tôi cũng tò mò trong bối cảnh đa ngôn ngữ thì sẽ thế nào. Nếu UI tiếng Iceland xử lý tên Pháp thì chắc sẽ luôn dùng chủ cách, và UI tiếng Anh xử lý tên Iceland có lẽ cũng vậy. Cuối cùng có lẽ chỉ thật sự cần trong ngữ cảnh gọi đích danh người dùng hoặc ở bảng quản trị kiểu “user x trả lời user y” mà thôi
Có tới 88 cái tên theo một mẫu biến cách nhất định kết thúc bằng “idur”, “tur”, “ður”, nhưng cùng một hậu tố không phải lúc nào cũng theo cùng một mẫu biến cách. Vấn đề này trông như quy tắc đơn giản nhưng thực ra rất thú vị. Liệu mẫu hậu tố có liên quan tới cách phát âm của âm tiết ngay trước đó không? Nếu muốn xử lý tên chưa biết tốt hơn, có nên dùng NLP để rút ra biểu diễn phát âm của tên thay vì chỉ dựa trên chữ cái rồi tra bằng trie hay cấu trúc tương tự không nhỉ
Cẩn thận, nghĩ theo hướng này một lúc là có thể trượt sang thảo luận về Dependent Types đấy
Ý tưởng rất sắc sảo. Thật ra ngay cả các tên phát âm giống nhau cũng có thể có mẫu biến cách khác nhau. Ví dụ:
Trong bối cảnh beygla/strict, perfect hashing có thể là một phương án thay thế
Tôi ngạc nhiên vì cách này hoạt động tốt đến mức đó, như thể biến cách tên tiếng Iceland đủ đơn giản và có tính quyết định để theo các mẫu như vậy. Ngôn ngữ nói chung vốn thường khá phức tạp mà