Text Summarization Algorithms for Bilingual Public Policy Documents

This project compares three extractive summarization algorithms on bilingual English and French public policy documents: TextRank, greedy submodular summarization, and lazy greedy submodular summarization. The goal is to choose a small, source-faithful summary while measuring the real cost of scaling across short, medium, long, and very long UN-style documents.

The main result: lazy greedy matched regular greedy's selected sentences on all 16 documents while saving about 27.8% of estimated gain checks. TextRank remains a strong graph baseline, but its dense sentence graph reached the highest peak memory in this run: 483.37 MB versus about 32.75 MB for the submodular methods.

Repository target: https://github.com/Drey332/Text_Summarization_Algorithms_for_Bilingual_Public_Policy_Documents

Why This Project Matters

Policy documents are long, formal, repetitive, and often multilingual. A useful summarizer for this setting should not invent wording, because legal and policy language needs to stay grounded in the source. Extractive summarization is a good fit because every output sentence is selected directly from the original document.

This project is also an algorithms project, not only an NLP demo. It asks how different definitions of "important" behave as the sentence pool grows:

• TextRank: importance as graph centrality.
• Greedy submodular: importance as new marginal coverage and diversity.
• Lazy greedy: the same submodular objective, accelerated with cached upper bounds.

Project Snapshot

Item	Value
Task	Extractive text summarization
Domain	UN/public policy documents
Languages	English and French
Documents	16
Cleaned sentence candidates	3,836
Summary budget	3 source sentences per document
Algorithms	TextRank, greedy submodular, lazy greedy submodular
Evaluation	Runtime, peak memory, graph density, objective value, overlap, gain-check savings, qualitative output inspection

Dataset

The corpus is organized by language and document size:

• Data/English and Data/French: original source PDFs.
• Data/Converted_Text: raw extracted text.
• Data/Clean_Text: cleaned readable documents.
• Data/Clean_Sentences: sentence candidates used by all algorithms.
• Data/Preprocessed: token/lemma outputs for inspection and analysis.
• Data/Preprocessing_Reports: QA reports from preprocessing.

All three summarization algorithms read from the same cleaned sentence files, so the comparison measures algorithm behavior rather than differences in input.

What I Built

flowchart LR
    A[Source PDFs<br/>English and French policy documents] --> B[Text extraction<br/>PyMuPDF]
    B --> C[Preprocessing<br/>clean headers, page markers, OCR artifacts]
    C --> D[Clean sentence candidates<br/>Data/Clean_Sentences]
    D --> E[TextRank<br/>graph centrality]
    D --> F[Greedy submodular<br/>coverage + topic + section diversity]
    D --> G[Lazy greedy<br/>same objective, fewer recomputations]
    E --> H[Comparison outputs<br/>CSV, JSON, report, graphs]
    F --> H
    G --> H

Loading

Core files:

File	Purpose
Algorithms/text_preprocessing.py	Converts PDFs, cleans text, creates sentence candidates, saves QA reports.
Algorithms/TextRank/textrank.py	Graph-based TextRank baseline using TF-IDF cosine similarity and PageRank.
Algorithms/Greedy Submodular/Greedy_submodular.py	Regular greedy maximization of a coverage/diversity objective.
Algorithms/Lazy Greedy/lazy_Greedy.py	Priority-queue lazy greedy version of the same submodular objective.
Algorithms/comparison.py	Runs all algorithms on the same corpus and writes comparison artifacts.

Algorithm Comparison

Algorithm	Main idea	Strength	Main cost
TextRank	Build a weighted sentence-similarity graph and rank sentences with PageRank.	Strong unsupervised baseline for central sentences.	Dense n x n similarity graph and graph processing.
Greedy submodular	Select the sentence with the highest marginal gain under a coverage, topic diversity, and section diversity objective.	More control over redundancy and document coverage.	Recomputes gains for remaining candidates at each step.
Lazy greedy	Preserve the greedy objective but use cached marginal gains as upper bounds.	Same greedy selections with fewer gain computations.	Worst case can approach regular greedy if many cached gains become stale.

The implemented submodular objective is:

F(S) = coverage(S) + 0.35 * topic_diversity(S) + 0.20 * section_diversity(S)

Coverage rewards sentences that represent the document broadly. Topic diversity uses KMeans topic labels to avoid selecting only one theme. Section diversity discourages selecting every sentence from the same part of a long document.

Key Results

