Skip to content

Khoảng cách Levenshtein và fuzzy query trong Elasticsearch

Posted on:October 20, 2017

Chào các bạn, quay lại với Elasticsearch, hôm nay chúng ta sẽ đến với một chủ đề khác trong fulltext search: fuzzy query.

Khi làm việc với Elasticsearch, hẳn là các bạn không lạ gì với fuzzy query, tuy nhiên nếu không hiểu về cách mà fuzzy query hoạt động, thì rất có thể việc search của bạn sẽ cho ra những kết quả như “trên trời rơi xuống” vậy. Vì vậy hiểu và nắm được nguyên lý của fuzzy query là một điều rất quan trọng trong fulltext search.

Khoảng cách Levenshtein

Để hiểu được nguyên lý của fuzzy query, trước hết ta phải nắm được về khoảng cách Levenshtein: Khoảng cách Levenshtein thể hiện khoảng cách khác biệt giữa 2 chuỗi ký tự.

Khoảng cách Levenshtein giữa chuỗi S1 và chuỗi S2 là số bước ít nhất biến chuỗi S1 thành chuỗi S2 thông qua 3 phép biến đổi là:

Ví dụ: Khoảng cách Levenshtein giữa 2 chuỗi “kitten” và “sitting” là 3, vì phải dùng ít nhất 3 lần biến đổi.

  1. kitten -> sitten (thay “k” bằng “s”)
  2. sitten -> sittin (thay “e” bằng “i”)
  3. sittin -> sitting (thêm ký tự “g”)

Rất rõ ràng, tuy nhiên vấn đề là làm thế nào để ta xác định được chuỗi biến đổi ngắn nhất đó. Về cơ bản đây là một bài lập trình thuật toán thuần tuý. Chúng ta có thể giải nó bằng quy hoạch động như sau:

def levenshtein(s1, s2):
    if len(s1) < len(s2):
        return Levenshtein(s2, s1)
    if len(s2) == 0:
        return len(s1)

    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row

    return previous_row[-1]
print levenshtein("kitten", "sitting")

Khoảng cách Levenshtein với Non-Ascii string

Trong hầu hết các ví dụ của lập trình, ta thông thường đều chỉ làm việc với tiếng Anh, kết quả thường đẹp tuyệt vời. Nhưng đời không như mơ, ngoài tiếng Anh, chúng ta còn thường xuyên gặp phải tiếng Việt, tiếng Nhật nữa, và liệu rằng những gì chúng ta tính toán trên kia có còn đúng nữa không ? chúng ta sẽ kiểm tra.

>>> print levenshtein("con đường", "cân đường")
2

(dafuq) không phải 1 sao ?

>>> print levenshtein("たいへん", "たいひひ")
3

(dafuq) không phải 2 sao ? Thật không thể tin nổi ? sao kết quả lại không như mong đợi ?

Nguyên nhân của điều này là do multibyte character. Với các kí tự trong các ngôn ngữ khác tiếng Anh, chúng ta đôi khi phải dùng nhiều hơn 1 byte để biểu diễn. Ví dụ như trên là ký tự “â, đ, ư, ờ” và các kí tự tiếng Nhật. Ta check thử từng kí tự:

>>> for i in "con đường": print ord(i),
>>> for i in "cân đường": print ord(i),
99 111 110 32 196 145 198 176 225 187 157 110 103
99 195 162 110 32 196 145 198 176 225 187 157 110 103
>>> for i in "たいへん": print ord(i),
>>> for i in "たいひひ": print ord(i),
227 129 159 227 129 132 227 129 184 227 130 147
227 129 159 227 129 132 227 129 178 227 129 178

Ra vậy, chúng đã lộ nguyên hình là các multibyte character, nhẩm tính thử, ta thấy các kết quả khoảng cách ta có như trên là hoàn toàn chính xác.

Fuzzy query trong Elasticsearch

Fuzzy query trong Elasticsearch cũng sử dụng khoảng cách Levenshtein, và cho phép ta config tham số fuzziness để cho kết quả phù hợp nhất với nhu cầu của mình:

Nếu trang web bạn đang sử dụng không phải là tiếng Anh, thì khi tìm kiếm fulltext search, có thể bạn sẽ phải chú ý điều chỉnh config giá trị fuzzy query hợp lý để đưa ra kết quả gần nhất với mong đợi. Nhiều khi AUTO chưa chắc đã là tốt.

Kết luận

Fulltext search rất linh hoạt, nhưng chính sự linh hoạt đó đôi khi khiến lập trình viên trở nên bối rối trong quá nhiều sự lựa chọn.

Enjoy coding !

Tham khảo