DE10160920B4 - Verfahren und Vorrichtung zur Erzeugung eines Extrakts von Dokumenten - Google Patents

Abstract

Verfahren zur automatischen Erzeugung eines Extrakts für ein Dokument, wobei
– das Dokument Bestandteil einer für ein Informationsbeschaffungssystem elektronisch verfügbaren Dokumenten-Kollektion ist,
– ein Benutzer mit dem Informationsbeschaffungssystem interagiert, wobei
– das Informationsbeschaffungssystem dem Benutzer bestimmte Dokumente aus der Kollektion anbietet und
– der Benutzer unter den angebotenen Dokumenten bestimmte auswählt, um sie sich anzeigen zu lassen,
– das Informationsbeschaffungssystem als zeitliche Reihenfolge protokolliert, welche Dokumente der Benutzer in welcher Reihenfolge ausgewählt hat,
– der Benutzer das Dokument vorgibt, für das das Extrakt erzeugt werden soll,
– dann, wenn jeweils zwei gemäß der protokollierten zeitlichen Reihenfolge nacheinander ausgewählte Dokumente ein hohes Maß für die Ähnlichkeit haben, das zeitlich frühere Dokument als relevant bewertet wird,
– Dokumentteile der ausgewählten Dokumente identifiziert werden,
– Bewertungen der identifizierten Dokumentteile berechnet werden,
– wobei die Bewertung mindestens eines Dokumentteils als Funktion eines Maßes...

Description

• Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur automatischen Erzeugung eines Extrakts für mindestens ein Dokument. Dieses Dokument ist Bestandteil einer Kollektion elektronischer Dokumente, die für ein Informationsbeschaffungssystem verfügbar sind.
• „Dokument" ist im folgenden ein Oberbegriff für Texte, Graphiken mit Texten, Tabellen, Datensammlungen und ähnliches. Die Dokumente sind textlich in elektronischer Form gegeben. Ein Dokument der Kollektion ist beispielsweise von einem Textverarbeitungssystem oder einem Datenbanksystem oder durch Erfassen aller Bildpunkte eines papiergebundenen Dokuments erzeugt. Ein Dokument der Kollektion kann auch als Satz von HTML- oder XML-Seiten im Internet oder einem Intranet vorliegen. Der Begriff „Extrakt" wird im folgenden als Oberbegriff für eine Liste von Schlagworten oder für eine Zusammenfassung verwendet, die das Dokument oder die Dokumente beschreiben.
• Ein Extrakt beschreibt das Dokument und hilft beispielsweise einem Benutzer zu entscheiden, ob das Dokument für ihn relevant ist oder nicht, wenn der Benutzer in einem Unternehmens-Intranet mit einer Dokumenten-Kollektion nach Informationen sucht und nicht die Zeit hat, jedes Dokument selber zu lesen. Ein Extrakt unterstützt z. B. eine Volltextsuche im Internet mit bekannten Suchmaschinen, die oft sehr viele Dokumente liefern. Ein Grund hierfür ist, daß der gleiche Begriff in verschiedenen Bedeutungen sowohl in relevanten als auch in nicht relevanten Dokumenten auftritt. Andererseits liefert eine einzige Suche mit einer bekannten Suchmaschine oft deshalb unbefriedigende Ergebnisse, weil für denselben Sachverhalt in verschiedenen Dokumenten unterschiedliche Begriffe verwendet werden, z. B. konjugierte Wortformen, Synonyme und Abkürzungen. Deshalb muß der Benutzer mehrere Suchen durchführen lassen.
• In DE 195 26 264 A1 wird ein Verfahren zur Erzeugung von Schlüsselworten für die Klassifikation von Dokumenten offenbart. Die Schlüsselworte werden in DE 195 26 264 A1 Deskriptoren genannt, die Dokumente Texte. Die Wortformen der Worte des Dokuments werden in kürzere Wortformen und gegebenenfalls Wortteile zerlegt, und die Schlüsselworte werden aus den nach der Zerlegung verbliebenen Wortformen und Wortteilen gebildet.
• In K. Zechner: „A Literature Survey on Information Extraction and Text Summarization" werden u. a. verschiedene Verfahren offenbart, um eine Zusammenfassung für ein einzelnes elektronisch verfügbares Dokument zu erzeugen. Aus J. G. Carbonell, J. Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceed. SIGIR '98, 1998, Melbourne, Australia, ist ein Verfahren bekannt, bei dem Dokumentteile, insbesondere Sätze, bewertet werden und die Zusammenfassung aus hoch bewerteten Sätzen zusammengesetzt wird. Hierfür werden Terme, insbesondere Worte oder Wortteile, mit statistischen Verfahren bewertet. Andere Verfahren, z. B. das in K. R. McKeown, J. Robin, K. Kukich: „Designing and evaluating a new revision-based model for summary generation", Information Processing and Management Vol. 31 No. 5, 1995, vorgestellte Verfahren, kombinieren Informations-Extraktion und Methoden zur Erzeugung von natürlichsprachigen Texten, um eine Zusammenfassung zu erzeugen.
• Alle diese Verfahren berücksichtigen nur jeweils ein einziges Dokument, nämlich nur das Dokument, für das der Extrakt erzeugt werden soll. Daher können sie den Kontext des Dokuments nicht mit einbeziehen. Oft kann aber nur aus dem Kontext entschieden werden, welche Informationen wirklich im Extrakt enthalten sein müssen. Beispielsweise haben manche Worte unterschiedliche Bedeutungen in verschiedenen Kontexten, z. B. „Bank" oder „Programm". Wenn bei der Erzeugung eines Extrakts dieser Kontext nicht berücksichtigt wird, muß ein Benutzer des Informationsbeschaffungssystems aus dem Extrakt die ihn interessierenden Informationen herausfiltern.
• Aus M.-R. Amini: „Interactive Learning for Text Summarization", Proceed. PKDD 2000, Workshop on Machine Learning and Textual Information Access, pp. 10–18, ist ein lernendes Verfahren bekannt, das Zusammenfassungen erzeugt und die Ergebnisse durch Benutzerabfragen verbessert. Im ersten Schritt des Verfahrens werden diejenigen Sätze eines Textes identifiziert, die die höchsten Bewertungen bezüglich der Benutzeranfrage erhalten. Die Bewertung von Sätzen wird automatisch mit einem tf/idf-Term-Gewichtungs-Verfahren durchgeführt. Dem Benutzer werden von jedem Dokument die r am höchsten bewerteten Sätze des Dokuments absteigend nach Bewertung sortiert angezeigt. Diese r Sätze bilden die Zusammenfassung des Dokuments. Im zweiten Schritt gibt der Benutzer eine Rückmeldung an das System, indem er die automatische Auswahl und Bewertung von Sätzen überprüft und bei Bedarf abändert. Die Rückmeldung des Benutzers wird verwendet, um die automatisch durchgeführte Bewertung zu verbessern.
• Befriedigende Ergebnisse vermag dieses Verfahren höchstens bei zureichend vielen und guten Bewertungen des Benutzers zu treffen. Die Rückmeldung ist für den Benutzer mit erheblichem Aufwand verbunden. Die Notwendigkeit der Rückmeldungen kann zu fehlerhaften Ergebnissen führen.
• Aus J. Goldstein, V. Mittal, J. Carbonell, J. Callan:
  „Creating and Evaluating Multi-Document Sentence Extract Summaries", Proceed. ACM Conf. Information and Knowledge Management (CIKM 2000), McLean (VA), 6.-11. 11. 2000, pp. 165–172, ist ein Verfahren bekannt, um eine Zusammenfassung aus Sätzen mehrerer Dokumente einer vorgegebenen Dokument-Kollektion zu erzeugen. Beispielsweise führt der Benutzer eine Suche im Internet durch, indem er mit Hilfe einer Suchmaschine eine Anfrage mit Suchbegriffen abschickt, um Fundstellen im Internet finden zu lassen. Die Dokument-Kollektion ist in diesem Beispiel das von der Suchmaschine gelieferte Ergebnis der Benutzer-Anfrage an das Internet.
