MinHash 与 SimHash：海量文本相似度检测

import hashlib

def shingle_hash(text, k=5):
    """将文本转为 k-shingle 的哈希集合"""
    shingles = set()
    for i in range(len(text) - k + 1):
        token = text[i:i+k]
        h = int(hashlib.md5(token.encode('utf-8')).hexdigest(), 16) % (2**32)
        shingles.add(h)
    return shingles

import random

class MinHashFamily:
    """MinHash 签名生成器"""

    def __init__(self, num_hashes, prime=2**31 - 1):
        self.num_hashes = num_hashes
        self.prime = prime
        self.a = [random.randint(1, prime - 1) for _ in range(num_hashes)]
        self.b = [random.randint(0, prime - 1) for _ in range(num_hashes)]

    def hash_func(self, i, x):
        return (self.a[i] * x + self.b[i]) % self.prime

    def signature(self, shingle_set):
        """计算集合的 MinHash 签名"""
        sig = [float('inf')] * self.num_hashes
        for x in shingle_set:
            for i in range(self.num_hashes):
                val = self.hash_func(i, x)
                if val < sig[i]:
                    sig[i] = val
        return sig

    def jaccard_estimate(self, sig_a, sig_b):
        """根据签名估计 Jaccard 相似度"""
        equal = sum(1 for a, b in zip(sig_a, sig_b) if a == b)
        return equal / self.num_hashes

class LSH:
    """基于 Banding 的 LSH 索引"""

    def __init__(self, num_bands, rows_per_band):
        self.b = num_bands
        self.r = rows_per_band
        self.buckets = [{} for _ in range(num_bands)]

    def _band_hash(self, band_values):
        """将一个 band 的值映射到桶 ID"""
        return hash(tuple(band_values))

    def index(self, doc_id, signature):
        """将文档签名加入索引"""
        for band_idx in range(self.b):
            start = band_idx * self.r
            end = start + self.r
            band = signature[start:end]
            bucket_id = self._band_hash(band)
            if bucket_id not in self.buckets[band_idx]:
                self.buckets[band_idx][bucket_id] = set()
            self.buckets[band_idx][bucket_id].add(doc_id)

    def query(self, signature):
        """查询与给定签名相似的候选文档"""
        candidates = set()
        for band_idx in range(self.b):
            start = band_idx * self.r
            end = start + self.r
            band = signature[start:end]
            bucket_id = self._band_hash(band)
            if bucket_id in self.buckets[band_idx]:
                candidates.update(self.buckets[band_idx][bucket_id])
        return candidates

import hashlib
import struct

def simhash(features, weights=None, f=64):
    """
    计算 SimHash 指纹

    features: 特征列表（字符串）
    weights: 对应权重（默认全为 1）
    f: 指纹位数
    """
    if weights is None:
        weights = [1.0] * len(features)

    v = [0.0] * f
    for feature, weight in zip(features, weights):
        h = _hash_feature(feature, f)
        for j in range(f):
            if h & (1 << j):
                v[j] += weight
            else:
                v[j] -= weight

    fingerprint = 0
    for j in range(f):
        if v[j] > 0:
            fingerprint |= (1 << j)
    return fingerprint


def _hash_feature(feature, f=64):
    """将特征映射到 f-bit 哈希值"""
    digest = hashlib.md5(feature.encode('utf-8')).digest()
    if f <= 64:
        return struct.unpack('<Q', digest[:8])[0] & ((1 << f) - 1)
    else:
        val = int.from_bytes(digest, 'little')
        return val & ((1 << f) - 1)


def hamming_distance(a, b):
    """计算两个整数的 Hamming 距离"""
    x = a ^ b
    count = 0
    while x:
        count += 1
        x &= x - 1   # Brian Kernighan 算法
    return count


def simhash_similarity(a, b, f=64):
    """将 Hamming 距离转换为相似度 [0, 1]"""
    d = hamming_distance(a, b)
    return 1.0 - d / f

