Thảo luận: Ý tưởng cho thuật toán nhắc từ khóa tương tự Google

[Itachi_Citus]

Gần đây mình sử dụng google thì để ý google có tích hợp autocomplete dựa trên lịch sử tìm kiếm gần nhất của người dùng.

Ví dụ: Mình bắt đầu tìm kiếm bằng từ khóa godfather

Ok, kết quả hiển thị bình thường.

Bây giờ mình muốn tìm kiếm thêm thông tin của godfather, giả sử corleone chẳng hạn:

Mình mới chỉ gõ đến chữ thứ 3, nghĩa là “cor”, google đã ngay lập tức gợi ý “corleone family”!

Bình thường, nếu không tìm kiếm godfather trước đó, google sẽ gợi ý như thế này

Hay nếu tìm kiếm từ khóa “farm” trước, sau đó gõ “cor”, google sẽ gợi ý từ “corn”

Và hệ thống hoạt động rất chính xác, kể cả với các từ khóa lạ. Không biết làm cách nào google có thể cài đặt hệ thống như vậy nhỉ?

[qloved (Quân)]

Thực ra không phải chỉ 1 thuật toán mà có rất nhiều thuật toán được gg áp dụng, có thể bạn chưa biết nhưng gg đã áp dụng trí Tuệ nhân tạo cho máy tìm kiếm gg để tăng khả năng tìm kiếm gần với kết quả mong muốn của người dùng nhất

[petehouston]

Nó là cả một hệ thống rất lớn, về cơ bản có những cái này:

Tìm từ khoá

• Cơ sở index từ khoá (indexing)
• Mapping từ khoá KVP (Key-Value Pair)
• Tham chiếu từ khoá liên quan (related keywords)
• Dự doán từ khoá (Keyword Prediction)

Tốc độ

• Cache phía server
• Cache cho từ khoá
• Cache cho view
• Phân tán server, tìm server gần nhất trả về response
  … còn một số nữa

[Itachi_Citus]

Uhm cảm ơn @petehouston. Ý mình đang hỏi là cách họ cài đặt phần từ khóa liên quan và dự đoán từ khóa thế nào nhỉ?

Giả sử với từ khóa liên quan họ có thể làm:

• Dựa vào nội dung của các kết quả đầu tiên của từ khóa vừa tìm kiếm?
• Clustering các từ khóa dựa trên nội dung?
• Clustering từ khóa dựa trên lịch sử tìm kiếm của nhiều người dùng?
• Nếu clustering thì giải quyết việc bổ sung từ khóa thế nào?
• …

Với việc dự đoán từ khóa:

• Sử dụng prefix tree sau khi có được danh sách từ khóa ứng viên?
• Nếu sử dụng prefix tree làm cách nào để xếp hạng ưu tiên?
• …?

Ý mình đang hỏi về phần cài đặt như vậy, liệu cách nào là khả thi nhỉ?

[Huy_Hoang_Pham (Huy Hoàng Phạm)]

Tham khảo bằng sáng chế về chức năng autocomplete của Google nhé ;). Mấy cái phức tạp thế này mình toàn lên Google Scholar tìm.

https://www.google.com/patents/US8645825

[Itachi_Citus]

À vâng cảm ơn anh .

In addition, the server system 120 may identify autocomplete suggestions based on input entered by many different anonymous users. For example, the server system 120 may have access to logs of queries entered by multiple anonymous users or have access to other user-generated content. The server system 120 can have access to browsing histories for different anonymous users, and thus may retrieve text accessed by different anonymous users. The server system 120 can extract words and phrases from these information sources, and can determine the relative frequency with which the extracted words and phrases occur in the information sources. The server system 120 can then provide autocomplete suggestions based on this data in response to requests received. For example, the server system 120 can select, as autocomplete suggestions for received n-grams, words and phrases that occur with the highest frequencies in the search queries or viewed content of the anonymous users.

Đọc thì nó chỉ nói tư tưởng chính chứ không nói cài đặt cụ thể, thuật toán thế nào (ngoại trừ cái n-gram).

[petehouston]

Giả sử với từ khóa liên quan họ có thể làm:

• Dựa vào nội dung của các kết quả đầu tiên của từ khóa vừa tìm kiếm?
• Clustering các từ khóa dựa trên nội dung?
• Clustering từ khóa dựa trên lịch sử tìm kiếm của nhiều người dùng?
• Nếu clustering thì giải quyết việc bổ sung từ khóa thế nào?
• …

Với việc dự đoán từ khóa:

• Sử dụng prefix tree sau khi có được danh sách từ khóa ứng viên?
• Nếu sử dụng prefix tree làm cách nào để xếp hạng ưu tiên?
• …?

Câu trả lời: Xếp hạng từ khoá.

Để xếp hạng một từ khoá thì có nhiều tiêu chí ví dụ: tần suất người dùng nhập (user input frequency), độ tương đồng của từ khoá (similarity), hành vi người dùng (user behavior), từ khoá bị cấm (blacklist), giới tính (gender), độ tuổi (age), mức độ xu hướng (trending) …

Có thể gom lại đơn giản là:

F(x) = a.f1(x) + b.f2(x) + c.f3(x) ...

• F(x): là hàm tìm keyword.
• a, b, c. …: trọng số…
• f1(), f2(), f3() …: hàm tính tiêu chí.

Khi thực hiện tìm kiếm 1 kết quả trên Google, thì server của Google sẽ log lại khá nhiều thông tin từ người dùng từ lúc gõ search từ, tới lúc click vào một link. Dữ liệu này có thể được lưu lại để tính cho mục autocomplete.

[quanminh2201 (Quang Minh)]

2 tỉ dòng code thôi mà =))