Milestone 2 - Hierarchical Parsing and Standardization - Introduction to Data Science

This milestone turns the raw LaTeX corpus of Milestone 1 into structured data: every version of every paper is parsed into a hierarchy, its content is cleaned and normalized, its bibliography is converted to BibTeX, and identical references and elements are deduplicated across versions. All numbers below are computed from the parse results when the book is built.

import html
import json
from pathlib import Path

import matplotlib.pyplot as plt
import pandas as pd
from IPython.display import HTML, Markdown, display

# ../data when run from m2/ (book build), data/ when the kernel starts at the repo root (Binder)
DATA = next(p for p in (Path("../data/m2"), Path("data/m2")) if p.exists())
summary = json.loads((DATA / "summary.json").read_text())
versions = pd.read_parquet(DATA / "versions.parquet")
papers = pd.read_parquet(DATA / "papers.parquet")
resources = pd.read_parquet(DATA / "resources.parquet")
tables = json.loads((DATA / "tables.json").read_text())
example_path = DATA / "example.json"
example = json.loads(example_path.read_text()) if example_path.exists() else None
gnu = {}
for f in DATA.glob("time_*.txt"):
    for line in f.read_text().splitlines():
        key, _, value = line.strip().rpartition(": ")
        gnu[key] = value
ok = versions[versions.status == "ok"]

plt.rcParams.update({"figure.figsize": (7, 3.6), "figure.dpi": 110, "axes.spines.top": False,
                     "axes.spines.right": False, "axes.grid": True, "grid.alpha": 0.3})


def mb(x):
    return f"{x / 2**20:,.1f} MB"


def hms(seconds):
    seconds = int(round(seconds))
    return f"{seconds // 3600}h {seconds % 3600 // 60:02d}m {seconds % 60:02d}s"


def table(rows, columns):
    return pd.DataFrame(rows, columns=columns).style.hide(axis="index")

1. Pipeline¶

python -m introds parse processes the corpus paper by paper, in parallel worker processes, and records the outcome of every version in SQLite so an interrupted run resumes where it stopped.

version folder ──► 1. multi-file gathering (root, \input / \include, comments)
                ──► 2. standardization (math normalization, formatting cleanup)
                ──► 3. hierarchy construction (headings, lists, sentences, formulas, figures)
                ──► 4. bibliography (.bib, \bibitem, .bbl) ──► BibTeX entries
paper (all versions) ──► 5. reference deduplication (one key per reference, \cite renamed)
                     ──► 6. element deduplication (identical cleaned content shares one ID)
                     ──► elements / hierarchy / bibtex

rows = [
    ("Papers", f"{summary['papers']:,}"),
    ("Versions", f"{summary['versions_total']:,}"),
    ("Versions with TeX sources", f"{summary['versions_with_tex']:,}"),
    ("Versions parsed", f"{summary['versions_parsed']:,}"),
    ("Parsing success rate (versions with TeX)", f"{summary['parse_success_rate']:.2%}"),
    ("Versions without TeX (recorded as empty)", f"{summary['versions_total'] - summary['versions_with_tex']:,}"),
]
table(rows, ["", "Value"])

2. Multi-file gathering¶

Root. The publication root is the .tex file containing \documentclass. When several files declare one (standalone figures, templates), the root is the one with a \begin{document}, then a conventional name (main.tex, ms.tex, ...), then the most \inputs.
Compilation path. \input, \include, \subfile and \import are followed transitively, relative to the root folder (as LaTeX does) and to the including file. Include cycles and missing files are skipped. Every other .tex file in the folder is a redundant auxiliary file and is ignored.
Comments. % ... comments (but not \%), comment environments and \iffalse ... \fi blocks are removed before anything else, so a commented-out \input is plain text and never followed.

multi = summary["versions_multi_file"]
display(Markdown(
    f"**{multi:,}** parsed versions ({multi / max(summary['versions_parsed'], 1):.1%}) are split over "
    f"several `.tex` files; **{summary['versions_with_unused_tex']:,}** contain files outside the "
    f"compilation path (**{summary['unused_tex_files']:,}** files ignored)."
))
fig, ax = plt.subplots()
counts = ok.n_tex.clip(upper=15).value_counts().sort_index()
ax.bar(counts.index.astype(int).astype(str), counts.values, color="#4C72B0")
ax.set(xlabel=".tex files in the version (15 = 15 or more)", ylabel="versions",
       title="Figure 1. Number of .tex files per version")
