Từ 3 GB xuống 10 MB: Tối ưu hóa dữ liệu với Finite State Transducer

Từ 3 GB xuống 10 MB: Tối ưu hóa dữ liệu với Finite State Transducer

Trong quá trình phát triển phần mềm, việc tối ưu hóa bộ nhớ thường là một thách thức lớn, đặc biệt khi làm việc với các tập dữ liệu phức tạp. Gần đây, một trường hợp nghiên cứu thú vị đã chứng minh sức mạnh của việc lựa chọn cấu trúc dữ liệu đúng đắn: giảm dung lượng của một cơ sở dữ liệu từ điển từ 3 GB xuống chỉ còn 10 MB (mức giảm 300 lần) nhờ sử dụng Finite State Transducer (FST).

Thách thức với ngôn ngữ Phần Lan

Câu chuyện bắt đầu với Taskusanakirja (tsk), một ứng dụng từ điển Phần Lan - Anh hỗ trợ tính năng tìm kiếm tăng dần (incremental search-as-you-type). Về cơ bản, vấn đề này được giảm xuống thành bài toán tìm kiếm tiền tố (prefix search), mà giải pháp kinh điển thường là sử dụng cấu trúc dữ liệu Trie.

Tuy nhiên, Phần Lan là một ngôn ngữ kết dính (agglutinative) cực kỳ phức tạp. Một từ gốc có thể có hơn một trăm dạng biến thể khác nhau khi thêm các đuôi từ. Với số lượng từ vựng lên tới hàng chục triệu, cấu trúc Trie truyền thống đã bộc lộ hạn chế. Nó tiêu tốn quá nhiều bộ nhớ (khoảng 50 MB cho 400.000 mục) và không thể mở rộng để xử lý hàng chục triệu biến thể mà vẫn đảm bảo hiệu suất trên các máy tính cấu hình thấp.

Cách tiếp cận đầu tiên: Trie và SQLite

Trong phiên bản đầu tiên viết bằng ngôn ngữ Go, tác giả đã sử dụng Trie kết hợp với việc ghi nhớ (memoization) các tổ hợp ký tự ngắn để tối ưu hóa tốc độ. Mặc dù hoạt động tốt với số lượng từ hạn chế, nhưng giải pháp này sụp đổ khi cần xử lý toàn bộ các biến thể của từ Phần Lan.

Cảm thấy bế tắc, tác giả đã chọn giải pháp "dễ nhưng không tốt": chuyển các dữ liệu biến tố sang một cơ sở dữ liệu SQLite riêng biệt với tiện ích mở rộng Full Text Search (FTS). Giải pháp này hoạt động mà không gây độ trễ đáng kể, nhưng nó yêu cầu người dùng phải tải về một tệp dữ liệu nặng tới 3 GB. Đây rõ ràng không phải là một giải pháp lý tưởng cho một ứng dụng từ điển bỏ túi.

Giải pháp đột phá: Finite State Transducer (FST)

Sau chín tháng trau dồi kỹ năng kỹ sư phần mềm, tác giả đã quyết định viết lại dự án bằng ngôn ngữ Rust. Nguồn cảm hứng đến từ BurntSushi (Andrew Gallant), tác giả của công cụ ripgrep nổi tiếng, người từng viết về việc lập chỉ mục 1,6 tỷ khóa bằng Automata và Rust.

Finite State Transducer (FST) về cơ bản là một máy trạng thái hữu hạn. Khác với Trie chỉ chia sẻ tiền tố giữa các từ, FST có khả năng nén cả tiền tố và hậu tố. Trong tiếng Phần Lan, có một số lượng nhỏ các đuôi từ phổ biến được lặp lại rất nhiều lần trong toàn bộ kho từ vựng. Do đó, FST là giải pháp hoàn hảo để loại bỏ sự dư thừa dữ liệu này.

Kết quả thật ngoạn mục: toàn bộ dữ liệu曾被 nén xuống chỉ còn 10 MB.

"Một mức giảm 300 lần về dung lượng bộ nhớ."

Bài học kinh nghiệm

Một điểm đáng chú ý trong câu chuyện này là triết lý phát triển phần mềm. Việc lựa chọn giải pháp SQLite ban đầu dù không tối ưu về dung lượng, nhưng nó đã giúp ứng dụng hoạt động được ngay lập tức. Nó cho phép tác giả hiểu rõ hơn về vấn đề và dữ liệu của mình trước khi tìm ra giải pháp tối ưu hơn.

Đôi khi, việc giải quyết vấn đề hai lần — một lần bằng giải pháp nhanh, và một lần bằng giải pháp tối ưu — là cách tiếp cận hiệu quả nhất để đạt được kết quả xuất sắc. Phiên bản Pro mới của tsk hiện có dung lượng khoảng 20 MB, nhỏ hơn rất nhiều so với phiên bản miễn phí trước đó, chứng minh rằng việc đầu tư vào kiến trúc dữ liệu là hoàn toàn xứng đáng.