文本对比算法原理与应用

一、为什么需要文本对比

做爬虫的时候，经常会遇到重复数据的问题。同一个商品在不同页面出现，同一篇文章被多个网站转载，如果不做去重，数据库里会堆满重复内容。

文本对比算法就是解决这个问题的利器。它能帮我们判断两段文本是否相同，或者有多相似，从而决定是否保留。

应用场景

爬虫数据去重
文章相似度检测
代码版本对比
内容更新监控

二、diff 算法原理

diff 算法最经典的实现是 Myers 算法，核心思想是找到两个序列之间的最短编辑路径。

2.1 编辑操作

diff 算法定义了三种基本操作：

插入（Insert）：在 A 中插入 B 的一个元素
删除（Delete）：从 A 中删除一个元素
不变（Equal）：A 和 B 的对应元素相同

2.2 简单示例

                        文本 A: a b c d e f
文本 B: a b d e f g

对比结果：
  a     (不变)
  b     (不变)
- c     (删除)
  d     (不变)
  e     (不变)
  f     (不变)
+ g     (新增)
                    

三、Python 实现

3.1 使用 difflib

Python 标准库提供了 difflib 模块，可以直接使用。

                        import difflib

# 对比两个文本
text1 = 'hello world'
text2 = 'hello python'

diff = difflib.ndiff(text1.split(), text2.split())
print('\n'.join(diff))

# 输出：
#   hello
# - world
# + python
                    

3.2 生成统一 diff 格式

                        import difflib

text1 = '''line 1
line 2
line 3
line 4'''

text2 = '''line 1
line 2 modified
line 3
line 5'''

diff = difflib.unified_diff(
    text1.splitlines(),
    text2.splitlines(),
    fromfile='before.txt',
    tofile='after.txt'
)

print('\n'.join(diff))

# 输出：
# --- before.txt
# +++ after.txt
# @@ -1,4 +1,4 @@
#  line 1
# -line 2
# +line 2 modified
#  line 3
# -line 4
# +line 5
                    

3.3 对比 HTML

                        import difflib

text1 = 'hello world
'
text2 = 'hello python
'

# 生成 HTML 格式的对比结果
d = difflib.HtmlDiff()
html = d.make_file(text1.splitlines(), text2.splitlines())

with open('diff.html', 'w', encoding='utf-8') as f:
    f.write(html)
                    

四、文本相似度计算

4.1 编辑距离（Levenshtein）

编辑距离是指将一个字符串转换成另一个字符串所需的最少编辑操作次数。

                        import Levenshtein

# 计算编辑距离
distance = Levenshtein.distance('hello', 'hallo')
print(f"编辑距离: {distance}")  # 1

# 计算相似度
similarity = Levenshtein.ratio('hello', 'hallo')
print(f"相似度: {similarity}")  # 0.8
                    

4.2 Jaccard 相似度

基于集合的相似度计算，适合长文本。

                        def jaccard_similarity(text1, text2):
    """计算 Jaccard 相似度"""
    set1 = set(text1)
    set2 = set(text2)
    
    intersection = set1 & set2
    union = set1 | set2
    
    return len(intersection) / len(union)

# 使用
sim = jaccard_similarity('hello world', 'hello python')
print(f"Jaccard 相似度: {sim}")
                    

4.3 余弦相似度

基于词频向量的相似度计算，适合文章级别的对比。

                        from collections import Counter
import math

def cosine_similarity(text1, text2):
    """计算余弦相似度"""
    # 分词
    words1 = text1.split()
    words2 = text2.split()
    
    # 统计词频
    counter1 = Counter(words1)
    counter2 = Counter(words2)
    
    # 获取所有词
    all_words = set(counter1.keys()) | set(counter2.keys())
    
    # 构建向量
    vec1 = [counter1.get(word, 0) for word in all_words]
    vec2 = [counter2.get(word, 0) for word in all_words]
    
    # 计算点积
    dot_product = sum(a * b for a, b in zip(vec1, vec2))
    
    # 计算模长
    norm1 = math.sqrt(sum(a * a for a in vec1))
    norm2 = math.sqrt(sum(a * a for a in vec2))
    
    # 计算余弦相似度
    if norm1 == 0 or norm2 == 0:
        return 0
    
    return dot_product / (norm1 * norm2)

# 使用
sim = cosine_similarity('hello world python', 'hello python world')
print(f"余弦相似度: {sim}")  # 1.0（完全相同）
                    

五、数据去重应用

5.1 简单去重

                        import hashlib

def get_content_hash(content):
    """计算内容哈希"""
    return hashlib.md5(content.encode('utf-8')).hexdigest()

# 去重
seen_hashes = set()
unique_items = []

for item in data:
    content_hash = get_content_hash(item['content'])
    if content_hash not in seen_hashes:
        seen_hashes.add(content_hash)
        unique_items.append(item)

print(f"去重前: {len(data)} 条")
print(f"去重后: {len(unique_items)} 条")
                    

5.2 相似度去重

                        import Levenshtein

def find_similar_items(items, threshold=0.8):
    """查找相似内容"""
    duplicates = []
    
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            similarity = Levenshtein.ratio(items[i], items[j])
            if similarity > threshold:
                duplicates.append((i, j, similarity))
    
    return duplicates

# 使用
items = [
    'Python 爬虫入门教程',
    'Python 爬虫入门指南',
    'JavaScript 基础教程'
]

duplicates = find_similar_items(items, threshold=0.8)
for i, j, sim in duplicates:
    print(f"相似度 {sim:.2f}: '{items[i]}' vs '{items[j]}'")
                    

5.3 增量更新检测

                        import hashlib

class ContentTracker:
    def __init__(self):
        self.content_hashes = {}
    
    def has_changed(self, url, content):
        """检测内容是否变化"""
        content_hash = hashlib.md5(content.encode('utf-8')).hexdigest()
        
        if url not in self.content_hashes:
            self.content_hashes[url] = content_hash
            return True
        
        if self.content_hashes[url] != content_hash:
            self.content_hashes[url] = content_hash
            return True
        
        return False

# 使用
tracker = ContentTracker()

# 第一次采集
if tracker.has_changed('https://example.com', 'content v1'):
    print("内容已更新，保存")

# 第二次采集（相同内容）
if tracker.has_changed('https://example.com', 'content v1'):
    print("内容已更新，保存")
else:
    print("内容未变化，跳过")

# 第三次采集（内容变化）
if tracker.has_changed('https://example.com', 'content v2'):
    print("内容已更新，保存")
                    

六、总结

文本对比算法在爬虫开发中很实用。根据场景选择合适的算法：

算法	适用场景	特点
diff	查看具体差异	显示增删改位置
编辑距离	短文本相似度	精确但计算量大
Jaccard	长文本相似度	简单快速
余弦相似度	文章相似度	考虑词频
哈希	精确去重	最快

对于爬虫数据去重，我的建议是：先用哈希做精确去重，再用相似度算法做模糊去重。这样既保证效率，又能处理内容微调的情况。

← 返回博客列表