Stopp falske PDF-tabeller fra høyrestilt tekst i Delphi

PDFium Component versjon 3.117.0 slutter å rapportere høyrestilte avsnitt som mellomromsjusterte tabeller ved å kreve at hver kolonnegrense er en loddrett korridor uten tekst på noen rad den skiller, ved å hoppe over ord som allerede er kravd av et linjebasert rutenett, og ved å sette sammen celletekst etter vertikal overlapp i stedet for avstand mellom glyfboksenes sentre. Alle tre endringene ligger inne i ExtractTables og ExtractDocumentTables og krever ingen innstilling

Rapporten som startet dette, var lite glamorøs. En pressemeldingsside uten en eneste tabell kom tilbake fra ExtractTables med en 5x4-mellomromstabell, med konfidens godt over standardverdien MinConfidence på 0.5, og cellene inneholdt fragmenter av helt vanlig brødtekst. Et søknadsskjema gjorde det samme med essayavsnittene sine og produserte en 3x4 og en 5x3. Begge dokumentene var høyrestilt. Den opplagte responsen er å justere tersklene, og den nyttige lærdommen fra denne utgivelsen er at justering ikke kan rette det, fordi regelen som ble justert, stilte feil spørsmål

uses
  PDFium;

// Regresjonssjekk: list opp hver mellomromstabell i et dokument så en side
// du vet bare inneholder prosa, kan bekreftes ren
procedure ReportWhitespaceTables(Pdf: TPdf);
var
  Options: TPdfTableExtractionOptions;
  Tables: TPdfTables;
  I: Integer;
begin
  Options := TPdfTableExtractionOptions.Default;   // MinColumnGap 12pt
  Tables := Pdf.ExtractDocumentTables(Options);
  for I := 0 to High(Tables) do
    if Tables[I].DetectionMode = ptdmWhitespace then
      Writeln(Format('page %d: %dx%d whitespace table, confidence %.2f, ' +
        'first cell "%s"',
        [Tables[I].PageNumber, Tables[I].RowCount, Tables[I].ColumnCount,
         Tables[I].Confidence, Tables[I].Cells[0].Text]));
end;

Hvorfor ser høyrestilt tekst ut som en tabell?

Et høyrestilt avsnitt ser ut som en tabell fordi en høyrestilt linje er en rad med ord skilt av mellomrom som layoutmotoren har strukket, og når et strukket mellomrom når MinColumnGap, har detektoren ingen radlokal måte å skille det fra en kolonneskilletegn. Mellomromsstrategien i PDFium Component grupperer ordbokser i visuelle rader, deler hver rad i ordgrupper der den vannrette avstanden til det forrige ordet er minst MinColumnGap (12 punkter som standard), og godtar en tabell når minst to påfølgende rader gjentar minst MinColumns venstrejusterte gruppeankere innenfor AlignmentTolerance, som er 3 punkter. Det er regelen som er beskrevet i oversikten over tabellgjenkjenning, og for en ekte justert tabell er den nøyaktig riktig

Bruk den nå på tjue linjer høyrestilt prosa i 10 punkter. Hver linje strekkes til den samme høyremargen, så en linje som slutter med et langt ord, drar de indre mellomrommene sine åpne, og i et avsnitt med noen korte linjer krysser noen av de mellomrommene 12 punkter. To påfølgende linjer trenger bare ett strukket mellomrom hver, som lander innenfor 3 punkter fra samme X-posisjon, for å danne en kandidat med to rader og to kolonner. Over nok linjer er dette ikke uflaks; det er en sannsynlighet som nærmer seg visshet, og 5x4-en på pressemeldingen var rett og slett den kjøringen der fire slike mellomrom stilte seg opp på fem linjer

Hver terskel bytter én dokumentklasse mot en annen. Å heve MinColumnGap til 20 punkter mister de kompakte kolonnene i tette finansrapporter, som er nøyaktig tilfellet standardverdien allerede var senket for. Å heve MinRows til 3 forkaster ekte tabeller med to rader og senker bare oddsen for lange avsnitt. Å stramme AlignmentTolerance under 3 punkter ødelegger ordbokser fra OCR, der venstrekantene vibrerer mer enn som så. Signalet på radnivå er genuint tvetydig, så rettelsen må komme fra et signal radene ikke bærer på egen hånd

