[IT] Nguyen_HSU tìm hiểu về hoạt động của các công cụ tìm kiếm

Nguyen_HSU

Thanh viên kỳ cựu
search_engines.jpg
Internet và World Wide Web có đến hàng trăm triệu website có sẵn mang các thông tin về nhiều chủ đề khác nhau. Tuy nhiên hầu hết chúng đều được đặt tiêu đề theo ý thích của tác giả, và được đặt trên máy chủ với các tên khó hiểu. Khi bạn cần biết về một chủ đề nào thì sẽ phải đọc các trang nào? Phần lớn mọi người khi băn khoăn về vấn đề này họ sẽ sử dụng một công cụ tìm kiếm trên Internet (Internet search engine).

Search engine trên Internet là các site đặc biệt trên web, được thiết kế để giúp mọi người tìm kiếm thông tin được lưu trên các site khác nhau. Có nhiều cách khác nhau trong cách tìm kiếm này, nhưng tất cả chúng đều thực hiện ba nhiệm vụ cơ bản:

  • Tìm kiếm Internet – hoặc chọn các mẩu thông tin trên Internet – dựa trên các từ quan trọng
  • Giữ một chỉ mục cho các từ tìm thấy cùng với địa chỉ tìm thấy chúng
  • Cho phép người dùng tìm kiếm các từ hoặc cụm từ được tìm kiếm trong chỉ mục đó.
Các cỗ máy tìm kiếm trước kia đều giữ chỉ mục của hàng trăm ngàn trang web và tài liệu, chúng thường nhận có thể một hoặc hai nghìn yêu cầu tìm kiếm mỗi ngày. Ngày nay, cỗ máy tìm kiếm hàng đầu đánh chỉ mục hàng trăm triệu trang và đáp trả đến hàng chục triệu yêu cầu mỗi ngày. Trong bài này chúng tôi muốn giới thiệu về các nhiệm vụ chính sẽ được thực hiện như thế nào, và cách các cỗ máy tìm kiếm này sẽ xử lý như thế nào để cho phép bạn tìm thông tin cần thiết trên web.

Xem xét Web
Khi hầu hết mọi người nói về các cỗ máy tìm kiếm Internet, họ đều cho đó là cỗ máy tìm kiếm World Wide Web. Tuy nhiên trước khi Web trở thành phần dễ thấy nhất của Internet thì thực sự đã có các cỗ máy tìm kiếm để giúp mọi người có thể tìm được các thông tin trên mạng. Các chương trình với những cái tên như “gopher” và “Archie” đã giữ chỉ số của các file được lưu trên máy chủ kết nối với Internet, đã giảm được một cách rõ rệt số lượng thời gian cần thiết để tìm kiếm các chương trình và tài liệu. Vào những năm cuối thập kỷ 80, việc có được các giá trị quan trọng từ Internet có nghĩa là biết cách sử dụng gopher, Archie, Veronica và một số chương trình tương tự khác.

Ngày nay, hầu hết người dùng Internet chưa hiểu nhiều về cách tìm kiếm của họ trên Web, chính vì vậy chúng tôi sẽ giới thiệu vấn đề này bằng cách tập trung vào nội dung của các trang web.

Khởi đầu
Trước khi cỗ máy tìm kiếm có thể cho bạn biết về nơi một file hoặc tài liệu nào đó được lưu trữ thì nó phải tìm ra được chúng. Để tìm các thông tin trên hàng trăm triệu trang web đang tồn tại, mỗi một cỗ máy tìm kiếm phải sử dụng đến các robot phần mềm đặc biệt, các robot phần mềm này được gọi là spider (con nhện), để thành lập danh sách các từ tìm thấy trong các website. Quá trình spider xây dựng danh sách được gọi là Web crawling. Để tạo và duy trì một danh sách hữu dụng cho việc tìm kiếm thì spider của cỗ máy tìm kiếm phải xem được nội dung của các trang web.
Vậy cách spider thực hiện công việc của nó trên Web như thế nào? Điểm khởi đầu là danh sách các máy chủ và trang web phổ biến. Spider sẽ bắt đầu với một site phổ biến nào đó, đánh chỉ mục các từ trên trang của nó và theo các liên kết tìm thấy bên trong site này. Theo cách này, hệ thống Spider sẽ nhanh chóng thực hiện công việc của nó và trải rộng ra toàn bộ các phần được sử dụng rộng rãi nhất của web.


