DE602005002473T2

DE602005002473T2 - Verfahren zum Erkennen von semantischen Einheiten in einem elektronischen Dokument

Info

Publication number: DE602005002473T2
Application number: DE602005002473T
Authority: DE
Inventors: Serge Bronstein
Original assignee: PDFlib GmbH
Current assignee: PDFlib GmbH
Priority date: 2005-07-01
Filing date: 2005-07-01
Publication date: 2008-01-10
Anticipated expiration: 2025-07-02
Also published as: EP1739574B1; US7705848B2; EP1739574A1; ATE373274T1; US20070002054A1; DE602005002473D1

Description

Die vorliegende Erfindung betrifft ein Verfahren zum Erkennen von semantischen Einheiten oder Wörtern in einem elektronischen Dokument, und insbesondere in einem Dokument, das in einer Seitenbeschreibungssprache beschrieben ist.
Zusätzlich zum Erzeugen von physikalischen Wiedergaben von digitalen Dokumenten, z. B. Papierausdrucken, spielt das Austauschen und Archivieren der digitalen Dokumente selbst eine zunehmende Rolle bei der geschäftlichen sowie bei der privaten Kommunikation. Um den Austausch zu ermöglichen und einen universalen Zugriff ohne Rücksicht auf das Computersystem und die Anwendung bereitzustellen, werden allgemeine Seitenbeschreibungssprachen anstatt von Textverarbeitungs-eigenen Formaten zum Austausch von digitalen Dokumenten verwendet. Um den Textinhalt von digitalen Dokumenten zur Archivierung, Indizierung, zum Suchen, Editieren und zu anderen Zwecken zu verwenden, die nicht das Erzeugen einer visuellen Wiedergabe der Seite betreffen, ist es wünschenswert, die logische (Lese-) Reihenfolge des Textes sowie semantische Einheiten (Wörter natürlicher Sprachen) zu erkennen.
Seitenbeschreibungssprachen wie z. B. das übertragbare Dokumentenformat (Portable Document Format; PDF), PostScript und PCL stellen die Semantik von einzelnen Textzeichen sowie deren Position auf der Seite bereit. Sie übermitteln jedoch im Allgemeinen nicht Informationen über Wörter und andere semantische Einheiten. Die Fragmente, die den Text auf einer Seite aufweisen, können einzelne Zeichen, Silben, Wörter, Zeilen oder eine beliebige Mischung davon enthalten, ohne explizite Kennzeichen, die den Beginn oder das Ende eines Wortes markieren.
Zu allem Übel kann die Reihenfolge der Textfragmente auf der Seite anders als die logische (Lese-) Reihenfolge sein. Es gibt keine Regeln für die Reihenfolge, in der Textabschnitte auf der Seite angeordnet werden. Z. B. könnte eine Seite, die zwei Textspalten enthält, durch Erzeugen der ersten Zeile in der linken Spalte gefolgt von der ersten Zeile der rechten Spalte, der zweiten Zeile der linken Spalte, der zweiten Zeile der rechten Spalte usw. hergestellt werden. Die logische Reihenfolge erfordert jedoch, dass sämtlicher Text der linken Spalte verarbeitet wird, bevor der Text der rechten Spalte verarbeitet wird. Das Extrahieren von Text aus derartigen Dokumenten durch einfaches Wiedergeben der Befeh le der Seitenbeschreibungssprache und das Speichern der Zeichen, anstatt sie auf einer sichtbaren Seite wiederzugeben, liefert im Allgemeinen unerwünschte Ergebnisse, da die logische Struktur des Textes verloren geht.
In der nachfolgenden Beschreibung werden die Begriffe "Zeichen" und "Glyphe" verwendet. Es ist wichtig, beide Konzepte zu unterscheiden.

Zeichen sind die kleinste Einheit, die Daten in einer Sprache übermitteln. Übliche Beispiele sind die Buchstaben des lateinischen Alphabets, chinesische Ideogramme und japanische Silben. Zeichen können eine Bedeutung innehaben, sie sind semantische Einheiten. Der Unicode-Standard kodiert Zeichen. Glyphen sind unterschiedliche graphische Varianten, die ein oder mehrere bestimmte Zeichen darstellen. Glyphen haben ein Erscheinungsbild, sie sind darstellerische Einheiten. Zeichensätze werden verwendet, um visuelle Darstellungen von Glyphen zu erzeugen (siehe untenstehende Beschreibung der Glyphenmetriken).

