DE69330701T2 - Verfahren zur Durchführung der Suche nach Ähnlichkeiten mit einer Abfrage in einer Dokumentenmenge - Google Patents

Description

• Die Erfindung betrifft Verbesserungen bei Text- und Bildverarbeitungsverfahren und -techniken und konkret Verbesserungen bei Verfahren zur Wort- und Begriffsidentifizierung und zur -suche in Dokumentbildern, noch genauer Verbesserungen bei Verfahren zum rechnergestützten Durchsuchen einer Reihe von Dokumentbildern nach Abfragewörtern oder -begriffen, die weniger Speicherplatz erfordern.
• Das Interesse an einer Dokumentverarbeitung sowohl in elektronischer als auch Papierform vorliegender Dokumente ist immer stärker geworden. Oft wird es gewünscht, bestimmte Suchbegriffe innerhalb einer großen Menge von Dokumenten aufzufinden, z. B. bei der Recherche von Aufsätzen oder Publikationen zu speziellen Themen, beim Auffinden bestimmter Aussagen in Erklärungen oder Enthüllungen, die spezielle Wörter oder Wendungen enthalten, beim Finden relevanter Gerichtsbeschlüsse mit bestimmten Schlüsselbegriffen in einer juristischen Datenbank und in vielerlei anderen Fällen.
• Mitunter liegen die Dokumente in elektronischer Form vor, wobei der Text und die Bilder auf einem elektronischen Speichermedium codiert worden sind, von dem die Dokumente zur genauen Durchsicht oder zur Erstellung einer "hard copy", also eines Papierausdrucks abgerufen werden können. In der Vergangenheit wurde beim Durchsuchen einer großen Anzahl von Dokumenten nach einem oder mehreren Suchbegriffen, meist Wörter, ein Index erstellt, mit dem die Suchbegriffe verglichen wurden. Ein solcher Index besteht meist aus zwei Teilen. Bei dem ersten handelt es sich um einen Dokument-Identifier oder -namen (hier Dokument-ID genannt). Der Dokument-ID bezeichnet einfach jedes Dokument in der Dokumentsammlung, und zwar mit einer Zahl, einem Schlüsselbegriff oder einer -wendung oder irgendeiner anderen eindeutigen Kennzeichnung. Den zweiten Teil bilden ein Wort und die Anzahl des Auftretens des Wortes im Dokument, in dem es identifiziert wurde (hier auch "Worthäufigkeit" genannt).
• Bislang wurde zum Identifizieren der speziellen Dokumente, in denen die Suchwörter vorhanden sind, der Index aller Wörter in einen Rechnerspeicher 10 eingestellt, woraufhin die Suchwörter nacheinander mit jedem einzelnen Wort im Speicher verglichen werden, wie in Fig. 1 abgebildet ist. Nach dem Vergleich jedes Wortes werden jene Dokumente, in denen es vorkam, vermerkt, es wird ein Zählwert oder Ergebnis (Score) von ihnen ermittelt und festgehalten. Folglich wird ein erstes Suchwort bearbeitet (11), und ein Teilergebnis dafür errechnet (13). Danach wird ein nächstes Suchwort bearbeitet (14) und ein Gesamtergebnis berechnet (16). Dieses Gesamtergebnis wird solange weiter erzeugt, bis alle nachfolgenden Suchwörter vollständig verarbeitet und die Gesamtergebnisse ermittelt sind (17). Nachdem die Suche nach dem letzte Wort beendet ist, können mit den Zählergebnissen die Dokumente identifiziert (18) oder in der Reihefolge der "Treffer" bezüglich der Suchwörter angeordnet und n einer Liste der gefundenen Dokumente angezeigt werden (19).
• Für solche Verfahren wird allerdings viel zugreifbarer Rechnerspeicherplatz benötigt, vor allem bei großen Dokumentsammlungen. Wegen dieses Speicherbedarfs ist die Dokumentsuche auf Personal- oder tragbaren Computern selbst dann praktisch oft nicht durchführbar, wenn die Dokumente auf Speicherplatten mit großer Kapazität gespeichert sind. Allgemein sind dazu Großrechner mit entsprechend großer Speicherkapazität erforderlich.
• Auf dem Gebiet der Bildverarbeitung sind in jüngster Zeit direkte Papierdokument- Suchmethoden vorgeschlagen worden, bei denen eine oder mehrere morphologische Eigenschaften der Bilder auf dem Dokument verarbeitet und zum Vergleich mit einem Suchwort, -begriff oder -bild verwendet werden. Nach diesen Verfahren wird ein Dokument eingescannt, und die morphologischen Eigenschaften seiner verschiedenen Bilder werden direkt bestimmt, ohne den Inhalt des Bildes zu decodieren. Demgegenüber kann beim Durchsuchen einer großen Dokumentmenge ein Verfahren verwendet werden, mit dem ein Index erstellt wird - ähnlich wie oben beschrieben, allerdings mit einer Häufigkeitsliste der morphologischen Eigenschaften anstelle der Wörter. Auch hier wird, besonders bei großen Dokumentsammlungen, zur Durchführung von Abfragen viel Speicherplatz benötigt.
• In dem Dokument von D. Lucarella "Heuristics to locate the best document set in information retrieval systems", von der 8. Internationalen Jahrestagung zu Computern und Kommunikation vom 22. März 1989, USA, Seiten 567-571, ist ein System zum Vergleich eines Suchbegriffs mit einer Reihe von Dokumenten zwecks Abfrage der relevanten Dokumente beschrieben. Dabei findet in allen Dokumenten eine Match- Suche nach dem ersten Suchwort statt, anschließend erfolgt die Betrachtung des nächsten Suchwortes in allen Dokumenten. Dies wird für alle Suchwörter in der Abfrage wiederholt. Dadurch ist es möglich, die relevanten Dokumente aufzufinden, jedoch ist für das Verfahren eine große Menge zugreifbaren Speichers, insbesondere bei großen zusammenhängenden Dokumenten, erforderlich.
• Angesichts dessen hat die vorliegende Erfindung das Ziel, ein verbessertes Verfahren zur Durchführung einer Suche nach Ähnlichkeiten in einer großen Dokumentsammlung mit weniger Speicher als bei herkömmlichen Verfahren zu schaffen.
• Ein anderes Ziel der Erfindung besteht in der Schaffung eines verbesserten Verfahrens der beschriebenen Art, das effizient angewandt werden kann.
• Durch die Erfindung wird ein Verfahren zur Durchführung einer Suchvorgangs in einer Vielzahl von Dokumenten gemäß der beigefügten Patentansprüche 1 und 2 bereitgestellt.
• Im weiteren Sinne der Erfindung wird ein Verfahren vorgestellt, mit dem eine Vielzahl von Dokumenten nach Ähnlichkeiten mit einem Suchbegriff oder -wort durchsucht wird. Zu dem Verfahren gehört die Abfrage eines ersten Dokuments und das Ermitteln der Auftrittshäufigkeit des Suchwortes im ersten Dokument. Anschließend wird ein nächstes Dokument abgefragt und festgestellt, wie oft das Suchwort darin vorkommt. Diese Schritte werden solange wiederholt, bis jedes aus der Vielzahl der Dokumente abgefragt und die Häufigkeit des Suchwortes in jedem von ihnen ermittelt worden ist.
• Das Suchwort kann mehrere Suchbegriffe umfassen, die insgesamt nacheinander in jedem Dokument und nicht einzeln in der gesamten Dokumentsammlung gesucht werden. Ausgehend von der Häufigkeit des Auftretens der Suchwörter in jedem Dokument werden danach die Dokumente bewertet und in eine entsprechende Rangliste eingeordnet.
• Bei einer Ausführungsform wird eine Liste der in dem aufgefundenen Dokument enthaltenen Wörter erzeugt, und die Suchwörter werden mit der erzeugten Wortliste verglichen.
• Bei Einer anderen Ausführungsform werden alle Suchwörter mit einem ersten Teil der Dokumente und anschließend mit einem zweiten Teil verglichen. Danach werden sie nach der festgestellten Häufigkeit der Suchwörter in jedem Dokument geordnet und in einer Rangliste festgehalten.
• Bei einer anderen Ausführungsform wird ein invertierter Index der Dokumente erstellt. Anstelle des Abfragens eines Dokuments wird in diesem Fall das Segment einer Liste mit den Paaren von Dokument-IDs und Häufigkeitsangaben des Suchbegriffs im Hinblick auf den Suchbegriff und das Dokument untersucht.
• Die Erfindung ist in den beigefügten Zeichnungen abgebildet, wobei:
• Fig. 1 ein Blockdiagramm ist, welches die einzelnen Schritte einer Suche nach Ähnlichkeiten in einer Dokumentmenge gemäß dem bisherigen Stand der Technik darstellt, und
• Fig. 2 im Blockdiagramm die Schritte einer Suche nach Ähnlichkeiten in einer Dokumentmenge gemäß einer bevorzugten Ausführungsform der Erfindung zeigt.
• Die vorliegende Erfindung betrifft ein Suchverfahren in einer Vielzahl von Dokumenten, das in jedem herkömmlichen Informationsverarbeitungssystem ausgeführt werden kann, wie es z. B. in Fig. 1 der europäischen Patentanmeldung Nr. 93396281.2 schematisch dargestellt und anhand dieser Figur beschrieben worden ist. Mit der vorliegenden Anmeldung wurde eine Kopie davon eingereicht.
• Die vorliegende Erfindung betrifft Techniken zum Suchen nach Ähnlichkeiten, bei denen die Ähnlichkeitssuche mittels Abfrage, bestehend aus einer Sequenz aus einem oder mehreren Wörtern, Silben, Wendungen, Bildern oder dergleichen, erfolgt. Zwar wird in dieser Patentschrift der Begriff "Suchwort" verwendet, doch natürlich umfasst das "Wort" ein Wort, einen Wortteil oder Teile eines Dokuments oder Bildes, welches Buchstaben, Zahlen oder andere Sprachsymbole, einschließlich nichtalphabetischer Sprachzeichen, wie z. B. Ideogramme, fremdsprachliche Syllabarien sowie Wort- und Zeichensubstitute, z. B. "Wildcard" oder Stellvertretersymbole oder dergleichen. Im Ergebnis der Ähnlichkeitssuche entsteht eine Rangliste von Dokumenten aus der indexierten Sammlung mit den höchsten Ähnlichkeitsquotienten bei der Abfrage. Der Ähnlichkeitsquotient eines Dokuments in Bezug auf eine Abfrage ist eine Zahl, die aus einer anwenderdefinierten Formel resultiert, welche die Anzahl der Dokumente, in denen das Suchwort erscheint, die Häufigkeit des Vorkommens in jedem Dokument und die Anzahl der Dokumente insgesamt einschließen kann. Manchmal ist es günstig, unterschiedliche Wichtungen der relativen Bedeutung von Suchwörtern vorzunehmen oder eine Reihefolge des Erscheinens von Suchwörtern oder ein anderes ähnliches Suchkriterium zu verwenden.
• Für eine erfindungsgemäße Ähnlichkeitssuche wird vorzugsweise ein invertierter Index zum Einsatz gebracht. Dieser enthält eine Liste aus paarweise angeordneten Dokument-Identifiern und der Worthäufigkeit für jedes eindeutige Wort in der Dokumentmenge bzw. -sammlung. Die Worthäufigkeit gibt an, wie viel Mal das Wort in dem durch den dazugehörigen Dokument-ID identifizierten Dokument vorkommt. Vorzugsweise werden diese Paare, bestehend aus Dokument-ID und Worthäufigkeit, in aufsteigender oder absteigender Reihenfolge der Dokument-IDs angeordnet. Das erfindungsgemäße Verfahren steht im Gegensatz zu früheren Verfahren, bei denen ein Ähnlichkeitsquotient gewöhnlich berechnet wurde, indem für ein einziges Suchwort die gesamte Liste der Dokument-IDs/Worthäufigkeitspaare durchgegangen und nachdem jedes Suchwort bearbeitet worden ist, die Teilergebnisse für jedes Dokument in der Liste berechnet werden. Demgegenüber werden bei dem Verfahren gemäß einer bevorzugten Ausführungsform der Erfindung (siehe Fig. 2) nicht alle Dokument-ID/Worthäufigkeitspaare für ein Suchwort abgefragt, ehe auf jene eines anderen Suchwortes zugegriffen wird, sondern bei dem Vergleich wird von einem Strom von Dokument/Worthäufigkeitspaaren zu einem anderen umgeschaltet. Folglich werden alle Dokument-ID/Worthäufigkeitspaare für ein Dokument aufgesucht, ehe zu anderen übergegangen wird.
• Dementsprechend werden die Dokument-ID/Worthäufigkeitspaare für das erste Dokument in einen Rechnerspeicher eingestellt (20). Daraus wird erkennbar, dass sich das erfindungsgemäße Verfahren besonders eignet, wenn nur begrenzte Speicherkapazität zur Verfügung steht, es ist analog zu einem n-fachen Mischalgorithmus, wenngleich in diesem Fall kein Mischen erfolgt, sondern eine Reihe von Berechnungen durchgeführt wird.
• Als Nächstes werden alle Suchwörter im Hinblick auf das erste Dokument verglichen, gesucht oder verarbeitet (21), und es wird ein vollständiges Ergebnis für dieses erste Dokument errechnet (23). Bei einer erfindungsgemäßen Ähnlichkeitssuche ist es wünschenswert, eine Liste aller Dokumente in der Sammlung oder zumindest eine Liste all jener Dokumente zu führen, die in den bearbeiteten Listen durchgesehen wurden. Dies ist günstig, um die Teilergebnisse der Dokumente zurückverfolgen zu können. Auf diese Liste kann an Punkten zugegriffen werden, die den Dokument-ID- Teilen der gerade in Bearbeitung befindlichen Dokument-ID/Worthäufigkeitspaare entsprechen. Wenn die Liste für jedes Suchwort bearbeitet ist, kann je nach der Reihenfolge der Dokument-IDs an aufsteigenden (oder absteigenden) Punkten auf die Dokumentliste zugegriffen werden.
• Weiter geht es, indem die Dokument-ID/Worthäufigkeitspaare für das nächste Dokument in den Rechnerspeicher eingestellt worden sind (25), erneut alle Suchwörter im Hinblick auf das nächste Dokument verarbeitet werden (27) und ein neues Ergebnis für das nächste Dokument berechnet wird (28). Dieser Prozess wird solange fortgesetzt, bis alle Dokumente verarbeitet worden sind (30). Danach werden die vollständig berechneten bzw. Gesamtergebnisse in einer Rangliste sortiert, welche angezeigt wird (31). Will man hingegen sofort nach Ende dieses Prozesses eine sortierte Liste erstellen, dann kann man gegebenenfalls nach jeder Teilberechnung das veränderte Gesamtergebnis für die Dokumente in der Rangliste entsprechend neu anordnen.
• Wenn bei früheren Verfahren nicht genügend Speicherplatz im System vorhanden war, um die gesamte Liste zusammen mit dem Teil der Liste von gerade bearbeiteten Dokument-ID/Worthäufigkeitspaaren für das betreffende Suchwort im Speicher zu behalten, dann wurde zum Vergleich mit jedem Suchwort der Großteil der Dokumentliste von einem externen Speicher eingelagert. Bei dem erfindungsgemäßen Verfahren hingegen wird von einem Strom von Paaren für das Suchwort zum nächsten geschaltet, um sämtliche Berechnungen, z. B. für den niedrigsten Dokument-ID der verschiedenen Listen, auszuführen, ehe es zum zweitniedrigsten Dokument-ID weitergeht, und so weiter. Erfindungsgemäß braucht man nur genug Speicher für den Eintrag jeweils eines Dokuments in der Dokumentliste und für jedes Suchwort einen Eintrag in der Liste der Dokument-ID/Worthäufigkeitspaare. Da bei umfangreichen Dokumentsammlungen die Dokumentenliste sehr lang ist, wird auf diese Weise eine Berechnung mit viel geringerem Speicherbedarf als bei früheren Verfahren möglich. Natürlich können für Vergleiche zwischen den Identifikationen des aktuellen Elements in den einzelnen Suchwortlisten mehr Berechnungen als bei früheren Verfahren notwendig sein. Verglichen mit den Platten-Input/Output-Kosten ist diese Berechnung jedoch preisgünstig.
• Bei einer alternativen Ausführungsform des erfindungsgemäßen Verfahrens werden mehrere Dokumente gleichzeitig verarbeitet. Die Anzahl von Dokumenten könnte ausgehend vom verfügbaren Speicherplatz zum Zeitpunkt des Programmlaufs oder ausgehend vom später voraussichtlich verwendeten Gerät zum Zeitpunkt des Kompilierens festgelegt werden. Dabei würde jede Liste von Dokument-ID/Worthäufigkeitspaaren solange bearbeitet werden, bis die Dokument-Identifikationen über den gegenwärtig bearbeiteten Bereich von Dokument-Identifikationen hinausgehen. Danach würde die Berechnung bei der nächsten Suchwortliste fortgesetzt. Bei dieser Variante verringert sich die Zahl zusätzlicher Berechnungen, obwohl sie diese nicht vollständig eliminiert, und es wird mehr Speicher benötigt, wenn auch nicht so viel wie bei früheren Verfahren.

