Bài 2: Google xếp hạng hàng tỷ trang web thế nào? Thuật toán PageRank và chỉ mục ngược

Bạn gõ vài chữ vào ô tìm kiếm, và chỉ trong tích tắc Google chọn ra 10 kết quả từ hàng trăm tỷ trang web. Năm 1998, hai nghiên cứu sinh Stanford là Larry Page và Sergey Brin đã giải bài toán này bằng một ý tưởng rất "tin học": coi cả Internet là một đồ thị khổng lồ và đo độ quan trọng của từng đỉnh.

Bài thứ hai của chuyên mục "Thuật toán trong đời sống". Hôm nay chúng ta tìm hiểu hai thuật toán làm nên Google: chỉ mục ngược (inverted index) và PageRank.

1. Bước 1: tìm trang có chứa từ khóa – chỉ mục ngược

Nếu mỗi lần tìm kiếm Google phải đọc lại toàn bộ Internet thì sẽ mất hàng năm. Thay vào đó, Google xây sẵn một chỉ mục (index). Theo trang "How Search Works" của Google, chỉ mục này bao phủ hàng trăm tỷ trang web và có dung lượng hơn 100.000.000 GB. Nó giống phần "chỉ mục" cuối một cuốn sách: với mỗi từ, ghi lại danh sách các trang chứa từ đó.

Từ	Danh sách trang chứa từ
thuật toán	trang 2, 5, 9, 14, …
dijkstra	trang 5, 14, 30, …
đồ thị	trang 5, 9, 14, 21, …

Khi bạn tìm "thuật toán dijkstra", máy chỉ cần lấy giao của hai danh sách (5, 14, …). Nếu danh sách đã sắp xếp, ta giao chúng bằng kỹ thuật hai con trỏ trong O(n + m) – đúng kỹ thuật bạn học trong chuyên đề mảng và sắp xếp! Trong bài báo năm 1998, Brin và Page mô tả chỉ mục của họ được chia thành các "barrel", kèm một "lexicon" (danh sách từ).

2. Bước 2: trang nào quan trọng hơn? – PageRank

Có thể có hàng triệu trang chứa từ khóa. Trang nào nên xếp đầu? Ý tưởng của PageRank:

Một trang quan trọng nếu nó được nhiều trang quan trọng khác liên kết tới. Mỗi liên kết giống như một "lá phiếu", và phiếu từ trang quan trọng có giá trị lớn hơn.

Định nghĩa này nghe như "con gà – quả trứng": muốn biết độ quan trọng của A phải biết độ quan trọng của các trang trỏ tới A. Lời giải là lặp: bắt đầu cho mọi trang điểm bằng nhau, rồi liên tục chia điểm của mỗi trang đều cho các trang nó trỏ tới, đến khi các con số ổn định.

Mô hình "người lướt web ngẫu nhiên"

Bài báo gốc giải thích PageRank bằng hình ảnh một người lướt web ngẫu nhiên: ở mỗi trang, anh ta bấm vào một liên kết bất kỳ, không bao giờ bấm "back"; thỉnh thoảng anh ta chán và nhảy sang một trang ngẫu nhiên. PageRank của một trang chính là xác suất người này đang ở trang đó sau một thời gian rất dài. Xác suất tiếp tục bấm link là hệ số d – bài báo viết rằng họ "thường đặt d bằng 0,85".

Công thức: PR(A) = (1 − d)/N + d × Σ PR(T) / C(T), lấy tổng trên mọi trang T có liên kết tới A, với C(T) là số liên kết đi ra từ T và N là tổng số trang.

Code: tính PageRank cho 4 trang web

Ví dụ: A trỏ tới B và C; B trỏ tới C; C trỏ tới A; D trỏ tới C. Không ai trỏ tới D.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;
// PageRank bằng phép lặp lũy thừa (power iteration)
int main(){
    int n = 4;                       // 4 trang web: 0=A, 1=B, 2=C, 3=D
    vector<vector<int>> out = {{1,2}, {2}, {0}, {2}};   // A->B,C  B->C  C->A  D->C
    double d = 0.85;                 // hệ số damping trong bài báo gốc
    vector<double> pr(n, 1.0 / n);
    for(int it = 0; it < 50; it++){
        vector<double> nx(n, (1 - d) / n);
        for(int u = 0; u < n; u++)
            for(int v : out[u]) nx[v] += d * pr[u] / out[u].size();
        pr = nx;
    }
    for(int u = 0; u < n; u++)
        printf("Trang %c: %.4f\n", 'A' + u, pr[u]);
}