Es gibt keine Eins-zu-eins-Beziehung zwischen Zeichen und Glyphen. Zum Beispiel ist eine Ligatur ein einzelner Glyph, der zwei oder mehreren separaten Zeichen entspricht.
Seitenbeschreibungssprachen wie z. B. PDF bieten eine Vielzahl von Operatoren zum Anordnen von Text auf der Seite. Die Reihenfolge des Textes und die Gruppierung von Glyphen in Fragmente liegt vollständig in der Hand der Anwendung, die das PDF erzeugt. Das PDF-Dateiformat gibt weder eine bestimmte Reihenfolge der Textinhalte vor, die von einer Seite umfasst sind, noch garantiert es eine solche. Obwohl PDF die Treue der letztendlichen visuellen Darstellungsseite garantiert, kann ein bestimmtes visuelles Ergebnis durch viele unterschiedliche Kombinationen von Seitenkennzeichnungsoperatoren erreicht werden.
Einige dieser Kombinationen können auf die logische (Lese-) Reihenfolge des Textes bezogen sein, während andere die logische Reihenfolge stören oder sogar umkehren können. Als ein Beispiel könnte der Text "This Time", der in 8 dargestellt ist, durch die folgende Abfolge in der Seitenbeschreibung erzeugt werden, die zufällig den Text in seiner logischen Reihenfolge enthält, und sogar ein Leerzeichen zwischen den Wörtern umfasst. In dem PDF-Kontext werden die x/y-Koordinaten von dem Td-Operator interpretiert, wohingegen der Text (jeweils durch den Operator Tj interpretiert wird:
50 700 Td (This)Tj (time)Tj
In dieser Situation wäre das Extrahieren von Text und das Erkennen von Wortgrenzen eine triviale Aufgabe. Das exakt selbe visuelle Ergebnis jedoch könnte ebenfalls durch die nachfolgende Sequenz in der Seitenbeschreibung erzeugt werden:
102 700 Td (time)Tj –52 0 Td (This)Tj
Obwohl die visuelle Seite identisch aussieht, erscheinen die Wörter, die den Text enthalten, in umgekehrter Reihenfolge in der Seitenbeschreibung und ein Leerzeichen zwischen den Wörtern ist nicht mehr vorhanden.
In der nächsten Kombination gibt es überhaupt keine Wörter mehr, die direkt in der Seitenbeschreibung erkannt werden könnten, obwohl die visuelle Ausgabe immer noch exakt dieselbe ist:
134 700 Td (e)Tj –20 0 Td (m)Tj –5.32 0 Td (i)Tj –6.68 0 Td (t)Tj
–18.664 0 Td (s)Tj –5.336 0 Td (i)Tj –13.336 0 Td (h)Tj –14.664 0 Td (T)Tj
Nicht nur sind keine erkennbaren Wörter mehr vorhanden, sondern auch die Lesereihenfolge der Zeichen, die die beiden Wörter umfassen, ist tatsächlich umgekehrt.
Um die Sache zu verschlimmern können beliebige Mischungen von derartigen Ausgabereihenfolgeschemata in einem elektronischen Dokument vorhanden sein. Obwohl es zwecklos erscheinen mag, eine derartige Ausgabe zu erzeugen, ist sie in der Tat sehr üblich aufgrund der Eigenschaften der Software, die die Ausgabe erzeugt. Z. B. kann ein Produkt zuerst alle Textfragmente auf der Seite erzeugen, die in einem Zeichensatz gedruckt werden, und anschließend mit allen Textfragmenten in dem zweiten Zeichensatz fortfahren usw. Ein anderes Produkt könnte durch sämtliche Textfragmente in Abhängigkeit ihrer Farbe vorgehen (zuerst alle schwarzen Fragmente, anschließend alle roten Fragmente usw.). Noch ein anderes Produkt könnte eine Ausgabe gemäß der Reihenfolge erzeugen, in der eine Person den Text getippt und editiert hat: ein Wort, das zu der ersten Zeile hinzugefügt worden ist, nachdem viele Zeilen eingetippt worden sind, könnte später in der Seitenbeschreibung erscheinen als der Rest der ersten Zeile.
EP-0 702 322-B1 beschreibt ein System und ein Verfahren zum Erkennen von Wörtern in einem übertragbaren elektronischen Format durch folgende Schritte: Empfangen eines Textsegments von einer Seite eines Dokuments mit vielfachen Textsegmenten und zugehöriger Positionsdaten einschließlich x- und y-Koordinaten für jedes Textsegment, Erzeugen eines Textobjektes für jedes Textsegment, Eingeben der Textobjekte in eine verbundene Liste und Erkennen von Wörtern aus der verbundenen Liste durch Untersuchung der Textobjekte auf Wortgrenzen und durch Untersuchung von Zwischenräumen zwischen Textobjekten und der Verwendung der zugehörigen Positionsdaten.
Das darin beschriebene Verfahren ergibt jedoch in vielen Fällen schlechte Ergebnisse aufgrund der nachfolgenden Gründe. Dokumente mit einer anspruchsvolleren Struktur als Dokumente mit mehreren Spalten werden aufgrund der Tatsache nicht korrekt verarbeitet, dass Wörter, die zu einer Spalte gehören, nicht in der korrekten semantischen Reihenfolge kopiert sind, woraus falsche Ergebnisse resultieren. Ein weiteres Problem des oben erwähnten Dokumentes ist dessen Unfähigkeit, gesperrt gedruckte Zeichen als eine verbundene semantische Einheit zu erkennen.
Hui Chao et al. beschreiben in "Layout and content extraction for PDF dokuments" DOCUMENT ANALYSIS SYSTEMS VI. 6^th INTERNATIONAL WORKSHOP, DAS 2004. PROCEEDINGS (LECTURE NOTES IN COMPUT. SCI. VOL. 3163), SPRINGER-VERLAG BERLIN, DEUTSCHLAND 2004, S. 213–224, einen Weg, logische Komponenten und ihre zugehörigen Layouts zu erkennen und den Inhalt der Bestandteile in einem PDF-Dokument zu extrahieren. Sie erwähnen Techniken, die automatisch eine PDF-Dokumentenseite in verschiedene logische Strukturbereiche wie zum Beispiel Textblöcke, Bildblöcke, Vektorgraphik-Blöcke und Verbund-Blöcke segmentieren. Zur Textextraktion wird das Verfahren gemäß dem oben erwähnten Dokument EP-0 702 322-A2 verwendet. Die Ergebnisse werden im XML-Format ausgedrückt.
Es ist deshalb die Aufgabe der vorliegenden Erfindung, ein schnelles, zuverlässiges und fehlerfreies Verfahren zum Rekonstruieren der semantischen Inhalte einer Seite und zum Gruppieren von Zeichen in semantische Einheiten (Wörter) bereitzustellen, um die Verar beitung der Textinhalte von digitalen Dokumenten zum Editieren, Suchen und zu ähnlichen Aufgaben zu erleichtern.
Diese Aufgabe wird durch die Merkmale des Anspruchs 1 gelöst.
Erfindungsgemäß umfasst das Verfahren zum Erkennen von Wörtern in einem elektronischen Dokument folgende Schritte:

a) Bereitstellen eines elektronischen Dokuments, das in einer Seitenbeschreibungssprache beschrieben ist, wobei das Dokument mindestens eine Seite mit einer Mehrzahl von Textfragmenten aufweist, wobei jedes Textfragment eine Mehrzahl von Glyphen umfasst, die nicht als semantische Einheiten identifiziert sind, wobei das Dokument des Weiteren geometrische Daten einschließlich der Position und der Breite aller Textfragmente auf der Seite und Seitenbeschreibungssprachenparameter wie z. B. Zeichensatzgröße, Zeichenabstand, Textverzerrung aller Glyphen umfasst;
b) Bestimmen eines Streifens als eine geometrische Fläche mindestens einer Glyphe durch Vergleichen der geometrischen Position jeder Glyphe mit der nachfolgenden Glyphe in der Seitenbeschreibung, wobei je zwei Glyphen als Teil eines Streifens betrachtet werden, wenn die Differenz ihrer vertikalen Koordinaten kleiner als ein erster vorbestimmter Wert ist, und wenn die Differenz ihrer horizontalen Koordinaten größer als Null und kleiner als ein zweiter vorbestimmter Wert ist;
c) Bestimmen einer Zone aus mindestens einem Streifen, wobei eine Zone durch die Kombinierte Fläche von Streifen definiert ist, die miteinander überlappen;
d) Bestimmen einer möglichen Grenze zwischen zwei semantischen Einheiten aus Glyphen in einer Zone, um Glyphen in semantische Einheiten zu kopieren, mit den folgenden Schritten:
i) Definieren einer Liste von Glyphen in einer Zone gemäß ihrer Anordnung in der Seitenbeschreibung mit zugehörigen Zeichensatzeigenschaften und geometrischer Position,
ii) Erkennen des Vorliegens einer möglichen Grenze zwischen semantischen Einheiten zwischen zwei Glyphen, wenn die Differenz zwischen der vertikalen Koordinate einer ausgewählten Glyphe und der vertikalen Koordinate der vorhergehenden Glyphe größer als ein dritter vorbestimmter Wert ist, und/oder
iii) Definieren einer Leerzeichen-Box von rechteckiger Form für jede Zeichensatz-Codier-Kombination, die in dem Dokument verwendet wird, wobei die breite der Leerzeichen-Box als die Breite einer existierenden oder hypothetischen Leerzeichenglyphe für die entsprechende Zeichensatzgröße definiert ist, und Erkennen des Vorliegens einer möglichen Grenze zwischen semantischen Einheiten, wenn der Abstand zwischen einer ausgewählten Glyphe und der vorhergehenden Glyphe gleich der Breite der Leerzeichen-Box ist oder sie um einen vierten vorbestimmten Wert überschreitet, wobei dadurch eine mögliche semantische Einheit bestimmt wird, und
iv) Wiederholen der Schritte i) bis iii) bis das Ende der Glyphenliste erreicht ist,
e) Sortieren der erkannten möglichen semantischen Einheiten in der Zone entsprechend der vertikalen Position und, falls sich die vertikalen Positionen um höchstens einen fünften vorbestimmten Wert unterscheiden, entsprechend der horizontalen Position, wodurch eine sortierte Liste möglicher semantischer Einheiten bereitgestellt wird,
f) Verarbeiten der sortierten Liste von möglichen semantischen Einheiten durch Kombinieren zweier möglicher semantischer Einheiten, wenn der Abstand zwischen der letzten Glyphe einer ersten möglichen semantischen Einheit und der ersten Glyphe der nächsten möglichen semantischen Einheit kleiner ist als die Summe der Breite der Leerzeichen-Box und einem sechsten vorbestimmten Wert, bis das Ende der Liste erreicht ist, wobei dadurch eine sortierte Liste von endgültig erkannten semantischen Einheiten in der Zone bestimmt wird; und
g) Wiederholen der Schritte d) bis f) bis alle Zonen verarbeitet sind.