Claims (8)

1. Verfahren zum Durchsuchen einer Vielzahl von Dokumenten nach Ähnlichkeiten mit einer Vielzahl von Suchwörtern, wobei das Verfahren dadurch gekennzeichnet ist, dass es folgende Schritte umfasst:

(a) Abfragen eines ersten Dokuments,

(b) Feststellen, wie viele Male jedes aus der Vielzahl von Suchwörtern im ersten Dokument vorkommt;

(c) Abfragen eines nächsten Dokuments,

(d) Feststellen, wie viele Male jedes aus der Vielzahl von Suchwörtern im nächsten Dokument vorkommt,

(e) Wiederholen der Schritte (c) und (d) solange, bis jedes aus der Vielzahl von Dokumenten durchsucht und die Häufigkeit jedes aus der Vielzahl der Suchwörter in jedem aus der Vielzahl von Dokumenten ermittelt worden ist.

2. /erfahren zum Durchsuchen einer Vielzahl von Dokumenten nach Ähnlichkeiten mit einer Vielzahl von Suchwörtern, wobei das Verfahren dadurch gekennzeichnet ist, dass es folgende Schritte umfasst:

(a) Abfragen eines ersten Teils der Vielzahl von Dokumenten,

(b) Feststellen, wie viele Male jedes aus der Vielzahl von Suchwörtern in jedem Dokument im ersten Teil aus der Vielzahl von Dokumenten vorkommt,

