Fuzzy search là gì? Những điều cần biết về thuật toán fuzzy

Chưa cần phải vội vàng tìm hiểu Fuzzy search hoặc thuật toán Fuzzy nha. Anh em cứ thong thả, nhâm nhi ly trà ta bắt đầu với câu chuyện nho nhỏ.

Tìm kiếm bằng Google, ôi dào, giờ tới cụ ông ngoài 70 cũng biết dùng, cụ không gõ được thì cụ nói với Google Assitance, ai mà chả xài được. Mà cái sự đời, già xài được thì trẻ xài được. Thằng Tèo học IT cũng thế, năm nay mới có đôi mươi, cậy mắt sáng nên nó ứ thèm dùng voice như ông nó. Ngồi cả ngày như cô hồn, chả buồn mồm cất lên câu nào. Tìm gì nó cũng gõ, tìm chỗ đá bida, nó gõ. Tìm nơi đá ph*, à nhầm đá gà, nó cũng gõ. Hot như ChatGPT nó cũng gõ nốt.

Gõ từ sáng tới tầm chập choạng chiều thì nó mới sực nhớ là nguyên ngày chưa ăn gì. Mà giờ lỡ xoá app shoppe đi rồi, lại lóc cóc ngồi gõ tìm ăn cơm gà. Đã lâu rồi nó chưa ăn cơm gà miền trung. Bao kí ức tuổi thơ ùa về, đĩa cơm gà mẹ nấu biết bao chan chứa tình yêu thương của mẹ.

Ý lộn, đã là chị Google thì phải nhẹ nhàng chứ, xin sửa lại thành “Tèo, có phải tục tưng muốn ăn cơm gà miền trung không nè?”. Chị Google thỏ thẻ đáp.

1. Quyết chí

Quên cả đơn đói cồn cào, Tèo quyết tâm tìm hiểu xem làm sao, cơ sự thế nào, nguyên nhân do đâu mà chị Google lại khéo léo thế. Chị biết cả mình thích ăn cơm gà, mà tìm cơm gà chứ không phải cơm ag, ab.

Phen này quyết tìm ra cái bí mật ẩn sâu chôn dấu của chị Google. Tìm kiếm thêm hồi nữa với chị Google thì Tèo tìm ra từ khoá Fuzzy.

Ok, kết thúc lãng xẹt, ta vào bài hôm nay. Thuật toán Fuzzy search!

2. Fuzzy search là gì?

Vẫn là phân tích từ ngữ trước tiên, muốn nhớ lâu thì anh em nên nhớ từ. Bản thân từ khoá của thuật toán hay bất cứ định nghĩa nào đều có ý nghĩa hết.

Điển hình như Fuzzy, từ này thì có nhiều nghĩa, nhưng một trong số đó là nghĩa ngà ngà. Không phải ngà voi nha mấy anh hai. Ngà này là ngà trong ngà say rượu ấy.

Đâu suy luận xíu, à vậy tên cái thuật toán nó đùa nhau ghê. Say rượu thì làm sao gõ đúng được, mà dựa theo cái ví dụ trên chẳng phải là ông say rượu sẽ gõ tìm kiếm sai sao?

Tèo đọc tới đây có vẻ hơi cay, nhưng không sao. Cứ cho là tên cái thuật toán nó troll đi, cũng quyết chí tìm hiểu xem nó là cái gì?.

Ok định nghĩa

Fuzzy search is the process of finding strings that approximately match a given string. A fuzzy matching search algorithm will be able to find relevant strings even if your original string contains typo errors and misspellings. Fuzzy search là quá trình tìm kiếm các chuỗi gần khớp với một chuỗi đã cho. Thuật toán tìm kiếm Fuzzy sẽ tìm ra được các chuỗi không liên quan ngay cả khi chuỗi ban đầu có chứa lỗi đánh máy và lỗi chính tả.

Ngon, vậy là gõ sai nhờ Fuzzy search vẫn có kết quả. Mà còn suggest ra được kết quả gần đúng cơ. Thuật toán đúng ngon.

Xem thêm việc làm Tuyển dụng Java hấp dẫn tại TopDev

3. Sử dụng Fuzzy matching khi nào?

Fuzzy matching được sử dụng trong nhiều ứng dụng khác nhau. Chỉ riêng công cụ tìm kiếm mà nói thì công cụ tìm kiếm nào cũng có fuzzy matching. Thuật toán này giúp giải quyết sự phức tạp của chính tả.