• Gemäß dem in J. Goldstein et al. offenbarten Verfahren werden die Dokumente der Kollektion in Dokumentteile zerlegt. Die Dokumentteile können Sätze oder Satzteile sein. Zunächst werden diejenigen Dokumentteile identifiziert, die relevant bezüglich der Dokumenten-Kollektion und der Suchanfrage des Benutzers sind. Aus diesen relevanten Dokumentteilen werden einige wie folgt ausgewählt: Schrittweise wird für jedes relevante, aber noch nicht ausgewählte Dokumentteil eine Bewertung gemäß dem Verfahren „maximal marginal relevance-multi-document" (MMR-MD) durchgeführt. Das dabei am höchsten bewertete Dokumentteil wird zusätzlich ausgewählt. Ein solcher Auswahlschritt wird so oft wiederholt, bis ein Abbruchkriterium erfüllt ist, beispielsweise bis eine vorgegebene Anzahl relevanter Dokumentteile ausgewählt wurde. Die Zusammenfassung wird erzeugt, indem die ausgewählten Dokumentteile sortiert und zusammengesetzt werden.
• Ein Dokumentteil p wird hierbei gemäß der Rechenvorschrift Bewertung(p) = λ·sim_1(p) – (1 – λ)·sim2(p)bewertet, wobei
  sim_2(p) = max{sim_2(p, p_sel)|p_sel bereits ausgewählt} ist.
