In 1935, linguist George Kingsley Zipf made a striking observation about the English language. He counted how often every word appeared in a large corpus of text, ranked them from most frequent to least frequent, and plotted the result. What he found was not random. It was not even close to uniform. It followed a precise mathematical law:
The most common word ("the") appears roughly twice as often as the second most common, three times as often as the third, and so on. The second word appears twice as often as the fourth. The pattern holds with eerie consistency — not just for English, but for every language ever studied, and far beyond linguistics.
The key insight: if you know a dataset follows Zipf's Law, you can predict what frequency each rank should have. Any element whose frequency deviates dramatically from that prediction is an anomaly — statistically unexpected given the structure of the rest of the data. That is the core idea behind ZipfFilter.
Most outlier detection methods ask: "is this value unusually large or small compared to all values?" That works when data is roughly symmetric. But language data, log data, web analytics, and most real-world count data are not symmetric. They are power-law distributed. A word appearing 5,000 times is not an outlier if it ranks first. A word appearing 5,000 times when it ranks 200th is deeply suspicious.
ZipfFilter filters relative to the expected frequency at each rank, not relative to a global mean or standard deviation. This makes it the right tool for any domain where Zipf's Law is a reasonable prior.
Pure Zipf's Law has one problem: it breaks down for the most frequent items. The theoretical curve predicts that rank-1 should have infinite frequency as the dataset grows, which is physically impossible. Benoit Mandelbrot (1953) fixed this with a two-parameter extension:
Three parameters, three distinct roles:
| Parameter | Role | Typical range | Effect |
|---|---|---|---|
| $k$ | Normalization constant | $> 0$, scales with corpus size | Shifts the entire curve up or down. Usually set to the frequency of the most common element. |
| $a$ | Decay exponent | $0.5$ – $2.0$ | Controls how fast frequency drops with rank. Higher $a$ → steeper drop → more concentrated on top elements. |
| $b$ | Frequency offset | $0$ – $5$ | Shifts the curve right, smoothing the top-rank behavior. Mandelbrot's fix for the singularity at $r = 0$. |
When $b = 0$ and $a = 1$, the law reduces to the original Zipf formula $f(r) = k/r$. The Zipf-Mandelbrot generalization fits real data far better, especially at the extremes of the rank distribution.
Given a real sequence, ZipfFilter fits the three parameters $(k, a, b)$ using nonlinear least squares via SciPy's curve_fit. The fitting minimizes the sum of squared residuals between observed frequencies and the model prediction:
The initial guess is $k = f_1$ (the highest observed frequency), $a = 1.0$, $b = 2.7$ — a reasonable starting point for most natural language and count data. If fitting fails (too few data points, degenerate distribution), the library falls back gracefully to the initial guess.
Once the model is fit, outlier detection is a matter of measuring how far each element's observed frequency deviates from what the model predicts for its rank.
Two modes are supported. Absolute deviation:
And the default relative deviation, which is scale-invariant and preferred for most use cases:
An element is classified as an outlier if its deviation exceeds the sensitivity threshold $\tau$:
| Operation | Complexity | Notes |
|---|---|---|
| Frequency counting | $O(n)$ | Single pass via collections.Counter |
| Sorting by rank | $O(V \log V)$ | $V$ = vocabulary size (unique elements) |
| Model fitting | $O(V \cdot I)$ | $I$ = iterations of curve_fit, typically small |
| Outlier detection | $O(V)$ | Vectorized NumPy comparison |
| Sequence filtering | $O(n)$ | Set-based $O(1)$ lookup per element |
| Total | $O(n + V \log V)$ | $V \ll n$ in practice |
The sensitivity parameter $\tau$ is the single most important knob. It controls how strict the filter is: how far an element's frequency can deviate from the Zipf-Mandelbrot model before being flagged.
| Value | Effect | Best for |
|---|---|---|
| $\tau = 0.05$ | Very strict — flags small deviations | Clean, large corpora; aggressive denoising |
| $\tau = 0.2$ (default) | Balanced — catches clear outliers only | General purpose |
| $\tau = 0.5$ | Lenient — only flags gross anomalies | Noisy data; conservative cleaning |
| $\tau > 1.0$ | Almost no filtering | Exploration / diagnostics only |
git clone https://github.com/huolter/zipffilter
pip install -r requirements.txt # numpy ≥ 1.19, scipy ≥ 1.5
from zipffilter import ZipfFilter sequence = [ "the", "of", "and", "to", "a", "the", "the", "of", "and", "the", "xyz123", "xyz123", "xyz123", "xyz123", # anomaly: too frequent for its rank "in", "is", "it", "of", ] zf = ZipfFilter(sensitivity=0.2, use_relative_deviation=True) filtered, outliers = zf.filter_outliers(sequence) print("Outliers:", outliers) # Outliers: ['xyz123'] print("Filtered sequence:", filtered) # Filtered sequence: ['the', 'of', 'and', 'to', 'a', 'the', ...]
metrics = zf.get_metrics() print(metrics) # { # 'k': 4.82, # normalization constant (≈ max frequency) # 'a': 0.93, # decay exponent (close to 1 = near-Zipf) # 'b': 2.61, # rank offset (Mandelbrot correction) # 'sensitivity': 0.2, # 'outliers': ['xyz123'], # 'num_outliers': 1 # }
# Just fit the model and get the frequency distribution freq_dict, sorted_freqs = zf.process_sequence(sequence) print(freq_dict) # Counter({'the': 4, 'of': 3, 'and': 2, 'xyz123': 4, ...}) print(sorted_freqs) # [4, 4, 3, 2, 1, 1, 1, ...] ← sorted descending by frequency
import re from zipffilter import ZipfFilter def clean_tokens(text, sensitivity=0.15): tokens = re.findall(r'\b\w+\b', text.lower()) zf = ZipfFilter(sensitivity=sensitivity) cleaned, removed = zf.filter_outliers(tokens) return cleaned, removed text = "... large document text ..." tokens, noise = clean_tokens(text) print(f"Removed {len(set(noise))} anomalous token types")
| Good fit | Poor fit |
|---|---|
| Natural language token cleaning Web server log analysis Event sequence denoising API call frequency auditing Any large count dataset with power-law structure |
Very small sequences (< 20 unique elements) Uniform or near-uniform distributions Continuous numerical data Multi-modal distributions Datasets where Zipf's Law is not a reasonable prior |
Most outlier detection treats data as if it were drawn from a Gaussian: flag points more than $k$ standard deviations from the mean. That assumption is wrong for almost all real-world count data, which is right-skewed, heavy-tailed, and power-law distributed.
ZipfFilter replaces the Gaussian assumption with the Zipf-Mandelbrot assumption — and for the right data, that change is the difference between a filter that works and a filter that removes everything that matters.
Zipf's Law is nearly 90 years old. The Zipf-Mandelbrot extension is 70 years old. What ZipfFilter adds is a practical, pip-installable Python implementation of their implications for data cleaning — making the 1935 observation from a linguistics paper into a callable function in a modern data pipeline.
← back to walter's page