Comprehensive Plan for Literature-Standard Benchmarking and Validation
Date: 2025-11-06 Status: Planning Phase - Implementation Pending Priority: High (Priority 1 from Evaluation Methodology)
Integrate Peter Norvig's big.txt corpus and the Birkbeck spelling error corpus to enable:
Storage Strategy:
Integration Points:
tests/corpus_validation.rsbenches/corpus_benchmarks.rssrc/corpus/ (test-only visibility)corpus-validation for isolated testing✅ Correctness: >95% recall on Birkbeck corpus (36K real errors) ✅ Performance: Reproducible benchmarks on big.txt (32K words) ✅ Automation: CI runs corpus tests without manual intervention ✅ Documentation: Clear setup instructions and usage guide
Purpose: Realistic English dictionary for performance testing and language modeling
Source & Composition:
Statistics:
Download: https://norvig.com/big.txt
Academic Usage:
Word Frequency Distribution:
Rank 1 (the): ~79,809 occurrences (7%)
Rank 10 (be): ~9,843 occurrences
Rank 100 (way): ~1,304 occurrences
Rank 1000 (floor): ~122 occurrences
Rank 10000 (drank): ~8 occurrences
Follows Zipf's Law: frequency ∝ 1/rank
Purpose: Correctness validation with authentic spelling errors from native speakers
Source & Composition:
Statistics:
File Format:
$correct_word
misspelling1
misspelling2
misspelling3
$next_correct_word
error1
error2
$Download: https://titan.dcs.bbk.ac.uk/~roger/corpora.html (Alternate: https://ota.bodleian.ox.ac.uk/repository/xmlui/handle/20.500.12024/0643)
Academic Usage:
Example Entries:
$abandon
abadon
abanddon
abandonn
abbandone
abondon
$absolutely
absolutly
absolutley
absalutly
absolootly
Holbrook Corpus:
Aspell Corpus:
Wikipedia Corpus:
/tests/) - 42 FilesExisting Patterns:
proptest (v1.4)Current Test Data Sources:
format!("word{:06}", i)Key Files:
integration_tests.rs - End-to-end integrationproptest_automaton_distance_cross_validation.rs - Cross-validation with naive algorithmutf8_tests.rs - Unicode handlingconcurrency_test.rs - Thread safetyGap: No literature-standard validation dataset
/benches/) - 43+ FilesExisting Patterns:
Current Data Sources:
/usr/share/dict/words (varies by OS, non-reproducible)word000001, word000002, ...Key Files:
backend_comparison.rs - 6 backend comparisoncomprehensive_profiling.rs - End-to-end scenariosreal_world_profiling.rs - 30-second stress testbatch1-4_simd_benchmarks.rs - SIMD validationGap: No standardized, reproducible corpus for cross-project comparison
/data/)Current Contents:
english_words.txt - 123,985 lines, ~1.17 MBreal_world_benchmark.rs, dawg_query_comparison.rs, ordered_query_benchmark.rsCharacteristics:
Planned Structure:
data/
├── english_words.txt # Existing
├── corpora/ # NEW
│ ├── README.md # Documentation
│ ├── big.txt # Downloaded (not committed)
│ └── birkbeck.txt # Downloaded (not committed)
└── generated/ # NEW (test data, not committed)
├── typos_distance_1.txt # Generated from big.txt
├── typos_distance_2.txt
└── query_workload.txt # Benchmark queries
.github/workflows/ci.yml)Current Jobs:
test - Unit and integration tests (Linux/macOS, stable/nightly)lint - Clippy and rustfmtbenchmarks - Performance benchmarks on mastertest-report - Aggregate test resultsCurrent Caching:
Planned Addition:
corpus-validation job (new, isolated)Gap: No corpus download/caching infrastructure
Cargo.toml)Current:
[dev-dependencies]
criterion = "0.5" # Statistical benchmarking
tempfile = "3.8" # Temporary file handling
proptest = "1.4" # Property-based testing
rayon = "1.11" # Parallel iteration
num_cpus = "1.16" # CPU detection
Needs: No new dependencies required! ✅
curl via shell scriptrand (already in main dependencies)Decision: Download On-Demand, Do Not Commit
Rationale:
Implementation:
.gitignore: data/corpora/*.txt, data/generated/*.txtscripts/download_corpora.shAlternatives Considered:
Decision: Opt-In Tests with #[ignore] Attribute
Rationale:
cargo test -- --ignored when neededImplementation:
#[test]
#[ignore] // Run explicitly with: cargo test -- --ignored
fn test_birkbeck_recall() {
// Test implementation
}
Alternatives Considered:
#[ignore] attribute: Standard Rust pattern, explicit opt-inDecision: Test-Only Module (#[cfg(test)])
Rationale:
Implementation:
// src/lib.rs
#[cfg(test)]
pub mod corpus;
Alternatives Considered:
#[cfg(test)] module: Standard Rust patternDecision: Deterministic Generation with Seeded RNG
Rationale:
Implementation:
use rand::{SeedableRng, rngs::StdRng};
let mut rng = StdRng::seed_from_u64(42); // Fixed seed
let typo = generate_typo(&word, &mut rng);
Alternatives Considered:
.gitignore (Update)Purpose: Exclude downloaded corpora and generated test data
Changes:
# Corpus data (download on demand)
data/corpora/*.txt
data/generated/*.txt
# Keep documentation
!data/corpora/README.md
!data/generated/README.md
Rationale: Prevents accidental commits of large corpus files
data/corpora/README.md (NEW, ~100 lines)Purpose: Document corpus sources, attribution, and usage
Contents:
download_corpora.shTemplate:
# Corpus Data for Testing and Benchmarking
## Quick Start
Download corpora:
```bash
./scripts/download_corpora.sh
cargo test --test corpus_validation -- --ignored
cargo bench --bench corpus_benchmarks
When publishing results using these corpora:
---
#### File 3: `scripts/download_corpora.sh` (NEW, ~150 lines)
**Purpose:** Automated corpus download with verification
**Features:**
1. **Idempotent:** Skip if already downloaded (unless `--force`)
2. **Checksum Verification:** SHA256 hashes for integrity
3. **Error Handling:** Retry logic, clear error messages
4. **Progress Reporting:** User-friendly output
**Pseudocode:**
```bash
#!/bin/bash
set -euo pipefail
CORPORA_DIR="data/corpora"
mkdir -p "$CORPORA_DIR"
# SHA256 checksums (computed from known-good downloads)
BIG_TXT_SHA256="..."
BIRKBECK_SHA256="..."
download_big_txt() {
if [ ! -f "$CORPORA_DIR/big.txt" ] || [ "$1" == "--force" ]; then
echo "Downloading big.txt from norvig.com..."
curl -f -o "$CORPORA_DIR/big.txt" https://norvig.com/big.txt
verify_checksum "$CORPORA_DIR/big.txt" "$BIG_TXT_SHA256"
echo "✓ big.txt downloaded and verified"
else
echo "✓ big.txt already exists (use --force to re-download)"
fi
}
download_birkbeck() {
if [ ! -f "$CORPORA_DIR/birkbeck.txt" ] || [ "$1" == "--force" ]; then
echo "Downloading Birkbeck corpus..."
# Download from Oxford Text Archive
curl -L -o "$CORPORA_DIR/birkbeck.zip" \
"https://ota.bodleian.ox.ac.uk/repository/xmlui/bitstream/handle/20.500.12024/0643/missp.dat"
# Extract
unzip -o "$CORPORA_DIR/birkbeck.zip" -d "$CORPORA_DIR/"
mv "$CORPORA_DIR/missp.dat" "$CORPORA_DIR/birkbeck.txt"
rm "$CORPORA_DIR/birkbeck.zip"
verify_checksum "$CORPORA_DIR/birkbeck.txt" "$BIRKBECK_SHA256"
echo "✓ Birkbeck corpus downloaded and verified"
else
echo "✓ Birkbeck corpus already exists"
fi
}
verify_checksum() {
local file=$1
local expected=$2
local actual=$(sha256sum "$file" | awk '{print $1}')
if [ "$actual" != "$expected" ]; then
echo "ERROR: Checksum mismatch for $file"
echo " Expected: $expected"
echo " Actual: $actual"
exit 1
fi
}
main() {
local force_flag=${1:-""}
download_big_txt "$force_flag"
download_birkbeck "$force_flag"
echo ""
echo "All corpora downloaded successfully!"
echo "Run 'cargo test --test corpus_validation -- --ignored' to validate"
}
main "$@"
Error Handling:
set -euo pipefail: Exit on any error.github/workflows/ci.yml (Update)Purpose: Integrate corpus tests into CI pipeline
Changes:
Step 1: Add Corpus Cache (after existing cache steps)
- name: Cache corpora
id: cache-corpora
uses: actions/cache@v4
with:
path: data/corpora
key: corpora-v1-${{ hashFiles('scripts/download_corpora.sh') }}
restore-keys: |
corpora-v1-
Rationale: Cache key includes script hash, invalidates when download logic changes
Step 2: Download Corpora
- name: Download corpora
if: steps.cache-corpora.outputs.cache-hit != 'true'
run: |
chmod +x scripts/download_corpora.sh
./scripts/download_corpora.sh
Rationale: Only download if cache miss (first run or script change)
Step 3: New Job - Corpus Validation
corpus-validation:
name: Corpus Validation Tests
runs-on: ubuntu-latest
env:
RUSTFLAGS: "-C target-cpu=native"
steps:
- name: Checkout repository
uses: actions/checkout@v4
- name: Install Rust toolchain
uses: actions-rust-lang/setup-rust-toolchain@v1
with:
toolchain: stable
- name: Cache corpora
id: cache-corpora
uses: actions/cache@v4
with:
path: data/corpora
key: corpora-v1-${{ hashFiles('scripts/download_corpora.sh') }}
restore-keys: corpora-v1-
- name: Download corpora
if: steps.cache-corpora.outputs.cache-hit != 'true'
run: |
chmod +x scripts/download_corpora.sh
./scripts/download_corpora.sh
- name: Run corpus validation tests
run: |
echo "::group::Birkbeck Recall Test"
cargo test --test corpus_validation test_birkbeck_recall -- --ignored --nocapture
echo "::endgroup::"
echo "::group::Algorithm Consistency Test"
cargo test --test corpus_validation test_algorithm_consistency -- --ignored --nocapture
echo "::endgroup::"
echo "::group::Distance Accuracy Test"
cargo test --test corpus_validation test_distance_accuracy -- --ignored --nocapture
echo "::endgroup::"
- name: Upload validation results
if: always()
uses: actions/upload-artifact@v4
with:
name: corpus-validation-results
path: |
test-results/
*.log
retention-days: 7
Step 4: Update Aggregate Job
test-report:
name: Test Report Summary
runs-on: ubuntu-latest
needs: [test, lint, benchmarks, corpus-validation] # Add corpus-validation
if: always()
src/corpus/mod.rs (NEW, ~30 lines)Purpose: Module structure for corpus utilities
Contents:
//! Corpus utilities for testing and benchmarking
//!
//! This module provides parsers and generators for working with
//! literature-standard corpora:
//!
//! - **Peter Norvig's big.txt**: Natural language word frequencies
//! - **Birkbeck corpus**: Real-world spelling errors
//!
//! # Examples
//!
//! ```rust,ignore
//! use liblevenshtein::corpus::parser::BigTxtCorpus;
//!
//! let corpus = BigTxtCorpus::load("data/corpora/big.txt")?;
//! let top_words = corpus.most_frequent(1000);
//! ```
pub mod parser;
pub mod generator;
pub mod stats;
pub use parser::{BirkbeckCorpus, BigTxtCorpus};
pub use generator::{TypoGenerator, QueryWorkload};
pub use stats::CorpusStats;
Design:
src/corpus/parser.rs (NEW, ~250 lines)Purpose: Parse Birkbeck and big.txt corpora
Structure:
Type 1: BirkbeckCorpus
pub struct BirkbeckCorpus {
/// Map: correct_word -> vec![misspelling1, ...]
pub errors: HashMap<String, Vec<String>>,
}
impl BirkbeckCorpus {
/// Load from file path
pub fn load<P: AsRef<Path>>(path: P) -> io::Result<Self>;
/// Total number of misspellings
pub fn total_errors(&self) -> usize;
/// Number of unique correct words
pub fn unique_words(&self) -> usize;
/// Get errors for specific word
pub fn errors_for(&self, word: &str) -> Option<&Vec<String>>;
/// Sample random error pairs (for testing)
pub fn sample(&self, count: usize, seed: u64) -> Vec<(String, String)>;
}
Parsing Logic:
Read line-by-line:
If starts with '$': Set current_word = line[1..]
Else: Add line to errors[current_word]
Type 2: BigTxtCorpus
pub struct BigTxtCorpus {
/// Word -> frequency count
pub frequencies: HashMap<String, usize>,
/// Total word count
pub total_words: usize,
}
impl BigTxtCorpus {
/// Load and tokenize big.txt
pub fn load<P: AsRef<Path>>(path: P) -> io::Result<Self>;
/// Number of unique words
pub fn unique_words(&self) -> usize;
/// Top N most frequent words
pub fn most_frequent(&self, n: usize) -> Vec<(&String, &usize)>;
/// Probability of word: P(word) = count / total
pub fn probability(&self, word: &str) -> f64;
/// Sample word by frequency (Zipfian distribution)
pub fn sample_by_frequency(&self, rng: &mut impl Rng) -> String;
}
Tokenization:
Read entire file to string
Split on whitespace
For each token:
- Convert to lowercase
- Strip non-alphabetic characters
- Count frequency
Tests:
#[cfg(test)]
mod tests {
#[test]
#[ignore]
fn test_load_birkbeck() {
let corpus = BirkbeckCorpus::load("data/corpora/birkbeck.txt").unwrap();
assert!(corpus.unique_words() > 6000);
assert!(corpus.total_errors() > 35000);
}
#[test]
#[ignore]
fn test_load_big_txt() {
let corpus = BigTxtCorpus::load("data/corpora/big.txt").unwrap();
assert!(corpus.unique_words() > 30000);
// "the" should be most frequent
let top = corpus.most_frequent(1);
assert_eq!(top[0].0, "the");
}
}
src/corpus/generator.rs (NEW, ~200 lines)Purpose: Generate realistic typos and query workloads
Type 1: TypoGenerator
pub struct TypoGenerator {
rng: StdRng, // Seeded for reproducibility
}
impl TypoGenerator {
/// Create with fixed seed
pub fn new(seed: u64) -> Self;
/// Generate all possible edits at distance 1
/// (Norvig's algorithm)
pub fn edits_distance_1(&self, word: &str) -> HashSet<String>;
/// Generate random typo at specified distance
pub fn random_typo(&mut self, word: &str, distance: usize) -> String;
/// Apply single random edit (internal)
fn apply_random_edit(&mut self, word: &str) -> String;
}
Edit Operations:
Deletions: "test" -> "tst", "est", "tet", "tes"
Transpositions: "test" -> "tset", "tets"
Replacements: "test" -> "aest", "best", ... "zest", "tast", ...
Insertions: "test" -> "atest", "taest", "tesat", "testa", ...
Type 2: QueryWorkload
pub struct QueryWorkload {
pub queries: Vec<Query>,
}
pub struct Query {
pub word: String, // Typo
pub max_distance: usize, // Search distance
pub expected_result: Option<String>, // Correct word
}
impl QueryWorkload {
/// Generate workload from corpus
pub fn generate_from_corpus(
corpus_words: &[String],
corpus_frequencies: &HashMap<String, usize>,
count: usize,
seed: u64,
) -> Self;
/// Sample word by frequency (Zipfian)
fn sample_by_frequency(...) -> String;
/// Save to file
pub fn save<P: AsRef<Path>>(&self, path: P) -> io::Result<()>;
/// Load from file
pub fn load<P: AsRef<Path>>(path: P) -> io::Result<Self>;
}
Stratified Sampling:
40% high-frequency (rank 1-1000): Most common queries
40% medium-frequency (rank 1000-10000): Moderate vocabulary
20% low-frequency (rank 10000+): Rare words
Tests:
#[test]
fn test_edits_distance_1() {
let gen = TypoGenerator::new(42);
let edits = gen.edits_distance_1("test");
assert!(edits.contains("est")); // deletion
assert!(edits.contains("tset")); // transposition
assert!(edits.contains("best")); // replacement
assert!(edits.contains("atest")); // insertion
// Should generate ~54n + 25 edits for n-letter word
assert!(edits.len() > 200);
}
#[test]
fn test_deterministic_generation() {
let mut gen1 = TypoGenerator::new(42);
let mut gen2 = TypoGenerator::new(42);
assert_eq!(gen1.random_typo("test", 2), gen2.random_typo("test", 2));
}
src/lib.rs (Update, 1 line)Purpose: Expose corpus module for tests/benchmarks only
Change:
// At top level, after other modules
#[cfg(test)]
pub mod corpus;
Rationale:
#[cfg(test)]: Only compiled for test/bench buildspub: Accessible from tests/ and benches/ directoriestests/corpus_validation.rs (NEW, ~400 lines)Purpose: Validate correctness against literature-standard errors
Test 1: Birkbeck Recall Test
Goal: Verify >95% recall on real spelling errors
Methodology:
For each (correct_word, misspelling) pair in Birkbeck:
1. Calculate actual Levenshtein distance
2. Query automaton with max_distance = min(actual_distance, 3)
3. Check if correct_word in results
4. Accumulate recall statistics
Pseudocode:
#[test]
#[ignore]
fn test_birkbeck_recall() {
let corpus = BirkbeckCorpus::load("data/corpora/birkbeck.txt")?;
let dict = build_dictionary(corpus.errors.keys());
let transducer = Transducer::new(dict, Algorithm::Standard);
let mut stats = RecallStats::new();
for (correct, misspellings) in &corpus.errors {
for misspelling in misspellings {
let actual_distance = naive_levenshtein(misspelling, correct);
let max_distance = actual_distance.min(3);
let results: Vec<_> = transducer.query(misspelling, max_distance).collect();
let found = results.contains(correct);
stats.record(actual_distance, found);
}
}
// Print detailed breakdown
println!("\n=== Birkbeck Recall Results ===");
println!("Total: {} / {} ({:.2}%)",
stats.found, stats.total, stats.recall() * 100.0);
for d in 1..=10 {
if let Some(rate) = stats.recall_at_distance(d) {
println!(" d={}: {:.2}%", d, rate * 100.0);
}
}
// Assert minimum threshold
assert!(stats.recall() >= 0.95,
"Recall {:.2}% below 95% threshold", stats.recall() * 100.0);
}
struct RecallStats {
total: usize,
found: usize,
by_distance: HashMap<usize, (usize, usize)>, // (total, found)
}
Expected Output:
=== Birkbeck Recall Results ===
Total: 34,527 / 36,133 (95.56%)
d=1: 98.21%
d=2: 96.45%
d=3: 92.33%
d=4: 84.12%
d=5: 71.56%
Failure Modes:
Test 2: Algorithm Consistency Test
Goal: Verify all algorithm variants produce consistent results
Methodology:
For sample of 1000 error pairs:
Run Standard, Transposition, MergeAndSplit algorithms
Verify all find (or all miss) the correct word
(Different algorithms may find different additional matches,
but should agree on the target word)
Pseudocode:
#[test]
#[ignore]
fn test_algorithm_consistency() {
let corpus = BirkbeckCorpus::load("data/corpora/birkbeck.txt")?;
let sample = corpus.sample(1000, 42); // Seeded sampling
let dict = build_dictionary(corpus.errors.keys());
let algorithms = [Algorithm::Standard, Algorithm::Transposition, Algorithm::MergeAndSplit];
let mut inconsistencies = 0;
for (correct, misspelling) in sample {
let mut found_by_algo = Vec::new();
for algo in &algorithms {
let transducer = Transducer::new(dict.clone(), *algo);
let results = transducer.query(&misspelling, 2).collect::<Vec<_>>();
let found = results.contains(&correct);
found_by_algo.push(found);
}
// Check consistency (all found or all not found)
let all_found = found_by_algo.iter().all(|&f| f);
let none_found = found_by_algo.iter().all(|&f| !f);
if !all_found && !none_found {
eprintln!("INCONSISTENCY: '{}' -> '{}'", misspelling, correct);
eprintln!(" Standard: {}, Transposition: {}, MergeAndSplit: {}",
found_by_algo[0], found_by_algo[1], found_by_algo[2]);
inconsistencies += 1;
}
}
assert_eq!(inconsistencies, 0,
"{} inconsistencies found across algorithms", inconsistencies);
}
Expected: 0 inconsistencies (all algorithms agree)
Rationale: While different algorithms may find different nearby words (e.g., Transposition finds more transposition errors), they should agree on whether the correct word is within distance n.
Test 3: Distance Accuracy Test
Goal: Verify reported distances match ground truth
Methodology:
For sample of error pairs:
Calculate naive Levenshtein distance (ground truth)
Query automaton with query_with_distance()
Verify reported distance == ground truth
Pseudocode:
#[test]
#[ignore]
fn test_distance_accuracy() {
let corpus = BirkbeckCorpus::load("data/corpora/birkbeck.txt")?;
let sample = corpus.sample(500, 42);
let dict = build_dictionary(corpus.errors.keys());
let transducer = Transducer::new(dict, Algorithm::Standard);
let mut mismatches = 0;
for (correct, misspelling) in sample {
let actual = naive_levenshtein(&misspelling, &correct);
if actual <= 3 {
let results = transducer
.query_with_distance(&misspelling, actual)
.collect::<Vec<_>>();
if let Some(candidate) = results.iter().find(|c| c.term == correct) {
if candidate.distance != actual {
eprintln!("MISMATCH: '{}' -> '{}' (expected {}, got {})",
misspelling, correct, actual, candidate.distance);
mismatches += 1;
}
}
}
}
assert_eq!(mismatches, 0, "{} distance mismatches", mismatches);
}
/// Naive Levenshtein for ground truth
fn naive_levenshtein(s1: &str, s2: &str) -> usize {
let len1 = s1.chars().count();
let len2 = s2.chars().count();
// Wagner-Fischer DP algorithm
let mut dp = vec![vec![0; len2 + 1]; len1 + 1];
for i in 0..=len1 { dp[i][0] = i; }
for j in 0..=len2 { dp[0][j] = j; }
let s1_chars: Vec<char> = s1.chars().collect();
let s2_chars: Vec<char> = s2.chars().collect();
for i in 1..=len1 {
for j in 1..=len2 {
let cost = if s1_chars[i-1] == s2_chars[j-1] { 0 } else { 1 };
dp[i][j] = min3(
dp[i-1][j] + 1, // deletion
dp[i][j-1] + 1, // insertion
dp[i-1][j-1] + cost, // substitution
);
}
}
dp[len1][len2]
}
benches/corpus_benchmarks.rs (NEW, ~500 lines)Purpose: Reproducible performance benchmarks on standard corpus
Benchmark 1: Dictionary Construction
Goal: Measure construction time and memory for 32K words
Implementation:
fn bench_construction(c: &mut Criterion) {
let corpus = BigTxtCorpus::load("data/corpora/big.txt").unwrap();
let words: Vec<String> = corpus.frequencies.keys().cloned().collect();
let mut group = c.benchmark_group("construction_big_txt");
group.throughput(Throughput::Elements(words.len() as u64));
// DoubleArrayTrie
group.bench_function("DoubleArrayTrie", |b| {
b.iter(|| {
let dict = DoubleArrayTrie::from_terms(words.clone());
black_box(dict)
})
});
// DAWG
group.bench_function("DawgDictionary", |b| {
b.iter(|| {
let dict = DawgDictionary::from_iter(words.iter().map(|s| s.as_str()));
black_box(dict)
})
});
// DynamicDawg
group.bench_function("DynamicDawg", |b| {
b.iter(|| {
let dict = DynamicDawg::from_terms(words.clone());
black_box(dict)
})
});
// PathMap
#[cfg(feature = "pathmap-backend")]
group.bench_function("PathMapDictionary", |b| {
b.iter(|| {
let dict = PathMapDictionary::from_terms(words.clone());
black_box(dict)
})
});
group.finish();
}
Expected Results:
construction_big_txt/DoubleArrayTrie time: [3.2 ms 3.3 ms 3.4 ms]
thrpt: [9.6 K elem/s 9.8 K elem/s 10.0 K elem/s]
construction_big_txt/DawgDictionary time: [6.0 ms 6.2 ms 6.4 ms]
construction_big_txt/DynamicDawg time: [3.9 ms 4.0 ms 4.1 ms]
construction_big_txt/PathMapDictionary time: [3.0 ms 3.1 ms 3.2 ms]
Benchmark 2: Realistic Query Workload
Goal: Measure query performance with frequency-weighted queries
Implementation:
fn bench_query_realistic_workload(c: &mut Criterion) {
let corpus = BigTxtCorpus::load("data/corpora/big.txt").unwrap();
let words: Vec<String> = corpus.frequencies.keys().cloned().collect();
// Generate 1000 queries with realistic typos
let workload = QueryWorkload::generate_from_corpus(
&words,
&corpus.frequencies,
1000,
42, // Fixed seed for reproducibility
);
let dict = DoubleArrayTrie::from_terms(words);
let transducer = Transducer::new(dict, Algorithm::Standard);
let mut group = c.benchmark_group("query_realistic_workload");
group.throughput(Throughput::Elements(workload.queries.len() as u64));
for distance in [1, 2, 3] {
let queries_at_d: Vec<_> = workload.queries.iter()
.filter(|q| q.max_distance == distance)
.collect();
group.bench_with_input(
BenchmarkId::new("distance", distance),
&queries_at_d,
|b, queries| {
b.iter(|| {
for query in queries.iter() {
let results: Vec<_> = transducer
.query(&query.word, black_box(distance))
.collect();
black_box(results);
}
})
},
);
}
group.finish();
}
Expected Results:
query_realistic_workload/distance/1 time: [8.2 µs 8.4 µs 8.6 µs]
thrpt: [119 K queries/s 122 K queries/s 125 K queries/s]
query_realistic_workload/distance/2 time: [12.9 µs 13.1 µs 13.3 µs]
thrpt: [75 K queries/s 76 K queries/s 78 K queries/s]
query_realistic_workload/distance/3 time: [18.5 µs 18.8 µs 19.1 µs]
thrpt: [52 K queries/s 53 K queries/s 54 K queries/s]
Benchmark 3: Frequency-Stratified Queries
Goal: Compare performance for high vs medium frequency words
Implementation:
fn bench_frequency_stratified_queries(c: &mut Criterion) {
let corpus = BigTxtCorpus::load("data/corpora/big.txt").unwrap();
let words: Vec<String> = corpus.frequencies.keys().cloned().collect();
// High-frequency: top 1000
let high_freq: Vec<String> = corpus.most_frequent(1000)
.into_iter()
.map(|(w, _)| w.clone())
.collect();
// Medium-frequency: rank 1000-5000
let mut sorted: Vec<_> = corpus.frequencies.iter().collect();
sorted.sort_by(|a, b| b.1.cmp(a.1));
let medium_freq: Vec<String> = sorted[1000..5000]
.iter()
.map(|(w, _)| (*w).clone())
.collect();
let dict = DoubleArrayTrie::from_terms(words);
let transducer = Transducer::new(dict, Algorithm::Standard);
let mut group = c.benchmark_group("query_by_frequency");
group.bench_function("high_frequency", |b| {
b.iter(|| {
for word in high_freq.iter().take(100) {
let results: Vec<_> = transducer.query(word, 2).collect();
black_box(results);
}
})
});
group.bench_function("medium_frequency", |b| {
b.iter(|| {
for word in medium_freq.iter().take(100) {
let results: Vec<_> = transducer.query(word, 2).collect();
black_box(results);
}
})
});
group.finish();
}
Expected Insight:
Benchmark 4: Algorithm Comparison
Goal: Measure overhead of extended algorithms on standard corpus
Implementation:
fn bench_algorithm_comparison(c: &mut Criterion) {
let corpus = BigTxtCorpus::load("data/corpora/big.txt").unwrap();
let words: Vec<String> = corpus.frequencies.keys().cloned().collect();
let dict = DoubleArrayTrie::from_terms(words);
let workload = QueryWorkload::generate_from_corpus(
&corpus.frequencies.keys().cloned().collect::<Vec<_>>(),
&corpus.frequencies,
100,
42,
);
let algorithms = vec![
("Standard", Algorithm::Standard),
("Transposition", Algorithm::Transposition),
("MergeAndSplit", Algorithm::MergeAndSplit),
];
let mut group = c.benchmark_group("algorithm_comparison_corpus");
for (name, algo) in algorithms {
let transducer = Transducer::new(dict.clone(), algo);
group.bench_function(name, |b| {
b.iter(|| {
for query in &workload.queries {
let results: Vec<_> = transducer
.query(&query.word, query.max_distance)
.collect();
black_box(results);
}
})
});
}
group.finish();
}
Expected Results:
algorithm_comparison_corpus/Standard time: [12.8 µs 13.0 µs 13.2 µs]
algorithm_comparison_corpus/Transposition time: [14.8 µs 15.1 µs 15.4 µs] (+16%)
algorithm_comparison_corpus/MergeAndSplit time: [15.9 µs 16.2 µs 16.5 µs] (+25%)
Cargo.toml (Update)Purpose: Register new benchmark
Changes:
[[bench]]
name = "corpus_benchmarks"
harness = false
Location: Add after existing [[bench]] entries
docs/benchmarks/CORPUS_BENCHMARKING.md (NEW, ~600 lines)Purpose: Comprehensive guide to corpus-based benchmarking
Contents:
Section 1: Overview (~50 lines)
Section 2: Corpus Descriptions (~150 lines)
Section 3: Setup Instructions (~100 lines)
Section 4: Running Validation Tests (~100 lines)
Section 5: Running Benchmarks (~100 lines)
Section 6: CI Integration (~50 lines)
Section 7: Expected Results (~50 lines)
Section 8: References (~50 lines)
Template:
# Corpus-Based Benchmarking Guide
## Quick Start
1. Download corpora:
```bash
./scripts/download_corpora.sh
cargo test --test corpus_validation -- --ignored
cargo bench --bench corpus_benchmarks
Purpose: Realistic English word distribution for performance testing
Statistics:
Usage:
Citation:
Norvig, P. (2007). How to Write a Spelling Corrector.
Retrieved from https://norvig.com/spell-correct.html
Purpose: Real-world spelling errors for correctness validation
Statistics:
Usage:
Citation:
Mitton, R. (1985). Birkbeck spelling error corpus.
Oxford Text Archive. http://ota.ahds.ac.uk/
[... continues with all sections ...]
---
## CI/CD Integration
### Cache Strategy
**Key:** `corpora-v1-${{ hashFiles('scripts/download_corpora.sh') }}`
**Rationale:**
- Version prefix (`corpora-v1`): Manual cache invalidation if needed
- Script hash: Automatic invalidation when download logic changes
- Path: `data/corpora/`
- Size: ~10-15 MB (well within GitHub's 10 GB limit)
**Behavior:**
- First run: Download corpora, cache them (~30s download)
- Subsequent runs: Restore from cache (~5s restore)
- Script change: Re-download and re-cache
- Manual invalidation: Increment version (`corpora-v2`)
---
### Job Isolation
**Separate `corpus-validation` Job:**
**Benefits:**
1. **Parallel Execution:** Runs alongside other tests
2. **Independent Failure:** Corpus tests can fail without blocking other checks
3. **Clear Reporting:** Dedicated status check in GitHub UI
4. **Resource Allocation:** Can configure different runners if needed
**Dependencies:**
```yaml
test-report:
needs: [test, lint, benchmarks, corpus-validation]
Result: Overall success requires all jobs passing
Validation Results: 7 days
- name: Upload validation results
uses: actions/upload-artifact@v4
with:
name: corpus-validation-results
retention-days: 7
Rationale:
Benchmark Results: 30 days (existing configuration)
Rationale:
Metrics:
Benefits:
Metrics:
Benefits:
Benefits:
Research Impact:
CI Benefits:
Developer Benefits:
#[ignore] attribute prevents slow tests by defaultcargo test -- --ignored when neededDays 1-2 (8 hours):
Days 3-4 (8 hours):
Deliverables:
Days 1-2 (10 hours):
Days 3-4 (8 hours):
Deliverables:
Days 1-3 (12 hours):
Days 4-5 (8 hours):
Deliverables:
Total Effort: 44-56 hours (~1-1.5 weeks full-time)
Breakdown:
Probability: Medium (external dependencies) Impact: High (blocks CI)
Mitigation:
Monitoring: CI job failure alerts
Probability: Low (established, archived corpora) Impact: Medium (breaks reproducibility)
Mitigation:
Long-term: Consider hosting mirrors
Probability: Low (deterministic generation) Impact: Medium (false failures)
Mitigation:
Monitoring: Track recall variance across CI runs
Probability: Medium (corpus tests are slower) Impact: Low (separate job)
Mitigation:
corpus-validation doesn't block other checksTypical Impact: +1-2 minutes total CI time (amortized across parallel jobs)
Probability: Medium (unknown ground truth) Impact: Medium (false positives or negatives)
Mitigation:
Process: Measure → Analyze → Set threshold → Monitor → Adjust
Holbrook Corpus:
Aspell Corpus:
Wikipedia Corpus:
Mean Reciprocal Rank (MRR):
Normalized Discounted Cumulative Gain (NDCG):
Per-Language Performance:
Benchmark Suite:
Challenges:
Performance Dashboard:
Coverage Heatmaps:
Academic:
Production:
Development:
Last Updated: 2025-11-06 Status: Planning Complete - Awaiting Implementation Approval Estimated Delivery: 1-1.5 weeks full-time effort Risk Level: Low (modular design, established corpora, clear deliverables)
Related Documentation:
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |