PDF text extraction

Deep dive

How it works

In: the glyphs one page's content stream draws (code, x, y, width, size) · Out: text in reading order, or a route to OCR · State: none between pages; font maps per document · Cost: O(n log n) in glyphs per page; about 0.1 ms per 3,400 glyphs measured, decoding the file costs more

1. Interpret. Tj, TJ (strings plus kerning numbers), ' and " draw glyphs; Tm, Td, TD, T* position them; Tc, Tw, Tz, Ts change spacing, scale, rise. In TJ, a large negative number (thousandths of an em) is a word space.
2. Decode. Map codes via /ToUnicode, else encoding and Adobe Glyph List; /ActualText overrides. Count U+FFFD and private-use characters per page.
3. Columns. Merge glyph x-extents; gaps of at least 1.5 em split the page.
4. Lines. Per column, sort top-down; glyphs within 0.4 em of a line's first glyph join it (absorbs superscripts and jitter).
5. Words. Sort a line by x; a gap above 0.25 em inserts a space. Many producers write no space glyphs.
6. Order and stitch. Columns left to right. Remove a line-end hyphen before a lowercase letter, expand ligatures, drop lines repeated at the same place on most pages. If the file is tagged, the structure tree (and /Artifact marks on page furniture) beats all heuristics.
7. Route. No text operators, or invisible text (render mode 3) over a page-sized image, is a scan: preprocess and OCR it. An invisible layer is an earlier OCR run; trust it only if you trust that engine.

stream ─► interpreter ─► glyphs ─► ToUnicode ─► chars + boxes
                                                    │
  no text / garbage ◄──── router ◄──────────────────┤ ok
        │                                           ▼
       OCR                      columns ─► lines ─► words ─► order,
                                                      de-hyphenate ─► text

Tables and math are the known hard cases: borders are vector lines and sub/superscripts are separate runs, so heuristics give a flat stream; use table structure recognition or a model. Next step: text chunking.

Code

#[derive(Clone, Copy)]
pub struct Glyph { pub ch: char, pub x: f32, pub y: f32, pub w: f32, pub size: f32 }

fn ligature(c: char) -> Option<&'static str> {
    match c { 'fi' => Some("fi"), 'fl' => Some("fl"), 'ff' => Some("ff"), _ => None }
}

/// Projection profile on x: merge glyph extents, a gap >= min_gap between merged runs is a column break.
fn columns(g: &[Glyph], min_gap: f32) -> Vec<(f32, f32)> {
    let mut v: Vec<(f32, f32)> = g.iter().map(|g| (g.x, g.x + g.w)).collect();
    v.sort_by(|a, b| a.0.total_cmp(&b.0));
    let (mut cols, mut cur) = (vec![], v[0]);
    for &(a, b) in &v[1..] {
        if a - cur.1 >= min_gap { cols.push(cur); cur = (a, b); } else { cur.1 = cur.1.max(b); }
    }
    cols.push(cur);
    cols
}

/// One column: glyphs -> baselines (top to bottom) -> words (left to right) -> line strings.
fn column_lines(mut g: Vec<Glyph>) -> Vec<String> {
    g.sort_by(|a, b| b.y.total_cmp(&a.y));
    let (mut lines, mut i) = (vec![], 0);
    while i < g.len() {
        let top = g[i];
        let mut j = i;
        // same line while within 0.4 em of the first (highest) glyph: tolerates superscripts and jitter
        while j < g.len() && top.y - g[j].y <= 0.4 * top.size { j += 1; }
        let row = &mut g[i..j];
        row.sort_by(|a, b| a.x.total_cmp(&b.x));
        let (mut s, mut end) = (String::new(), f32::NEG_INFINITY);
        for c in row.iter() {
            if c.ch == ' ' { end = f32::NEG_INFINITY; if !s.ends_with(' ') { s.push(' '); } continue; }
            if !s.is_empty() && !s.ends_with(' ') && c.x - end > 0.25 * c.size { s.push(' '); } // word gap in em
            match ligature(c.ch) { Some(l) => s.push_str(l), None => s.push(c.ch) }
            end = c.x + c.w;
        }
        lines.push(s.trim().to_string());
        i = j;
    }
    lines
}

/// Join lines; a trailing '-' after a letter followed by a lowercase start is a soft hyphen.
fn join(lines: &[String]) -> String {
    let mut out = String::new();
    for (i, l) in lines.iter().enumerate() {
        if i > 0 {
            let soft = out.ends_with('-')
                && out[..out.len() - 1].chars().last().map_or(false, char::is_alphabetic)
                && l.chars().next().map_or(false, char::is_lowercase);
            if soft { out.pop(); } else { out.push(' '); }
        }
        out.push_str(l);
    }
    out
}

pub fn page_text(glyphs: &[Glyph]) -> String {
    if glyphs.is_empty() { return String::new(); }
    let mut sizes: Vec<f32> = glyphs.iter().map(|g| g.size).collect();
    sizes.sort_by(f32::total_cmp);
    let em = sizes[sizes.len() / 2];
    let cols = columns(glyphs, 1.5 * em);
    let texts: Vec<String> = cols.iter().map(|&(lo, hi)| {
        let col: Vec<Glyph> = glyphs.iter().copied().filter(|g| g.x >= lo && g.x <= hi).collect();
        join(&column_lines(col))
    }).collect();
    texts.join("\n\n") // columns are already left to right
}

