DE69525401T2

DE69525401T2 - Verfahren und Gerät zur Identifikation von Wörtern, die in einem portablen elektronischen Dokument beschrieben sind

Info

Publication number: DE69525401T2
Application number: DE69525401T
Authority: DE
Inventors: Robert M. Ayers; Mohammed Daryoush Paknad
Original assignee: Adobe Systems Inc
Current assignee: Adobe Inc
Priority date: 1994-09-12
Filing date: 1995-06-08
Publication date: 2002-11-21
Anticipated expiration: 2015-06-09
Also published as: DE69525401D1; JPH08249329A; EP0702322A2; EP0702322B1; CA2153377A1; EP0702322A3; US5832530A

Description

Die vorliegende Erfindung betrifft allgemein die Bearbeitung von digital gespeicherten Objekten, und insbesondere ein Verfahren und eine Einrichtung zum Identifizieren von Worten aus codierten Objekten in einer Anzeigedatei.
Zeichen, Worte und andere Objekte können in Dateien effizient als höherer Code bzw. Hochpegelcode gespeichert werden, wobei jeder Code ein Objekt darstellt. Die Zeichen oder anderen Objektcodes können unter Verwendung eines auf dem Computer laufenden Anwendungssoftwareprogramms angezeigt, editiert oder anderweitig bearbeitet werden. Wenn die Zeichen mit einer Ausgabeeinrichtung wie beispielsweise einem Drucker oder einem Bildschirm angezeigt werden, können die Zeichencodes als Bitmaps und/oder Pixelmaps wiedergegeben und als eine Anzahl von Pixeln dargestellt werden. Ein Pixel ist ein grundlegendes Bildelement eines Bildes und bei einer Bitmap handelt es sich um eine Datenstruktur.
Es gibt verschiedene Möglichkeiten, ein codiertes Objekt anzuzeigen. Eine Rasterausgabeeinrichtung, wie beispielsweise ein Laserdrucker oder ein Computermonitor, erfordert üblicherweise eine Bitmap des codierten Objekts, welche zur Anzeige auf einem Drucker oder Bildschirm in eine Pixelmap eingefügt werden kann. Eine Rasterausgabeeinrichtung erzeugt ein Bild, indem es das in Zeilen und Spalten angeordnete Pixelarray aus der Pixelmap anzeigt. Eine Möglichkeit, die Bitmap des codierten Objektes zur Verfügung zu stellen, ist es, für jeden möglichen Code eine Ausgabebitmap im Speicher zu speichern. Z. B. kann bei Zeichen in Zeichensätzen darstellendem Code jedem Zeichen des Zeichensatzes für jede ggf. benötigte Größe des Zeichensatzes eine Bitmap zugeordnet werden. Die Zeichencodes und die Zeichensatzgröße werden verwendet, um auf die Bitmaps zuzugreifen. Dieses Verfahren ist jedoch sehr ineffizient, da es dazu neigt, eine große Menge Peripherie- und Hauptspeicher zu erfordern. Eine andere Methode ist es, einen jedem Zeichencode zugeordneten Zeichenumriß (charakter outline) zu verwenden und eine Bitmap eines Zeichens aus dem Zeichenumriß und anderen Zeicheninformationen, wie beispielsweise Zeichensatz und Größe, wiederzugeben. Der Zeichenumriß kann die Form des Zeichens angeben und erfordert viel weniger Speicherplatz als die viele Größen darstellende Vielzahl von Bitmaps. Die Zeichen können daher in einer Seitenbeschreibungsdatei gespeichert werden, die die Zeichencodes, Zeichensatzinformationen, Größeninformationen u. s. w. enthält. Zu den zur Berechnung von Bitmaps aus Zeichenumrissen verwendeten Seitenbeschreibungssprachen gehören die beiden von Adobe Systems Inc., Mountain View, Kalifornien, entwickelten Portable-Document-Format(PDF)-Sprache und die PostScript®- Sprache. Zeichenumrisse können durch Standardformate, wie beispielsweise das Format Type 1® von Adobe Systems Inc., beschrieben werden.
Portable elektronische Dokumente, wie beispielsweise in der PDF-Sprache gespeicherte Dokumente, sind dazu vorgesehen, in der Form angezeigt und betrachtet zu werden, in der sie erzeugt wurden, unabhängig von der Hardware- und/oder Softwareplattform, welche zum Betrachten oder Bearbeiten des Dokuments verwendet wird. Es sind Anwendungsprogramme zum Erzeugen solcher portablen Dokumente entwickelt worden. Das von Adobe Systems Inc. entwickelte AcrobatTM ist ein Anwendungsprogramm, das auf mehreren unterschiedlichen Computerplattformen verwendet werden kann. Ein Acrobat-Programm auf einer Plattform kann ein PDF-Dokument, das von einem auf einer anderen Plattform laufenden anderen Acrobat-Programm erstellt wurde, erzeugen, anzeigen, editieren, drucken, kommentieren etc., unabhängig von der Art der verwendeten Computerplattform. Ebenso kann ein Dokument in einem bestimmten Format oder einer bestimmten Sprache unter Verwendung von Acrobat in ein PDF-Dokument umgewandelt werden. Z. B. kann eine PostScript-Datei ohne Verlust von anzuzeigenden Informationen, wie Graphik und Text, in ein PDF-Dokument umgewandelt werden.
Das Auffinden von Wortobjekten in einem Dokument oder einer Datei, die als portables elektronisches Dokument formatiert worden ist, kann aufgrund der verschiedenen zum Speichern der Codes in der Datei verwendeten Verfahren schwierig sein. Anwendungsprogramme können z. B. ein portables elektronisches Dokument erstellen, das eine mit Zeichen und Zeichenketten gefüllte Seite aufweist. Die Reihenfolge der in dem Dokument gespeicherten Zeichenketten stimmt jedoch nicht notwendigerweise mit der Reihenfolge der Zeichenketten überein, wie sie auf der Seite angezeigt wird. Jede Zeichenkette kann z. B. einen Satz von zugehörigen Koordinaten besitzen, um die Position auf der Seite zu liefern, wo die Kette anzuzeigen ist. Da die Ausgabeeinrichtung die Ketten in Abhängigkeit von ihren Koordinaten anzeigt, müssen die Ketten nicht sequentiell gespeichert werden. Da Zeichen oder Ketten, die ein Wort aufweisen, innerhalb des Dokuments verstreut sein können, ist es schwierig, ein Wort in einem solchen Dokument zu suchen oder gar zu identifizieren.
Ein anderes Problem ist es, die Worte in einem portablen elektronischen Dokument zu unterscheiden, wenn verschiedene Zeichen des Wortes verschiedene Charakteristika besitzen. Die Zeichen in einem Wort können, wenn sie auf einer Seite angezeigt werden, z. B. jeweils "gedreht" sein, d. h. in einem Winkel zur Horizontalen stehen. Ein Wort, das solche gedrehten Zeichen enthält, würde dann nicht als ein ganzes Wort identifiziert, wenn lediglich Zeichencharakteristika wie beispielsweise die Koordinatenlage verwendet würden, um festzustellen, welche Zeichen sich in einem Wort befinden.
In den Patent Abstracts aus Japan, Ausgabe 001, Nr. 091 (P-558) vom 23. März 1987 und in JP-A-61 243531 (NEC Corp) vom 29. Oktober 1986 wird ein ein Worterkennungsmittel umfassendes Informationswiedergewinnungssystem beschrieben, während im IBM Technical Disclosure Bulletin, Ausgabe 37, Nr. 5 (Mai 1994) das Erzeugen von Worten aus Zeichen unter Verwendung eines adaptiven Lernalgorithmus beschrieben wird, welcher Mittel zum Erzeugen von lesbarem Text aus einer ansonsten unlesbaren Zeichenfolge zur Verfügung stellt.
Es gibt verschiedene Unix-Tools, die portable elektronische Dokumente vom PostScript-Format ins ASCII-Format umwandeln (siehe z. B. die von Jonathan Monsarrat für die Usenet Newsgruppe comp.sources.postscript zusammengestellten "häufig gefragten Fragen", z. B. Version 1.12 vom 07. Juli 1994). Zumindest eines dieser Tools, ps2ascii, verwendet einen fertigentwickelten PostScript-Interpreter, um seine Aufgabe zu erfüllen. Neben anderen Dingen ordnet dieser Interpreter die Textsegmente innerhalb eines Postscript-Dokuments gemäß ihrer zugehörigen Anzeigeposition. Darüber hinaus identifiziert ps2ascii Worte mit Hilfe der Entscheidung, ob abhängig von der Lücke zwischen benachbarten Zeichen, eine ASCII- Leerstelle erzeugt werden soll oder nicht.
Die vorliegende Erfindung stellt ein Verfahren und eine Einrichtung zum Identifizieren von Worten zur Verfügung, die in einem portablen elektronischen Dokument, wie z. B. einem mit dem zuvor erwähnten AcrobatTM-Programm erstellten Dokument, gespeichert sind. Die Erfindung kann Worte aus in dem Dokument gespeicherten verstreuten Textsegmenten, gedrehten Textsegmenten und beabstandeten Textsegmenten identifizieren.
Die Einrichtung der vorliegenden Erfindung umfaßt ein System zum Identifizieren von Worten in einer Seite eines Dokuments, das in einem portablen elektronischen Dokument beschrieben ist. Eine digitale Verarbeitungseinrichtung speichert eine Seite des Dokuments, wobei jedes Textsegment vorzugsweise eine zugehörige x-Koordinate und y-Koordinate besitzt, die anzeigen, wo das Textsegment auf einer angezeigten Seite anzuzeigen ist. Die Seite umfaßt Textsegmente von einem oder mehreren Zeichen, die nicht als Worte identifiziert worden sind. Ein Wortidentifizierungsmechanismus analysiert die Zeichen der Seite, um eine Wortliste aus auf der Seite identifizierten Worten zu erzeugen. Ein Mechanismus zum Identifizieren von verstreuten Dokumenten stellt ferner fest, ob die Seite eine Sortierung erfordert, damit die Worte richtig identifiziert werden.
Ein Textsegment und die zugehörigen Informationen für das Textsegment werden von dem Wortidentifizierungsmechanismus aus der Seite gelesen und als ein Textobjekt in einer verknüpften Liste gespeichert. Der Wortidentifizierungsmechanismus identifiziert Worte aus den Textobjekten in der verknüpften Liste und speichert die Worte in der Wortliste. Ein Wort wird identifiziert, indem ein Wortunterbrechungszeichen in den Textobjekten aufgefunden wird oder indem zwischen benachbarten Textobjekten eine Lücke aufgefunden wird, deren Größe größer als eine Schwellenwertgröße ist. Die Lücke wird ermittelt, indem die räumliche Distanz zwischen benachbarten Textobjekten unter Verwendung der Koordinaten der Textsegmente in den Textobjekten analysiert wird. Wenn die Lücke zwischen den benachbarten Textobjekten unterhalb der Schwellenwertgröße liegt, werden zumindest Abschnitte benachbarter Textobjekte von dem Wortidentifizierungsmechanismus als ein Wort zu der Wortliste hinzugefügt. Zusätzlich werden zumindest Abschnitte benachbarter gedrehter Textobjekte von dem Wortidentifizierungsmechanismus als ein Wort zu der Wortliste hinzugefügt, wenn sich die Umgrenzungskästen der Textobjekte überschneiden oder durch eine Distanz einer Schwellenwertlücke getrennt sind. Ferner ist ein Sortiermechanismus zum Sortieren der Wortliste enthalten, falls der Verstreutes-Dokument-Identifizierungsmechanismus feststellt, daß die Seite eine Sortierung erfordert. Der Sortierungsmechanismus sortiert die Worte in der Wortliste zunächst nach den y-Koordinaten und dann nach den x-Koordinaten der Worte in der Wortliste. Der Wortidentifizierungsmechanismus baut die Wortliste neu auf, indem Worte in der Wortliste, die innerhalb einer Schwellenwertdistanz voneinander positioniert sind, und Worte, die ein Bindestrich-Zeichen am Ende des Wortes aufweisen, verkettet werden.
Die vorliegende Erfindung umfaßt weiterhin ein Verfahren zum Identifizieren von Worten in einem portablen elektronischen Dokument. Ein Textsegment wird aus einer Seite eines Dokuments erhalten, die eine Vielzahl von Textsegmenten und zugehörige Positionsdaten, die die x- und y-Koordinate für jedes Textsegment umfassen, aufweist. Für jedes Textsegment wird ein Textobjekt erzeugt und die Textobjekte werden in eine verknüpfte Liste eingegeben. Worte aus der verknüpften Liste werden dann identifiziert, indem die Textobjekte auf Wortunterbrechungen analysiert werden und indem Lücken zwischen Textobjekten unter Verwendung der zugehörigen Positionsdaten analysiert werden. In den Textobjekten identifizierte Worte werden, werden zu einer Wortliste hinzugefügt. Die oben beschriebenen Schritte werden wiederholt, bis das Ende der Seite erreicht ist.
Die Textsegmente werden vorzugsweise dadurch identifiziert und die zugehörigen Positionsdaten werden vorzugsweise dadurch wiedergewonnen, daß Befehle des portablen elektronischen Dokuments, durch die die Textsegmente in dem Dokument gespeichert werden, interpretiert werden. Neuverschlüsselte Zeichen der Textsegmente werden unter Verwendung einer Neuzuordnungstabelle neu zugeordnet und anschließend in dem Textobjekt gespeichert. Ein Ablaufrichtungsanzeiger wird vorzugsweise ebenso in den Textobjekten gespeichert. Das Wort wird aus den Textobjekten identifiziert, indem ein Wortunterbrechungszeichen in einem Textobjekt aufgefunden wird oder indem zwischen benachbarten Textobjekten eine Lücke aufgefunden wird, deren Größe größer als eine Schwellenwertgröße ist. Wenn gefunden wird, daß die Lücke zwischen benachbarten Textobjekten unterhalb einer Schwellenwertgröße liegt, dann werden zumindest Abschnitte der benachbarten Textobjekte als ein Wort identifiziert und zu der Wortliste hinzugefügt. Die Wortliste identifizierter Worte wird vorzugsweise dann sortiert, wenn die Seite des Dokuments als verstreut angesehen wird. Die Worte werden zunächst nach ihren y-Koordinaten und dann nach ihren x-Koordinaten sortiert. Worte in der Wortliste, die innerhalb einer Schwellenwertdistanz voneinander positioniert sind, oder Worte, die ein Bindestrich-Zeichen am Ende des Wortes aufweisen, werden verkettet, um die Wortliste wiederaufzubauen.
Ein weiterer Aspekt der vorliegenden Erfindung ist es, daß eine Software zum Auffinden von Worten in einer Datei zur Verfügung gestellt wird. Die Datei umfaßt eine Vielzahl von Textsegmenten aus einem oder mehreren Zeichen und Seitenbeschreibungssprachenbefehle. Ein Textsegmentwiedergewinner gewinnt Textsegmente aus der Datei wieder, vorzugsweise indem die Befehle in der Datei zur Identifizierung von Textsegmenten analysiert werden. Ein Listenersteller erstellt eine Liste von Textobjekten für die Textsegmente. Ein Wortunterbrechungsanalysierer stellt fest, ob eine Wortunterbrechung innerhalb eines Textobjektes liegt und fügt ein Wort in eine Wortliste ein, wenn eine Wortunterbrechung gefunden wird. Der Wortunterbrechungsanalysierer findet vorzugsweise Wortunterbrechungszeichen wie eine Leerstelle oder ein Satzzeichen auf. Ein Lückenanalysierer stellt fest, ob eine Lücke zwischen benachbarten Textobjekten das Abstandskriterium, ein Teil eines Wortes zu sein, erfüllt und fügt ein Wort in die Wortliste ein, nachdem das Abstandskriterium nicht erfüllt wurde. Der Lückenanalysierer fügt das Wort vorzugsweise unter Verwendung eines Wortanfangszeigers, der auf ein erstes Zeichen eines Wortes in den Textobjekten zeigt, und eines Wortendezeigers, der auf ein letztes Zeichen eines Wortes in den Textobjekten zeigt, in die Wortliste ein.
Ein Vorteil der vorliegenden Erfindung ist, daß Worte in einem portablen elektronischen Dokument identifiziert werden, das Textsegmente und Zeichen enthalten kann, die in Formaten gespeichert sind, bei denen Worte schwierig direkt zu identifizieren sind. Portable elektronische Dokumente können Zeichen in einer verstreuten Art speichern und stellen oftmals zur Trennung der Worte keine Leerzeichen zur Verfügung. Die Erfindung sortiert die Zeichen gemäß ihrer angezeigten Reihenfolge und Positionen und kann die Worte einem anforderndem Clientprozeß zur Verfügung stellen.
Ein weiterer Vorteil der Erfindung ist, daß Worte in einem portablen elektronischen Dokument identifiziert werden können, die die verschiedensten Formate aufweisen. Z. B. können Worte, die Zeichen unterschiedlicher Zeichensätze, Größe, Position und unterschiedlicher anderer Anzeigecharakteristika aufweisen, leicht identifiziert werden.
Diese und andere Vorteile der Erfindung werden dem Fachmann beim Lesen der folgenden Beschreibung der Erfindung und beim Studium der verschiedenen Figuren der Zeichnung deutlich.

