Tìm kiếm toàn văn MySQL mờ

Fuzzy Seach [tìm kiếm "mờ"], hay còn được gọi là Tìm kiếm gần đúng [tìm kiếm "xấp xẩm"] là khái niệm chỉ dành cho kỹ thuật để tìm kiếm một xâu "gần giống" [thay vì "giống như"]

Qua. Thắng Trần Đức

Đây là câu mở đầu của bài viết Tìm kiếm mờ đơn giản Đọc đến đây chắc các bạn cũng biết rằng bài viết này mình sẽ viết về Tìm kiếm mờ. Tại lâu quá không viết bài nào nên mình cũng không biết nên mở đầu ra sao nữa. Mong các bạn thông cảm

.

Nếu bạn chưa biết về Fuzzy Seach có thể đọc bài viết ở link trên. Tuy không chắc chắn là đầy đủ nhưng vẫn giúp bất kỳ phần nào cho việc tìm hiểu. Trong bài viết này mình sẽ thử tự tạo Fuzzy Seach áp dụng thuật toán Khoảng cách Levenshtein với khoảng cách tối thiểu là 1 và sẽ kết hợp với tìm kiếm toàn văn để tìm kiếm đối tượng tương đối chính xác mà mình mong muốn thứ hai

Open post

Khi làm việc nhiều với Sql và gần đây là mysql mình tự hỏi một điều rằng

Tại sao các quản trị viên không thêm những thuật toán tìm kiếm để giúp đỡ cho những culi của làng code như mình nhỉ?. Nghĩ đến đây mình mủi lòng tự nhủ à thì có mà dùng là được rồi, được voi đòi tiên mà để làm gì

Chắc chắn các bạn biết rằng trong Sql có 1 chức năng là Công dụng của nó như sau

• Soundex là một thuật toán âm thanh để liệt kê các từ theo âm sắc, theo cách phát âm của tiếng Anh
• Mục đích là mã hóa những từ có cùng cách phát âm qua các đặc trưng giống nhau, từ đó người ta có thể tìm được một từ nào đó dù có sai sót nhỏ trong mô tả chính xác từ đó

Giúp ta có thể sử dụng SOUNDEX kết hợp với tìm kiếm toàn văn một cách dễ dàng mình sẽ làm ví dụ trong một bài viết gần nhất

.

Nhưng đây chắc chắn không phải là những gì mình muốn chương trình của mình thực hiện. Mình muốn có một thuật toán thực sự tồn tại và nếu được thì kết hợp luôn cả Levenshtein. Qua tìm ngăn tủ thì mình thấy mysql không có những tính năng này mà muốn sử dụng thì ta phải sử dụng những máy chủ tìm kiếm khác như SOLR hoặc Elaticsearch. Việc sử dụng 1 chương trình tìm kiếm thứ 3 làm cho phần mềm không mát mẻ

Nên mình quyết định tự tạo một phương pháp cho bản thân mình =]]. Nếu bạn đã đọc bài viết về Fuzzy Seach của anh Thắng thì sẽ biết rằng trong PHP có 1 hàm mang tên levenshtein nhưng trong ngôn ngữ khác thì hoàn toàn không. Do vậy mình sẽ làm từ đầu đến hết tất cả các giai đoạn.

Thân bài

B1. Khoảng cách Levenshtein là gì

Khoảng cách Levenshtein là một số liệu chuỗi để đo sự khác biệt giữa hai chuỗi. Một cách không chính thức, khoảng cách Levenshtein giữa hai từ là số lần chỉnh sửa một ký tự tối thiểu [i. e. chèn, xóa hoặc thay thế] cần thiết để thay đổi từ này sang từ khác

Qua. wikipedia. tổ chức

Để hiểu thêm xin mời tham khảo ví dụ này.

B2. Ý tưởng cho bài toán

Khoảng cách tối thiểu là 1 ta sẽ sử dụng 3 phép biến đổi của Levenshtein để tạo ra những từ như sau. VD. Từ "Fuzzy", with a " _ " tương ứng là 1 ký tự hoặc cụm ký tự