• Sim_1(p) ist um so höher, je ähnlicher das Dokumentteil p der Anfrage ist, je höher der Informationsgehalt von p ist und je neuer das Dokument ist, in dem p enthalten ist. Sim_2 ist um so höher, je ähnlicher p einem schon ausgewählten Dokumentteil ist. Dadurch, daß sim_2 subtrahiert wird, wird vermieden, daß mehrere ähnliche und damit redundante Dokumentteile in der Zusammenfassung auftreten.
• Das in J. Goldstein et al. offenbarte Verfahren ist insbesondere dann rechenaufwendig und damit zeitraubend, wenn die Kollektion umfangreich ist, beispielsweise wenn die Suchanfrage mehrere hundert Dokumente lieferte. Nicht automatisch berücksichtigt werden kann, welche dieser vielen Dokumente der Benutzer als relevant eingestuft hat und welche nicht.
• Auch in J. G. Carbonell & J. Goldstein: „The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries", Proceed. 21^St Annual Internat. ACM SIGIR Conf. Research and Development in Information Retrieval, Aug. 24^th–28^th, 1988, Melbourne, Australia, pp. 1–2, wird ein Verfahren offenbart, um ein Extrakt für ein Dokument, das zu einer Dokumenten-Kollektion gehört, zu erzeugen. Nacheinander wird aus der Dokumenten-Kollektion jeweils ein Dokument ermittelt, das einerseits möglichst ähnlich zu der Anfrage eines suchenden Benutzers ist, andererseits möglichst unähnlich zu den bereits zuvor ermittelten Dokumenten der Kollektion. Dies wird wiederholt, bis ein Abbruchkriterium erfüllt ist, und die ermittelten Dokumente werden dem Benutzer als Ergebnis seiner Suchanfrage präsentiert. Ein entsprechendes Ähnlichkeitsmaß wird offenbart. Um eine Zusammenfassung eines Dokuments zu erzeugen, werden die zur Benutzer-Anfrage passenden Dokumente in Dokumentteile zerlegt und die Dokumentteile entsprechend des Ähnlichkeitsmaßes bewertet.
• Wie die Bewertungen eines Benutzers in die Erzeugung des Extrakts einfließen, wird nicht beschrieben.
• Der Erfindung liegt die Aufgabe zugrunde, ausgehend von J. Goldstein, V. Mittal et al. ein Verfahren der eingangs genannten Art zu schaffen, das bei der Erzeugung des Extrakts Dokumentteile bewertet und bei der Dokumentteil-Bewertung automatisch berücksichtigt, welche Dokumente der Kollektion der Benutzer als relevant eingestuft hat, ohne hierfür von ihm zusätzlichen Rückmeldungen oder sonstige Angaben zu verlangen.
• Die Aufgabe wird durch ein Verfahren nach dem Anspruch 1, eine Vorrichtung nach dem Anspruch 11 und einem Computerprogramm nach Anspruch 13 oder Anspruch 14 gelöst.
• Die Erfindung offenbart ein Verfahren zur automatischen Erzeugung eines Extrakts für ein Dokument. Das Dokument ist Bestandteil einer für ein Informationsbeschaffungssystem elektronisch verfügbaren Kollektion von Dokumenten. Ein Benutzer interagiert mit dem Informationsbeschaffungssystem. Bei dieser Interaktion bietet das Informationsbeschaffungssystem dem Benutzer bestimmte Dokumente aus der Kollektion an. Der Benutzer wählt unter den angebotenen Dokumenten bestimmte aus, um sie sich anzeigen zu lassen.
• Das Informationsbeschaffungssystem protokolliert eine zeitliche Reihenfolge. Diese protokollierte zeitliche Reihenfolge ist die Reihenfolge, in der der Benutzer Dokumente der Kollektion ausgewählt hat.
• Der Benutzer gibt das Dokument vor, für das das Extrakt erzeugt werden soll. Automatisch wird ermittelt, welche der Dokumente für den Benutzer relevant sind. Hierbei wird dann, wenn jeweils zwei gemäß der protokollierten zeitlichen Reihenfolge nacheinander ausgewählte Dokumente ein hohes Maß für die Ähnlichkeit haben, das zeitlich frühere Dokument als relevant bewertet wird.
• Dokumentteile der ausgewählten Dokumente werden identifiziert. Bewertungen der identifizierten Dokumentteile werden berechnet. Hierbei wird die Bewertung mindestens eines Dokumentteils als Funktion zweier Ähnlichkeitsmaße berechnet, nämlich
• – eines Maßes für die Ähnlichkeiten des Dokumentteils zu den relevanten unter den ausgewählten Dokumenten und
• – eines Maßes für die Ähnlichkeiten des Dokumentteils zu den nicht relevanten unter den ausgewählten Dokumenten.
• In die Funktion gehen die Ähnlichkeiten zu den relevanten und die Ähnlichkeiten zu den nicht relevanten Dokumenten in verschiedener Weise ein.
• Dokumentteile werden in Abhängigkeit von ihren Bewertungen ausgewählt. Der Extrakt wird aus ausgewählten Dokumentteilen zusammengesetzt.
• Das Verfahren sieht vor, Eingaben des Benutzers in das Informationsbeschaffungssystem zu protokollieren, die er bei der Suche nach Informationen ohnehin vornimmt, nämlich die Auswahl bestimmter Dokumente.
• Verfahren nach dem Stand der Technik erfragen vom Benutzer eine Rückmeldung z. B. in Form einer Bewertung der Suchergebnisse. Diese Befragung ist zeitaufwendig, wird von Benutzern oft als lästig und überflüssig empfunden und ist fehlerträchtig, weil Benutzer manchmal nicht zu benennen vermögen, was sie wirklich interessiert, insbesondere wenn sie im nachhinein befragt werden. Das erfindungsgemäße Verfahren spart diese Befragung ein, indem Eingaben des Benutzers in das Informationsbeschaffungssystem, die er ohnehin vornimmt, protokolliert und für die Ermittlung weiterer Dokumente ausgewertet werden. Zusätzliche Benutzereingaben erfordert das erfindungsgemäße Verfahren nicht. Der Benutzer braucht insbesondere nicht gefragt zu werden, welche Dokumente er als wie relevant bewertet und welche für ihn irrelevant sind. Diese Informationen werden vielmehr automatisch aus den Benutzereingaben gewonnen.
• Durch das erfindungsgemäße Verfahren wird automatisch ein Extrakt erzeugt, der an den jeweiligen Benutzer und seine Interessen angepaßt ist. Dies wird erreicht, weil protokollierte Eingaben des jeweiligen Benutzers berücksichtigt werden. Das Verfahren kann also bei demselben Dokument und verschiedenen Benutzern unterschiedliche Ergebnisse liefern. Insbesondere werden dadurch automatisch unterschiedliche Bedeutungen von Worten unterschieden. Falls ein Benutzer sich beispielsweise für Dokumente über Finanzdienstleister interessiert, stellt das Verfahren sicher, daß Dokumente als relevant eingestuft werden, in dem das Wort „Bank" in der Bedeutung als Finanzdienstleister auftritt, aber keine Dokumente mit einer Bank in der Bedeutung als Sitzgelegenheit.
• Möglich ist sogar, daß im erfindungsgemäß erzeugten Extrakt für das Dokument ein Schlüsselwort oder ein Satz oder Abschnitt auftritt, das bzw. der im Dokument selber gar nicht vorkommt.
• Die Verwendung der Benutzer-Eingaben hat den weiteren Vorteil, daß bevorzugt ausschließlich Informationen verwendet werden, die auf einem Netzwerk-Teilnehmerrechner (Client) verfügbar sind. Damit läßt sich das Verfahren unabhängig von einem bestimmten Internet-Diensteprogramm (Web Server) oder einem bestimmten Netzwerk-Zentralrechner (Server) realisieren. Die Benutzereingaben lassen sich darüber hinaus einem bestimmten Benutzer zuordnen, so daß dieser das erfindungsgemäße Verfahren von verschiedenen Netzwerk-Teilnehmerrechnern aus ausführen lassen kann. Das Internet-Diensteprogramm oder der Netzwerk-Zentralrechner können sogar ausgetauscht werden, ohne daß erneute Eingaben des Benutzers benötigt werden.
• Das erfindungsgemäße Verfahren berücksichtigt mehrere Dokumente, ist aber trotzdem wesentlich weniger rechenaufwendig als Verfahren nach dem Stand der Technik. Dieser Vorteil wird insbesondere dadurch erreicht, daß zuerst weitere Dokumente der Kollektion unter Verwendung der protokollierten Benutzereingaben ermittelt werden und nur die ausgewählten weiteren Dokumente anstelle aller Dokumente der Kollektion eingehend und mit erhöhtem Rechenaufwand untersucht werden. Oft umfaßt die Kollektion mehrere hundert Dokumente, als weitere Dokumente werden aber z. B. nur zehn oder zwanzig Dokumente ausgewählt.
• Der Extrakt kann sich auf ein einziges Dokument beziehen. Dieses Dokument ist beispielsweise von einem Benutzer vorgegeben. Ein Benutzer kann auch mehrere Dokumente vorgeben, und der erzeugte Extrakt bezieht sich auf alle diese vorgegebenen Dokumente.
• Möglich ist aber auch, daß ein einziger Extrakt für das Dokument und die ausgewählten weiteren Dokumente erzeugt wird (Anspruch 3). Eine Fortbildung sieht vor, daß das Dokument, für das der Extrakt erzeugt wird, nicht vorgegeben ist, sondern eines der ausgewählten weiteren Dokumente ist.
• Der Extrakt umfaßt beispielsweise eine Liste von Schlüsselworten (Anspruch 7), und mehrere oder alle der identifizierten und bewerteten Dokumentteile sind Worte, z. B. Worte der deutschen oder englischen Sprache oder kennzeichnende Abkürzungen. Als Schlüsselworte werden z. B. diejenigen Worte ausgewählt, deren Bewertung eine vorgegebene Schranke überstiegt, oder die s am höchsten bewerteten Worte, wobei s eine vorgegebene Anzahl ist. Eine Liste von Schlüsselworten ist kürzer und damit schneller zu erfassen als andere Formen eines Extrakts. Um das Dokument z. B. in einen elektronischen Katalog einzusortieren, werden Schlagworte benötigt.
• Gemäß Anspruch 8 umfaßt der Extrakt eine Zusammenfassung, und zu den identifizierten und bewerteten Dokumentteilen gehören vollständige Sätze oder Abschnitte. Die Zusammenfassung wird beispielsweise aus den s am höchsten bewerteten Sätzen zusammengesetzt, wobei s eine vorgegebene Anzahl ist und die Reihenfolge der Sätze in der Zusammenfassung gleich der Reihenfolge in den Dokumenten der Kollektion ist. Eine derartige Zusammenfassung ist oft besser verständlich als eine bloße Auflistung von Schlüsselworten. Eine Fortbildung sieht vor, daß alle identifizierten und bewerteten Dokumentteile Abschnitte sind und die Zusammenfassung aus einem einzigen Abschnitt besteht.
• Um zu protokollieren, welche Dokumente der Benutzer bislang ausgewählt hat, wird vorzugsweise der Benutzer-Klickpfad bestimmt. Der Benutzer-Klickpfad besteht aus Verweisen auf die bislang vom Benutzer ausgewählten Dokumente der Kollektion, vorzugsweise in chronologischer Reihenfolge sortiert, oder aus geeigneten Repräsentationen dieser Dokumente.
• Vorzugsweise wird für die Erzeugung des Extrakts eine Suchanfrage von einem Netzwerk-Teilnehmerrechner an einen Netzwerk-Zentralrechner übermittelt. Die Suchanfrage umfaßt geeignete Repräsentationen der ausgewählten weiteren Dokumente oder Verweise auf die ausgewählten weiteren Dokumente (Anspruch 4). Beispielsweise in Datenspeichern des Netzwerk-Zentralrechners sind die Dokumente der Kollektion abgespeichert. Durch diese Ausgestaltung lassen sich bekannte Informationsbeschaffungssysteme wiederverwenden. Im Unterschied zu bekannten Informationsbeschaffungssystemen besteht die Suchanfrage aber nicht aus vom Benutzer eingegebenen Suchbegriffen, sondern aus einer automatisch erzeugten Suchanfrage. Die Suchanfrage läßt sich aus Informationen erzeugen, die auf dem Netzwerk-Teilnehmerrechner abgespeichert sind, so daß eine vorhergehende Informationsabfrage vom Netzwerk-Teilnehmerrechner an den Netzwerk-Zentralrechner nicht erforderlich ist. Diese Ausgestaltung erspart dem Benutzer Arbeitszeit und Wartezeit vor seinem Netzwerk-Teilnehmerrechner.
• Das erfindungsgemäße Verfahren sieht vor, daß das identifizierte Dokumentteil in Abhängigkeit von einem Maß für die Ähnlichkeit zwischen dem Dokumentteil und den ausgewählten weiteren Dokumenten automatisch bewertet wird.
• Die Ausgestaltung nach Anspruch 5 sieht eine zusätzliche Einflußgröße auf die Bewertung des identifizierten Dokumentteils vor. Für die Berechnung der Dokumentteil-Bewertung werden zusätzlich Gewichtungen von denjenigen ausgewählten weiteren Dokumenten, in denen das Dokumentteil auftritt, berechnet und verwendet. Damit läßt sich automatisch eine Differenzierung unter den ausgewählten weiteren Dokumenten vornehmen, was die Aussagekraft des erzeugten Extrakts weiter erhöht.
• Die Fortbildung dieser Ausgestaltung nach Anspruch 6 sieht vor, nicht nur zwischen ähnlichen und nicht ähnlichen Dokumenten zu unterscheiden, sondern zusätzlich ein Maß für die Ähnlichkeit zwischen dem Dokument und den ausgewählten weiteren Dokument zu berechnen. Dieses Maß wird für die Berechnung der Gewichtung eines ausgewählten weiteren Dokuments verwendet. Beispielsweise ist das Maß für die Ähnlichkeit eine Zahl zwischen 0 und 1, die direkt als Gewichtung verwendet wird.
• Gemäß Anspruch 9 wird ein Extrakt erzeugt, das eine Zusammenfassung umfaßt. Hierfür werden Dokumentteile identifiziert, indem Dokumente der Kollektion in Sätze oder Abschnitte zerlegt werden. Eine Liste von Schlüsselworten wird erzeugt, beispielsweise durch ein Verfahren nach Anspruch 7. Die erzeugte Zusammenfassung umfaßt diejenigen identifizierten Dokumentteile, die mindestens ein Schlüsselwort enthalten. Die dergestalt erzeugte Zusammenfassung umfaßt weniger Sätze oder Absätze als eine auf andere Weise erzeugte Zusammenfassung, und die Sätze präsentieren Schlüsselworte in ihrem Kontext anstelle isoliert.
• Bei der Ausgestaltung nach Anspruch 10 wird eine Zusammenfassung erzeugt, die aus Sätzen und/oder Abschnitten besteht. Das mindestens eine bewertete Dokumentteil ist ein Satz oder Abschnitt. Für die Berechnung von dessen Bewertung wird eine Bewertung mindestens eines Wortes, das im Satz bzw. Abschnitt enthalten ist, verwendet. Die Bewertung dieses Worts hängt von einem Maß für die Ähnlichkeit zwischen dem Wort und den ausgewählten weiteren Dokumenten ab.
• Anspruch 11 sieht eine Vorrichtung zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 10 vor. Diese Vorrichtung umfaßt
• – Mittel zum Auswählen von weiteren Dokumenten der Kollektion,
• – Mittel zum Protokollieren von Benutzereingaben in das Informationsbeschaffungssystem,
• – Mittel zur Bewertung von Dokumentteilen in Abhängigkeit von den protokollierten Benutzereingaben,
• – Mittel zum Auswählen von Dokumentteilen in Abhängigkeit von ihren Bewertungen
• – und Mittel zum Zusammensetzen des Extrakts aus ausgewählten Dokumentteilen.
• Vorzugsweise ist die Vorrichtung Bestandteil einer Datenverarbeitungsanlage, die mindestens zeitweise als Netzwerk-Teilnehmerrechner mit mindestens einem Netzwerk-Zentralrechner verbunden ist (Anspruch 12). Dieser Netzwerk-Zentralrechner umfaßt Datenspeicher, in denen Dokumente der Kollektion abgespeichert sind. Der Netzwerk-Teilnehmerrechner ist bevorzugt über das Internet oder einem Inteanet mit dem Netzwerk-Zentralrechner oder den Netzwerk-Zentralrechnern verbunden.
• Anspruch 13 sieht ein Computerprogramm vor. Dieses Computerprogramm wird in einem Computer abgearbeitet und führt dabei ein Verfahren nach einem der Ansprüche 1 bis 10 aus.
• Das Computerprogramm-Produkt nach Anspruch 14 ist auf einem von einem Computer lesbaren Medium gespeichert. Es umfaßt von einem Computer lesbare Programm-Mittel, die den Computer veranlassen, ein Verfahren nach einem der Ansprüche 1 bis 10 auszuführen.
• In der bevorzugten Ausführungsform läuft das erfindungsgemäße Verfahren auf einer Datenverarbeitungsanlage, z. B. einem PC, ab, der als Netzwerk-Teilnehmerrechner mit einem Netzwerk-Zentralrechner oder einer Menge von Netzwerk-Zentralrechnern verbunden ist. In Datenspeichern dieser Netzwerk-Zentralrechner sind Dokumente der Kollektion enthalten, so daß der Netzwerk-Teilnehmerrechner auf alle Dokumente zugreifen kann. Um den Netzwerk-Teilnehmerrechner mit dem Netzwerk-Zentralrechner oder den Netzwerk-Zentralrechnern zu verbunden, wird bevorzugt die Internet-Technologie mit mindestens einem Internet-Diensteprogramm, der auf den Netzwerk-Zentralrechnern abläuft, verwendet. Die Netzwerk-Zentralrechner gehören beispielsweise zum Internet oder zu einem Unternehmens-Intranet, sie können mit mehreren Netzwerk-Teilnehmerrechnern kommunizieren. Vorzugsweise werden für die Erzeugung des Extrakts ausschließlich Informationen verwendet, die auf dem Netzwerk-Teilnehmerrechner verfügbar sind. Damit arbeitet das Verfahren unabhängig von einem bestimmten Netzwerk-Zentralrechner.
• Das Informationsbeschaffungssystem, in dem das erfindungsgemäße Verfahren abläuft, läuft auf dem oder den Netzwerk-Teilnehmerrechnern sowie dem oder den Netzwerk-Zentralrechnern ab. Ein Netzwerk-Teilnehmerrechner sendet Aufträge, z. B. Anfragen, an einen Netzwerk-Zentralrechner, und der beauftragte Netzwerk-Zentralrechner sendet Antworten, z. B. ein bestimmtes Dokument der Kollektion, an den Netzwerk-Teilnehmerrechner.
• Ein Benutzer interagiert mit dem Informationsbeschaffungssystem. Dabei bietet das Informationsbeschaffungssystem bestimmte Dokumente aus der Kollektion dem Benutzer an, und der Benutzer wählt unter den ausgebotenen Dokumenten bestimmte aus, um sie sich anzeigen zu lassen. Protokolliert werden dabei wesentliche Eingaben des Benutzers, z. B. welche Dokumente er in welcher Reihenfolge ausgewählt hat. Auf Wunsch des Benutzers wird ein Extrakt von Dokumenten der Kollektion erzeugt. Vorzugsweise gibt er ein Dokument vor, für das ein Extrakt unter Berücksichtigung des bisherigen Benutzerverhaltens erzeugt wird. Dieses vorgegebene Dokument wird im folgenden als erstes Dokument D_0 bezeichnet. Möglich ist aber auch, daß der Benutzer mehrere Dokumente vorgibt oder daß überhaupt kein Dokument vorgegeben ist, sondern sich der Extrakt auf ermittelte weitere Dokumente bezieht.
• Die Dokumente der Kollektion werden vorzugsweise unter Verwendung eines Vektorraum-Modells repräsentiert. Vektorraum-Modelle sind aus C. D. Manning, H. Schütze:
  „Foundations of Statistical Natural Language Processing", MIT Press, Boston 1990, bekannt. Eine Indexierungssprache, das ist eine Menge von M Zeichenfolgen, wird vorgegeben. Die Zeichenfolgen der Indexierungssprache werden im folgenden Indexierungsterme genannt.
