Monday, July 30, 2007

Tìm hiểu đôi chút về hệ thống Google

Không còn nghi ngờ gì nữa, Google Search Engine là một trong những thành tựu vĩ đại nhất của kỉ nguyên mạng (nếu có bình chọn, tôi sẽ xếp Google chỉ đứng sau Internet và World Wide Web). “Trên Google, cái gì cũng có″. “Chưa có công cụ tìm kiếm nào nhanh như Google”. “Muốn tìm hả, cứ Google đi, sẽ có ngay”. v.v…Người ta nói và dùng Google ở mọi lúc, mọi nơi, như thể Google là một phần cuộc sống của họ. Sự kiện Google trở thành một động từ chỉ động tác tìm kiếm đã đánh dấu một mốc quan trọng trong con đường đưa Google trở thành một huyền thoại, sánh ngang với những Windows, Unix, Internet hay World Wide Web..

Google Search Engine là điển hình cho nhiều sự tương phản đến kì lạ:

  • Có lẽ thanh công cụ tìm kiếm Google là một trong những phần mềm có giao diện đơn giản nhất mà loài người đã từng viết ra: chỉ đơn giản một ô nhập liệu và hai cái nút bấm, nhưng nó lại làm được một trong những nhiệm vụ khó khăn nhất: Tìm kiếm thông tin cho con người. Khi bạn nhập vào từ khóa cần và bấm những cái nút kia, những gì bạn mong muốn sẽ xuất hiện, chính xác và hợp lí “như có phép màu”.
  • Google chính là một trong những tập đoàn xuất hiện muộn nhất trong kỉ nguyên mạng (ra đời vào năm 1998 khi mà thị trường công nghệ “tưởng như đã an bài” - cho đến nay chưa được 10 năm), nhưng liên tiếp là tập đoàn thành công nhất thế giới số trong những năm gần đây. Sự thăng tiến đến chóng mặt của Google đã khuấy đảo cả những “ông trùm” lớn và có lịch sử hào hùng như Microsoft hay Yahoo, đồng thời tạo nên một cuộc chạy đua vĩ đại chưa từng có, lôi kéo hàng loạt “đại gia” hàng đầu về công nghệ.
  • Thành công và sự thống trị của Google đã chứng minh cho một chân lý: “Trong thế giới công nghệ thông tin, không có gì là quá muộn cả. Bạn vẫn có thể làm vua dù bạn ra đời sau, miễn là bạn có những bước đi hợp lý và mạnh dạn với hướng đầu tư của mình”. Trước khi có sự xuất hiện của Google, thị trường tìm kiếm chỉ có thể nói là “thô sơ”, “đóng băng” và “hời hợt”, đến mức ngay cả những Microsoft hay Yahoo, với khả năng “săn mồi” cực nhạy cũng không nhìn thấy triển vọng nơi đâu. Nhưng Google lại khác. Họ đã nhìn ra và tấn công vào lãnh địa tìm kiếm “tất yếu” nhưng chưa “chín muồi”, đã nhìn thấy tiềm năng trong khi những người khác không nhìn thấy. Và họ đã làm vua, dù về tuổi đời cũng như truyền thống, họ còn thua xa Microsoft.

Người ta có thể rút ra hàng ngàn bài học từ Google. Trong kinh doanh cũng như trong chiến lược, Google đều tỏ ra rất khôn ngoan và lọc lõi. Tuy nhiên, đây là thế giới thông tin, và bạn không thể đại thành công với một tri thức tồi, hoặc thậm chí “tốt nhưng chưa đủ xuất chúng”. Nếu bạn nhập vào từ khóa, sau đó bấm vào mấy cái nút ấy mà kết quả không ra gì hay “chưa đủ sức thuyết phục”, Google chỉ là một cái tên xoàng xĩnh. Tuy nhiên, nếu bạn luôn đạt được điều mình mong muốn, bạn sẽ hiểu rằng đằng sau mấy cái nút đơn giản ấy là cả một kho tàng chứa đựng vô vàn trí tuệ cũng như công sức. Và hiển nhiên, những cái nút lại trở thành biểu tượng để người ta tôn sùng.

Bài viết này không có ý định trình bày về những thành tựu mà Google đã đạt được - mọi người đã nói quá nhiều rồi. Ở đây, ta sẽ cùng nhau “đào xới” đôi chút về kiến trúc của Google Search Engine để có thể trả lời một phần cho câu hỏi: Đâu là cội nguồn sức mạnh của Google?

