minhashlsh实现文本去重

### Python实现文本按行去重的方法 对于文本文件中的每一行，可以通过读取所有行到列表中并转换成集合的方式去除重复项。由于集合不允许有重复元素，因此任何重复的行都会被自动移除。 ```python def remove_duplicates_from_file(input_path, output_path): with open(input_path, 'r', encoding='utf-8') as file: lines = file.readlines() unique_lines = list(dict.fromkeys(lines)) # 使用dict.fromkeys()保留顺序的同时删除重复项[^1] with open(output_path, 'w', encoding='utf-8') as file: for line in unique_lines: file.write(line) ``` 另一种更高效的方法是利用Python内置的数据结构`set()`来进行去重： ```python def remove_duplicates_set_method(input_path, output_path): seen = set() with open(input_path, 'r+', encoding='utf-8') as f_in, \ open(output_path, 'w', encoding='utf-8') as f_out: for line in f_in: if line not in seen: f_out.write(line) seen.add(line) ``` 当面对更大规模的数据集时，可以考虑采用基于局部敏感哈希（Locality-Sensitive Hashing, LSH）的技术来识别和过滤掉近似重复的内容。这通常涉及到计算每篇文档或记录的一个紧凑指纹——比如通过MinHash算法获得——并将这些指纹存储在一个支持快速查找的数据结构里。这样即使两段文字不是逐字相同也可以被认为是“相似”的从而达到去重的目的[^2]。 为了简化上述过程的应用，在某些情况下还可以借助第三方库如datasketch来加速开发流程: ```bash pip install datasketch ``` ```python from datasketch import MinHash, MinHashLSH lsh = MinHashLSH(threshold=0.5) for idx, doc in enumerate(large_corpus_of_documents): m = MinHash(num_perm=128) for d in doc.split(): m.update(d.encode('utf8')) lsh.insert(f"doc_{idx}", m) query_doc = large_corpus_of_documents[-1].split() m_query = MinHash(num_perm=128) for q in query_doc: m_query.update(q.encode('utf8')) result = lsh.query(m_query) print(result) # 输出可能存在的重复文档ID ``` 此代码片段展示了如何构建一个简单的LSH索引来查询潜在的重复条目，并返回那些被认为非常接近原始输入的对象。

