pagelayout.c - libextractor - GNU libextractor

pagelayout.c (14696B)
      1 /*
      2      This file is part of libextractor.
      3      Copyright (C) 2026 Christian Grothoff
      4 
      5      libextractor is free software; you can redistribute it and/or modify
      6      it under the terms of the GNU General Public License as published
      7      by the Free Software Foundation; either version 3, or (at your
      8      option) any later version.
      9 
     10      libextractor is distributed in the hope that it will be useful, but
     11      WITHOUT ANY WARRANTY; without even the implied warranty of
     12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     13      General Public License for more details.
     14 
     15      You should have received a copy of the GNU General Public License
     16      along with libextractor; see the file COPYING.  If not, write to the
     17      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
     18      Boston, MA 02110-1301, USA.
     19  */
     20 /**
     21  * @file plugins/pagelayout.c
     22  * @brief paragraph detection from line geometry for paged formats
     23  * @author Christian Grothoff
     24  */
     25 #include "platform.h"
     26 #include "pagelayout.h"
     27 #include <math.h>
     28 
     29 /**
     30  * Maximum number of left margins (text columns, indentation levels
     31  * of lists, ...) we track per page.
     32  */
     33 #define MAX_MARGINS 8
     34 
     35 /**
     36  * Lines whose left end is within this many font sizes of a margin
     37  * start "at" that margin.
     38  */
     39 #define AT_MARGIN 0.3
     40 
     41 /**
     42  * Minimum indentation of a paragraph's first line, in font sizes.
     43  */
     44 #define MIN_INDENT 0.5
     45 
     46 /**
     47  * Maximum indentation of a paragraph's first line, in font sizes.
     48  */
     49 #define MAX_INDENT 4.0
     50 
     51 
     52 /**
     53  * Per-margin statistics.
     54  */
     55 struct Margin
     56 {
     57   /**
     58    * Horizontal position of the margin.
     59    */
     60   double x;
     61 
     62   /**
     63    * Typical right end of the lines starting at this margin.
     64    */
     65   double right;
     66 
     67   /**
     68    * 1 if most lines at this margin end at @e right (justified text).
     69    */
     70   int justified;
     71 };
     72 
     73 
     74 /**
     75  * Layout statistics of one page, computed over the non-skipped lines.
     76  */
     77 struct PageStats
     78 {
     79   /**
     80    * Left margins.
     81    */
     82   struct Margin margins[MAX_MARGINS];
     83 
     84   /**
     85    * Number of entries in @e margins.
     86    */
     87   unsigned int num_margins;
     88 
     89   /**
     90    * Median font size.
     91    */
     92   double size;
     93 
     94   /**
     95    * Typical baseline distance of consecutive lines.
     96    */
     97   double spacing;
     98 
     99   /**
    100    * Relative uncertainty of the right ends.
    101    */
    102   double tol;
    103 };
    104 
    105 
    106 /**
    107  * Compare two doubles for qsort().
    108  *
    109  * @param a first value
    110  * @param b second value
    111  * @return comparison result
    112  */
    113 static int
    114 cmp_double (const void *a,
    115             const void *b)
    116 {
    117   double x = *(const double *) a;
    118   double y = *(const double *) b;
    119 
    120   if (x < y)
    121     return -1;
    122   if (x > y)
    123     return 1;
    124   return 0;
    125 }
    126 
    127 
    128 /**
    129  * Return the value at quantile @a q of the @a n values in @a v (which
    130  * are sorted in place).
    131  *
    132  * @param v values, @a n > 0
    133  * @param n number of values
    134  * @param q quantile in [0,1]
    135  * @return the quantile
    136  */
    137 static double
    138 quantile (double *v,
    139           size_t n,
    140           double q)
    141 {
    142   size_t i;
    143 
    144   qsort (v,
    145          n,
    146          sizeof (double),
    147          &cmp_double);
    148   i = (size_t) (q * (double) (n - 1) + 0.5);
    149   if (i >= n)
    150     i = n - 1;
    151   return v[i];
    152 }
    153 
    154 
    155 /**
    156  * Check whether a geometry value is usable.
    157  *
    158  * @param d value to check
    159  * @return 1 if finite
    160  */
    161 static int
    162 ok (double d)
    163 {
    164   return isfinite (d) ? 1 : 0;
    165 }
    166 
    167 
    168 /**
    169  * Find the margin a line starting at @a x belongs to: the closest
    170  * margin to the left within #MAX_INDENT font sizes (or just right of
    171  * it within #AT_MARGIN).
    172  *
    173  * @param st page statistics
    174  * @param x left end of the line
    175  * @return margin index, -1 if none
    176  */
    177 static int
    178 find_margin (const struct PageStats *st,
    179              double x)
    180 {
    181   int best = -1;
    182   double bestd = 0;
    183   unsigned int i;
    184 
    185   for (i = 0; i < st->num_margins; i++)
    186   {
    187     double d = x - st->margins[i].x;
    188 
    189     if ( (d < -AT_MARGIN * st->size) ||
    190          (d > MAX_INDENT * st->size) )
    191       continue;
    192     if ( (-1 == best) ||
    193          (fabs (d) < bestd) )
    194     {
    195       best = (int) i;
    196       bestd = fabs (d);
    197     }
    198   }
    199   return best;
    200 }
    201 
    202 
    203 /**
    204  * Check whether a line starting at @a x starts at a left margin.
    205  *
    206  * @param st page statistics
    207  * @param x left end of the line
    208  * @return 1 if at a margin
    209  */
    210 static int
    211 at_margin (const struct PageStats *st,
    212            double x)
    213 {
    214   unsigned int i;
    215 
    216   for (i = 0; i < st->num_margins; i++)
    217     if (fabs (x - st->margins[i].x) <= AT_MARGIN * st->size)
    218       return 1;
    219   return 0;
    220 }
    221 
    222 
    223 /**
    224  * Check whether line @a b (with page statistics @a st) is the indented
    225  * first line of a paragraph, given that it follows line @a a.
    226  *
    227  * @param st statistics of the page of @a b
    228  * @param a previous line
    229  * @param b line to check
    230  * @return 1 if @a b is indented
    231  */
    232 static int
    233 is_indented (const struct PageStats *st,
    234              const struct EXTRACTOR_PageLineGeom *a,
    235              const struct EXTRACTOR_PageLineGeom *b)
    236 {
    237   unsigned int i;
    238 
    239   if (at_margin (st,
    240                  b->x0))
    241     return 0;
    242   /* a block of lines that are all indented alike (a quote, a list) */
    243   if (fabs (a->x0 - b->x0) < AT_MARGIN * st->size)
    244     return 0;
    245   for (i = 0; i < st->num_margins; i++)
    246   {
    247     double d = b->x0 - st->margins[i].x;
    248 
    249     if ( (d >= MIN_INDENT * st->size) &&
    250          (d <= MAX_INDENT * st->size) )
    251       return 1;
    252   }
    253   return 0;
    254 }
    255 
    256 
    257 /**
    258  * Check whether line @a a ends well before the right margin of a
    259  * justified block.
    260  *
    261  * @param st statistics of the page of @a a
    262  * @param a line to check
    263  * @return 1 if @a a is short
    264  */
    265 static int
    266 is_short (const struct PageStats *st,
    267           const struct EXTRACTOR_PageLineGeom *a)
    268 {
    269   int m;
    270   const struct Margin *mg;
    271   double width;
    272   double slack;
    273 
    274   m = find_margin (st,
    275                    a->x0);
    276   if (-1 == m)
    277     return 0;
    278   mg = &st->margins[m];
    279   if (! mg->justified)
    280     return 0;
    281   width = mg->right - mg->x;
    282   if (width <= 0)
    283     return 0;
    284   slack = (0.05 + 2 * st->tol) * width;
    285   if (slack < 2 * st->size)
    286     slack = 2 * st->size;
    287   return (a->x1 < mg->right - slack) ? 1 : 0;
    288 }
    289 
    290 
    291 /**
    292  * Check whether the font size changes noticeably from @a a to @a b.
    293  *
    294  * @param a first line
    295  * @param b second line
    296  * @return 1 on a size change
    297  */
    298 static int
    299 size_change (const struct EXTRACTOR_PageLineGeom *a,
    300              const struct EXTRACTOR_PageLineGeom *b)
    301 {
    302   double mx = (a->size > b->size) ? a->size : b->size;
    303 
    304   return (fabs (a->size - b->size) > 0.15 * mx) ? 1 : 0;
    305 }
    306 
    307 
    308 /**
    309  * Compute the layout statistics of page @a page.
    310  *
    311  * @param page the page
    312  * @param g geometry of its lines
    313  * @param tol relative uncertainty of right ends
    314  * @param[out] st statistics to fill
    315  * @return 0 on success, -1 on allocation failure or if the page has
    316  *         no usable lines
    317  */
    318 static int
    319 page_stats (const struct EXTRACTOR_FullTextPage *page,
    320             const struct EXTRACTOR_PageLineGeom *g,
    321             double tol,
    322             struct PageStats *st)
    323 {
    324   double *v;
    325   double *xs;
    326   size_t n;
    327   size_t k;
    328   unsigned int i;
    329   unsigned int prev;
    330   int have_prev;
    331 
    332   memset (st, 0, sizeof (*st));
    333   st->tol = tol;
    334   if (0 == page->num_lines)
    335     return -1;
    336   v = malloc (page->num_lines * sizeof (double));
    337   xs = malloc (page->num_lines * sizeof (double));
    338   if ( (NULL == v) ||
    339        (NULL == xs) )
    340   {
    341     free (v);
    342     free (xs);
    343     return -1;
    344   }
    345   /* median font size */
    346   n = 0;
    347   for (i = 0; i < page->num_lines; i++)
    348     if ( (! page->lines[i].skip) &&
    349          (g[i].size > 0) )
    350       v[n++] = g[i].size;
    351   if (0 == n)
    352   {
    353     free (v);
    354     free (xs);
    355     return -1;
    356   }
    357   st->size = quantile (v, n, 0.5);
    358   /* typical line spacing */
    359   n = 0;
    360   have_prev = 0;
    361   prev = 0;
    362   for (i = 0; i < page->num_lines; i++)
    363   {
    364     double dy;
    365 
    366     if (page->lines[i].skip)
    367       continue;
    368     if (have_prev)
    369     {
    370       dy = g[i].y - g[prev].y;
    371       if ( (dy > 0.3 * st->size) &&
    372            (dy < 3 * st->size) )
    373         v[n++] = dy;
    374     }
    375     prev = i;
    376     have_prev = 1;
    377   }
    378   st->spacing = (n > 0) ? quantile (v, n, 0.5) : 1.2 * st->size;
    379   /* left margins: clusters of line starts */
    380   n = 0;
    381   for (i = 0; i < page->num_lines; i++)
    382     if (! page->lines[i].skip)
    383       xs[n++] = g[i].x0;
    384   qsort (xs,
    385          n,
    386          sizeof (double),
    387          &cmp_double);
    388   k = 0;
    389   while (k < n)
    390   {
    391     size_t e = k + 1;
    392     size_t cnt;
    393 
    394     while ( (e < n) &&
    395             (xs[e] - xs[e - 1] <= AT_MARGIN * st->size) )
    396       e++;
    397     cnt = e - k;
    398     if ( ( (cnt >= 2) &&
    399            (cnt * 100 >= n * 15) ) ||
    400          ( (n < 4) &&
    401            (0 == k) ) )
    402     {
    403       if (st->num_margins < MAX_MARGINS)
    404       {
    405         st->margins[st->num_margins].x = xs[k];
    406         st->num_margins++;
    407       }
    408       else
    409       {
    410         /* replace the smallest cluster? keep it simple: stop */
    411         break;
    412       }
    413     }
    414     k = e;
    415   }
    416   /* right ends per margin */
    417   for (i = 0; i < st->num_margins; i++)
    418   {
    419     struct Margin *mg = &st->margins[i];
    420     unsigned int j;
    421     size_t at;
    422     size_t near;
    423     double slack;
    424 
    425     n = 0;
    426     for (j = 0; j < page->num_lines; j++)
    427       if ( (! page->lines[j].skip) &&
    428            ((int) i == find_margin (st, g[j].x0)) )
    429         v[n++] = g[j].x1;
    430     if (n < 3)
    431       continue;
    432     mg->right = quantile (v, n, 0.75);
    433     slack = tol * (mg->right - mg->x);
    434     if (slack < 0.5 * st->size)
    435       slack = 0.5 * st->size;
    436     near = 0;
    437     for (at = 0; at < n; at++)
    438       if (fabs (v[at] - mg->right) <= slack)
    439         near++;
    440     mg->justified = (2 * near >= n) ? 1 : 0;
    441   }
    442   free (v);
    443   free (xs);
    444   return 0;
    445 }
    446 
    447 
    448 /**
    449  * Decide whether line @a a ends a paragraph, given that line @a b (on
    450  * the same page) follows it.
    451  *
    452  * @param st page statistics
    453  * @param a the line
    454  * @param b the next line
    455  * @return 1 if @a a ends a paragraph
    456  */
    457 static int
    458 ends_paragraph (const struct PageStats *st,
    459                 const struct EXTRACTOR_PageLineGeom *a,
    460                 const struct EXTRACTOR_PageLineGeom *b)
    461 {
    462   double dy = b->y - a->y;
    463   double big;
    464   double lim;
    465 
    466   big = (a->size > b->size) ? a->size : b->size;
    467   lim = 1.15 * big;
    468   if (lim < st->spacing)
    469     lim = st->spacing;
    470   if ( (dy > 0) &&
    471        (dy > 1.3 * lim) )
    472     return 1;
    473   if (size_change (a, b))
    474     return 1;
    475   if (is_indented (st, a, b))
    476     return 1;
    477   if (is_short (st, a))
    478     return 1;
    479   return 0;
    480 }
    481 
    482 
    483 void
    484 EXTRACTOR_pagelayout_paragraphs_ (struct EXTRACTOR_FullTextPage *pages,
    485                                   struct EXTRACTOR_PageLineGeom *const *geoms,
    486                                   unsigned int num_pages,
    487                                   double width_tolerance)
    488 {
    489   struct PageStats *stats;
    490   unsigned int p;
    491   int have_last;
    492   unsigned int last_p = 0;
    493   unsigned int last_i = 0;
    494 
    495   if (0 == num_pages)
    496     return;
    497   stats = calloc (num_pages,
    498                   sizeof (*stats));
    499   if (NULL == stats)
    500     return;
    501   have_last = 0;
    502   for (p = 0; p < num_pages; p++)
    503   {
    504     struct EXTRACTOR_FullTextPage *page = &pages[p];
    505     const struct EXTRACTOR_PageLineGeom *g = geoms[p];
    506     unsigned int i;
    507     int have_prev;
    508     unsigned int prev = 0;
    509 
    510     for (i = 0; i < page->num_lines; i++)
    511     {
    512       page->lines[i].par_end = 0;
    513       if ( (! ok (g[i].x0)) ||
    514            (! ok (g[i].x1)) ||
    515            (! ok (g[i].y)) ||
    516            (! ok (g[i].size)) )
    517         page->lines[i].skip = 1;
    518     }
    519     if (0 != page_stats (page,
    520                          g,
    521                          width_tolerance,
    522                          &stats[p]))
    523       continue;
    524     have_prev = 0;
    525     for (i = 0; i < page->num_lines; i++)
    526     {
    527       if (page->lines[i].skip)
    528         continue;
    529       if (have_prev)
    530       {
    531         page->lines[prev].par_end = ends_paragraph (&stats[p],
    532                                                     &g[prev],
    533                                                     &g[i]);
    534       }
    535       else if (have_last)
    536       {
    537         /* first line of this page, previous page's last line */
    538         const struct EXTRACTOR_PageLineGeom *a = &geoms[last_p][last_i];
    539 
    540         if ( (is_short (&stats[last_p], a)) ||
    541              (size_change (a, &g[i])) ||
    542              (is_indented (&stats[p], a, &g[i])) )
    543           pages[last_p].lines[last_i].par_end = 1;
    544       }
    545       prev = i;
    546       have_prev = 1;
    547     }
    548     if (have_prev)
    549     {
    550       have_last = 1;
    551       last_p = p;
    552       last_i = prev;
    553     }
    554   }
    555   if (have_last)
    556     pages[last_p].lines[last_i].par_end = 1;
    557   free (stats);
    558 }
    559 
    560 
    561 /**
    562  * Precomposed characters for base letter + combining accent.
    563  */
    564 struct Composition
    565 {
    566   /**
    567    * Combining accent.
    568    */
    569   uint16_t accent;
    570 
    571   /**
    572    * Base letters (ASCII).
    573    */
    574   const char *bases;
    575 
    576   /**
    577    * Precomposed characters, same order as @e bases.
    578    */
    579   uint16_t composed[26];
    580 };
    581 
    582 
    583 /**
    584  * Table of precomposed characters.
    585  */
    586 static const struct Composition compositions[] = {
    587   { 0x0300, "AEIOUaeiou",
    588     { 0xC0, 0xC8, 0xCC, 0xD2, 0xD9, 0xE0, 0xE8, 0xEC, 0xF2, 0xF9 } },
    589   { 0x0301, "AEIOUYaeiouyCcNnSsZzLlRr",
    590     { 0xC1, 0xC9, 0xCD, 0xD3, 0xDA, 0xDD, 0xE1, 0xE9, 0xED, 0xF3, 0xFA,
    591       0xFD, 0x106, 0x107, 0x143, 0x144, 0x15A, 0x15B, 0x179, 0x17A,
    592       0x139, 0x13A, 0x154, 0x155 } },
    593   { 0x0302, "AEIOUaeiou",
    594     { 0xC2, 0xCA, 0xCE, 0xD4, 0xDB, 0xE2, 0xEA, 0xEE, 0xF4, 0xFB } },
    595   { 0x0303, "ANOano",
    596     { 0xC3, 0xD1, 0xD5, 0xE3, 0xF1, 0xF5 } },
    597   { 0x0304, "AaEeIiOoUu",
    598     { 0x100, 0x101, 0x112, 0x113, 0x12A, 0x12B, 0x14C, 0x14D, 0x16A,
    599       0x16B } },
    600   { 0x0306, "AaGgUu",
    601     { 0x102, 0x103, 0x11E, 0x11F, 0x16C, 0x16D } },
    602   { 0x0307, "ZzIEeCcGg",
    603     { 0x17B, 0x17C, 0x130, 0x116, 0x117, 0x10A, 0x10B, 0x120, 0x121 } },
    604   { 0x0308, "AEIOUaeiouyY",
    605     { 0xC4, 0xCB, 0xCF, 0xD6, 0xDC, 0xE4, 0xEB, 0xEF, 0xF6, 0xFC, 0xFF,
    606       0x178 } },
    607   { 0x030A, "AaUu",
    608     { 0xC5, 0xE5, 0x16E, 0x16F } },
    609   { 0x030B, "OoUu",
    610     { 0x150, 0x151, 0x170, 0x171 } },
    611   { 0x030C, "CcDdEeNnRrSsTtZz",
    612     { 0x10C, 0x10D, 0x10E, 0x10F, 0x11A, 0x11B, 0x147, 0x148, 0x158,
    613       0x159, 0x160, 0x161, 0x164, 0x165, 0x17D, 0x17E } },
    614   { 0x0327, "CcSsTtKkLlNnRr",
    615     { 0xC7, 0xE7, 0x15E, 0x15F, 0x162, 0x163, 0x136, 0x137, 0x13B, 0x13C,
    616       0x145, 0x146, 0x156, 0x157 } },
    617   { 0x0328, "AaEeIiUu",
    618     { 0x104, 0x105, 0x118, 0x119, 0x12E, 0x12F, 0x172, 0x173 } },
    619   { 0x0337, "Ll",
    620     { 0x141, 0x142 } },
    621   { 0, NULL, { 0 } }
    622 };
    623 
    624 
    625 uint32_t
    626 EXTRACTOR_pagelayout_compose_ (uint32_t base,
    627                                uint32_t accent)
    628 {
    629   unsigned int i;
    630   const char *pos;
    631 
    632   if (0x0131 == base)
    633     base = 'i';
    634   if (0x0237 == base)
    635     base = 'j';
    636   if ( (base >= 0x80) ||
    637        (! isalpha ((int) base)) )
    638     return 0;
    639   for (i = 0; NULL != compositions[i].bases; i++)
    640   {
    641     if (compositions[i].accent != accent)
    642       continue;
    643     pos = strchr (compositions[i].bases,
    644                   (int) base);
    645     if (NULL == pos)
    646       return 0;
    647     return compositions[i].composed[pos - compositions[i].bases];
    648   }
    649   return 0;
    650 }
    651 
    652 
    653 /* end of pagelayout.c */
	libextractor GNU libextractor
	Log \| Files \| Refs \| Submodules \| README \| LICENSE