Với các chị em có butter finger (tay vụng) thì fuzzy matching là vị cứu tinh. Gõ sai mà cũng hiểu thì còn gì nói nữa, quá tuyệt vời. Đôi khi fuzzy matching cũng được các công cụ tìm kiếm sử dụng để thu thập tìm kiếm người dùng. Tuy nhiên dữ liệu tìm kiếm này không đáng tin cậy (có thể do tiếng địa phương hoặc sự kết hợp giữa âm thanh và ngữ âm).

4. Thuật toán đứng sau Fuzzy search

Fuzzy Search là tên thuật toán phổ biến và thường được sử dụng. Nhưng kì thực thuật toán giúp Fuzzy có thể tìm kiếm đúng với từ khoá nhập sai lại không phải tên là Fuzzy.

Có tới 6 thuật toán được sử dụng cho Fuzzy Matching. Nội dung bài viết này chỉ chú trọng phân tích thuật toán Naive Algorithm

4.1 Naive Algorithm

Trong số các thuật toán tìm kiếm theo pattern (theo mẫu) thì Naive Algorithm là thuật toán thường được dùng phổ biến nhất. Thuật toán này tìm kiếm tất cả các ký tự của chuỗi chính trong mẫu (pattern) được cung cấp. Bằng cách kiểm tra chuỗi nhập vào, ta có thể tìm thấy các chuỗi con (substring) ở trong đó.

Ngoài Naive, còn có các thuật toán khác được sử dụng. Tên của các thuật toán đó bao gồm:

• Hamming Distance Algorithm
• Levenstein Distance Algorithm
• N-gram Algorithm
• BK Tree Algorithm
• Bitap Algorithm

5. Ví dụ về Naive Algorithm

Thuật toán Naive String kiểm tra tất cả các vị trí có thể có của pattern p[1..m] (m đây anh em hiểu là character index nha, từ 1 tới m, pattern p là chuỗi có độ dài m). Đem ra so sánh với mẫu string input vào t[1..n] (chuỗi string có độ dài n, t là input nhập vào).

Rồi, nhảy vào ví dụ luôn cho nó dễ hiểu vòng for ha.

// TEXT tìm kiếm
ACAACAA 
// PATTERN tìm kiếm
AAC

Lúc này giá trị n là length(T – Text) là 6. Giá trị m là length (P – Pattern) là 3. Cùng duyệt qua vòng for để tìm xem pattern xuất hiện ở đâu trong chuỗi text.

5.1 Step by step

Lần đầu tiên, P[0] == T[0] ok pass, nhưng ký tự thứ hai thì C với A lại không khớp.

Nếu đã không khớp thì quay lại kiểm tra kí tự đầu tiên của P, với ký tự thứ hai của T, bắt đầu tại chính chỗ không khớp.

Lần thứ hai này vẫn không khớp do A khác C. Lắc đầu quẹo phải phát nữa qua tới T[2]

Lạy trúa khớp đây rồi, xanh rì như mạ mới gieo. Mà quên còn khúc cuối

Khúc cuối thì lại không khớp rồi ha.

6. Tổng kết

Nội dung bài viết này giới thiệu về Fuzzy Search và thuật toán cơ bản nhất là Naive để tìm ra chuỗi con gần đúng nhất. Tuy nhiên thuật toán Naive còn tồn tại nhiều khuyết điểm như không thể tìm ra các chuỗi nếu như vị trí không liền mạch. Kiểu AABC mà BC ở phía trên chuỗi tìm kiếm lại không đứng cạnh nhau.

insertion:     bat → boat
deletion:      coat → cot
substitution:  coat → cost

Bài viết sau sẽ làm rõ hơn cho anh em vấn đề này.

7. Tham khảo

• What is fuzzy search?
• Levenshtein distance – Wikipedia
• Clean code – Tất cả từ một cái tên

Cảm ơn anh em đã đọc bài – Thank you for your time – Wish you all the best – Happy coding!

Tác giả: Kiên Nguyễn

Xem thêm:

• Giới thiệu Aspect Oriented Programming (AOP)
• Ngôn ngữ lập trình bậc thấp là gì?
• Hướng dẫn kết nối PHP với SQL Server

Tìm việc làm IT mọi cấp độ tại TopDev