Spider lấy nội dung của trang web và tạo các từ khóa tìm kiếm để cho phép người dùng trực tuyến có thể tìm các trang mong muốn.
Google.com bắt đầu như một cỗ máy tìm kiếm của trường đại học. Trong bài viết mô tả về cách hệ thống được xây dựng như thế nào, Sergey Brin và Lawrence Page đã lấy một ví dụ về spider của họ có thể làm việc nhanh đến cỡ nào. Họ đã xây dựng hệ thống ban đầu để có thể sử dụng nhiều spider, thường là có đến 3 spiders hoạt động đồng thời. Mỗi Spider có thể giữ tới khoảng 300 kết nối với các trang web mỗi thời điểm. Với hiệu suất đỉnh của nó, sử dụng đến 4 Spider, hệ thống của họ có thể tìm thêm trên 100 trang mỗi giây, tạo ra khoảng 600KB dữ liệu mỗi giây.

Việc giữ được tốc độ tìm kiếm nhanh cũng có nghĩa phải xây dựng hệ thống có thể cung cấp được các thông tin cần thiết cho Spider. Hệ thống Google trước kia có một máy chủ chuyên dụng dùng để cung cấp các URL cho Spider. Thay cho việc phụ thuộc vào nhà cung cấp dịch vụ về DSN để dịch tên của máy chủ thành địa chỉ, Google đã có DSN của chính họ để độ giữ chậm diễn ra chỉ trong khoảng thời gian tối thiểu.

Khi Spider của Google xem các trang HTML, nó lưu ý hai thứ:


  • Các từ bên trong trang
  • Nơi tìm thấy các từ
Các từ xuất hiện trong tiêu đề, phụ đề, các thẻ meta và các phần quan trọng khác có liên quan được lưu ý bằng những xem xét đặc biệt cho những tìm kiếm của người dùng sau đó. Spider của Google đã được xây dựng để có thể đánh chỉ mục mọi từ quan trọng trên một trang và chỉ để lại các mạo từ như “a,” “an” và “the”. Các Spider khác lại sử dụng các phương pháp khác.

Các phương pháp khác mà Spider áp dụng thường là cố gắng làm cho hệ thống của Spider diễn ra nhanh hơn, cho phép người dùng có thể tìm kiếm hiệu quả hơn, hoặc cả hai. Ví dụ, một số Spider giữ liên hệ với các từ trong tiêu đề, các heading nhỏ và liên kết, cùng với 100 từ thường được sử dụng trên trang và các từ trong 20 dòng đầu tiên của văn bản.
Các hệ thống khác chẳng hạn như AltaVista lại tiếp cận theo một hướng khác, đánh chỉ mục các từ đơn trên mỗi trang, gồm có cả “a,” “an,” “the” và các từ “không quan trọng” khác. Tính đầy đủ trong phương pháp này được so khớp bởi các hệ thống khác trong phần thẻ meta của Website.

Các thẻ Meta

Thẻ Meta cho phép chủ sở hữu của trang có thể chỉ định các từ khóa và khái niệm sẽ được đánh chỉ mục. Đây là một trong các thẻ rất hữu dụng, đặt biệt trong nhiều trường hợp các từ trên trang có thể có đến hai hoặc 3 nghĩa – thẻ Meta có thể hướng dẫn cỗ máy tìm kiếm trong việc chọn nghĩa nào trong số các nghĩa có thể là đúng đối với một từ nào đó. Tuy vậy vẫn có một lo lắng trong việc tin cậy nhiều vào thẻ Meta vì các trang kém chất lượng mà chủ sở hữu của nó lại đưa vào thẻ này những chủ đề phổ biến nhưng không có nội dung gì về nó. Để khắc phục hiện tượng này, Spider sẽ tương quan các thẻ Meta với nội dung của trang, loại ra các thẻ không thỏa khớp với các từ trong trang.

