Dùng khoảng cách Levenshtein trong MySQL

Khoảng cách Levenshtein đo sự khác biệt giữa hai từ, bằng cách đếm các thay đổi tối thiểu các ký tự để một từ trờ thành từ còn lại. Các thay đổi ký tự được dùng là thêm, bớt hay thay thế.

Thí dụ:

siu vịt -> siêu việt (thêm 2 ký tự)
Thằng nein -> thanh niên (thay thế g thành h, thêm bớt chữ i)

MySQL không có hàm dùng kỹ thuật levenshtein nên chúng ta phải tạo UDF. Mặc dù có thể viết UDF bằng ngôn ngữ MySQL nhưng tốc độ thực thi rất chậm, tính bằng giây hoặc phút. Một số hàm levenshtein được viết sẵn bằng ngôn ngữ C, tải về tại đây

Vấn đề còn lại là làm sao biên dịch các hàm UDF này trên RPi, tất nhiên MySQL đã được cài đặt sẵn.

MySQL được cài đặt bằng apt-get nên không có các file nguồn MySQL cần thiết cho việc biên dịch levenshtein.c

Lệnh sau đây tải file nguồn MySQL v5.5 và giải nén

sudo aptitude install mysql-source-5.5
tar -xzf /usr/src/mysql/mysql-source-5.5.tar.gz

Giả sử đang ở thư mục /root thì thư mục nguồn được giải nén là /root/mysql-5.5

Chép levenshtein.c vào thư mục /root, câu lệnh biên dịch tương ứng là

gcc -o /usr/lib/mysql/plugin/levenshtein.so -shared levenshtein.c -I ./mysql-5.5/include/ -I ./mysql-5.5/builddir/include/

Có tất cả 4 hàm levenshtein trong file levenshtein.so

CREATE FUNCTION levenshtein RETURNS INT SONAME 'levenshtein.so';
CREATE FUNCTION levenshtein_k RETURNS INT SONAME 'levenshtein.so';
CREATE FUNCTION levenshtein_ratio RETURNS REAL SONAME 'levenshtein.so';
CREATE FUNCTION levenshtein_k_ratio RETURNS REAL SONAME 'levenshtein.so';

Các hàm ratio tính theo công thức 1 – levenshtein (s1, s2) / max (length(s1), length(s2)), kết quả là một giá trị <= 1. Có thể nhân giá trị này với 100 để có độ chính xác gần đúng của 2 từ tính theo %

Mở mySQL với user root và chạy các câu lệnh trên, chúng ta được 4 hàm UDF levenshtein.

Thí dụ về việc sử dụng:

mysql> select levenshtein('siu vit', 'sieu viet');
+-------------------------------------+
| levenshtein('siu vit', 'sieu viet') |
+-------------------------------------+
|                                   2 |
+-------------------------------------+
1 row in set (0.00 sec)

mysql> select levenshtein('thang nein', 'thanh nien');
+-----------------------------------------+
| levenshtein('thang nein', 'thanh nien') |
+-----------------------------------------+
|                                       3 |
+-----------------------------------------+
1 row in set (0.00 sec)

Sửa lại code một chút để ratio có tỉ lệ % thay vì một giá trị <= 1

mysql> select levenshtein_ratio('thang nein', 'thanh nien');
+-----------------------------------------------+
| levenshtein_ratio('thang nein', 'thanh nien') |
+-----------------------------------------------+
|                                            70 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select levenshtein_ratio('siu vit', 'sieu viet');
+-------------------------------------------+
| levenshtein_ratio('siu vit', 'sieu viet') |
+-------------------------------------------+
|                         77.77777777777779 |
+-------------------------------------------+
1 row in set (0.00 sec)

Như vậy nếu ta cần tra cứu CSDL MySQL với độ chính xác >= 70% thì tìm được cả thanh niên và siêu việt