Hva gjør en kolonnegrense ekte?

En ekte kolonnegrense er en loddrett stripe av siden som forblir tom gjennom hver rad den skiller. En tabell har en mellom hvert par av kolonner ved konstruksjon, fordi cellene ble lagt ut mot delte X-posisjoner. Et høyrestilt avsnitt strekker ordmellomrommene sine på forskjellige vannrette posisjoner på hver linje, så ingen stripe overlever snittet av mer enn en linje eller to. PDFium Component tester nå nøyaktig det: etter at kandidatens ordgrupper er tilordnet ankerkolonner, tar den for hvert par av tilstøtende kolonner, på hver rad som har innhold i begge cellene, intervallet fra høyre kant av ordene i venstre celle til venstre kant av ordene i høyre celle, snitter disse intervallene på tvers av rader, og avviser hele kandidaten hvis snittet er smalere enn MinColumnGap ganger 0.5, som er 6 punkter med standardverdien

To detaljer betyr noe. Rader der en av cellene er tomme, stemmer ikke, så en tabell med en tom celle, eller en overskrift som spenner over færre kolonner enn kroppen, går fortsatt gjennom. Og korridorbredden utledes fra MinColumnGap i stedet for å eksponeres som et eget alternativ, fordi de to beskriver den samme fysiske tingen: mellomrommet en designer lar stå mellom kolonner. Logikken er liten nok til å reprodusere hvis du bygger på råe ordbokser og ikke på tabell-API-et, og eksemplet nedenfor speiler sjekken inne i komponenten:

uses
  Math, PDFium;

type
  TIndexList = array of Integer;
  TCellIndexes = array of TIndexList;   // Row * ColumnCount + Column

// Returnerer False når noe par av tilstøtende kolonner mangler en tekstfri
// loddrett korridor som er minst MinColumnGap / 2 bred over radene som bruker den
function HasTextFreeCorridors(const Words: TPdfWordBoxes;
  const Cells: TCellIndexes; RowCount, ColumnCount: Integer;
  MinColumnGap: Double): Boolean;
var
  Col, Row, I, LeftCell, RightCell, Supported: Integer;
  CorridorLeft, CorridorRight, RowLeft, RowRight: Double;
begin
  for Col := 0 to ColumnCount - 2 do
  begin
    CorridorLeft := -MaxDouble;
    CorridorRight := MaxDouble;
    Supported := 0;
    for Row := 0 to RowCount - 1 do
    begin
      LeftCell := Row * ColumnCount + Col;
      RightCell := LeftCell + 1;
      if (Length(Cells[LeftCell]) = 0) or (Length(Cells[RightCell]) = 0) then
        Continue;                             // tomme celler stemmer ikke
      RowLeft := -MaxDouble;
      RowRight := MaxDouble;
      for I in Cells[LeftCell] do
        RowLeft := Max(RowLeft, Words[I].Rect.Right);
      for I in Cells[RightCell] do
        RowRight := Min(RowRight, Words[I].Rect.Left);
      CorridorLeft := Max(CorridorLeft, RowLeft);
      CorridorRight := Min(CorridorRight, RowRight);
      Inc(Supported);
    end;
    if (Supported > 0) and
       (CorridorRight - CorridorLeft < MinColumnGap * 0.5) then
      Exit(False);
  end;
  Result := True;
end;

Hvorfor ble linjebaserte tabeller hentet ut to ganger?

Linjebaserte tabeller ble hentet ut to ganger fordi mellomromspasset pleide å se hvert ord på siden, inkludert ordene det linjebaserte passet allerede hadde plassert i et rutenett, og en ren linjebasert tabell er ved konstruksjon også en perfekt justert mellomromstabell. En overlappssjekk avviste allerede en mellomromskandidat hvis avgrensning dekket mer enn halvparten av en eksisterende tabell, men en kandidat som kombinerte tabellens nedre rader med noen justerte tekstlinjer under den, kunne falle under den andelen og overleve som en andre, litt større tabell som blødde inn i naboen. ExtractTables fjerner nå de ordene før mellomromspasset kjører. Et ord droppes når midtpunktet ligger inne i avgrensningen til en tabell det linjebaserte passet produserte; midtpunktet brukes og ikke full inneslutning, slik at et ord som stikker en brøkdel av et punkt over en ramme, følger tabellen det visuelt hører til. Mellomromsstrategien jobber da bare med de frie ordene, noe som også betyr at en liten tabell uten linjenett som ligger rett under en linjebasert tabell, oppdages på egne premisser i stedet for å smelte sammen med rutenettet over seg

