Bạn hoàn toàn có thể tự nghĩ ra thuật toán PageRank — đây là cách hoạt động

Năm 1996, bạn bực bội với các công cụ tìm kiếm như AltaVista — chúng chỉ khớp từ khóa một cách máy móc, trả về kết quả sai lệch đến buồn cười. Trong bối cảnh đó, Sergey Brin và Larry Page đã phát minh ra PageRank, thuật toán giúp Google trở thành tên tuổi quen thuộc và mang về hàng tỷ đô la. Nhưng điều thú vị là: về bản chất, bạn hoàn toàn có thể tự nghĩ ra nó — chỉ với vài ý tưởng đơn giản.

Ý tưởng lõi: Uy tín được lan truyền

PageRank không phải là phép màu toán học, mà chỉ là sự tổng hợp của ba nguyên tắc cơ bản:

• Mỗi trang web có một "điểm uy tín" (rank) nhất định.
• Một trang "chia sẻ" uy tín của mình cho trang khác bằng cách đặt liên kết đến — giống như trao cho họ một dấu chứng nhận.
• Tổng uy tín của một trang bằng một mức tối thiểu cộng với toàn bộ uy tín nhận được từ các trang liên kết đến nó.

Chỉ vậy thôi. Để dễ hình dung, hãy tưởng tượng trang BBC News có uy tín là 50 và nó đặt liên kết đến 5 trang khác. Giả sử nó phân phối 80% (tức 40 điểm) uy tín của mình cho các trang được liên kết, phần còn lại chia đều cho tất cả các trang trên web. Khi đó, mỗi trang được BBC liên kết sẽ nhận được 40/5 = 8 điểm từ BBC.

Code Python bất ngờ nhỏ gọn

Điều đáng ngạc nhiên là toàn bộ thuật toán này có thể được viết trong một chương trình Python cực ngắn và dễ đọc:

# incoming[n] chứa các trang liên kết đến n
# outgoing[n] chứa các trang n liên kết tới
# Một trang phân phối damping% uy tín cho các trang nó liên kết.
# (1-damping)% được chia đều cho tất cả các trang.

def pagerank(incoming, outgoing, damping=.85, tolerance=1e-10):
    n = len(incoming)                # tổng số trang
    rank = [1 / n] * n               # khởi tạo uy tín bằng nhau
    minimum_rank = (1 - damping) / n # mức tối thiểu mỗi trang nhận
                                     # từ các bước nhảy ngẫu nhiên

    while True:
        old = rank.copy()
        for page, neighbors in enumerate(incoming):
            # bạn nhận uy tín từ những trang liên kết đến mình
            acquired = sum(old[neighbor] / len(outgoing[neighbor])
                           for neighbor in neighbors)
            rank[page] = minimum_rank + damping * acquired

        # lặp cho đến khi hội tụ
        if max(abs(a - b) for a, b in zip(rank, old)) < tolerance:
            return rank

Và thế là xong! Nếu bạn chạy các vòng lặp cập nhật này một vài lần, bạn sẽ thu được điểm uy tín cho từng trang web — con số phản ánh mức độ quan trọng thực sự của chúng. Tất nhiên, vẫn có một số giả định được đặt ra (như không có trang "treo" dangling nodes), nhưng đó chỉ là chi tiết kỹ thuật nhỏ — bạn đã nắm được cốt lõi của thuật toán.

Từ ý tưởng đơn giản đến đế chế tìm kiếm

Điều đáng suy ngẫm là PageRank không ra đời từ một công thức toán học cao siêu nào, mà từ một quan sát thông thường: liên kết là sự tín nhiệm. Google chỉ đơn giản là vĩ đại vì họ dám đặt cược vào một ý tưởng trực quan ai cũng có thể hiểu, trong khi tất cả các đối thủ đều lao đầu vào việc tinh chỉnh "khớp từ khóa".

Với những ai đang học lập trình hoặc làm trong lĩnh vực tìm kiếm tại Việt Nam, đây là một bài học quý giá:

Đôi khi, thuật toán làm nên kỷ nguyên không nằm ở độ phức tạp, mà nằm ở khả năng diễn đạt một chân lý đơn giản thành mã chạy được.

Và nếu một ngày nào đó bạn thấy mình bị kẹt trong năm 1996 — bạn biết mình phải làm gì rồi đấy!