fn put(out: &mut Vec<Glyph>, s: &str, x0: f32, y: f32) {
    for (k, ch) in s.chars().enumerate() {
        if ch != ' ' { out.push(Glyph { ch, x: x0 + 5.0 * k as f32, y, w: 5.0, size: 10.0 }); }
    }
}

fn main() {
    let left = ["The text extrac-", "tion works on glyphs.", "Second paragraph line."];
    let right = ["Right column starts", "after the first one."];
    let mut g = vec![];
    for i in 0..3 { // content-stream order interleaves the columns row by row
        put(&mut g, left[i], 50.0, 700.0 - 12.0 * i as f32);
        if i < 2 { put(&mut g, right[i], 330.0, 700.0 - 12.0 * i as f32 + 1.0); } // 1 pt baseline jitter
    }
    let t = page_text(&g);
    assert_eq!(t, "The text extraction works on glyphs. Second paragraph line.\n\nRight column starts after the first one.");
}

The synthetic page interleaves two columns in stream order, jitters one baseline and has no space glyphs.

Complexity and constants

• Reconstruction: a sort for the profile and one per column, O(n log n); 20 bytes per glyph.
• Measured (mine, M4 Pro, release build): a synthetic 3,400-glyph two-column page in memory, 34-35 million glyphs/s over three runs of 2,000 pages. Excludes parsing, decompression and font decoding, which dominate real runs.
• Cost drivers: Flate decompression, font and CMap parsing, glyph count, then any layout model or OCR.

Efficiency

• Cost: reconstruction is about 0.1 ms per 3,400-glyph page on one M4 Pro core (measured here), CPU-bound. The Docling report measured layout-model runs without OCR over 225 pages: 1.27-2.45 pages/s on an Apple M3 Max (16 cores), 0.60-1.57 on a 16-core Xeon E5-2690; EasyOCR on CPU "upwards of 30 seconds per page"; TableFormer 2-6 s per table. The gap to OCR is order of 10^3-10^5 (arithmetic; my figure excludes file decoding).
• Levers:
  • Route per page: parse first, OCR only failures — skips about 30 s/page on pages that have text (Docling report) — mixed batches with some scans.
  • Skip the layout model when a heuristic is confident (one column, no rules) — avoids per-page model time and 2-6 s per table (Docling report) — e-books, plain letters.
  • Native parser backend — pypdfium 2.45 vs Docling's own parser 1.34 pages/s, 16 threads, M3 Max (Docling report) — when parsing is the bottleneck.
  • Page-level parallelism — Xeon 4 → 16 threads: 0.60 → 0.92 pages/s (Docling report), a modest gain — large batches.
• Naive → standard → state of the art:
  • Concatenate in stream order · fastest; wrong in columns, garbage on bad fonts
  • Layout heuristics (pdfminer, pdftotext, PyMuPDF) + per-page OCR fallback · parsing cheap, OCR only where needed
  • ML layout and table models over programmatic text (Docling), or page-image models (Nougat, Marker) for math · seconds per page on CPU

Implementation notes

• Advance = (width/1000 × size + Tc + Tw for spaces) × Tz; skipping Tc/Tw misplaces gaps.
• pdfminer.six defaults (verified in its source): word_margin 0.1, char_margin 2.0, line_margin 0.5, line_overlap 0.5, boxes_flow 0.5. My 0.25 / 0.4 / 1.5 em thresholds are untuned beyond one synthetic page.
• OCR fallback when many characters are U+FFFD or private-use, or a page has little text under a large image; tune both thresholds on your corpus.
• Run NFKC and soft-hyphen cleanup afterwards (text normalization).

Pitfalls

• A full-width title closes every column gap; XY-cut cuts horizontally first to avoid this.
• Fonts without ToUnicode (some Type 3 and subset fonts) give wrong characters at perfect positions; only a decode-quality test catches them.
• The hyphen rule joins real compounds ("well-" / "known"); check the joined word against a dictionary.
• Fake bold (glyph drawn twice with a tiny offset) doubles letters; rotated pages need coordinate rotation first.
• Repeated headers and watermarks pollute chunks; AcroForm field values live outside the content stream.

Variants and alternatives

In production

Search over filings, invoice capture, statement ingestion, paper and manual indexing and form pipelines run on pdfium, MuPDF, poppler or PDFBox; browsers use pdf.js.

Implementations

Sources

• Adobe, PDF 32000-1:2008 (ISO 32000-1): text objects, fonts, ToUnicode, tagged PDF. spec
• ISO 32000-2:2020, Portable document format, Part 2: PDF 2.0 (no link: the PDF Association and ISO sites refused automated checks).
• Christoph Auer et al., Docling Technical Report, arXiv 2024. paper · code
• Lukas Blecher et al., Nougat: Neural Optical Understanding for Academic Documents, arXiv 2023. paper · code
• Yiheng Xu et al., LayoutLM: Pre-training of Text and Layout for Document Image Understanding, KDD 2020. paper
• pdfminer.six, Converting a PDF file to text. docs · code
• PyMuPDF, text extraction recipes. docs · Marker. code