Hvorfor kom «Purpose of Request:» ut som «of Purpose Request:»?

Ordene kom ut i feil rekkefølge fordi ordboksene PDFium Component bygger, er unioner av glyfenes avgrensningsbokser, og «of» har ingen underlengde mens «Purpose» og «Request:» har det. FPDFText_GetCharBox returnerer den trange boksen rundt glyfens blekk i siderommet, ikke en boks polstret til fontens ascender og descender, og ordboksen er unionen av tegnenes bokser. Et ord uten underlengder er derfor lavere, og det loddrette midtpunktet ligger høyere, med 2 til 3 punkter på skjemaet det gjaldt. Den gamle rutinen for celletekst sorterte ordene på midt-Y først, med 1 punkts toleranse for «samme linje», og deretter på venstrekant; «of» klarte toleransen, sorterte som sin egen linje over de andre, og ble sendt ut først

Dette er ikke så mye en PDFium-egenhet som en konsekvens av hvordan PDF plasserer tekst. ISO 32000-1 §9.2.2 og §9.4.4 definerer glyfplassering som vannrett forskyvning langs grunnlinjen i tekstrommet, og de eneste loddrette metrikkene filen bærer, er per font: oppføringene Ascent, Descent og FontBBox i fontbeskrivelsen i §9.8.1. Ingenting i filen sier at to glyfer deler en linje; det må utledes fra geometrien, og de trange glyfboksene som får markeringsutheving til å se riktig ut, slik det er beskrevet i tekstlinjemarkering med PDFium-tegnbokser, er feil inndata for en senteravstandssammenligning

Rettelsen i versjon 3.117.0 endrer spørsmålet fra «hvor langt fra hverandre ligger sentrene» til «hvor mye overlapper boksene loddrett». Celletekst settes sammen ved først å gruppere cellens ord i visuelle linjer, der et ord slutter seg til en linje når den loddrette overlappen med linjens løpende avgrensning er minst 25 prosent av den minste av de to høydene, deretter innsettingssortere hver linje på venstrekant, og til slutt føye linjene sammen med et linjeskift. «Purpose» og «of» overlapper over hele x-høyden, som er langt mer enn 25 prosent av den korteste boksen, så de lander på samme linje og sorteres på X som tiltenkt

Grupper tekstlinjer etter overlapp, ikke etter senteravstand

Regelen som er verdt å ta med seg fra denne feilen, er generell: enhver PDF-tekstlayoutkode som avgjør «samme linje» ved å sammenligne loddrette sentre mot en fast toleranse, vil feile på ekte fonter, og feilen er stille: ingenting feiler, ordene kommer bare ut i feil rekkefølge. Blandede underlengder er den mildeste utløseren. En fet etikett på 12 punkter ved siden av verdier i 10 punkter, en hevet fotnotemarkør, et valutasymbol hentet fra en reservefont, og OCR-ordbokser med høydevariasjon per ord flytter alle sentrene mer enn noen toleranse som fortsatt skiller tilstøtende linjer med 10-punktstekst og 12 punkters linjeavstand. Overlappsforholdet er størrelsesinvariant: to bokser på samme grunnlinje overlapper over den delte x-høyden uansett hva ascenderne og descenderne deres gjør, og to bokser på tilstøtende linjer overlapper ikke i det hele tatt

Den samme regelen er lett å bruke utenfor tabelluttrekk. TPdf.PageWordBoxes returnerer hvert ord på den aktive siden med rektangelet sitt i siderommet, så å gruppere en side i visuelle linjer er en kort løkke:

uses
  Math, PDFium;

function SameVisualLine(const A, B: TPdfRectangle): Boolean;
var
  Overlap, MinHeight: Double;
