hojichar.filters.deduplication
This module provides filters for deduplication using MinHash and Locality-Sensitive Hashing (LSH).
If you want to use this module, install hojichar via pip install 'hojichar[dedup]'
What is MinHash LSH?
A gentle introduction for first‑time leaner for MinHash LSH
1 What problem does this solve?
When you have millions of documents it is too expensive to compare every pair directly. MinHash + Locality‑Sensitive Hashing (LSH) lets you
- estimate Jaccard similarity extremely fast, and memory‑efficiently
- retrieve near‑duplicates in sub‑linear time.
In practice you can keep a single set or Redis index of the generated LSH keys and ask:
"Does any existing document share at least one LSH key with mine?"
If the answer is yes the two documents are almost certainly similar; if no they are very likely different.
How the pipeline works
GenerateDedupLSH filter generates LSH keys for each document.
- Tokenize
- Split text into tokens. (Default: character‑level, but you can plug in any callable.)
- n-grams
- Group tokens into n‑grams (n_grams=5) to capture context.
- MinHash
- Hash each n‑gram with
num_permindependent permutations and keep only the minimum value. The resulting signature is a vector of num_perm 32‑bit integers. - This module uses
rensa.RMinHashwhich is a fast MinHash implementation by Rust language.
- Hash each n‑gram with
- Banding and compression
- Split the signature into b bands, each containing
rintegers (num_perm ≈ b×r). - Treat the
rintegers as raw bytes, hash them with xxhash‑128, and format as v2:+ .
- Split the signature into b bands, each containing
- Output
- Store all band keys in
document.extras['dedup_lsh']as a list of strings.
- Store all band keys in
InlineDeduplicator, RedisDeduplicator, and RedisBloomDeduplicator filters use the generated LSH keys to mark documents as duplicates.
InlineDeduplicatorstores LSH keys in a local set, so it works only in a single process.RedisDeduplicatorstores LSH keys in Redis, so it works in a distributed environment.RedisBloomDeduplicatorstores LSH keys in RedisBloom, which is a scalable Bloom filter. It uses less memory than Redis keys but may return false positives.
1""" 2This module provides filters for deduplication using MinHash and Locality-Sensitive Hashing (LSH). 3If you want to use this module, install hojichar via `pip install 'hojichar[dedup]'` 4 5## What is MinHash LSH? 6*A gentle introduction for first‑time leaner for MinHash LSH* 7 8--- 9 10### 1 What problem does this solve? 11 12When you have **millions of documents** it is too expensive to compare every pair directly. 13**MinHash + Locality‑Sensitive Hashing (LSH)** lets you 14 15- estimate Jaccard similarity extremely fast, and memory‑efficiently 16- retrieve **near‑duplicates** in sub‑linear time. 17 18In practice you can keep a single `set` or Redis index of the generated **LSH keys** and ask: 19"Does any existing document share *at least one* LSH key with mine?" 20 21If the answer is yes the two documents are almost certainly similar; if no they are very likely different. 22 23### How the pipeline works 24 25`GenerateDedupLSH` filter generates LSH keys for each document. 26 271. Tokenize 28 - Split text into tokens. (Default: character‑level, but you can plug in any callable.) 292. n-grams 30 - Group tokens into n‑grams (n_grams=5) to capture context. 313. MinHash 32 - Hash each n‑gram with `num_perm` independent permutations and keep only the minimum value. The resulting **signature** is a vector of num_perm 32‑bit integers. 33 - This module uses `rensa.RMinHash` which is a fast MinHash implementation by Rust language. 344. Banding and compression 35 - Split the signature into b bands, each containing `r` integers (num_perm ≈ b×r). 36 - Treat the `r` integers as raw bytes, hash them with xxhash‑128, and format as v2:<band_idx>+<digest32hex>. 375. Output 38 - Store all band keys in `document.extras['dedup_lsh']` as a list of strings. 39 40`InlineDeduplicator`, `RedisDeduplicator`, and `RedisBloomDeduplicator` filters use the generated LSH keys to mark documents as duplicates. 41 42- `InlineDeduplicator` stores LSH keys in a local set, so it works only in a single process. 43- `RedisDeduplicator` stores LSH keys in Redis, so it works in a distributed environment. 44- `RedisBloomDeduplicator` stores LSH keys in RedisBloom, which is a scalable Bloom filter. It uses less memory than Redis keys but may return false positives. 45 46""" 47 48from __future__ import annotations 49 50import importlib 51import re 52import struct 53import sys 54from collections import deque 55from collections.abc import Callable, Iterable 56from itertools import islice 57from typing import Any, Final, cast 58 59import numpy as np 60from numpy.typing import NDArray 61 62try: 63 import redis 64 import xxhash 65 from datasketch.lsh import _optimal_param # type: ignore 66 from rensa import RMinHash # type: ignore 67 68 is_loaded_dedup = True 69except ImportError: 70 is_loaded_dedup = False 71 72 73from hojichar import Document, Filter 74 75_japanese_tagger: fugashi.Tagger | None = None # type: ignore[name-defined] # noqa: F821 76NON_ALPHA = re.compile("[^A-Za-z_0-9]") 77IS_LOADED_DEDUP_ERROR_MSG = ( 78 "Failed to import redis, xxhash, rensa, or datasketch. " 79 "Please install the extra dependencies with `pip install 'hojichar[dedup]'`" 80) 81 82 83def char_level_splitter(text: str) -> list[str]: 84 """ 85 Split the text into characters. 86 This is a simple implementation that splits the text into individual characters. 87 """ 88 return list(text) 89 90 91def non_alpha_num_splitter(text: str) -> list[str]: 92 """ 93 Split the text into alphanumeric tokens. 94 This is a simple implementation that splits on non-alphanumeric characters. 95 """ 96 return [token for token in NON_ALPHA.split(text) if token] 97 98 99def _ngrams(tokens: Iterable[str], n: int) -> Iterable[tuple[str, ...]]: 100 """Yield sliding windows of *n* tokens.""" 101 iterator = iter(tokens) 102 window = deque(islice(iterator, n), maxlen=n) 103 if len(window) == n: 104 yield tuple(window) 105 for token in iterator: 106 window.append(token) 107 yield tuple(window) 108 109 110def japanese_word_splitter(text: str) -> list[str]: 111 """ 112 Split the text into Japanese words using fugashi. 113 This will import fugashi and instantiate Tagger on first use. 114 """ 115 global _japanese_tagger 116 if _japanese_tagger is None: 117 fugashi = importlib.import_module("fugashi") 118 _japanese_tagger = fugashi.Tagger() 119 return [token.surface for token in _japanese_tagger(text)] 120 121 122class GenerateDedupLSH(Filter): 123 """ 124 Filter that uses MinHash + Locality-Sensitive Hashing (LSH) to assign 125 deduplication keys to documents, allowing fast near-duplicate detection. 126 127 Attributes: 128 num_perm (int): Number of permutations (hash functions) for MinHash. 129 threshold (float): Similarity threshold for tuning LSH parameters. 130 tokenizer (Callable[[str], Iterable[str]]): Function to tokenize text. 131 n_grams (int): n-gram size for token grouping. 132 seed (int): Random seed for MinHash. 133 num_bands (int): Number of LSH bands, specified explicitly or computed automatically. 134 band_size (int): Number of hashes per band. 135 136 Notes 137 ----- 138 When band parameters are omitted, `_optimal_param` searches for the optimal 139 number of **bands** (`b`) and 140 **rows per band** (`r`) that minimise a weighted sum of false positives / 141 false negatives at the specified *threshold*. 142 143 HojiChar 0.18.0 introduces ``v2:`` keys using Rensa 0.5 and an optimized 144 hashing path. Hash generation was over 4x faster than HojiChar 0.17.3 145 in our 2,000-character English benchmark. Hashes differ from 146 HojiChar 0.17.x. Please rebuild your deduplication fingerprints, 147 or keep using HojiChar 0.17.x if you want to use existing LSH pool. 148 """ 149 150 _BYTES_PER_U32: Final[int] = 4 151 _LSH_KEY_VERSION: Final[str] = "v2" 152 153 def __init__( 154 self, 155 num_perm: int = 500, 156 threshold: float = 0.8, 157 tokenizer: Callable[[str], Iterable[str]] = char_level_splitter, 158 n_grams: int = 5, 159 seed: int = 42, 160 *, 161 num_bands: int | None = None, 162 band_size: int | None = None, 163 **kwargs: Any, 164 ) -> None: 165 """ 166 Initialize the deduplication filter with MinHash and LSH settings. 167 168 Args: 169 num_perm: Number of hash permutations for MinHash signature length. 170 Ignored when num_bands and band_size are both provided. 171 threshold: Similarity threshold to decide optimal LSH parameters. 172 Ignored when num_bands and band_size are both provided. 173 tokenizer: Function to split text into tokens. 174 n_grams: Number of tokens per n-gram for MinHash update. 175 seed: Seed for hash permutation consistency. 176 num_bands: Explicit number of LSH bands. Must be a positive integer 177 and provided together with band_size. 178 band_size: Explicit number of hashes per band. Must be a positive integer 179 and provided together with num_bands. When both are provided, 180 automatic selection is bypassed and the MinHash signature length 181 (self.num_perm) is set to num_bands * band_size. 182 **kwargs: Additional keyword arguments for parent Filter. 183 """ 184 super().__init__(**kwargs) 185 if not is_loaded_dedup: 186 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 187 if n_grams <= 0: 188 raise ValueError("n_grams must be positive") 189 self.num_perm = num_perm 190 self.threshold = threshold 191 self.tokenizer = tokenizer 192 self.n_grams = n_grams 193 self.seed = seed 194 195 if num_bands is None and band_size is None: 196 self.num_bands, self.band_size = _optimal_param( 197 threshold=self.threshold, 198 num_perm=self.num_perm, 199 false_negative_weight=0.5, 200 false_positive_weight=0.5, 201 ) 202 else: 203 if num_bands is None or band_size is None: 204 raise ValueError("num_bands and band_size must be provided together") 205 if num_bands <= 0 or band_size <= 0: 206 raise ValueError("num_bands and band_size must be positive") 207 self.num_bands = num_bands 208 self.band_size = band_size 209 self.num_perm = num_bands * band_size 210 211 def _calculate_minhash_digest(self, text: str) -> list[int]: 212 """Compute the raw digest shared by the array API and the LSH fast path.""" 213 if self.tokenizer is char_level_splitter: 214 n = self.n_grams 215 tokens = [text[i : i + n] for i in range(len(text) - n + 1)] 216 else: 217 tokens = [" ".join(grams) for grams in _ngrams(self.tokenizer(text), self.n_grams)] 218 minhash = RMinHash(num_perm=self.num_perm, seed=self.seed) 219 minhash.update(tokens) 220 return cast(list[int], minhash.digest()) 221 222 def calculate_minhash_signature(self, text: str) -> NDArray[np.uint32]: 223 """ 224 Compute MinHash signature of input text as an array of uint32. 225 226 Steps: 227 1. Tokenize text using the provided tokenizer. 228 2. Generate n-gram tokens. 229 3. Update MinHash with n-gram tokens. 230 231 Args: 232 text: Input document text to be hashed. 233 234 Returns: 235 A 1D numpy array of shape (num_perm,) with dtype uint32. 236 """ 237 return np.asarray(self._calculate_minhash_digest(text), dtype=np.uint32) 238 239 def _sig_bytes_le(self, sig: NDArray[np.uint32]) -> memoryview: 240 """ 241 Return the signature as *little-endian* byte view. 242 Platform‑independent way to get bytes from a numpy array. 243 """ 244 if sys.byteorder == "little": 245 # amd64 / arm64 (little) 246 return memoryview(cast(Any, sig)).cast("B") # zero-copy 247 else: 248 # big-endian CPU 249 return memoryview(cast(Any, sig.byteswap())).cast("B") # 1 copy 250 251 def signature_to_lsh_digest( 252 self, signature: NDArray[np.uint32], band_size: int, band_idx: int 253 ) -> int: 254 """ 255 Convert a slice of the MinHash signature into an LSH digest with less memory overhead. 256 257 This method is optimized for speed by avoiding copies: 258 - We view the uint32 array as raw bytes (uint8 view). 259 - We create a memoryview of the byte slice for the specified band. 260 - We compute a 128-bit hash directly on the slice. 261 262 Args: 263 signature: 1D numpy array of uint32 representing MinHash signature. 264 band_size: Number of hashes per LSH band. 265 band_idx: Index of the band to hash (0-based). 266 267 Returns: 268 An integer representing the 128-bit hash digest of the band. 269 270 Raises: 271 AssertionError: If signature shape/dtype or band index is invalid. 272 """ 273 assert signature.dtype == np.uint32 and signature.ndim == 1, ( 274 "signature must be a 1D numpy array of uint32" 275 ) 276 assert 0 <= band_idx < self.num_bands, ( 277 f"band_idx {band_idx} out of range [0, {self.num_bands})" 278 ) 279 assert len(signature) >= band_size * self.num_bands, ( 280 "signature length is too short for given band_size and num_bands" 281 ) 282 283 # Compute byte offsets for the selected band 284 start = band_idx * band_size * self._BYTES_PER_U32 285 stop = start + band_size * self._BYTES_PER_U32 286 287 # View signature as raw bytes without copy. memoryview avoids creating new bytes. 288 mv = self._sig_bytes_le(signature)[start:stop] # slice view 289 290 return xxhash.xxh128_intdigest(mv) 291 292 def _format_lsh_key(self, band_idx: int, digest: int) -> str: 293 """ 294 Format the LSH key with the HojiChar scheme version, band index, and digest. 295 """ 296 return f"{self._LSH_KEY_VERSION}:{band_idx}+{digest:032x}" 297 298 def apply(self, document: Document) -> Document: 299 """ 300 Decorate the document with LSH deduplication keys. 301 302 For each band, compute the digest and format as a hex string: 303 'v2:<band_idx>+<128-bit-digest-hex>'. 304 Keys are stored in document.extras['dedup_lsh']. 305 306 Args: 307 document: Document object with 'text' attribute. 308 309 Returns: 310 The same Document object with 'dedup_lsh' added in extras. 311 """ 312 digest = self._calculate_minhash_digest(document.text) 313 # Pack once in little-endian order without an intermediate NumPy array. 314 signature_bytes = memoryview(struct.pack(f"<{self.num_perm}I", *digest)) 315 band_bytes = self.band_size * self._BYTES_PER_U32 316 lsh_keys = [ 317 f"{self._LSH_KEY_VERSION}:{band_idx}+" 318 + xxhash.xxh128_hexdigest( 319 signature_bytes[band_idx * band_bytes : (band_idx + 1) * band_bytes] 320 ) 321 for band_idx in range(self.num_bands) 322 ] 323 324 document.extras["dedup_lsh"] = lsh_keys 325 return document 326 327 328class InlineDeduplicator(Filter): 329 """ 330 Simple in‑memory deduplicator. 331 332 Stores every LSH key in a local :pyclass:`set`. If any key of the incoming 333 document is already present, the document is marked as duplicate via 334 `document.is_rejected = True`. 335 336 **Limitations** 337 ------------- 338 *State is per‑process only.* Running multiple workers or machines will *not* 339 share the key set – use :class:`RedisDeduplicator` or 340 :class:`RedisBloomDeduplicator` for distributed setups. 341 """ 342 343 def __init__(self, **kwargs: Any): 344 super().__init__(**kwargs) 345 self.hash_pool: set[str] = set() 346 347 def apply(self, document: Document) -> Document: 348 """ 349 Inline deduplication based on the LSH keys in the document. 350 This filter cannot use in the distributed environment because it uses a local hash pool. 351 """ 352 lsh_keys = document.extras.get("dedup_lsh") 353 if lsh_keys is None: 354 raise ValueError( 355 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 356 ) 357 358 for lsh in lsh_keys: 359 if lsh in self.hash_pool: 360 document.is_rejected = True 361 else: 362 self.hash_pool.add(lsh) 363 return document 364 365 366class RedisDeduplicator(Filter): 367 """ 368 Distributed deduplicator using **plain Redis keys**. 369 You have to run a Redis server and pass its connection parameters. 370 """ 371 372 def __init__( 373 self, 374 *, 375 host: str = "localhost", 376 port: int = 6379, 377 db: int = 0, 378 key_prefix: str = "dedup", 379 **kwargs: Any, 380 ) -> None: 381 """ 382 Initialize the Redis deduplicator. 383 Args: 384 host (str): Redis server hostname. 385 port (int): Redis server port. 386 db (int): Redis database number. 387 key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. 388 **kwargs: Additional keyword arguments for parent Filter. 389 """ 390 if not is_loaded_dedup: 391 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 392 super().__init__(**kwargs) 393 self.rds = redis.Redis(host=host, port=port, db=db, decode_responses=False) 394 self.key_prefix = key_prefix.encode() 395 396 try: 397 self.rds.ping() 398 except redis.exceptions.RedisError as exc: 399 raise RuntimeError(f"Cannot connect to Redis server {host}:{port}/{db}") from exc 400 401 def apply(self, document: Document) -> Document: 402 lsh_keys = document.extras.get("dedup_lsh") 403 if lsh_keys is None: 404 raise ValueError("Apply GenerateDedupLSH first") 405 406 pipe = self.rds.pipeline(transaction=False) 407 for k in lsh_keys: 408 pipe.set(self.key_prefix + b":" + k.encode(), b"1", nx=True) 409 results: list[bool | None] = pipe.execute() # If instance already exists, it returns None 410 411 if any(r is None for r in results): 412 document.is_rejected = True 413 return document 414 415 416class RedisBloomDeduplicator(Filter): 417 """ 418 Distributed deduplicator backed by **RedisBloom scalable Bloom filters**. 419 You can use this filter to store-LSHs with less memory than Redis keys with the risk of false positives. 420 421 Each *band* gets its own scalable Bloom filter on the Redis side: 422 423 ```text 424 BF.RESERVE <prefix>:<band_idx> <error> <capacity> EXPANSION <n> 425 ``` 426 427 """ 428 429 def __init__( 430 self, 431 *, 432 expected_docs: int, 433 host: str = "localhost", 434 port: int = 6379, 435 db: int = 0, 436 key_prefix: str = "bloomdedup", 437 error_rate: float = 1e-7, 438 expansion: int = 2, 439 num_bands: int | None = None, 440 **kwargs: Any, 441 ): 442 """ 443 Initialize the RedisBloom deduplicator. 444 Args: 445 expected_docs (int): Expected number of documents to deduplicate. This is used to set the initial capacity of the Bloom filter. 446 host (str): Redis server hostname. 447 port (int): Redis server port. 448 db (int): Redis database number. 449 key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. 450 error_rate (float): Desired error rate for the Bloom filter. 451 expansion (int): Expansion factor for the Bloom filter. This is used to increase the capacity of the filter dynamically. 452 num_bands (int | None): Number of bands to use for LSH to calculate the capacity of BloomFilter. If None, it will be set to 32. 453 **kwargs: Additional keyword arguments for parent Filter. 454 """ 455 if not is_loaded_dedup: 456 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 457 super().__init__(**kwargs) 458 self.rds = redis.Redis(host=host, port=port, db=db) 459 self.key_prefix = key_prefix.encode() 460 461 _num_bands = num_bands if num_bands is not None else 32 462 463 try: 464 self.rds.execute_command( 465 "BF.RESERVE", 466 self.key_prefix, 467 error_rate, 468 expected_docs * _num_bands, 469 "EXPANSION", 470 expansion, 471 ) 472 except redis.ResponseError as e: 473 if "exists" not in str(e): 474 raise 475 476 def apply(self, document: Document) -> Document: 477 lsh_keys: list[str] | None = document.extras.get("dedup_lsh") 478 if lsh_keys is None: 479 raise ValueError( 480 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 481 ) 482 483 key_bytes = [k.encode() for k in lsh_keys] 484 485 # Return value of BF.MADD is [1,0,1,...] (0 = already exists, 1 = insertion successful) 486 flags: Iterable[int] = self.rds.execute_command("BF.MADD", self.key_prefix, *key_bytes) 487 if 0 in flags: 488 document.is_rejected = True 489 return document 490 491 492class InlineDuplicateAnalyzer(Filter): 493 def __init__(self, **kwargs: Any): 494 super().__init__(**kwargs) 495 self.docs: dict[int, Document] = dict() # doc_id -> Document mapping 496 self.hash_pool: dict[str, int] = dict() # LSH key -> doc_id mapping 497 498 self._current_doc_id = 0 499 500 def apply(self, document: Document) -> Document: 501 """ 502 Analyze duplicates inline based on the LSH keys in the document. 503 This filter cannot use in the distributed environment because it uses a local hash pool. 504 """ 505 lsh_keys = document.extras.get("dedup_lsh") 506 if lsh_keys is None: 507 raise ValueError( 508 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 509 ) 510 511 for lsh in lsh_keys: 512 if lsh in self.hash_pool: 513 document.is_rejected = True 514 document.extras["similar_doc"] = self.docs[self.hash_pool[lsh]].text 515 else: 516 self.hash_pool[lsh] = self._current_doc_id 517 self.docs[self._current_doc_id] = document 518 519 self._current_doc_id += 1 520 return document
84def char_level_splitter(text: str) -> list[str]: 85 """ 86 Split the text into characters. 87 This is a simple implementation that splits the text into individual characters. 88 """ 89 return list(text)
Split the text into characters. This is a simple implementation that splits the text into individual characters.
92def non_alpha_num_splitter(text: str) -> list[str]: 93 """ 94 Split the text into alphanumeric tokens. 95 This is a simple implementation that splits on non-alphanumeric characters. 96 """ 97 return [token for token in NON_ALPHA.split(text) if token]
Split the text into alphanumeric tokens. This is a simple implementation that splits on non-alphanumeric characters.
111def japanese_word_splitter(text: str) -> list[str]: 112 """ 113 Split the text into Japanese words using fugashi. 114 This will import fugashi and instantiate Tagger on first use. 115 """ 116 global _japanese_tagger 117 if _japanese_tagger is None: 118 fugashi = importlib.import_module("fugashi") 119 _japanese_tagger = fugashi.Tagger() 120 return [token.surface for token in _japanese_tagger(text)]
Split the text into Japanese words using fugashi. This will import fugashi and instantiate Tagger on first use.
123class GenerateDedupLSH(Filter): 124 """ 125 Filter that uses MinHash + Locality-Sensitive Hashing (LSH) to assign 126 deduplication keys to documents, allowing fast near-duplicate detection. 127 128 Attributes: 129 num_perm (int): Number of permutations (hash functions) for MinHash. 130 threshold (float): Similarity threshold for tuning LSH parameters. 131 tokenizer (Callable[[str], Iterable[str]]): Function to tokenize text. 132 n_grams (int): n-gram size for token grouping. 133 seed (int): Random seed for MinHash. 134 num_bands (int): Number of LSH bands, specified explicitly or computed automatically. 135 band_size (int): Number of hashes per band. 136 137 Notes 138 ----- 139 When band parameters are omitted, `_optimal_param` searches for the optimal 140 number of **bands** (`b`) and 141 **rows per band** (`r`) that minimise a weighted sum of false positives / 142 false negatives at the specified *threshold*. 143 144 HojiChar 0.18.0 introduces ``v2:`` keys using Rensa 0.5 and an optimized 145 hashing path. Hash generation was over 4x faster than HojiChar 0.17.3 146 in our 2,000-character English benchmark. Hashes differ from 147 HojiChar 0.17.x. Please rebuild your deduplication fingerprints, 148 or keep using HojiChar 0.17.x if you want to use existing LSH pool. 149 """ 150 151 _BYTES_PER_U32: Final[int] = 4 152 _LSH_KEY_VERSION: Final[str] = "v2" 153 154 def __init__( 155 self, 156 num_perm: int = 500, 157 threshold: float = 0.8, 158 tokenizer: Callable[[str], Iterable[str]] = char_level_splitter, 159 n_grams: int = 5, 160 seed: int = 42, 161 *, 162 num_bands: int | None = None, 163 band_size: int | None = None, 164 **kwargs: Any, 165 ) -> None: 166 """ 167 Initialize the deduplication filter with MinHash and LSH settings. 168 169 Args: 170 num_perm: Number of hash permutations for MinHash signature length. 171 Ignored when num_bands and band_size are both provided. 172 threshold: Similarity threshold to decide optimal LSH parameters. 173 Ignored when num_bands and band_size are both provided. 174 tokenizer: Function to split text into tokens. 175 n_grams: Number of tokens per n-gram for MinHash update. 176 seed: Seed for hash permutation consistency. 177 num_bands: Explicit number of LSH bands. Must be a positive integer 178 and provided together with band_size. 179 band_size: Explicit number of hashes per band. Must be a positive integer 180 and provided together with num_bands. When both are provided, 181 automatic selection is bypassed and the MinHash signature length 182 (self.num_perm) is set to num_bands * band_size. 183 **kwargs: Additional keyword arguments for parent Filter. 184 """ 185 super().__init__(**kwargs) 186 if not is_loaded_dedup: 187 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 188 if n_grams <= 0: 189 raise ValueError("n_grams must be positive") 190 self.num_perm = num_perm 191 self.threshold = threshold 192 self.tokenizer = tokenizer 193 self.n_grams = n_grams 194 self.seed = seed 195 196 if num_bands is None and band_size is None: 197 self.num_bands, self.band_size = _optimal_param( 198 threshold=self.threshold, 199 num_perm=self.num_perm, 200 false_negative_weight=0.5, 201 false_positive_weight=0.5, 202 ) 203 else: 204 if num_bands is None or band_size is None: 205 raise ValueError("num_bands and band_size must be provided together") 206 if num_bands <= 0 or band_size <= 0: 207 raise ValueError("num_bands and band_size must be positive") 208 self.num_bands = num_bands 209 self.band_size = band_size 210 self.num_perm = num_bands * band_size 211 212 def _calculate_minhash_digest(self, text: str) -> list[int]: 213 """Compute the raw digest shared by the array API and the LSH fast path.""" 214 if self.tokenizer is char_level_splitter: 215 n = self.n_grams 216 tokens = [text[i : i + n] for i in range(len(text) - n + 1)] 217 else: 218 tokens = [" ".join(grams) for grams in _ngrams(self.tokenizer(text), self.n_grams)] 219 minhash = RMinHash(num_perm=self.num_perm, seed=self.seed) 220 minhash.update(tokens) 221 return cast(list[int], minhash.digest()) 222 223 def calculate_minhash_signature(self, text: str) -> NDArray[np.uint32]: 224 """ 225 Compute MinHash signature of input text as an array of uint32. 226 227 Steps: 228 1. Tokenize text using the provided tokenizer. 229 2. Generate n-gram tokens. 230 3. Update MinHash with n-gram tokens. 231 232 Args: 233 text: Input document text to be hashed. 234 235 Returns: 236 A 1D numpy array of shape (num_perm,) with dtype uint32. 237 """ 238 return np.asarray(self._calculate_minhash_digest(text), dtype=np.uint32) 239 240 def _sig_bytes_le(self, sig: NDArray[np.uint32]) -> memoryview: 241 """ 242 Return the signature as *little-endian* byte view. 243 Platform‑independent way to get bytes from a numpy array. 244 """ 245 if sys.byteorder == "little": 246 # amd64 / arm64 (little) 247 return memoryview(cast(Any, sig)).cast("B") # zero-copy 248 else: 249 # big-endian CPU 250 return memoryview(cast(Any, sig.byteswap())).cast("B") # 1 copy 251 252 def signature_to_lsh_digest( 253 self, signature: NDArray[np.uint32], band_size: int, band_idx: int 254 ) -> int: 255 """ 256 Convert a slice of the MinHash signature into an LSH digest with less memory overhead. 257 258 This method is optimized for speed by avoiding copies: 259 - We view the uint32 array as raw bytes (uint8 view). 260 - We create a memoryview of the byte slice for the specified band. 261 - We compute a 128-bit hash directly on the slice. 262 263 Args: 264 signature: 1D numpy array of uint32 representing MinHash signature. 265 band_size: Number of hashes per LSH band. 266 band_idx: Index of the band to hash (0-based). 267 268 Returns: 269 An integer representing the 128-bit hash digest of the band. 270 271 Raises: 272 AssertionError: If signature shape/dtype or band index is invalid. 273 """ 274 assert signature.dtype == np.uint32 and signature.ndim == 1, ( 275 "signature must be a 1D numpy array of uint32" 276 ) 277 assert 0 <= band_idx < self.num_bands, ( 278 f"band_idx {band_idx} out of range [0, {self.num_bands})" 279 ) 280 assert len(signature) >= band_size * self.num_bands, ( 281 "signature length is too short for given band_size and num_bands" 282 ) 283 284 # Compute byte offsets for the selected band 285 start = band_idx * band_size * self._BYTES_PER_U32 286 stop = start + band_size * self._BYTES_PER_U32 287 288 # View signature as raw bytes without copy. memoryview avoids creating new bytes. 289 mv = self._sig_bytes_le(signature)[start:stop] # slice view 290 291 return xxhash.xxh128_intdigest(mv) 292 293 def _format_lsh_key(self, band_idx: int, digest: int) -> str: 294 """ 295 Format the LSH key with the HojiChar scheme version, band index, and digest. 296 """ 297 return f"{self._LSH_KEY_VERSION}:{band_idx}+{digest:032x}" 298 299 def apply(self, document: Document) -> Document: 300 """ 301 Decorate the document with LSH deduplication keys. 302 303 For each band, compute the digest and format as a hex string: 304 'v2:<band_idx>+<128-bit-digest-hex>'. 305 Keys are stored in document.extras['dedup_lsh']. 306 307 Args: 308 document: Document object with 'text' attribute. 309 310 Returns: 311 The same Document object with 'dedup_lsh' added in extras. 312 """ 313 digest = self._calculate_minhash_digest(document.text) 314 # Pack once in little-endian order without an intermediate NumPy array. 315 signature_bytes = memoryview(struct.pack(f"<{self.num_perm}I", *digest)) 316 band_bytes = self.band_size * self._BYTES_PER_U32 317 lsh_keys = [ 318 f"{self._LSH_KEY_VERSION}:{band_idx}+" 319 + xxhash.xxh128_hexdigest( 320 signature_bytes[band_idx * band_bytes : (band_idx + 1) * band_bytes] 321 ) 322 for band_idx in range(self.num_bands) 323 ] 324 325 document.extras["dedup_lsh"] = lsh_keys 326 return document
Filter that uses MinHash + Locality-Sensitive Hashing (LSH) to assign deduplication keys to documents, allowing fast near-duplicate detection.
Attributes: num_perm (int): Number of permutations (hash functions) for MinHash. threshold (float): Similarity threshold for tuning LSH parameters. tokenizer (Callable[[str], Iterable[str]]): Function to tokenize text. n_grams (int): n-gram size for token grouping. seed (int): Random seed for MinHash. num_bands (int): Number of LSH bands, specified explicitly or computed automatically. band_size (int): Number of hashes per band.
Notes
When band parameters are omitted, _optimal_param searches for the optimal
number of bands (b) and
rows per band (r) that minimise a weighted sum of false positives /
false negatives at the specified threshold.
HojiChar 0.18.0 introduces v2: keys using Rensa 0.5 and an optimized
hashing path. Hash generation was over 4x faster than HojiChar 0.17.3
in our 2,000-character English benchmark. Hashes differ from
HojiChar 0.17.x. Please rebuild your deduplication fingerprints,
or keep using HojiChar 0.17.x if you want to use existing LSH pool.
154 def __init__( 155 self, 156 num_perm: int = 500, 157 threshold: float = 0.8, 158 tokenizer: Callable[[str], Iterable[str]] = char_level_splitter, 159 n_grams: int = 5, 160 seed: int = 42, 161 *, 162 num_bands: int | None = None, 163 band_size: int | None = None, 164 **kwargs: Any, 165 ) -> None: 166 """ 167 Initialize the deduplication filter with MinHash and LSH settings. 168 169 Args: 170 num_perm: Number of hash permutations for MinHash signature length. 171 Ignored when num_bands and band_size are both provided. 172 threshold: Similarity threshold to decide optimal LSH parameters. 173 Ignored when num_bands and band_size are both provided. 174 tokenizer: Function to split text into tokens. 175 n_grams: Number of tokens per n-gram for MinHash update. 176 seed: Seed for hash permutation consistency. 177 num_bands: Explicit number of LSH bands. Must be a positive integer 178 and provided together with band_size. 179 band_size: Explicit number of hashes per band. Must be a positive integer 180 and provided together with num_bands. When both are provided, 181 automatic selection is bypassed and the MinHash signature length 182 (self.num_perm) is set to num_bands * band_size. 183 **kwargs: Additional keyword arguments for parent Filter. 184 """ 185 super().__init__(**kwargs) 186 if not is_loaded_dedup: 187 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 188 if n_grams <= 0: 189 raise ValueError("n_grams must be positive") 190 self.num_perm = num_perm 191 self.threshold = threshold 192 self.tokenizer = tokenizer 193 self.n_grams = n_grams 194 self.seed = seed 195 196 if num_bands is None and band_size is None: 197 self.num_bands, self.band_size = _optimal_param( 198 threshold=self.threshold, 199 num_perm=self.num_perm, 200 false_negative_weight=0.5, 201 false_positive_weight=0.5, 202 ) 203 else: 204 if num_bands is None or band_size is None: 205 raise ValueError("num_bands and band_size must be provided together") 206 if num_bands <= 0 or band_size <= 0: 207 raise ValueError("num_bands and band_size must be positive") 208 self.num_bands = num_bands 209 self.band_size = band_size 210 self.num_perm = num_bands * band_size
Initialize the deduplication filter with MinHash and LSH settings.
Args: num_perm: Number of hash permutations for MinHash signature length. Ignored when num_bands and band_size are both provided. threshold: Similarity threshold to decide optimal LSH parameters. Ignored when num_bands and band_size are both provided. tokenizer: Function to split text into tokens. n_grams: Number of tokens per n-gram for MinHash update. seed: Seed for hash permutation consistency. num_bands: Explicit number of LSH bands. Must be a positive integer and provided together with band_size. band_size: Explicit number of hashes per band. Must be a positive integer and provided together with num_bands. When both are provided, automatic selection is bypassed and the MinHash signature length (self.num_perm) is set to num_bands * band_size. **kwargs: Additional keyword arguments for parent Filter.
223 def calculate_minhash_signature(self, text: str) -> NDArray[np.uint32]: 224 """ 225 Compute MinHash signature of input text as an array of uint32. 226 227 Steps: 228 1. Tokenize text using the provided tokenizer. 229 2. Generate n-gram tokens. 230 3. Update MinHash with n-gram tokens. 231 232 Args: 233 text: Input document text to be hashed. 234 235 Returns: 236 A 1D numpy array of shape (num_perm,) with dtype uint32. 237 """ 238 return np.asarray(self._calculate_minhash_digest(text), dtype=np.uint32)
Compute MinHash signature of input text as an array of uint32.
Steps: 1. Tokenize text using the provided tokenizer. 2. Generate n-gram tokens. 3. Update MinHash with n-gram tokens.
Args: text: Input document text to be hashed.
Returns: A 1D numpy array of shape (num_perm,) with dtype uint32.
252 def signature_to_lsh_digest( 253 self, signature: NDArray[np.uint32], band_size: int, band_idx: int 254 ) -> int: 255 """ 256 Convert a slice of the MinHash signature into an LSH digest with less memory overhead. 257 258 This method is optimized for speed by avoiding copies: 259 - We view the uint32 array as raw bytes (uint8 view). 260 - We create a memoryview of the byte slice for the specified band. 261 - We compute a 128-bit hash directly on the slice. 262 263 Args: 264 signature: 1D numpy array of uint32 representing MinHash signature. 265 band_size: Number of hashes per LSH band. 266 band_idx: Index of the band to hash (0-based). 267 268 Returns: 269 An integer representing the 128-bit hash digest of the band. 270 271 Raises: 272 AssertionError: If signature shape/dtype or band index is invalid. 273 """ 274 assert signature.dtype == np.uint32 and signature.ndim == 1, ( 275 "signature must be a 1D numpy array of uint32" 276 ) 277 assert 0 <= band_idx < self.num_bands, ( 278 f"band_idx {band_idx} out of range [0, {self.num_bands})" 279 ) 280 assert len(signature) >= band_size * self.num_bands, ( 281 "signature length is too short for given band_size and num_bands" 282 ) 283 284 # Compute byte offsets for the selected band 285 start = band_idx * band_size * self._BYTES_PER_U32 286 stop = start + band_size * self._BYTES_PER_U32 287 288 # View signature as raw bytes without copy. memoryview avoids creating new bytes. 289 mv = self._sig_bytes_le(signature)[start:stop] # slice view 290 291 return xxhash.xxh128_intdigest(mv)
Convert a slice of the MinHash signature into an LSH digest with less memory overhead.
This method is optimized for speed by avoiding copies:
- We view the uint32 array as raw bytes (uint8 view).
- We create a memoryview of the byte slice for the specified band.
- We compute a 128-bit hash directly on the slice.
Args: signature: 1D numpy array of uint32 representing MinHash signature. band_size: Number of hashes per LSH band. band_idx: Index of the band to hash (0-based).
Returns: An integer representing the 128-bit hash digest of the band.
Raises: AssertionError: If signature shape/dtype or band index is invalid.
299 def apply(self, document: Document) -> Document: 300 """ 301 Decorate the document with LSH deduplication keys. 302 303 For each band, compute the digest and format as a hex string: 304 'v2:<band_idx>+<128-bit-digest-hex>'. 305 Keys are stored in document.extras['dedup_lsh']. 306 307 Args: 308 document: Document object with 'text' attribute. 309 310 Returns: 311 The same Document object with 'dedup_lsh' added in extras. 312 """ 313 digest = self._calculate_minhash_digest(document.text) 314 # Pack once in little-endian order without an intermediate NumPy array. 315 signature_bytes = memoryview(struct.pack(f"<{self.num_perm}I", *digest)) 316 band_bytes = self.band_size * self._BYTES_PER_U32 317 lsh_keys = [ 318 f"{self._LSH_KEY_VERSION}:{band_idx}+" 319 + xxhash.xxh128_hexdigest( 320 signature_bytes[band_idx * band_bytes : (band_idx + 1) * band_bytes] 321 ) 322 for band_idx in range(self.num_bands) 323 ] 324 325 document.extras["dedup_lsh"] = lsh_keys 326 return document
Decorate the document with LSH deduplication keys.
For each band, compute the digest and format as a hex string:
'v2:
Args: document: Document object with 'text' attribute.
Returns: The same Document object with 'dedup_lsh' added in extras.
329class InlineDeduplicator(Filter): 330 """ 331 Simple in‑memory deduplicator. 332 333 Stores every LSH key in a local :pyclass:`set`. If any key of the incoming 334 document is already present, the document is marked as duplicate via 335 `document.is_rejected = True`. 336 337 **Limitations** 338 ------------- 339 *State is per‑process only.* Running multiple workers or machines will *not* 340 share the key set – use :class:`RedisDeduplicator` or 341 :class:`RedisBloomDeduplicator` for distributed setups. 342 """ 343 344 def __init__(self, **kwargs: Any): 345 super().__init__(**kwargs) 346 self.hash_pool: set[str] = set() 347 348 def apply(self, document: Document) -> Document: 349 """ 350 Inline deduplication based on the LSH keys in the document. 351 This filter cannot use in the distributed environment because it uses a local hash pool. 352 """ 353 lsh_keys = document.extras.get("dedup_lsh") 354 if lsh_keys is None: 355 raise ValueError( 356 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 357 ) 358 359 for lsh in lsh_keys: 360 if lsh in self.hash_pool: 361 document.is_rejected = True 362 else: 363 self.hash_pool.add(lsh) 364 return document
Simple in‑memory deduplicator.
Stores every LSH key in a local :pyclass:set. If any key of the incoming
document is already present, the document is marked as duplicate via
document.is_rejected = True.
Limitations
State is per‑process only. Running multiple workers or machines will not
share the key set – use RedisDeduplicator or
RedisBloomDeduplicator for distributed setups.
344 def __init__(self, **kwargs: Any): 345 super().__init__(**kwargs) 346 self.hash_pool: set[str] = set()
Initialize the filter.
Parameters
p : float
The probability of applying the filter.
If p is 1, the filter will always be applied.
skip_rejected : bool
If True, the filter will skip documents that are already rejected.
If you want to apply the filter to all documents (e.g., postprocess), set this to False.
random_state : int | np.random.Generator | None
Seed for the random number generator.
If None, a new random number generator will be created.
If None, and use in the Compose class, the random state is shared with the Compose object.
use_batch : bool
If True, the filter will process documents in batches in the apply_stream method.
batch_size : int
The size of the batch to process documents in the apply_stream method.
kwargs : Any
Additional keyword arguments to pass to the filter.
348 def apply(self, document: Document) -> Document: 349 """ 350 Inline deduplication based on the LSH keys in the document. 351 This filter cannot use in the distributed environment because it uses a local hash pool. 352 """ 353 lsh_keys = document.extras.get("dedup_lsh") 354 if lsh_keys is None: 355 raise ValueError( 356 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 357 ) 358 359 for lsh in lsh_keys: 360 if lsh in self.hash_pool: 361 document.is_rejected = True 362 else: 363 self.hash_pool.add(lsh) 364 return document
Inline deduplication based on the LSH keys in the document. This filter cannot use in the distributed environment because it uses a local hash pool.
367class RedisDeduplicator(Filter): 368 """ 369 Distributed deduplicator using **plain Redis keys**. 370 You have to run a Redis server and pass its connection parameters. 371 """ 372 373 def __init__( 374 self, 375 *, 376 host: str = "localhost", 377 port: int = 6379, 378 db: int = 0, 379 key_prefix: str = "dedup", 380 **kwargs: Any, 381 ) -> None: 382 """ 383 Initialize the Redis deduplicator. 384 Args: 385 host (str): Redis server hostname. 386 port (int): Redis server port. 387 db (int): Redis database number. 388 key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. 389 **kwargs: Additional keyword arguments for parent Filter. 390 """ 391 if not is_loaded_dedup: 392 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 393 super().__init__(**kwargs) 394 self.rds = redis.Redis(host=host, port=port, db=db, decode_responses=False) 395 self.key_prefix = key_prefix.encode() 396 397 try: 398 self.rds.ping() 399 except redis.exceptions.RedisError as exc: 400 raise RuntimeError(f"Cannot connect to Redis server {host}:{port}/{db}") from exc 401 402 def apply(self, document: Document) -> Document: 403 lsh_keys = document.extras.get("dedup_lsh") 404 if lsh_keys is None: 405 raise ValueError("Apply GenerateDedupLSH first") 406 407 pipe = self.rds.pipeline(transaction=False) 408 for k in lsh_keys: 409 pipe.set(self.key_prefix + b":" + k.encode(), b"1", nx=True) 410 results: list[bool | None] = pipe.execute() # If instance already exists, it returns None 411 412 if any(r is None for r in results): 413 document.is_rejected = True 414 return document
Distributed deduplicator using plain Redis keys. You have to run a Redis server and pass its connection parameters.
373 def __init__( 374 self, 375 *, 376 host: str = "localhost", 377 port: int = 6379, 378 db: int = 0, 379 key_prefix: str = "dedup", 380 **kwargs: Any, 381 ) -> None: 382 """ 383 Initialize the Redis deduplicator. 384 Args: 385 host (str): Redis server hostname. 386 port (int): Redis server port. 387 db (int): Redis database number. 388 key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. 389 **kwargs: Additional keyword arguments for parent Filter. 390 """ 391 if not is_loaded_dedup: 392 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 393 super().__init__(**kwargs) 394 self.rds = redis.Redis(host=host, port=port, db=db, decode_responses=False) 395 self.key_prefix = key_prefix.encode() 396 397 try: 398 self.rds.ping() 399 except redis.exceptions.RedisError as exc: 400 raise RuntimeError(f"Cannot connect to Redis server {host}:{port}/{db}") from exc
Initialize the Redis deduplicator. Args: host (str): Redis server hostname. port (int): Redis server port. db (int): Redis database number. key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. **kwargs: Additional keyword arguments for parent Filter.
402 def apply(self, document: Document) -> Document: 403 lsh_keys = document.extras.get("dedup_lsh") 404 if lsh_keys is None: 405 raise ValueError("Apply GenerateDedupLSH first") 406 407 pipe = self.rds.pipeline(transaction=False) 408 for k in lsh_keys: 409 pipe.set(self.key_prefix + b":" + k.encode(), b"1", nx=True) 410 results: list[bool | None] = pipe.execute() # If instance already exists, it returns None 411 412 if any(r is None for r in results): 413 document.is_rejected = True 414 return document
Definition of filter behavior.
The document must have a protocol TextContent,
and mostly used hojichar.Document class.
In this method, the filter will modify document.text or
document.extras and set document.is_rejected = True to discard the document.
Parameters
document : Document Input document
Returns
Document Processed Document
417class RedisBloomDeduplicator(Filter): 418 """ 419 Distributed deduplicator backed by **RedisBloom scalable Bloom filters**. 420 You can use this filter to store-LSHs with less memory than Redis keys with the risk of false positives. 421 422 Each *band* gets its own scalable Bloom filter on the Redis side: 423 424 ```text 425 BF.RESERVE <prefix>:<band_idx> <error> <capacity> EXPANSION <n> 426 ``` 427 428 """ 429 430 def __init__( 431 self, 432 *, 433 expected_docs: int, 434 host: str = "localhost", 435 port: int = 6379, 436 db: int = 0, 437 key_prefix: str = "bloomdedup", 438 error_rate: float = 1e-7, 439 expansion: int = 2, 440 num_bands: int | None = None, 441 **kwargs: Any, 442 ): 443 """ 444 Initialize the RedisBloom deduplicator. 445 Args: 446 expected_docs (int): Expected number of documents to deduplicate. This is used to set the initial capacity of the Bloom filter. 447 host (str): Redis server hostname. 448 port (int): Redis server port. 449 db (int): Redis database number. 450 key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. 451 error_rate (float): Desired error rate for the Bloom filter. 452 expansion (int): Expansion factor for the Bloom filter. This is used to increase the capacity of the filter dynamically. 453 num_bands (int | None): Number of bands to use for LSH to calculate the capacity of BloomFilter. If None, it will be set to 32. 454 **kwargs: Additional keyword arguments for parent Filter. 455 """ 456 if not is_loaded_dedup: 457 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 458 super().__init__(**kwargs) 459 self.rds = redis.Redis(host=host, port=port, db=db) 460 self.key_prefix = key_prefix.encode() 461 462 _num_bands = num_bands if num_bands is not None else 32 463 464 try: 465 self.rds.execute_command( 466 "BF.RESERVE", 467 self.key_prefix, 468 error_rate, 469 expected_docs * _num_bands, 470 "EXPANSION", 471 expansion, 472 ) 473 except redis.ResponseError as e: 474 if "exists" not in str(e): 475 raise 476 477 def apply(self, document: Document) -> Document: 478 lsh_keys: list[str] | None = document.extras.get("dedup_lsh") 479 if lsh_keys is None: 480 raise ValueError( 481 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 482 ) 483 484 key_bytes = [k.encode() for k in lsh_keys] 485 486 # Return value of BF.MADD is [1,0,1,...] (0 = already exists, 1 = insertion successful) 487 flags: Iterable[int] = self.rds.execute_command("BF.MADD", self.key_prefix, *key_bytes) 488 if 0 in flags: 489 document.is_rejected = True 490 return document
Distributed deduplicator backed by RedisBloom scalable Bloom filters. You can use this filter to store-LSHs with less memory than Redis keys with the risk of false positives.
Each band gets its own scalable Bloom filter on the Redis side:
BF.RESERVE <prefix>:<band_idx> <error> <capacity> EXPANSION <n>
430 def __init__( 431 self, 432 *, 433 expected_docs: int, 434 host: str = "localhost", 435 port: int = 6379, 436 db: int = 0, 437 key_prefix: str = "bloomdedup", 438 error_rate: float = 1e-7, 439 expansion: int = 2, 440 num_bands: int | None = None, 441 **kwargs: Any, 442 ): 443 """ 444 Initialize the RedisBloom deduplicator. 445 Args: 446 expected_docs (int): Expected number of documents to deduplicate. This is used to set the initial capacity of the Bloom filter. 447 host (str): Redis server hostname. 448 port (int): Redis server port. 449 db (int): Redis database number. 450 key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. 451 error_rate (float): Desired error rate for the Bloom filter. 452 expansion (int): Expansion factor for the Bloom filter. This is used to increase the capacity of the filter dynamically. 453 num_bands (int | None): Number of bands to use for LSH to calculate the capacity of BloomFilter. If None, it will be set to 32. 454 **kwargs: Additional keyword arguments for parent Filter. 455 """ 456 if not is_loaded_dedup: 457 raise ImportError(IS_LOADED_DEDUP_ERROR_MSG) 458 super().__init__(**kwargs) 459 self.rds = redis.Redis(host=host, port=port, db=db) 460 self.key_prefix = key_prefix.encode() 461 462 _num_bands = num_bands if num_bands is not None else 32 463 464 try: 465 self.rds.execute_command( 466 "BF.RESERVE", 467 self.key_prefix, 468 error_rate, 469 expected_docs * _num_bands, 470 "EXPANSION", 471 expansion, 472 ) 473 except redis.ResponseError as e: 474 if "exists" not in str(e): 475 raise
Initialize the RedisBloom deduplicator. Args: expected_docs (int): Expected number of documents to deduplicate. This is used to set the initial capacity of the Bloom filter. host (str): Redis server hostname. port (int): Redis server port. db (int): Redis database number. key_prefix (str): Prefix for Redis keys to avoid collisions. You should use a unique prefix for each deduplication task. error_rate (float): Desired error rate for the Bloom filter. expansion (int): Expansion factor for the Bloom filter. This is used to increase the capacity of the filter dynamically. num_bands (int | None): Number of bands to use for LSH to calculate the capacity of BloomFilter. If None, it will be set to 32. **kwargs: Additional keyword arguments for parent Filter.
477 def apply(self, document: Document) -> Document: 478 lsh_keys: list[str] | None = document.extras.get("dedup_lsh") 479 if lsh_keys is None: 480 raise ValueError( 481 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 482 ) 483 484 key_bytes = [k.encode() for k in lsh_keys] 485 486 # Return value of BF.MADD is [1,0,1,...] (0 = already exists, 1 = insertion successful) 487 flags: Iterable[int] = self.rds.execute_command("BF.MADD", self.key_prefix, *key_bytes) 488 if 0 in flags: 489 document.is_rejected = True 490 return document
Definition of filter behavior.
The document must have a protocol TextContent,
and mostly used hojichar.Document class.
In this method, the filter will modify document.text or
document.extras and set document.is_rejected = True to discard the document.
Parameters
document : Document Input document
Returns
Document Processed Document
493class InlineDuplicateAnalyzer(Filter): 494 def __init__(self, **kwargs: Any): 495 super().__init__(**kwargs) 496 self.docs: dict[int, Document] = dict() # doc_id -> Document mapping 497 self.hash_pool: dict[str, int] = dict() # LSH key -> doc_id mapping 498 499 self._current_doc_id = 0 500 501 def apply(self, document: Document) -> Document: 502 """ 503 Analyze duplicates inline based on the LSH keys in the document. 504 This filter cannot use in the distributed environment because it uses a local hash pool. 505 """ 506 lsh_keys = document.extras.get("dedup_lsh") 507 if lsh_keys is None: 508 raise ValueError( 509 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 510 ) 511 512 for lsh in lsh_keys: 513 if lsh in self.hash_pool: 514 document.is_rejected = True 515 document.extras["similar_doc"] = self.docs[self.hash_pool[lsh]].text 516 else: 517 self.hash_pool[lsh] = self._current_doc_id 518 self.docs[self._current_doc_id] = document 519 520 self._current_doc_id += 1 521 return document
Base class for all filters. Document-level filters must inherit from this class.
The definition of text processing is in apply method.
If you define a new filter, override the method.
When this class is called, apply the filter from string to string.
With context manager, you can use the filter as follows:
with YourFilter(p=0.5) as filt:
text = filt("This is a sample text.")
494 def __init__(self, **kwargs: Any): 495 super().__init__(**kwargs) 496 self.docs: dict[int, Document] = dict() # doc_id -> Document mapping 497 self.hash_pool: dict[str, int] = dict() # LSH key -> doc_id mapping 498 499 self._current_doc_id = 0
Initialize the filter.
Parameters
p : float
The probability of applying the filter.
If p is 1, the filter will always be applied.
skip_rejected : bool
If True, the filter will skip documents that are already rejected.
If you want to apply the filter to all documents (e.g., postprocess), set this to False.
random_state : int | np.random.Generator | None
Seed for the random number generator.
If None, a new random number generator will be created.
If None, and use in the Compose class, the random state is shared with the Compose object.
use_batch : bool
If True, the filter will process documents in batches in the apply_stream method.
batch_size : int
The size of the batch to process documents in the apply_stream method.
kwargs : Any
Additional keyword arguments to pass to the filter.
501 def apply(self, document: Document) -> Document: 502 """ 503 Analyze duplicates inline based on the LSH keys in the document. 504 This filter cannot use in the distributed environment because it uses a local hash pool. 505 """ 506 lsh_keys = document.extras.get("dedup_lsh") 507 if lsh_keys is None: 508 raise ValueError( 509 "Document does not contain LSH keys for deduplication. Please apply GenerateDedupLSH first." 510 ) 511 512 for lsh in lsh_keys: 513 if lsh in self.hash_pool: 514 document.is_rejected = True 515 document.extras["similar_doc"] = self.docs[self.hash_pool[lsh]].text 516 else: 517 self.hash_pool[lsh] = self._current_doc_id 518 self.docs[self._current_doc_id] = document 519 520 self._current_doc_id += 1 521 return document
Analyze duplicates inline based on the LSH keys in the document. This filter cannot use in the distributed environment because it uses a local hash pool.