plt.show()

3. Hierarchy construction¶

Levels. The document is the root. Sectioning commands (\part > \chapter > \section > \subsection > \subsubsection > \paragraph > \subparagraph) get their level from the commands the paper actually uses: in a paper without chapters, sections are the second level.
Leaves. Prose becomes sentences; equation blocks become formulas; floats (figure, table, algorithm, code listings, standalone tabular) become figures.
Lists. An itemize (also enumerate and description) is a list component whose items are the next level; an item contains sentences, formulas or nested lists.
Included / excluded. The abstract, acknowledgements (section or environment) and appendices (\appendix, including unnumbered \section*) are part of the tree. The references section (thebibliography, \bibliography, or a heading titled References / Bibliography) is not.
Sentences end at ., ! or ? followed by a new sentence, never inside math, commands (\cite{a.b}), URLs, decimal numbers or abbreviations such as e.g., i.e., et al., Fig. 1.

before, after = summary["kinds_before_dedup"], summary["kinds_after_dedup"]
kinds = ["document", "heading", "sentence", "formula", "figure", "list", "item"]
rows = [(k, f"{before.get(k, 0):,}", f"{after.get(k, 0):,}",
         f"{1 - after.get(k, 0) / before[k]:.1%}" if before.get(k) else "-") for k in kinds]
rows.append(("total", f"{summary['nodes_before_dedup']:,}", f"{summary['elements_after_dedup']:,}",
             f"{1 - summary['elements_after_dedup'] / summary['nodes_before_dedup']:.1%}"))
display(Markdown("Tree nodes over all versions, and distinct elements after cross-version deduplication:"))
table(rows, ["kind", "nodes (all versions)", "elements (deduplicated)", "reduction"])

fig, ax = plt.subplots()
depth = ok.max_depth.value_counts().sort_index()
ax.bar(depth.index.astype(int).astype(str), depth.values, color="#55A868")
ax.set(xlabel="maximum depth of the tree (root = 0)", ylabel="versions",
       title="Figure 2. Depth of the hierarchy")
plt.show()
display(Markdown(
    f"**{summary['versions_with_appendix']:,}** versions have appendices and "
    f"**{summary['papers_with_acknowledgements']:,}** papers have an acknowledgements heading."
))

4. Standardization¶

Cleanup. Formatting without semantic meaning is removed: \centering, float placement options ([htpb]), table rules (\toprule, \midrule, ...), spacing (\vspace, \hspace), font size and style switches, \label, title-page metadata (\author, \affiliation, ...), colour commands and \makeatletter macro code. Emphasis wrappers keep their text (\textbf{x} → x).
Inline math $ ... $ and \begin{math} become $ ... $ .
Block math $$ ... $$, \[ ... \], equation*, displaymath become \begin{equation} ... \end{equation}; multi-line environments keep their alignment inside it (align → \begin{equation}\begin{aligned} ... \end{aligned}\end{equation}), so the result is still valid LaTeX. \label, \nonumber and \notag are dropped.

\begin{align*} a &= b \\ c &= d \end{align*}   →   \begin{equation}\begin{aligned}a &= b \\ c &= d\end{aligned}\end{equation}
\[ E = mc^2 \]                                  →   \begin{equation}E = mc^2\end{equation}
\( x_i \)                                       →   $x_i$

5. References¶

Each version’s bibliography comes from, in this order:

the .bib files named by \bibliography{...} / \addbibresource{...}, keeping only the entries actually cited (as BibTeX does), unless \nocite{*};
\bibitem entries of a thebibliography environment in the TeX, converted to BibTeX with regular expressions: key, authors (first block), title (second \newblock, quotes or emphasis), venue, year, DOI, URL and arXiv identifier (turned into an arxiv.org/abs URL), entry type from the venue (In Proceedings → inproceedings, volume/journal → article, publisher → book);
the .bbl file, only when the version has no .bib (natbib \bibitem lists and biblatex \entry records are both supported).

Deduplication. Within a paper, entries that share a DOI, a normalized title, or a key are one reference. The key used by the latest version is kept, every \cite{} of the other keys is renamed to it, and the fields are unioned (the latest non-empty value wins), so no information is lost:

version	key	title	author	year	doi
v1	`vaswani2017`	✓	✓	✓
v2	`vit_transformer`	✓	✓	✓	✓
v3	`vit_transformer`	✓	✓
unified	`vit_transformer`	✓	✓	✓	✓