Tất cả vấn đề này khởi nguồn từ chủ sở hữu của trang này, họ muốn trang web được hiển thị trong kết quả tìm kiếm của các cỗ máy tìm kiếm này. Nhiều khi, chủ sở hữu không muốn trang của họ xuất hiện trên các trang kết quả của một cỗ máy tìm kiếm hoặc không muốn Spider truy cập vào trang của họ. (Ví dụ, một game xây dựng các trang active mới mỗi lần các section của trang được hiển thị hoặc theo sau là các liên kết mới. Nếu một Spider Web có thể truy cập vào và bắt đầu đi theo tất cả liên kết cho các trang mới thì game có thể mắc lỗi activity cho player tốc độ cao và kéo dài sự kiểm soát.) Để tránh tình trạng này, giao thức loại trừ robot đã được phát triển. Giao thức này bổ sung vào phần thẻ meta ở bắt đầu mỗi trang, thông báo cho Spider phải rời trang của nó – không đánh chỉ mục các từ trên trang này hoặc cố gắng lần theo các liên kết của nó.

Xây dựng chỉ mục
Khi Spider đã hoàn tất nhiệm vụ tìm thông tin trên các trang web (chúng tôi lưu ý rằng đây là nhiệm vụ không bao giờ hoàn tất vì luôn có sự thay đổi của các trang nên điều đó có nghĩa là Spider sẽ luôn thực hiện nhiệm vụ của nó), cỗ máy tìm kiếm phải lưu các thông tin này theo một cách nào đó để có lợi nhất. Có hai thành phần chính liên quan tới việc tạo dữ liệu đã thu thập được để có thể truy cập với người dùng:


  • Thông tin được lưu với dữ liệu
  • Phương pháp mà thông tin được đánh chỉ mục
Trong trường hợp đơn giản nhất, một cỗ máy tìm kiếm có thể chỉ lưu các từ và URL nơi mà nó tìm ra. Trong thực tế, điều này sẽ làm hạn chế rất nhiều vì sẽ không có cách nào để nói từ đó đã được sử dụng là quan trọng hay không có giá trị trên trang đó, hoặc từ đã được sử dụng một lần hay nhiều lần, hoặc trang đó có chứa liên kết đến các trang khác có chứa từ hay không. Nói theo cách khác là sẽ không có cách nào xây dựng được danh sách thứ hạng để bình chọn các trang hữu ích nhất ở trên đầu mỗi danh sách kết quả tìm kiếm.

Để làm cho các kết quả tìm kiếm được phù hợp nhất, hầu hết các cỗ máy tìm kiếm đều lưu nhiều từ và URL. Một engine có thể lưu số lần từ nào đó xuất hiện trong một trang. Nó có thể gán “trọng lượng” cho mỗi một entry nào đó, tăng dần giá trị gán cho các từ khi chúng xuất hiện gần phía trên của tài liệu, trong các heading con, các liên kết và trong thẻ meta hoặc trong tiêu đề của trang. Mỗi một cỗ máy tìm kiếm mang tính thương mại đều có một công thức khác nhau đối với việc gán trọng lượng cho các từ trong chỉ mục của nó. Đây chính là một trong những lý do tại sao một tìm kiếm cho những từ giống nhau trên các cỗ máy tìm kiếm khác nhau lại cho ra danh sách khác nhau, các trang được thể hiện theo thứ tự khác nhau.
Không quan tâm đến sự kết hợp nghiêm ngặt các mẩu thông tin bổ sung được lưu bởi mỗi search engine, dữ liệu sẽ được mã hóa để lưu trữ trong các điểm lưu trữ riêng.

Một chỉ mục chỉ có một mục đích: Nó cho phép thông tin được tìm thấy một cách nhanh chóng. Có khá nhiều cách cho việc xây dựng chỉ mục, nhưng cách hiệu quả nhất vẫn là xây dựng một bảng hash. Một công thức được sử dụng để gắn giá trị bằng số cho mỗi một từ. Công thức này được thiết kế để cung cấp cho các entry trên số lượng được xác định trước các phần chia. Phần chia bằng số này khác với phần chia từ trong bảng alphabet và đó chính là hiệu lực chính của bảng hash.

