Elasticsearch Bài học 31: Fuzzy Search - Tìm kiếm mờ (Sai chính tả vẫn ra kết quả đúng)

Ở bài trước, tôi có hơi "cầm đèn chạy trước ô tô" khi báo rằng chúng ta đã kết thúc Phần 5. Thực tế, tầng Query DSL vẫn còn một số bí kíp sinh tử mà nếu bỏ qua, trải nghiệm tìm kiếm của hệ thống E-commerce sẽ cực kỳ tệ. Một trong số đó là bài toán Sai chính tả.

Khách hàng trên Hasaki thường xuyên gõ vội trên điện thoại:

• Định gõ "Sữa rửa mặt", nhưng lại gõ thành "Sữa rủa mặt".

• Định gõ "Cetaphil", nhưng lại gõ thành "Cetapil".

• Định gõ "iPhone", nhưng ngón tay trượt thành "ipohne".

Nếu bạn dùng match query thông thường, kết quả trả về sẽ là 0. Điều này đồng nghĩa với việc bạn vừa đánh rơi hàng ngàn đơn hàng mỗi ngày. Để biến nguy thành cơ, Elasticsearch trang bị tính năng Fuzzy Search (Tìm kiếm mờ).

1. Bản chất Toán học: Khoảng cách Levenshtein (Edit Distance)

Để biết một từ bị gõ sai có "gần giống" với từ gốc hay không, Elasticsearch sử dụng một thuật toán nổi tiếng trong Khoa học máy tính mang tên Khoảng cách Damerau-Levenshtein (Edit Distance).

Khoảng cách này được định nghĩa là: Số bước thao tác (chỉnh sửa) tối thiểu để biến chuỗi A thành chuỗi B.

Có 4 loại thao tác được tính là 1 bước (1 đơn vị khoảng cách):

1. Thay thế (Substitution): kem $\rightarrow$ kam (Khoảng cách = 1)

2. Thêm vào (Insertion): kem $\rightarrow$ kema (Khoảng cách = 1)

3. Xóa bớt (Deletion): kem $\rightarrow$ ke (Khoảng cách = 1)

4. Đổi chỗ 2 ký tự liền kề (Transposition): sony $\rightarrow$ soyn (Khoảng cách = 1)

Ví dụ: Khách gõ "cetapil". Trong Inverted Index của bạn có từ "cetaphil". Để biến "cetapil" thành "cetaphil", ta chỉ cần Thêm chữ h. Vậy khoảng cách Levenshtein ở đây là 1.

2. Áp dụng Fuzziness vào Query DSL

Cách tốt nhất để sử dụng Fuzzy Search không phải là gọi một câu fuzzy query độc lập, mà là nhúng trực tiếp tham số fuzziness vào bên trong câu lệnh match quen thuộc.

Cú pháp:

JSON

GET products/_search
{
  "query": {
    "match": {
      "name": {
        "query": "sữa rủa mặt cetapil",
        "fuzziness": 1 
      }
    }
  }
}

Phân tích:

Với fuzziness: 1, Elasticsearch sẽ băm câu query thành các token: ["sữa", "rủa", "mặt", "cetapil"]. Sau đó, với mỗi token, nó sẽ đi vào Inverted Index lùng sục không chỉ các từ khớp 100%, mà cả những từ có khoảng cách Levenshtein $\le 1$.

Nhờ vậy, nó tự động tìm ra "rửa" (do cách "rủa" 1 bước thay thế) và "cetaphil" (do cách "cetapil" 1 bước chèn). Sản phẩm vẫn hiện ra chuẩn xác!

3. Quyền năng của "fuzziness": "AUTO"

Nếu bạn hard-code fuzziness: 2 cho mọi truy vấn, hệ thống sẽ gặp rắc rối.

• Với từ dài như "macbook", sai 2 ký tự thành "macbokk" thì vẫn hiểu được.

• Nhưng với từ ngắn như "ốp", sai 2 ký tự thành "áo" thì hệ thống sẽ trả về kết quả rác (Áo thun thay vì ốp lưng).

Giải pháp hoàn hảo là dùng "AUTO".

JSON

"match": {
  "name": {
    "query": "cetapil",
    "fuzziness": "AUTO"
  }
}

Quy tắc ngầm của "AUTO" trong Elasticsearch:

• Từ khóa dài 0..2 ký tự: fuzziness = 0 (Bắt buộc khớp chính xác. Khách gõ "ốp" thì phải tìm đúng "ốp").

• Từ khóa dài 3..5 ký tự: fuzziness = 1 (Cho phép sai 1 ký tự).

• Từ khóa dài >5 ký tự: fuzziness = 2 (Cho phép sai tối đa 2 ký tự).

Đây là "Chén thánh" của Fuzzy Search, tự động điều chỉnh độ mờ tỷ lệ thuận với chiều dài của từ khóa, bảo vệ trải nghiệm tìm kiếm.

4. Tối ưu Hiệu năng (Performance Tuning)

Khoảng cách Levenshtein đòi hỏi Elasticsearch phải tính toán xác suất mở rộng (expansion) của từ khóa rất lớn. Nếu bạn có 1 triệu từ vựng trong Index, việc tìm tất cả các từ cách chữ "iphone" 2 khoảng cách sẽ tiêu tốn lượng CPU khổng lồ.

Để bảo vệ Cluster, bạn hãy luôn kẹp thêm 2 tham số tối ưu này vào câu match:

JSON

"match": {
  "name": {
    "query": "iphone",
    "fuzziness": "AUTO",
    "prefix_length": 2, 
    "max_expansions": 50 
  }
}

• prefix_length: 2: Rất quan trọng! Nó ra lệnh: "Dù có mờ đến đâu, 2 ký tự ĐẦU TIÊN bắt buộc phải đúng chính tả". Con người thường gõ sai ở giữa hoặc cuối từ, ít khi gõ sai chữ cái đầu. Việc cố định 2 chữ cái đầu giúp Elasticsearch loại bỏ được 99% các từ vựng không liên quan trong Inverted Index ngay lập tức, giải cứu CPU.

• max_expansions: 50: Giới hạn việc mở rộng từ vựng. Khi Elasticsearch tìm thấy 50 từ biến thể thỏa mãn khoảng cách Levenshtein, nó sẽ dừng tìm kiếm thêm để trả về kết quả ngay.

Sử dụng Fuzzy Search đúng cách sẽ giúp biểu đồ Conversion Rate (Tỷ lệ chuyển đổi đơn hàng) của Hasaki tăng lên trông thấy.

Tiếp theo mạch bài về tìm kiếm không chính xác, chúng ta sẽ đụng độ với một nhóm Query khác cũng nổi tiếng ngốn tài nguyên nhưng lại không thể thiếu cho tính năng "Gợi ý tự động" hoặc "Tìm theo mã quy ước": Đó là Wildcard, Prefix và Regexp.