Google搜索算法原理概述
Google搜索算法的核心是PageRank算法，由拉里·佩奇和谢尔盖·布林提出。该算法通过分析网页间的链接关系评估网页重要性，基本原理是：被更多高质量网页链接的网页具有更高权重。现代Google搜索已融合数百种因素（如内容质量、用户行为、语义分析等），但PageRank仍是基础。
PageRank数学模型
PageRank值通过以下公式迭代计算：
[ PR(u) = \\frac{1-d}{N} + d \\sum_{v \\in B_u} \\frac{PR(v)}{L(v)} ]
- ( PR(u) )：网页u的PageRank值
- ( N )：网页总数
- ( B_u )：链接到网页u的网页集合
- ( L(v) )：网页v的出链数量
- ( d )：阻尼系数（通常设为0.85）
Python实现PageRank算法
以下代码演示简化版PageRank计算过程，假设有4个网页（A, B, C, D）及其链接关系：
import numpy as np
# 定义网页链接关系 (邻接矩阵)
# 行表示出链，列表示入链
links = np.array([
[0, 1, 1, 0], # A -> B, C
[0, 0, 1, 0], # B -> C
[1, 0, 0, 1], # C -> A, D
[0, 0, 1, 0] # D -> C
])
def pagerank(links, d=0.85, max_iter=100, tol=1e-6):
n = links.shape[0]
# 初始化PR值为均等分布
pr = np.ones(n) / n
# 计算转移矩阵（考虑阻尼系数）
M = d * links / (links.sum(axis=1, keepdims=True) + 1e-10) + (1 – d) / n
# 迭代计算
for _ in range(max_iter):
new_pr = M.T @ pr
if np.linalg.norm(new_pr – pr) < tol:
break
pr = new_pr
return pr
# 计算并打印结果
result = pagerank(links)
print("PageRank值:", dict(zip(['A','B','C','D'], result)))
倒排索引实现
搜索引擎通过倒排索引快速定位文档。以下代码展示倒排索引的构建与查询：
from collections import defaultdict
# 文档集合 (模拟网页内容)
documents = {
1: "the quick brown fox",
2: "the lazy dog jumps",
3: "the fox jumps over the dog"
}
# 构建倒排索引
inverted_index = defaultdict(list)
for doc_id, text in documents.items():
for word in text.split():
inverted_index[word].append(doc_id)
# 去重并排序
inverted_index = {k: sorted(set(v)) for k, v in inverted_index.items()}
print("倒排索引:", inverted_index)
# 查询函数
def search(query):
terms = query.split()
if not terms:
return []
result = set(inverted_index.get(terms[0], []))
for term in terms[1:]:
result.intersection_update(inverted_index.get(term, []))
return sorted(result)
# 示例查询
print("搜索 'fox dog':", search("fox dog"))
TF-IDF权重计算
TF-IDF用于评估词项在文档中的重要性：
import math
# 计算词频(TF)
def compute_tf(text):
tf = {}
words = text.split()
total_words = len(words)
for word in words:
tf[word] = tf.get(word, 0) + 1 / total_words
return tf
# 计算逆文档频率(IDF)
def compute_idf(documents):
idf = {}
n_docs = len(documents)
all_words = set(word for doc in documents.values() for word in doc.split())
for word in all_words:
count = sum(1 for doc in documents.values() if word in doc)
idf[word] = math.log(n_docs / (1 + count))
return idf
# 计算TF-IDF
def compute_tfidf(documents):
idf = compute_idf(documents)
tfidf = {}
for doc_id, text in documents.items():
tf = compute_tf(text)
tfidf[doc_id] = {word: tf_val * idf[word] for word, tf_val in tf.items()}
return tfidf
# 示例计算
tfidf_result = compute_tfidf(documents)
print("TF-IDF结果:", tfidf_result)
