Levenshtein Automaton là gì?
Levenshtein Automaton là một cấu trúc toán học giúp máy tính tìm nhanh những từ gần giống một từ cho trước, mà không cần so sánh từng cặp từ một. Nó được xây dựng dựa trên khoảng cách Levenshtein, tức số lần chỉnh sửa tối thiểu để biến chuỗi này thành chuỗi khác. Ứng dụng kinh điển nhất của nó là tính năng “Did you mean?” của Google và fuzzy search trong Elasticsearch.
Nói đơn giản hơn: thay vì hỏi “từ này giống từ kia bao nhiêu phần trăm” với hàng triệu từ trong từ điển, mình chỉ cần chạy một phép kiểm tra rất nhẹ để biết từ nào nằm trong ngưỡng cho phép. Kiểm tra đó chính là Levenshtein Automaton.
Tại sao cần Levenshtein Automaton khi đã có Edit Distance?
Bài viết về Edit Distance đã giải thích cách tính số phép biến đổi giữa hai chuỗi. Vấn đề là cách tính đó chạy độ phức tạp O(m×n) cho mỗi cặp từ. Nếu từ điển có 500.000 từ và mình muốn tìm mọi từ cách từ “helo” tối đa 2 phép chỉnh sửa, phải chạy 500.000 lần tính toán đầy đủ.
Levenshtein Automaton đảo ngược vấn đề. Với từ gốc và ngưỡng khoảng cách N cho trước, mình xây một Automaton, hiểu nôm na là một cỗ máy trạng thái. Cỗ máy này “nuốt” từng ký tự của từ ứng viên và trả lời đúng sai ngay lập tức: từ này có nằm trong bán kính N phép chỉnh sửa hay không. Phép kiểm tra này nhanh gần bằng việc đọc từ đó một lần, không cần bảng quy hoạch động.
Đổi lại, câu hỏi thay đổi từ “khoảng cách bằng bao nhiêu” thành “có nằm trong ngưỡng không”. Với mục đích tìm kiếm mờ thì như vậy là đủ, vì mình thường chỉ cần mọi từ trong bán kính 1 hoặc 2 lỗi gõ.
Levenshtein Automaton hoạt động như thế nào?
Cách hình dung dễ nhất là nghĩ về trạng thái của một lưới so sánh. Khi tính Edit Distance thông thường, mình điền một lưới hai chiều. Với Automaton, mỗi trạng thái là một cột của lưới, và mỗi lần đọc một ký tự của từ ứng viên là chuyển sang cột tiếp theo.
Ba bước cơ bản:
Bước một, xây Automaton cho từ gốc “helo” với ngưỡng N = 2. Trạng thái ban đầu của cỗ máy ghi lại hàng đầu tiên của lưới: 0, 1, 2, 3, 4.
Bước hai, với mỗi từ ứng viên, cho cỗ máy đọc từng ký tự. Quy tắc chuyển trạng thái chính là công thức quen thuộc của Edit Distance: chèn, xóa, thay thế, mỗi lần đọc ký tự là sinh ra trạng thái mới.
Bước ba, sau khi đọc hết từ ứng viên, nếu giá trị nhỏ nhất trong trạng thái hiện tại không vượt quá 2 thì từ đó được chấp nhận. “hello”, “help”, “helot” đều nằm trong bán kính, còn “hotel” thì cách 3 phép nên bị loại.
Điểm hay là với ngưỡng nhỏ, số trạng thái khả dĩ của cỗ máy cũng rất nhỏ. Từ 4 ký tự ngưỡng 2 chỉ có vài chục trạng thái, và mọi từ ứng viên đều đi qua đúng bộ trạng thái đó.
Vì sao nó lại nhanh đến vậy?
Bí mật nằm ở chỗ Automaton được xây một lần cho từ gốc, rồi dùng lại cho cả từ điển. Thêm nữa, khi kết hợp với cây tiền tố, tức cấu trúc dữ liệu lưu từ điển theo dạng chữ cái đầu chung, mình có thể cắt tỉa cả nhánh.
Cụ thể: nếu cỗ máy đọc tiền tố “xyz” của một nhánh mà đã rơi vào trạng thái dead, nghĩa là dù phần sau thế nào cũng không thể nào về được ngưỡng 2, thì toàn bộ nhánh đó bị bỏ qua không cần đếm xểm. Đây chính là cách Lucene, engine đứng sau Elasticsearch và Solr, triển khai fuzzy query từ những năm 2010. Tốc độ tìm kiếm mờ tăng từ vài trăm lần trở lên so với duyệt từng từ.
Cách làm này gần giống tư duy của Longest Common Subsequence (LCS) ở chỗ cùng dùng quy hoạch động làm nền, nhưng Automaton biến bảng tính thành cỗ máy có thể tái sử dụng, và đó là khác biệt quyết định về hiệu năng.
So sánh với các phương pháp so khớp khác?
Jaro-Winkler cho ra điểm tương đồng 0 đến 1, phù hợp so khớp tên riêng ngắn. Nhưng để lọc cả từ điển triệu từ, mỗi phép tính vẫn phải chạy đầy đủ, không cắt tỉa được.
Soundex và Double Metaphone so khớp theo cách phát âm, rất tốt cho tên người nhưng mù với lỗi chính tả kiểu gõ thiếu chữ, thêm chữ.
Embedding bắt được tương đồng về ý nghĩa, nhưng “helo” và “hello” theo nghĩa ngữ nghĩa lại là hai vạn tám ngàn, và chạy vector trên toàn từ điển cũng tốn kém hơn nhiều. Levenshtein Automaton bám chắc vào mặt ký tự, rẻ, nhanh, chính xác cho lỗi gõ máy.
Mình tóm lại thế này: lỗi chính tả kiểu gõ phím thì dùng Automaton, sai chính tả theo cách phát âm thì dùng thuật toán âm học, còn sai ý nghĩa thì để embedding lo.
Ứng dụng thực tế cho người làm nội dung và bán hàng?
Ứng dụng quen thuộc nhất là gợi ý từ khóa tìm kiếm trên website. Khách gõ “ao thun namm” mà hệ thống trả về không có gì thì mất đơn. Fuzzy search dựa trên Levenshtein Automaton sẽ tự hiểu ý và trả về “ao thun nam”.
Với ai làm dữ liệu khách hàng, nó giúp gom các bản ghi gần trùng nhau trong quá trình khử trùng lặp dữ liệu, ví dụ “Nguyen Van An” và “Nguyen Van Aan”. Lưu ý nhỏ cho tiếng Việt: nên chuẩn hóa bỏ dấu hoặc tách thanh trước khi so, vì “Hà” và “Ha” theo Edit Distance đã tốn 1 phép rồi.
Các công cụ dựng sẵn: Elasticsearch và OpenSearch có fuzzy query, Lucene là thư viện gốc, còn Python có gói python-Levenshtein kèm hàm tìm trong ngưỡng. PostgreSQL cũng hỗ trợ fuzzy matching qua extension pg_trgm, bên trong dùng tư duy tương tự.
Có hạn chế gì cần biết?
Hạn chế đầu tiên là Automaton chỉ trả lời trong ngưỡng hay ngoài ngưỡng, không cho điểm số mịn để xếp hạng. Muốn xếp kết quả theo độ giống nhau thì vẫn phải tính lại khoảng cách cho nhóm ứng viên nhỏ đã lọc ra, thường chỉ còn vài chục từ nên nhanh.
Hạn chế thứ hai là ngưỡng lớn làm cỗ máy phình to rất nhanh. Thực tế người ta hầu như chỉ dùng ngưỡng 1 hoặc 2, đủ bao phủ hầu hết lỗi gõ thông thường.
Cuối cùng, nó không hiểu ngữ cảnh. “Hà Nội” gõ thành “Ha Noi” khớp hoàn hảo, nhưng “bank” và “bankk” khớp cả hai từ “bank” và “banks” với cùng khoảng cách, chọn từ nào đúng ý người dùng là việc của tầng xếp hạng phía sau.
Theo góc nhìn cá nhân của mình, Levenshtein Automaton là một ví dụ đẹp về việc giải quyết bài toán hiệu năng bằng cách thay đổi câu hỏi thay vì tối ưu câu trả lời. Thay vì hỏi khoảng cách chính xác là bao nhiêu cho mọi cặp từ, chỉ cần hỏi đủ hay không đủ, và cả từ điển triệu từ bỗng trở nên nhẹ tênh. Bài học tư duy này đáng giá hơn cả thuật toán.
Kết luận
Levenshtein Automaton là phiên bản công nghiệp của Edit Distance: xây một lần, chạy rất nhiều lần, cắt tỉa cả nhánh từ điển không liên quan. Nếu bạn đang làm tìm kiếm trên website, làm sạch dữ liệu khách hàng, hay đơn giản tò mò cách “Did you mean?” hoạt động, đây là thuật ngữ đáng nằm trong sổ tay. Muốn đi sâu hơn, hãy đọc về SymSpell, một hướng tiếp cận khác cũng rất nhanh dựa trên tiền xử lý từ điển.