Kurzbeschreibung der Zeichnungen

Fig. 1 zeigt ein Blockschaltbild eines erfindungsgemäßen Computersystems zum Identifizieren von Worten in einem portablen elektronischen Dokument;
Fig. 2a zeigt eine graphische Darstellung eines Abschnittes eines Bildschirms, der angezeigte Bilder aus einem portablen elektronischen Dokument zeigt;
Fig. 2b zeigt eine graphische Darstellung eines portablen elektronischen Dokuments, das die in Fig. 2a gezeigten Bilder zur Verfügung stellt;
Fig. 3a zeigt eine graphische Darstellung eines Abschnitts eines Bildschirms, der von einem verstreuten portablen elektronischen Dokument abgeleitete angezeigte Bilder zeigt;
Fig. 3b zeigt eine graphische Darstellung eines portablen elektronischen Dokuments, welches die auf dem Bildschirm gemäß Fig. 3a angezeigten Bilder zur Verfügung stellt;
Fig. 4a zeigt eine graphische Darstellung eines Abschnitts eines Bildschirms, der von einem portablen elektronischen Dokument abgeleitete, gedrehte angezeigte Bilder zeigt.
Fig. 4b zeigt eine graphische Darstellung eines portablen elektronischen Dokuments, welches die auf dem Bildschirm gemäß Fig. 4a angezeigten Bilder zur Verfügung stellt.
Fig. 5 zeigt ein Flußdiagramm, das den erfindungsgemäßen Prozeß zum Identifizieren von Worten in einem portablen elektronischen Dokument veranschaulicht;
Fig. 6 zeigt ein Flußdiagramm, das einen Schritt aus Fig. 5 veranschaulicht, bei dem die Codezeilen in dem portablen elektronischen Dokument interpretiert werden, bis ein Anzeigebefehl und Textsegment aufgefunden werden;
Fig. 7 zeigt ein Flußdiagramm, das einen Schritt aus Fig. 5 veranschaulicht, bei welchem ein aufgefundenes Textsegment analysiert wird und ein Textobjekt für das Textsegment erzeugt wird und zu einer verknüpften Liste hinzugefügt wird;
Fig. 8a zeigt eine graphische Darstellung eines erfindungsgemäßen Textobjektes;
Fig. 8b zeigt eine graphische Darstellung der ersten beiden Textobjekte in einer verknüpften Liste für das in Fig. 2b gezeigte portable elektronische Dokument;
Fig. 8c zeigt eine graphische Darstellung der drei Textobjekte in der verknüpften Liste für das in Fig. 2b gezeigte portable elektronische Dokument;
Fig. 9a zeigt eine graphische Darstellung des ersten Textobjektes in einer verknüpften Liste, die für das in Fig. 3b gezeigte portable elektronische Dokument erzeugt wurde;
Fig. 9b zeigt eine graphische Darstellung einer verknüpften Liste, die die aus dem in Fig. 3b gezeigten portablen elektronischen Dokument abgeleiteten Textobjekte umfaßt;
Fig. 10a zeigt eine graphische Darstellung des ersten Textobjektes aus der verknüpften Liste, die für das in Fig. 4b gezeigte portable elektronische Dokument erzeugt wurde;
Fig. 10b zeigt eine graphische Darstellung einer verknüpften Liste, die die aus dem in Fig. 4b gezeigten portablen elektronischen Dokument abgeleiteten Textobjekte umfaßt;
Fig. 11 zeigt ein Flußdiagramm, das einen Schritt aus Fig. 5 veranschaulicht, bei welchem die Koordinaten von Textobjekten verglichen werden, ein Wort identifiziert wird, das Wort zu einer Wortliste hinzugefügt wird und ein oder mehrere Textobjekte aus der verknüpften Liste entfernt werden, wenn diese vollständig analysiert wurde;
Fig. 12a zeigt eine graphische Darstellung einer verknüpften Liste von Textobjekten, die aus einem portablen elektronischen Dokument gewonnen wurden, wobei eines der Textobjekte ein negativ unterschnittenes (negatively-kerned) Zeichen umfaßt;
Fig. 12b zeigt eine graphische Darstellung eines Abschnittes eines Bildschirms, der Bilder der Textobjekte aus Fig. 12a zeigt;
Fig. 13 zeigt ein Flußdiagramm, das einen Schritt aus Fig. 11 veranschaulicht, bei welchem die Lücke zwischen dem Anfang des aktuellen Textobjektes und dem Ende des letzten Textobjektes analysiert wird;
Fig. 14 zeigt ein Flußdiagramm, das den Prozeß des Hinzufügens eines Wortes aus den Textobjekten zu der Wortliste und des Entfernens von einem oder mehreren Textobjekten aus der verknüpften Liste veranschaulicht;
Fig. 15 zeigt ein Flußdarstellung, das einen Schritt aus Fig. 5 veranschaulicht, bei welchem die Worte in der Wortliste sortiert werden; und
Fig. 16 zeigt ein Flußdarstellung, das einen Schritt aus Fig. 5 veranschaulicht, bei welchem die Wortliste wiederhergestellt wird.
Die vorliegende Erfindung eignet sich gut zum Identifizieren von Worten in einem portablen elektronischen Dokument, das verschiedene Arten von Zeichencharakteristika, Abstandscharakteristika und unterschiedliche Formatierungen umfaßt. Insbesondere kann ein portables elektronisches Dokument, wie beispielsweise ein mit AcrobatTM von Adobe Systems, Inc. erstelltes Dokument, von der vorliegenden Erfindung zur Identifizierung von Worten verarbeitet werden. Die Erfindung eignet sich, um Worte an ein Client-Anwendungsprogramm zu liefern, welches Seitenbeschreibungsdokumente durchsucht oder einem Benutzer einzelne oder mehrere Worte zur Verfügung stellt.
Hier wird eine Anzahl von Begriffen zur Beschreibung von Bildern und verwandten Strukturen verwendet. Ein "Pixel" bezeichnet ein einzelnes Bildelement eines Bildes. Zusammen bilden die Pixel das Bild. Eine "Bitmap" bezeichnet Bits, die im digitalen Speicher in einer die Pixel darstellenden Datenstruktur gespeichert sind. So wie es hier verwendet wird, kann sich "Bitmap" sowohl auf eine Datenstruktur zur Ausgabe von schwarzen und weißen Pixeln, wobei jedes Pixel entweder an oder aus ist, als auch auf eine "Pixelmap" beziehen, die mehr Informationen über jedes Pixel, wie z. B. Farb- oder Grautonpixel, enthält. Der Begriff "Wiedergeben (Render)" bezeichnet die Erzeugung einer Bitmap aus einer Bildbeschreibung, wie z. B. einem Zeichenumriß. Ein "Raster" bezeichnet die Anordnung von Pixeln auf einer Ausgabeeinrichtung, die ein Bild erzeugt, indem ein Array von in Zeilen und Spalten angeordneten Pixeln angezeigt wird. Rasterausgabeeinrichtungen umfassen Laserdrucker, Computerbildschirme, Videoanzeigen, LCD-Anzeigen u. s. w. "Codierte" Daten werden von einem "Code" dargestellt, der so entwickelt ist, daß er kürzer ist und einfacher in einer Computereinrichtung bearbeitet werden kann als unbearbeitete Daten in beispielsweise Bitmapform. Z. B. kann der Kleinbuchstabe "a" in Form von codierten Daten, wie z. B. als Zahl 97 bei der ASCII- Codierung, dargestellt werden.
Ein in Fig. 1 gezeigtes Computersystem 10 zum Identifizieren von Worten in einem portablen elektronischen Dokument umfaßt einen digitalen Computer 11, einen Bildschirm 22, einen Drucker 24, ein Diskettenlaufwerk 26, ein Festplattenlaufwerk 28, eine Netzwerkschnittstelle 30 und eine Tastatur 34. Der digitale Computer 11 umfaßt einen Mikroprozessor 12, einen Speicherbus 14, einen Speicher mit wahlfreiem Zugriff (RAM) 16, einen Nur-Lese-Speicher (ROM) 18, einen Peripheriebus 20 und eine Tastatursteuereinrichtung 32. Bei dem digitalen Computer kann es sich um einen Personalcomputer (beispielsweise einen IBM-AT-PC-kompatiblen Personalcomputer), eine Workstation (beispielsweise eine SUN- oder Hewlett-Packard-Workstation) u. s. w. handeln.
Der Mikroprozessor 12 ist ein digitaler Mehrzweckprozessor, welcher den Betrieb des Computersystems 10 steuert. Der Mikroprozessor 12 kann ein Einchipprozessor sein oder mit einer Vielzahl von Komponenten implementiert sein. Unter Verwendung von aus dem Speicher wiedergewonnenen Befehlen steuert der Mikroprozessor 12 den Empfang und die Bearbeitung von Eingangsdaten und die Ausgabe und das Anzeigen von Daten auf Ausgabeeinrichtungen. Bei dem beschriebenen Ausführungsbeispiel ist eine Funktion des Mikroprozessors 12, eine codierte Datei zu untersuchen und Objekte innerhalb dieser Datei zu erfassen. Die Objekte können z. B. von unterschiedlichen Anwendungsprogrammen verwendet werden, die von dem Mikroprozessor 12 oder anderen Computersystemen implementiert werden.
Der Speicherbus 14 wird vom Mikroprozessor 12 verwendet, um auf den RAM 16 und den ROM 18 zuzugreifen. Der RAM 16 wird vom Mikroprozessor 12 als allgemeiner Speicherbereich und als Zwischenspeicher verwendet und kann ebenso zur Speicherung von Eingangsdaten und verarbeiteten Daten verwendet werden. Der ROM 18 kann sowohl zur Speicherung von Befehlen, denen der Mikroprozessor 12 folgt, verwendet werden, als auch zur Speicherung von Bildbeschreibungen und Zeichenumrissen, die zur Anzeige von Bildern in einem bestimmten Format verwendet werden. Eingangsdaten aus einer Datei z. B. können in der Form von Zeichen darstellenden Zeichencodes, einer Sprache für portable elektronische Dokumente, wie z. B. dem "Portable Document FormatTM" (PDFTM) oder einer Seitenbeschreibungssprache wie z. B. PostScript® vorliegen. Die zu dem Zeichen zugehörigen Zeichenumrisse können aus dem ROM 18 abgerufen werden, wenn Bitmaps der Zeichen wiedergegeben werden, um als wiedergegebene Bilder von einer Rasterausgabeeinrichtung angezeigt zu werden. Wahlweise kann sich der ROM 18 in einer Ausgabeeinrichtung, wie z. B. dem Drucker 24 befinden.
Der Peripheriebus 20 wird verwendet, um auf die von dem digitalen Computer 11 verwendeten Eingabe-, Ausgabe- und Speichereinrichtungen zuzugreifen. Bei dem beschriebenen Ausführungsbeispiel umfassen diese Einrichtungen den Bildschirm 22, die Druckeinrichtung 24, das Diskettenlaufwerk 26, das Festplattenlaufwerk 28 und die Netzwerkschnittstelle 30. Die Tastatursteuereinrichtung 32 wird verwendet, um Eingaben von der Tastatur 34 zu empfangen und um entschlüsselte Symbole für jede gedrückte Taste über den Bus 33 an den Mikroprozessor 12 zu senden.
Bei Bildschirm 22 handelt es sich um eine Ausgabeeinrichtung, die Bilder von Daten anzeigt, die von dem Mikroprozessor 12 über den Peripheriebus 20 oder von anderen Komponenten in dem Computersystem zur Verfügung gestellt werden. Bei dem beschriebenen Ausführungsbeispiel ist Bildschirm 22 eine Rastereinrichtung, welche Bilder den Bits einer Bitmap entsprechend in Zeilen und Spalten von Pixeln auf einem Bildschirm anzeigt. Das heißt, eine Bitmap kann in den Bildschirm 22 eingegeben werden und die Bits der Bitmap können als Pixel angezeigt werden. Eine eingegebene Bitmap kann direkt auf dem Bildschirm angezeigt werden oder Komponenten des Computersystems 10 können zuerst Codes oder andere Bildbeschreibungen aus einer Seitenbeschreibungsdatei als Bitmaps wiedergeben und diese anzuzeigenden Bitmaps an einen Bildschirm 24 senden. Rasterbildschirme wie z. B. CRTs, LCD-Bildschirme etc. eignen sich für die vorliegende Erfindung.
Die Druckereinrichtung 24 liefert ein Bild einer Bitmap auf einem Blatt Papier oder einer ähnlichen Oberfläche. Bei dem Drucker 24 kann es sich um einen Laserdrucker handeln, der, wie der Bildschirm 22, eine Rastereinrichtung ist, die von Bitmaps abgeleitete Pixel anzeigt. Die Druckereinrichtung 24 kann aus codierten Daten, wie sie z. B. in einem portablen elektronischen Dokument zu finden sind, abgeleitete Bilder drucken. Als Druckereinrichtung 24 können andere Ausgabeeinrichtungen wie z. B. ein Plotter, eine Schriftsetzmaschine (Typesetter) etc. verwendet werden.
Um Bilder mit einer Ausgabeeinrichtung wie z. B. dem Bildschirm 22 oder dem Drucker 24 anzuzeigen, kann das Computersystem 10 eine oder mehrere Arten von Prozeduren implementieren. Eine Prozedur ist die Umwandlung codierter Objekte in Bildbeschreibungen. Z. B. ist der Code eines Textzeichens ein Teil einer Bildbeschreibung, die weniger Speicherplatz in Anspruch nimmt als mehrere Kopien der Bitmaps des erkannten Zeichens. Der Textzeichencode kann zugehörige Informationen umfassen, wie z. B. Positionskoordinaten, Größe, Zeichensatz usw., die angeben, wie das Zeichen anzuzeigen ist. Eine bekannte Sprache für portable elektronische Dokumente zur Spezifizierung von Bildbeschreibungen ist die "Portable Document Format"(PDF)-Sprache von Adobe Systems, Inc. aus Mountain View, Kalifornien, die in dem AcrobatTM- Anwendungsprogramm verwendet wird. Die Bildbeschreibung kann auf gespeicherte Zeichenumrisse verweisen, die die Form des Zeichens beschreiben und enthält andere Wiedergabeinformationen. Ein bekanntes Zeichenumrißformat ist das Format Type 1® von Adobe Systems. Unter Verwendung der Zeichenumrisse kann das Computersystem 10 eine Bitmap für jedes Zeichen wiedergeben und die Bitmap an einen Cache-Speicher oder einen anderen Speicherbereich senden, auf die eine Ausgabeeinrichtung zum Anzeigen zugreifen kann. Bei anderen Ausführungsbeispielen können Ausgabeeinrichtungen wie Drucker Mikroprozessoren oder ähnliche Steuereinrichtungen umfassen, die eine Bitmap aus Zeichenumrissen wiedergeben können. Mit einem "portablen elektronischen Dokument" ist hier eine Datei oder eine ähnliche Speichereinheit gemeint, die Objekte einer Bildbeschreibung umfaßt, die in einer Sprache für portable elektronische Dokumente, wie z. B. PDF gespeichert sind. Ein portables elektronisches Dokument kann Objekte umfassen, die durch eine Seitenbeschreibungssprache, wie z. B. die PostScript-Sprache, dargestellt werden. Eine Seitenbeschreibungssprachendatei wird hier somit als ein portables elektronisches Dokument betrachtet.
Das Diskettenlaufwerk 26 und das Festplattenlaufwerk 28 können zur Speicherung von Bitmaps, Bildbeschreibungen (codierte Daten) und Zeichenumrissen sowie von anderen Arten von Daten verwendet werden. Das Diskettenlaufwerk 26 vereinfacht den Transport derartiger Daten zu anderen Computersystemen und das Festplattenlaufwerk 28 erlaubt einen schnellen Zugriff auf große Mengen gespeicherter Daten, wie z. B. Bitmaps, die dazu neigen, eine große Menge an Speicherplatz zu erfordern. Andere Massenspeichereinheiten wie nicht-flüchtige Speicher (z. B. Flash-Speicher), PC-Datenkarten oder dgl. können ebenso verwendet werden, um die von dem Computersystem 10 verwendeten Daten zu speichern.
Die Netzwerkschnittstelle 30 wird dazu verwendet, Daten über ein mit anderen Computersystemen verbundenes Netzwerk zu senden und zu empfangen. Eine Schnittstellenkarte oder eine ähnliche Einrichtung und eine entsprechende, von dem Mikroprozessor 12 implementierte Software können verwendet werden, um das Computersystem 10 an ein bestehendes Netzwerk anzuschließen und Daten gemäß Standardprotokollen zu übertragen.
Die Tastatur 34 wird von einem Benutzer verwendet, um in das Computersystem 10 Kommandos oder andere Befehle einzugeben. Auf dem Bildschirm 22 angezeigte oder dem Computersystem 10 zugängliche Bilder können von dem Benutzer editiert, gesucht oder anderweitig bearbeitet werden, indem Befehle über die Tastatur 34 eingegeben werden. Es können ebenso andere Arten von Benutzereingabeeinrichtungen in Verbindung mit der vorliegenden Erfindung verwendet werden. Z. B. können Zeigeeinrichtungen wie z. B. eine Computermaus, ein Trackball, ein Stylus oder ein Zeichentablett verwendet werden, um einen Zeiger auf einem Bildschirm eines Mehrzweckcomputers zu bearbeiten.
Fig. 2a zeigt eine graphische Darstellung eines Abschnitts eines Bildschirms 22, der angezeigte Bilder aus einem portablen elektronischen Dokument zeigt. Ein portables elektronisches Dokument ist eine Datei oder eine andere Ansammlung von digitalen Daten, die in einer Sprache für portable elektronische Dokumente gespeicherte codierte Objekte aufweist. Sprachen für portable elektronische Dokumente, wie z. B. PDF können verwendet werden, um die Identität eines Objektes und damit verknüpfte, zu dem Objekt zugehörige Informationen zu speichern, die zum Anzeigen des Objektes verwendet werden. Eine Seite aus Textzeichen oder Zeichenketten kann in einem PDF-Dokument in Form von Codes gespeichert werden, die sowohl die Identität der Zeichen als auch die Positionen, bei denen die Zeichen angezeigt werden sollen, Zeichensatzinformationen, die Größe und die Ausrichtung der Zeichen wiedergeben. Portable elektronische Dokumente, wie sie hier definiert sind, unterscheiden sich von normalen ASCII-Textdateien, da ASCII-Textdokumente oder - Dateien nur den ASCII-Code der Zeichen und keine weiteren Anzeigeinformationen enthalten und die Zeichen in der Reihenfolge angezeigt werden, in der sie in der Datei gespeichert sind.
Es wird auf Fig. 2a Bezug genommen. Ein Bildschirm 22 zeigt die von einem portablen elektronischen Dokument abgeleiteten Bilder. Ein Textbild 40 wird mit Hilfe der Codes, der Zeichensatzinformationen, Größenangaben, Koordinationeninformationen etc. auf dem Bildschirm angezeigt, welche in dem portablen elektronischen Dokument gespeichert sind und üblicherweise aus wiedergegebenen Bitmaps abgeleitet werden, wie es weiter oben unter Bezugnahme auf Fig. 1 beschrieben wurde. Das Textbild 40 kann ebenso auf einem von dem Drucker 24 ausgegebenen Blatt Papier angezeigt werden. Der Computer bestimmt den Zeichensatz und die Größe jedes anzuzeigenden Zeichens oder Zeichenkette, indem der zugehörige Zeichensatz, die Größe und andere Informationen in dem PDF-Dokument untersucht werden.
Fig. 2b zeigt eine graphische Darstellung eines portablen elektronischen Dokumentes 42, welches das in Fig. 2a gezeigte Bild 40 zur Verfügung stellt. Ein portables elektronisches Dokument, das als Eingabe für die vorliegende Erfindung dient, kann die verschiedensten Formate aufweisen. Hier wird auf ein portables elektronisches Dokument mit in der PDF-Sprache gespeicherten Daten als Hauptbeispiel Bezug genommen. Ebenso können portable elektronische Dokumente, die Daten enthalten, die in einer anderen Sprache wie z. B. PostScript gespeichert wurden, in der vorliegenden Erfindung verwendet werden. Objekte wie z. B. Zeichen werden von der PDF-Sprache als Code gespeichert, wobei ein Anzeigebefehl 44 wie z. B. "Tj" ein Befehl an den Mikroprozessor ist, ein Textsegment 46 in den zugehörigen Klammern zur Anzeige an eine Ausgabeeinrichtung (oder einen Ausgabespeicher-Cache) zu senden. Hier besteht ein "Textsegment" aus einem oder mehreren Zeichen (d. h. einer Zeichenkette), die einem einzigen Anzeigebefehl zugeordnet sind. Das dem Anzeigebefehl zugeordnete Textsegment 46 wird bei einer Position angezeigt, die von jedem Anzeigebefehl zugeordneten Koordinaten 48 angegeben wird. Die Koordinaten 48 umfassen üblicherweise eine (horizontale) x-Koordinate und eine (vertikale) y-Koordinate. Zeichensatz-, Größen- und andere Informationen 50 können ebenso jedem Anzeigebefehl 44 oder Textsegment 46 in dem PDF-Dokument zugeordnet sein, um die Anzeigecharakteristika der Segmente zur Verfügung zu stellen. Die Zeichensatzinformationen z. B. umfassen Informationen darüber, in welchem Zeichensatz die Segmente anzuzeigen sind und können ebenso Informationen bezüglich der Neuabbildung (re-mapping) eines Zeichencodes in ein anderes Zeichen umfassen. Der Zeichencode "97" in dem PDF-Dokument kann z. B. üblicherweise ein "a"-Zeichen darstellen. Wenn der Zeichensatz jedoch neu verschlüsselt worden ist, kann der Zeichencode ein völlig anderes Zeichen darstellen. Ebenso können eine Transformationsmatrix oder ähnliche Befehle ein Segment 46 in den Informationen 50 begleiten, wenn das Segment gedreht oder in einer nicht standardgerechten Ausrichtung positioniert werden soll. Zusätzlich können die Anzeige von Textsegmenten betreffende Informationen in einem Hauptbereich des PDF- Dokumentes wie z. B. dem Anfang des Dokumentes enthalten sein. Die Erzeugung von PDF-Dokumenten oder anderen Arten von portablen elektronischen Dokumenten ist dem Fachmann bekannt.
Die Textsegmente 46 in Fig. 2b werden in dem Dokument in der gleichen Reihenfolge gespeichert, in der sie schließlich auf dem Bildschirm 22 angezeigt werden, wie es in Fig. 2a gezeigt ist. Z. B. werden die Textsegmente "f", "oo" und "bar" in der gleichen Reihenfolge gespeichert, in der sie auf dem Bildschirm 22 angezeigt werden. Hier wird die Reihenfolge, in der Segmente in dem PDF-Dokument gespeichert werden, als die "gespeicherte Reihenfolge" bezeichnet. Dies ist ferner die Reihenfolge, in welcher der Computer die Textsegmente aus dem PDF-Dokument verarbeitet und die Segmente einzeln auf dem Bildschirm anzeigt. Hier wird die Reihenfolge der Segmentbilder, in der sie in ihren Endpositionen auf dem Bildschirm angezeigt werden oder in der die Bilder schließlich auf einem ausgegebenen Blatt Papier gezeigt werden, als die "Anzeigereihenfolge" bezeichnet. Die Anzeigereihenfolge verläuft üblicherweise von links nach rechts und dann von oben nach unten, so als würde man Worte in English lesen.
Fig. 3a zeigt eine graphische Darstellung eines Abschnitts eines Bildschirms 22, der die aus einem in Fig. 3b weiter unten gezeigten verstreuten PDF-Dokument gewonnenen angezeigten Bilder 52 zeigt. Die Bilder 52 entsprechen den in dem PDF-Dokument gespeicherten Textsegmenten, wobei jedes Segment an einer Position angezeigt wird, die durch seine zugehörigen Koordinaten und gemäß den in den Informationen 50 gespeicherten Parametern festgelegt wird.
Fig. 3b zeigt eine graphische Darstellung eines PDF- Dokumentes 54, das die auf dem Bildschirm 22 in Fig. 3a angezeigten Bilder 52 zur Verfügung stellt. Ähnlich dem in Fig. 2b gezeigten PDF-Dokument 42 umfaßt das PDF-Dokument 54 zur Anzeige der Segmente Anzeigebefehle 44', den Anzeigebefehlen zugeordnete Textsegmente 46', den Textsegmenten 46' zugeordnete Koordinaten 48' und Informationen 50'. Bei dem PDF-Dokument 54 jedoch entspricht die gespeicherte Reihenfolge der Segmente in dem Dokument nicht der Anzeigereihenfolge der Segmente auf dem Bildschirm. Die gespeicherte Reihenfolge der Segmente lautet "llo", "rld", "He" und "Wo". Im Gegensatz dazu lautet die Anzeigereihenfolge der Segmente "He", "llo", "Wo" und "rld". Einige PDF- oder andere portable elektronische Dokumente erzeugende Anwendungsprogramme speichern Zeichen oder Segmente in einer verstreuten oder nicht-fortlaufenden Reihenfolge, die sich von der Anzeigereihenfolge der Segmente unterscheidet. Daher kann es schwierig sein, Worte in einem portablen elektronischen Dokument zu unterscheiden, wenn die Segmente in dem Dokument gemäß ihrer gespeicherten Reihenfolge untersucht werden. Das Lesen aufeinanderfolgender Segmente in der gespeicherten Reihenfolge kann zu einem fehlerhaften oder durcheinandergebrachten Wort führen. Hier wird ein portables elektronisches Dokument, in dem sich die gespeicherte Reihenfolge und die Anzeigereihenfolge der Segmente unterscheiden, als ein "verstreutes" (scattered) Dokument bezeichnet.
Bei dem beschriebenen Ausführungsbeispiel können Textsegmente in einer Wortliste gemäß ihren Koordinaten sortiert und neu geordnet werden. Wenn die Textsegmente an einen Client-Prozeß geliefert werden, werden sie folglich in ihrer endgültigen Anzeigereihenfolge geliefert.
Fig. 4a zeigt eine graphische Darstellung eines Abschnittes eines Bildschirms 22, der die aus einem (in Fig. 4b weiter unten gezeigten) PDF-Dokument gewonnenen gedrehten angezeigten Bilder 56 zeigt. Jedes einzelne Bild 58 wurde so gedreht, daß die Bilder eine gekrümmte Bahn bilden. Die Bilder 58 besitzen somit nicht die gleiche Textgrundlinie. Eine Textgrundlinie ist eine Linie, nach der die unteren Enden von keine Unterlängen aufweisenden Zeichen einer Textzeile ausgerichtet sind. Bei Fig. 3a z. B. besitzen alle Zeichen des Wortes "Hello" die gleiche Textgrundlinie und y-Koordinate.
Fig. 4b zeigt eine graphische Darstellung eines PDF- Dokumentes 60, welches die auf dem Bildschirm 22 in Fig. 4 angezeigten Bilder zur Verfügung stellt. Das Dokument 60 umfaßt Anzeigebefehle 44 ", Textsegmente 46 " und Informationen 50 ", die den in den Fig. 2b und 3b gezeigten entsprechenden Daten ähnlich sind. Bei Dokument 60 sind die Koordinaten 48 " in einer jedem Segment 46 " zugehörigen Transformationsmatrix 62 enthalten. Die Transformationsmatrix stellt dem Mikroprozessor oder der Ausgabeeinrichtung Informationen zur Verfügung, um das zugehörige Segment bei der Anzeige des Segmentes zu drehen und zu skalieren. Die Transformationsmatrix kann mehrere Faktoren, gezeigt als "a&sub1;, b&sub1;, c&sub1;, d&sub1;" u. s. w. umfassen, die den Winkel und die Position des angezeigten Segmentes verändern können. Transformationsmatrizen sind den Fachleuten bekannt. Transformierte Textsegmente können Schwierigkeiten bei der Identifizierung von Worten verursachen, da die Segmente an nichtlinearen Positionen angeordnet sein können und Lücken zwischen Segmenten unregelmäßig groß sein können, was Verwirrung darüber verursacht, wann ein Wort endet und das neue Wort beginnt.
Fig. 5 zeigt ein Flußdiagramm, das den erfindungsgemäßen Prozeß 70 zum Identifizieren von Worten in einem portablen elektronischen Dokument veranschaulicht. Der Prozeß beginnt bei 72. Bei Schritt 74 empfängt das Computersystem 10 ein portables elektronisches Dokument, das hier als PDF- Dokument bezeichnet wird. Ein PDF-Dokument, wie es oben beschrieben wurde, ist eine Datei oder eine andere Ansammlung von Daten, die in der PDF-Sprache gespeicherte codierte Objekte umfaßt.
Bei dem beschriebenen Ausführungsbeispiel wird das PDF- Dokument von einem von dem Mikroprozessor 12 implementierten anderen Anwendungsprogramm empfangen (oder einem anderen Computersystem, welches dem Mikroprozessor 12 z. B. über eine Netzwerkschnittstelle 30 oder eine Diskette 26 Daten zur Verfügung stellt). Das PDF-Dokument kann von anderen Anwendungsprogrammen, die den Fachleuten bekannt sind, bearbeitet werden. Z. B. erlaubt Acrobat einem Benutzer ein elektronisches Dokument, wie z. B. ein PDF-Dokument, nach verschiedene Formatierungscharakteristika und Formatierungsarten aufweisenden Objekten zu durchsuchen. Wenn ein Benutzer ein Acrobat-zugängliches PDF-Dokument zu durchsuchen wünscht, kann Acrobat das PDF-Dokument an den erfindungsgemäßen Prozeß senden, welcher Worte in dem PDF-Dokument auffinden und diese Acrobat zur Verfügung stellen würde. Hier werden Anwendungsprogramme, die das PDF-Dokument der Erfindung zur Verfügung stellen können und die Ausgabe der Erfindung empfangen können, wie z. B. Acrobat, als "Clients" oder "Client- Prozeß" bezeichnet. Alternativ kann der erfindungsgemäße Prozeß Worte in eine Datei ausgeben. Die Erfindung kann z. B. alle Worte in einem PDF-Dokument erfassen und diese Worte in eine Zieldatei ausgeben. Der "Client" kann in diesem Falle einfach die Zieldatei sein.
Zusätzlich zum Senden eines PDF-Dokumentes an ein Computersystem 10, auf dem der erfindungsgemäße Prozeß abläuft, kann der Client ferner die Zeichen in dem PDF-Dokument betreffende zusätzliche Informationen senden. Diese zusätzlichen Informationen können z. B. eine Tabelle von Kategorien umfassen, die die Kategorie für jede Art von Zeichen in der Datei zur Verfügung stellt. Die Tabelle kann z. B. anzeigen, ob ein Zeichen ein Buchstabe, eine Zahl, ein Punkt, ein Bindestrich, ein Großbuchstabe oder ein Kleinbuchstabe ist. Ein Zeichen kann sich in mehr als einer Kategorie befinden. Wenn der Client alle oder einige der oben angegebenen zusätzlichen Informationen nicht liefert, kann der erfindungsgemäße Prozeß eine Standardtabelle mit dem Fachmann bekannten Standardkategorien für die Zeichen verwenden. Der Client kann ferner sowohl eine Liste der Zeichen liefern, die Ligaturen sind, wobei es sich um zwei oder mehr Zeichen handelt, die miteinander verbunden sind, wie z. B. ein "æ", als auch die einzelnen, die Ligaturen bildenden (z. B. "a" und "e") Zeichen. Von dem Client können ebenfalls andere Informationen über irreguläre Zeichen oder Segmente zur Verfügung gestellt werden.
Bei dem nächsten Schritt 76 prüft der Mikroprozessor, ob auf der nächsten Seite des PDF-Dokumentes Worte zu identifizieren sind. Wenn es in dem PDF-Dokument keine weiteren Seiten mehr gibt oder der Client einen Befehl liefert, das Identifizieren von Worten zu beenden, wird die nächste Seite nicht untersucht und der Prozeß wird, wie bei 78 angezeigt, beendet. Wenn die nächste Seite zur Identifizierung von Worten untersucht werden soll, geht der Prozeß mit dem Schritt 80 weiter. Bei Schritt 80 stellt der Mikroprozessor fest, ob das PDF-Dokument verstreut ist, was bedeutet, das das Dokument Textsegmente in einer gespeicherten Reihenfolge enthält, die nicht mit der Anzeigereihenfolge der Segmente übereinstimmt, wie es unter Bezugnahme auf Fig. 3b weiter oben beschrieben wurde. Bei dem beschriebenen Ausführungsbeispiel kann bei diesem Schritt des Prozesses der verstreute oder nicht-verstreute Zustand des PDF-Dokumentes explizit in dem Dokument oder durch einen Befehl oder ein von dem Client gesetztes Flag angezeigt werden. Wenn z. B. alle von bestimmten Anwendungsprogrammen erzeugten portablen elektronischen Dokumente bekanntermaßen verstreut sind, dann kann der Mikroprozessor das PDF-Dokument untersuchen, um festzustellen, ob eines dieser Anwendungsprogramme das Dokument erzeugt hat. Wenn das Anwendungsprogramm, mit dem das Dokument erzeugt wurde, nicht bekannt ist, kann die vorliegende Erfindung ferner die Textsegmente in dem PDF-Dokument betrachten und dann feststellen, ob das Dokument verstreut ist, wie es weiter unten bei Schritt 87 detailliert beschrieben wird.
Wenn bei Schritt 80 festgestellt wird, daß das PDF- Dokument verstreut ist, wird bei Schritt 82 ein Sortier-Flag gesetzt. Dieses Flag zeigt an, daß das verstreute Dokument bei einem späteren Schritt des Prozesses sortiert werden soll, bevor die Worte an den Client gesendet werden. Nach Schritt 82 oder wenn das PDF-Dokument verstreut ist oder einen unbekannten Verstreut-Zustand aufweist, wird Schritt 84 implementiert, bei welchem von dem erfindungsgemäßen Prozeß verwendete Flags und Zeiger gelöscht oder zurückgesetzt werden und andere Reinigungs(Clean-Up)- und Initialisierungsprozeduren implementiert werden. Das einzige Flag, das bei Schritt 84 nicht zurückgesetzt wird, ist das Sortier- Flag, welches in seinem vorherigen Zustand belassen wird. Bei dem nächsten Schritt 86 werden die Codezeilen (Befehle, Daten u. s. w.) in dem PDF-Dokument von einem Interpreter interpretiert, bis ein Anzeigebefehl, wie z. B. "Tj" aufgefunden wird. Dieses zeigt an, daß ein Textsegment in dem PDF-Dokument aufgefunden wurde. Bei anderen Ausführungsbeispielen können ferner andere Befehle, die das Vorliegen eines Textsegmentes anzeigen, untersucht werden. Dieser Prozeß des Interpretierens von Codezeilen in dem Dokument und des Auffindens eines Textsegmentes wird detaillierter unter Bezugnahme auf Fig. 6 beschrieben. Bei Schritt 87 überprüft der Mikroprozessor, ob das PDF-Dokument ein verstreutes Dokument ist. Dieser Schritt wird nur dann implementiert, wenn das Sortier-Flag nicht gesetzt worden ist, was bedeutet, daß der Verstreut-Zustand des Dokumentes noch nicht bekannt ist. Um festzustellen, ob das Dokument verstreut ist, untersucht der Mikroprozessor das aus dem PDF-Dokument gewonnene Textsegment. Die y-Koordinate des Textsegmentes wird überprüft, um festzustellen, ob sie um eine Schwellenwertdistanz von der y-Koordinate des Textsegmentes abweicht, welches zuvor bei Schritt 86 wiedergewonnen wurde. Der Schwellenwert kann z. B. das Zweifache oder mehr der Höhe einer Textzeile in dem PDF-Dokument betragen. Wenn sich die y-Koordinaten um den Schwellenwert oder mehr unterscheiden, wird ein Prüf-Flag gesetzt. Wenn das nächste, bei Schritt 86 wiedergewonnene Textsegment eine y-Koordinate aufweist, die von der y-Koordinate des letzten Segmentes in Richtung des zuvor wiedergewonnenen Textsegmentes um den Schwellenwert oder mehr abweicht, dann wird das PDF-Dokument als verstreutes Dokument betrachtet und der Prozeß geht mit Schritt 91 weiter, wo das Sortier-Flag gesetzt wird. Der Mikroprozessor sucht folglich nach einer verstreuten auf und-ab-Positionierung aufeinanderfolgender Textsegmente (oder links-nach- rechts, wenn der Text von oben nach unten ausgerichtet ist).
Nach Schritt 91 oder wenn die y-Koordinaten innerhalb des Schwellenwertes liegen, geht der Prozeß mit Schritt 88 weiter. Jedes Mal, wenn ein Segment aus dem PDF-Dokument wiedergewonnen wird, überprüft der Mikroprozessor, ob es sich um ein verstreutes Dokument handelt. Wenn das Sortier-Flag gesetzt worden ist (bei Schritt 82 oder 91), überspringt der Mikroprozessor den Schritt 87, wenn bei Schritt 86 weitere Textsegmente wiedergewonnen werden. Das Setzen des Sortier- Flags hat den zusätzlichen Effekt, daß z. B. in Fig. 13 jegliche Bindestrich-Untersuchungslogik deaktiviert wird, da wiedergewonnene Textsegmente nicht als benachbart angenommen werden können, wenn das PDF-Dokument verstreut ist.
Bei Schritt 88 überprüft der Mikroprozessor, ob die Interpretierung der Codezeilen abgeschlossen und das Ende der Seite erreicht worden ist. Dieses tritt ein, wenn alle Textsegmente der aktuellen Seite interpretiert worden sind, d. h. eine Seitenende-Anzeige, wie beispielsweise ein Befehl, in dem PDF-Dokument aufgefunden wird. Wenn noch nicht alle Textsegmente der Seite interpretiert worden sind, geht der Prozeß mit Schritt 90 weiter, wo ein bei Schritt 86 aufgefundenes Textsegment analysiert wird und als Textobjekt zu einer verknüpften Liste hinzugefügt wird. Dieser Schritt wird unter Bezugnahme auf Fig. 7 detaillierter beschrieben. Bei dem nächsten Schritt 92 legt der Mikroprozessor fest, ob sich mehr als ein Textobjekt in der verknüpften Liste befindet. Wenn nicht, kehrt der Prozeß zu Schritt 86 zurück, um ein anderes Textsegment in dem PDF-Dokument aufzufinden. Wenn sich mehr als ein Textobjekt in der Liste befindet, geht der Prozeß mit Schritt 94 weiter, der weiter unten beschrieben wird.
Wenn bei Schritt 88 ein Seitenende erreicht wird, geht der Prozeß mit Schritt 89 weiter, wo ein "Flush"- bzw. "Räum"-Flag gesetzt wird. Dieses Flag zeigt dem Mikroprozessor an, daß er die verbleibenden Textobjekte bei dem weiter unten beschriebenen Schritt 94 in die Wortliste "spülen" (flush) soll. Zusätzlich wird ein Textobjekt für das letzte aus dem PDF-Dokument interpretierte Textsegment vor der Seitenende-Anzeige erzeugt. Der Prozeß geht dann mit Schritt 94 weiter.
Bei Schritt 94 werden die Koordinaten der Textobjekte in der verknüpften Liste gemäß heuristischen Methoden verglichen, die Zeichen in den Textobjekten werden untersucht um festzustellen, ob irgendwelche Wortunterbrechungszeichen vorhanden sind, und ein Wort wird aus den Textobjekten identifiziert. Das identifizierte Wort wird zu einer Wortliste hinzugefügt und das Textobjekt oder die Textobjekte, die zur Identifizierung des Wortes verwendet wurden, werden dann entfernt, wenn diese Textobjekte vollständig analysiert worden sind. Unter Bezugnahme auf Fig. 11 wird Schritt 94 genauer beschrieben.
Nach Schritt 94 geht der Prozeß mit Schritt 96 weiter, bei welchem der Mikroprozessor überprüft, ob das Flush-Flag gesetzt worden ist, das anzeigt, daß das Ende der Seite erreicht worden ist. Wenn das Flush-Flag FALSCH (nicht gesetzt) anzeigt, kehrt das Prozeß zum Schritt 86 zurück, um weitere Codezeilen in dem PDF-Dokument zu interpretieren und andere Textsegmente aufzufinden. Wenn das Flush-Flag gesetzt ist, dann geht der Prozeß mit Schritt 98 weiter, bei welchem der Mikroprozessor überprüft, ob das Sortier-Bit gesetzt worden ist, d. h. ob das PDF-Dokument ein verstreutes Dokument ist. Wenn das der Fall ist, geht der Prozeß mit Schritt 100 weiter, wo die Wortliste mit Hilfe der Koordinatenwerte sortiert wird. Dieser Schritt wird unter Bezugnahme auf Fig. 15 genauer beschrieben. Nach der Sortierung wird die Wortliste bei Schritt 102 wieder aufgebaut, um alle übriggebliebenen Wortfragmente in der Wortliste zu verketten, was genauer anhand von Fig. 16 beschrieben wird.
Sobald die Wortliste bei Schritt 102 wieder aufgebaut worden ist oder das Sortier-Bit bei Schritt 98 auf FALSCH gesetzt wird, geht der Prozeß mit Schritt 104 weiter, wo die Wortliste identifizierter Worte an den Client zurückgegeben wird. Bei dem beschriebenen Ausführungsbeispiel umfaßt jedes Wort in der Wortliste mehrere Merkmale bzw. Attribute. Jedes Wort (oder "Wortobjekt") umfaßt fünf Wortmerkmale, und zwar den Zeichensatz des Wortes, die Farbe, Umgrenzungskastenkoordinaten, eine vom Anfang der Seite an gezählte Wortnummer und eine vom Anfang der Seite gezählte Zeichennummer des ersten Zeichens des Wortes. Jedes Wort in der Wortliste umfaßt ferner zwei Zeichenmerkmale für jedes Zeichen des Wortes, und zwar den Zeichencode, der die Identität des Zeichens liefert, und die Zeichenart. Bei einem Wort wie beispielsweise "Hello-" kann der Zeichensatz Times, die Farbe schwarz, die Wortnummer 87 und die Zeichennummer 345 sein. Die Zeichenmerkmale können sein der Code für "H" und eine Zeichenart "Großbuchstabe". Entsprechend wird das Bindestrich-Zeichen ("-") mit einem Zeichencode und einer Zeichenart "Bindestrich" gespeichert. Der Client kann die Wortmerkmale verwenden, um bei der Anzeige der identifizierten Worte zu helfen. Der Client kann z. B. die Koordinaten eines Umgrenzungskastens verwenden, um ein empfangenes Wort in einem Texteditor hervorzuheben.
Die Worte in der Wortliste können einzeln an den Client zurückgegeben werden, wenn der Client alle Worte anfordert, oder dem Client kann die ganze Wortliste auf einmal zur Verfügung gestellt werden. Sobald die Wortliste zurückgegeben worden ist, kehrt der Prozeß zu Schritt 76 zurück, um zu überprüfen, ob die Worte auf der nächsten Seite zu identifizieren sind und wenn dies der Fall ist, wird der ganze Prozeß wiederholt.
Das beschriebene erfindungsgemäße Ausführungsbeispiel ist seitenbasiert, d. h. daß eine Seite von Textsegmenten analysiert und in eine Wortliste eingefügt wird, bevor die nächste Seite des Dokumentes analysiert wird. Zeichen wie z. B. ein Trennungszeichen zwischen Seiten werden von dem beschriebenen, seitenbasierten Prozeß nicht erfaßt. Bei einem alternativen Ausführungsbeispiel kann jedoch ein Schritt hinzugefügt werden, um einen Bindestrich nach dem letzten Textsegment einer Seite zu erfassen. Bei einem Ausführungsbeispiel, bei dem z. B. das letzte Textobjekt bei Schritt 169 in Fig. 11 "geflushed" und zu der Wortliste hinzugefügt werden soll (was weiter unten beschrieben wird), kann das letzte Zeichen dieses Textobjektes untersucht werden. Wenn es sich bei dem letzten Zeichen um ein Trennzeichen handelt (d. h. einen Bindestrich, der sich am Ende einer Textzeile befindet und welcher damit anzeigt, daß das Wort vor dem Bindestrich an das Wort in der nächsten Zeile angehängt werden soll), dann soll das Wort in dem Textobjekt noch nicht zu der Wortliste hinzugefügt werden. Um das nächste Worte aufzufinden, kann die erste Zeile der nächsten Seite interpretiert werden, in Textobjekte umgewandelt und analysiert werden. Das nächste Wort kann dann mit dem durch einen Bindestrich getrennten Wort verkettet und anschließend zu der Wortliste hinzugefügt werden.
Fig. 6 zeigt ein Flußdarstellung, welches Schritt 86 in Fig. 5 veranschaulicht, bei welchem die Codezeilen in dem PDF-Dokument interpretiert werden, bis ein Anzeigebefehl wie z. B. "Tj" und ein Textsegment aufgefunden werden. Der Prozeß beginnt bei 110 und bei Schritt 112 stellt der Mikroprozessor fest, ob ein Textsegment in dem PDF-Dokument aufgefunden worden ist. Wenn ein Textsegment aufgefunden worden ist, geht der Prozeß mit Schritt 114 weiter, wo der Mikroprozessor eine Codezeile aus dem PDF-Dokument interpretiert, um festzustellen, ob ein Textsegment vorhanden ist. Der Mikroprozessor verwendet einen Interpreter für portable elektronische Dokumente, um die Befehle in dem PDF-Dokument auszuführen und um bei Ausführung eines Anzeigebefehls das dem Anzeigebefehl zugeordnete Textsegment an den aktuellen Prozeß weiterzugeben. Der Prozeß untersucht ferner den "Graphikzustand" des Interpreters, um die dem Textsegment zugeordneten verwandten Informationen aufzufinden. Der Graphikzustand ist eine Ansammlung von Werten, die sich auf das aktuelle Textsegment beziehen können und die geführt und aktualisiert werden, wenn die PDF-Befehle ausgeführt werden. Z. B. wird die Position eines Zeigers aktualisiert, der auf einen Befehl zeigt, und der Zeichensatz, die Farbe, die Drehung usw. des aktuellen Textsegmentes werden aufgefunden und aktualisiert. Wie dem Fachmann bekannt ist, können aus dem Graphikzustand die Koordinaten, der Zeichensatz, die Größe, die Ausrichtung usw. des Textsegmentes bestimmt werden. Der Prozeß kehrt dann zu Schritt 112 zurück. Sobald ein Textsegment bei der Überprüfung gemäß Schritt 112 aufgefunden worden ist, ist der Prozeß, wie es bei 116 angezeigt ist, beendet.
Fig. 7 zeigt ein Flußdarstellung, das den Schritt 90 in Fig. 5 veranschaulicht, bei welchem das aufgefundene Textsegment analysiert und ein Textobjekt für das Textsegment erzeugt wird und zu einer verknüpften Liste hinzugefügt wird. Der Prozeß beginnt bei 120. Bei Schritt 122 wird ein Textobjekt erzeugt und einer verknüpften Liste von Textobjekten am Ende hinzugefügt. Bei anderen Ausführungsbeispielen können neben verknüpften Listen andere Arten von Listen verwendet werden. Das hier verwendete "Textobjekt" ist ein Knoten in der verknüpften Liste, der bei dem beschriebenen Ausführungsbeispiel eine Anzahl von Feldern umfaßt. Unter Bezugnahme auf die Fig. 8a bis 10b werden diese Felder weiter unten detailliert beschrieben. Das in dem PDF- Dokument aufgefundene Textsegment wird in einem der Felder des Textobjektes angeordnet. Die Zeichen des Textsegmentes in einem Textobjekt werden hier als die Zeichen des Textobjektes bezeichnet.
Es wird wieder auf Fig. 7 Bezug genommen. Bei Schritt 124 werden die Verschlüsselungsvektoren für die Zeichen in dem Textsegment überprüft und jedes verschlüsselte Zeichen wird einem mit dem Client kompatiblen Code neu zugewiesen. Bei üblichen PDF-Dokumenten oder anderen portablen elektronischen Dokumenten können einige in dem Dokument verwendeten Zeichencodes unterschiedlichen Zeichen zugewiesen sein. Z. B. kann ein Anwendungsprogramm, das ein PDF-Dokument erzeugt hat, ein Zeichen als die Zahl "97", welche üblicherweise ein "a"-Zeichen darstellt, speichern und anschließend die "97" einem anderen Zeichen neu zuweisen, wie z. B. einem "@"- Symbol. Die Verschlüsselungsinformationen sind in dem PDF- Dokument üblicherweise in einer Verschlüsselungstabelle oder in den jedem Textsegment zugeordneten Informationen 50 enthalten. Diese Verschlüsselungsinformationen zeigen an, welche Zeichen in einem Textsegment anderen Zeichen als den Standardzeichen des Textsegmentszeichensatzes neu zugewiesen wurden und die Codes, die neu zugewiesen wurden. Die Verschlüsselungsvektoren des Clients sind bekannt, wenn der Client das PDF-Dokument an den erfindungsgemäßen Prozeß sendet. Der Client sendet mit dem PDF-Dokument und anderen unter Bezugnahme auf Fig. 5 beschriebenen Informationen seine eigenen Verschlüsselungsvektoren, die dem Mikroprozessor mitteilen, welche Codes welche Zeichen darstellen sollen. Bei Schritt 124 untersucht der Mikroprozessor die Verschlüsselungsinformationen in dem PDF-Dokument und die von dem Client gesendeten Verschlüsselungsinformationen und ändert die verschlüsselten Zeichen in einen dem neu zugewiesenen Code äquivalenten Code, der mit dem Zeichenschema des Clients kompatibel ist.
Bei Schritt 126 werden die Parameter jedes Zeichens des in dem Textobjekt gespeicherten Textsegmentes festgestellt und in dem Textobjekt gespeichert. Die Parameter werden aus dem PDF-Dokument gelesen und in Feldern des Textobjektes gespeichert. Die verknüpfte Liste und die in den Textobjekten des beschriebenen Ausführungsbeispieles gespeicherten Parameter sind in den Fig. 8a bis 10b gezeigt.
Der Mikroprozessor überprüft bei dem nächsten Schritt 128, ob das soeben erzeugte Textobjekt mehr als ein Zeichen umfaßt. Wenn nicht, ist der Prozeß bei 134 abgeschlossen.
Wenn mehr als ein Zeichen vorhanden ist, wird Schritt 130 implementiert, bei dem eine Ablauf- bzw. Flußreihenfolge bestimmt wird und ein Flußreihenfolgenanzeiger in dem Textobjekt gespeichert wird, wie es in Fig. 8a gezeigt ist. Die Flußreihenfolge ist die Richtung mit der Zeichen auf einer Seite angezeigt werden. Bei dem beschriebenen Ausführungsbeispiel wird die Flußreihenfolge durch eine von vier Richtungen (vier Zahlen) angegeben, links nach rechts, rechts- nach-links, oben nach unten oder unten-nach-oben. Die Flußrichtung des Textobjektes zeigt die Richtung an, in der ein Wort "fließt" bzw. verläuft. Wenn ein Text beim Anzeigen auf einer Seite z. B. vertikal nach unten positioniert wird, wäre die Reihenfolge oben nach unten. Die Flußreihenfolge kann durch eine Prüfung der Koordinaten der Zeichen in dem Textobjekt festgestellt werden. Nach Schritt 130 wird Schritt 131 eingeleitet, bei dem der Mikroprozessor überprüft, ob ein vorhergehendes Textobjekt in der verknüpften Liste existiert. Wenn dies der Fall ist, wird Schritt 132 implementiert, bei dem der Mikroprozessor überprüft, ob die Flußreihenfolge des vorhergehenden Textobjektes eingestellt worden ist. Wenn nicht, wird dann bei Schritt 133 die Flußreihenfolge des vorhergehenden Textobjektes bestimmt, indem die Koordinaten des vorhergehenden Textobjektes und des aktuellen Textobjektes untersucht werden. Diese Flußreihenfolge wird in dem vorhergehenden Textobjekt gespeichert. Wenn bei Schritt 132 die Flußreihenfolge des vorhergehenden Textobjektes eingestellt worden ist oder bei Schritt 131 kein vorhergehendes Textobjekt in der verknüpften Liste existiert, ist der Prozeß bei Schritt 134 beendet. Nachfolgende Textobjekte könnten somit verwendet werden, um die Flußrichtung für vorhergehende Textobjekte festzustellen, die nur ein Zeichen umfassen und somit keine unmittelbar bestimmbare Flußrichtung besitzen.
Wie es in Fig. 8a gezeigt ist, umfaßt ein Textobjekt 136 vorzugsweise Felder zum Speichern von sowohl einem Textsegment 137 als auch anderer Parameter des Textsegmentes, einschließlich der Koordinaten 138 des Textsegmentes 137 (üblicherweise als x,y-Koordinaten gezeigt), des Zeichensatzes 139 des Textsegmentes 137, des Schriftstils 141 des Textsegmentes 137 (wie beispielsweise fett, kursiv, unterstrichen u. s. w.), der Umgrenzungskastenparameter 143 des Textsegmentes 137 (die bei dem beschriebenen Ausführungsbeispiel die vier Punkte des das Textobjekt umgebenden Umgrenzungskastens umfassen) und der Farbe 145 des Textsegmentes 137. Die Flußrichtung 147 ist ebenfalls enthalten, die bei der Anzeige auf der Seite die Richtung der Textsegmente, wie oben beschrieben, anzeigt. Zusätzlich zeigt ein Drehungs- Flag 149 an, ob das Textobjekt gedreht ist, d. h. ob das Textobjekt eine Transformationsmatrix umfaßt, die die Ausrichtung des Textsegmentes ändert. Schließlich umfaßt ein Textobjekt vorzugsweise zwei Zeichen-Positions-Flags 151a, ein STARTFLAG und ein ENDFLAG. Diese Flags werden auf 1 gesetzt, wenn sich die Zeichen eines Wortanfangs bzw. des Wortendes in dem Textobjekt befinden. Ferner sind zwei Zeichen-Offset-Flags 151b, ein STARTOFFSET und ein ENDOFFSET, enthalten. Diese Offsets zeigen die Zeichenpositionen des Wortanfangs bzw. des Wortendes, betrachtet vom Anfang des Textobjektes, an, wobei die erste Zeichenposition 0 ist. Die Flags 151a und die Offsets 151b werden bei dem Prozeß des Identifizierens von Worten in den Textobjekten verwendet und unter Bezug auf Fig. 11 beschrieben. Bei anderen Ausführungsbeispielen können auch andere Textsegmentcharakteristika gespeichert werden. Diese Charakteristika des Textobjektes werden aus der PDF-Datei wiedergewonnen und zusammen mit dem Textsegment in dem Textobjekt gespeichert. Bei dem Beispiel in Fig. 8a ist das Textsegment "f" das erste Textsegment aus dem in Fig. 2b gezeigten PDF-Dokument 42. Wenn einige Zeichen in einem Textobjekt unterschiedliche Zeichensätze aufweisen, können in dem Feld für diesen Parameter eine Vielzahl von Parametern gespeichert werden. Wenn z. B. Zeichen in einem Textobjekt unterschiedliche Zeichensätze aufweisen, können alle Zeichensätze des Textobjektes im Zeichensatzfeld 139 gespeichert werden.
Einige Textsegmente in einem PDF-Dokument können mehr als ein Wort oder mehr als einen Abschnitt eines Wortes umfassen. Ein Befehl "(Hello World) Tj" ist z. B. ein Code zur Anzeige des Textsegmentes "Hello World". Das vollständige Textsegment, das zwei durch eine Leerstelle getrennte Worte umfaßt, wäre in einem einzigen Textobjekt enthalten. Wie es weiter unten unter Bezug auf Fig. 11 beschrieben wird, würde eine Mehrzahl von Worten aus einem derartigen Textobjekt identifiziert werden, und die Flags und die Offsets in dem Textobjekt würden neuzugewiesen werden, wenn getrennte Worte in dem Textobjekt identifiziert und zu einer Wortliste hinzugefügt werden. Sobald z. B. das Wort "Hello" identifiziert und zu der Wortliste hinzugefügt wird, würde STARTOFFSET (der Anfang eines Wortes) von Zeichenposition 0 ("H") auf Position 6 ("W") geändert werden. ENDOFFSET würde sich von Position 4 ("o") auf Position 10 ("d") als das Ende eines Wortes ändern.
Fig. 8b zeigt eine Darstellung, welche die ersten beiden Textobjekte in einer verknüpften Liste für das in Fig. 2b gezeigte PDF-Dokumentes 42 veranschaulicht. Das erste Textobjekt 136 weist das Textsegment "f" auf und das zweite Textobjekt 155 umfaßt das Textsegment "oo". Das dritte Textobjekt wird anschließend zu der verknüpften Liste des PDF- Dokumentes 42 hinzugefügt, und das Ergebnis wird in Fig. 8c dargestellt. Textobjekt 157, welches das Textsegment "bar" umfaßt, ist an dem Ende der verknüpften Liste hinzugefügt worden.
Fig. 9a zeigt eine Darstellung, die das erste Textobjekt 136' in der verknüpften Liste veranschaulicht, die für das in Fig. 3b gezeigte PDF-Dokument erzeugt wurde. Ähnlich dem Textsegment 136 in Fig. 8a umfaßt das Textobjekt 136' die unter Bezug auf Fig. 8a beschriebenen Felder. In Fig. 9b wird eine verknüpfte Liste 159 gezeigt, die alle aus dem in Fig. 3b gezeigten PDF-Dokumente gewonnenen Textobjekte umfaßt. Die Reihenfolge der Textobjekte in der verknüpften Liste ist gleich der gespeicherten Reihenfolge der Textsegmente in dem PDF-Dokument. Bei diesem Beispiel befinden sich die Textobjekte in der verknüpften Liste nicht in einer Anzeigereihenfolge, da das PDF-Dokument ein verstreutes Dokument war.
Fig. 10a zeigt eine Darstellung, die das erste Textobjekt in der verknüpften Liste, die für das in Fig. 4b gezeigte PDF-Dokument 60 erzeugt wurde, veranschaulicht und das den in den Fig. 8a bzw. 9a gezeigten Textobjekten 136 und 136' ähnlich ist. Da das Textsegment "s", wie in Fig. 4a gezeigt, gedreht war, ist das Drehungs-Flag 149 für dieses Textobjekt gesetzt. Fig. 10b zeigt eine verknüpfte Liste 161, die alle aus dem in Fig. 4b gezeigten PDF-Dokument 60 gewonnenen Textobjekte umfaßt.
Fig. 11 zeigt ein Flußdiagramm, das Schritt 94 in Fig. 5 veranschaulicht, bei dem die Koordinaten von Textobjekten verglichen werden, ein Wort identifiziert wird, das Wort zu einer Wortliste hinzugefügt wird und ein oder mehrere Textobjekte aus der verknüpften Liste entfernt werden, wenn diese vollständig analysiert sind. Der Prozeß beginnt bei 140. Bei Schritt 141 wird die Variable OBJNUM auf 0 initialisiert. OBJNUM stellt die Nummer des aktuell untersuchten Textobjektes in der verknüpften Liste dar. Bei Schritt 144 stellt der Mikroprozessor fest, ob es keine weiteren zu verarbeitenden Textobjekte mehr in der verknüpften Liste gibt. Ist dies der Fall, geht der Prozeß mit Schritt 169 weiter (der weiter unten genau beschrieben wird). Wenn noch Textobjekte in der verknüpften Liste vorhanden sind, geht der Prozeß mit Schritt 148 weiter, bei welchem das nächste Textobjekt aus der verknüpften Liste wiedergewonnen wird. Zusätzlich wird die Variable CHARPOS auf 0 gesetzt. CHARPOS ist ein bei der Untersuchung der Zeichen des Textobjektes verwendeten Zeichenpositionsanzeiger. Bei dem folgenden Schritt 150 stellt der Mikroprozessor fest, ob OBJNUM größer als 0 ist. Ist dies nicht der Fall, ist das aktuelle Textobjekt das erste Textobjekt in der verknüpften Liste und Schritt 154 wird eingeleitet, bei dem CHARPOS auf 0 gelöscht wird und die Flags 151a und die Offsets 151b (wie in Fig. 8a gezeigt) des aktuellen Textobjektes initialisiert werden: Das STARTFLAG wird auf 1 gesetzt, das ENDFLAG wird auf 0 gelöscht, der STARTOFFSET und der ENDOFFSET werden auf 0 gelöscht. Der Prozeß geht dann mit Schritt 156 weiter (wie es weiter unten beschrieben wird). Wenn bei Schritt 150 OBJNUM größer als 0 ist, dann befindet sich ein vorhergehendes Textobjekt bereits in der verknüpften Liste. Schritt 152 wird implementiert, bei welchem heuristische Methoden verwendet werden, um den Anfang des aktuellen Textobjektes mit dem Ende des letzten Textobjektes zu vergleichen. Schritt 152 wird genauer in Hinblick auf Fig. 13 beschrieben. Nachdem Schritt 152 beendet worden ist, wird Schritt 156 eingeleitet.
Bei Schritt 156 beginnt eine Schleife. Die Variable C wird auf CHARPOS initialisiert und C wird mit NCHAR, der Anzahl der Zeichen in dem aktuellen Textobjekt, verglichen. Wenn C kleiner als NCHAR ist, wird Schritt 158 implementiert, bei dem der Mikroprozessor überprüft, ob char(C) des aktuellen Textobjektes gleich einem Unterbrechungszeichen ist. Ein Unterbrechungszeichen ist ein Zeichen, das anzeigt, daß eine Wortunterbrechung aufgefunden wurde und daß die zuvor untersuchten Zeichen als ein Wort zusammengefaßt werden sollen.
Bei dem beschriebenen Ausführungsbeispiel wird eine umfangreiche Liste von Wortunterbrechungszeichen mit char(C) verglichen. Diese Liste umfaßt Standardsymbole, Zeichensetzungszeichen und andere, den verschiedenen Zeichensätzen zugeordnete Zeichen. Die Liste der Zeichen umfaßt eine Leerstelle und folgende, mit ihren Standardnamen aufgelistete Symbole, die hier als "Zeichensetzungszeichen" bezeichnet sind: Ausrufezeichen, doppeltes Anführungszeichen, Nummernzeichen, Dollarzeichen, Prozent, Und-Zeichen, linke runde Klammer, rechte runde Klammer, Plus, Komma, Periode, Schrägstrich, Doppelpunkt, Semikolon, kleiner als, gleich, größer als, Fragezeichen, AT-Zeichen, linke eckige Klammer, rechte eckige Klammer, senkrechter Strich, Kugel, Gulden, doppeltes Anführungszeichen unten, Auslassungszeichen, Promill, doppeltes Anführungszeichen links, doppeltes Anführungszeichen rechts, M-Bindestrich, N-Bindestrich, Marke, Tilda, umgekehrtes Ausrufezeichen, Cent, Stirling, Währungs-Zeichen, Yen, unterbrochener senkrechter Strich, Paragraph, Copyright, weibliches Ordinal, männliches Ordinal, registrierte Marke, angewinkelte doppelte Anführungszeichen links, Verneinungs-Zeichen, Überstrich, Grad-Zeichen, Plus/Minus- Zeichen, hochgestellte Zwei, hochgestellte Drei, Absatz/Paragraphen-Zeichen, Mittelpunkt, hochgestellte Eins, ein Viertel, angewinkelte doppelte Anführungszeichen rechts, ein Halb, drei Viertel, umgekehrtes Fragezeichen, Multiplikationszeichen, Bindestrich, Divisionszeichen, Tilde, ASCII- Tilde, Circumflex, ASCII-Circum, einfaches Anführungszeichen links, Unterstrichen, angewinkeltes einzelnes Anführungszeichen links, einfaches Anführungszeichen unten, angewinkeltes einzelnes Anführungszeichen rechts, Bruchstrich, Multiplikations-Operator, Backslash, Kreuz, geschweifte Klammer links, geschweifte Klammer rechts, Kreuz und Doppelkreuz.
Wenn bei Schritt 158 char(C) kein Unterbrechungszeichen ist, kehrt der Prozeß zu Schritt 156 zurück, wo C erhöht und wiederum mit NCHAR verglichen wird. Wenn char(C) ein Unterbrechungszeichen ist, wird Schritt 160 implementiert, bei welchem der Mikroprozessor feststellt, ob das dem aktuellen Zeichen folgende Zeichen rückgekerned ist. "Kerning" (Unterschneidung) ist der Ausdruck, der zur Spezifizierung der Steuerung des Abstands zwischen zwei Zeichen verwendet wird. Wenn ein Zeichen rückgekerned ist, d. h. negativ unterschnitten, wird dieses Zeichen näher an das vorhergehende Zeichen heran bewegt (was bestimmt wird, indem die Koordinaten des nächsten Zeichens betrachtet werden). Wenn das nächste Zeichen des Textobjektes rückgekerned ist, wird Schritt 163 eingeleitet, bei welchem das bei Schritt 158 aufgefundene aktuelle Unterbrechungszeichen als "Überspringe-Zeichen" markiert wird, was bei dem beschriebenen Ausführungsbeispiel bedeutet, daß in der Zeichenart ein Flag gesetzt wird, so daß das Zeichen übersprungen wird, wenn bei Schritt 164 ein Wort zu der Wortliste hinzugefügt wird. Der Prozeß kehrt zu Schritt 156 zurück, um C zu erhöhen und C mit NCHAR zu vergleichen. Ein Beispiel eines Zeichens, das rückgekerned worden ist, ist in den Fig. 12a und 12b, die weiter unten beschrieben werden, gezeigt.
Wenn bei Schritt 160 das nächste Zeichen nicht rückgekerned ist, wird Schritt 162 eingeleitet, bei dem das ENDFLAG des aktuellen Zeichenobjektes auf 1 gesetzt und der ENDOFFSET gleich C-1 gesetzt wird, was das letzte Zeichen eines Wortes wäre. Bei dem folgenden Schritt 164 wird das identifizierte Wort zu der Wortliste hinzugefügt und die Textobjekte werden aus der verknüpften Liste entfernt. Das hinzugefügte Wort wird aus den Zeichen vorhergehender Textobjekte und/oder des aktuellen Textobjektes entnommen. Der Prozeß des Hinzufügens eines Wortes zu der Wortliste und des Löschens von Textobjekten wird unter Bezug auf Fig. 14 genauer beschrieben. Der Prozeß kehrt dann zu Schritt 156 zurück, wo C erhöht wird. Wenn C bei Schritt 156 gleich oder größer als NCHAR ist, geht der Prozeß mit Schritt 168 weiter, wo OBJNUM erhöht wird. Der Prozeß kehrt dann zu Schritt 144 zurück. Die Zeichen eines weiteren Textobjektes werden analysiert, wenn noch Textobjekte in der verknüpften Liste verblieben sind. Wenn keine weiteren Textobjekte verblieben sind, wird Schritt 169 eingeleitet.
Bei Schritt 169 überprüft der Mikroprozessor, ob das Flush-Flag gesetzt worden ist. Wenn dies der Fall ist, dann wird aktuell das letzte Textobjekt untersucht und Schritt 170 implementiert. Bei Schritt 170 wird das ENDFLAG für das aktuelle Textobjekt auf 1 gesetzt und der ENDOFFSET wird auf das letzte Zeichen des aktuelle Textobjektes gesetzt. Beim nächsten Schritt 172 wird ein Wort aus dem aktuellen Textobjekt zu der Wortliste hinzugefügt. Schritt 172 wird unter Bezug auf Fig. 14 genauer beschrieben. Der Prozeß ist dann, wie bei 173 angezeigt, beendet.
Fig. 12a zeigt eine graphische Darstellung einer verknüpften Liste 174 von aus einem PDF-Dokument gewonnenen Textobjekten 176, wobei eines der Textobjekte ein negativ unterschnittenes (negatively-kerned) Zeichen umfaßt. Die aus der PDF-Datei wiedergewonnenen und in dem Textobjekt 176 angeordneten Textsegmente umfassen die Textsegmente "R", "A" und "NG". Textsegment 178 unterscheidet sich insofern, daß es die Zeichen "T I" umfaßt, bei denen eine Leerstelle 180 zwischen dem "T" und dem "I" enthalten ist. Die in dem PDF- Dokument gespeicherten Koordinateninformationen des Zeichens I zeigen jedoch an, daß bei Anzeige dieses Zeichens mit einer Ausgabeeinrichtung das "I" nahe dem "T" positioniert ist; das "I" ist somit rückwärts unterschnitten (kerned back).
Fig. 12b zeigt eine Darstellung eines Abschnittes eines Bildschirms 22, der Bilder 181 der Textobjekte der verknüpften Liste 174 in Fig. 12a zeigt. Alle Zeichen in der verknüpften Liste, einschließlich der Zeichen "I" und "T", die in dem Textobjekt durch eine Leerstelle voneinander getrennt sind, werden mit normalem Abstand zwischen den Zeichen angezeigt. Das "I" ist rückwärts unterschnitten worden, um den Abstand zwischen den Zeichen auszufüllen. Wenn ein Zeichen negativ unterschnitten ist, zeigt daher ein vor dem unterschnittenen Zeichen positioniertes Unterbrechungszeichen, wie z. B. eine Leerstelle 180, nicht unbedingt an, daß ein Wort beendet ist. Dieses Wortunterbrechungszeichen sollte somit nicht in einem identifizierten Wort enthalten sein und wird als Überspringe-Zeichen markiert, so daß es nicht zu der Wortliste hinzugefügt wird.
Fig. 13 zeigt ein Flußdiagramm, das Schritt 152 in Fig. 11 veranschaulicht, bei dem die Lücke zwischen dem Anfang des aktuellen Textobjektes und dem Ende des letzten Textobjektes analysiert wird. Der Prozeß beginnt bei 190. Bei Schritt 192 überprüft der Mikroprozessor, ob das Textobjekt gedreht ist, d. h. ob das Textobjekt ein Drehungs-Flag 149, wie es in Fig. 10a gezeigt ist, umfaßt. Ist dies der Fall, wird Schritt 194 eingeleitet, bei welchem der Mikroprozessor überprüft, ob die Umgrenzungskästen des aktuellen Textobjektes und des letzten Textobjektes zusammengehören. Ein Umgrenzungskasten ist ein Viereck, dessen Seiten gerade außerhalb der Ränder des Textsegmentes positioniert sind, so daß das Segment vollständig von dem Umgrenzungskasten eingeschlossen wird. Bei dem beschriebenen Ausführungsbeispiel sind für jedes Segment aus dem PDF-Dokument vier Koordinatensätze für alle vier Ecken des Umgrenzungskastens bekannt. Wenn sich die Umgrenzungskästen des Anfangs des aktuellen Textobjektes und des Endes des vorhergehenden Textobjektes überschneiden, dann werden die Umgrenzungskästen als "zusammengehörig" betrachtet: Sie sind Teil desselben Wortes. Verfahren zur Feststellung, ob sich Umgrenzungskästen überschneiden, sind dem Fachmann bekannt. Entsprechend werden die Umgrenzungskästen als zusammengehörig betrachtet, wenn die Umgrenzungskästen der Textobjekt innerhalb einer vorgegebenen Distanz voneinander angeordnet sind. Wenn bei dem beschriebenen Ausführungsbeispiel die Lücke zwischen den Kästen 1/20 des Wertes der Höhe des Umgrenzungskastens des aktuellen Textobjektes oder weniger mißt, werden die Kästen als Teil desselben Wortes betrachtet. Wenn die Umgrenzungskästen gemäß Schritt 194 zusammengehören, wird bei Schritt 196 CHARPOS um 1 erhöht und der Prozeß ist bei 198 beendet. Wenn die Umgrenzungskästen nicht zusammengehören, geht der Prozeß mit Schritt 212 weiter, der weiter unten beschrieben wird.
Wenn das aktuelle Textobjekt bei Schritt 192 nicht als gedreht ermittelt wurde, wird Schritt 200 eingeleitet, bei welchem der Mikroprozessor überprüft, ob die Lücke zwischen dem Anfang des aktuellen Textobjektes und dem Ende des vorhergehenden Textobjektes kleiner als ein vorgegebener Parameter ist. Die Größe der Lücke kann berechnet werden, indem die Koordinaten jedes Textobjektes untersucht werden und unter Verwendung der in den Zeichensatzinformationen jedes Textobjektes enthaltenen Größeninformationen die Breite jedes Zeichens in jedem Textobjekt berechnet wird. Die in jedem Textobjekt enthaltene Flußreihenfolge informiert den Mikroprozessor darüber, welche Koordinaten bei der Berechnung der zur Berechnung des Lückenschwellenwertes benötigten Zeichenbreite verwendet werden sollen. Bei dem beschriebenen Ausführungsbeispiel wird der als Lückenschwellenwert verwendete vorgegebene Parameter von einem speziellen Algorithmus festgelegt:
Wenn das Ende des vorhergehenden Textobjektes ≥ der Anfang des aktuellen Textobjektes + die durchschnittliche Breite der Zeichen in dem aktuellen Textobjekt, oder
wenn der Anfang des aktuellen Textobjektes ≥ das Ende des vorhergehenden Textobjektes + die durchschnittliche Breite des aktuellen Textobjektes geteilt durch 4 ist,
dann ist die Lücke groß genug, um eine Wortunterbrechung zu sein.
Der oben angegebene Algorithmus wird für links-nachrechts oder unten-nach-oben-Flußrichtungen verwendet. Bei rechts-nach-links- und oben nach unten-Flußrichtungen werden die "≥"-Zeichen gegen "≤"-Zeichen und die Plus-Zeichen gegen Minus-Zeichen ausgetauscht. Wenn die Lücke zu klein ist, um als Wortunterbrechung betrachtet zu werden, dann werden der Anfang des aktuellen Textobjektes und der verbleibende Abschnitt des vorhergehenden Textobjektes als Teil desselben Wortes betrachtet und der Prozeß geht mit Schritt 196 weiter, um CHARPOS zu erhöhen. Der Prozeß ist anschließend wie bei 198 gezeigt beendet.
Wenn bei Schritt 200 die Lücke zwischen den Textobjekten nicht geringer als der vorgegebene Parameter war, wird Schritt 204 eingeleitet. Bei Schritt 204 überprüft der Mikroprozessor, ob ein Bindestrich am Ende des vorhergehenden Textobjektes vorhanden ist und ob das Sortier-Flag ausgeschaltet ist. Wenn dies der Fall ist, überprüft der Mikroprozessor bei Schritt 206, ob die Lücke zwischen dem vorhergehenden Textobjekt und dem aktuellen Textobjekt groß ist und ob sich das aktuelle Textobjekt auf einer neuen Zeile befindet. Sind die beiden Bedingungen erfüllt, wird bei Schritt 208 für das letzte Zeichen des vorhergehenden Textobjektes das Trennungszeichen-Flag gesetzt, um anzuzeigen, daß das Wort getrennt und ein Wortfragment ist (die Schritte 204, 206 und 208 werden nicht implementiert, wenn das Sortier-Flag gesetzt ist). Worte in der Wortliste, die ein Trennungszeichen aufweisen, werden später, wie es in Fig. 16 beschrieben ist, mit anderen Worten verkettet. Anschließend wird bei Schritt 196 die Variable CHARPOS erhöht und der Prozeß ist bei 198 beendet. Wenn bei Schritt 206 keine große Lücke vorhanden ist oder sich das aktuelle Textobjekt nicht auf einer neuen Zeile befindet, geht der Prozeß wie unten beschrieben mit Schritt 212 weiter.
Wenn bei Schritt 204 kein Bindestrich in dem letzten Objekt enthalten oder das Sortier-Flag ausgeschaltet ist, dann wird Schritt 210 eingeleitet. Bei Schritt 210 überprüft der Mikroprozessor, ob das aktuelle und das vorhergehende Textobjekt Einzelzeichenobjekte sind und ähnliche Abstände auf beiden Seiten der Objekte aufweisen. Dieses würde anzeigen, daß selbst wenn die Lücke zwischen den Textobjekten groß ist, alle Zeichen des Wortes im gleichen Abstand voneinander angeordnet worden sind, was oft geschieht, um ein Wort, wie z. B. einen Titel, hervorzuheben. Ist dies der Fall, wird bei Schritt 196 die Variable CHARPOS erhöht und der Prozeß ist wie bei 198 gezeigt beendet. Wenn die Bedingungen bei Schritt 210 nicht erfüllt sind, wird die Lücke zwischen den Textobjekten als eine Wortunterbrechung betrachtet, und das vorhergehende Textobjekt ist das Ende eines Wortes. Bei Schritt 212 wird das ENDFLAG des vorhergehenden Textobjektes auf 1 und der ENDOFFSET des vorhergehenden Textobjektes auf die Position des letzten Zeichens des vorhergehenden Textobjektes gesetzt. Das STARTFLAG des aktuellen Textobjektes wird auf 1 und der STARTOFFSET des aktuellen Textobjektes wird auf Null gesetzt. Beim folgenden Schritt 213 wird ein Wort zu der Wortliste hinzugefügt, eins oder mehrere Textobjekte werden aus der verknüpften Liste entfernt und CHARPOS wird auf Null gesetzt. Der Prozeß ist anschließend wie bei 214 gezeigt beendet.
Fig. 14 zeigt ein Flußdiagramm, das den Prozeß des Hinzufügens eines Wortes zu der Wortliste der Textobjekte und das Entfernen von einem oder mehreren Textobjekten aus der verknüpften Liste veranschaulicht. Dieser Prozeß wird bei den Schritten 164 und 172 in Fig. 11 und bei Schritt 213 in Fig. 13 implementiert. Der Prozeß beginnt bei 216 und bei Schritt 218 werden die zwischen einem Bereich von Offsets befindlichen Zeichen als ein Wort zu der Wortliste hinzugefügt. Der Anfang des Bereiches wird durch den STARTOFFSET des Textobjektes in der verknüpften Liste definiert, dessen STARTFLAG auf 1 gesetzt ist. Das Ende des Bereiches wird durch den ENDOFFSET des Textobjektes in der verknüpften Liste definiert, dessen ENDFLAG auf 1 gesetzt ist.
"Überspringe-Zeichen" werden nicht zu der Wortliste hinzugefügt.
Bei Schritt 220 wird die Zeichenart jedes Zeichens zu der Wortliste hinzugefügt. Bei dem beschriebenen Ausführungsbeispiel wird die Zeichenart jedes Zeichens in einem Textobjekt in einem Feld des Textobjektes gespeichert (in Fig. 8a nicht gezeigt). Eine 32-Bit-Zahl kann z. B. die Art des Zeichens, das Überspringe-Flag des Zeichens und andere Parameterarten kennzeichnen. Bei dem nachfolgenden Schritt 222 wird der Umgrenzungskasten des gerade zu der Wortliste hinzugefügten Wortes berechnet. Der Umgrenzungskasten ist das alle Zeichen des Wortes umgebende Viereck. Dieses wird aus den Koordinaten des Anfangs- und Endzeichens des zu der Wortliste hinzugefügten Wortes berechnet. Bei Schritt 222 werden ferner alle verbleibenden Wortmerkmale in der Wortliste gespeichert, wie z. B. Zeichensatz, Farbe, die Zeichennummer (welche bestimmt werden kann, indem eine Zählvariable erhalten wird, wie z. B. bei Schritt 156 in Fig. 11) und die Wortnummer (eine Wortnummerzählvariable kann erhöht werden, wenn ein Wort zu der Wortliste hinzugefügt wird). Wenn ein Wort mehrere Arten eines einzelnen Merkmals umfaßt, können die Merkmale des individuellen Zeichens mit dem Wort in der Wortliste gespeichert werden. Wenn z. B. die ersten drei Zeichen eines 4-Zeichen-Wortes blau sind und das verbleibende Zeichen rot, kann mit dem Wort eine verknüpfte Liste mit zwei Knoten gespeichert werden. Der erste Knoten kann für einen Zeichenbereich 0-3 die Farbe blau festlegen und der zweite Knoten kann die Farbe rot für das Zeichen 4 festlegen.
Bei Schritt 224 werden alle Textobjekte, die vollständig in dem Bereich zwischen STARTOFFSET und ENDOFFSET enthalten sind, aus der verknüpften Liste entfernt. Ein Textobjekt wird folglich entfernt, wenn alle Zeichen des Textobjektes zu der Wortliste hinzugefügt wurden. Wenn ein Textobjekt mehr als ein Wort umfaßt und der ENDOFFSET auf das Ende des ersten Wortes in diesem Textobjekt gesetzt ist, dann würde dieses Textobjekt nicht entfernt werden, da es nicht vollständig in dem Zeichenbereich von STARTOFFSET bis ENDOFFSET enthalten ist.
Bei Schritt 226 wird das STARTOFFSET auf das nächste Zeichen in dem verbleibenden Textobjekt gesetzt, wenn ein solches vorhanden ist. Wenn ein Textobjekt nicht entfernt wird, da es zwei Worte enthält, würde der STARTOFFSET folglich auf den Anfang des zweiten Wortes in dem Textobjekt gesetzt werden. Das STARTFLAG wird auf 1 gesetzt, um anzuzeigen, daß dieses Textobjekt den Anfang eines Wortes enthält. Bei Schritt 228 wird ENDOFFSET des verbleibenden Textobjektes (soweit vorhanden) auf -1 gesetzt, um anzuzeigen, daß bis jetzt keine ENDOFFSET-Position für das verbleibende Textobjekt festgelegt wurde. Ferner wird das ENDFLAG des verbleibenden Textobjektes gelöscht, da es noch nicht bekannt ist, ob das Ende eines Wortes in dem verbleibenden Textobjekt enthalten ist. Der Prozeß wird dann wie bei Schritt 230 angezeigt, beendet.
Fig. 15 zeigt ein Flußdiagramm, das Schritt 100 in Fig. 5 veranschaulicht, bei dem die Worte in der Wortliste sortiert werden. Der Prozeß beginnt bei 236. Bei Schritt 238 werden die Worte in der Wortliste anhand ihrer y-Koordinaten sortiert, so daß die Zeichen in einer Reihenfolge ansteigender y-Koordinaten gespeichert sind. Bei dem beschriebenen Ausführungsbeispiel werden die Koordinaten des unteren linken Punktes des Umgrenzungskastens jedes Wortes verwendet, um die Worte in der Wortliste zu sortieren. Bei dem anschließenden Schritt 240 werden die x-Koordinaten der Worte in der Wortliste sortiert, so daß die Worte in einer Reihenfolge ansteigender x-Koordinaten gespeichert werden. Dies erzeugt eine Wortliste mit Worten, die gemäß ihren Wortkoordinaten in der endgültigen Anzeigeposition gespeichert und geordnet sind. Die Verfahren des Sortierens sind den Fachleuten bekannt. Der Prozeß ist dann wie bei 242 gezeigt, beendet.
Fig. 16 zeigt ein Flußdiagramm, das Schritt 102 in Fig. 5 veranschaulicht, bei dem die Wortliste neu aufgebaut wird und in die endgültige Form gebracht wird, um an den Client gesendet zu werden. Einige der Worte in der Wortliste, insbesondere wenn das PDF-Dokument ein verstreutes Dokument ist, sind Wortfragmente, d. h. sie sind Abschnitte eines Wortes, die mit anderen Wortfragmenten in der Wortliste verkettet werden müssen, um ein vollständiges Wort zu bilden. Die Verkettung wird als "Neuaufbau" der Wortliste betrachtet. Der Prozeß beginnt bei 244. Bei Schritt 246 wird eine Wortvariable W auf 0 initialisiert und mit NWORDS - 1 verglichen, wobei NWORDS die Anzahl der Worte in der Wortliste angibt. Wenn W keiner als NWORDS - 1 ist, geht der Prozeß mit 248 weiter, wo Wort(W + 1) - Wort(W) mit GAP verglichen wird. Das heißt, die Koordinaten des Wortes(W + 1) und des Wortes(W) werden voneinander subtrahiert, um festzustellen, ob die Worte mit einem geringeren Abstand als der Lückenschwellenwert GAP angeordnet sind, der bei dem beschriebenen Ausführungsbeispiel 1/8 der Höhe des Umgrenzungskastens von Wort(W) beträgt. Wenn die Differenz geringer als GAP ist, sind die beiden Worte nah genug beieinander positioniert, um ein einziges Wort zu bilden und das Wort(W + 1) und das Wort(W) werden bei Schritt 250 verkettet. Der Prozeß kehrt anschließend zur Erhöhung von W zu Schritt 246 zurück.
Wenn die Differenz zwischen Wort(W + 1) und Wort(W) gleich oder größer als GAP ist, wird Schritt 252 implementiert, bei dem der Mikroprozessor feststellt, ob Wort(W) einen Bindestrich enthält, die Lücke zwischen Wort(W) und Wort(W + 1) groß ist und ob sich Wort(W + 1) auf einer neuen Zeile in Flußrichtung befindet. Die Flußrichtung eines Wortes wird festgestellt, indem seine Umgrenzungskastenkoordinaten betrachtet werden. Wenn der untere rechte Punkt größer als der untere linke Punkt ist, ist die Flußrichtung links- nach-rechts, wenn der untere rechte Punkt größer als der untere linke Punkt ist, ist sie rechts-nach-links u. s. w. Sind diese Bedingungen erfüllt, so wird bei Schritt 254 das Trennungszeichen-Flag für das Bindestrichzeichen gesetzt (welches zuvor nicht gesetzt wurde, wenn das PDF-Dokument als verstreut gefunden wurde, d. h. das Sortier-Flag gesetzt war) und Wort(W + 1) und Wort(W) werden bei Schritt 250 verkettet. Der Prozeß kehrt dann zur Erhöhung von W zu Schritt 246 zurück. Wenn die Bedingungen nicht erfüllt sind, kehrt der Prozeß zu Schritt 246 zurück.
Sobald der Wert von W auf einen Wert kleiner oder gleich NWORDS - 1 erhöht worden ist, sind alle Worte in der Wortliste bezüglich einer Verkettung untersucht worden und der Prozeß ist wie bei 256 gezeigt beendet.
Während diese Erfindung im Hinblick auf mehrere bevorzugte Ausführungsbeispiele beschrieben worden ist, ist es zu erwarten, daß dem Fachmann beim Lesen der Beschreibung und bei dem Studium der Zeichnung Abänderungen, Modifikationen und Permutationen davon klar werden. Die Erfindung wird z. B. anhand der Verwendung für portable elektronische Dokumente, wie z. B. PDF-Dokumenten, beschrieben. Es können jedoch andere Dateien oder Ansammlungen von Daten, die sowohl Zeichencodes oder andere Objekte als auch andere Anzeigeinformationen wie z. B. Positionsinformationen für diese Objekte enthalten, zur Identifizierung von Worten verarbeitet werden. Ferner wurden bestimmte Fachausdrücke aus Gründen der Beschreibungsklarheit verwendet und nicht um die vorliegende Erfindung zu beschränken. Daher ist es beabsichtigt, daß die folgenden beigefügten Ansprüche alle derartigen Abänderungen, Modifikationen und Permutationen umfassen, die in den Schutzbereich der vorliegenden Erfindung fallen.