Bevorzugte Ausführungsführungsformen der Erfindung sind in den Unteransprüchen beschrieben.
Weitere Aufgaben, Merkmale und Vorteile der Erfindung werden aus der ausführlichen Beschreibung der bevorzugten Ausführungsform und den beigefügten Zeichnungen deutlich.
1 zeigt eine schematische Darstellung allgemeiner Glyphenmetriken;
2 zeigt eine schematische Darstellung, die die Zeichensatzgröße eines bestimmten Zeichensatzes veranschaulicht;
3 zeigt ein Flussdiagramm, das die Hauptschritte eines bevorzugten Verfahrens zum Erkennen semantischer Einheiten in einem elektronischem Dokument gemäß der Erfindung veranschaulicht;
4 zeigt ein Flussdiagramm, das die detaillierten Ablaufschritte zum Erzeugen von Streifen in Schritt 14 aus 3 darstellt;
5 zeigt ein Flussdiagramm, das die detaillierten Ablaufschritte zum Erzeugen von Zonen in Schritt 16 aus 3 darstellt;
6 zeigt ein Flussdiagramm, das die ausführlichen Ablaufschritte zum Bestimmen von Wortgrenzen und für das Zonen-Aufräumen in Schritt 18 aus 3 darstellt;
7 zeigt ein Flussdiagramm, das im größeren Detail die Ablaufschritte zum Bestimmen von Wortgrenzen in Schritt 102 aus 6 darstellt;
8 zeigt die graphischen Details beispielhafter semantischer Einheiten ohne zusätzlichen Zeichenabstand; und
9 zeigt die graphischen Details einer weiteren beispielhaften semantischen Einheit mit großem Zeichenabstand.
Glyphenmetriken
In 1 und 2 werden allgemeine Glyphenmetriken, die im erfindungsgemäßen Verfahren verwendet werden, veranschaulicht.
Wie in 1 gezeigt weist jede Glyphe auf der Seite eine Position (x, y), die an ihrem Anfangspunkt gemessen wird, und eine Glyphenbreite w auf, die aus der Zeichensatzmetrik und den Textparametern abgeleitet wird. Der Winkel "alpha" ist der Winkel der Textgrundlinie, auf die sich die Glyphe stützt. Im Gegensatz zu dem in 1 gezeigten Beispiel wird "alpha" in den meisten Fällen 0° betragen, d. h. die Glyphe wird in einer Zeile horizontal auf der Seite angezeigt. Das Anlegen der Breite w bei (x, y) in Richtung von "alpha" ergibt den Endpunkt (x', y'). Da ein Zeichenabstand c bestimmt sein könnte, um den Zwischenraum zwischen den Glyphen zu erhöhen oder zu vermindern, ist der Endpunkt (x', y') der vorhergehenden Glyphe nicht notwendigerweise identisch mit dem Anfangspunkt der nächsten Glyphe. Der Zeichenabstand c kann für jede Glyphe individuell eingestellt werden (z. B. um Kerning zu erzielen oder engere Abstände für bestimmte kritische Paare, wie z. B. "Ty" in einigen Zeichensätzen), oder er kann auf alle Glyphen in einem Wort angewendet sein, um das Wort zu betonen (positiver Zeichenabstand) oder Platz in dem Layout zu sparen (negativer Zeichenabstand). Alle für die Glyphenmetrik erforderlichen Werte können auf der Seitenbeschreibung durch Anwenden von Verfahren abgeleitet werden, die dem einschlägigen Fachmann hinreichend bekannt sind.
Unter Bezugnahme auf 2 ist die Zeichensatzgröße dargestellt, wie sie in den Post-Script- und PDF-Seitenbeschreibungssprachen definiert ist: die Zeichensatzgröße kann nicht direkt bei einer bestimmten Glyphe gemessen werden. Stattdessen wird die Zeichensatzgröße als der Minimalabstand zwischen aneinandergrenzenden Grundlinien genommen, wodurch gewährleistet ist, dass Unterlängen in der ersten Zeile sich nicht mit Oberlängen in der zweiten Zeile überlappen. Obwohl das Verhältnis der Zeichensatzgröße und der Oberlängen/Unterlängen zeichensatz-spezifisch ist und Designentscheidungen unterliegt, wird es im Allgemeinen derart gewählt, dass extreme Oberlängen (z. B. Ä) extreme Unterlängen berühren (z. B. j, g), wenn der Abstand zwischen den Grundlinien exakt der Zeichensatzgröße entspricht (d. h. dass weder eine Überlappung noch einen weißen Leerraum zwischen den Unterlängen und Oberlängen vorhanden sein wird). In der Folge weisen im Allgemeinen alle Glyphen in einem Zeichensatz eine Höhe auf, die erheblich kleiner ist, als der Wert der Zeichensatzgröße (typischerweise 60 %–80 %) wie aus 2 ersichtlich ist.
Erfindungsgemäß ist eine Glyphen-Box ein Viereck, dass auf der Grundlinie angeordnet ist, wobei zwei Ecken durch den Start- und Endpunkt der Glyphe bestimmt werden, d. h. die Breite der Glyphen-Box wird durch den Startpunkt der Glyphe und ihren Endpunkt bestimmt. Die Höhe der Glyphen-Box wird durch die Zeichensatzgröße der Glyphe bestimmt, wobei ein bestimmter Korrekturfaktor angewendet werden kann, um einen variierenden Zwischenraum zwischen den Zeilen zu berücksichtigen. Typische Werte für diesen Faktor liegen im Bereich zwischen 1,0 und 2,0. Bei gedrehtem oder verzerrtem Text werden die entsprechenden Dreh- bzw. Verzerrungswinkel ebenfalls auf die Glyphen-Box angewendet.
Erfindungsgemäß wird eine so genannte Leerzeichen-Box für jede Zeichensatz-/Codier-Kombination, die in dem Dokument verwendet wird, berechnet. Die Leerzeichen-Box ist ein Rechteck mit der Zeichensatzgröße als Höhe. Die Breite des Rechtecks basiert auf der Breite einer existierenden oder hypothetischen Leerzeichen-Glyphe für eine gegebene Zeichensatzgröße. Wenn der Zeichensatz eine Leerzeichen-Glyphe enthält, wird deren Breite direkt verwendet, ansonsten wird eine Näherung basierend auf den allgemeinen Eigenschaften des Zeichensatzes berechnet. Die relevanten geometrischen Parameter (wie z. B. horizontale Skalierung und Zeichenabstand) der vorhergehenden Glyphe werden auf die Leerzeichenbreite angewendet, um die Breite der Leerzeichen-Box zu bestimmen. Wenn mehrere Glyphen umfasst sind und eine Leerzeichen-Box erforderlich ist, wird die Leerzeichen-Box gemäß dem Zeichensatz und der Zeichensatzgröße bestimmt, der für die Mehrzahl der Glyphen verwendet wird.
Allgemeines Verfahren
Eine bevorzugte Ausführungsform des erfindungsgemäßen Verfahrens wandelt eine Liste von Glyphen auf der Seite in eine höchst strukturierte Liste von Zonen um, wobei jede Zone eine Liste von Wörtern enthält. Ein exemplarisches erfindungsgemäßes Verfahren setzt sich aus den in 3 dargestellten Schritten zusammen. Details der Schritte werden nachfolgend angegeben.
In Schritt 10 wird eine Liste aller Glyphen auf der Seite zusammen mit ihrer Position auf der Seite ermittelt. Dieser Schritt wird gemäß der zugrunde liegenden Seitenbeschreibungssprache durchgeführt. Es ist vorteilhaft, dass die zugrunde liegende Seitenbeschreibung alle Unicode-Werte für alle Glyphen auf der Seite enthält, da das Bereitstellen sämtlicher Unicode-Werte zu besseren Ergebnissen in dem Gesamtverfahren führt. Die praktische Erfahrung hat jedoch gezeigt, dass es schwer, wenn nicht sogar unmöglich sein kann, 100 % der Unicode-Werte zu ermitteln (da die erforderliche Information in dem Dokument fehlen kann). In jedem Fall liefert das erfindungsgemäße Verfahren auch ohne sämtliche Unicode-Werte ausgezeichnete Ergebnisse.
Der optionale Schritt 12 eliminiert eine oder mehrere Glyphen von aufeinander folgenden Glyphen in der Seitenbeschreibung, die redundanten Text wie z. B. Schatten- oder künstlichen Fettdrucktext darstellen. Die Umsetzung des Schrittes der Schattenentfernung ist Gegenstand verschiedener Studien und bis heute wurden immer mehr ausgereifte Untersuchungen für dieses Problem bereitgestellt. Die vorliegende Erfindung ist nicht auf dieses Problem gerichtet, sondern kann ein beliebiges dem einschlägigen Fachmann bekanntes Verfahren verwenden.
In Schritt 14 wird eine Liste von Glyphen erzeugt. Bei einfachen Seitenaufbauten kann ein Streifen als eine einzelne Textzeile betrachtet werden. Spezielle Details zu Schritt 14 sind nachfolgend aufgelistet.
In Schritt 16 wird eine Liste von Zonen aus der Liste von Streifen erzeugt. Bei einfachen Seitenaufbauten kann eine Zone z. B. als eine einzelne Textspalte betrachtet werden.
In Schritt 18 werden die Inhalte jeder Zone verarbeitet, um Wortgrenzen zu bestimmen (Glyphen in semantische Einheiten gruppieren) und redundanter Inhalt wird beseitigt. Das letztere umfasst die Beseitigung von Schatten- und künstlichem Fettdrucktext und das erneute Zusammenführen von getrennten Wörtern. Das Ergebnis für jede Zone ist eine sortierte Liste von Wörtern auf der Seite.
Eine ausführlichere Beschreibung der Schritte 16 und 18 kann ebenfalls im Folgenden gefunden werden.
Darauf folgend können in Schritt 20 alle Zonen auf der Seite entsprechend ihrer x-/y-Position sortiert werden und damit wird eine Liste von Zonen in Schritt 22 erreicht, die eine sortierte Liste von Wörtern enthält.
Demgemäß wurden alle Wörter auf der Seite erkannt und sortiert.
Erzeugen von Streifen aus Glyphen (Schritt 14)
Ein Streifen ist eine polygonale Fläche auf der Seite, die die Vereinigung aller Glyphen-Boxen umfasst, die den Glyphen in dem Streifen entsprechen. In einer vereinfachten Version kann eine viereckige Zeichen-Box des Streifens anstatt des polygonalen Streifens verwendet werden.
Obwohl die in diesem Schritt erzeugten Streifen selbst keine gebräuchlichen semantischen Einheiten sind, bilden sie die Basis für das Erzeugen von Textzonen auf der Seite.
Das Verfahren des Erzeugens von Streifen setzt sich aus dem in 4 dargestellten Schritten zusammen. Details der Schritte sind im nachfolgenden angegeben.
Das Verfahren beginnt in Schritt 30 mit einer Liste von Glyphen auf der Seite, wobei die Glyphen in der Reihenfolge bereitgestellt werden, in der sie in der Seitenbeschreibung erscheinen. Wie oben erläutert gibt es keine besondere Beziehung zwischen der Glyphenreihenfolge und ihrer Semantik. Zum Beispiel können die Glyphen, die ein Wort bilden, über die Seitenbeschreibung ohne jegliche Beziehung verteilt sein.
In Schritt 32 wird der Zähler n, der die auf der Seite erkannten Streifen zählt, auf 1 gesetzt.
In Schritt 34 wird der Streifen s_n als leerer Streifen initialisiert.
In Schritt 36 wird bestimmt, ob noch mehr Glyphen in der Liste vorhanden sind. Wenn keine Glyphen mehr vorhanden sind, wird das Verfahren bei Schritt 38 angehalten.
Wenn weitere Glyphen in der Liste verfügbar sind, schreitet das Verfahren zu Schritt 40 weiter, wo die nächste verfügbare Glyphe g zugeordnet wird.
In Schritt 42 wird g zu dem Streifen s_n hinzuaddiert.
In Schritt 44 wird erneut bestimmt, ob in der Liste noch mehr Glyphen vorhanden sind. Wenn keine Glyphen mehr vorhanden sind, wird das Verfahren in Schritt 38 angehalten.
Wenn weitere Glyphen in der Liste vorhanden sind, schreitet das Verfahren zu Schritt 46 fort, wobei g p (der vorhergehenden Glyphe) zugeordnet wird, und die nächste verfügbare Glyphe gemäß der Seitenbeschreibung wird erneut g zugeordnet.
In Schritt 48 wird bestimmt, ob p und g basierend auf ihrer Position zu denselben Streifen gehören. Zwei Glyphen p und g werden als Teil desselben Streifens betrachtet, wenn ihre y-Koordinaten dieselben sind oder sich lediglich marginal unterscheiden, definiert durch einen ersten vorbestimmten Toleranzwert, und wenn die x-Koordinate von g größer als die x-Koordinate p ist, d. h. wenn g rechts von p angeordnet ist. Als eine weitere Bedingung darf der horizontale Abstand zwischen p und g nicht zu groß sein, da ansonsten p und g als Teil von verschiedenen Spalten betrachtet würden, und deshalb in unterschiedlichen Streifen enthalten sein müssten. Der obere Toleranzwert (zweiter vorbestimmter Wert) für den horizontalen Abstand zwischen p und g hängt von der Leerzeichen-Box multipliziert mit einem geeigneten Faktor ab. Für übliche Layouts kann der Faktor als 4 gewählt werden. Gedrehte oder verzerrte Glyphen werden auf eine ähnliche Art und Weise verarbeitet wie bei in den Schritten 134 bis 138 beschrieben ist.
Es ist anzumerken, dass für andere Sprachen, die von rechts nach links geschrieben werden wie z. B. Hebräisch und Arabisch, die Verarbeitungsschritte entsprechend angepasst werden, um die unterschiedliche Verarbeitungsrichtung zu berücksichtigen. In diesen Fällen wäre g links von p angeordnet.
Wenn p und g als Teil des gleichen Streifens basierend auf ihrer Position bestimmt sind, geht das Verfahren in der Schleife zurück zu Schritt 42. Die kombinierten Streifeninformationen wie z. B. die Geometrie werden in geeigneter Art und Weise zwischengespeichert. Ansonsten fährt das Verfahren fort zu Schritt 50, der abprüft, ob die Glyphen p und g eine bestimmte geeignete Bedingung für mit Bindestrich geschriebene Wörter erfüllen.
Diese optionale Überprüfung macht die Unicode-Werte, die den Glyphen auf einer Seite entsprechen, erforderlich. Die Bedingung kann je nach natürlicher Sprache ausgewählt werden, die den Text aufweist; eine übliche Bedingung überprüft, ob p gleich dem Bindestrichzeichen ist und g ein in Kleinschrift geschriebenes Zeichen darstellt, da in den meisten Sprachen der Teil eines mit Bindestrich geschriebenen Wortes, das auf die nächste Zeile aufgeteilt ist, nicht mit einem Zeichen in Großschrift beginnt. Die Verwendung einer derartigen Bedingung vermeidet die falsche Klassifizierung von Wörtern, die mit einem Ge dankenstrich-Zeichen (engl. dash) kombiniert sind, da ein mit Bindestrich geschriebenes Wort durch ein Bindestrich-Zeichen (engl. hyphen) getrennt ist. Eine derartige Fehleinteilung könnte auftreten, da in den meisten Seitenbeschreibungssprachen Bindestrich- und das Gedankenstrich- (oder Minus-) -Zeichen nicht zuverlässig erkannt werden können.
Wenn p und g nicht die Bedingungen für mit Bindestrich geschriebene Wörter erfüllen, fährt das Verfahren zu Schritt 54 fort, wo der Zähler n um 1 erhöht wird.
Wenn Schritt 50 festgelegt hat, dass p und g den Bedingungen für mit Bindestrich geschriebene Wörter entsprechen, wird das Paar (p, g) als ein mit Bindestrich geschriebenes Paar in Schritt 52 gekennzeichnet. Das Verfahren fährt anschließend mit Schritt 54 fort.
Von Schritt 54 schreitet das Verfahren erneut zu Schritt 34 fort, um die Glyphen für den nächsten Streifen zu sammeln.
Erzeugen von Zonen aus Streifen (Schritt 16)
Eine Zone ist ein polygonaler Bereich auf der Seite. Die Zonenerzeugung basiert auf dem vorherigen Schritt der Streifenerzeugung und kombiniert sequenziell Streifen zu Zonen basierend auf deren geometrischer Nachbarschaft. Das Verfahren setzt sich aus den in 5 dargestellten Schritten zusammen. Die Details der Schritte sind nachfolgend angegeben.
Schritt 60 beginnt mit einer Liste von Streifen, die den Text auf der Seite aufweisen.
Schritt 62 überprüft, ob noch Streifen in der Liste enthalten sind. Wenn keine Streifen mehr verfügbar sind, hält das Verfahren bei Schritt 64 an.
Wenn noch mehr Streifen in der Liste verfügbar sind, wird eine neue leere Zone Z in Schritt 66 erzeugt. In dem nächsten Schritt 68 wird s als der erste Streifen in der Liste definiert.
In dem nächsten Schritt 70 wird der Streifen s aus der Liste von Streifen gelöscht, und in Schritt 72 der Streifen s zu der Zone Z hinzuaddiert.
Schritt 74 bestimmt, ob noch mehr Streifen in der Liste vorhanden sind. Wenn keine Streifen mehr vorhanden sind, hält das Verfahren bei Schritt 64 an.
Wenn Schritt 74 feststellt, dass noch Streifen in der Liste vorhanden sind, fährt das Verfahren zu Schritt 76 fort, wo es sich auf den Beginn der Liste positioniert.
In Schritt 78 wird s als der nächste in der Liste verfügbare Streifen definiert.
Schritt 80 überprüft, ob die Zone Z mit dem Streifen s basierend auf den entsprechenden geometrischen Flächen überlappt. Wenn die Schnittmenge von beiden eine Innenfläche aufweist, die nicht Null ist, wird festgelegt, dass der Streifen teilweise oder vollständig in der Zone Z enthalten ist, und das Verfahren fährt fort bei Schritt 70. Die Berechnung der Schnittmenge der geometrischen Flächen kann gemäß einem dem einschlägigen Fachmann bekannten Verfahren implementiert werden.
Wenn Z und s nicht überlappen, fährt das Verfahren bei Schritt 82 fort, wo bestimmt wird, ob s der letzte Streifen in der Liste war. Wenn ja, so schreitet das Verfahren mit Schritt 66 fort. Wenn s nicht der letzte Streifen in der Liste war, geht das Verfahren mit Schritt 78 weiter.
Aufräumen von Zonen (Schritt 18)
Dieser Teil des Verfahrens verbessert die Inhalte jeder Zone durch die Bestimmung von Wortgrenzen (Gruppieren von Glyphen in semantische Einheiten), durch das Gruppieren und Sortieren der Wörter entsprechend ihrer Position, durch das Eliminieren von redundantem Text und durch das Kombinieren der Bestandteile von mit Bindestrich geschriebenen Wörtern. Dieser Teil des Verfahrens setzt sich aus den in 6 dargestellten Schritten zusammen. Details der Schritte sind nachfolgend angegeben.
Das Verfahren beginnt in Schritt 100 mit einer Zone, die eine Liste von Glyphen auf der Seite enthält, wobei die Glyphen in keiner besonderen Reihenfolgen angegeben sind. Die Zone ist nicht leer, da Schritt 16 mindestens einen Streifen und deshalb mindestens eine Glyphe in jede Zone legt.
Schritt 102 bestimmt die Wortgrenzen entsprechend den in 7 dargestellten und nachfolgend in größerem Detail erläuterten Schritten. Das Ergebnis ist eine Liste von Wörtern und Wortfragmenten, die um die Informationen der Wortanfangs- und Wortendemarkierun gen ergänzt sind. Es ist nicht gewährleistet, dass die Listeninhalte schon vollständige Wörter enthalten, da die Teile eines Wortes über die Seite verteilt sein können und später in Schritt 108 kombiniert werden müssen.
In Schritt 104 werden die Inhalte der Liste gemäß ihrer y-Position sortiert. Zwei Fragmente mit nahezu identischer y-Position werden des Weiteren nach ihrer x-Position sortiert. Ein geeigneter Toleranzwert für die Entscheidung nach dem Vergleich der y-Positionen kann die Hälfte der Zeichensatzgröße sein. Es können sich jedoch andere Werte als für diese Berechnung geeignet erweisen.
In Schritt 106 wird redundanter Text basierend auf Wörtern oder Wortfragmenten nach einem geeigneten bekannten Verfahren entfernt. Obwohl Schatten und andere redundante Textfragmente auf Glyphenbasis bereits in Schritt 12 beseitigt worden sein könnten, ist es erforderlich, den Prozess zum Beseitigen von redundantem Text erneut auszuführen, dieses Mal durch Verarbeitung der Wörter oder Wortfragmente anstatt der Glyphen. Dies ist erforderlich, da in einigen Fällen redundante Fragmente über die Seite verteilt sein können und nur erkannt werden können, nachdem die Wortfragmente sortiert worden sind. Im Gegensatz dazu arbeitet der optionale Schritt 12 mit der unsortierten Liste der Glyphen.
In Schritt 108 werden Wörter und Wortfragmente kombiniert, wenn bestimmt wurde, dass sie aneinander angrenzen. Wenn der Euklidische Abstand zwischen der letzten Glyphe eines Fragments und der ersten Glyphe des nächsten Fragments (möglicherweise unter Berücksichtigung des Zeichenabstandswertes der letzten Glyphe) kleiner ist als die Leerzeichen-Box, dann werden die beiden Fragmente als Teil desselben Wortes betrachtet und kombiniert. Wie oben erläutert ist dieser Schritt erforderlich, da Teile eines Wortes außerhalb der Reihenfolge in der Seitenbeschreibung erzeugt werden können. Übliche Beispiele sind fettgedruckte oder in Farbe gedruckte Wörter, die in einem separaten Schritt nach sämtlichem anderen Text erzeugt werden, und deshalb nicht in der logischen Reihenfolge auf der Seitenbeschreibung erscheinen.
In dem optionalen Schritt 110 werden die Teile von mit Bindestrich getrennten Wörtern kombiniert und das Bindestrich-Zeichen wird entfernt. Um dies zu erreichen, werden alle mit Bindestrich versehenen Glyphenpaare, die in Schritt 52 gekennzeichnet wurden, untersucht, und die Wortfragmente, die die Glyphen des Paares enthalten, werden kombiniert, um ein einzelnes Wort zu bilden.
Als Ergebnis enthält die Zone eine sortierte Liste von Wörtern, wobei entsprechende Bestandteile eines Wortes kombiniert worden sind.
Bestimmen von Wortgrenzen (Schritt 102)
Dieser Abschnitt des Verfahrens bestimmt die Anfangs- und Endmarkierungen für die Wörter, die den Text auf der Seite enthalten, basierend auf der Position von individuellen Glyphen und (optional) den entsprechenden Unicode-Werten.
Das Verfahren setzt sich aus den in 7 dargestellten Schritten zusammen. Details der Schritte sind nachfolgend angegeben.
Das Verfahren beginnt in Schritt 120 mit dem Ermitteln einer Liste von Glyphen mit ihren zugehörigen Koordinaten auf der Seite sowie den entsprechenden Glyphenbreiten und Zeichenabstandswerten.
In Schritt 122 wird p die erste Glyphe in der Liste zugeordnet.
In Schritt 124 wird eine Wortanfangsmarkierung vor p eingefügt.
In Schritt 126 wird bestimmt, ob das Ende der Glyphenliste erreicht ist. Wenn ja, fährt das Verfahren mit Schritt 128 fort.
Schritt 128 fügt eine Wortendemarkierung nach p ein und der Ablauf hält in Schritt 130 an.
Wenn das Ende der Glyphenliste noch nicht in Schritt 126 erreicht ist, wird g die nächste Glyphe in der Liste zugeordnet.
In Schritt 134 werden die Grundlinienwinkel von g und p verglichen. Wenn festgestellt wird, dass sie gleich sind, fährt das Verfahren direkt mit Schritt 138 fort.
Wenn die Grundlinienwinkel von p und g unterschiedlich sind, wird g an seinem Anfangspunkt unter Verwendung des Unterschieds der Grundlinienwinkel von g und p als Drehwinkel gedreht. Als ein Ergebnis sind sowohl p und g in derselben Richtung ausgerichtet. Nach dieser Drehung schreitet das Verfahren zu Schritt 138 fort. In Schritt 138 werden sowohl p als auch g an dem Ursprung unter Verwendung des negativen Wertes des Grundlinientextwinkels von p als Drehwinkel gedreht. Im Ergebnis sind nun sowohl p als auch g horizontal ausgerichtet, d. h. ihr Grundlinientextwinkel ist Null. Als ein Ergebnis der Drehschritte 136 und 138 kann das Verfahren Wortgrenzen sogar für gekrümmten oder gedrehten Text bestimmen.
Das Verfahren geht anschließend weiter mit Schritt 140, wobei bestimmt wird, ob die y-Koordinaten von p und g identisch sind oder sich lediglich um einen kleinen vorbestimmten Betrag (dritter vorbestimmter Wert) unterscheiden. Wenn ja fährt das Verfahren mit Schritt 142 fort. In Schritt 142 wird der Zwischenraum (weißer Leerraum) zwischen p und g als die Differenz der Anfangs-x-Koordinate von g und der End-x-Koordinate von p berechnet. Das Verfahren fährt anschließend mit Schritt 146 fort.
Schritt 146 stellt fest, ob der Zwischenraum zwischen p und g groß genug ist, um als eine Wortgrenze betrachtet zu werden. Um dies zu erreichen, wird der Zwischenraum mit der Summe der Leerzeichen-Box und einem vierten vorbestimmten Wert verglichen, z. B. dem Zeichenabstandswert von p. Die Berücksichtigung des Zeichenabstandes bietet für solchen Text Vorteile, der durch einen großen Zeichenabstand betont wird (üblicherweise in deutschen Zeitungen verwendet), da in diesem Fall der Zwischenraum größer sein muss, um als eine Wortgrenze betrachtet zu werden.
Zwei Textbeispiele sind in den 8 und 9 veranschaulicht. 8 zeigt ein Textfragment ohne zusätzlichen Zeichenabstand, wohingegen 9 ein Textfragment mit zusätzlichem Zeichenabstand zeigt (großer Zeichenabstand). In beiden Figuren sind die Glyphen mit ihren Startpunkten x₁, x₂, ..., x_n bzw. ihren Endpunkten x'₁, x'₂, ..., x_n gekennzeichnet. Sie haben eine Glyphenbreite w₁, w₂ ..., w_n. In den in 8 abgebildeten Fall trennt die Leerzeichen-Box s die Wörter "This" und "Time", wobei s exakt dem Zwischenraum zwischen den beiden Wörtern entspricht. 9 zeigt einen zusätzlichen Zeichenabstand c₁, c₂, ..., c_n zwischen aneinandergrenzenden Glyphen und einen Zwischenraum zwischen den beiden Wörtern, der größer ist als die Summe der Leerzeichen-Box s mit dem Zeichenabstand c_n der letzen Glyphe des ersten Wortes.
Die Verwendung des oben erwähnten Kriteriums ergibt sehr zuverlässige Ergebnisse in beiden Fällen.
Alternativ kann, wenn sämtliche Unicode-Werte verfügbar sind, eine Wortgrenze zwischen p und g basierend auf den Unicode-Werten, die beiden Glyphen entsprechen, festgelegt werden. Das genaue Kriterium für eine Unicode-basierte Wortgrenze ist anwendungsabhängig. Typischerweise wird, wenn p einem Leerzeichen entspricht, eine Wortgrenze erzeugt.
Darüber hinaus können einige Anwendungen ebenfalls eine Wortgrenze erzeugen, wenn g einem Interpunktionszeichen oder einem beliebigen anderem vorbestimmten Trennzeichen entspricht.
Wenn entweder der geometrische oder der Unicode-basierte Wortgrenzentest bestimmt, dass zwischen p und g eine Wortgrenze vorhanden ist, fährt das Verfahren mit Schritt 148 fort. Ansonsten geht das Verfahren zu Schritt 156 über.
Wenn die y-Koordinaten von p und g in Schritt 140 als unterschiedlich bestimmt wurden, fährt das Verfahren zu Schritt 152 fort. Schritt 152 überprüft, ob p und g in Schritt 52 als ein mit Bindestrich geschriebenes Paar gekennzeichnet wurden. Wenn ja, fährt das Verfahren zu Schritt 154 fort. Ansonsten geht das Verfahren mit Schritt 148 weiter.
Schritt 154 entfernt p aus der Liste der Glyphen und das Verfahren geht mit Schritt 156 weiter.
Schritt 156 ordnet g zu p zu und schreitet zu Schritt 126.
Schritt 148 fügt eine Wortendemarkierung nach p ein und fährt mit Schritt 150 fort.
Schritt 150 ordnet g zu p zu und schreitet fort zu Schritt 124.
Als Ergebnis wurden die Wortanfangs- und Wortendemarkierungen erzeugt, um Wortgrenzen zu erkennen.
Die bevorzugte Ausführungsform wie oben beschrieben enthält eine Vielzahl von Schritten, die als teilweise redundant erscheinen mögen. Experimente haben jedoch gezeigt, dass die Anzahl von bestimmten Verarbeitungswiederholungen und die Reihenfolge signifikant die Ergebnisse des erfindungsgemäßen Verfahrens verbessern. Deshalb ist anzumerken, dass, obwohl eine bestimmte Anzahl von Verarbeitungsschritten in der bevorzugten Ausführungsform beschrieben wurde, es vorteilhaft sein kann, einen Verarbeitungsschritt oder mehrere davon je nach Verfeinerung der gewünschten Ergebnisse wegzulassen. Es mag ebenfalls geeignet erscheinen, die wie oben in der bevorzugten Ausführungsform beschriebene Reihenfolge der Verarbeitungsschritte zu verändern, je nach z. B. der Verfügbarkeit von Unicode-Werten für sämtliche Glyphen in einem gegebenen elektronischen Dokument oder dergleichen.
Es versteht sich, dass die vorliegende Erfindung in verschiedenen Formen von Hardware, Software, Firmware, Spezialzweckprozessoren oder einer Kombination daraus implementiert werden kann. In einer Ausführungsform kann die vorliegende Erfindung in Software als ein Anwendungsprogramm implementiert sein, das greifbar auf einem Computerlesbaren Programmspeichermedium verkörpert ist. Das Anwendungsprogramm, dass das erfindungsgemäße Verfahren darstellt, kann auf eine Maschine, die eine beliebige geeignete Architektur aufweist, hochgeladen und von ihr ausgeführt werden.
Nach Angabe der hierin bereitgestellten Lehre der vorliegenden Erfindung ist der einschlägig Fachmann in der Lage, diese und ähnliche Implementierungen oder Konfigurationen der vorliegenden Erfindung zu berücksichtigen.