Trong tiếng Anh, có một số ký tự được bắt đầu nhiều hơn với các ký tự khác. Ví dụ như bạn sẽ thấy phần “M” của từ điển sẽ dày hơn phần “X”. Sự không công bằng này có nghĩa rằng việc tìm một từ bắt đầu với một ký tự “phổ biến” có thể lâu hơn nhiều so với việc tìm một từ bắt đầu với một ký tự kém phổ biến hơn. Thuật toán Hash cân bằng sự khác nhau này, và giảm thời gian trung bình để tìm kiếm mỗi entry. Nó cũng phân biệt chỉ mục với entry thực tại. Bảng hash gồm có các số được đánh hash cùng với một con trỏ dữ liệu, con trỏ này có thể được phân loại theo bất cứ cách nào cho phép lưu trữ hiệu quả nhất. Sự kết hợp giữa việc đánh chỉ mục hiệu quả và lưu trữ hiệu quả làm cho người dùng có thể thực hiện các thao tác tìm kiếm một cách nhanh chóng thậm chí khi họ tạo một tìm kiếm phức tạp.

Xây dựng một tìm kiếm
Việc tìm kiếm thông qua một chỉ mục cần người dùng xây dựng một truy vấn và đệ trình nó thông qua search engine. Truy vấn có thể khá đơn giản như một từ chẳng hạn. Việc xây dựng một truy vấn phức tạp hơn cần sử dụng các toán tử Boolean để cho phép bạn lọc và mở rộng dưới dạng tìm kiếm.
Các toán tử Boolean thường được sử dụng nhất là:


  • AND – Tất cả các mục đã được nối bằng toán tử này phải xuất hiện trong trang hoặc các tài liệu. Một số search engine thay thế toán tử này bằng dấu “+”.
  • OR – Ít nhất một trong các mục đã được nối bằng “OR” phải xuất hiện trong các trang hoặc tài liệu.
  • NOT – Mục hoặc các mục sau toán tử này không xuất hiện trong trang hoặc tài liệu, một số search engine thay thế bằng dấu “-”.
  • FOLLOWED BY – Một trong số các mục phải được theo sau trực tiếp bởi mục khác.
  • NEAR – Một trong các mục phải nằm bên trong một số các từ cụ thể
  • Dấu ngoặc kép – Các từ giữa các dấu ngoặc kép phải được coi như một cụm từ, và cụm từ đó phải được tìm thấy trong tài liệu hoặc file.
Tìm kiếm trong tương lai

Các tìm kiếm đã được định nghĩa bởi toán tử Boolean trở nên khá bình thường, engine sẽ tìm kiếm các từ hoặc cụm từ chính xác khi chúng được nhập vào. Điều này có thể phát sinh một vấn đề khi các từ được nhập có đa nghĩa. Nếu bạn chỉ quan tâm đến một trong các nghĩa đó thì có thể không muốn thấy xuất hiện các trang tiêu biểu cho tất cả các nghĩa của nó. Tuy bạn có thể tạo một tìm kiếm bằng cách loại trừ ra các nghĩa không mong muốn nhưng nếu cỗ máy tìm kiếm giúp được bạn việc này thì tốt biết bao.

Một trong những lĩnh vực nghiên cứu tìm kiếm là tìm kiếm dựa trên khái niệm. Một số nghiên cứu này liên quan đến việc sử dụng phân tích thống kê về các trang chứa từ hoặc cụm từ mà bạn tìm kiếm, để tìm ra các trang khác có thể bạn quan tâm. Rõ ràng các thông tin được lưu trong mỗi trang thực sự rất quan trọng cho tìm kiếm dựa trên khái niệm, và xa hơn nữa là việc xử lý được yêu cầu cho mỗi tìm kiếm. Nhiều nhóm nghiên cứu đã và đang làm việc hết mình để cải thiện cả kết quả và hiệu suất của các cỗ máy tìm kiếm này. Một số nhóm khác đã chuyển sang một lĩnh vực nghiên cứu khác như truy vấn ngôn ngữ tự nhiên.

Ý tưởng ẩn đằng sau nghiên cứu truy vấn ngôn ngữ tự nhiện là bạn có thể đánh vào đó một câu hỏi giống như cách bạn hỏi đối với người ngồi bên cạnh bạn – khong cần đến các toán tử Boolean hoặc các cấu trúc truy vấn phức tạp. Site truy vấn ngôn ngữ tự nhiên nhất hiện nay là AskJeeves.com, nó có khả năng phân tích cú pháp truy vấn về các từ khóa để áp dụng cho chỉ mục của các site mà nó đã xây dựng. Tuy nhiên site này chỉ làm việc với các truy vấn đơn giản vì việc đặt khái niệm cho một truy vấn khá phức tạp.


itteen
 
Last edited by a moderator:

Bình luận bằng Facebook

Top