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.

  1. Tokenize
    • Split text into tokens. (Default: character‑level, but you can plug in any callable.)
  2. n-grams
    • Group tokens into n‑grams (n_grams=5) to capture context.
  3. MinHash
    • 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.
    • This module uses rensa.RMinHash which is a fast MinHash implementation by Rust language.
  4. Banding and compression
    • Split the signature into b bands, each containing r integers (num_perm ≈ b×r).
    • Treat the r integers as raw bytes, hash them with xxhash‑128, and format as v2:+.
  5. Output
    • Store all band keys in document.extras['dedup_lsh'] as a list of strings.

InlineDeduplicator, RedisDeduplicator, and RedisBloomDeduplicator filters use the generated LSH keys to mark documents as duplicates.

  • InlineDeduplicator stores LSH keys in a local set, so it works only in a single process.
  • RedisDeduplicator stores LSH keys in Redis, so it works in a distributed environment.
  • RedisBloomDeduplicator stores 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
def char_level_splitter(text: str) -> list[str]:
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.

def non_alpha_num_splitter(text: str) -> list[str]:
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.

def japanese_word_splitter(text: str) -> list[str]:
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.

class GenerateDedupLSH(hojichar.core.filter_interface.Filter):
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.

GenerateDedupLSH( num_perm: int = 500, threshold: float = 0.8, tokenizer: collections.abc.Callable[[str], collections.abc.Iterable[str]] = <function char_level_splitter>, n_grams: int = 5, seed: int = 42, *, num_bands: int | None = None, band_size: int | None = None, **kwargs: Any)
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.

def calculate_minhash_signature( self, text: str) -> numpy.ndarray[tuple[typing.Any, ...], numpy.dtype[numpy.uint32]]:
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.

def signature_to_lsh_digest( self, signature: numpy.ndarray[tuple[typing.Any, ...], numpy.dtype[numpy.uint32]], band_size: int, band_idx: int) -> int:
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.

def apply( self, document: hojichar.core.models.Document) -> hojichar.core.models.Document:
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:+<128-bit-digest-hex>'. Keys are stored in document.extras['dedup_lsh'].

Args: document: Document object with 'text' attribute.

Returns: The same Document object with 'dedup_lsh' added in extras.

class InlineDeduplicator(hojichar.core.filter_interface.Filter):
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.

InlineDeduplicator(**kwargs: Any)
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.

def apply( self, document: hojichar.core.models.Document) -> hojichar.core.models.Document:
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.

class RedisDeduplicator(hojichar.core.filter_interface.Filter):
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.

RedisDeduplicator( *, host: str = 'localhost', port: int = 6379, db: int = 0, key_prefix: str = 'dedup', **kwargs: Any)
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.

def apply( self, document: hojichar.core.models.Document) -> hojichar.core.models.Document:
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

class RedisBloomDeduplicator(hojichar.core.filter_interface.Filter):
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>
RedisBloomDeduplicator( *, expected_docs: int, host: str = 'localhost', port: int = 6379, db: int = 0, key_prefix: str = 'bloomdedup', error_rate: float = 1e-07, expansion: int = 2, num_bands: int | None = None, **kwargs: Any)
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.

def apply( self, document: hojichar.core.models.Document) -> hojichar.core.models.Document:
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

class InlineDuplicateAnalyzer(hojichar.core.filter_interface.Filter):
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.")
InlineDuplicateAnalyzer(**kwargs: Any)
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.

def apply( self, document: hojichar.core.models.Document) -> hojichar.core.models.Document:
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.