class SimHashIndex:
    """基于分块的 SimHash 索引，支持 Hamming 距离 <= k 的查询"""

    def __init__(self, f=64, num_blocks=4):
        self.f = f
        self.num_blocks = num_blocks
        self.block_bits = f // num_blocks
        self.tables = [{} for _ in range(num_blocks)]
        self.fingerprints = {}  # doc_id -> fingerprint

    def _get_block(self, fingerprint, block_idx):
        """提取指纹的第 block_idx 块"""
        shift = block_idx * self.block_bits
        mask = (1 << self.block_bits) - 1
        return (fingerprint >> shift) & mask

    def add(self, doc_id, fingerprint):
        """添加文档指纹"""
        self.fingerprints[doc_id] = fingerprint
        for i in range(self.num_blocks):
            block = self._get_block(fingerprint, i)
            if block not in self.tables[i]:
                self.tables[i][block] = set()
            self.tables[i][block].add(doc_id)

    def query(self, fingerprint, max_distance=3):
        """查询 Hamming 距离不超过 max_distance 的文档"""
        candidates = set()
        for i in range(self.num_blocks):
            block = self._get_block(fingerprint, i)
            if block in self.tables[i]:
                candidates.update(self.tables[i][block])

        results = []
        for doc_id in candidates:
            d = hamming_distance(fingerprint, self.fingerprints[doc_id])
            if d <= max_distance:
                results.append((doc_id, d))
        return sorted(results, key=lambda x: x[1])

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>

#define MAX_SHINGLES  100000
#define PRIME         2147483647ULL  /* 2^31 - 1，梅森素数 */

typedef struct {
    uint64_t *a;      /* 哈希系数 a */
    uint64_t *b;      /* 哈希系数 b */
    int       k;      /* 哈希函数个数 */
} MinHasher;

typedef struct {
    uint32_t *values;  /* 签名值数组 */
    int       k;
} Signature;

/* 初始化 MinHash 生成器 */
MinHasher *minhash_create(int num_hashes)
{
    MinHasher *mh = malloc(sizeof(MinHasher));
    mh->k = num_hashes;
    mh->a = malloc(sizeof(uint64_t) * num_hashes);
    mh->b = malloc(sizeof(uint64_t) * num_hashes);

    for (int i = 0; i < num_hashes; i++) {
        mh->a[i] = (uint64_t)rand() % (PRIME - 1) + 1;
        mh->b[i] = (uint64_t)rand() % PRIME;
    }
    return mh;
}

void minhash_free(MinHasher *mh)
{
    free(mh->a);
    free(mh->b);
    free(mh);
}

/* 单个哈希函数计算 */
static inline uint32_t hash_func(uint64_t a, uint64_t b, uint32_t x)
{
    return (uint32_t)((a * (uint64_t)x + b) % PRIME);
}

/* 计算一个集合的 MinHash 签名 */
Signature *minhash_signature(MinHasher *mh,
                             uint32_t *shingles, int num_shingles)
{
    Signature *sig = malloc(sizeof(Signature));
    sig->k = mh->k;
    sig->values = malloc(sizeof(uint32_t) * mh->k);

    for (int i = 0; i < mh->k; i++)
        sig->values[i] = UINT32_MAX;

    for (int s = 0; s < num_shingles; s++) {
        for (int i = 0; i < mh->k; i++) {
            uint32_t val = hash_func(mh->a[i], mh->b[i], shingles[s]);
            if (val < sig->values[i])
                sig->values[i] = val;
        }
    }
    return sig;
}

void signature_free(Signature *sig)
{
    free(sig->values);
    free(sig);
}

/* 根据签名估计 Jaccard 相似度 */
double jaccard_estimate(Signature *a, Signature *b)
{
    if (a->k != b->k) return -1.0;
    int match = 0;
    for (int i = 0; i < a->k; i++) {
        if (a->values[i] == b->values[i])
            match++;
    }
    return (double)match / a->k;
}

/*
 * LSH 索引（简化版，单桶哈希）
 * 生产系统中应使用更高效的哈希表实现
 */
#define MAX_DOCS    1000000
#define MAX_BUCKET  (1 << 20)

typedef struct BucketNode {
    int doc_id;
    struct BucketNode *next;
} BucketNode;

typedef struct {
    int num_bands;
    int rows_per_band;
    BucketNode **buckets;  /* num_bands * MAX_BUCKET */
} LSHIndex;

LSHIndex *lsh_create(int num_bands, int rows_per_band)
{
    LSHIndex *lsh = malloc(sizeof(LSHIndex));
    lsh->num_bands = num_bands;
    lsh->rows_per_band = rows_per_band;

    size_t total = (size_t)num_bands * MAX_BUCKET;
    lsh->buckets = calloc(total, sizeof(BucketNode *));
    return lsh;
}

/* FNV-1a 哈希，将一个 band 的值映射到桶 */
static uint32_t band_hash(uint32_t *values, int r)
{
    uint32_t h = 2166136261u;
    for (int i = 0; i < r; i++) {
        h ^= values[i];
        h *= 16777619u;
    }
    return h % MAX_BUCKET;
}