begin
  Overlap := Min(A.Top, B.Top) - Max(A.Bottom, B.Bottom);
  MinHeight := Min(A.Top - A.Bottom, B.Top - B.Bottom);
  Result := (MinHeight > 0) and (Overlap >= MinHeight * 0.25);
end;

procedure GroupPageIntoLines(Pdf: TPdf; out Lines: TArray<TPdfWordBoxes>);
var
  Words: TPdfWordBoxes;
  Bounds: TArray<TPdfRectangle>;   // løpende union per linje
  I, J, Found: Integer;
begin
  Words := Pdf.PageWordBoxes;
  Lines := nil;
  Bounds := nil;
  for I := 0 to High(Words) do
  begin
    Found := -1;
    for J := High(Lines) downto 0 do
      if SameVisualLine(Bounds[J], Words[I].Rect) then
      begin
        Found := J;
        Break;
      end;
    if Found < 0 then
    begin
      SetLength(Lines, Length(Lines) + 1);
      SetLength(Bounds, Length(Bounds) + 1);
      Found := High(Lines);
      Bounds[Found] := Words[I].Rect;
    end;
    SetLength(Lines[Found], Length(Lines[Found]) + 1);
    Lines[Found][High(Lines[Found])] := Words[I];
    Bounds[Found].Left := Min(Bounds[Found].Left, Words[I].Rect.Left);
    Bounds[Found].Right := Max(Bounds[Found].Right, Words[I].Rect.Right);
    Bounds[Found].Top := Max(Bounds[Found].Top, Words[I].Rect.Top);
    Bounds[Found].Bottom := Min(Bounds[Found].Bottom, Words[I].Rect.Bottom);
  end;
  // sorter hver linje på Rect.Left før du leser den; PageWordBoxes returnerer
  // ord i innholdsstrømsrekkefølge, som ikke er garantert å være visuell
end;

Hva endres for eksisterende kallere, og hvor grensene ligger

Poenget med det utsnittet er predikatet, ikke løkken; for noe ut over en rask dump bør du starte fra den strukturerte tekstmodellen, som allerede bærer blokker, linjer og en kilde for leserekkefølge, slik det er dekket i strukturert PDF-tekstuttrekk med leserekkefølge. Eksisterende tabellkallere får alle tre rettelsene uten å røre alternativene sine. Korridorterskelen er fastsatt til halvparten av MinColumnGap, mellomromsstrategien beholder grensen på to rader selv når MinRows settes til 1 (noe den linjebaserte strategien nå godtar), og filtreringen av ord som det linjebaserte passet tok først, er ubetinget når begge strategiene er slått på. På utvalget med 13 dokumenter som ble brukt for utgivelsen, hadde mellomromspasset tidligere returnert 34 fragmenter og falske treff ved siden av 9 linjebaserte tabeller; etter utgivelsen returnerer det ingen, og antallet linjebaserte tabeller steg til 41, selv om mesteparten av den økningen kommer fra at den samme utgivelsen lærte den linjebaserte detektoren å lese rammer tegnet som fylte rektangler, som er en egen historie

De ærlige grensene: korridortesten trenger minst én rad med innhold på begge sider av en grense for i det hele tatt å avvise noe, så en kandidat med to rader der de to strukne mellomrommene tilfeldigvis faller innenfor 6 punkter fra hverandre, går fortsatt gjennom. Det er et smalt sammentreff og ikke den nære vissheten det var før, men prosatunge dokumenter uten ekte tabeller med to rader kan lukke det ved å sette MinRows til 3. Venstrejustert, ujevn tekst var aldri problemet og påvirkes ikke. Og PDF har fortsatt ikke noe tabellobjekt; ISO 32000-1 §14.8.4.3 definerer et Table-strukturelement, men bare Tagged PDF bærer det, så for alt annet forblir rutenettet en slutning fra geometrien, og konfidensverdien på hver TPdfTable er der fordi slutninger fortjener en poengsum

Tabelluttrekk, strukturert tekst og ordbokser leser alle fra den samme sidemodellen i Delphi, C++Builder og Lazarus; hele API-et, inkludert TPdfTableExtractionOptions og demoen TableExtractionLab som leveres sammen med det, er beskrevet på siden for PDFium Component for Delphi