Chú ý: Trong bài viết này có sử dụng một số công thức Toán học được gõ bằng TeX. Bạn vẫn có thể xem bình thường nhưng sẽ nhận được một thông báo lỗi. Nguyên nhân là do máy tính của bạn chưa cài các font dành cho TeX. Có hai lựa chọn cho bạn:

Giới thiệu về Search Engine

Trong phần này, ta sẽ tìm hiểu những khái niệm và thành phần cơ bản của một Search Engine điển hình. Sau khi đọc xong mục này bạn sẽ:

  • Hiểu về chỉ số - chỉ số ngược và tầm quan trọng của chúng trong việc xây dựng Search Engine
  • Nắm bắt được định nghĩa và nhận biết được 3 loại Search Engine
  • Hiểu cấu tạo và hoạt động của Search Engine
  • Nhận thức được những thách thức phải đối diện khi xây dựng một Search Engine

Chỉ số và chỉ số ngược

Index là từ mang nhiêu ý nghĩa khác nhau. Trong xuất bản và in ấn, index nghĩa là bảng chú dẫn, cho phép tra cứu nhanh thông tin về những từ khóa quan trọng trong một cuốn sách. Trong kinh tế, index lại hàm ý số so sánh, đo tỉ lệ giữa giá cả và chất lượng. Trong Toán học, index gắn liền với khái niệm “chỉ số” của lý thuyết số, lũy thừa, số thứ tự của một số trong dãy, hay định lý Poncairé-Hopf liên quan đến tổng các chỉ số của một trường vector. Ở đây, chúng ta sẽ xem xét khái niệm index trong phạm vi của lập trình máy tính và cơ sở dữ liệu.

Chỉ số (index)

Trong khoa học máy tính cũng như trong lập trình, một chỉ số (index) có thể là:

  • Một số nguyên dùng để xác định phần tử nào đó trong một mảng
  • Một phần tử trỏ đến dữ liệu
  • Cấu trúc dữ liệu cho phép tìm kiếm trong thời gian tuyến tính

Giả sử ta có n đối tượng dữ liệu. Thuật toán “ngây thơ” nhất để tìm kiếm một đối tượng nào đó có tính chất mong muốn hay không là “dạo qua” hết tất cả các đối tượng. Thuật toán này yêu cầu thời gian tuyến tính O(n). Nếu đây là lần đầu tiên chúng ta được “tiếp xúc” với tất cả các đối tượng dữ liệu này và ngay lập tức phải tìm kiếm trên danh sách, tất nhiên việc phải duyệt toàn bộ là không thể tránh khỏi. Tuy nhiên, việc tìm kiếm phải dựa trên cơ sở những thông tin có sẵn, và thay vì phải dùng thuật toán “ngây thơ” hùng hục lật từng đối tượng, ta có thể tận dụng thông tin đã biết để tăng tốc thao tác tìm kiếm.

Chỉ số còn có ý nghĩa là bất kì cấu trúc dữ liệu nào dùng để cải thiện việc tìm kiếm. Người ta đã đưa ra rất nhiều cấu trúc dữ liệu phục vụ cho mục đích này, chẳng hạn như các hàm băm, các cấu trúc cây, v.v…Đa số các thuật toán cho phép tìm kiếm trong thời gian O(log(n)). Cá biệt có thuật toán tìm kiếm trong thời gian hằng số trên những đối tượng dữ liệu đặc biệt.

Trong khoa học cơ sở dữ liệu, chỉ số đặc trưng cho một tập thuộc tính (tương ứng với một tập các cột trong bảng) cho phép truy cập nhanh đến các bản ghi (tương ứng với các hàng). Chỉ số được tối ưu hóa nhằm phục vụ mục đích tìm kiếm, vì thế thường nhỏ hơn một bảng thực sự. Khác với khóa, chỉ số có thể là duy nhất (unique) hoặc không (non-unique).

Như đã nói ở trên, chỉ số bao gồm một tập thuộc tính (hay các cột) trong một bảng. Thứ tự xuất hiện của các cột ở đây đóng vai trò rất quan trọng. Ta có thể ngay lập tức thu được được bản ghi cần tìm nếu dùng chỉ cột thứ nhất, nhưng chưa chắc nếu chỉ dùng cột thứ hai.

Người ta thường dùng nhiều cấu trúc dữ liệu khác nhau để cài đặt chỉ số trong cơ sở dữ liệu, điển hình nhất là các cây cân bằng (B - Tree) và bảng băm (Hash).