void lsh_insert(LSHIndex *lsh, int doc_id, Signature *sig)
{
    for (int b = 0; b < lsh->num_bands; b++) {
        int start = b * lsh->rows_per_band;
        uint32_t bucket = band_hash(&sig->values[start],
                                    lsh->rows_per_band);
        size_t idx = (size_t)b * MAX_BUCKET + bucket;

        BucketNode *node = malloc(sizeof(BucketNode));
        node->doc_id = doc_id;
        node->next = lsh->buckets[idx];
        lsh->buckets[idx] = node;
    }
}

/*
 * 查询候选对：返回与给定签名在任何 band 中同桶的文档 ID
 * 调用者负责去重和精确验证
 */
int lsh_query(LSHIndex *lsh, Signature *sig,
              int *result_buf, int max_results)
{
    int count = 0;
    for (int b = 0; b < lsh->num_bands; b++) {
        int start = b * lsh->rows_per_band;
        uint32_t bucket = band_hash(&sig->values[start],
                                    lsh->rows_per_band);
        size_t idx = (size_t)b * MAX_BUCKET + bucket;

        BucketNode *node = lsh->buckets[idx];
        while (node && count < max_results) {
            result_buf[count++] = node->doc_id;
            node = node->next;
        }
    }
    return count;
}

void lsh_free(LSHIndex *lsh)
{
    size_t total = (size_t)lsh->num_bands * MAX_BUCKET;
    for (size_t i = 0; i < total; i++) {
        BucketNode *node = lsh->buckets[i];
        while (node) {
            BucketNode *tmp = node;
            node = node->next;
            free(tmp);
        }
    }
    free(lsh->buckets);
    free(lsh);
}