1, Add an character

2, Bớt một ký tự

3, Change a character

Do đó tổng cộng ta có 16 cụm từ cần phải tìm kiếm để có kết quả chính xác nhất với mong muốn. Từ đây ta có thể viết được 1 câu truy vấn như sau

SELECT *  FROM table_name WHERE
`name` LIKE '%_fuzzy%' OR
`name` LIKE '%f_uzzy%' OR
`name` LIKE '%fu_zzy%' OR
`name` LIKE '%fuz_zy%' OR
`name` LIKE '%fuzz_y%' OR
`name` LIKE '%fuzzy_%' OR
`name` LIKE '%uzzy%' OR
`name` LIKE '%fzzy%' OR
`name` LIKE '%fuzy%' OR
`name` LIKE '%fuzz%' OR
`name` LIKE '%_uzzy%' OR
`name` LIKE '%f_zzy%' OR
`name` LIKE '%fu_zy%' OR
`name` LIKE '%fuz_y%' OR
`name` LIKE '%fuzz_%'

Khi nhìn số từ cần tìm ta có thể thấy ngay chúng ta cần [3 * n] + 1 từ so sánh [với n là độ dài của từ cần tìm]. That is in the contract of ta use the distance of the minimum. Còn nếu gọi khoảng cách ta dùng là d thì ta phải có ít nhất là [3∗n]d[3 * n]^d[3∗n]d từ.

Đó là một con số rất lớn, Từ đây mình nhận ra rằng việc mình đang làm thật sự là ngu ngơ và ngây thơ

. Thôi kệ làm tiếp vậy.

Từ câu Sql ở bên trên

bạn thấy việc tìm kiếm này tổng quát hơn Chắc chắn việc chỉ sử dụng câu truy vấn thông thường như sau.

SELECT * FROM table_name WHERE `name` LIKE '%fuzzy%'

Làm sao để tạo ra một câu truy vấn dài ngoằng như trên

Hãy cùng suy nghĩ nào.

B3. Suy nghĩ tiếp

Chỗ này mình viết mã giả bằng js để hiển thị màu mè cho dễ nhìn

.

Ở B2 ta đã xác định câu hỏi cần tạo ra. Nhìn vào câu này ta có thể dễ dàng nghĩ đến giải pháp cộng chuỗi để tạo ra nó như sau

var list_regex = ["_fuzzy", "f_uzzy",..., "fuzz_"];
var sql = "SELECT *  FROM table_name WHERE ";
list_regex.forEach[ function[el] {
    if [el == list_regex.pop[]]
        sql += `name LIKE '% ${el} %'`;
    else
        sql += `name LIKE '% ${el} %' OR`;
}

Đó là ta có 1 đoạn mã giả thật là. Đến đây nếu bạn để ý rằng ta đã có 1 thuật toán tìm kiếm và tự đánh chỉ mục cho dữ liệu rất chi là chất chứa trong Sql đó là Tìm kiếm toàn văn. Có thể tóm tắt là nếu bạn tìm kiếm 1 cụm từ bằng tìm kiếm toàn văn, thì nó sẽ sinh ra cho bạn 1 câu truy vấn tương tự như trên. Từ đây công việc của chúng ta dễ dàng hơn vài phần

Biến mảng từ cần tìm thành 1 câu

var list_regex = ["_fuzzy", "f_uzzy",..., "fuzz_"];
var text_search = list_regex.join[' '];

Sau đó dùng full text search ta có 1 câu truy vấn như sau

SELECT name FROM table_name WHERE MATCH [name] AGAINST [text_search IN BOOLEAN MODE];

Rằng từ đây bạn không cần phải suy nghĩ để viết ra câu truy vấn dài kia làm gì. Cái gì khó có thể sử dụng mấy cái có sẵn cho đời thêm vui

.

B 4. Viết hàm ngốc nghếch tạo ra cụm từ cần tìm kiếm

Đây là bước mất công suy nghĩ nhất của bài viết này.

function my_Levenshtein_level_one[word, key] {
    var list_regex = [];
    var lg = word.length;
    
    for [var i = 0; i