The full comparison run processed 16 documents and 3,836 sentence candidates with a fixed budget of 3 summary sentences.

Metric	TextRank	Greedy Submodular	Lazy Greedy
Total runtime	3.080954 s	0.911426 s	0.782153 s
Highest peak memory	483.37 MB	32.75 MB	32.74 MB
Greedy/lazy selected-sentence mismatch	N/A	0 documents	0 documents
Average TextRank vs greedy overlap	0.350	N/A	N/A
Average lazy gain-check savings	N/A	N/A	27.8%

Interpretation:

• TextRank was the most memory-heavy method because policy documents created dense sentence graphs.
• Greedy submodular summarization gave a more explicit coverage/diversity objective than graph centrality alone.
• Lazy greedy preserved the regular greedy solution while reducing repeated marginal-gain calculations.
• Language did not change the abstract algorithmic complexity, but French preprocessing produced more sentence candidates in the very long group, which affected actual runtime and memory.

Result Graphs

Runtime by Language and Size

Peak Memory by Language and Size

TextRank Graph Density and Similarity

Lazy Greedy Gain-Check Savings

Selected-Sentence Overlap

Complexity And Scalability

Let:

• n = number of sentence candidates
• d = TF-IDF feature dimension
• w = total word tokens
• k = summary sentence budget
• e = nonzero TextRank graph edges
• p = PageRank iterations
• q = KMeans iterations
• r = lazy greedy recomputations

Algorithm	Dominant time complexity	Memory pressure
TextRank	O(w + n^2 d + p(n + e) + n log n)	O(n^2 + nd + e)
Greedy submodular	O(w + n^2 d + qncd + k n^2)	O(n^2 + nd + n)
Lazy greedy	O(w + n^2 d + qncd + r n + (n+r) log n)	O(n^2 + nd + n)

The practical lesson is that sentence count drives scaling. File size matters, but the real algorithmic input is the number and quality of cleaned sentence candidates. Long policy documents create large similarity matrices, and noisy sentence segmentation can make every algorithm look worse.

How To Run

Create an environment and install dependencies:

python3 -m venv .venv
source .venv/bin/activate
python3 -m pip install -r requirements.txt

If you want to rerun preprocessing from PDFs, install the spaCy language models:

python3 -m spacy download en_core_web_sm
python3 -m spacy download fr_core_news_sm

Run preprocessing:

python3 Algorithms/text_preprocessing.py

Run each algorithm:

python3 Algorithms/TextRank/textrank.py
python3 "Algorithms/Greedy Submodular/Greedy_submodular.py"
python3 "Algorithms/Lazy Greedy/lazy_Greedy.py"

Run the full comparison:

python3 Algorithms/comparison.py

Main outputs:

• Data/Algorithm_Comparison/comparison_detailed.csv
• Data/Algorithm_Comparison/comparison_group_summary.csv
• Data/Algorithm_Comparison/comparison_document_overlap.csv
• Data/Algorithm_Comparison/comparison_results.json
• Data/Algorithm_Comparison/comparison_report.txt
• Data/Algorithm_Comparison/summary_examples.txt
• Data/Algorithm_Comparison/Graphs/

Reports And Slides

• CUS_715_Final_report.pdf: full project report with problem statement, related work, complexity analysis, results, and error analysis.
• Vincent_Text sumarization_slides.pdf: presentation slides summarizing the algorithms and findings.

What The Results Show

TextRank and submodular summarization often agree on important policy content, but they get there through different logic. TextRank favors sentences that are central in a similarity graph. Greedy submodular summarization favors sentences that add new coverage and diversity after previous selections. Lazy greedy keeps that same objective but avoids some recomputation by using diminishing returns.

The strongest engineering lesson is that preprocessing is not cosmetic. If a sentence candidate contains OCR noise, page metadata, or a giant legal list fragment, the algorithms treat it as a real candidate. Better sentence segmentation would directly improve summary readability.

Limitations And Next Steps

• The dataset is realistic but small: 16 documents.
• The fixed k = 3 sentence budget makes comparisons clean, but future work should also test word-budget summaries.
• Some French OCR and PDF extraction artifacts remain.
• Very long legal/list structures sometimes become oversized sentence candidates.
• Future work should add stronger legal-aware sentence splitting, normalized objective values, and human quality evaluation.

License And Reuse

This repository currently documents an academic portfolio project. Before external reuse, choose and add an explicit open-source license that matches the intended permissions for the code, data, reports, and slides.