src = summary["bib_sources"]
labels = {"bib": ".bib", "bibitem": "\\bibitem in TeX", "bbl": ".bbl", "none": "none"}
fig, ax = plt.subplots()
items = sorted(src.items(), key=lambda kv: -kv[1])
ax.barh([", ".join(labels.get(p, p) for p in k.split(",")) for k, _ in items], [v for _, v in items], color="#8172B2")
ax.invert_yaxis()
ax.set(xlabel="versions", title="Figure 3. Source of each version's bibliography")
plt.show()
rows = [("Bibliography entries over all versions", f"{summary['entries_before_dedup']:,}"),
        ("Unified entries after deduplication", f"{summary['entries_after_dedup']:,}"),
        ("Reduction", f"{1 - summary['entries_after_dedup'] / max(summary['entries_before_dedup'], 1):.1%}")]
table(rows, ["", "Value"])

6. Deduplication across versions¶

After cleanup and citation renaming, an element whose kind and content match exactly in two versions is stored once, so a single element_id serves both versions. Each version keeps its own root (<paper>#root1, <paper>#root2, ...) and its own parent edges, so the same sentence can sit under different headings in different versions. Element IDs are the publication key followed by a kind prefix and a counter: h heading, s sentence, e equation, f figure, l list, i item. The root is its own parent (parent_id is required to be non-null).

multi = papers[papers.n_versions_parsed >= 2]
fig, ax = plt.subplots()
ratio = (1 - multi.n_elements / multi.n_nodes).clip(lower=0)
ax.hist(ratio, bins=40, color="#C44E52")
ax.set(xlabel="share of tree nodes removed by deduplication", ylabel="papers",
       title="Figure 4. Deduplication in papers with two or more parsed versions")
plt.show()
display(Markdown(
    f"For the **{len(multi):,}** papers with at least two parsed versions, deduplication removes "
    f"**{1 - multi.n_elements.sum() / multi.n_nodes.sum():.1%}** of the tree nodes."
))

Explore one paper¶

The tree below is generated from the parse output. Click a heading, list or item to expand it. Elements shared by several versions show the versions they appear in.

def render(example, version):
    elements = example["elements"]
    edges = [(e, p) for v, e, p in example["hierarchy"] if v == version]
    in_versions = {}
    for v, e, _ in example["hierarchy"]:
        in_versions.setdefault(e, set()).add(v)
    children, root = {}, None
    for e, p in edges:
        if e == p:
            root = e
        else:
            children.setdefault(p, []).append(e)

    def node(e, open_=False):
        kind, content = elements[e]
        tag = f"<code>{html.escape(e.split('#')[1])}</code>"
        shared = sorted(in_versions[e])
        badge = f" <small>(v{', v'.join(map(str, shared))})</small>" if len(shared) > 1 else ""
        text = html.escape(content if len(content) < 300 else content[:300] + " ...")
        if e in children:
            label = f"<b>{kind}</b> {tag}: {text}{badge}"
            inner = "".join(f"<li>{node(c)}</li>" for c in children[e])
            return f"<details{' open' if open_ else ''}><summary>{label}</summary><ul>{inner}</ul></details>"
        return f"<i>{kind}</i> {tag}: {text}{badge}"

    return node(root, open_=True)


if example:
    versions_of_example = sorted({v for v, _, _ in example["hierarchy"]})
    parts = [f"<h4>arXiv:{example['arxiv_id']} - version {v}</h4>" + render(example, v)
             for v in versions_of_example]
    display(HTML("<div style='font-size: 0.85em'>" + "".join(parts) + "</div>"))

7. Version coverage¶

coverage = papers.n_versions_parsed / papers.n_versions
fig, ax = plt.subplots()
ax.hist(coverage, bins=20, color="#4C72B0")
ax.set(xlabel="parsed versions / versions of the paper", ylabel="papers",
       title="Figure 5. Version coverage of every publication")
plt.show()
display(Markdown(
    f"**{summary['papers_full_version_coverage']:,}** of {summary['papers']:,} papers have every "
    f"version parsed (mean coverage {summary['mean_version_coverage']:.1%}). Versions without TeX "
    "(PDF-only or withdrawn) cannot be parsed; they are recorded as empty, not dropped."
))

8. Performance¶

Measured on Google Colab, CPU-only runtime (2 vCPU Intel Xeon @ 2.20 GHz, 13.6 GB RAM), with one worker process per CPU. Wall time covers python -m introds parse end to end and is cross-checked with GNU time -v; RAM is sampled every 2 seconds over the main process and its workers.

rows = [
    ("End-to-end wall time", hms(summary["time_wall_total_s"])),
    ("Average wall time per publication", f"{summary['time_wall_per_paper_s']:.3f} s"),
    ("Average processing time per publication (one worker)", f"{summary['time_per_paper_avg_s']:.3f} s"),
    ("Peak RAM (sampled, all processes)", mb(summary["ram_peak_bytes"] or 0)),
    ("Average RAM (sampled)", mb(summary["ram_avg_bytes"] or 0)),
    ("Output: parsed papers (parsed/*.json.gz)", mb(summary["output_parsed_bytes"])),
    ("Output: elements / hierarchy / bibtex Parquet tables", mb(summary["output_tables_bytes"])),
]
if "Elapsed (wall clock) time (h:mm:ss or m:ss)" in gnu:
    rows.append(("GNU time: elapsed wall clock", gnu["Elapsed (wall clock) time (h:mm:ss or m:ss)"]))
if "Maximum resident set size (kbytes)" in gnu:
    rows.append(("GNU time: maximum resident set size (largest process)",
                 mb(int(gnu["Maximum resident set size (kbytes)"]) * 1024)))
table(rows, ["Measure", "Value"])

if len(resources):
    res = resources.sort_values("ts")
    minutes = (res.ts - res.ts.min()) / 60
    fig, ax = plt.subplots()
    ax.plot(minutes, res.rss_bytes / 2**20, color="#C44E52", lw=1)
    ax.set(xlabel="minutes since start", ylabel="RAM (MB)", title="Figure 6. RAM during the parse")
    plt.show()

9. Output data¶

Each paper’s result is kept in parsed/<paper>.json.gz: its distinct elements, the node-parent edges of every version and its unified BibTeX entries, so the final tables are built without parsing again. A version without TeX sources yields no elements and stays recorded as empty. The three tables below are exported as sharded Parquet for the final dataset, published with Milestone 3.

for name in ("elements", "hierarchy", "bibtex"):
    t = tables[name]
    display(Markdown(f"**{name}**: {t['rows']:,} rows in {t['shards']} Parquet shard(s)"))
    display(table([(c["name"], c["type"], "yes" if c["nullable"] else "no", str(t["sample"].get(c["name"]))[:80])
                   for c in t["columns"]], ["column", "type", "nullable", "example"]))

10. Limitations¶

The parser is regular-expression based, not a TeX engine: user macros (\newcommand) are not expanded, and unusual document classes may hide structure in custom commands.
Sentence splitting is rule based; very long “sentences” usually come from text without final punctuation (lists of items, captions).
\bibitem conversion relies on the usual \newblock layout; free-form references may get an incomplete title or venue.

11. References¶

Lab Instructors, Milestone 2 statement.
BibTeX, natbib, biblatex and REVTeX documentation: the bibliography formats read in Section 5.
amsmath documentation: multi-line math inside equation (Section 4).
Python documentation: re and multiprocessing.
Apache Parquet and Hugging Face dataset configuration: the output tables (Section 9).

12. Requirements checklist¶

Requirement (Milestone 2 statement)	Where
Every version of every paper parsed; versions without TeX recorded as empty	1, 7, 9
Root file, transitive `\input` / `\include`, commented commands ignored, auxiliary files ignored	2, Figure 1
Hierarchy: document root, automatic levels, sentences, block formulas, figures, tables as figures	3, Figure 2
Lists and items; references section excluded; acknowledgements and appendices included	3
Sentence splitting that respects math, commands, abbreviations, URLs and decimals	3
Formatting cleanup	4
Inline and block math normalized	4
`\bibitem` converted to BibTeX	5, Figure 3
Reference deduplication: one key, `\cite` renamed, fields unioned	5
Full-text deduplication across versions, after cleanup	6, Figure 4
Element IDs; `elements`, `hierarchy` and `bibtex` tables	6, 9
Parsing success rate	1
Version coverage of every publication	7, Figure 5
Element and entry counts before and after deduplication	3, 5
End-to-end wall time and average time per publication	8
Maximum RAM and final output size, on Colab CPU-only	8, Figure 6
Figures and tables generated during book compilation	every figure and table on this page