Fuzzy Matching
Kỹ thuật tìm kiếm tìm các chuỗi tương tự thay vì khớp chính xác. Xử lý lỗi chính tả và biến thể chính tả.
Fuzzy matching là kỹ thuật tìm kiếm tìm các chuỗi có độ tương tự trên một ngưỡng nhất định thay vì yêu cầu khớp chính xác. Nó xử lý lỗi chính tả, biến thể chính tả, viết tắt và các sự không nhất quán văn bản khác, và được sử dụng rộng rãi trong công cụ tìm kiếm, tính năng tự động hoàn thành, kiểm tra chính tả và làm sạch dữ liệu. Đây là công nghệ rất thực tế cho phép người dùng tìm thông tin cần thiết ngay cả khi không nhớ chính xác cách viết.
Thuật toán tiêu biểu nhất là khoảng cách Levenshtein (khoảng cách chỉnh sửa), tính toán số lượng tối thiểu các phép chèn, xóa và thay thế cần thiết để biến đổi một chuỗi thành chuỗi khác. Ví dụ, khoảng cách chỉnh sửa giữa "kitten" và "sitting" là 3. Khoảng cách chỉnh sửa nhỏ hơn cho thấy độ tương tự chuỗi lớn hơn. Sách thuật toán tìm kiếm cung cấp kiến thức có hệ thống.
Ngoài khoảng cách Levenshtein, nhiều thuật toán khác nhau tồn tại cho các mục đích khác nhau: độ tương tự n-gram (chia chuỗi thành các chuỗi con n ký tự để so sánh), khoảng cách Jaro-Winkler (nhấn mạnh khớp ở đầu chuỗi) và độ tương tự ngữ âm (Soundex, Metaphone). Jaro-Winkler phù hợp cho khớp tên, trong khi Soundex được dùng để tìm từ tiếng Anh có phát âm tương tự. Đối với văn bản tiếng Nhật, so sánh dựa trên cách đọc (furigana) và phiên âm La-tinh cũng được sử dụng.
Về triển khai, fuzzy query của Elasticsearch (dựa trên khoảng cách chỉnh sửa), extension pg_trgm của PostgreSQL (dựa trên trigram) và thư viện fuse.js của JavaScript giúp tích hợp tìm kiếm mờ vào ứng dụng web tương đối đơn giản. Trong Elasticsearch, chỉ định fuzziness: "AUTO" tự động điều chỉnh khoảng cách chỉnh sửa cho phép dựa trên độ dài chuỗi truy vấn.
Khi triển khai tìm kiếm mờ, cấu hình ngưỡng là rất quan trọng. Đặt ngưỡng tương tự quá thấp trả về nhiều kết quả không liên quan (false positive), trong khi đặt quá cao bỏ lỡ kết quả nên khớp (false negative). Ngoài ra, đối với chuỗi ngắn, ngay cả sự khác biệt một ký tự cũng gây biến động đáng kể về độ tương tự, vì vậy khoảng cách chỉnh sửa cho phép nên giảm cho chuỗi ngắn hơn. Sách nhập môn truy xuất thông tin cung cấp thêm ngữ cảnh.
Từ góc độ đếm ký tự, fuzzy matching chấp nhận sự khác biệt nhỏ về số ký tự (1-2 ký tự), hữu ích khi không cần khớp chính xác số ký tự. Ví dụ, khi hiển thị gợi ý nhập liệu trong biểu mẫu có giới hạn ký tự, áp dụng fuzzy matching cho đầu vào một phần của người dùng có thể hiển thị các ứng viên phù hợp ngay cả khi có lỗi chính tả. Hiểu mối quan hệ giữa độ dài chuỗi và độ tương tự trực tiếp góp phần cải thiện độ chính xác tìm kiếm.