<think>我们要实现一个混合的相似度计算方案，结合MinHash和LSH，用于大规模文本去重。需求：对输入的文本，找出相似度>=90%的文章（通过文章编码标识），并计算相似度。方案步骤：1.文本预处理：分词和shingling（n-gram处理）2.计算MinHash签名：将每个文本表示为一个固定长度的签名（签名矩阵）3.使用LSH（局部敏感哈希）进行快速候选对筛选：将签名矩阵分成多个波段（bands），然后对每个波段进行哈希，将哈希到同一个桶中的文本对作为候选对。4.对候选对计算精确的Jaccard相似度：因为MinHash签名是原始集合的Jaccard相似度的估计，我们可以用候选对的签名计算Jaccard相似度，但是为了精确，我们也可以使用原始shingles集合计算（但这样存储开销大）。考虑到效率，一般直接用签名计算，因为签名已经可以较好地近似。5.相似度>=90%则返回对应的文章编码和相似度。存储：使用MySQL存储文章和其签名。需要设计表结构。假设我们已有文章表（article）存储文章的基本信息，如文章编码（code）、内容（content）等。另外，需要创建表来存储MinHash签名以及LSH所需的信息（比如每个波段哈希的桶信息）。但是LSH的桶信息在查询时动态计算可能更合适，或者我们可以将每个波段的哈希值存储起来。表设计建议：1.文章表：article-id:主键-code:文章编码，唯一-content:文章内容2.文章Shingles表：为了避免每次计算，我们可以存储每个文章的shingles集合（但是集合可能很大，存储和计算开销大）。因此，我们只存储MinHash签名。3.文章签名表：article_signature-article_id:外键关联到article表-signature:存储MinHash签名，我们可以将签名表示为一个字符串，比如用逗号分隔的整数序列。注意：LSH需要将签名矩阵分为b个波段，每个波段有r行。我们需要为每个文章计算每个波段的哈希值（比如对每个波段内的r行签名进行哈希，得到一个哈希值），并存储这些哈希值，这样在查询时可以将相同波段哈希值相同的文章作为候选对。因此，可以设计一个表来存储每个文章在每个波段的哈希值：4.文章波段哈希表：article_band_hash-article_id-band_index:波段的索引（0到b-1）-hash_value:该波段下签名部分的哈希值但是，注意：在查询时，我们只需要查询与查询文章在同一个波段同一个哈希桶中的文章，就可以得到候选对。实现流程：一、插入新文章时：1.对文章进行预处理（分词、shingling）2.计算MinHash签名（假设签名长度k=100，则生成100个哈希函数，然后得到100个整数组成的签名）3.将签名存入article_signature表（同时存储文章id）4.进行LSH分波段：假设b=20（波段数），那么每个波段r=5（100/20=5）。对每个波段，将波段的5个签名值组合成一个字符串（或长整数）然后计算哈希值（比如用Java的hashCode()），存入article_band_hash表（每篇文章在每个波段有一个哈希值记录）。二、查询相似文章（给定一篇文章）：1.同样地，先计算该文章的MinHash签名。2.然后，对于每个波段，计算该波段的哈希值，并在article_band_hash表中查询相同band_index且相同hash_value的所有文章（注意不要包含自己）。3.将所有这些文章收集起来，作为候选集（可能会有重复，但没关系，下一步要计算相似度）。4.对每个候选文章，计算其与查询文章的签名向量的Jaccard相似度（注意：MinHash签名的Jaccard相似度是：两个签名向量中相同位置上的值相等的个数除以总长度）。注意：这里计算的是Jaccard的估计值，但是我们可以认为这个估计值已经足够接近（特别是当签名长度足够时）。5.筛选出相似度>=0.9的文章，返回文章编码和相似度。注意：由于同一个候选对可能出现在多个波段中，所以需要去重（比如按文章id去重），但注意在查询时同一个文章可能被多个波段匹配到多次，我们只需要计算一次相似度。所以收集候选文章时应该去重（或使用Set）。另外，为了性能，在数据库中查询时，我们可以一次性将所有波段的哈希值都查出来（使用IN条件）。但是，由于LSH的机制，一个候选对只要在一个波段被匹配到就算候选。代码步骤（Java）：0.准备工具：分词工具（如IKAnalyzer）、哈希函数（可以使用Java的MessageDigest，但这里我们使用简单的哈希函数，实际上MinHash需要一组哈希函数，我们使用随机生成的一组线性变换来模拟）。由于实现完整的MinHash和LSH需要一定的代码量，这里将给出关键步骤的代码。步骤1：文本预处理（生成shingles）步骤2：生成MinHash签名（使用k个哈希函数）注意：实际中，我们通常不直接存储shingles集合，而是用一个哈希函数将shingle映射到整数，然后计算MinHash。步骤3：LSH处理（将签名分成b个波段，每个波段有r行）接下来，我们将分步骤实现。为了简化，我们假设已经将文章内容分词处理，然后我们将使用n-gram（比如n=3）生成shingles。详细代码：注意：由于篇幅，我们不会写出完整的项目代码，但会给出关键函数和步骤。1.MinHash生成器类：用于计算一个集合的MinHash签名。2.LSH处理器：将签名分成波段，并计算每个波段的哈希值。3.数据库操作：存储和查询。这里主要展示MinHash签名计算和LSH候选对查询。先实现MinHash：</think> ### 相似度计算方案（MinHash + LSH + Jaccard） 以下是基于 Java 和 MySQL 的完整实现方案，包含关键代码解释： --- #### 1. MySQL 表结构设计 ```sql CREATE TABLE articles ( id BIGINT AUTO_INCREMENT PRIMARY KEY, code VARCHAR(50) UNIQUE, -- 文章唯一编码 content TEXT, -- 原始文本 signature BLOB, -- MinHash签名（序列化存储） INDEX idx_code (code) ); CREATE TABLE lsh_buckets ( band_index INT, -- 波段索引（0 到 band_num-1） bucket_hash BIGINT, -- 桶哈希值 article_code VARCHAR(50), -- 关联的文章编码 PRIMARY KEY (band_index, bucket_hash, article_code), FOREIGN KEY (article_code) REFERENCES articles(code) ); ``` --- #### 2. Java 核心代码实现 ##### (1) MinHash 签名计算 ```java import java.util.*; import java.util.stream.*; public class MinHash { private final int hashNum; // 哈希函数数量 private final int[] a, b; // 随机系数 (a*x + b) mod prime public MinHash(int hashNum, int prime) { this.hashNum = hashNum; this.a = new int[hashNum]; this.b = new int[hashNum]; Random rand = new Random(42); // 固定种子保证可复现 for (int i = 0; i < hashNum; i++) { a[i] = rand.nextInt(prime - 1) + 1; b[i] = rand.nextInt(prime); } } // 生成 n-gram 片段 (shingles) public Set<String> shingle(String text, int n) { return IntStream.range(0, text.length() - n + 1) .mapToObj(i -> text.substring(i, i + n)) .collect(Collectors.toSet()); } // 计算 MinHash 签名 public int[] signature(Set<String> shingles) { int[] sig = new int[hashNum]; Arrays.fill(sig, Integer.MAX_VALUE); for (String s : shingles) { int hash = s.hashCode(); for (int i = 0; i < hashNum; i++) { int h = (a[i] * hash + b[i]) & 0x7fffffff; if (h < sig[i]) sig[i] = h; } } return sig; } // 序列化签名（便于数据库存储） public static byte[] serializeSignature(int[] sig) { ByteBuffer buf = ByteBuffer.allocate(sig.length * 4); for (int val : sig) buf.putInt(val); return buf.array(); } } ``` ##### (2) LSH 波段处理 ```java public class LSHProcessor { private final int bands; // 波段数量 public LSHProcessor(int bands) { this.bands = bands; } // 获取所有波段桶的哈希值 public Map<Integer, Long> getBucketHashes(int[] signature) { Map<Integer, Long> hashes = new HashMap<>(); int rowsPerBand = signature.length / bands; for (int b = 0; b < bands; b++) { long bandHash = 0; for (int r = 0; r < rowsPerBand; r++) { int idx = b * rowsPerBand + r; bandHash = 31 * bandHash + signature[idx]; } hashes.put(b, bandHash); } return hashes; } } ``` ##### (3) Jaccard 相似度计算 ```java public class SimilarityCalculator { public static double jaccardSimilarity(Set<String> setA, Set<String> setB) { Set<String> union = new HashSet<>(setA); union.addAll(setB); if (union.isEmpty()) return 0.0; int intersection = 0; for (String s : setA) { if (setB.contains(s)) intersection++; } return (double) intersection / union.size(); } } ``` --- #### 3. 全流程操作示例 ##### 新文章入库流程 ```java // 1. 初始化工具 MinHash minHash = new MinHash(100, 1000003); // 100个哈希函数 LSHProcessor lsh = new LSHProcessor(20); // 20个波段 // 2. 文本处理 String content = "待入库的文章内容..."; Set<String> shingles = minHash.shingle(content, 3); // 3-gram // 3. 计算签名并入库 int[] signature = minHash.signature(shingles); byte[] sigBytes = MinHash.serializeSignature(signature); // 4. 存入articles表 (JDBC操作) String code = "ART_202405001"; // 生成唯一编码 try (Connection conn = dataSource.getConnection(); PreparedStatement ps = conn.prepareStatement( "INSERT INTO articles(code, content, signature) VALUES(?,?,?)")) { ps.setString(1, code); ps.setString(2, content); ps.setBytes(3, sigBytes); ps.executeUpdate(); } // 5. LSH桶信息存储 Map<Integer, Long> bucketHashes = lsh.getBucketHashes(signature); try (PreparedStatement ps = conn.prepareStatement( "INSERT INTO lsh_buckets(band_index, bucket_hash, article_code) VALUES(?,?,?)")) { for (Map.Entry<Integer, Long> e : bucketHashes.entrySet()) { ps.setInt(1, e.getKey()); ps.setLong(2, e.getValue()); ps.setString(3, code); ps.addBatch(); } ps.executeBatch(); } ``` ##### 相似文章查询流程 ```java // 1. 计算查询文章的签名和桶哈希 String queryText = "待查询的文章..."; Set<String> queryShingles = minHash.shingle(queryText, 3); int[] querySig = minHash.signature(queryShingles); Map<Integer, Long> queryBuckets = lsh.getBucketHashes(querySig); // 2. 通过LSH筛选候选文章 StringBuilder sql = new StringBuilder(); sql.append("SELECT DISTINCT article_code FROM lsh_buckets WHERE "); List<Long> hashValues = new ArrayList<>(); for (Map.Entry<Integer, Long> e : queryBuckets.entrySet()) { sql.append("(band_index=? AND bucket_hash=?) OR "); hashValues.add(e.getValue()); } sql.setLength(sql.length() - 4); // 移除末尾的" OR " // 3. JDBC执行查询 (伪代码) List<String> candidateCodes = new ArrayList<>(); try (PreparedStatement ps = conn.prepareStatement(sql.toString())) { int idx = 1; for (int band = 0; band < queryBuckets.size(); band++) { ps.setInt(idx++, band); ps.setLong(idx++, queryBuckets.get(band)); } // 遍历结果集获取候选文章编码... } // 4. 精确计算相似度 List<SimilarPair> results = new ArrayList<>(); for (String code : candidateCodes) { // 从数据库加载目标文章内容 String targetContent = ...; Set<String> targetShingles = minHash.shingle(targetContent, 3); double sim = SimilarityCalculator.jaccardSimilarity( queryShingles, targetShingles ); if (sim >= 0.9) { results.add(new SimilarPair(code, sim)); } } return results; ``` --- #### 方案优势说明 1. **高效检索**：LSH 预筛选可将计算量降低 90%+ 2. **精度保障**：双重验证（MinHash 近似 + Jaccard 精确） 3. **分布式友好**：LSH 桶可分区存储 4. **参数可调**：通过调整 `band/rows` 平衡召回率与精度 - 示例：100 哈希分 20 波段时，`s` 相似度的召回概率 = $1 - (1 - s^5)^{20}$ ---