Chỉ số có rất nhiều ứng dụng, đặc biệt trong Information Retrieval, ngành khoa học nghiên cứu tất cả thủ tục tìm kiếm thông tin trong các tài liệu, dữ liệu meta mô tả tài liệu, siêu văn bản trên Internet hay cơ sở dữ liệu.

Chỉ số ngược (inverted index)

<đang viết dở>

Định nghĩa và phân loại Search Engine

Định nghĩa

Nói một cách đơn giản, Search Engine (công cụ tìm kiếm) hay Search Service (dịch vụ tìm kiếm) là phần mềm hay chương trình được thiết kế để trợ giúp cho việc tìm kiếm thông tin trong một hệ thống máy tính, chẳng hạn như World Wide Web, hay một mạng cục bộ hoặc máy tính cá nhân. Search Engine cho phép người dùng tìm kiếm thông tin theo một số tiêu chuẩn (criteria) nhất định, thông thường là những thành phần có chứa một hoặc một vài từ khóa (keywords) và trả lại một danh sách các kết quả phù hợp với tiêu chuẩn đó.

Thuật ngữ Search Engine trên môi trường Internet World Wide Web mà ta sử dụng hàng ngày chỉ dạng tìm kiếm thông qua cơ sở dữ liệu gồm nhiều trang văn bản có định dạng HTML. Về cơ bản, có ba loại Search Engine:

  • Search Engine dùng các robot, thường gọi là crawlers (tạm dịch: “những kẻ sục sạo”), ants (đàn kiến) hoặc spiders (bầy nhện).
  • Search Engine do con người tự gửi dữ liệu (human submissions search engine).
  • Search Engine kết hợp cả hai loại trên.

Phân loại

  • Các Search Engine dựa trên crawler (Crawler - based search engines): Sử dụng những phần mềm “do thám” tự động (automated software agents) gọi là các crawlers. Chúng sẽ ghé thăm các Website, đọc thông tin thực sự có trong đó, đồng thời đọc tag meta và theo các liên kết trong Website để tiến hành thao tác đánh chỉ số. Các “đặc vụ viên” này sau đó gửi thông tin thu nhận được về kho dữ liệu trung tâm (data central depository), nơi dữ liệu được đánh chỉ số thực sự. Kho dữ liệu trung tâm này thực chất là hệ thống máy chủ của các hãng tìm kiếm. Cứ sau một thời gian nhất định, “những kẻ sục sạo” lại “rà soát” và “đào xới” Internet để tiến hành tìm kiếm thông tin mới và cập nhật lại dữ liệu cũ. Tần suất “bới móc” do người quản trị của Search Engine quyết định.
  • Các Search Engine do con người gửi dữ liệu (Human - powered search engines) dựa trên việc con người đưa tự thông tin rồi sau đó được đánh chỉ số và phân loại.

Trong bất kì trường hợp nào, khi sử dụng công cụ tìm kiếm, bạn thực sự chỉ tìm kiếm trong phạm vi tập chỉ số, bạn không tìm kiếm trên World Wide Web hay Internet. Tập chỉ số này vốn là một cơ sở dữ liệu khổng lồ gồm những thông tin đã được thu thập và lưu trữ từ trước. Đó là lí do giải thích tại sao đôi khi kết quả tìm kiếm mà Google hay Yahoo đưa ra lại chứa một vài links đã bị chết. Nguyên nhân là kết quả tìm kiếm dựa trên chỉ số, mà nếu những chỉ số không được cập nhật khi những liên kết không còn tồn tại, Search Engine vẫn coi như các links này đang sống. Tình hình chỉ thay đổi cho đến lần cập nhật tiếp theo.

Cấu tạo và hoạt động của Search Engine

<đang viết dở>

Các thành phần của một Search Engine

Dưới đây

Những thách thức phải đối diện

<đang viết dở>

Kiến trúc của Google

<đang viết dở>

Thuật toán điều hướng kết quả tìm kiếm

<đang viết dở>

PageRank

<đang viết dở>

Thuật toán hiện tại của Google

<đang viết dở>

Hệ thống file của Google

<đang viết dở>

Tài liệu tham khảo

<đang viết dở>



nguồn: vieblog.wordpress.com

No comments:

3 site auto đào Bitcoin miễn phí 0.0006BTC mỗi ngày

Bitcoin  (BTC) hiện nay là đồng tiền ảo đắc giá nhất hiện nay và cụm từ “đào Bitcoin” cũng không xa lạ với chúng ta, không ít bạn đầu tư nhi...