• Die Indexierungssprache läßt sich aus folgenden Arten von Zeichenfolgen aufbauen:
• – Worte, vorzugsweise Worte in der Dokumenten-Kollektion. Da verschiedene Flexionsformen als unterschiedliche Zeichenfolgen behandelt werden, wird die Indexierungssprache groß, und die Übereinstimmung zwischen verschiedenen Flexionsformen eines Worts wird nicht oder nur mit zusätzlichem Rechenaufwand erkannt.
• – Wortstämme, die mittels linguistischer Regeln aus den Worten abgeleitet werden. Für jede Sprache, u. U. sogar für jeden Dialekt einer Sprache, sind erneut linguistische Regeln aufzustellen.
• – Zeichenfolgen der Länge n, sogenannte n-Gramme. In der Praxis werden Quadgramme, das sind Zeichenfolgen der Länge n = 4, und Trigramme, das sind Zeichenfolgen der Länge n = 3, verwendet. Diese Ausgestaltung hängt nicht von der Sprache ab und ist robust gegenüber Flexionsformen und Tippfehlern. Jedoch haben viele n-Gramme keine anschauliche Bedeutung für den Benutzer.
• – Phrasen, also feste Abfolgen von Worten. Die Menge von Phrasen muß bei dieser Ausgestaltung für jede Anwendung, z. B. jedes Themengebiet oder gar jede Kollektion, neu definiert werden.
• Bevorzugt werden Worte, Quadgramme oder Trigramme als Zeichenfolgen der Indexierungssprache verwendet.
• Jedes Dokument wird gemäß dem Vektorraum-Modell durch einen Vektor der Länge M repräsentiert, wobei M die Anzahl der Indexierungsterme ist. Das j-te Element des Vektors V_i für das Dokument D_i gibt eine Gewichtung für die Bedeutung des Indexierungsterms j im Dokument D_i an. Beispielsweise ist die Gewichtung entweder 0 oder 1. Um Speicherplatz zu sparen, werden von einem Vektor für ein Dokument nur die Indizes und Einträge derjenigen Vektorelemente abgespeichert, die ungleich 0 sind.
• Als Gewichtungen werden bevorzugt nicht nur die Werte 0 und 1 verwendet, sondern Gewichtungen, die nach dem tf/idf-Verfahren bestimmt wurden. Die Gewichtung G(t, i) einer Zeichenfolge t bezüglich des Dokuments D_i wird beim tf/idf-Verfahren gemäß der Formel G(t, i) = tf(t, i)·idf(t)bestimmt. Hierbei gibt die Zeichenfolgen-Häufigkeit tf(t, i) an, wie oft die Zeichenfolge t im Dokument D_i vorkommt. Die inverse Dokument-Häufigkeit idf(t) ist um so größer, je seltener der Term t in der Dokumenten-Kollektion auftritt. Sie ist gleich N/df(t), wobei N die Anzahl der Dokumente in der Kollektion und die Dokument-Häufigkeit df(t) die Anzahl der Dokumente, in denen die Zeichenfolge t auftritt, ist.
• Falls eine Zeichenfolge t in keinem Dokument der Kollektion auftritt, wird G(t, i) = 0 gesetzt.
• Worte, die häufig in einem Dokument auftreten und nichts über den Inhalt des Dokuments aussagen, werden Funktionsworte genannt. Zu den Funktionsworten zählen Pronomen, Artikel und Hilfsverben. Für Funktionsworte werden bevorzugt keine Gewichtungen bestimmt, und sie werden bei der Identifizierung und Bewertung von Dokumentteilen, insbesondere bei der Suche nach Schlüsselworten, außer Acht gelassen. Die automatisch ermittelten und nicht berücksichtigten Funktionsworte werden in einer sogenannten Stopwortliste zusammengefaßt.
• Aus C. J. van Rijsbergen: „Information Retrieval", Butterworth Press, London 1979, ist ein Verfahren zur automatischen Ermittlung der Stopwortliste bekannt. Dieses Verfahren wird bevorzugt auf die Kollektion von Dokumenten übertragen. Funktionsworte sind im Dokument annähernd Poisson-verteilt. Der Parameter λ = λ(w, i) = tf (w, i)/N der Poisson-Verteilung ist gleich der relativen Häufigkeit des Funktionswortes w in der Kollektion von Dokumenten wobei N die Anzahl der Dokumente in der Kollektion ist. Um zu entscheiden, ob ein Wort w ein Funktionswort ist, wird das Vorliegen einer Poisson-Verteilung geprüft.
• Erfindungsgemäß werden neben dem ersten Dokument D_0 weitere Dokumente der Kollektion ermittelt und ausgewertet, um einen Extrakt zu erzeugen. Eine Ausgestaltung der Erfindung sieht vor, hierbei nach Dokumenten der Kollektion zu suchen, die ähnlich zum ersten Dokument D_0 sind. Aus U. Bohnacker, L. Dehning, J. Franke, I. Renz, R. Schneider: „Weaving Intranet Relations – Managing Web Content", Proceed. RIAO 2000: Content-Based Multimedia Information Access, Paris, 12.–14. 4. 2000, pp. 1744–1751, ist ein Verfahren bekannt, um in einer vorgegebenen Kollektion Dokumente, die zu einem vorgegebenen Dokument ähnlich sind, zu ermitteln. Einmal vorab wird für jedes Paar von Dokumenten (D_1, D_2) der Kollektion die Ähnlichkeit zwischen D_1 und D_2 bewertet. Falls ein Benutzer ein Dokument D_l auswählt und nach zu D_1 ähnlichen Dokumenten der Kollektion suchen läßt, werden die als ähnlich bewerteten Dokumente der Kollektion ermittelt und ihm angezeigt. Die Benutzeranfrage wird besonders schnell beantwortet. Bevorzugt wird das aus U. Bohnacker et al. bekannte Verfahren angewendet, um automatisch nach zu D_0 ähnlichen Dokumenten zu suchen.
• Für jeden Indexierungsterm, also für jede Zeichenfolge der Indexierungssprache, wird wie oben beschriebene eine Gewichtung des Indexierungsterms bezüglich jedes ähnlichen Dokuments der Kollektion bestimmt und ausgewertet, vorzugsweise nach dem tf/idf-Verfahren. Die einzelnen Gewichtungen des Indexierungsterms werden zu einer Bewertung des Indexierungsterms bezüglich der Kollektion zusammengefaßt. Sei G(t, i) die Gewichtung des Indexierungsterms t bezüglich des Dokuments D_i. Sei B(t, Koll) die erfindungsgemäß bestimmte Bewertung des Indexierungsterms t bezüglich der Kollektion. Seien D_1,...
• D_k die zum ersten Dokument D_0 ähnlichen Dokumente der Kollektion. Die Bewertung B(t, Koll) wird entweder durch die Vorschrift B (t, Koll) = G (t, 0) + G (t, 1) + ... + G (t, k)oder durch die Vorschrift
  B (t, Koll) G (t, 0)·sim(0, 0) + G (t, 1)·sim(0, 1) + ... + G (t, k)·sim(0, k)bestimmt. Hierbei ist sim(0, i) ein Maß für die Ähnlichkeit zwischen den Dokumenten D_0 und D_i (i = 0, 1, ..., k). In beiden Fällen werden also nur D_0 und zu D_0 ähnliche Dokumente für die Erzeugung des Extrakts herangezogen.