def pagerank(out, d=0.85, iters=50):
    n = len(out)
    pr = [1 / n] * n
    for _ in range(iters):
        nx = [(1 - d) / n] * n
        for u in range(n):
            for v in out[u]:
                nx[v] += d * pr[u] / len(out[u])
        pr = nx
    return pr

out = [[1, 2], [2], [0], [2]]      # A->B,C  B->C  C->A  D->C
for name, x in zip("ABCD", pagerank(out)):
    print(name, round(x, 4))

Kết quả: C ≈ 0,394 cao nhất (được A, B, D trỏ tới), A ≈ 0,373 đứng thứ hai dù chỉ có một liên kết vào – vì liên kết đó đến từ C, trang quan trọng nhất. D ≈ 0,0375 thấp nhất vì không ai trỏ tới. Đây chính là ý "phiếu bầu có trọng số".

Về mặt toán học, PageRank là vector riêng của một ma trận chuyển trạng thái (xích Markov), và phép lặp trên là phương pháp lặp lũy thừa (power iteration). Với hàng tỷ trang, mỗi vòng lặp là một phép duyệt qua toàn bộ cạnh của đồ thị – một bài toán xử lý dữ liệu lớn thực thụ.

3. Những câu chuyện thú vị

• Tên gọi: theo Wikipedia, "PageRank" vừa là "xếp hạng trang web" (page) vừa là… họ của Larry Page.
• Bằng sáng chế thuộc về Stanford: bằng sáng chế PageRank (cấp năm 2001) được giao cho Đại học Stanford, không phải Google. Đổi lại, Stanford nhận 1,8 triệu cổ phiếu Google và bán vào năm 2005 với giá 336 triệu USD (theo Wikipedia, dẫn báo San Jose Mercury News).
• Quy mô ban đầu: bài báo năm 1998 mô tả hệ thống với ít nhất 24 triệu trang web – nay chỉ mục đã lên tới hàng trăm tỷ trang.

4. Google ngày nay: PageRank chỉ là một phần

Hiện nay Google dùng rất nhiều tín hiệu để xếp hạng, nhiều trong đó dựa trên học máy:

• RankBrain (2015): hệ thống học máy hiểu câu tìm kiếm; theo Bloomberg (dẫn qua Wikipedia), từng được Google gọi là yếu tố quan trọng thứ ba sau liên kết và nội dung.
• BERT (2019): mô hình ngôn ngữ giúp hiểu ngữ cảnh câu hỏi. Google cho biết BERT hỗ trợ khoảng 1 trong 10 truy vấn tiếng Anh ở Mỹ lúc ra mắt, ví dụ phân biệt ý nghĩa của từ "to" trong câu "2019 brazil traveler to usa need a visa".

Nhưng dù AI có phát triển thế nào, chỉ mục ngược, sắp xếp, giao danh sách và các thuật toán trên đồ thị vẫn là "bộ xương" giúp mỗi lần tìm kiếm chỉ mất một phần giây.

5. Bạn học được gì từ đây?

• Hai con trỏ và sắp xếp – kiến thức cơ bản – là nền tảng của việc giao các danh sách trong máy tìm kiếm.
• Đồ thị có hướng mô hình hóa được cả Internet.
• Lặp đến khi hội tụ là kỹ thuật mạnh để giải các định nghĩa "vòng tròn" – bạn sẽ gặp lại nó trong xác suất, quy hoạch động trên xích Markov và học máy.

Thử thách nhỏ: thêm liên kết D → A vào ví dụ trên và chạy lại code. Bạn dự đoán thứ hạng thay đổi thế nào? Hãy chia sẻ kết quả trong phần bình luận!

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 3: Vì sao Grab không luôn gọi tài xế gần nhất? Bài toán ghép cặp trên đồ thị hai phía

Đọc tiếp: Grab & bài toán ghép cặp →

← Bài trước: Google Maps & DijkstraXem tất cả 27 bài →

Nguồn tham khảo

• Brin & Page (1998) – The Anatomy of a Large-Scale Hypertextual Web Search Engine (Google Research)
• Bản đầy đủ bài báo của Brin & Page
• Google – How Search Works: Organizing information
• Wikipedia – PageRank
• Google Blog – Understanding searches better than ever before (BERT, 2019)
• Wikipedia – RankBrain