Fuzzy Seach (tìm kiếm "mờ"), hay còn hay được gọi là Approximate Search (tìm kiếm "xấp xỉ") là khái niệm để chỉ kỹ thuật để tìm kiếm một xâu "gần giống" (thay vì "giống hệt") so với một xâu cho trước.
Chẳng hạn như bạn bạn nhập vào ô tìm kiếm từ khoá "tran dc thag" để tìm kiếm về tên một người trong công ty, thì bằng cách sử dụng Fuzzy Search, ta có thể trả ra kết quả là "tran duc thang", bởi nó "gần giống" với từ khoá được nhập vào. Hay như khi vào Google bạn gõ "frangia vietnam" thì Google sẽ gợi ý cho bạn là "Did you mean: framgia vietnam".
Việc implement kỹ thuật Fuzzy Search vào hệ thống của bạn sẽ giúp cho người dùng dễ dàng tiếp cận được với nội dung của nó hơn, khi mà họ có thể tìm thấy được những thứ cần thiết, ngay cả khi họ không nhớ được chính xác nội dung mình muốn tìm kiếm là gì.
Trong bài viết này, mình sẽ giới thiệu về một số thuật toán cơ bản và đơn giản để thực hiện kỹ thuật Fuzzy Search. Tất cả chỉ dừng lại ở mức CỰC KỲ CƠ BẢN thôi nhé, nếu bạn đòi hỏi những thuật toán phức tạp và cao siêu thì mình cũng chịu, bởi với một số thuật toán cơ bản dưới đây thì mình cũng đã có thể implement được một package Fuzzy Search đủ dùng rồi.
Một số thuật toán
So sánh Substring
Đây có lẽ là cách đơn giản nhất, cách mọi người hay dùng nhất để tìm kiếm gần chính xác (mình cũng không biết nó có được coi là kỹ thuật Fuzzy Search hay không nữa =)), nhưng thôi cứ tạm giới thiệu qua ở đây).
Giả sử như người dùng nhập vào xâu A, bạn có thể trả về những kết quả có chứa từ A chẳng hạn.
Phép toán tìm kiếm bằng từ khoá LIKE trong sql cho phép chúng ta thực hiện điều này một cách dễ dàng.
Input: "thang" Acceptable results: "tran duc thang", "nguyen ngoc thang", "nguyen tat thang"
"Khoảng cách Levenshtein" (Levenshtein distance)
Thế nào là khoảng cách Levenshtein
"Khoảng cách Levenshtein" là thuật toán được đặt theo tên của một nhà khoa học người Nga, người đã nghiên cứu và phát triển nó vào năm 1965.
Khoảng cách Levenshtein là số bước ít nhất biến một xâu A thành xâu B thông qua 3 phép biến đổi:
- Thêm một ký tự
- Bớt một ký tự
- Thay đổi một ký tự
Ví dụ, một xâu là thang, có thể biến thành xâu tung thông qua 2 phép biến đổi là
- Loại bỏ chữ
h(thang->tang) - Đổi chữ
athành chữu. (tang->tung)
Như vậy, khoảng cách Levenshtein giữa 2 xâu thang và tung là 2.
Áp dụng Khoảng cách Levenshtein vào tìm kiếm xấp xỉ
Hiện tại, thuật toán tính Khoảng cách Levenshtein được sử dụng rất phổ biến và rộng rãi khi nói về Fuzzy Search. Về cách implement thuật toán, bạn có thể tham khảo trên mạng, search cái chắc có ngay ấy mà . Và vì độ nổi tiếng và tính hữu ích của thuật toán mà chắc ở mọi ngôn ngữ đều đã có người viết thư viện cho bạn để bạn có thể sử dụng luôn rồi đấy. Trong PHP còn có sẵn cả hàm levenshtein.
Đã có thể tính được khoảng cách Levenshtein giữa 2 xâu rồi, vậy tiếp theo, ta sẽ làm thế nào để thực hiện Fuzzy Search đây. Cách mình nghĩ đến là bạn tính khoảng cách giữa 2 xâu, sau đó so sánh khoảng cách đó với độ dài của xâu cần tìm kiếm, nếu nó nhỏ hơn một mức nào đó cho phép thì có thể coi xâu đang so sánh là "gần giống" với xâu tìm kiếm.
Input: "tran dc thag" Acceptable results: "tran duc thang", "tran duc thanh"
Xâu con chung dài nhất (Longest common substring)
Longest common substring (Xâu con chung dài nhất), như tên gọi của nó, đơn giản là một xâu chung dài nhất của hai (hay nhiều xâu). Chẳng hạn như ta có xâu "thag" và "tran duc thang" thì xâu con chung dài nhất của chúng sẽ là "tha".
Ta có thể áp dụng thuật toán tìm xâu con chung dài nhất của hai xâu, sau đó so sánh độ dài của của nó với độ dài của xâu cần tìm kiếm, nếu nó lớn hơn một giá trị định trước nào đó, thì có thể coi xâu đang so sánh là thoả mãn kết quả. (Còn về cách implement thuật toán Longest common substring, bạn có thể tham khảo tại wikipedia)
Mình thường hay sử dụng thuật toán tìm Longest common substring để bổ sung cho thuật toán Khoảng cách Levenshtein ở trên, bởi nếu lấy ví dụ là xâu nhập vào là "thag" chẳng hạn, thì rõ ràng khoảng cách Levenshtein của nó đến xâu "tran duc thang" là rất lớn, và không thể thoả mãn yêu cầu. Tuy nhiên, nếu dùng Longest common substring thì ta lại có thể coi "tran duc thang" là một kết quả hợp lệ.
Input: "thag" Acceptable results: "tran duc thang", "tran duc thanh"
Một package Fuzzy Search đơn giản cho PHP
Dưới đây là một package Composer mà mình viết, có sử dụng kết hợp các hàm và thuật toán đã đề cập ở trên để thực hiện kỹ thuật Fuzzy Search. Các bạn có thể tham khảo và sử dụng trong project của mình
- Github: https://github.com/wataridori/simple-fuzzy-search
- Install:
composer require wataridori/simple-fuzzy-search - About: Với Simple Fuzzy Search bạn có thể thực hiện Fuzzy Search từ một mảng đầu vào, theo một hoặc nhiều attribute nếu muốn. Các kết quả được coi là thoả mãn sẽ được sắp xếp lại. Ví dụ như khi bạn tìm kiếm từ
"trn duc thnh"thì kết quả"tran duc thanh"sẽ ở phía trước kết quả"tran duc thang". - Usage: Xem ví dụ tại đây
Nếu bạn muốn thực hiện Fuzzy Search ở phía Client, hãy tìm hiểu qua về Fuse, một thư viện nhỏ, nhưng cũng khá là mạnh mẽ.
Ngoài ra, bên cạnh các hàm và thuật toán được giới thiệu ở bài viết này, bạn cũng có thể tìm hiểu và sử dụng các thuật toán khác như Longest Common Subsequence, hay Soundex ... cũng rất là thú vị đấy.
Tran Duc Thang
Nguồn: viblo