• Die Bewertung B(t, Koll) wird wie oben beschrieben für jeden Indexierungsterm bestimmt. Also werden M Bewertungen bestimmt, wobei M die Anzahl der Indexierungsterme ist. Dadurch wird ein Cluster-Indexierungsterme-Vektor der Länge M gebildet. Indexierungsterme, die in mehreren Dokumenten enthalten sind, erhalten in der Regel eine höhere Bewertung als solche, die nur in einem Dokument enthalten sind.
• Bevorzugt wird mit Hilfe des Cluster-Indexierungsterme-Vektors ein Extrakt in Form einer Liste von Schlüsselworten erzeugt. Dies wird vorzugsweise auf eine der folgenden beiden Arten durchgeführt:
  Die erste Art: Der Cluster-Indexierungsterme-Vektor wird absteigend nach den Bewertungen B(t, Koll) der Indexierungsterme bezüglich der Kollektion sortiert. Als Schlüsselworte werden die am höchsten bewerteten Indexierungsterme verwendet. Dieses Verfahren läßt sich insbesondere dann anwenden, wenn als Indexierungsterme Worte verwendet werden. Oder es werden als Schlüsselworte die Worte von Dokumenten verwendet, die die am höchsten bewerteten Indexierungsterme enthalten.
• Die zweite Art: Für jedes Wort w des ersten Dokuments D_0 und werden die Bewertungen B(t, Koll) bezüglich der Kollektion aller Indexierungsterme, die im Wort w enthalten sind, addiert. Die Worte der Stopwortliste werden hierbei außer Acht gelassen. Sei w ein Wort in D_0, das nicht zur Stopwortliste gehört, und seien t_1, ..., t_l die Indexierungsterme, die im Wort w auftreten. Dann wird die Bewertung B(w, Koll) des Wortes w bezüglich der Kollektion gemäß der Vorschrift B(w, Koll) = B(t_1, Koll) + ... + B(t_l, Koll)bestimmt. Diejenigen r Worte des Dokuments D_0, die die höchsten Bewertungen B(w, Koll) erhalten, werden als Schlüsselworte bestimmt. Diese Ausgestaltung eignet sich besonders für Trigramme und Quadgramme als Indexierungsterme. In einer Fortbildung werden die Bewertungen B(w, Koll) nicht nur für die Worte des ersten Dokuments, sondern auch für die Worte der ähnlichen Dokumente erzeugt. Die Liste der Schlagworte, die wiederum durch Auswahl der am höchsten bewerteten Worte erzeugt wird, kann dann auch Worte enthalten, die nicht im ersten Dokument D_0, sondern in zu D_0 ähnlichen Dokumenten vorkommen.
• Eine weitere Ausgestaltung der Erfindung sieht vor, den sogenannten Benutzer-Klickpfad aufzuzeichnen und für die Erzeugung des Extrakts zu verwenden. Im Benutzer-Klickpfad sind diejenigen Dokumente der Kollektion aufgelistet, die bislang der Benutzer zur Anzeige ausgewählt hat, z. B. nachdem sie ihm vom Informationsbeschaffungssystem zur Auswahl angeboten wurden. Diese Auflistung umfaßt z. B. Verweise auf die Dokumente oder Repräsentationen von Dokumenten gemäß dem Vektorraum-Modell. Der Benutzer-Klickpfad repräsentiert damit das Profil des Benutzers bei dessen Suche nach Dokumenten. Der Benutzer-Klickpfad ist bevorzugt nach der zeitlichen Reihenfolge sortiert, in der der Benutzer Dokumente ausgewählt hat, das als letztes ausgewählte Dokument ist das letzte des Benutzer-Klickpfades. Beispielsweise werden die Internet- oder Intranet-Adresse eines Dokuments in Form einer eindeutigen Kennung, z. B. eines sogenannten „Uniform Resource Locator" (URL), ermittelt und lokal im Netzwerk-Teilnehmerrechner abgespeichert, wodurch der Benutzer-Klickpfad auf einem Netzwerk-Teilnehmerrechner zur Verfügung steht. Der Benutzer-Klickpfad wird z. B. in sogenannten „Cookies" eines Internet-Zugriffsprogramms abgespeichert. Der Benutzer-Klickpfad umfaßt eine Auflistung der Kennungen aller vom Benutzer ausgewählten Dokumente. Vorzugsweise wird der Benutzer-Klickpfad als Suchanfrage von einem Netzwerk-Teilnehmerrechner an einen Netzwerk-Zentralrechner gesandt. Durch diese Ausgestaltung werden keine Informationen benötigt, die im Netzwerk-Zentralrechner abgespeichert sind. Vielmehr reicht es, den Benutzer-Klickpfad auf dem Netzwerk-Teilnehmerrechner zu protokollieren und abzuspeichern.
• Beispielhaft wird im folgenden die Erzeugung einer Liste von Schlüsselworten als dem Extrakt beschrieben. Seien D_1, ..., D_k die Dokumente des Benutzer-Klickpfades. Eines dieser Dokumente kann in diesem Beispiel gleich dem ersten Dokument D_0 sein, z. B. das letzte Dokument des Benutzer-Klickpfades. Für die Indexierungsterme wird wie oben beschrieben eine Gewichtung G(t, i) des Indexierungsterms t bezüglich des Dokuments D_i bestimmt. Aus diesen Gewichtungen werden Schlüsselworte bevorzugt auf eine der beiden folgenden Weisen bestimmt:
  Ausgestaltung 1: Eine Bewertung B(t, BKP) des Indexierungsterms t bezüglich des Benutzer-Klickpfades BKP und des ersten Dokuments D 0 wird wie oben beschrieben bestimmt. In diese Bewertung fließen die k Gewichtungen G(t, D_1), ..., G(t, D_k) des Indexierungsterms t bezüglich der k Dokumente des Benutzer-Klickpfades ein, die gemäß dem Vektorraum-Modell erzeugt worden sind. Beispielsweise ist G(t, D_i) = tf(t, D_i)·idf (t), und G(t, BKP) wird gemäß der Vorschrift

  

  bestimmt.
