Thuật toán tìm kiếm cơ bản của Google

Các bạn cũng biết công cụ tìm kiếm mạnh nhất hiện nay không ai khác là ông lớn Google. Khi mới hình thành thì có Yahoo, Bing,.. nhưng sau một thời gian thì Google đã loại bỏ hai ông lớn kia. Vậy Google đã là gì, và thực hiện nó như thế nào.

Đơn giản chỉ là Google luôn luôn đặt những tiêu chí ưu tiên cho người dùng, tối ưu hóa các câu truy vấn của người dùng và cho ra những kết quả tìm kiếm tốt nhất. Họ đã ngày càng hổ báo khi liên tục cập nhật thuật toán tìm kiếm mới.

Vì sao Google mạnh? câu hỏi nhức ngói mà ai cũng muốn biết.

Thật đơn giản, cũng giống như xây dựng nhà. Muốn nhà vững chắc, thì phải có móng nhà vững chắc. Google cũng thế, google mạnh vì nó đã xây dựng một bài toán, một thuật toán tìm kiếm thật vững chắc, và sau đó dựa vào các thuật toán đó họ đã tăng sức mạnh. Và đây là một trong những thuật toán mà google đã thực hiện.

1. Loại bỏ các từ không có ý nghĩa (LOẠI BỎ STOPWORD )

Loại bỏ các từ không có nghĩa là các từ xuất hiện thường xuyên trong câu, các từ đó giúp xây dựng câu văn hay hơn nhưng không biểu đạt nội dung và chất lượng của tài liệu.


Ví dụ: Những, khi, cũng, có thể, một, và, một số, nhiều,......

Và danh sách các từ loại bỏ này sẽ được Google loại bỏ theo từng danh mục và từng ứng dụng.

Vì sao Google phải loại bỏ các từ không có nghĩa (Stopword) này

• Loại bỏ sẽ giúp giảm đi kích thước của tập trung chỉ mục. (theo thống kê các từ không có nghĩa này chiếm đến 20-30% tổng số từ trong một bài nội dung).
• Tăng hiệu suất và hiệu quả. Vì khi các từ không có nghĩa này sẽ là nhiễu đi nội dung tìm kiếm và chất lượng tìm kiếm. 

2. Chuyển biến từ về thể gốc:

Nói một cách nôn na thì một từ có nhiều thể cú pháp khác nhau phụ thuốc vào ngữ cảnh khi nó xuất hiện.

Mình sẽ lấy ví dụ bằng ngôn ngữ Tiếng Anh để các bạn dễ hiểu: 

• Danh từ có thể số ít và số nhiều: Apple và Apples 
• Động  từ  có  thể  nguyên  bản  và  tiếp  diễn  (+ing): eat và eating. 
• Động từ ở các thì khác nhau: eat, ate và eaten  

Những biến thể này sẽ làm giảm đi mật độ từ khóa và chất lượng từ khóa của một văn bản.

Trên thực tế thì Google đã phát triển rất nhiều thực toán này, và mọi người thường gọi nó là  stemmers. PORTER STEMMER là thuật  toán  hoạt  động theo cơ chế kiểm  tra  tính thỏa  của  từ  đối  với  một bộ luật. Do Martin  F.  Porter  đề xuất vào năm 1980. 

Thuật toán Porter Stemmer hoạt động như thế nào.

Ví dụ bước 1 

• SSES   →   SS  
• caresses  →   caress 
• IES   →   I 
• ponies   →   poni 
• ties   →   ti  

Ưu điểm của thuật toán chuyển biến từ về thể gốc này

• Giúp  tăng  hiệu  quả  truy  vấn  và khai thác văn bản. 
• Stemming  làm  giảm  kích  thước  của  cấu trúc đánh chỉ mục. (Luật kết hơn này sẽ giảm đi 10-20% các từ có chung thể gốc).

Nhược điểm của thuật toán làm ảnh  hưởng đến độ chính xác vì tài liệu không liên quan cũng bị xem là liên quan.  

◦ Ví dụ: “cop” và “cope” → “cop”, nhưng tài liệu chỉ chứa  “cope”  không  liên  quan  đến  chủ  đề  cảnh sát.  

3.Tần số lần xuất hiện của một từ trong một tài liệu.  ( TF-IDF )

Tần số từ (term frequency): số lần xuất hiện;của một từ trong một văn bản, tài liệu, dữ liệu

• Sử dụng  tần  số  xuất hiện để chỉ độ quan trọng tương đối của từ trong tài liệu.
• Nếu một  từ  xuất hiện thường xuyên trong văn bản thì văn bản có liên hệ với chủ đề mà từ biểu diễn.

Tần số tài liệu (document frequency): được định nghĩa là số tài liệu trong ngữ liệu chứa một từ xác định.

Định nghĩa: TF-IDF  (term  frequency –  inverse;document frequency) cho biết độ quan trọng của một từ đốivới một tài liệu trong ngữ liệu.

Công thức: �𝑓 ∗ 𝑖𝑑𝑓 �, 𝑑,𝐷 = �𝑓 �, 𝑑 × 𝑖𝑑𝑓 �,𝐷