Workflow:Google research Deduplicate text datasets Suffix array querying
| Knowledge Sources | |
|---|---|
| Domains | Data_Engineering, NLP, Search |
| Last Updated | 2026-02-14 21:00 GMT |
Overview
Process for building a suffix array index over a text dataset and performing fast substring occurrence queries against it using binary search.
Description
This workflow enables rapid ad-hoc analysis of text datasets by constructing a suffix array and then querying it to count how many times any given substring appears. The suffix array acts as a full-text index, enabling O(log N) lookups where N is the dataset size. This is useful for auditing datasets, checking for memorized content, verifying deduplication results, and exploring data characteristics.
Key characteristics:
- O(log N) query time regardless of dataset size (milliseconds even on 100GB+ datasets)
- Supports raw text queries or tokenized queries (GPT-2, T5, or custom tiktoken tokenizer)
- Can optionally print the byte locations of each occurrence
- Query time is dominated by Python startup, not the actual lookup
- The suffix array only needs to be built once and can be queried repeatedly
Usage
Execute this workflow when you need to quickly check how many times a specific string or passage appears in a large text dataset. Common use cases include verifying deduplication results, checking for memorized training examples, auditing datasets for specific content, and exploring data characteristics. This is the appropriate tool for small numbers of queries; for bulk comparison of large text against a dataset, use the Cross Dataset Deduplication workflow instead.
Execution Steps
Step 1: Load and serialize dataset
Load the dataset and serialize it into a single flat binary file. This can use either the TFDS loader, the HuggingFace loader, or start from a pre-existing binary file. If you plan to query with tokenized strings, the dataset should be tokenized with the same tokenizer during serialization.
Key considerations:
- If the dataset is already serialized from a prior deduplication run, this step can be skipped
- Tokenization must match between dataset serialization and query time
- The serialized file includes separator tokens per example, but these do not affect query results
Step 2: Build suffix array
Construct a suffix array for the serialized binary file. This uses the same parallel chunked construction process as the deduplication workflows. The suffix array only needs to be built once and can be reused for unlimited queries.
Key considerations:
- Building the suffix array is the expensive one-time cost; all subsequent queries are nearly instant
- For very large datasets, ensure sufficient disk space (the suffix array is typically 4-8x the dataset size)
- If a suffix array already exists from a prior deduplication run, this step can be skipped entirely
Step 3: Query for substring occurrences
Use binary search on the suffix array to count how many times a given query string appears in the dataset. The query can be provided as a command-line string or loaded from a file. Optional tokenization encodes the query to match a tokenized dataset.
Key considerations:
- Query time is O(log N * query_length), which is milliseconds even for 100GB+ datasets
- If the dataset was tokenized during serialization, pass the same tokenizer flag when querying
- The print-location flag additionally returns the byte offsets of each occurrence
- The load-disk flag streams the suffix array from disk instead of loading it into memory, useful for very large arrays
- Multiple queries can be run against the same suffix array without rebuilding