• Wie oben beschrieben wird anschließend aus den Bewertungen B(t_1, BKP), ..., B(t_l, BKP) von den in einem Wort w enthaltenen Indexierungsterme t_1, ..., t_l eine Bewertung B(w, BKP) des Worts w erzeugt. Die l Bewertungen der Indexierungsterme t_1, ..., t_l, die in einem Wort w enthalten sind, werden zu einer Bewertung B(w, BKP) zusammengefaßt. Die Bewertung B(w, BKP) wird vorzugsweise gemäß der Vorschrift

  

  bestimmt. Eine weitere Ausführungsform ist

  
• In beiden Berechnungsvorschriften ist n die Anzahl von Zeichen im Wort w. Wort-Bewertungen werden für Worte des ersten Dokuments D_0 und der Dokumente des Benutzer-Klickpfades durchgeführt. Die am höchsten bewerteten Worte werden als Schlüsselworte verwendet.
• Ausgestaltung 2: In einem ersten Schritt werden mit Hilfe der Gewichtungen G(t, D_i) jeweils getrennt Schlüsselworte für die Dokumente D_1, ..., D_k des Benutzer-Klickpfades berechnet, also ohne daß der komplette Benutzer-Klickpfad für diese Ermittlung von Schlüsselworten eines Dokuments verwendet wird. Für die Ermittlung der Schlüsselworte werden oben beschriebene Verfahren analog verwendet, z. B. indem für ein Wort w im Dokument D_i die im Wort w enthaltenen Indexierungsterme t_1, ..., t_l ermittelt werden und ihre Gewichtungen G(t_1, D_i), ..., G(t_l, D_i) zu einer Bewertung B(w, D_i) zusammengefaßt werden. Beispielsweise wird B(w, D_i) gemäß der Vorschrift

  

  berechnet, wobei n die Anzahl von Zeichen im Wort w ist.
• Für jedes Dokument D_i (i = 1, ..., k) werden dadurch r_i Schlüsselworte bestimmt. Sei B(w, i) die Einzel-Bewertung eines Schlüsselwortes w bezüglich des Dokuments D_i (i = 1, ..., k). Aus den Einzel-Bewertungen der Schlüsselworte bezüglich der Dokumente werden Bewertungen der Schlüsselworte bezüglich der Kollektion bestimmt, indem die Einzel-Bewertungen addiert werden.
• Ein Beispiel für die Ausgestaltung 2: Falls das Wort w ein Schlüsselwort für die Dokumente D_1, D_2 und D_k ist (mit k > = 3), so ist die Gesamt-Bewertung B(w, BKP) = B(w, 1) + B(w, 2) + B(w, k). Ein weiteres Beispiel:
  Falls w nur für das Dokument D_3 und für kein anderes Dokument des Benutzer-Klickpfades Schlüsselwort ist, so ist die Gesamt-Bewertung B(w, BKP) = B(w, 3).
• Diese Ausgestaltungen führen in der Regel ohne weitere Vorkehrung dazu, daß Worte hoch bewertet werden, die Themen beschreiben, die für den Benutzer relevant sind oder ihn interessieren. Denn viele Dokumente des Benutzer-Klickpfades beziehen sich auf Themen, die den Benutzer interessieren und/oder für ihn relevant sind. Wenn der Benutzer auf ein ihn interessierendes Dokument stößt, wird er oft nach ähnlichen Dokumente suchen oder suchen lassen. Worte in diesem Dokument erhalten daher eine hohe Bewertung, einige werden zu Schlüsselworten. Stößt er hingegen auf ein für ihn uninteressantes Dokument, so wird er kein ähnliches Dokument anfordern, und die nur im uninteressanten Dokument auftretenden Worte erhalten eine niedrige Bewertung.
• Die gerade beschriebenen Ausgestaltungen lassen sich verwenden, um Schlüsselworte für ein einzelnes erstes Dokument D_0 unter Berücksichtigung des Kontextes zu bestimmen. Es ist auch möglich, einen Satz von Schlüsselworten für mehrere Dokumente zu erzeugen, beispielsweise für die Dokumente des Benutzer-Klickpfades. Die erzeugten Schlüsselworte beschreiben den wesentlichen Inhalt der vom Benutzer ausgewählten Dokumente.
• Eine Fortbildung der Erfindung sieht vor, die Bewertung eines Wortes so wie in den beiden vorigen Abschnitten beschrieben zu berechnen, aber zusätzlich Bewertungen der k Dokumente des Benutzer-Klickpfades zu bestimmen und bei der Berechnung der Wort-Bewertungen zu verwenden.
• Gemäß einer Ausgestaltung dieser Fortbildung wird ein Dokument um so höher bewertet, je später es in dem chronologisch sortierten Benutzer-Klickpfad auftritt. Das Dokument, das der Benutzer als erstes ausgewählt hat, erhält also die niedrigste Bewertung und das zuletzt ausgewählte die höchste.
• In einer weiteren Ausgestaltung werden bei der Berechnung der Dokument-Bewertungen Dokumente hinsichtlich ihrer Relevanz für den Benutzer unterschiedlich bewertet. Dabei wird automatisch die Relevanz ermittelt, während bisher nur Verfahren bekannt sind, um die Relevanz durch Befragung des Benutzers und Auswertung seiner Rückmeldungen zu ermitteln. Vorzugsweise wird eine der beiden folgenden Methoden angewendet, um die Relevanz eines Dokuments des Benutzer-Klickpfades automatisch zu ermitteln:
• • Notiert wird, für welche Dokumente der Benutzer eine Suche nach ähnlichen Dokumenten forderte. Aus U: Bohnacker et al. ist bekannt, wie ein Informationsbeschaffungssystem automatisch eine Suche nach ähnlichen Dokumenten durchführt. Diese Dokumente werden als relevant eingestuft.
• • Die Ähnlichkeit zwischen jeweils zwei Dokumenten der Kollektion wird wie oben beschrieben vorab ermittelt, z. B. durch das aus U. Bohnacker et al. bekannte Verfahren. Wenn im Benutzer-Klickpfad zwei nacheinander folgende Dokumente D_i und D_j ähnlich sind, also ein hohes Maß für die Ähnlichkeit haben, so wird das zeitlich frühere Dokument D_i als relevant bewertet.
• Wie automatisch Klassifikationen der ermittelten weiteren Dokumente in relevante und nicht relevante Dokumente verwendet werden, wird wieder am Beispiel eines Extrakts in Form einer Liste von Schlüsselworten beschrieben. Aufgrund ihrer Relevanz werden Bewertungen für die Dokumente des Benutzer-Klickpfades bestimmt und für die Berechnung von Wort-Bewertungen verwendet. Eine Ausgestaltung sieht vor, für ein Wort w des ersten Dokuments D_0 die l Indexierungsterme t_1, ..., t_l der Indexierungssprache zu ermitteln, die im Wort w enthalten sind. Für einen solchen Indexierungsterm t_j (j = 1, ..., l) werden wie oben beschrieben k Einzel-Bewertungen B(t_j, D_1), ..., B(t_j, D_k) des Indexierungsterms t_j bezüglich der k Dokumente D_1, ..., D_k des Benutzer-Klickpfades sowie eine Einzel-Bewertung B(t_j, D_0) bezüglich des ersten Dokuments D_0 bestimmt. Die Gesamt-Bewertung B(t_j, BKP) des Indexierungsterms t_j bezüglich des Benutzer-Klickpfades BKP und des ersten Dokuments wird gemäß der Formel

  

  bestimmt. Hierbei bezeichnen D[R] und D[N] die Menge der relevanten bzw. nicht relevanten Dokumente im Benutzer- Klickpfad und R bzw. N die Anzahl der Dokumente in D[R] bzw. D[N]. Aus den l Bewertungen B(t_j, D_l), ..., B(t_j, D_k) wird eine Bewertung B(w, BKP) des Worts w bestimmt. Hoch bewertete Worte werden wiederum als Schlüsselworte verwendet.