(c) Wiederauffinden eines zweiten Teils aus der Vielzahl von Dokumenten,

(d) Feststellen, wie viele Male jedes aus der Vielzahl von Suchwörtern in jedem Dokument im zweiten Teil aus der Vielzahl von Dokumenten vorkommt.

3. Verfahren nach Anspruch 1 oder Anspruch 2, welches weiterhin das Aufstellen einer Rangordnung für die Dokumente entsprechend der ermittelten Häufigkeit der Suchwörter in jedem Dokument umfasst.

4. Verfahren nach Anspruch 3, welches weiterhin das Erstellen einer Dokumentenliste entsprechend ihrer Rangordnung umfasst.

5. Verfahren nach einem der vorangehenden Ansprüche, wobei die genannten Schritte des Abfragens eines Dokuments das Einbringen eines Bildes aus dem durchsuchten Dokument in einen elektronischen Speicher einschließen.

6. Verfahren nach einem der vorangehenden Ansprüche, wobei der Schritt des Ermittelns der Häufigkeit jedes der Suchwörter das Erstellen einer Liste von Wörtern, die in dem durchsuchten Dokument enthalten sind, und das Vergleichen der Suchwörter mit der erstellten Wortliste umfasst.

7. Verfahren nach Anspruch 6, wenn eine Abhängigkeit von Anspruch 1 vorliegt, wobei das Verfahren zum Erstellen einer Wortliste auch die Erzeugung eines Indexes mit Einträgen für sämtliche Wörter sämtlicher Dokumente umfasst, von denen jedes Dokument durch einen Dokument-Identifier gekennzeichnet ist, jeder Eintrag einen Dokument-Identifier und eine Angabe darüber enthält, wie häufig ein Wort in dem identifizierten Dokument erscheint, und wobei das Verfahren zum Vergleichen der Suchwörter mit der erstellten Wortliste für jeden Dokument-Identifier wiederum den Vergleich jedes aus der Vielzahl von Suchwörtern mit jedem Wort einschließt, das mit jedem Dokument-Identifier gekoppelt ist.

8. Verfahren nach Anspruch 6, wenn eine Abhängigkeit von Anspruch 2 vorliegt, wobei das Verfahren zum Aufstellen einer Wortliste das Erstellen eines Indexes für sämtliche Wörter eines Teils aller Dokumente umfasst, wobei jedes der Dokumente durch einen Dokument-Identifier gekennzeichnet ist und jeder Eintrag einen Dokument-Identifier und eine Angabe enthält, wie häufig ein Wort in dem identifizierten Dokument erscheint, und wobei das Verfahren zum Vergleichen der Suchwörter mit der erstellten Wortliste für jeden Dokument-Identifier wiederum den Vergleich jedes aus der Vielzahl von Suchwörtern mit jedem Wort einschließt, das mit jedem Dokument-Identifier gekoppelt ist.