Claims

1. Ein System zum Identifizieren von Worten in einem portablen elektronischen Dokument (Fig. 2, 3), wobei das System eine digitale Verarbeitungsreinrichtung umfaßt, welche die folgenden Hardware- und Softwaremittel aufweist:

(a) Hardware- und Softwaremittel zum Wiedergewinnen eines Textsegments (46) einschließlich seiner zugehörigen Positionsdaten (48) aus einem Dokument, das wenigstens eine Seite einschließlich einer Mehrzahl von Textsegmenten und zugeordneten Positionsdaten aufweist, wobei jedes Textsegment eine Mehrzahl von Zeichen enthält, die als Zeichen aber nicht als Worte (46, 46') identifiziert worden sind, wobei die Reihenfolge der Textsegmente nicht der Reihenfolge entspricht, in welcher sie erscheinen sollen, wenn sie angezeigt werden (Fig. 3a, 3b);

(b) Hardware- und Softwaremittel zum Erzeugen eines Textobjekts (136) aus jedem Textsegment und zum Eingeben des Textobjekts in eine verknüpfte Liste von Textobjekten (Fig. 8b, 8c), wobei jedes Textobjekt einen Umgrenzungskasten aufweist;

(c) Hardware- und Softwaremittel zum Identifizieren von Worten aus der verknüpften Liste durch (A) Analysieren des Textobjekts nach Wortunterbrechungen und durch Analysieren (200) einer Lücke zwischen dem aktuellen Textobjekt und einem vorgehenden Textobjekt unter Verwendung der zugehörigen Positionsdaten und durch (B) Bestimmen, ob die Umgrenzungskästen zwischen dem aktuellen Textobjekt und dem vorhergehenden Textobjekt sich überschneiden (194);

(d) Hardware- und Softwaremittel zum Hinzufügen identifizierter Worte zu einer Wortliste (164); und

(e) Hardware- und Softwaremittel zum Wiederholen der Schritte (a) bis (e), bis das Ende der Seite erreicht ist.

2. Ein System nach Anspruch 1, ferner aufweisend:

auf der Datenverarbeitungseinrichtung implementierte Identifikationsmittel zum Bestimmen, ob die Seite ein Sortieren erfordert.

3. Ein System zum Identifizieren von Worten nach Anspruch 1, wobei jedes Zeichen zumindest Teil eines Textsegments ist, und wobei jedes Textsegment eine zugehörige x-Koordinate und eine y-Koordinate aufweist, welche ein x,y-Koordinatenpaar definieren, das anzeigt, wo das Textsegment angezeigt werden soll.

4. Ein System zum Identifizieren von Worten nach Anspruch 3, wobei das Wortidentifizierungsmittel ein Textsegment als Textobjekt in einer verknüpften Liste speichert.

5. Ein System zum Identifizieren von Worten nach Anspruch 4, wobei zugehörige, das Textsegment beschreibende Informationen einschließlich der x,y-Koordinatenpaarinformationen in dem Textobjekt gespeichert werden.

6. Ein System zum Identifizieren von Worten nach Anspruch 5, wobei das Wortidentifizierungsmittel wenigstens ein Wort aus den Textobjekten in der verknüpften Liste identifiziert und das Wort in einer Wortliste speichert.

7. Ein System zum Identifizieren von Worten nach Anspruch 6, wobei das Wortidentifizierungsmittel ein Wort identifiziert, indem es ein Wortunterbrechungszeichen in den Textobjekten auffindet.

8. Ein System zum Identifizieren von Worten nach Anspruch 7, wobei das Wortidentifizierungsmittel ein Wort identifiziert, indem es zwischen benachbarten Textobjekten eine Lücke auffindet, deren Größe größer als eine Schwellenwertgröße ist.

9. Ein System zum Identifizieren von Worten nach Anspruch 8, wobei das Wortidentifizierungsmittel die Lücke erfaßt, indem die räumliche Distanz zwischen benachbarten Textobjekten in der verknüpften Liste durch Benutzen der Koordinaten der in den Textobjekten gespeicherten Textsegmente analysiert werden.

10. Ein System zum Identifizieren von Worten nach Anspruch 9, wobei das Wortidentifizierungsmittel wenigstens einen Abschnitt benachbarter Textobjekte als ein Wort zu der Wortliste hinzufügt, wenn die Lücke zwischen den benachbarten Textobjekten unterhalb der Schwellenwertgröße liegt.

11. Ein System zum Identifizieren von Worten nach Anspruch 1, wobei das Wortidentifizierungsmittel ferner Verstreute-Dokument-Identifikationsmittel und Sortiermittel zum Sortieren der Wortliste, wenn das Verstreute-Dokument-Identifikationsmittel feststellt, daß die Seite ein Sortieren erfordert, aufweist.

12. Ein System zum Identifizieren von Worten nach Anspruch 11, wobei jedem Wort in der Wortliste eine x-Koordinate und eine y-Koordinate zugeordnet ist, welche ein x,y- Koordinatenpaar definieren, das anzeigt, wo das Wort auf einer angezeigten Seite angezeigt werden soll, und wobei das Sortiermittel die Worte in der Wortliste zunächst nach ihren y-Koordinaten und dann nach ihren x-Koordinaten sortiert.

13. Ein System zum Identifizieren von Worten nach Anspruch 9, wobei das Wortidentifizierungsmittel Worte in der Wortliste, welche innerhalb einer Schwellenwertdistanz voneinander angeordnet sind, und Worte, welche am Ende des Wortes ein Bindestrich-Zeichen enthalten, verkettet.

14. Ein System zum Identifizieren von Worten nach Anspruch 4, wobei jedes der Textobjekte einen zugehörigen Umgrenzungskasten aufweist und wobei jedes der Textobjekte anzeigt, ob es ein rotiertes Textobjekt ist, und wobei wenigstens Abschnitte benachbarter rotierter Textobjekte als ein Wort zu der Wortliste durch das Wortidentifizierungsmittel hinzugefügt werden, wenn sich ihre Umgrenzungskästen überschneiden oder sie durch weniger als eine vorgegebene Lücke voneinander getrennt sind.

15. Ein Verfahren zum Identifizieren von Worten in einem portablen elektronischen Dokument (Fig. 2, 3), umfassend die Schritte:

(a) Wiedergewinnen eines Textsegments (46) einschließlich seiner zugehörigen Positionsdaten (48) aus einem Dokument, das wenigstens eine Seite einschließlich einer Mehrzahl von Textsegmenten und zugehörigen Positionsdaten aufweist, wobei jedes Textsegment eine Mehrzahl von Zeichen enthält, die als Zeichen aber nicht als Worte (46, 46) identifiziert worden sind, wobei die Reihenfolge der Textsegmente nicht der Reihenfolge entspricht, in welcher sie erscheinen sollten, wenn sie angezeigt werden (Fig. 3a, 3b).

(b) Erzeugen eines Textobjekts (136) aus jedem Textsegment und Eingeben des Textobjekts in eine verknüpfte Liste von Textobjekten (Fig. 8b, 8c), wobei jedes Textobjekt einen Umgrenzungskasten aufweist;

(c) Identifizieren von Worten aus der verknüpften Liste, indem (A) das Textobjekt nach Wortunterbrechungen analysiert wird und indem eine Lücke zwischen dem aktuellen Textobjekt gegenüber dem früheren Textobjekt unter Verwendung der zugehörigen Positionsdaten analysiert wird (200), und indem (B) bestimmt wird, ob die Umgrenzungskästen zwischen dem aktuellen Textobjekt und dem vorhergehenden Textobjekt einander überschneiden (194);

(d) Hinzufügen identifizierter Worte zu einer Wortliste; und

(e) Wiederholen der Schritte (a) bis (e) bis Ende der Seite erreicht ist.

16. Ein Verfahren nach Anspruch 15, wobei die mehreren Textsegmente ein Teil eines portablen elektronischen Dokuments sind, das durch eine Seitenbeschreibungssprache dargestellt wird, und wobei Kommandos der Seitenbeschreibungssprache interpretiert werden, um die Textsegmente zu identifizieren und die zugehörigen Positionsdaten wiederzugewinnen.

17. Ein Verfahren nach Anspruch 16, wobei die zugehörigen Positionsdaten x- und y-Koordinaten für ein Textsegment einschließen und wobei die x- und y-Koordinaten in dem dem Textsegment zugeordneten Textobjekt gespeichert werden.

18. Ein Verfahren nach Anspruch 15, wobei der Schritt des Erzeugens eines Textobjekts eine Neuzuweisung der Zeichen der Textsegmente unter Verwendung einer Tabelle und das Speichern der neu zugewiesenen Zeichen in dem Textobjekt einschließt.

19. Ein Verfahren nach Anspruch 15, wobei das Wort identifiziert wird, indem ein Wortunterbrechungszeichen in einem Textobjekt aufgefunden wird.

20. Ein Verfahren nach Anspruch 15, wobei das Wort identifiziert wird, indem zwischen benachbarten Textobjekten eine Lücke aufgefunden wird, die eine Größe aufweist, die größer als eine Schwellenwertgröße ist.

21. Ein Verfahren nach Anspruch 20, wobei die Lücke unter Benutzung der zugehörigen Positionsdaten aufgefunden wird.

22. Ein Verfahren nach Anspruch 21, wobei wenigstens Abschnitte der benachbarten Textobjekte als ein Wort identifiziert werden, wenn die Lücke zwischen den benachbarten Textobjekten geringer als eine Schwellenwertgröße ist.

23. Ein Verfahren nach Anspruch 21, ferner umfassend einen dem Schritt (e) folgenden Schritt des Sortierens der Wortliste, sofern die Seite des Dokuments als verstreut angesehen wird.

24. Ein Verfahren nach Anspruch 23, wobei die Worte x- und y-Koordinaten ihrer Positionen auf einer angezeigten Seite enthalten und wobei die Worte zunächst nach den y-Koordinaten und dann nach den x-Koordinaten sortiert werden.

25. Ein Verfahren nach Anspruch 24, ferner umfassend einen Schritt des Verkettens der Worte, welche innerhalb einer Schwellenwertdistanz voneinander angeordnet sind, und derjenigen Worte, welche ein Bindestrich-Zeichen am Ende des Wortes enthalten, in einer Wortliste.