• Nachdem erfindungsgemäß Schlüsselworte für das erste Dokument D_0 ermittelt wurden, lassen sich diese Schlüsselworte verwenden, um eine Zusammenfassung für das erste Dokument zu erzeugen. Bevorzugt werden hierfür folgende Schritte durchgeführt:
• 1. Das erste Dokument D_0 wird in Sätze zerlegt.
• 2. Die Sätze des ersten Dokuments werden bewertet. Um die Bewertung eines Satzes s zu berechnen, werden die Bewertungen von im Satz s enthaltenen Worten verwendet.
• 3. Aus den hoch bewerteten Sätzen wird eine Zusammenfassung des ersten Dokuments erzeugt.
• Um den Schritt 1, nämlich die Zerlegung des ersten Dokuments in Sätzen, durchzuführen, werden bevorzugt die folgenden syntaktischen Regeln angewendet, die für viele Sprachen gelten:
• – Ein Satz endet mit einem Satztrennzeichen (!, ? und.).
• – Ein Satz beginnt am Textanfang oder nach einem Satzende-Zeichen.
• – Befindet sich vor einem Punkt eine Abkürzung, so markiert dieser Punkt nicht das Satzende.
• – Befindet sich ein Punkt unmittelbar nach einer Zahl zwischen 1 und 31, so markiert dieser Punkt ebenfalls kein Satzende.
• – Befindet sich ein Punkt direkt nach einer Ziffer und ist das nächste Zeichen, das kein Leerzeichen ist, ebenfalls eine Ziffer, dann markiert der Punkt ebenfalls kein Satzende.
• – Befinden sich mehrere Satztrennzeichen unmittelbar hintereinander, so wird nur das letzte Satztrennzeichen berücksichtigt.
• – Ein Satzende-Zeichen kennzeichnet dann das Ende eines Satzes, wenn darauf mindestens ein Leerzeichen gefolgt von einer Ziffer oder einem Großbuchstaben folgt.
• – Befindet sich ein Satzende-Zeichen am Ende des Textes, so kennzeichnet dieses auf jedem Fall das Ende eines Satzes.
• – Ein Satz muß mindestens drei Worte haben.
• – Ein Satz darf eine vorgegebene Anzahl von Worten oder Zeichen nicht überschreiten.
• Diese Regeln werden auf das erste Dokument D_0 angewendet und liefern eine Auflistung der Sätze.
• Für den Schritt 2, nämlich die Berechnung von Satz-Bewertungen, werden bevorzugt ausschließlich Schlüsselworte, die im ersten Dokument enthalten sind, herangezogen. Deren Bewertungen werden zu einer Satz-Bewertung zusammengefaßt. Sei s ein Satz des ersten Dokuments. Falls dieser Satz kein Schlüsselwort enthält, erhält er die niedrigste Bewertung, z. B. die Zahl 0. Seien ansonsten w_1, ..., w_k die k Schlüsselworte des Satzes s (k > = 1). Seien B(w_1), ..., B(w_k) die k Bewertungen dieser Schlüsselworte, die nach einer der oben beschriebenen Ausgestaltungen der Erfindung ermittelt wurden. Sei S je nach Ausgestaltung die Anzahl der Worte (Schlüsselworte und sonstige Worte) oder die Anzahl der Zeichen des Satzes s. Bevorzugt wird die Bewertung B(s) des Satzes s nach einer der folgenden Vorschriften bestimmt:

  
• Dadurch, daß in die Bewertung der Faktor k einfließt, also die Anzahl von Schlüsselworten im Satz, wird ein Satz mit mehreren Schlüsselworten in der Regel höher bewertet als einer mit nur einem Schlüsselwort, auch wenn dieses eine hohe Wort-Bewertung erhält.
• Beim Schritt 3, der Erzeugung der Zusammenfassung aus Sätzen, werden die Sätze des ersten Dokuments bevorzugt absteigend nach den in Schritt 2 berechneten Satz-Bewertungen sortiert. Die Zusammenfassung wird aus den m am höchsten bewerteten Sätzen des ersten Dokuments D_0 erzeugt. Die Reihenfolge der Sätze ist in der erzeugten Teil-Zusammenfassung die gleiche wie im ersten Dokument D_0. Vorzugsweise wird eine obere Schranke für die Anzahl der Zeichen der Zusammenfassung vorgegeben, z. B. maximal 500 Zeichen. Die Anzahl m der ausgewählten Sätze der Zusammenfassung wird so bestimmt, daß die m Sätze zusammen nicht mehr Zeichen als die vorgegebene Schranke haben. Eine andere Ausgestaltung sieht vor, direkt die Anzahl m der auszuwählenden Sätze vorzugeben.
• Eine Fortbildung der Erfindung sieht vor, anstelle von Sätzen vielmehr Abschnitte des ersten Dokuments zu bewerten und die Zusammenfassung aus hoch bewerteten Abschnitten zusammenzusetzen. Die Zusammenfassung wird durch drei Schritte analog zu den oben beschriebenen drei Schritten erzeugt.
• Um den Schritt 1, nämlich die Zerlegung des Dokuments in Abschnitte, durchzuführen, wird bevorzugt die Formatierung des ersten Dokuments berücksichtigt, z. B. indem nach Leerzeilen gesucht wird oder indem syntaktische Regeln angewendet werden. In Dokument-Beschreibungssprachen wie HTML oder XML werden Abschnitte durch bestimmte Zeichenfolgen gekennzeichnet, z. B. <P> und </P>. In Schritt 2 wird die Bewertung eines Abschnitts a bevorzugt gemäß der Formel

  

  berechnet. Der Abschnitt a enthält hierbei die k Schlüsselworte w_1, ..., w_k und insgesamt A Worte.
• Eine andere Ausgestaltung sieht vor, daß eine Zusammenfassung ausschließlich aus dem am höchsten bewerteten Abschnitt des Textes erzeugt wird. Hierfür wird eine obere Schranke für die Anzahl der Zeichen der Zusammenfassung vorgegeben. Das erste Dokument wird so in Abschnitte zerlegt, daß jeder Abschnitt aus vollständigen, im ersten Dokument aufeinander folgenden Sätzen besteht und jeder Abschnitt höchsten aus so vielen Zeichen wie die obere Schranke besitzt. Jeder Abschnitt wird nach einer der oben beschriebenen Ausgestaltungen bewertet, wofür die Bewertungen der im Abschnitt enthaltenen Schlüsselworte verwendet werden. Die Zusammenfassung ist gleich dem am höchsten bewerteten Abschnitt.
• Eine weitere Ausgestaltung der Erfindung offenbart eine Methode, um mit Hilfe des Benutzer-Klickpfades direkt einen Extrakt in Form einer Zusammenfassung zu erzeugen, ohne zuvor Schlüsselworte zu ermitteln. Vorzugsweise wird wie oben beschrieben der Benutzer-Klickpfad als Suchanfrage als Suchanfrage von einem Netzwerk-Teilnehmerrechner an einen Netzwerk-Zentralrechner gesandt, um die weiteren Dokumente zu ermitteln. Eine Fortbildung sieht vor, nur diejenigen Dokumente des Benutzer-Klickpfades bei der Erzeugung einer Zusammenfassung zu berücksichtigen, die automatisch als relevant eingestuft worden sind, und zwar vorzugsweise nach einem der oben beschriebenen Ausgestaltungen. Die Zusammenfassung für das erste Dokument D_0 wird erzeugt, indem Bewertungen für die Sätze des ersten Dokuments berechnet werden. Die Zusammenfassung wird durch Zusammensetzen von hoch bewerteten Sätzen erzeugt.
• Die Bewertung eines Satzes s wird mit Hilfe des Benutzer-Klickpfades – oder nur der relevanten Dokumente des Benutzer-Klickpfades – berechnet. Seien D_1, ..., D_k die für die Berechnung der Bewertung herangezogenen Dokumente des Benutzer-Klickpfades – entweder alle oder die als relevant ermittelten Dokumente –, die im folgenden als weitere ermittelte Dokumente verwendet werden. In die Bewertung des Satzes s fließen Bewertungen von Indexierungstermen ein, die sowohl im Satz s als auch den k Dokumenten D_1, ..., D_k der weiteren ermittelten Dokumente auftreten. Seien t_1, ..., t_l diese Indexierungsterme. Diese Indexierungsterme gehören zu einer vorgegebenen Indexierungssprache, vorzugsweise sind es Quadgramme, Trigramme, Worte oder Wortstämme.
• Eine Ausgestaltung sieht vor, daß Worte des Satzes, insbesondere Schlüsselworte, bewertet werden und hierbei Funktionsworte einer Stopwortliste nicht berücksichtigt werden. Eine Bewertung B(t_j, s, BKP) des Indexierungsterms D_j bezüglich des Satzes s und der weiteren ermittelten Dokumente des Benutzer-Klickpfades BKP wird bestimmt (j = 1, ..., l). Die Satz-Bewertung B(s, BKP) wird gemäß einer Ausführungsform aus diesen l Indexierungsterm-Bewertungen durch Aufaddieren bestimmt, also gemäß der Vorschrift

  
• Diese Vorschrift wird als Euklidisches Maß für die Ähnlichkeit zwischen dem Satz und der als Suchanfrage des Informationsbeschaffungssystems behandelten Benutzer-Klickpfades BKP bezeichnet.
• Die in der obigen Berechnungsvorschrift verwendete Bewertung B(t_j, s, BKP) des Indexierungsterms t_j wird bevorzugt nach der Vorschrift B(t_j, s, BKP) = G(t_j, s)·G(t_j, BKP)berechnet. Die Bewertung des Satzes s wird demnach gemäß der Vorschrift

  

  berechnet.
