Compare commits
| Author | SHA1 | Date | |
|---|---|---|---|
|
|
bfe3f55032 | ||
|
|
e0be3b5021 | ||
|
|
fb45d37dfe | ||
|
|
5eb6a13860 |
+763
-7
@@ -1921,6 +1921,53 @@ pub(crate) fn is_newspaper_layout(
|
||||
ratio > 0.5
|
||||
}
|
||||
|
||||
/// Short dense prose columns: a genuine column set below
|
||||
/// [`is_newspaper_layout`]'s 15-line floor (three-column FAQ, the closing
|
||||
/// page of an article) whose lines fill their column widths is a set of
|
||||
/// independent text flows that must read column-by-column.
|
||||
///
|
||||
/// This is a *reading-order* refinement only — it deliberately lives outside
|
||||
/// `is_newspaper_layout` because the table pipeline uses that predicate as a
|
||||
/// veto when building borderless tables, and a long-celled table must keep
|
||||
/// both its row-wise reading and its extraction there. Borderless tables are
|
||||
/// also excluded here by construction: cell text leaves most of the column
|
||||
/// width empty, and every column must qualify, so a term/description pair
|
||||
/// keeps row-wise reading on its short side.
|
||||
///
|
||||
/// Deliberately stricter than `columns_have_prose` (60% fill on 60% of lines
|
||||
/// vs 45% fill with a ratio-or-run escape): that gate asks whether raw items
|
||||
/// justify *creating* a column split, where a false negative just keeps the
|
||||
/// single-column order; this one overrides the borderless-table defense on
|
||||
/// already-built columns, where a false positive reads a table column-wise
|
||||
/// and destroys its rows.
|
||||
fn short_prose_columns(per_column_lines: &[Vec<TextLine>], columns: &[ColumnRegion]) -> bool {
|
||||
if per_column_lines.len() != columns.len() || columns.len() < 2 {
|
||||
return false;
|
||||
}
|
||||
// Only the 5..15-line window: columns with more lines are the balance
|
||||
// and Y-collision checks' jurisdiction in `is_newspaper_layout`.
|
||||
let min_lines = per_column_lines.iter().map(|c| c.len()).min().unwrap_or(0);
|
||||
if !(5..15).contains(&min_lines) {
|
||||
return false;
|
||||
}
|
||||
per_column_lines.iter().zip(columns).all(|(lines, col)| {
|
||||
let col_width = (col.x_max - col.x_min).max(1.0);
|
||||
let full = lines
|
||||
.iter()
|
||||
.filter(|line| {
|
||||
let left = line.items.iter().map(|i| i.x).fold(f32::INFINITY, f32::min);
|
||||
let right = line
|
||||
.items
|
||||
.iter()
|
||||
.map(|i| i.x + effective_width(i))
|
||||
.fold(f32::NEG_INFINITY, f32::max);
|
||||
right - left >= col_width * 0.60
|
||||
})
|
||||
.count();
|
||||
full * 10 >= lines.len() * 6
|
||||
})
|
||||
}
|
||||
|
||||
/// Split column lines into a core cluster and stragglers.
|
||||
/// The core is the largest group of consecutive lines separated by normal
|
||||
/// line spacing. Lines in other groups (header remnants, per-word items from
|
||||
@@ -2222,16 +2269,92 @@ fn group_into_lines_with_thresholds_and_regions_impl(
|
||||
None => detect_columns(column_detection_items, page, table_pages.contains(&page)),
|
||||
};
|
||||
|
||||
if columns.len() <= 1 {
|
||||
// Single column - use simple sorting
|
||||
let lines = group_single_column(page_items, adaptive_threshold);
|
||||
all_lines.extend(lines);
|
||||
// Whether the page-level model found columns or not, band
|
||||
// segmentation runs first: pages whose column structure changes
|
||||
// vertically (newsletter bands, figure-split flows, a three-column
|
||||
// strip inside a two-column page) cannot be represented by one
|
||||
// full-height column set, and the projection either finds nothing or
|
||||
// weaves the odd band's columns into the wrong buckets. It engages
|
||||
// only on contradicting band evidence, so pages the flat model
|
||||
// explains keep their current ordering. Chart pages are excluded
|
||||
// because chart-internal text would seed phantom bands.
|
||||
let banded = if chart_regions.contains_key(&page) {
|
||||
None
|
||||
} else {
|
||||
try_banded_layout(
|
||||
&page_items,
|
||||
column_detection_items,
|
||||
&columns,
|
||||
page,
|
||||
table_pages.contains(&page),
|
||||
adaptive_threshold,
|
||||
)
|
||||
};
|
||||
if let Some(lines) = banded {
|
||||
all_lines.extend(lines);
|
||||
} else if columns.len() <= 1 {
|
||||
all_lines.extend(group_single_column(page_items, adaptive_threshold));
|
||||
} else {
|
||||
all_lines.extend(order_multi_column_region(
|
||||
page_items,
|
||||
&columns,
|
||||
adaptive_threshold,
|
||||
page,
|
||||
));
|
||||
}
|
||||
}
|
||||
|
||||
all_lines
|
||||
}
|
||||
|
||||
/// Order a multi-column region's items into reading order.
|
||||
///
|
||||
/// The core multi-column machinery: pre-mask spanning lines, bucket items
|
||||
/// into columns by horizontal overlap, group each column into lines, then
|
||||
/// emit newspaper (sequential columns) or tabular (Y-interleaved) ordering.
|
||||
///
|
||||
/// Whole-page entry: keeps every page-level defense (newspaper/tabular
|
||||
/// classification and straggler splitting) active.
|
||||
fn order_multi_column_region(
|
||||
page_items: Vec<TextItem>,
|
||||
columns: &[ColumnRegion],
|
||||
adaptive_threshold: f32,
|
||||
page: u32,
|
||||
) -> Vec<TextLine> {
|
||||
order_columns_with_policy(page_items, columns, adaptive_threshold, page, false)
|
||||
}
|
||||
|
||||
/// Banded-planner entry: the columns already passed the planner's prose
|
||||
/// validation for a Y-cohesive band, which replaces two page-level defenses
|
||||
/// that would misfire on a band — [`is_newspaper_layout`]'s line-count
|
||||
/// minimums (bands are shorter than pages, so a genuine two-column band
|
||||
/// would Y-interleave) and straggler splitting (a merged band deliberately
|
||||
/// flows across a figure gap, which splitting would undo). Only
|
||||
/// [`try_banded_layout`] may call this.
|
||||
fn order_validated_band(
|
||||
page_items: Vec<TextItem>,
|
||||
columns: &[ColumnRegion],
|
||||
adaptive_threshold: f32,
|
||||
page: u32,
|
||||
) -> Vec<TextLine> {
|
||||
order_columns_with_policy(page_items, columns, adaptive_threshold, page, true)
|
||||
}
|
||||
|
||||
fn order_columns_with_policy(
|
||||
page_items: Vec<TextItem>,
|
||||
columns: &[ColumnRegion],
|
||||
adaptive_threshold: f32,
|
||||
page: u32,
|
||||
band_validated: bool,
|
||||
) -> Vec<TextLine> {
|
||||
let mut all_lines = Vec::new();
|
||||
{
|
||||
{
|
||||
// Multi-column detected. Pre-mask lines that span the full page
|
||||
// width (titles, section headers, footers). These multi-item lines
|
||||
// would otherwise be split across column buckets, corrupting
|
||||
// newspaper detection and reading order.
|
||||
let spanning_mask = identify_spanning_lines(&page_items, &columns);
|
||||
let spanning_mask = identify_spanning_lines(&page_items, columns);
|
||||
let premasked_count = spanning_mask.iter().filter(|&&m| m).count();
|
||||
if premasked_count > 0 {
|
||||
debug!(
|
||||
@@ -2245,7 +2368,7 @@ fn group_into_lines_with_thresholds_and_regions_impl(
|
||||
let mut column_items: Vec<TextItem> = Vec::new();
|
||||
|
||||
for (i, item) in page_items.into_iter().enumerate() {
|
||||
if spanning_mask[i] || spans_multiple_columns(&item, &columns) {
|
||||
if spanning_mask[i] || spans_multiple_columns(&item, columns) {
|
||||
spanning_items.push(item);
|
||||
} else {
|
||||
column_items.push(item);
|
||||
@@ -2309,7 +2432,9 @@ fn group_into_lines_with_thresholds_and_regions_impl(
|
||||
// Process spanning items as their own group
|
||||
let spanning_lines = group_single_column(spanning_items, adaptive_threshold);
|
||||
|
||||
let is_newspaper = is_newspaper_layout(&per_column_lines, &columns);
|
||||
let is_newspaper = band_validated
|
||||
|| is_newspaper_layout(&per_column_lines, columns)
|
||||
|| short_prose_columns(&per_column_lines, columns);
|
||||
debug!(
|
||||
"page {}: layout={}",
|
||||
page,
|
||||
@@ -2324,6 +2449,16 @@ fn group_into_lines_with_thresholds_and_regions_impl(
|
||||
let mut core_columns: Vec<Vec<TextLine>> = Vec::new();
|
||||
let mut col_stragglers: Vec<Vec<TextLine>> = Vec::new();
|
||||
for col in per_column_lines {
|
||||
if band_validated {
|
||||
// Banded regions are already Y-cohesive — and a
|
||||
// merged band deliberately flows across a figure
|
||||
// gap, which straggler-splitting would undo by
|
||||
// pushing the upper half into the Y-sorted "above"
|
||||
// bucket where the columns re-interleave.
|
||||
core_columns.push(col);
|
||||
col_stragglers.push(Vec::new());
|
||||
continue;
|
||||
}
|
||||
let (core, stragglers) = split_column_stragglers(col);
|
||||
core_columns.push(core);
|
||||
col_stragglers.push(stragglers);
|
||||
@@ -2416,6 +2551,321 @@ fn group_into_lines_with_thresholds_and_regions_impl(
|
||||
all_lines
|
||||
}
|
||||
|
||||
/// One horizontal slice of a page produced by [`split_into_y_bands`]. Items
|
||||
/// belong to the band whose `(y_bottom, y_top]` range contains their baseline.
|
||||
#[derive(Debug, Clone, Copy)]
|
||||
struct YBand {
|
||||
y_top: f32,
|
||||
y_bottom: f32,
|
||||
}
|
||||
|
||||
impl YBand {
|
||||
fn contains(&self, y: f32) -> bool {
|
||||
y <= self.y_top && y > self.y_bottom
|
||||
}
|
||||
}
|
||||
|
||||
/// Split a page into horizontal bands at full-width whitespace gaps.
|
||||
///
|
||||
/// Occupancy is measured from non-wide items only: wide spanning items
|
||||
/// (headlines, captions) sit inside the very gaps this looks for and would
|
||||
/// otherwise weld independent bands together. Cut positions are gap
|
||||
/// midpoints; the first and last band extend to infinity so every item on
|
||||
/// the page lands in exactly one band.
|
||||
///
|
||||
/// Returns the bands top-first plus the `(gap_top, gap_bottom)` whitespace
|
||||
/// extent between each consecutive pair, or empty vectors when the page has
|
||||
/// no qualifying gap.
|
||||
fn split_into_y_bands(detection_items: &[TextItem]) -> (Vec<YBand>, Vec<(f32, f32)>) {
|
||||
// A band gap must be clearly larger than ordinary line spacing: at least
|
||||
// this floor, and at least LEADING_FACTOR times the page's median leading
|
||||
// (measured between glyph boxes, so ordinary leading contributes only its
|
||||
// whitespace portion).
|
||||
const MIN_GAP: f32 = 14.0;
|
||||
const LEADING_FACTOR: f32 = 1.4;
|
||||
// Same spanning-item threshold as the column histogram's exclusion rule.
|
||||
const WIDE_FRACTION: f32 = 0.6;
|
||||
|
||||
// Text items only throughout: an image placeholder is the very figure
|
||||
// whose whitespace the cuts trace, so its box must not fill a gap (nor
|
||||
// its edges set the wide-item scale).
|
||||
let text_items: Vec<&TextItem> = detection_items
|
||||
.iter()
|
||||
.filter(|i| crate::extractor::is_text_layout_item(i))
|
||||
.collect();
|
||||
|
||||
let (x_min, x_max) = text_items
|
||||
.iter()
|
||||
.fold((f32::INFINITY, f32::NEG_INFINITY), |(lo, hi), i| {
|
||||
(lo.min(i.x), hi.max(i.x + effective_width(i)))
|
||||
});
|
||||
if !(x_max - x_min).is_finite() {
|
||||
return (vec![], vec![]);
|
||||
}
|
||||
let wide_threshold = (x_max - x_min) * WIDE_FRACTION;
|
||||
|
||||
// (top, bottom) glyph-box intervals of non-wide items, sorted top-first.
|
||||
//
|
||||
// The width test is deliberately per-item, so a separator emitted as
|
||||
// several narrow word runs stays in occupancy and can suppress a cut (a
|
||||
// missed engagement, never a corruption). Assembling same-baseline
|
||||
// fragments into runs before the test was tried and measured: word-gap
|
||||
// and gutter-gap distributions overlap in real documents, so assembled
|
||||
// runs fused the two columns of narrow-guttered pages into page-wide
|
||||
// "lines", emptied the occupancy, and disengaged banding on exactly the
|
||||
// pages it rescues — a measured reading-order regression with no
|
||||
// measured win. Revisit only with a discriminator stronger than line
|
||||
// geometry.
|
||||
let mut intervals: Vec<(f32, f32)> = text_items
|
||||
.iter()
|
||||
.filter(|i| effective_width(i) <= wide_threshold)
|
||||
.map(|i| (i.y + i.height.max(0.0), i.y))
|
||||
.filter(|(top, bottom)| top.is_finite() && bottom.is_finite())
|
||||
.collect();
|
||||
if intervals.len() < 10 {
|
||||
return (vec![], vec![]);
|
||||
}
|
||||
intervals.sort_by(|a, b| b.0.total_cmp(&a.0));
|
||||
|
||||
let mut baselines: Vec<f32> = intervals.iter().map(|&(_, bottom)| bottom).collect();
|
||||
baselines.sort_by(|a, b| b.total_cmp(a));
|
||||
let mut steps: Vec<f32> = baselines
|
||||
.windows(2)
|
||||
.map(|w| w[0] - w[1])
|
||||
.filter(|d| *d > 1.0)
|
||||
.collect();
|
||||
steps.sort_by(|a, b| a.total_cmp(b));
|
||||
let median_leading = steps.get(steps.len() / 2).copied().unwrap_or(12.0);
|
||||
let gap_threshold = (median_leading * LEADING_FACTOR).max(MIN_GAP);
|
||||
|
||||
// Sweep top-to-bottom, cutting where occupancy leaves a full-width gap.
|
||||
let mut cuts: Vec<(f32, f32)> = Vec::new();
|
||||
let mut largest_rejected = 0.0f32;
|
||||
let mut run_bottom = intervals[0].1;
|
||||
for &(top, bottom) in &intervals[1..] {
|
||||
if run_bottom - top >= gap_threshold {
|
||||
cuts.push((run_bottom, top));
|
||||
run_bottom = bottom;
|
||||
} else {
|
||||
largest_rejected = largest_rejected.max(run_bottom - top);
|
||||
run_bottom = run_bottom.min(bottom);
|
||||
}
|
||||
}
|
||||
log::trace!(
|
||||
"y-bands: {} intervals, leading {:.1}, threshold {:.1}, {} cuts, largest rejected gap {:.1}",
|
||||
intervals.len(),
|
||||
median_leading,
|
||||
gap_threshold,
|
||||
cuts.len(),
|
||||
largest_rejected
|
||||
);
|
||||
if cuts.is_empty() {
|
||||
return (vec![], vec![]);
|
||||
}
|
||||
|
||||
let mut bands = Vec::with_capacity(cuts.len() + 1);
|
||||
let mut top = f32::INFINITY;
|
||||
for &(gap_top, gap_bottom) in &cuts {
|
||||
bands.push(YBand {
|
||||
y_top: top,
|
||||
y_bottom: (gap_top + gap_bottom) / 2.0,
|
||||
});
|
||||
top = (gap_top + gap_bottom) / 2.0;
|
||||
}
|
||||
bands.push(YBand {
|
||||
y_top: top,
|
||||
y_bottom: f32::NEG_INFINITY,
|
||||
});
|
||||
(bands, cuts)
|
||||
}
|
||||
|
||||
/// Two column sets match when they have the same multi-column count and each
|
||||
/// gutter midpoint lies within tolerance of its counterpart.
|
||||
fn columns_match(a: &[ColumnRegion], b: &[ColumnRegion]) -> bool {
|
||||
const GUTTER_TOLERANCE: f32 = 25.0;
|
||||
if a.len() != b.len() || a.len() < 2 {
|
||||
return false;
|
||||
}
|
||||
std::iter::zip(a.windows(2), b.windows(2)).all(|(wa, wb)| {
|
||||
let gutter_a = (wa[0].x_max + wa[1].x_min) / 2.0;
|
||||
let gutter_b = (wb[0].x_max + wb[1].x_min) / 2.0;
|
||||
(gutter_a - gutter_b).abs() <= GUTTER_TOLERANCE
|
||||
})
|
||||
}
|
||||
|
||||
// NOTE on merge unions: `detect_columns` returns contiguous partitions —
|
||||
// adjacent regions share their boundary coordinate — so merging two bands
|
||||
// whose boundaries disagree produces union partitions that overlap by the
|
||||
// disagreement. That zone is bounded by GUTTER_TOLERANCE, items inside it
|
||||
// are split by greatest-overlap bucketing proportionally, and a "reject
|
||||
// overlapping unions" guard is unimplementable against partitions: with
|
||||
// shared boundaries it degenerates to exact-equality matching and rejects
|
||||
// every legitimate merge.
|
||||
|
||||
/// Band-segmented page layout: the region-segmentation path used when the
|
||||
/// page-level column model cannot represent the page.
|
||||
///
|
||||
/// Splits the page into horizontal bands at full-width whitespace gaps, runs
|
||||
/// column detection independently inside each band, and re-merges consecutive
|
||||
/// bands whose column geometry matches across an empty gap (aligned
|
||||
/// whitespace inside one continuous flow — a figure float — splits occupancy
|
||||
/// without changing the layout, and reading must continue down the columns
|
||||
/// rather than restart per band; a wide separator in the gap means
|
||||
/// independent stories, which stay separate bands).
|
||||
///
|
||||
/// Engages only when at least one band yields prose-validated columns whose
|
||||
/// count contradicts the page-level structure — a multi-column band on a page
|
||||
/// that read as single-column, or a band whose column count differs from the
|
||||
/// page-level count (whose projection would weave that band's columns into
|
||||
/// the wrong buckets). Gutter jitter alone never engages. Otherwise returns
|
||||
/// `None` and the caller keeps the page-level ordering, so pages the flat
|
||||
/// column model already explains are untouched.
|
||||
fn try_banded_layout(
|
||||
page_items: &[TextItem],
|
||||
detection_items: &[TextItem],
|
||||
page_columns: &[ColumnRegion],
|
||||
page: u32,
|
||||
page_has_table: bool,
|
||||
adaptive_threshold: f32,
|
||||
) -> Option<Vec<TextLine>> {
|
||||
// Below this the page is too sparse for per-band column evidence.
|
||||
const MIN_ITEMS: usize = 40;
|
||||
|
||||
if page_has_table || detection_items.len() < MIN_ITEMS {
|
||||
return None;
|
||||
}
|
||||
// Band membership is a baseline comparison, so an item with non-finite Y
|
||||
// would fall through every band and silently vanish from the output.
|
||||
if page_items.iter().any(|i| !i.y.is_finite()) {
|
||||
return None;
|
||||
}
|
||||
let (bands, gaps) = split_into_y_bands(detection_items);
|
||||
if bands.len() < 2 {
|
||||
return None;
|
||||
}
|
||||
|
||||
struct BandPlan {
|
||||
band: YBand,
|
||||
columns: Vec<ColumnRegion>,
|
||||
// The founding band's columns, untouched by merge widening. Merge
|
||||
// candidates are compared against these: the widened union's gutter
|
||||
// is the intersection of its constituents' gutters, and across a
|
||||
// chain of one-directionally drifting bands that intersection can
|
||||
// walk past GUTTER_TOLERANCE, rejecting a band identical to the
|
||||
// founder. The run's column system is defined by its first band.
|
||||
anchor_columns: Vec<ColumnRegion>,
|
||||
}
|
||||
|
||||
let mut plans: Vec<BandPlan> = Vec::new();
|
||||
for band in bands {
|
||||
let band_detection: Vec<TextItem> = detection_items
|
||||
.iter()
|
||||
.filter(|i| band.contains(i.y))
|
||||
.cloned()
|
||||
.collect();
|
||||
let columns = detect_columns(&band_detection, page, false);
|
||||
let refs: Vec<&TextItem> = band_detection.iter().collect();
|
||||
let columns = if columns.len() > 1 && columns_have_prose(&columns, &refs) {
|
||||
columns
|
||||
} else {
|
||||
vec![]
|
||||
};
|
||||
plans.push(BandPlan {
|
||||
band,
|
||||
anchor_columns: columns.clone(),
|
||||
columns,
|
||||
});
|
||||
}
|
||||
|
||||
let page_count = page_columns.len().max(1);
|
||||
if !plans
|
||||
.iter()
|
||||
.any(|p| p.columns.len() > 1 && p.columns.len() != page_count)
|
||||
{
|
||||
return None;
|
||||
}
|
||||
|
||||
// Sorted baselines let each gap-content probe below run in O(log n)
|
||||
// instead of rescanning every item per band pair. Text items only: an
|
||||
// image placeholder in the gap IS the figure float whose flow-through
|
||||
// the merge exists for, so it must not read as separator content.
|
||||
let mut sorted_ys: Vec<f32> = page_items
|
||||
.iter()
|
||||
.filter(|i| crate::extractor::is_text_layout_item(i))
|
||||
.map(|i| i.y)
|
||||
.collect();
|
||||
sorted_ys.sort_by(|a, b| b.total_cmp(a));
|
||||
let gap_has_content = |gap: (f32, f32)| -> bool {
|
||||
let first_below_top = sorted_ys.partition_point(|&y| y >= gap.0);
|
||||
first_below_top < sorted_ys.len() && sorted_ys[first_below_top] > gap.1
|
||||
};
|
||||
|
||||
let mut merged: Vec<BandPlan> = Vec::new();
|
||||
for (idx, plan) in plans.into_iter().enumerate() {
|
||||
if idx > 0 {
|
||||
if let Some(prev) = merged.last_mut() {
|
||||
if columns_match(&prev.anchor_columns, &plan.columns)
|
||||
&& !gap_has_content(gaps[idx - 1])
|
||||
{
|
||||
prev.band.y_bottom = plan.band.y_bottom;
|
||||
for (pc, nc) in prev.columns.iter_mut().zip(&plan.columns) {
|
||||
pc.x_min = pc.x_min.min(nc.x_min);
|
||||
pc.x_max = pc.x_max.max(nc.x_max);
|
||||
}
|
||||
continue;
|
||||
}
|
||||
}
|
||||
}
|
||||
merged.push(plan);
|
||||
}
|
||||
|
||||
debug!(
|
||||
"page {}: banded layout: {} bands ({} multi-column)",
|
||||
page,
|
||||
merged.len(),
|
||||
merged.iter().filter(|p| p.columns.len() > 1).count()
|
||||
);
|
||||
|
||||
// Assign every item to its band in one pass: bands are top-first with
|
||||
// strictly decreasing bottoms, so the first band whose bottom lies below
|
||||
// the item's baseline is its home (same strict-bottom rule as
|
||||
// `YBand::contains`).
|
||||
let mut band_items: Vec<Vec<TextItem>> = (0..merged.len()).map(|_| Vec::new()).collect();
|
||||
for item in page_items {
|
||||
let idx = merged.partition_point(|p| p.band.y_bottom >= item.y);
|
||||
band_items[idx.min(merged.len() - 1)].push(item.clone());
|
||||
}
|
||||
|
||||
let mut out = Vec::new();
|
||||
for (plan, items) in merged.iter().zip(band_items) {
|
||||
if items.is_empty() {
|
||||
continue;
|
||||
}
|
||||
if plan.columns.len() > 1 {
|
||||
out.extend(order_validated_band(
|
||||
items,
|
||||
&plan.columns,
|
||||
adaptive_threshold,
|
||||
page,
|
||||
));
|
||||
} else if page_count > 1 {
|
||||
// No validated band structure of its own: order with the
|
||||
// page-level columns so a dense band that merely failed the
|
||||
// prose gate keeps the page's column reading instead of
|
||||
// regressing to Y-interleave.
|
||||
out.extend(order_multi_column_region(
|
||||
items,
|
||||
page_columns,
|
||||
adaptive_threshold,
|
||||
page,
|
||||
));
|
||||
} else {
|
||||
out.extend(group_single_column(items, adaptive_threshold));
|
||||
}
|
||||
}
|
||||
Some(out)
|
||||
}
|
||||
|
||||
/// Determine if Y-sorting should be used instead of stream order.
|
||||
/// Returns true if the stream order appears chaotic (items jump around in Y position).
|
||||
fn should_use_y_sorting(items: &[TextItem]) -> bool {
|
||||
@@ -2611,6 +3061,312 @@ mod tests {
|
||||
}
|
||||
}
|
||||
|
||||
/// A dense block of single-column prose lines at `x` starting from
|
||||
/// `y_top`, one 32-char item per line, 14pt leading.
|
||||
fn prose_block(x: f32, y_top: f32, lines: usize, tag: &str) -> Vec<TextItem> {
|
||||
(0..lines)
|
||||
.map(|i| {
|
||||
make_item(
|
||||
1,
|
||||
x,
|
||||
y_top - i as f32 * 14.0,
|
||||
&format!("{tag}{i:02} word word word word word"),
|
||||
)
|
||||
})
|
||||
.collect()
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn y_bands_split_at_full_width_gap() {
|
||||
// Two dense two-column blocks separated by ~50pt of whitespace →
|
||||
// one cut. (Two columns keep individual items under the wide-item
|
||||
// threshold, as on a real page.)
|
||||
let mut items = two_column_band(700.0, 12, "TA", "TB");
|
||||
items.extend(two_column_band(480.0, 12, "BA", "BB"));
|
||||
let (bands, gaps) = split_into_y_bands(&items);
|
||||
assert_eq!(bands.len(), 2, "one full-width gap must yield two bands");
|
||||
assert_eq!(gaps.len(), 1);
|
||||
// The cut must land between the blocks (below 546, above 492).
|
||||
assert!(bands[0].y_bottom < 546.0 && bands[0].y_bottom > 492.0);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn y_bands_ignore_wide_separator_inside_gap() {
|
||||
// A page-wide headline inside the whitespace gap must not weld the
|
||||
// bands together: wide items are excluded from occupancy.
|
||||
let mut items = two_column_band(700.0, 12, "TA", "TB");
|
||||
items.extend(two_column_band(480.0, 12, "BA", "BB"));
|
||||
// ~80 chars * 6pt = 480pt wide on a ~450pt-wide page → wide item
|
||||
items.push(make_item(1, 50.0, 520.0, &"m".repeat(80)));
|
||||
let (bands, _) = split_into_y_bands(&items);
|
||||
assert_eq!(bands.len(), 2, "wide separator must not suppress the cut");
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn y_bands_no_cut_in_continuous_text() {
|
||||
let items = two_column_band(700.0, 30, "LL", "RR");
|
||||
let (bands, _) = split_into_y_bands(&items);
|
||||
assert!(bands.is_empty(), "uniform leading must produce no bands");
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn columns_match_requires_count_and_gutter() {
|
||||
let two = |g0: f32| {
|
||||
vec![
|
||||
ColumnRegion {
|
||||
x_min: 0.0,
|
||||
x_max: g0,
|
||||
},
|
||||
ColumnRegion {
|
||||
x_min: g0 + 20.0,
|
||||
x_max: 500.0,
|
||||
},
|
||||
]
|
||||
};
|
||||
assert!(columns_match(&two(240.0), &two(250.0)));
|
||||
assert!(!columns_match(&two(240.0), &two(320.0)));
|
||||
assert!(!columns_match(&two(240.0), &[]));
|
||||
}
|
||||
|
||||
/// Two-column band: `lines` prose lines per column, columns at x=50 and
|
||||
/// x=310, ~190pt wide each.
|
||||
fn two_column_band(y_top: f32, lines: usize, left_tag: &str, right_tag: &str) -> Vec<TextItem> {
|
||||
let mut items = Vec::new();
|
||||
for i in 0..lines {
|
||||
let y = y_top - i as f32 * 14.0;
|
||||
items.push(make_item(
|
||||
1,
|
||||
50.0,
|
||||
y,
|
||||
&format!("{left_tag}{i:02} {}", "x".repeat(26)),
|
||||
));
|
||||
items.push(make_item(
|
||||
1,
|
||||
310.0,
|
||||
y,
|
||||
&format!("{right_tag}{i:02} {}", "x".repeat(26)),
|
||||
));
|
||||
}
|
||||
items
|
||||
}
|
||||
|
||||
fn joined_order(lines: &[TextLine]) -> String {
|
||||
lines
|
||||
.iter()
|
||||
.flat_map(|l| l.items.iter())
|
||||
.map(|i| i.text.split(' ').next().unwrap_or("").to_string())
|
||||
.collect::<Vec<_>>()
|
||||
.join(",")
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn banded_layout_orders_mismatched_band_sequentially() {
|
||||
// Top band: two prose columns. Bottom band: single narrow block.
|
||||
// The page-level model (single column) cannot represent this; the
|
||||
// banded path must read left column, right column, then the bottom.
|
||||
let mut items = two_column_band(700.0, 12, "L", "R");
|
||||
items.extend(prose_block(150.0, 480.0, 16, "B"));
|
||||
let lines = try_banded_layout(&items, &items, &[], 1, false, 0.10)
|
||||
.expect("contradicting band evidence must engage");
|
||||
let order = joined_order(&lines);
|
||||
let li = order.find("L00").unwrap();
|
||||
let ri = order.find("R00").unwrap();
|
||||
let bi = order.find("B0").unwrap();
|
||||
assert!(li < ri && ri < bi, "expected L*, R*, B* order, got {order}");
|
||||
assert!(
|
||||
order.find("L11").unwrap() < ri,
|
||||
"left column must complete before right column starts: {order}"
|
||||
);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn banded_layout_merges_matching_bands_across_empty_gap() {
|
||||
// Two two-column bands with identical gutters and nothing in the
|
||||
// gap: a figure float inside one continuous flow. Reading must run
|
||||
// each column through both bands, not restart per band.
|
||||
let mut items = two_column_band(700.0, 12, "LA", "RA");
|
||||
items.extend(two_column_band(460.0, 12, "LB", "RB"));
|
||||
let lines = try_banded_layout(&items, &items, &[], 1, false, 0.10)
|
||||
.expect("multi-column bands on a single-column page must engage");
|
||||
let order = joined_order(&lines);
|
||||
assert!(
|
||||
order.find("LB00").unwrap() < order.find("RA00").unwrap(),
|
||||
"columns must flow through the empty gap (LB before RA): {order}"
|
||||
);
|
||||
}
|
||||
|
||||
/// Two-column band with a controllable gutter: the left column runs
|
||||
/// `50..(50 + 6·left_chars)`, the right column starts at `right_x`.
|
||||
/// The 6-char tag prefix ("LA00 x") is included in `left_chars`, so a
|
||||
/// band's left-column width — and with it its gutter — is exact.
|
||||
fn gutter_band(
|
||||
items: &mut Vec<TextItem>,
|
||||
y_top: f32,
|
||||
left_chars: usize,
|
||||
right_x: f32,
|
||||
tag: &str,
|
||||
) {
|
||||
for i in 0..12 {
|
||||
let y = y_top - i as f32 * 14.0;
|
||||
items.push(make_item(
|
||||
1,
|
||||
50.0,
|
||||
y,
|
||||
&format!("L{tag}{i:02} {}", "x".repeat(left_chars - 6)),
|
||||
));
|
||||
items.push(make_item(
|
||||
1,
|
||||
right_x,
|
||||
y,
|
||||
&format!("R{tag}{i:02} {}", "x".repeat(29)),
|
||||
));
|
||||
}
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn banded_layout_merge_anchors_on_founding_band() {
|
||||
// Invariant lock (not a differential regression test — the pre-fix
|
||||
// union also accepts this shape, since one merge keeps the union
|
||||
// gutter within tolerance of both constituents): the founder, a
|
||||
// band whose gutter sits ~23pt right of it, and a band identical to
|
||||
// the founder must all flow as one run. The differential coverage
|
||||
// for the anchor rule is banded_layout_rejects_creeping_drift.
|
||||
let mut items = Vec::new();
|
||||
gutter_band(&mut items, 700.0, 38, 330.0, "A"); // gutter mid ~304
|
||||
gutter_band(&mut items, 460.0, 42, 352.0, "B"); // mid ~327 (+23)
|
||||
gutter_band(&mut items, 220.0, 38, 330.0, "C"); // identical to founder
|
||||
let lines = try_banded_layout(&items, &items, &[], 1, false, 0.10)
|
||||
.expect("multi-column bands on a single-column page must engage");
|
||||
let order = joined_order(&lines);
|
||||
assert!(
|
||||
order.find("LC00").unwrap() < order.find("RA00").unwrap(),
|
||||
"founder-identical band must stay in the founder's run \
|
||||
(its left column reads before any right column): {order}"
|
||||
);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn banded_layout_rejects_creeping_drift() {
|
||||
// The genuine drift regression: band C's gutter (mid ~340) is
|
||||
// within tolerance of the moving union after A+B merge (mid ~316,
|
||||
// the intersection of A's and B's gutters) but 36pt from the
|
||||
// founder. Pre-anchor code admitted C into the run; matching
|
||||
// against the founder's raw columns must reject it, so C reads as
|
||||
// its own sequential band after the A+B run completes.
|
||||
let mut items = Vec::new();
|
||||
gutter_band(&mut items, 700.0, 38, 330.0, "A"); // gutter mid ~304
|
||||
gutter_band(&mut items, 460.0, 42, 352.0, "B"); // mid ~327 (+23)
|
||||
gutter_band(&mut items, 220.0, 45, 360.0, "C"); // mid ~340 (+36)
|
||||
let lines = try_banded_layout(&items, &items, &[], 1, false, 0.10)
|
||||
.expect("multi-column bands on a single-column page must engage");
|
||||
let order = joined_order(&lines);
|
||||
assert!(
|
||||
order.find("RA00").unwrap() < order.find("LC00").unwrap(),
|
||||
"a band beyond tolerance of the founder must not join its run: {order}"
|
||||
);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn banded_layout_merges_across_gap_holding_figure_placeholder() {
|
||||
// The gap between two matching bands holds an image placeholder —
|
||||
// that IS the figure float the merge exists for, so the columns
|
||||
// must still flow through it.
|
||||
let mut items = two_column_band(700.0, 12, "LA", "RA");
|
||||
items.extend(two_column_band(460.0, 12, "LB", "RB"));
|
||||
let mut figure = make_item(1, 100.0, 505.0, "[img]");
|
||||
figure.item_type = ItemType::Image;
|
||||
items.push(figure);
|
||||
let lines = try_banded_layout(&items, &items, &[], 1, false, 0.10)
|
||||
.expect("multi-column bands on a single-column page must engage");
|
||||
let order = joined_order(&lines);
|
||||
assert!(
|
||||
order.find("LB00").unwrap() < order.find("RA00").unwrap(),
|
||||
"figure placeholder in the gap must not block the merge: {order}"
|
||||
);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn banded_layout_keeps_bands_apart_across_separator() {
|
||||
// Same two bands, but a page-wide headline sits in the gap:
|
||||
// independent stories, so the top band completes before the bottom.
|
||||
let mut items = two_column_band(700.0, 12, "LA", "RA");
|
||||
items.extend(two_column_band(460.0, 12, "LB", "RB"));
|
||||
items.push(make_item(1, 50.0, 505.0, &"m".repeat(80)));
|
||||
let lines = try_banded_layout(&items, &items, &[], 1, false, 0.10)
|
||||
.expect("multi-column bands on a single-column page must engage");
|
||||
let order = joined_order(&lines);
|
||||
assert!(
|
||||
order.find("RA00").unwrap() < order.find("LB00").unwrap(),
|
||||
"separator must keep bands sequential (RA before LB): {order}"
|
||||
);
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn short_prose_columns_read_newspaper() {
|
||||
// Three balanced columns of 8 full-width prose lines each: below the
|
||||
// 15-line floor, but every line fills its column, so these are
|
||||
// independent text flows, not table rows.
|
||||
let cols: Vec<ColumnRegion> = (0..3)
|
||||
.map(|c| ColumnRegion {
|
||||
x_min: c as f32 * 200.0,
|
||||
x_max: c as f32 * 200.0 + 190.0,
|
||||
})
|
||||
.collect();
|
||||
let per_column: Vec<Vec<TextLine>> = (0..3)
|
||||
.map(|c| {
|
||||
(0..8)
|
||||
.map(|i| {
|
||||
let y = 700.0 - i as f32 * 14.0;
|
||||
let item = make_item(1, c as f32 * 200.0 + 5.0, y, &"m".repeat(30));
|
||||
TextLine {
|
||||
y,
|
||||
page: 1,
|
||||
adaptive_threshold: 0.10,
|
||||
items: vec![item],
|
||||
}
|
||||
})
|
||||
.collect()
|
||||
})
|
||||
.collect();
|
||||
assert!(short_prose_columns(&per_column, &cols));
|
||||
// The table pipeline's veto stays untouched: the shared newspaper
|
||||
// predicate itself must keep rejecting this shape.
|
||||
assert!(!is_newspaper_layout(&per_column, &cols));
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn short_cell_columns_stay_tabular() {
|
||||
// Term/description shape: the left column's lines are short cells.
|
||||
// The all-columns prose requirement must keep row-wise reading.
|
||||
let cols = vec![
|
||||
ColumnRegion {
|
||||
x_min: 0.0,
|
||||
x_max: 190.0,
|
||||
},
|
||||
ColumnRegion {
|
||||
x_min: 200.0,
|
||||
x_max: 390.0,
|
||||
},
|
||||
];
|
||||
let make_col = |x: f32, text: &str| -> Vec<TextLine> {
|
||||
(0..8)
|
||||
.map(|i| {
|
||||
let y = 700.0 - i as f32 * 14.0;
|
||||
let item = make_item(1, x, y, text);
|
||||
TextLine {
|
||||
y,
|
||||
page: 1,
|
||||
adaptive_threshold: 0.10,
|
||||
items: vec![item],
|
||||
}
|
||||
})
|
||||
.collect()
|
||||
};
|
||||
let per_column = vec![make_col(5.0, "term"), make_col(205.0, &"m".repeat(30))];
|
||||
assert!(!short_prose_columns(&per_column, &cols));
|
||||
assert!(!is_newspaper_layout(&per_column, &cols));
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn prose_gate_accepts_figure_diluted_column_via_run() {
|
||||
// A prose column hosting a figure: 9 consecutive full-width lines
|
||||
|
||||
File diff suppressed because it is too large
Load Diff
+48
-8
@@ -9,6 +9,7 @@
|
||||
pub(crate) mod analysis;
|
||||
mod classify;
|
||||
mod convert;
|
||||
mod furniture;
|
||||
mod heading;
|
||||
mod postprocess;
|
||||
mod preprocess;
|
||||
@@ -634,7 +635,12 @@ fn is_parallel_prose_table(table: &crate::tables::Table) -> bool {
|
||||
}
|
||||
}
|
||||
|
||||
let is_parallel = !has_compact_header
|
||||
// A compact header row is evidence for a real table — unless cross-row
|
||||
// prose continuations outnumber the rows, which no genuine table
|
||||
// produces: the "header" is then just two short line fragments at the
|
||||
// top of parallel prose columns.
|
||||
let header_blocks = has_compact_header && continuation_fragments <= table.cells.len();
|
||||
let is_parallel = !header_blocks
|
||||
&& non_empty >= 5
|
||||
// Independent prose columns have asynchronous line/paragraph breaks;
|
||||
// a fully populated grid is positive evidence for a real descriptive
|
||||
@@ -1149,7 +1155,7 @@ pub(crate) fn strip_repeated_header_footer_lines(
|
||||
lines: Vec<crate::types::TextLine>,
|
||||
page_count: u32,
|
||||
) -> Vec<crate::types::TextLine> {
|
||||
preprocess::strip_repeated_lines(lines, page_count)
|
||||
furniture::strip_header_footer_lines(lines, page_count)
|
||||
}
|
||||
|
||||
/// Convert positioned text items to markdown with structure detection
|
||||
@@ -1374,7 +1380,6 @@ pub(crate) fn to_markdown_from_items_with_rects_and_lines(
|
||||
chart_page_prose_column_split(&page_layout_items)
|
||||
.filter(|&split_x| chart_spans_prose_split(region, split_x))
|
||||
});
|
||||
let chart_prose_columns = chart_prose_split.is_some();
|
||||
|
||||
// Check for side-by-side table layout using the original items. Sparse
|
||||
// numeric cells need table context before they can be distinguished
|
||||
@@ -1615,10 +1620,16 @@ pub(crate) fn to_markdown_from_items_with_rects_and_lines(
|
||||
if subset_items.len() < min_items {
|
||||
return;
|
||||
}
|
||||
// Keep body-font detection available on chart pages: a real
|
||||
// table can share the prose anchors. Reject only candidates
|
||||
// whose cells prove they are parallel prose fragments.
|
||||
let reject_parallel_prose = chart_prose_columns && !was_split;
|
||||
// Reject candidates whose cells prove they are parallel
|
||||
// prose fragments — the shape produced when the body-font
|
||||
// pass projects a multi-column text page onto one table
|
||||
// grid (two-column reference sections are the classic
|
||||
// case). The check needs internal transition evidence
|
||||
// (unterminated cells flowing into lowercase starts in
|
||||
// the same column), so genuine tables with long cells
|
||||
// pass. Band-split retries stay exempt: they exist for
|
||||
// tables that only assemble after recombining bands.
|
||||
let reject_parallel_prose = !was_split;
|
||||
let tables = detect_tables_with_page_width(
|
||||
subset_items,
|
||||
base_size,
|
||||
@@ -2106,7 +2117,7 @@ pub(crate) fn to_markdown_from_items_with_rects_and_lines(
|
||||
|
||||
// Strip repeated headers/footers before conversion
|
||||
let lines = if options.strip_headers_footers {
|
||||
preprocess::strip_repeated_lines(lines, document_page_count)
|
||||
furniture::strip_header_footer_lines(lines, document_page_count)
|
||||
} else {
|
||||
lines
|
||||
};
|
||||
@@ -2673,6 +2684,35 @@ mod tests {
|
||||
);
|
||||
assert!(!is_parallel_prose_table(&data));
|
||||
|
||||
// A compact header row atop parallel prose columns: cross-row prose
|
||||
// continuations outnumber the rows, so the header cannot save the
|
||||
// candidate — this is page prose with two short fragments on top.
|
||||
let headed_parallel_prose = crate::tables::Table::new(
|
||||
vec![90.0, 340.0],
|
||||
vec![340.0, 320.0, 300.0, 280.0, 260.0],
|
||||
vec![
|
||||
vec!["June 2023".into(), "Page 5".into()],
|
||||
vec![
|
||||
"the committee reviewed the proposal and decided that the".into(),
|
||||
"funding for the second phase would continue subject to the".into(),
|
||||
],
|
||||
vec![
|
||||
"implementation schedule should be extended by another".into(),
|
||||
"quarterly reviews established during the first phase of the".into(),
|
||||
],
|
||||
vec![
|
||||
"six months to accommodate the revised procurement rules".into(),
|
||||
"".into(),
|
||||
],
|
||||
vec![
|
||||
"adopted at the previous meeting of the governing board".into(),
|
||||
"participating institutions across the partner regions".into(),
|
||||
],
|
||||
],
|
||||
(0..10).collect(),
|
||||
);
|
||||
assert!(is_parallel_prose_table(&headed_parallel_prose));
|
||||
|
||||
let headed_text_table = crate::tables::Table::new(
|
||||
vec![90.0, 340.0],
|
||||
vec![320.0, 300.0, 280.0],
|
||||
|
||||
+1
-384
@@ -1,6 +1,6 @@
|
||||
//! Line preprocessing: heading merging, drop cap handling, and repeated line removal.
|
||||
|
||||
use std::collections::{HashMap, HashSet};
|
||||
use std::collections::HashMap;
|
||||
|
||||
use crate::structure_tree::StructRole;
|
||||
use crate::types::{TextItem, TextLine};
|
||||
@@ -229,342 +229,6 @@ pub(crate) fn merge_drop_caps(lines: Vec<TextLine>, base_size: f32) -> Vec<TextL
|
||||
result
|
||||
}
|
||||
|
||||
/// Normalize whitespace in a string for comparison: trim and collapse internal runs of whitespace.
|
||||
fn normalize_whitespace(s: &str) -> String {
|
||||
s.split_whitespace().collect::<Vec<_>>().join(" ")
|
||||
}
|
||||
|
||||
/// Normalize text for frequency comparison: collapse whitespace and strip leading/trailing
|
||||
/// digit sequences (page numbers). E.g., "Chapter 3 — Page 5" and "Chapter 3 — Page 6"
|
||||
/// both normalize to "Chapter 3 — Page".
|
||||
fn normalize_for_comparison(s: &str) -> String {
|
||||
let ws = normalize_whitespace(s);
|
||||
let trimmed = ws
|
||||
.trim_start_matches(|c: char| c.is_ascii_digit())
|
||||
.trim_start();
|
||||
let trimmed = trimmed
|
||||
.trim_end_matches(|c: char| c.is_ascii_digit())
|
||||
.trim_end();
|
||||
trimmed.to_string()
|
||||
}
|
||||
|
||||
/// Returns true if the line looks like a list item or heading (should not be stripped).
|
||||
fn is_structural_line(text: &str) -> bool {
|
||||
let t = text.trim_start();
|
||||
t.starts_with('#')
|
||||
|| t.starts_with("- ")
|
||||
|| t.starts_with("* ")
|
||||
|| t.starts_with("• ")
|
||||
|| t.chars()
|
||||
.next()
|
||||
.map(|c| c.is_ascii_digit())
|
||||
.unwrap_or(false)
|
||||
&& (t.contains(". ") || t.contains(") "))
|
||||
}
|
||||
|
||||
/// Returns true if a line consists entirely of a single repeated character
|
||||
/// (e.g., "----------", "**************", "============").
|
||||
fn is_decorative_separator(text: &str) -> bool {
|
||||
let mut chars = text.chars();
|
||||
let first = match chars.next() {
|
||||
Some(c) => c,
|
||||
None => return false,
|
||||
};
|
||||
chars.all(|c| c == first)
|
||||
}
|
||||
|
||||
/// Strip lines that repeat on many distinct pages (running headers/footers).
|
||||
///
|
||||
/// A line is considered a repeated header/footer if:
|
||||
/// 1. Its normalized text appears on `>= max(3, page_count * 30%)` distinct pages
|
||||
/// 2. It is at least 10 characters long
|
||||
/// 3. It doesn't look like a structural element (heading, list item)
|
||||
/// 4. It consistently appears in the top or bottom N distinct Y positions
|
||||
/// 5. Its Y positions across pages have low variance (consistent placement),
|
||||
/// distinguishing true headers/footers from table content that happens to
|
||||
/// land near page margins
|
||||
/// 6. It is not a decorative separator (repeated single character)
|
||||
///
|
||||
/// Additionally, TextLines at the same Y position on a page are grouped into
|
||||
/// "Y-bands." When any member of a Y-band is stripped, all siblings in that
|
||||
/// band are also stripped. This handles split column headers where individual
|
||||
/// fragments may not independently meet the frequency threshold.
|
||||
///
|
||||
/// Page numbers are stripped from line text before comparison, so headers like
|
||||
/// "Chapter 3 — Page 5" and "Chapter 3 — Page 6" are treated as the same text.
|
||||
pub(crate) fn strip_repeated_lines(lines: Vec<TextLine>, page_count: u32) -> Vec<TextLine> {
|
||||
if lines.is_empty() || page_count < 3 {
|
||||
return lines;
|
||||
}
|
||||
|
||||
// Compute Y range per page (min_y, max_y)
|
||||
let mut page_y_range: HashMap<u32, (f32, f32)> = HashMap::new();
|
||||
for line in &lines {
|
||||
let entry = page_y_range.entry(line.page).or_insert((line.y, line.y));
|
||||
if line.y < entry.0 {
|
||||
entry.0 = line.y;
|
||||
}
|
||||
if line.y > entry.1 {
|
||||
entry.1 = line.y;
|
||||
}
|
||||
}
|
||||
|
||||
// Build sorted Y values per page, so we can check line rank (position from edge)
|
||||
let mut page_sorted_ys: HashMap<u32, Vec<f32>> = HashMap::new();
|
||||
for line in &lines {
|
||||
page_sorted_ys.entry(line.page).or_default().push(line.y);
|
||||
}
|
||||
for ys in page_sorted_ys.values_mut() {
|
||||
ys.sort_by(|a, b| a.total_cmp(b));
|
||||
ys.dedup();
|
||||
}
|
||||
|
||||
// A line is in the page margin if it's among the first or last N distinct
|
||||
// Y positions on that page. This is more robust than a percentage-based zone
|
||||
// because it catches actual edge lines regardless of how much content fills
|
||||
// the page. N=5 accommodates multi-line headers/footers and repeated form
|
||||
// column headers (e.g., 5-row IRS form headers) that sit just inside the
|
||||
// page margin.
|
||||
const EDGE_LINE_COUNT: usize = 5;
|
||||
|
||||
/// Returns true if the given Y position is among the first or last N distinct
|
||||
/// Y positions on the specified page.
|
||||
fn is_y_at_edge(y: f32, page: u32, page_sorted_ys: &HashMap<u32, Vec<f32>>, n: usize) -> bool {
|
||||
let ys = match page_sorted_ys.get(&page) {
|
||||
Some(ys) => ys,
|
||||
None => return false,
|
||||
};
|
||||
if ys.len() <= n * 2 {
|
||||
// Page has very few lines — everything is near the edge
|
||||
return true;
|
||||
}
|
||||
// Check if this Y is among the first or last N
|
||||
let pos = match ys.iter().position(|&py| (py - y).abs() < 0.1) {
|
||||
Some(p) => p,
|
||||
None => return false,
|
||||
};
|
||||
pos < n || pos >= ys.len() - n
|
||||
}
|
||||
|
||||
// Average page span for normalizing Y variance
|
||||
let avg_span = {
|
||||
let total: f32 = page_y_range.values().map(|(lo, hi)| hi - lo).sum();
|
||||
if page_y_range.is_empty() {
|
||||
1.0
|
||||
} else {
|
||||
(total / page_y_range.len() as f32).max(1.0)
|
||||
}
|
||||
};
|
||||
|
||||
// Build Y-bands: group line indices by (page, quantized_y).
|
||||
// Lines at the same Y position (within ~0.1pt) on the same page form a band.
|
||||
let mut y_bands: HashMap<(u32, i32), Vec<usize>> = HashMap::new();
|
||||
for (idx, line) in lines.iter().enumerate() {
|
||||
let y_bucket = (line.y * 10.0).round() as i32;
|
||||
y_bands.entry((line.page, y_bucket)).or_default().push(idx);
|
||||
}
|
||||
|
||||
// Build frequency maps using normalize_for_comparison.
|
||||
// Individual line text -> distinct pages
|
||||
let mut freq: HashMap<String, HashSet<u32>> = HashMap::new();
|
||||
let mut y_positions: HashMap<String, Vec<f32>> = HashMap::new();
|
||||
for line in &lines {
|
||||
if !is_y_at_edge(line.y, line.page, &page_sorted_ys, EDGE_LINE_COUNT) {
|
||||
continue;
|
||||
}
|
||||
let text = line.text();
|
||||
let normalized = normalize_for_comparison(&text);
|
||||
if normalized.len() < 10 || is_decorative_separator(&normalized) {
|
||||
continue;
|
||||
}
|
||||
freq.entry(normalized.clone())
|
||||
.or_default()
|
||||
.insert(line.page);
|
||||
y_positions.entry(normalized).or_default().push(line.y);
|
||||
}
|
||||
|
||||
// Coalesced row text -> distinct pages (for multi-member Y-bands).
|
||||
// This catches split column headers where individual fragments don't meet
|
||||
// the frequency threshold but the combined row does.
|
||||
let mut band_freq: HashMap<String, HashSet<u32>> = HashMap::new();
|
||||
let mut band_y_positions: HashMap<String, Vec<f32>> = HashMap::new();
|
||||
for (&(page, _), indices) in &y_bands {
|
||||
if indices.len() < 2 {
|
||||
continue; // single-line bands are already in the individual map
|
||||
}
|
||||
let band_y = lines[indices[0]].y;
|
||||
if !is_y_at_edge(band_y, page, &page_sorted_ys, EDGE_LINE_COUNT) {
|
||||
continue;
|
||||
}
|
||||
let mut sorted_indices = indices.clone();
|
||||
sorted_indices.sort();
|
||||
let coalesced: String = sorted_indices
|
||||
.iter()
|
||||
.map(|&i| lines[i].text())
|
||||
.collect::<Vec<_>>()
|
||||
.join(" ");
|
||||
let normalized = normalize_for_comparison(&coalesced);
|
||||
if normalized.len() < 10 || is_decorative_separator(&normalized) {
|
||||
continue;
|
||||
}
|
||||
band_freq
|
||||
.entry(normalized.clone())
|
||||
.or_default()
|
||||
.insert(page);
|
||||
band_y_positions.entry(normalized).or_default().push(band_y);
|
||||
}
|
||||
|
||||
// Compute threshold
|
||||
let threshold = 3u32.max(page_count * 30 / 100);
|
||||
|
||||
// Check Y-position consistency: headers/footers appear at the same position
|
||||
// on every page, table content varies. Require normalized stddev < 5% of
|
||||
// average page span.
|
||||
let has_consistent_y = |text: &str, positions: &HashMap<String, Vec<f32>>| -> bool {
|
||||
let pos = match positions.get(text) {
|
||||
Some(p) if p.len() >= 2 => p,
|
||||
_ => return true, // single occurrence — allow
|
||||
};
|
||||
let n = pos.len() as f32;
|
||||
let mean = pos.iter().sum::<f32>() / n;
|
||||
let variance = pos.iter().map(|y| (y - mean).powi(2)).sum::<f32>() / n;
|
||||
let stddev = variance.sqrt();
|
||||
stddev / avg_span < 0.05
|
||||
};
|
||||
|
||||
// Identify candidates from individual frequency map
|
||||
let candidates: HashSet<String> = freq
|
||||
.into_iter()
|
||||
.filter(|(text, pages)| {
|
||||
pages.len() as u32 >= threshold
|
||||
&& !is_structural_line(text)
|
||||
&& has_consistent_y(text, &y_positions)
|
||||
})
|
||||
.map(|(text, _)| text)
|
||||
.collect();
|
||||
|
||||
// Identify candidates from coalesced band frequency map
|
||||
let band_candidates: HashSet<String> = band_freq
|
||||
.into_iter()
|
||||
.filter(|(text, pages)| {
|
||||
pages.len() as u32 >= threshold
|
||||
&& !is_structural_line(text)
|
||||
&& has_consistent_y(text, &band_y_positions)
|
||||
})
|
||||
.map(|(text, _)| text)
|
||||
.collect();
|
||||
|
||||
if candidates.is_empty() && band_candidates.is_empty() {
|
||||
return lines;
|
||||
}
|
||||
|
||||
// Build removal set.
|
||||
// A line is removed if it's at an edge position and:
|
||||
// (a) its individual text matches a candidate, OR
|
||||
// (b) its Y-band's coalesced text matches a band candidate, OR
|
||||
// (c) any sibling in its Y-band was removed (propagation).
|
||||
//
|
||||
// The first occurrence (lowest page number) of each repeated header/footer
|
||||
// is kept so that document titles, column headers, etc. appear once.
|
||||
let mut removal_set: HashSet<usize> = HashSet::new();
|
||||
|
||||
// Track which page first shows each candidate (to preserve first occurrence)
|
||||
let mut first_page_individual: HashMap<String, u32> = HashMap::new();
|
||||
for (idx, line) in lines.iter().enumerate() {
|
||||
if !is_y_at_edge(line.y, line.page, &page_sorted_ys, EDGE_LINE_COUNT) {
|
||||
continue;
|
||||
}
|
||||
let text = line.text();
|
||||
let normalized = normalize_for_comparison(&text);
|
||||
if candidates.contains(&normalized) {
|
||||
let first = first_page_individual.entry(normalized).or_insert(line.page);
|
||||
if line.page > *first {
|
||||
removal_set.insert(idx);
|
||||
} else if line.page == *first {
|
||||
// Keep this occurrence (first page)
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// Track first page for band candidates
|
||||
let mut first_page_band: HashMap<String, u32> = HashMap::new();
|
||||
// First pass: find first page for each band candidate
|
||||
for (&(page, _), indices) in &y_bands {
|
||||
if indices.len() < 2 {
|
||||
continue;
|
||||
}
|
||||
let band_y = lines[indices[0]].y;
|
||||
if !is_y_at_edge(band_y, page, &page_sorted_ys, EDGE_LINE_COUNT) {
|
||||
continue;
|
||||
}
|
||||
let mut sorted_indices = indices.clone();
|
||||
sorted_indices.sort();
|
||||
let coalesced: String = sorted_indices
|
||||
.iter()
|
||||
.map(|&i| lines[i].text())
|
||||
.collect::<Vec<_>>()
|
||||
.join(" ");
|
||||
let normalized = normalize_for_comparison(&coalesced);
|
||||
if band_candidates.contains(&normalized) {
|
||||
let first = first_page_band.entry(normalized).or_insert(page);
|
||||
if page < *first {
|
||||
*first = page;
|
||||
}
|
||||
}
|
||||
}
|
||||
// Second pass: mark for removal (skip first page)
|
||||
for (&(page, _), indices) in &y_bands {
|
||||
if indices.len() < 2 {
|
||||
continue;
|
||||
}
|
||||
let band_y = lines[indices[0]].y;
|
||||
if !is_y_at_edge(band_y, page, &page_sorted_ys, EDGE_LINE_COUNT) {
|
||||
continue;
|
||||
}
|
||||
let mut sorted_indices = indices.clone();
|
||||
sorted_indices.sort();
|
||||
let coalesced: String = sorted_indices
|
||||
.iter()
|
||||
.map(|&i| lines[i].text())
|
||||
.collect::<Vec<_>>()
|
||||
.join(" ");
|
||||
let normalized = normalize_for_comparison(&coalesced);
|
||||
if band_candidates.contains(&normalized) {
|
||||
let first = first_page_band.get(&normalized).copied().unwrap_or(0);
|
||||
if page > first {
|
||||
for &idx in &sorted_indices {
|
||||
removal_set.insert(idx);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
// (c) Y-band sibling propagation: if any member is removed, remove all
|
||||
// members (provided the band is at an edge position).
|
||||
for (&(page, _), indices) in &y_bands {
|
||||
let band_y = lines[indices[0]].y;
|
||||
if !is_y_at_edge(band_y, page, &page_sorted_ys, EDGE_LINE_COUNT) {
|
||||
continue;
|
||||
}
|
||||
if indices.iter().any(|idx| removal_set.contains(idx)) {
|
||||
for &idx in indices {
|
||||
removal_set.insert(idx);
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
if removal_set.is_empty() {
|
||||
return lines;
|
||||
}
|
||||
|
||||
lines
|
||||
.into_iter()
|
||||
.enumerate()
|
||||
.filter(|(idx, _)| !removal_set.contains(idx))
|
||||
.map(|(_, line)| line)
|
||||
.collect()
|
||||
}
|
||||
|
||||
#[cfg(test)]
|
||||
mod tests {
|
||||
use super::*;
|
||||
@@ -679,53 +343,6 @@ mod tests {
|
||||
assert_eq!(result.len(), 2, "should merge font-based heading lines");
|
||||
}
|
||||
|
||||
#[test]
|
||||
fn test_strip_repeated_keeps_first_occurrence() {
|
||||
// Simulate a repeated page header on 10 pages.
|
||||
// Each page has a running header at y=750 and many unique body lines.
|
||||
let mut lines = Vec::new();
|
||||
for page in 1..=10u32 {
|
||||
// Header at top
|
||||
lines.push(make_line(
|
||||
"VOICE OF SOUTH MARION May fifteen twenty twenty five",
|
||||
10.0,
|
||||
page,
|
||||
750.0,
|
||||
None,
|
||||
));
|
||||
// Body content — unique text per line per page (no digits to strip)
|
||||
for j in 0..20u32 {
|
||||
lines.push(make_line(
|
||||
&format!(
|
||||
"parcel r-{:04}-{:03} owner smith address oak street",
|
||||
page * 100 + j,
|
||||
page
|
||||
),
|
||||
10.0,
|
||||
page,
|
||||
600.0 - j as f32 * 15.0,
|
||||
None,
|
||||
));
|
||||
}
|
||||
}
|
||||
|
||||
let result = strip_repeated_lines(lines, 10);
|
||||
|
||||
// The header should appear exactly once (page 1)
|
||||
let header_count = result
|
||||
.iter()
|
||||
.filter(|l| l.text().contains("VOICE OF SOUTH MARION"))
|
||||
.count();
|
||||
assert_eq!(header_count, 1, "repeated header should be kept once");
|
||||
|
||||
// First occurrence should be on page 1
|
||||
let first_header = result
|
||||
.iter()
|
||||
.find(|l| l.text().contains("VOICE OF SOUTH MARION"))
|
||||
.unwrap();
|
||||
assert_eq!(first_header.page, 1, "first occurrence should be on page 1");
|
||||
}
|
||||
|
||||
fn make_bold_line(text: &str, page: u32, y: f32) -> TextLine {
|
||||
let mut item = make_item(text, 12.0, None);
|
||||
item.is_bold = true;
|
||||
|
||||
@@ -2,9 +2,19 @@
|
||||
|
||||
# BePriced?
|
||||
|
||||
*Commercial real estate pricing* **C O M M E R C I A L R E A L E S T A T E** pricingisliketheweather:everyonetalks *needs disciplined and systematic*about it, but few understand it. Most observers base “appropriate” real estate *analysis of the data.* pricing on historical norms. The cap rate—anindicatorofvaluerelativetosta- bilized net operating income (NOI) before capital expenditures, tenant improvement,andleasingcommissions— isthemostcommonlyusedmetricofreal estate pricing. But cap rates have been largelyunresponsivetoalternativeratesof return available to investors, with the **P E T E R L I N N E M A N** exception of BBB bonds, throughout
|
||||
*Commercial real estate pricing*
|
||||
|
||||
8 4 Z E L L / L U R I E R E A L E S T A T E C E N T E R
|
||||
*needs disciplined and systematic*
|
||||
|
||||
*analysis of the data.*
|
||||
|
||||
**C O M M E R C I A L R E A L E S T A T E** pricingisliketheweather:everyonetalks about it, but few understand it. Most observers base “appropriate” real estate pricing on historical norms. The cap rate—anindicatorofvaluerelativetosta- bilized net operating income (NOI) before capital expenditures, tenant improvement,andleasingcommissions— isthemostcommonlyusedmetricofreal estate pricing. But cap rates have been largelyunresponsivetoalternativeratesof return available to investors, with the exception of BBB bonds, throughout
|
||||
|
||||
C E N T E R
|
||||
|
||||
**P E T E R L I N N E M A N**
|
||||
|
||||
8 4 Z E L L / L U R I E R E A L E S T A T E
|
||||
|
||||
**Table I:** Cap rate correlations **Cap Rate Correlation With:*** **BBB Corp** **10-Year Bond Yield S&P Dividend** **Treasury (10-15 yr) Yield** Multifamily 0.187 0.771 0.068 Industrial-0.221 0.748-0.307 CBD Office-0.449 0.694-0.458 Retail-0.181 0.649-02.58
|
||||
|
||||
@@ -13,9 +23,11 @@
|
||||
12 10 8 Percent 6 4 2 1982 1986 1990 1994 1998 2002 2006
|
||||
Apartment Retail ndustrial 10-yr reasury CBD Office
|
||||
|
||||
most of the past twenty-five years (Table presented in Figure 2 with an eighteen-
|
||||
most of the past twenty-five years (Table
|
||||
|
||||
I). Such a relationship defies investment theory,asrealestatepricingshouldchange as property risks and the returns of alter- nativeinvestmentschange. Figure1displaysNCREIFcapratesby property type compared to the ten-year Treasury yield. Because the National Council of Real Estate Investment Fiduciaries (NCREIF) cap rate data is seriouslyflawedduetoappraisallags,itis
|
||||
presented in Figure 2 with an eighteen- monthlag.Thisdataprovidesanoverview ofthepricingofinstitutionalqualityreal estate.Figure2reflectsthesecapratesnet of the ten-year Treasury yield. Since cap rate spreads are highly correlated across propertytypes(TableII),wecanspeakof “cap rates” without reference to property type with little loss of insight. Cap rate spreadswerenegativeintheearlytomid- 1980s, when purchasing real estate was
|
||||
|
||||
I). Such a relationship defies investment monthlag.Thisdataprovidesanoverview theory,asrealestatepricingshouldchange ofthepricingofinstitutionalqualityreal as property risks and the returns of alter-estate.Figure2reflectsthesecapratesnet nativeinvestmentschange. of the ten-year Treasury yield. Since cap Figure1displaysNCREIFcapratesby rate spreads are highly correlated across property type compared to the ten-year propertytypes(TableII),wecanspeakof Treasury yield. Because the National “cap rates” without reference to property Council of Real Estate Investment type with little loss of insight. Cap rate Fiduciaries (NCREIF) cap rate data is spreadswerenegativeintheearlytomid- seriouslyflawedduetoappraisallags,itis 1980s, when purchasing real estate was
|
||||
R E V I E W 8 5
|
||||
|
||||
**Figure 2:** Capratespreadsover10-yearTreasury
|
||||
|
||||
Reference in New Issue
Block a user