MinHash + LSH：1 億文書から似たペアを高速発見する確率的アルゴリズム

# pip install datasketchfrom datasketch import MinHash, MinHashLSH
def make_minhash(text, num_perm=128):    '''テキストを MinHash signature に変換'''    m = MinHash(num_perm=num_perm)    for word in text.lower().split():        m.update(word.encode('utf-8'))    return m
# サンプル文書documents = {    'doc1': 'the quick brown fox jumps over the lazy dog',    'doc2': 'the quick brown fox jumps over the lazy cat',  # 1 word 違い    'doc3': 'a completely different document about machine learning',    'doc4': 'the lazy dog sleeps under the warm sun',    'doc5': 'the quick brown fox jumps over the sleepy dog',  # 2 words 違い}
# MinHash 計算minhashes = {k: make_minhash(v) for k, v in documents.items()}
# LSH index に投入lsh = MinHashLSH(threshold=0.5, num_perm=128)for k, m in minhashes.items():    lsh.insert(k, m)
# クエリ: doc1 と類似するものresult = lsh.query(minhashes['doc1'])print(f'doc1 と類似 (threshold=0.5): {result}')
# Jaccard 推定値の確認print('\nJaccard 類似度 (推定):')for a in documents:    for b in documents:        if a < b:            j = minhashes[a].jaccard(minhashes[b])            print(f'  {a} vs {b}: {j:.3f}')
# 実機実行結果:# doc1 と類似 (threshold=0.5): ['doc5', 'doc1', 'doc2']# doc1 vs doc2: 0.758# doc1 vs doc5: 0.789# doc1 vs doc3: 0.000 (全く違う)

# 各文書を MinHash に変換 (Spark / Dask で並列化)# 1 文書 ≈ 512B、1 億で 50 GB → 分散ストア
# datasketch の MinHashLSH は Redis backend にも対応from datasketch import MinHashLSH
# Redis をストレージとして使うlsh = MinHashLSH(    threshold=0.7,    num_perm=128,    storage_config={'type': 'redis', 'redis': {'host': 'localhost', 'port': 6379}})
# 100 万件投入後、クエリ# similar = lsh.query(query_minhash)