• Die Gewichtungen G(t_j, s) und G(t_j, BKP) werden beide mit Hilfe einer Ausgestaltung des tf/idf-Verfahrens berechnet, nämlich gemäß den Vorschriften

  
• Hierbei geben die Term-Häufigkeiten tf(t_j) und tf(t_j, BKP) an, wie oft der Indexierungsterm t_j im Satz s bzw. in den k weiteren ermittelten Dokumenten D_1, ..., D_k auftritt, und df(t_j) ist die Anzahl von weiteren ermittelten, in denen der Indexierungsterm t_j mindestens einmal vorkommt. Der Faktor

  

  wird in dieser Ausgestaltung als inverse Dokumenthäufigkeit des tf/idf-Verfahrens verwendet.
• Gemäß einer bevorzugten Ausführungsform wird hingegen eine Normierung vorgenommen und als Ähnlichkeitsmaß zwischen dem Satz s und den ermittelten weiteren Dokumenten ein Cosinus-Maß verwendet. Die Satz-Bewertung wird dann nach der Vorschrift

  

  berechnet. Die Gewichtungen des Indexierungsterms t_j werden wie oben beschrieben berechnet.
• Eine Weiterbildung dieser Ausgestaltung sieht vor, zunächst einen Extrakt in Form einer Zusammenfassung mit Sätzen oder Abschnitten zu erzeugen und anschließend Schlüsselworte in dieser Zusammenfassung zu ermitteln. Dadurch werden weniger Schlüsselworte als bei anderen Verfahren ermittelt, weil als Schlüsselworte nur Worte der Zusammenfassung in Betracht kommen. Als Schlüsselworte werden dabei bevorzugt diejenigen Worte der Zusammenfassung ermittelt, die zur Bewertung der für die Zusammenfassung ausgewählten Sätze am meisten beigetragen haben.
• Vorzugsweise werden Bewertungen von Worten bezüglich der einzelnen Sätze der Zusammenfassung erzeugt und anschließend Gesamt-Bewertungen der Worte bezüglich der Zusammenfassung erzeugt. Beispielsweise wird die Gesamt-Bewertung B(w, s, BKP) eines Wortes w bezüglich des Satzes s der Zusammenfassung und bezüglich der weiteren ermittelten Dokumente D_1, ..., D_k des Benutzer-Klickpfades einschließlich des ersten Dokuments gemäß

  

  berechnet. Hierbei geben tf(w, s) und tf(w, BKP) an, wie oft das Wort w in dem Satz s bzw. in den k weiteren ermittelten Dokumenten auftritt. Die Anzahl von weiteren ermittelten Dokumenten, in denen das Wort w mindestens einmal vorkommt, wird mit df(w) bezeichnet.

Claims (14)

1. Verfahren zur automatischen Erzeugung eines Extrakts für ein Dokument, wobei – das Dokument Bestandteil einer für ein Informationsbeschaffungssystem elektronisch verfügbaren Dokumenten-Kollektion ist, – ein Benutzer mit dem Informationsbeschaffungssystem interagiert, wobei – das Informationsbeschaffungssystem dem Benutzer bestimmte Dokumente aus der Kollektion anbietet und – der Benutzer unter den angebotenen Dokumenten bestimmte auswählt, um sie sich anzeigen zu lassen, – das Informationsbeschaffungssystem als zeitliche Reihenfolge protokolliert, welche Dokumente der Benutzer in welcher Reihenfolge ausgewählt hat, – der Benutzer das Dokument vorgibt, für das das Extrakt erzeugt werden soll, – dann, wenn jeweils zwei gemäß der protokollierten zeitlichen Reihenfolge nacheinander ausgewählte Dokumente ein hohes Maß für die Ähnlichkeit haben, das zeitlich frühere Dokument als relevant bewertet wird, – Dokumentteile der ausgewählten Dokumente identifiziert werden, – Bewertungen der identifizierten Dokumentteile berechnet werden, – wobei die Bewertung mindestens eines Dokumentteils als Funktion eines Maßes für die Ähnlichkeiten des Dokumentteils zu den relevanten unter den ausgewählten Dokumenten und eines Maßes für die Ähnlichkeiten des Dokumentteils zu den nicht relevanten unter den ausgewählten Dokumenten berechnet wird und die Ähnlichkeiten zu den relevanten und die Ähnlichkeiten zu den nicht relevanten Dokumenten in verschiedener Weise in die Funktion eingehen, – Dokumentteile in Abhängigkeit von ihren Bewertungen ausgewählt werden und – der Extrakt aus ausgewählten Dokumentteilen zusammengesetzt wird.
2. verfahren nach Anspruch 1, dadurch gekennzeichnet, daß ein Dokument der Kollektion dann als relevant bewertet wird, wenn der Benutzer für dieses Dokument eine Suche nach ähnlichen Dokumenten veranlaßte.
3. Verfahren nach Anspruch 1 oder Anspruch 2, dadurch gekennzeichnet, daß der Extrakt als ein einziger Extrakt für das Dokument und die ausgewählten weiteren Dokumente erzeugt wird.
4. Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, daß für die Erzeugung des Extrakts eine Suchanfrage von einem Netzwerk-Teilnehmerrechner an einen Netzwerk-Zentralrechner übermittelt wird, wobei die Suchanfrage die ausgewählten weiteren Dokumente oder Verweise auf die ausgewählten weiteren Dokumente umfaßt.
5. Verfahren nach einem der Ansprüche 1 bis, dadurch gekennzeichnet, daß Gewichtungen von denjenigen ausgewählten weiteren Dokumenten, in denen das identifizierte Dokumentteil auftritt, berechnet und zusätzlich für die Bewertung des identifizierten Dokumentteils verwendet werden.
6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß – ein Maß für die Ähnlichkeit zwischen dem Dokument und den ausgewählten weiteren Dokument – berechnet und für die Berechnung der Gewichtungen der ausgewählten weiteren Dokumente verwendet wird.
7. Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß – mehrere oder alle der identifizierten und bewerteten Dokumentteile Worte sind – und der erzeugte Extrakt eine Liste von Schlüsselworten umfaßt.
8. Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, daß – mehrere oder alle der identifizierten und bewerteten Dokumentteile Sätze oder Abschnitte sind – und der erzeugte Extrakt eine Zusammenfassung umfaßt.
9. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß eine Liste von Schlüsselworten des Dokuments erzeugt wird, und die erzeugte Zusammenfassung identifizierte und bewertete Dokumentteile umfaßt, die mindestens ein Schlüsselwort enthalten.
10. Verfahren nach Anspruch 8, dadurch gekennzeichnet, daß für die Bewertung des identifizierten Dokumentteils eine Bewertung mindestens eines Wortes, das im Dokumentteil enthalten ist, verwendet wird, wobei die Wort-Bewertung von einem Maß für die Ähnlichkeit zwischen dem Wort und den ausgewählten weiteren Dokumenten abhängt.
11. Vorrichtung zur Durchführung des Verfahrens nach einem der Ansprüche 1 bis 10, dadurch gekennzeichnet, daß – Mittel zum Auswählen von weiteren Dokumenten der Kollektion, – Mittel zum Protokollieren von Benutzereingaben in das Informationsbeschaffungssystem, – Mittel zur Bewertung von Dokumentteilen in Abhängigkeit von den protokollierten Benutzereingaben, – Mittel zum Auswählen von Dokumentteilen in Abhängigkeit von ihren Bewertungen – und Mittel zum Zusammensetzen des Extrakts aus ausgewählten Dokumentteilen umfaßt.
12. Vorrichtung nach Anspruch 11, dadurch gekennzeichnet, daß die Vorrichtung Bestandteil einer Datenverarbeitungsanlage ist, die mindestens zeitweise die Funktion eines Netzwerk-Teilnehmerrechners ausübt, wobei der Netzwerk-Teilnehmerrechner mit mindestens einem Netzwerk-Zentralrechner, der einen Datenspeicher mit Dokumenten der Kollektion umfaßt, verbunden ist.
13. Computerprogramm, das in einem Computer abgearbeitet wird und dabei ein Verfahren nach einem der Ansprüche 1 bis 10 ausführt.
14. Computerprogramm-Produkt, das auf einem von einem Computer lesbaren Medium gespeichert ist und das von einem Computer lesbare Programm-Mittel aufweist, die den Computer veranlassen, ein Verfahren nach einem der Ansprüche 1 bis 10 auszuführen.