Claims

Verfahren zum Erkennen semantischer Einheiten in einem elektronischen Dokument, das die folgenden Schritte aufweist: a) Bereitstellen (10) eines elektronischen Dokuments, das in einer Seitenbeschreibungssprache beschrieben ist, wobei das Dokument mindestens eine Seite mit einer Mehrzahl von Textfragmenten aufweist, wobei jedes Textfragment eine Mehrzahl von Glyphen umfasst, die nicht als semantische Einheiten identifiziert sind, wobei das Dokument des weiteren geometrische Daten einschließlich der Position und der Breite alle Textfragmente auf der Seite und Seitenbeschreibungssprachen-Parameter wie zum Beispiel Zeichensatzgröße, Zeichenabstand, Textverzerrung aller Glyphen umfasst, b) Bestimmen (14) eines Streifens als eine geometrische Fläche mindestens einer Glyphe durch Vergleichen (48) der geometrischen Position jeder Glyphe mit der nachfolgenden Glyphe in der Seitenbeschreibung, wobei je zwei Glyphen als Teil eines Streifens betrachtet werden, wenn – die Differenz ihrer vertikalen Koordinaten kleiner als ein erster vorbestimmter Wert ist, und wenn – die Differenz ihrer horizontalen Koordinaten größer als Null und kleiner als einer zweiter vorbestimmter Wert ist, c) Bestimmen (16) einer Zone aus mindestens einem Streifen, wobei eine Zone durch die kombinierte Fläche von Streifen definiert ist, die miteinander überlappen, d) Bestimmen (102) einer möglichen Grenze zwischen zwei semantischen Einheiten aus Glyphen in einer Zone, um Glyphen in semantische Einheiten zu gruppieren, mit den folgenden Schritten: i) Definieren (120) einer Liste von Glyphen in einer Zone gemäß ihrer Anordnung in der Seitenbeschreibung mit zugehörigen Zeichensatz-Eigenschaften und geometrischer Position, ii) Erkennen (140) des Vorliegens einer möglichen Grenze zwischen semantischen Einheiten zwischen zwei Glyphen, wenn die Differenz zwischen der vertikalen Koordinate einer ausgewählten Glyphe und der vertikalen Koordinate der vorhergehenden Glyphe größer als ein dritter vorbestimmter Wert ist, und/oder iii) Definieren (142) einer Leerzeichen-Box von rechteckiger Form für jede Zeichensatz-Kodier-Kombination, die in dem Dokument verwendet wird, wobei die Breite der Leerzeichen-Box als die Breite einer existierenden oder hypothetischen Leerzeichenglyphe für die entsprechende Zeichensatzgröße definiert ist, und Erkennen (146) des Vorliegens einer möglichen Grenze zwischen semantischen Einheiten, wenn der Abstand zwischen einer ausgewählten Glyphe und der vorhergehenden Glyphe gleich der Breite der Leerzeichen-Box ist oder sie um einen vierten vorbestimmten Wert überschreitet, wobei dadurch eine mögliche semantische Einheit bestimmt wird, und iv) Wiederholen der Schritte i) bis iii), bis das Ende der Glyphenliste erreicht ist, e) Sortieren (104) der erkannten möglichen semantischen Einheiten in der Zone entsprechend der vertikalen Position und, falls sich die vertikalen Positionen um höchstens einen fünften vorbestimmten Wert unterscheiden, entsprechend der horizontalen Position, wodurch eine sortierte Liste möglicher semantischer Einheiten bereitgestellt wird, f) Verarbeiten (108) der sortierten Liste von möglichen semantischen Einheiten durch Kombinieren zweier möglicher semantischer Einheiten, wenn der Abstand zwischen der letzten Glyphe einer ersten möglichen semantischen Einheit und der ersten Glyphe der nächsten möglichen semantischen Einheit kleiner ist als die Summe der Breite der Leerzeichen-Box und einem sechsten vorbestimmten Wert, bis das Ende der Liste erreicht ist, wobei dadurch eine sortierte Liste von endgültig erkannten semantischen Einheiten in der Zone bestimmt wird, und g) Wiederholen der Schritte d) bis f), bis alle Zonen verarbeitet sind.
Verfahren zum Erkennen semantischer Einheiten nach Anspruch 1, wobei Schritt a) des Weiteren das Bereitstellen eines elektronischen Dokuments aufweist, das geeignete Unicode-Werte für alle Glyphen aufweist.
Verfahren zum Erkennen semantischer Einheiten nach Anspruch 2, wobei Schritt d) des Weiteren das Klassifizieren der Unicode-Werte jeder Glyphe und das Erkennen (146) des Vorliegens einer Grenze zwischen semantischen Einheiten in einer Abfolge einer ersten, zweiten und dritten Glyphe zwischen der ersten und der dritten Glyphe umfasst, sofern ein Unicode-Wert der zweiten Glyphe eine Grenze zwischen semantischen Einheiten bedeutet.
Verfahren zum Erkennen semantischer Einheiten nach Anspruch 2, das des Weiteren den Schritt des Erkennens (50, 52, 110, 152) einer ersten und einer zweiten Glyphe als Teil einer semantischen Einheit aufweist, wenn die erste Glyphe ein Unicode-Wert ist, der ein Trennzeichen wie zum Beispiel einen Trennstrich darstellt, und die zweite Glyphe einen Kleinbuchstaben darstellt.
Verfahren zum Erkennen semantischer Einheiten gemäß einem der vorhergehenden Ansprüche, das weiterhin zwischen den Schritten d) i) und d) ii) folgende Schritte aufweist: Vergleichen (134) der beiden Grundlinien-Winkel einer ausgewählten und einer folgenden Glyphe, und Drehen (136) der folgenden Glyphe, wenn beide Grundlinien-Winkel unterschiedlich sind, um einen Winkel, der durch die Differenz zwischen beiden Grundlinien-Winkeln bestimmt wird.
Verfahren zum Erkennen semantischer Einheiten gemäß einem der vorgehenden Ansprüche, wobei in Schritt d) iii), der die Leerzeichen-Box definiert, das Anwenden des Zeichenabstandwertes der vorhergehenden Glyphe auf die Breite einer existierenden oder hypothetischen Leerzeichen-Glyphe umfasst.
Verfahren zum Erkennen semantischer Einheiten gemäß einem der vorhergehenden Ansprüche, wobei in Schritt d) iii) der Abstand zwischen einer ausgewählten Glyphe und der vorhergehenden Glyphe zwischen einem Anfangspunkt der ausgewählten Glyphe und einem Endpunkt der vorhergehenden Glyphe berechnet wird.
Verfahren zum Erkennen semantischer Einheiten gemäß einem der vorhergehenden Ansprüche, wobei Schritt d) iii) des Weiteren das Einfügen (124) einer Anfangsmarkierung vor der vorausgehenden Glyphe und das Einfügen (128, 148) einer Endmarkierung nach der vorausgehenden Glyphe je nach Ergebnis der Grenzerkennung umfasst.
Computerlesbare Programmspeichervorrichtung, die konkret ein Programm von Befehlen verkörpert, die von dem Computer ausführbar sind, und Verfahrensschritte zum Erkennen semantischer Einheiten in einem portierbaren elektronischen Dokument gemäß einem der vorhergehenden Ansprüche durchzuführen.