/* 演示 */
int main(void)
{
    srand(42);
    uint32_t set_a[] = {1, 2, 3, 4, 5, 6, 7, 8};
    uint32_t set_b[] = {1, 2, 3, 4, 5, 9, 10, 11};
    uint32_t set_c[] = {20, 21, 22, 23, 24, 25, 26, 27};

    MinHasher *mh = minhash_create(100);
    Signature *sig_a = minhash_signature(mh, set_a, 8);
    Signature *sig_b = minhash_signature(mh, set_b, 8);
    Signature *sig_c = minhash_signature(mh, set_c, 8);

    printf("J_hat(A,B) = %.3f  (真实: 5/11 ≈ 0.455)\n",
           jaccard_estimate(sig_a, sig_b));
    printf("J_hat(A,C) = %.3f  (真实: 0.000)\n",
           jaccard_estimate(sig_a, sig_c));

    LSHIndex *lsh = lsh_create(20, 5);
    lsh_insert(lsh, 0, sig_a);
    lsh_insert(lsh, 1, sig_b);
    lsh_insert(lsh, 2, sig_c);

    int results[100];
    int n = lsh_query(lsh, sig_a, results, 100);
    printf("LSH 候选对：");
    for (int i = 0; i < n; i++) printf(" %d", results[i]);
    printf("\n");

    signature_free(sig_a); signature_free(sig_b); signature_free(sig_c);
    lsh_free(lsh); minhash_free(mh);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

/* FNV-1a 64-bit 哈希 */
static uint64_t fnv1a_64(const char *data, size_t len)
{
    uint64_t h = 14695981039346656037ULL;
    for (size_t i = 0; i < len; i++) {
        h ^= (uint8_t)data[i];
        h *= 1099511628211ULL;
    }
    return h;
}

/* 计算 64-bit SimHash */
uint64_t simhash_compute(const char **features, const double *weights,
                         int n)
{
    double v[64];
    memset(v, 0, sizeof(v));

    for (int i = 0; i < n; i++) {
        uint64_t h = fnv1a_64(features[i], strlen(features[i]));
        double w = weights ? weights[i] : 1.0;
        for (int j = 0; j < 64; j++) {
            if (h & (1ULL << j))
                v[j] += w;
            else
                v[j] -= w;
        }
    }

    uint64_t fingerprint = 0;
    for (int j = 0; j < 64; j++) {
        if (v[j] > 0)
            fingerprint |= (1ULL << j);
    }
    return fingerprint;
}

/* 利用 popcount 的快速 Hamming 距离 */
static inline int hamming_dist(uint64_t a, uint64_t b)
{
    return __builtin_popcountll(a ^ b);
}

/* 分块索引：64-bit 分成 4 个 16-bit 块 */
#define NUM_BLOCKS   4
#define BLOCK_BITS   16
#define TABLE_SIZE   (1 << BLOCK_BITS)

typedef struct DocEntry {
    int              doc_id;
    uint64_t         fingerprint;
    struct DocEntry *next;
} DocEntry;

typedef struct {
    DocEntry *tables[NUM_BLOCKS][TABLE_SIZE];
} SimHashIndex;

static inline uint16_t get_block(uint64_t fp, int block)
{
    return (uint16_t)((fp >> (block * BLOCK_BITS)) & 0xFFFF);
}

void simhash_index_add(SimHashIndex *idx, int doc_id, uint64_t fp)
{
    for (int b = 0; b < NUM_BLOCKS; b++) {
        uint16_t key = get_block(fp, b);
        DocEntry *entry = malloc(sizeof(DocEntry));
        entry->doc_id = doc_id;
        entry->fingerprint = fp;
        entry->next = idx->tables[b][key];
        idx->tables[b][key] = entry;
    }
}

int simhash_index_query(SimHashIndex *idx, uint64_t fp,
                        int max_dist, int *results, int max_results)
{
    int count = 0;
    for (int b = 0; b < NUM_BLOCKS; b++) {
        uint16_t key = get_block(fp, b);
        for (DocEntry *e = idx->tables[b][key]; e && count < max_results; e = e->next) {
            if (hamming_dist(fp, e->fingerprint) <= max_dist)
                results[count++] = e->doc_id;
        }
    }
    return count;
}

int main(void)
{
    const char *doc_a[] = {"hello", "world", "foo", "bar", "test"};
    const char *doc_b[] = {"hello", "world", "foo", "baz", "test"};
    const char *doc_c[] = {"alpha", "beta", "gamma", "delta", "epsilon"};

    uint64_t fp_a = simhash_compute(doc_a, NULL, 5);
    uint64_t fp_b = simhash_compute(doc_b, NULL, 5);
    uint64_t fp_c = simhash_compute(doc_c, NULL, 5);

    printf("Hamming(A,B) = %d\n", hamming_dist(fp_a, fp_b));
    printf("Hamming(A,C) = %d\n", hamming_dist(fp_a, fp_c));

    SimHashIndex idx = {{{0}}};
    simhash_index_add(&idx, 0, fp_a);
    simhash_index_add(&idx, 1, fp_b);
    simhash_index_add(&idx, 2, fp_c);

    int results[100];
    int n = simhash_index_query(&idx, fp_a, 3, results, 100);
    printf("SimHash 近似文档（Hamming<=3）：");
    for (int i = 0; i < n; i++)
        printf(" doc_%d", results[i]);
    printf("\n");
    return 0;
}

"""
MinHash + LSH + SimHash 完整流水线
用于文本近似重复检测
"""

import hashlib
import random
import struct
from collections import defaultdict


# ==================== Shingling ====================

def text_to_shingles(text, k=5):
    """将文本转为字符级 k-shingle 哈希集合"""
    shingles = set()
    text = text.lower().strip()
    for i in range(len(text) - k + 1):
        token = text[i:i + k]
        h = struct.unpack('<I',
            hashlib.md5(token.encode('utf-8')).digest()[:4])[0]
        shingles.add(h)
    return shingles


# ==================== MinHash ====================

class MinHash:
    """MinHash 签名生成器"""

    def __init__(self, num_perm=128, seed=42):
        self.num_perm = num_perm
        self.prime = (1 << 31) - 1
        rng = random.Random(seed)
        self.a = [rng.randint(1, self.prime - 1) for _ in range(num_perm)]
        self.b = [rng.randint(0, self.prime - 1) for _ in range(num_perm)]

    def signature(self, shingle_set):
        """计算集合的 MinHash 签名"""
        sig = [float('inf')] * self.num_perm
        for elem in shingle_set:
            for i in range(self.num_perm):
                val = (self.a[i] * elem + self.b[i]) % self.prime
                if val < sig[i]:
                    sig[i] = val
        return sig

    @staticmethod
    def jaccard_from_sigs(sig_a, sig_b):
        """根据签名估计 Jaccard 相似度"""
        matches = sum(1 for a, b in zip(sig_a, sig_b) if a == b)
        return matches / len(sig_a)


# ==================== LSH ====================

class LSHIndex:
    """基于 Banding 的 LSH 索引"""

    def __init__(self, num_bands, rows_per_band):
        self.num_bands = num_bands
        self.rows_per_band = rows_per_band
        self.hash_tables = [defaultdict(set) for _ in range(num_bands)]

    def insert(self, doc_id, signature):
        """将文档签名加入索引"""
        for band_idx in range(self.num_bands):
            start = band_idx * self.rows_per_band
            end = start + self.rows_per_band
            band = tuple(signature[start:end])
            self.hash_tables[band_idx][band].add(doc_id)

    def query(self, signature):
        """查询候选相似文档"""
        candidates = set()
        for band_idx in range(self.num_bands):
            start = band_idx * self.rows_per_band
            end = start + self.rows_per_band
            band = tuple(signature[start:end])
            candidates.update(self.hash_tables[band_idx][band])
        return candidates


# ==================== SimHash ====================

class SimHash:
    """64-bit SimHash 指纹生成器"""

    def __init__(self, f=64):
        self.f = f

    def fingerprint(self, features, weights=None):
        """计算 SimHash 指纹"""
        if weights is None:
            weights = [1.0] * len(features)

        v = [0.0] * self.f
        for feat, w in zip(features, weights):
            h = self._hash_feature(feat)
            for j in range(self.f):
                if h & (1 << j):
                    v[j] += w
                else:
                    v[j] -= w

        result = 0
        for j in range(self.f):
            if v[j] > 0:
                result |= (1 << j)
        return result

    def _hash_feature(self, feature):
        digest = hashlib.md5(feature.encode('utf-8')).digest()
        val = struct.unpack('<Q', digest[:8])[0]
        return val & ((1 << self.f) - 1)

    @staticmethod
    def hamming(a, b):
        x = a ^ b
        count = 0
        while x:
            count += 1
            x &= x - 1
        return count

    def similarity(self, a, b):
        return 1.0 - self.hamming(a, b) / self.f


# ==================== 完整流水线 ====================

def dedup_pipeline(documents, threshold=0.5,
                   num_perm=128, num_bands=16, rows_per_band=8):
    """
    文本去重完整流水线

    documents: dict of {doc_id: text}
    threshold: Jaccard 相似度阈值
    返回: 近似重复的文档对列表
    """
    mh = MinHash(num_perm=num_perm)
    lsh = LSHIndex(num_bands=num_bands, rows_per_band=rows_per_band)

    # 第一步：计算签名并索引
    signatures = {}
    shingle_sets = {}
    for doc_id, text in documents.items():
        shingles = text_to_shingles(text)
        shingle_sets[doc_id] = shingles
        sig = mh.signature(shingles)
        signatures[doc_id] = sig
        lsh.insert(doc_id, sig)

    # 第二步：查找候选对
    candidate_pairs = set()
    for doc_id, sig in signatures.items():
        candidates = lsh.query(sig)
        for cand_id in candidates:
            if cand_id != doc_id:
                pair = tuple(sorted([doc_id, cand_id]))
                candidate_pairs.add(pair)

    # 第三步：精确验证
    duplicates = []
    for id_a, id_b in candidate_pairs:
        set_a = shingle_sets[id_a]
        set_b = shingle_sets[id_b]
        jaccard = len(set_a & set_b) / len(set_a | set_b) if set_a | set_b else 0
        if jaccard >= threshold:
            duplicates.append((id_a, id_b, jaccard))

    return sorted(duplicates, key=lambda x: -x[2])


# ==================== 演示 ====================

if __name__ == '__main__':
    docs = {
        'doc1': '今天天气真好，适合出去散步和锻炼身体',
        'doc2': '今天天气真好，非常适合出去散步锻炼身体',
        'doc3': '量子计算机可以在某些问题上超越经典计算机',
        'doc4': '深度学习模型需要大量的训练数据和计算资源',
    }

    print('=== MinHash + LSH 去重 ===')
    results = dedup_pipeline(docs, threshold=0.3,
                             num_perm=128, num_bands=16, rows_per_band=8)
    for id_a, id_b, sim in results:
        print(f'  {id_a} <-> {id_b}: Jaccard = {sim:.3f}')

    print('\n=== SimHash Hamming 距离 ===')
    sh = SimHash(f=64)
    fps = {did: sh.fingerprint(list(text)) for did, text in docs.items()}
    ids = list(docs.keys())
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            d = SimHash.hamming(fps[ids[i]], fps[ids[j]])
            print(f'  {ids[i]} <-> {ids[j]}: Hamming = {d}')

import numpy as np

def minhash_vectorized(shingles, a_coeffs, b_coeffs, prime):
    """shingles: (n,), a/b: (k,) → 返回 (k,) 签名"""
    s = shingles.astype(np.uint64)
    a = a_coeffs.astype(np.uint64).reshape(-1, 1)
    b = b_coeffs.astype(np.uint64).reshape(-1, 1)
    return ((a * s + b) % prime).min(axis=1)

# Redis 索引/查询伪代码
for band_idx in range(b):
    key = f"lsh:band:{band_idx}:{band_hash}"
    redis.sadd(key, doc_id)       # 索引
    candidates |= redis.smembers(key)  # 查询