- Taskusanakirja là một từ điển Phần Lan-Anh cung cấp tìm kiếm tiền tố khi đang nhập
- Khi mở rộng các dạng biến tố tiếng Phần Lan, số mục tăng lên 40 triệu~60 triệu, khiến trie chạm giới hạn
- Giải pháp tạm thời dùng SQLite FTS chạy nhanh nhưng yêu cầu tải xuống ban đầu 3GB
- FST viết bằng Rust đã thu gọn dữ liệu SQLite thành tệp nhị phân khoảng 10MB, tiết kiệm 300 lần
- FST chia sẻ cả tiền tố lẫn hậu tố, nên rất hợp với các mẫu biến tố lặp lại
Cấu trúc tìm kiếm của Taskusanakirja và những giới hạn ban đầu
- Taskusanakirja, viết tắt là
tsk, là từ điển Phần Lan-Anh có tính năng tìm kiếm tăng dần trong lúc nhập
- Về bản chất, đây là bài toán tìm kiếm tiền tố, và cách giải kinh điển cho tự động hoàn thành là cài đặt trie
- Bản cài đặt đầu tiên được viết bằng Go, và mục tiêu thiết kế ban đầu là phân phối toàn bộ chương trình dưới dạng một
.exe, một .app, hoặc một tệp nhị phân liên kết tĩnh duy nhất
- Để tránh khớp mọi mục thuộc một tỷ lệ phần trăm một chữ số nào đó trong tập từ vựng cỡ sáu chữ số ở giữa, hệ thống chỉ trả về khoảng 50 hoặc 100 kết quả đầu tiên và ghi nhớ các tổ hợp 1, 2, 3 chữ cái
- Với cách này, có thể nhét một trie đã tối ưu cơ bản vào khoảng 60MB, và sau 1 năm tự dùng nhiều thì không thấy độ trễ đáng kể
Bài toán quy mô do dữ liệu biến tố tiếng Phần Lan tạo ra
- Tiếng Phần Lan là một ngôn ngữ chắp dính, nên một từ gốc có thể có hơn 100 đuôi từ nếu tính mọi tổ hợp
- Các tổ hợp này không đều đặn, và quy tắc chính tả tiếng Phần Lan được chuẩn hóa rất cao lại phản ánh khá trực tiếp cách người bản ngữ nói, khiến từ gốc khi gắn với đuôi sẽ bị kéo dài, dịch chuyển và biến đổi
- Người học sơ cấp dễ bị khựng lại trước những câu như “
Opiskelijassammekin on leijonan sydän”, và tsk còn muốn chứa thông tin giúp tách từ ở đúng ranh giới
- Về mặt ngôn ngữ học, các biến đổi này liên quan đến luân phiên phụ âm và hòa hợp nguyên âm, và tiếng Phần Lan dùng cả hai cùng lúc
- Ví dụ,
katu nghĩa là “street”, nhưng dạng sở hữu không phải katun mà là kadun, vì t yếu hóa thành d trong âm tiết đóng
- Khi nhân cấu trúc này với 15 cách, 2 số nhiều, 6 hậu tố sở hữu và một số lượng không xác định các tiểu từ, trie ngây thơ không thể chia sẻ chi phí của phần đuôi như
-ssa-mme-kin, vốn được hàng nghìn từ cùng dùng
- Khoảng 400 nghìn mục có thể được giữ trong trie với khoảng 50MB RAM, nhưng cách làm tương tự không mở rộng được lên 40 triệu~60 triệu mục
- Giải pháp tạm thời là đưa các dạng biến tố vào một cơ sở dữ liệu SQLite FTS riêng để tìm khi cần; nó chạy không có độ trễ cảm nhận được, nhưng yêu cầu tải xuống 3GB ở lần đầu
Kết quả sau khi chuyển sang Rust và FST
- Sau 9 tháng, khi thử lại bằng Rust, tác giả đã viết một chương trình Rust tối giản để lấy dữ liệu từ cơ sở dữ liệu SQLite 3GB và nén thành FST
- Động lực đến từ bài viết của BurntSushi aka Andrew Gallant Index 1,600,000,000 Keys with Automata and Rust, với điểm mấu chốt là máy trạng thái hữu hạn có thể biểu diễn một tập hoặc map chuỗi đã sắp xếp theo cách nhỏ gọn và nhanh
- Tệp nhị phân kết quả chỉ khoảng 10MB, tức tiết kiệm khoảng 300 lần so với cơ sở dữ liệu SQLite 3GB
- Trường hợp sử dụng này cũng đặc biệt phù hợp với fst crate, vì đây là bài toán ánh xạ các dạng biến tố và chia động từ trong một ngôn ngữ chắp dính mạnh trở về định nghĩa gốc của chúng
- Trie nén tiền tố, còn FST nén cả tiền tố lẫn hậu tố
- Trong kho ngữ liệu từ điển tiếng Phần Lan, chỉ có một số ít hậu tố phổ biến xuất hiện lặp đi lặp lại rất thường xuyên, nên việc chia sẻ hậu tố đem lại hiệu quả lớn
- Dữ liệu là dữ liệu tĩnh không thay đổi trong lúc chạy, nên có thể tránh được điểm yếu lớn nhất của
fst
Vì sao FST nhỏ hơn trie
- Điểm mấu chốt giúp FST nhỏ hơn trie rất nhiều trên dữ liệu ngôn ngữ tự nhiên là chia sẻ hậu tố
- Trie chia sẻ tiền tố theo kiểu
kadun và kaduille dùng chung ba nút đầu, nhưng các nhánh hậu tố khác nhau vẫn phải được lưu riêng
- Automaton hữu hạn xác định không chu trình tối thiểu sẽ gộp hai cây con có cấu trúc giống hệt nhau
- Trong một kho ngữ liệu mà 100 nghìn từ cùng kết thúc bằng khoảng 12 mẫu biến tố giống nhau, việc gộp này mang lại mức tiết kiệm bộ nhớ rất lớn
- Heuristic cốt lõi của trường hợp này là thay một cơ sở dữ liệu đa dụng tự ráp bằng một cấu trúc dữ liệu chuyên biệt, nhỏ và tĩnh chỉ làm đúng việc cần thiết, để đổi lấy giảm 300 lần bộ nhớ
Vai trò còn lại của giải pháp SQLite tạm thời và kích thước phân phối
- Quyết định dùng SQLite cách đó 9 tháng là một lựa chọn kiểu “xấu nhưng dễ” thay vì “không làm được điều tốt”, và nó thực sự hoạt động
- Vì đã hiểu B-tree của SQLite và Full Text Search extension, nên khi đó đây là giải pháp có thể thử nghiệm nhanh
- Phần mở rộng FTS đó vẫn được dùng cho một số tính năng ít dùng không có trong bản alpha
tsk v2.0.0, nhưng nếu nó làm hại đến mức dùng bộ nhớ hiện tại thì có thể sẽ bị loại bỏ hoàn toàn
- Bản Pro của
v2 đang được nhắm tới khoảng 20MB cho mọi thứ gộp lại, tức nhỏ hơn 3 lần so với bản miễn phí v1
tsk ban đầu khởi đầu là một chương trình TUI viết bằng Go, phát triển từ nguyên mẫu finstem dựa trên fzf, và có liên hệ với bài viết the highest-ROI program I’ve written so fartaskusanakirja trong tiếng Phần Lan có nghĩa là “pocket dictionary”, và tiêu chuẩn vẫn là: nếu nó không vừa cả trên một chiếc laptop cũ thì đó không còn là từ điển bỏ túi mà giống một cuốn Oxford cũ được biên dịch hơn- Có một mô-típ lặp lại là “giải bài toán hai lần cũng không sao”; thay vì dừng lại vì cảm giác tội lỗi rằng lẽ ra phải tìm ra một cách cài đặt tốt hơn sẵn có, đôi khi tự làm lại vài cái bánh xe sẽ giúp chạm tới giới hạn thực tế nhanh hơn
- Quan điểm này gắn với ý niệm “luyện tập” trong Caplanian view, và Do Ten Times as Much được đưa ra như một lời khuyên khó chịu nhưng hiệu quả
1 bình luận
Ý kiến trên Lobste.rs
Bản thân bài viết đã rất thú vị, và tôi thích cách họ áp dụng đúng công cụ cho đúng bài toán để đạt được mức cải thiện một chữ số, nhưng chú thích cuối bài còn gây ấn tượng hơn cả phần chính
Nó chỉ ra rất chính xác nỗi băn khoăn khiến ta chững lại vì cảm giác tội lỗi rằng công cụ mình đang làm có khi đã được ai đó hiện thực tốt hơn từ 30~40 năm trước. Nhưng đó là một cái bẫy, và ý rằng phải tự làm lại vài cái bánh xe thì mới chạm tới ranh giới của việc làm bánh xe thực sự rất thấm. Ở đa số lĩnh vực, bốn năm cái có lẽ là đủ; ngay cả với những lĩnh vực chặt chẽ như toán học hay khoa học máy tính, khoảng hai mươi ba cái cũng có thể đã đủ; và lập luận ở đây là chính những câu hỏi ném ra trong quá trình tự tay làm lại như vậy sẽ đưa ta tới tiền tuyến thực sự nhanh hơn nhiều so với việc chỉ học đơn thuần
Vì trước hết đã có một bản tham chiếu hoạt động được, nên việc tạo ra một bản cài đặt hiệu quả hơn để thay thế nó trở nên dễ dàng hơn
Nhưng khi nhìn vào các lời giải sẵn có, tôi thấy có quá nhiều phần mang theo mà mình không cần. Theo kinh nghiệm, tôi biết ý tưởng của mình đáng để theo đến cùng, nhưng vẫn cứ nghĩ liệu có phải mình đang bỏ sót điều gì không; đọc xong cái này thì tôi quyết định cứ làm thử. Dù thất bại thì cũng sẽ học được gì đó từ quá trình ấy
Quá tuyệt. Nó làm tôi nhớ đến Compressing Icelandic name declension patterns into a 3.27 kB trie
Khi làm bot Scrabble, tôi biết đến một cấu trúc dữ liệu liên quan là DAWG(Directed Acyclic Word Graph), và có vẻ nó khá phổ biến cho mục đích đó
Khác biệt chính với crate
fstdường như là nó không ánh xạ mỗi từ sang một số nguyên duy nhất. Tương tự, kích thước giảm mạnh và hiệu năng cũng tăng lên đáng kể. Về cơ bản, bot Scrabble phải lọc toàn bộ từ điển để tìm các từ khớp với những regex đơn giản như..cat.., nhưng trên thực tế còn phải xử lý mọi regex đơn giản có thể có từ bàn cờ hiện tại. Tác vụ từng mất cỡ 1 phút chờ đợi đã giảm xuống mức trễ không còn cảm nhận đượcBài được dẫn link cũng đáng đọc: https://burntsushi.net/transducers/
Cuối cùng thì
fstcũng là công cụ được dùng cho hỗ trợ tiếng Đức củasrgn, sau khi Andrew trực tiếp gợi ýĐây là cùng một không gian bài toán nén các tiền tố và hậu tố chung, và nó hoạt động cực kỳ tốt. Hơn nữa, vì là công cụ CLI nên cũng cần tối thiểu hóa chi phí khởi động, và crate
fsthỗ trợ nạp zero-copy, nên không có overhead runtime. FST được tạo ra ở thời điểm biên dịchThật sự rất hay, và sẽ tuyệt nếu cũng có thứ như thế này cho tiếng Đức và tiếng Anh. Từ ghép tiếng Đức đến giờ vẫn thường xuyên làm tôi bối rối