DE19952769B4

DE19952769B4 - Suchmaschine und Verfahren zum Abrufen von Informationen mit Abfragen in natürlicher Sprache

Info

Publication number: DE19952769B4
Application number: DE19952769A
Authority: DE
Inventors: Matthias Dr. Mountain View Kaiser
Original assignee: SAP SE
Current assignee: SAP SE
Priority date: 1999-11-02
Filing date: 1999-11-02
Publication date: 2008-07-17
Anticipated expiration: 2019-11-03
Also published as: EP1379972B1; DE19952769A1; WO2001033414A3; US6741959B1; AU1854001A; CA2358432A1; ATE511146T1; CA2358432C; EP1379972A2; WO2001033414A2

Abstract

Suchmaschine (100) zum Abrufen von Informationen aus Dokumenten einer Datenbasis (110) auf der Grundlage einer Abfrage (10) eines Benutzers, wobei die Suchmaschine (100) folgendes umfaßt:
einen Lexikongenerator zur Erstellung einer Wortschatz- und/oder Lexikondatenbasis (122) von Wortstämmen aus der Datenbasis (110) und aus der Abfrage (10); und
eine Auswertungskomponente (140), wobei die Auswertungskomponente (140) einen Dokumentenvektorisierer (141) zur Erzeugung von Dokumenten-Darstellungsvektoren für entsprechende Dokumente der Datenbasis (110) und einen Abfrage-Darstellungsvektor für die Abfrage (10) unter Verwendung der Wortschatz- und/oder Lexikondatenbasis (122) enthält, wobei die Dokumenten-Darstellungsvektoren Daten bezüglich der in den entsprechenden Dokumenten (110) enthaltenen Wortstämme enthalten und der Abfrage-Darstellungsvektor Daten bezüglich der in der Abfrage (10) enthaltenen Wortstämme enthält, wobei die Auswertungskomponente (140) weiterhin eine Vektorregelbasis (142) und eine Vektorauswertungsvorrichtung (143) enthält, wobei die Vektorauswertungsvorrichtung (143) die Dokumenten-Darstellungsvektoren auf der Grundlage der Vektorregelbasis (142) mit dem Abfrage-Darstellungsvektor vergleicht, wobei die Auswertungskomponente die Informationen aus der Datenbasis auf der Grundlage...

Description

Die vorliegende Erfindung betrifft eine Suchmaschine zum Abrufen von Informationen auf der Grundlage von Benutzereingaben und insbesondere eine Suchmaschine und ein Verfahren zum Abrufen, Auswerten und Einstufen von recherchierten Daten aus einem Datensatz auf der Grundlage einer Benutzerabfrage in natürlicher Sprache.
Computersysteme mit Suchmaschinen sind in der Technik bekannt und werden zum Abrufen von Informationen aus Datenbasen auf der Grundlage von Eingaben eines Benutzers verwendet, wobei unter Datenbasen insbesondere auf Datenträgern abgespeicherte Datenbanken verstanden werden. Bei großen Informationssystemen bleiben derzeitige Suchwerkzeuge jedoch bei der Bereitstellung angemessener Lösungen der komplizierteren Probleme, denen Benutzer häufig gegenüberstehen, erfolglos. Zum Beispiel beschränken viele bekannte Suchmaschinen Benutzer auf die Verwendung von Schlüssel-Suchbegriffen, die durch logische Operatoren wie zum Beispiel „und", „oder" und „nicht" verknüpft werden können. Dies ist bei komplexen Benutzerproblemen, die häufig in einer natürlichen Sprache ausgedrückt werden, unzweckmäßig. Die ausschließliche Verwendung von Schlüsselwörtern in Verbindung mit booleschen Operatoren führt häufig zu einem Mißerfolg der Suchmaschine bei der Erkennung des richtigen Kontexts der Suchbegriffe. Dies kann zu dem Abrufen einer großen Informationsmenge aus der Datenbank führen, die häufig nicht sehr viel mit der Fragestellung des Benutzers zu tun hat. Da bekannte Suchmaschinen die Komplexität der Benutzereingabe nicht ausreichend verarbeiten, kommt es häufig vor, daß es mit derzeitigen Online-Hilfeeinrichtungen sehr schwierig ist, relevante Dokumentation für ein der Suchanfrage zugrunde liegendes komplexes Problem zu recherchieren.
Ein weiteres Problem bei derzeitigen Verfahren zum Abrufen von Dokumenten besteht darin, daß der Benutzer bestimmte, bei einer Suche ermittelte Dokumente wichtiger als andere erachten kann, der Benutzer jedoch nicht in der Lage ist, ein Kriterium für die Relevanz der zu ermittelnden Dokumente vorab explizit auszudrücken. Bei der Arbeit mit komplexen Kontexten ist es deshalb häufig schwierig, ein Relevanzkriterium genau und explizit anzugeben.
Das Dokument US 5,963,940 offenbart ein System und ein Verfahren zum Abrufen von Informationen in natürlicher Sprache, bei dem ein Benutzer eine Anfrage eingibt und das System die Anfrage bearbeitet, um eine alternative Darstellung zu erzeugen. Nach der Bearbeitung der Anfrage zeigt das System dem Benutzer Anfrageinformationen an, mit denen die Interpretation und Darstellung des Inhalts der Anfrage durch das System erkenntlich sind. Der Benutzer hat dann die Gelegenheit, eine Eingabe zu machen, auf die das System mit einer Modifikation der alternativen Darstellung reagiert. Nachdem der Benutzer eine gewünschte Eingabe gemacht hat, wird die möglicherweise modifizierte Darstellung der Anfrage mit der betreffenden Dokumentendatenbank verglichen, und für die Dokumente wird ein Maß für deren Wichtigkeit erzeugt. Ein Dokumentensatz wird dem Benutzer angezeigt, aus dem er ein Dokument oder alle auswählen kann.
Das Dokument US 5,873,056 offenbart ein System zur Verarbeitung natürlicher Sprache zur semantischen Vektordarstellung, welches lexikalische Mehrdeutigkeiten berücksichtigt. Das System verwendet unformattierten natürlich vorkommenden Text und erzeugt eine Vektordarstellung des Textes, der ein gesamtes Dokument oder ein Teil eines Dokumentes wie zum Beispiel der Titel, ein Absatz, ein Satz oder ein Satzteil sein kann.
Das Dokument US 5,778,357 offenbart ein System zur Datenabfrage von Marktinformationen.
Das Dokument EP 0 522 591 A2 offenbart ein Datenbankabfragesystem mit einem Parser zum Parsen einer Eingabe in einer natürlichen Sprache in Ausdrücke als Ergebnis einer Syntaxanalyse.
Das Dokument WO 97/08604 A2 offenbart ein System zum Auffinden mehrsprachiger Dokumente und ein Verfahren, das semantische Vektoren verwendet.
Aufgabe der vorliegenden Erfindung ist die Bereitstellung einer Suchmaschine, eines Verfahrens sowie eines computerlesbaren Mediums mit mehreren darauf gespeicherten Anweisungen, die bei der Ausführung durch einen Prozessor bewirken, daß der Prozessor das Verfahren ausführt, die einen allgemeinen oder nicht-kontextspezifischen Ansatz für ein Suchwerkzeug verwenden, das in der Lage ist, nach Informationen in Dokumenten einer Datenbank auf der Grundlage einer Problemspezifikation zu suchen, die gänzlich in natürlicher Sprache formuliert wird und die nicht auf eine spezifische Umgebung, wie zum Beispiel das Abrufen aus einer Datenbank, beschränkt ist, sondern auch in vielfältigen Kontexten, wie zum Beispiel der kontextsensitiven Online-Hilfe in komplexen Arbeits- und Informationsumgebungen, der Recherche nach relevanten Informationen in Ausbildungs- und Benutzungssystemen sowie für die Entscheidungsfindung bei der Organisation von Informationsdatenbanken und z. B. suchenden, Informationsagenten verwendet werden kann.
Diese Aufgabe wird durch eine Suchmaschine mit den Merkmalen des Anspruchs 1, durch ein Verfahren mit den Merkmalen des Anspruchs 12 sowie durch ein computerlesbares Medium mit den Merkmalen des Anspruchs 22 gelöst. Bevorzugte Ausführungsformen sind Gegenstand der abhängigen Ansprüche.
Gemäß der Erfindung wird diese Aufgabenstellung dadurch gelöst, daß eine Suchmaschine bereitgestellt wird, mit der eine Suche von in natürlicher Sprache formulierte Abfrage durchgeführt werden kann. Das Verfahren reduziert die in natürlicher Sprache eingegebene Abfrage zu einem Vektor von Wortstämmen (AWSV), und kann außerdem die abzusuchenden Dokumente zu Vektoren von Wortstämmen (DWSV) reduzieren, wobei ein Wortstamm ein Wort oder ein Teil eines Worts ist, aus dem die verschiedenen Formen eines Worts abgeleitet werden. Die Suchmaschine analysiert die Vektoren von Wortstämmen, um Parameter wie zum Beispiel die Häufigkeit, mit der Wortstämme in der Abfrage und in Dokumenten der Datenbasis auftreten, und/oder die Signifikanz der in den Dokumenten erscheinenden Wortstämme und andere Vergleichsinformationen zwischen dem Abfragevektor und den Datenbank-Dokumentvektoren zu bestimmen, um so die Eignung eines Dokuments, als Ergebnis der Abfrage zu dienen, festzustellen.
Die erfindungsgemäße Suchmaschine bzw. das Verfahren zum Abrufen von Informationen aus einer Datenbank auf der Grundlage einer Abfrage eines Benutzers enthält vozugsweise einen Lexikongenerator zum Ableiten einer Lexikon-Datenbasis (LDB) von Wortstämmen aus den Dokumenten der Datenbasis einerseits und aus der Abfrage andererseits. Sie kann weiterhin eine Auswertungskomponente enthalten, die einen Dokument-Vektorisierer zur Erzeugung von Dokumenten- Darstellungsvektoren (DDV) für die Dokumente der Datenbasis und einen Abfrage-Darstellungsvektor (ADV) für die Abfrage unter Verwendung der Lexikon-Datenbasis aufweist. Die Dokumenten-Darstellungsvektoren enthalten Daten über die Wortstämme in der Abfrage. Die Auswertungskomponente enthält weiterhin eine Vektorregelbasis und eine Vektorauswertungsvorrichtung zur Anwendung eines Auswertungsverfahrens. Die Vektorauswertungsvorrichtung leitet eine Relevanzwert für einen Dokumenten-Darstellungsvektor relativ zu einem Abfrage-Darstellungsvektor gemäß der Vektorregelbasis und der Ausgangsinformationen aus der Datenbasis ab. Die Suchmaschine kann außerdem eine Feinabstimmvorrichtung zum Modifizieren der Vektorregelbasis enthalten. Mit einer von dem Benutzer bereitgestellten externen Rückmeldung (Feedback) über die aus der Datenbasis abgerufenen Informationen kann die Feinabstimmvorrichtung die Vektorregelbasis modifizieren.
Die vorliegende Erfindung betrifft außerdem ein Verfahren zur Anwendung der Suchmaschine zum Abrufen von Dokumenten aus einer Datenbasis durch eine Abfrage, das die folgenden Schritte aufweist:

(i) Ableiten einer Wortschatzdatenbasis von Wortstämmen aus den Dokumenten der Datenbasis und dem Abfragedokument der z. B. durch die Eingabeeinheit eingegebenen Abfrage,
(ii) Erzeugen eines Dokumenten-Darstellungsvektors (DDV) entsprechend jedem Dokument der Datenbasis und eines Abfrage-Darstellungsvektors entsprechend der Abfrage, wobei jeder Dokumenten-Darstellungsvektor Informationen über die Wortstämme der Wortschatzdatenbasis enthält, die in dem Dokument enthalten sind, dem der zugehörige Darstellungsvektor entspricht, wobei der Abfrage-Darstellungsvektor Informationen über die Wort stämme enthält, die in dem Abfragedokument enthalten sind,
(iii) Auswerten jedes Darstellungsvektors relativ zu dem Abfrage-Darstellungsvektor (ADV) unter Verwendung von Vektor-Auswertungsregeln, zum Beispiel Bewerten der Ähnlichkeit der in Vektoren enthaltenen Elemente,
(iv) Erzeugen einer Ausgabe, die die Auswertung der Darstellungsvektoren widerspiegelt und
(v) Ausgeben der Ausgabe auf der Ausgabeeinheit.

Die Erfindung wird nachfolgend anhand eines bevorzugten, in Figuren dargestellten, Ausführungsbeispiels näher erläutert.
Es zeigen:
1: eine Übersicht der Suchmaschine,
2: ein Flußdiagramm eines Verfahrens zum Suchen einer Datenbasis gemäß der vorliegenden Erfindung,
3: ein Beispiel der Lexikon-Komponente gemäß der vorliegenden Erfindung,
4: ein Beispiel der Auswertungskomponente gemäß der vorliegenden Erfindung,
5: ein Flußdiagramm eines Entwicklungsalgorithmus für die Feinabstimmvorrichtung gemäß der vorliegenden Erfindung und
6: eine Computersystemimplementierung einer Ausführungsform der vorliegenden Erfindung.
1 zeigt die Suchmaschine 100 der vorliegenden Erfindung. Die Suchmaschine 100 nimmt eine Abfrage 10 (die auch als ein Abfragedokument 10 bezeichnet wird) als eine Eingabe des Benutzers über die nicht dargestellte Eingabeeinheit an. Die Abfrage 10 besteht z. B. aus einer Spezifikation eines verbal formulierten komplexen Benutzerproblems mit Suchbegriffen in natürlicher Sprache. Die Suchmaschine 100 verwendet die Inhalte dieser Abfrage 10 zum Auffinden relevanter Dokumente oder von Teilen von Dokumenten aus der Datenbasis 110. Dokumente 111 bedeuten allgemein ein beliebiges Dokument oder beliebige Dokumente in der Datenbasis 110. Die Suchmaschine 100 enthält Mittel zum Auswerten von Dokumenten, wie zum Beispiel eine Auswertungskomponente 140, die die Dokumente 111 mit der Abfrage 10 vergleicht und ein Resultat 20 erzeugt. Das Resultat 20 kann zum Beispiel eine Liste von Dokumenten aus der Datenbasis 110 mit einer Einstufung ihrer Relevanz für das Abfragedokument 10 sein. Als Alternative dazu könnte das Resultat 20 eine Liste einer Teilmenge der Dokumente 111, der Text der Dokumente 111, der das Suchkriterium betrifft, Teile der Dokumente 111, die mit dem Suchkriterium übereinstimmen, oder Informationen in bezug auf Suchstatistiken, wie zum Beispiel die Häufigkeit des Auftretens von Wörtern in einem durchsuchten Dokument 111, die mit Wörtern in dem Abfragedokument 10 übereinstimmen, oder andere Arten von Suchergebnissen sein, die Fachleuten bekannt sind.
Wie in 1 gezeigt, kann die Suchmaschine 100 gemäß einer Ausführungsform der vorliegenden Erfindung außerdem eine Feinabstimmvorrichtung 130 aufweisen. Die Feinabstimmvorrichtung 130 ermöglicht, daß der Suchmaschine 100, z. B. durch den Benutzer, zusätzliche externe Suchkriterien bereitgestellt werden. Die Feinabstimmvorrichtung 130 verwendet die Benutzereingaben 30 zur Veränderung der Auswertungskomponente 140 zur Beeinflussung des Resultats 20 der Suche. Die Feinabstimmvorrichtung 130 wird nachfolgend ausführlicher besprochen.
Bei der Datenbasis 110 kann es sich zum Beispiel um eine Ansammlung von Dokumenten in natürlicher Sprache oder andere Formen von Daten handeln. Die Informationen der Datenbasis liegen z. B. in Form von Text wie zum Beispiel Notizen, Kommentaren über Objekte wie zum Beispiel Medien in einem Medienarchiv, Angestellteninformationen, Informationen in Logistik-Datenbasen wie zum Beispiel Materialressourcen, Katalogen zum Kauf oder zum Einkauf über Internet oder in anderen Formen von Informationen vor.
Obwohl sich die Beschreibung der bevorzugten Ausführungsform auf die Dokumente der Datenbasis 110 bezieht, kann die Suchmaschine 100 mit Datenbasen arbeiten, die nicht streng genommen Dokumente in einer vordefinierten Form enthalten. Allgemeiner bezeichnet der Begriff Dokument keine besondere Struktur, sondern wird zum gattungsgemäßen Bezug auf eine beliebige Partition, Unterteilung, Komponente, einen Abschnitt oder Teil der Datenbasis verwendet, ungeachtet, wie diese aufgeteilt oder abgegrenzt wird. Zusätzlich müssen die Datenbasis 110 und die in der Datenbasis 110 enthaltenen Dokumente 111 keine bestimmte Struktur oder Organisation aufweisen. Die Suchmaschine 100 könnte jedoch eine spezielle Struktur oder Organisation der Datenbasis 110 ausnutzen, indem zum Beispiel entsprechende Strukturanalysiermodule zur Verbesserung der Genauigkeit und Effizienz des Suchverfahrens integriert werden.
Außerdem ist die Suchmaschine 100 gemäß der vorliegenden Erfindung nicht auf eine spezifische Umgebung, wie zum Beispiel das Abrufen aus einer Datenbasis, beschränkt, sondern kann auch in vielfältigen Kontexten, wie zum Beispiel bei der kontextsensitiven Online-Hilfe in komplexen Arbeits- und Informationsumgebungen, dem Abrufen von relevanten Informationen in Ausbildungs- und Konsultationssystemen, beim Entscheidungssupport für die Organisation von Informationsdatenbasen und Informationsagenten verwendet werden, die zum Aufbau, der Organisation und Wartung neuer Informationsdatenbasen verwendet werden.
Die Dokumentendatenbasis 110 enthält die Dokumente 111, die als Reaktion auf das Abfragedokument 10 inhaltlich ausgewertet werden sollen. Bei der Datenbasis 110 kann es sich um eine vorbestimmte Anzahl von Dokumenten oder eine dynamische Anzahl erzeugter Dokumente handeln. Zum Beispiel ermöglicht die Suchmaschine 100 eine umdefinierte oder neu ausgerichtete Suche, bei der die Datenbasis 110 die Ausgabe einer früheren Suche sein kann.
2 zeigt ein Flußdiagramm mit Verfahrensschritten gemäß einer Ausführungsform der Erfindung, die zur Bewertung der Relevanz von Dokumenten 111 im Bezug auf die Abfrage 10 verwendet werden. Als erstes wird, wie im Block 11 gezeigt, eine Wortschatzdatenbasis 122 (z. B. eine Lexikon-Datenbasis) (siehe 3) aus den Dokumenten 111 abgeleitet. Die Wortschatzdatenbasis 122 ist eine Ansammlung von Wortstämmen 126, die von den Dokumenten 111 und der Abfrage 10 abgeleitet werden. Ein Wortstamm ist das Wort oder der Teil eines Worts, aus dem verschiedene Formen eines Worts abgeleitet werden. Zum Beispiel könnten die Wörter "erkennen" und "erkennbar" auf den Wortstamm "erkenn" reduziert werden. Die Wörter "abtrennbar" und "abtrennen" können auf den Wortstamm "abtrenn" reduziert werden. Die Bestimmung von Wortstämmen wird ausführlicher in bezug auf 3 besprochen.
Die Zusammenstellung und der Aufbau der Wortschatzdatenbasis 122 erfolgt bevor die Suchmaschine 100 von einem Benutzer auf eine bekannte Datenbasis 110 angewandt wird. Wenn die zu durchsuchende Datenbasis 110 jedoch entsprechend der Benutzerwahl aus einer umfangreichen Dokumentenquelle erstellt wird, wie zum Beispiel aus dem Internet abgerufene Dokumente oder eine bestimmte andere Quelle, die nicht genau definiert ist oder modifiziert, aktualisiert oder erweitert werden kann, ist es gegebenenfalls nicht möglich, die Dokumente 111 der Datenbasis 110 zur Erzeugung der Wortschatzdatenbasis 122 zu verarbeiten, bevor die Suchmaschine 100 vom Benutzer eingesetzt wird.
Die Dokumente 111 werden im Parsingverfahren lexikalisch gegliedert und in ihre Wortstämme zerlegt (Wortstammerzeugung), um derartig eine Wortschatzdatenbasis 122 unter Verwendung eines Mittels zur Erzeugung einer Wortschatzdatenbasis, wie zum Beispiel dem Lexikongenerator 121 zu erzeugen. Mit der Wortschatzdatenbasis 122 werden Darstellungsvektoren der Dokumente 111 und der Abfrage 10 erzeugt, wie durch den Block 12 angezeigt. Die Wortstämme 126, die in einem Dokument enthalten sind, werden in einem Darstellungsvektor gespeichert. Gemäß Block 13 vergleicht die Vektor-Auswertungsvorrichtung die Darstellungsvektoren der Dokumente 111 der Dokumentendatenbasis 110 mit dem Darstellungsvektor der Abfrage 10 bzw. wertet diese aus, wie nachfolgend näher dargestellt wird.
Wie in Block 14 gezeigt, gewichtet die Auswertungsvorrichtung nach der Auswertung der Darstellungsvektoren die Dokumente 111 der Dokumentendatenbasis 110 und zeigt die Ergebnisse dem Benutzer mittels der Anzeige- und/oder der Ausgabeeinheit an. Die Ausgabe bzw. das Resultat 20 der Suche ist z. B. eine Liste gewichteter Suchergebnisse, welche die Dokumente 111 in der Reihenfolge ihrer Relevanz in bezug auf die Suchkriterien der Abfrage 10 angibt. Alternativ werden dem Benutzer ausschließlich die relevanten Teile der Dokumente 111 vorgelegt.
Die obigen Schritte zur Erzielung der Ergebnisse können erfindungsgemäß auch in einer anderen Reihenfolge durchgeführt werden. Zum Beispiel kann es angemessen sein, die Darstellungsvektoren der Dokumente 111 zusammen mit dem Parsingverfahren und der lexikalischen Gliederung in Wortstämme zu erzeugen. Dies stellt einen effizienteren Algorithmus dar als, wenn alle Dokumente zuerst im Parsing- und Wortstammerzeugungs-Verfahren bearbeitet werden und danach die Darstellungsvektoren erzeugt werden.
Mit Bezug auf 3 besteht die Lexikonkomponente 120 gemäß einer Ausführungsform der vorliegenden Erfindung aus zwei Teilen: dem Lexikongenerator 121 und der Wortschatzdatenbasis 122. Der Lexikongenerator 121, der aus einem Parser 123, einem Stammbildner 124 und einer Stammbildnerregelbasis 125 besteht, kann die Dokumente der Datenbasis 110 und das Abfragedokument 10 bearbeiten, um die Wortschatzdatenbasis 122 zu erzeugen. Der Lexikongenerator 121 verarbeitet ein Dokument im Parsing-Verfahren zu einer Liste von einzelnen Wörtern unter Verwendung des Parsers 123.
Nach dem Parsen eines Dokuments reduziert der Lexikongenerator 121 einzelne Wörter unter Verwendung des Stammbildners 124 zu Wortstämmen 126. Wortstämme 126 sind partielle Wortformen, die aus einzelnen Wörtern des Dokuments abgeleitet werden. Der Wortstammbildner 124 verwendet heuristische Regeln aus der Stammregelbasis 125 zur Reduktion gebeugter oder verbundener Wörter auf ihre Wortstämme 126. Die aus den Dokumenten 111 der Datenbasis 110 abgeleiteten Wortstämme 126 werden in die Wortschatzdatenbasis 122, z. B. in eine Lexikon-Datenbasis integriert.
Gemäß einer Ausführungsform der Erfindung kann die Liste einzelner Wörter zur Erleichterung der Verarbeitung der Wörter aus den Dokumenten 111 alphabetisch sortiert werden. Da die Wortliste sortiert ist, ist das erste Wort einer Gruppe ähnlicher Wörter das kürzeste, wobei ähnliche Wörter denselben Wortstamm 126 aufweisen, aber verschiedene Endungen aufweisen, zum Beispiel können "erkennen" und "erkennbar" den Wortstamm "erkenn" erzeugen. Die Erfindung ist flexibel und ermöglicht alternative Regeln zur Ableitung von Wortstämmen. Gemäß einer alternativen Ausführungsform erzeugen zum Beispiel die Wörter "erkennen" und "erkennbar" den Wortstamm "erkennen".
Ähnlichkeitsregeln helfen bei der Bestimmung, ob zwei Wörter ähnlich sind, und können zur Bestimmung eines Wortstamms verwendet werden. Wenn das Wort zum Beispiel "lese" ist, kann gemäß den Ähnlichkeitsregeln erkannt werden, daß die Wörter "liest", "Leser" und "lesend" denselben Wortstamm "lese" tragen. Bei der Aufstellung von Ähnlichkeitsregeln werden die Konzepte von minimalen Wortlängen und des Ähnlichkeitsschwellenwerts, die bei verschiedenen Ausführungsformen verändert werden können, herangezogen, um die Leistung der Suchmaschine 100 einzustellen. Die minimale Wortlänge bedeutet eine minimale Anzahl von Buchstaben, die in verschiedenen Vergleichsoperationen verwendet werden. Der Ähnlichkeitsschwellenwert bedeutet eine Schwellenanzahl von Buchstaben, die bei Wörtern, die als ähnlich angesehen werden, verschieden sein können. Ähnlichkeitsregeln, die verwendet werden können, sind zum Beispiel u. a. die folgenden:

1. Ein Wort muß eine minimale Wortlänge (z. B. vier Buchstaben) aufweisen, um ein Anwärter für einen Ähnlichkeitsvergleich zu sein. Für Wörter mit weniger als der minimalen Wortlänge (z. B. drei Buchstaben oder weniger) müssen die Wörter völlig übereinstimmen, um als ähnlich angesehen zu werden. Zum Beispiel können gemäß des Bei spiels der Verwendung einer minimalen Wortlänge von vier Zeichen oder Buchstaben Wörter mit drei Zeichen oder Buchstaben direkt als ein Stammwort in die Wortschatzdatenbasis eingegeben werden.
2. Wenn zwei Wörter die gleiche Länge aufweisen und für mindestens eine minimale Wortlänge übereinstimmende Buchstaben aufweisen und die Anzahl von nichtübereinstimmenden Zeichen oder Buchstaben am Ende der Wörter den Ähnlichkeitsschwellenwert nicht übersteigt, dann ist das Wort ohne den ungleichen Teil der Wortstamm.
3. Wörter, die für mindestens eine minimale Wortlänge identische Zeichen oder Buchstaben aufweisen und eine unterschiedliche Länge von höchstens dem Ähnlichkeitsschwellenwert (z. B. drei) aufweisen, werden als ähnlich angesehen. Das kürzere Wort wird als der Wortstamm angenommen.
4. Wörter, die für mindestens die minimale Wortlänge dieselben Zeichen oder Buchstaben aufweisen und eine Längendifferenz von höchstens einem Ähnlichkeitsschwellenwert aufweisen, werden als ähnlich angesehen. Der Teil der Wörter, der übereinstimmende Zeichen oder Buchstaben aufweist, wird als der Wortstamm angenommen.

Man beachte, daß die Regeln 3. und 4. ähnlich sind. Unter bestimmten Umständen würden sie bei der Bestimmung von Wortstämmen dasselbe Ergebnis liefern, würden unter anderen Umständen jedoch unterschiedliche Ergebnisse liefern. Zum Beispiel würden die Regeln 3. und 4. bei der Verarbeitung der Wörter "lese" und "lesend" denselben Wortstamm liefern. Wenn die minimale Wortlänge für den Ähnlichkeitsvergleich vier beträgt, dann ist "lese" ein potentieller Wortstamm. Wenn der Ähnlichkeits schwellenwert drei beträgt, dann ist "lesend" "lese" ähnlich, weil es mit dem Wortstamm übereinstimmt und am Ende zwei unterschiedliche Buchstaben aufweist (was nicht mehr als der Ähnlichkeitsschwellenwert ist). Gemäß beider Regeln 3. und 4. ist "lese" der Wortstamm für "lese" und "lesend".
Die Regeln 3. und 4. würden bei der Verarbeitung von "erkennen" und "Erkennung" ein verschiedenes Ergebnis liefern. Gemäß Regel 3. wäre "erkennen" der Wortstamm. Gemäß Regel 4. wäre "erkenn" der Wortstamm. Somit liefern die Regeln 3. und 4. zwei verschiedene Arten der Bestimmung von Wortstämmen und stellen somit bei dem Aufbau der Suchmaschine Alternativen dar. Es ist z. B. möglich, ein Mittel bereitzustellen, das einem Benutzer erlaubt, zwischen den beiden Ähnlichkeits-Vergleichsregeln entsprechend seiner Preferenz auszuwählen.
Gemäß der obigen beispielhaften Ausführungsform findet der Lexikongenerator 121 nicht immer unbedingt grammatisch korrekte Wortstämme 126. Er findet jedoch Wörter mit derselben oder ähnlichen Wortschatzbedeutung. Man betrachte zum Beispiel die englischen Wörter "voluntarism" und "voluntary". Gemäß der obigen Regel 4 (bei Verwendung einer minimalen Wortlänge von vier und einem Ähnlichkeitsschwellenwert von drei) ist "voluntar" der Wortstamm von "voluntarism" und "voluntary". Obwohl dies möglicherweise im grammatischen Sinn nicht korrekt ist ("voluntar" ist keine grammatische Wortwurzel), ist es bei der Feststellung einer Ähnlichkeit zwischen den beiden Wörtern hilfreich.
Der Lexikongenerator 121 ist vorteilhaft, weil er zur Erzeugung einer Wortschatzdatenbasis 122 aller in der Dokumentendatenbasis 110 vorkommenden Wortstämme ohne Kenntnis eines grammatischen Modells der zugrunde liegenden natürlichen Sprache verwendet werden kann. Gemäß der vorliegenden Erfindung reicht es aus, wenn nachvollziehbare und konsistente Hypothesen eingesetzt werden, die zu Wortstämmen 126 für die in den Dokumenten der Datenbasis 110 enthaltenen Wörter führen. Das beschriebene Verfahren der Stammbildung kann ohne wesentliche Anpassung insbesondere für alle indoeuropäischen Sprachen verwendet werden. Bei anderen Sprachen kann das Verfahren gegebenenfalls angepaßt und weiter verbessert werden, um Charakteristika der verschiedenen Sprachen zu berücksichtigen.
So kann die Erfindung auch auf Sprachen angewandt werden, die auf Zeichen- oder Symboldarstellungen, wie z. B. die japanische oder chinesische Sprache basieren. Hierbei weist die Erfindung Mittel auf, mittels welchen die Wortstammbildung in diesen Zeichensprachen in besonderer Weise berücksichtigt ist.
Auch wenn die heuristischen Regeln der Stammbildnerregelbasis 125 in bestimmten speziellen Fällen erfolglos bleiben, ist die resultierende Wortschatzdatenbasis 122 in der Regel ausreichend für das Suchverfahren der vorliegenden Erfindung. Die besten Ergebnisse werden dann erzielt, wenn die heuristischen Regeln der Stammbildnerregelbasis 125 konsistent verwendet werden. Es ist jedoch vorteilhaft, dieselbe oder eine ähnliche Stammbildnerregelbasis 125 auf ein gegebenes Abfragedokument 10 und auf die Dokumente der Datenbasis 110 anzuwenden, um beim Vergleich von Abfragedokumenten 10 mit der Wortschatzdatenbasis 122 einheitliche Ergebnisse zu erzielen.
Gemäß den obigen beispielhaften Stammbildnerregeln können Wörter mit denselben Wortanfängen, aber mit verschiedenen Endungen auf einen gemeinsamen Wortstamm 126 reduziert werden, die zu der Wortschatzdatenbasis 122 hinzugefügt werden können. Die Suchmaschine 100 kann als Option Regeln zum Vergleichen von Wörtern mit verschiedenen Vorsilben enthalten. Als Beispiel betrachte man, daß das englische Wort "mobile" in der Wortschatzdatenbasis (Lexikon-Datenbasis) 122 vorliegt und das Wort "immobile" verarbeitet wird. "Immobile" kann auf die folgende Weise ähnlich wie "mobile" ähnlich gefunden werden:

1. Ein Wort in einer Benutzerabfrage, das nicht im Lexikon gefunden wurde, wird in alle seine Teilzeichenketten zerlegt, die größer oder gleich der minimalen Wortlänge sind. Unter Annahme einer minimalen Übereinstimmungslänge von vier erzeugt "immobil" die Zeichenketten "immo", "immob", "immobi", "immobil", "mmob", "mmobi", "mmobil", "mmobile", "mobi", "mobil", "mobile", "obil", "obile" und "bile".
2. Alle diese Teilzeichenketten werden mit Einträgen in der Lexikon-Datenbasis 122 verglichen. Vorzugsweise wird die Übereinstimmung der längsten Teilzeichenkette festgestellt. Deshalb besteht ein Verfahren zum Auffinden einer Übereinstimmung darin, mit der Teilzeichenkette der längsten Länge zu beginnen, der dann abnehmende Längen folgen, bis eine Übereinstimmung gefunden wird. Da die Teilzeichenkette "mobile" ein Eintrag im Lexikon 122 ist, wird das in der Benutzerabfrage gegebene ursprüngliche Wort "immobile" dem Lexikoneintrag "mobile" zugeordnet.
3. Dokumente, die das Wort "immobile" enthalten, werden nicht so hoch eingestuft, wie die, die "mobile" enthalten, werden jedoch höher eingestuft als Dokumente, die keine solche Zuordnungen enthalten.

Die Regeln zur Zerlegung von Wörtern in ihre Wortstämme 126 werden durch die Stammbildnerregelbasis 125 bereit gestellt. Wortstämme 126 aus den Wörtern aller Dokumente 111 der Datenbasis 110 werden in der Lexikon-Datenbasis 122 gespeichert. Wörter aus den Dokumenten 111 werden in der Lexikon-Datenbasis 122 nachgeschlagen, indem das Wort unter Verwendung der Stammbildnerregelbasis 125 in Stämme aufgetrennt wird und dann in der Lexikon-Datenbasis 122 nach dem Wortstamm 126 gesucht wird. Jedem Wortstamm 126 wird in der Lexikon-Datenbasis 122 ein eindeutiger Index zugewiesen. Der Wortstamm 126, der eindeutige Index des Wortstamms sowie andere Informationen, wie zum Beispiel die Häufigkeit des Auftretens des Wortstamms 126 in jedem Dokument 111 werden in der Lexikon-Datenbasis 122 gespeichert.
Man betrachte zum Beispiel ein Dokument 111, dem die Identifizierungsnummer 50 gegeben wird und die Wörter "lese", "lesend", "liest", und "Leser" enthält. Alle diese Wörter können durch Verwendung der obigen beispielhaften Stammbildnerregeln dem Wortstamm "lese" zugeordnet werden. Somit könnte ein Lexikoneintrag, der den Wortstamm 126, das Dokument 111 (mit der hypothetischen Identifizierungsnummer 50) und die Häufigkeit des Wortstamms 126 identifiziert, der folgende sein: lese 50 4
Zusätzlich zu Informationen, die die Häufigkeit eines Wortstamms 126 anzeigen, kann jedem Wortstamm 126 außerdem ein Signifikanzwert zugewiesen werden. Ein Signifikanzwert kann z. B. auf der eindeutigen Identifizierungskraft eines Worts in Dokumenten oder bestimmten anderen Kriterien basieren. Zum Beispiel hat ein Artikel wie zum Beispiel "der" oder "ein" keine signifikante Identifizierungskraft, um zu zeigen, welche Dokumente für eine Abfrage relevant sind. Im Gegensatz dazu hat ein Wort wie "Präsident" Identifizierungskraft. Ein Kriterium zur Bestimmung des Signifikanzwerts eines Wortes ist z. B. die Anzahl von Dokumenten, in denen der Wortstamm 126 tatsächlich aufgetreten ist. Jedem Wortstamm 126 wird ein eindeutiger Signifikanzwert zugeordnet. Der Signifikanzwert selbst kann zum Beispiel als ein Multiplikator in dem nachfolgend besprochenen Auswertungsprozeß verwendet werden. Wenn zum Beispiel ein Wort in einem Dokument 111 der Datenbasis 110 gefunden wird, kann sein Auftreten unter Verwendung des dem Wort in der Lexikon-Datenbasis 122 zugewiesenen Signifikanzwerts als Multiplikator herausgestellt werden.
Signifikanzwerte werden unter Verwendung von Informationen gefunden, welche bei der Verarbeitung der Dokumente 111 der Datenbasis 110 gewonnen werden. So z. B. wird die Anzahl der Dokumente 111, in welchen ein bestimmter Wortstamm 126 vorhanden ist, ermittelt, nachdem sämtliche Dokumente 111 analysiert und die in ihnen enthaltenen Wortstämme 126 bestimmt worden sind. In analoger Weise wird die Anzahl der in einem bestimmten Dokument 111 enthaltenen Wortstämme 126 bestimmt. Derartige Informationen werden zur Berechnung der Signifikanzwerte verwendet. Generell gilt, daß je mehr Dokumente 111 in einer Datenbasis 110 einen bestimmten Wortstamm 126 aufweisen, um so weniger signifikant ist der spezifische Wortstamm 126, um die Dokumente 111 voneinander zu unterscheiden. Falls z. B. ein Wortstamm 126 in allen Dokumenten 111 vorkommt, so ist dieser spezifische Wortstamm 126 wenig signifikant für einzelne unterschiedliche Dokumente 111. In diesem Fall kann die Häufigkeit, mit der der Wortstamm 126 in einzelnen Dokumenten 111 vorkommt, verwendet werden, um diese voneinander zu unterscheiden. Andererseits gilt, daß je häufiger ein spezifischer Wortstamm 126 in Relation zu anderen in diesem Dokument 111 enthaltenen Wortstämmen 126 vorkommt, desto signifikanter ist der häufigere Wortstamm 126 für dieses spezifische Dokument 111. So ist ein spezifischer Wortstamm 126, der zehnmal häufiger in einem Dokument 111 vorkommt, als ein anderer Wortstamm, welcher nur dreimal in diesem Dokument 111 vorkommt, charakteristischer und signifikanter für dieses spezifische Dokument 111.
Zur formelmäßigen Berechnung des Signifikanzwertes für in einer Datenbasis 110 auftretende Wortstämme 126 ergibt sich:
Signifikanzwert = (Logarithmus der Anzahl aller Dokumente 111 in der Datenbasis 110) – (Logarithmus der Anzahl der Dokumente 111, in welchen der Wortstamm 126 vorkommt).
Dieser Signifikanzwert wird als Globalsignifikanzwert angesehen, da seine Bestimmung auf der Gesamtheit der in der Datenbasis 110 enthaltenen Dokumente 111 basiert.
Neben diesem Globalsignifikanzwert kann ein spezifischer Signifikanzwert definiert werden, der ein Maß dafür gibt, wie signifikant ein Wortstamm 126 für ein spezifisches Dokument 111 ist:
Spezifischer Signifikanzwert = (Häufigkeit eines Wortstamms 126 in einem spezifischen Dokument 111) geteilt durch (Gesamtanzahl der Wörter in dem Dokument 111).
Der spezifische Signifikanzwert kann auch angesehen werden als inverse Dokumentenhäufigkeit eines spezifischen Bezeichners oder Ausdrucks. Ein gemeinsames, einheitliches Merkmal dieser Berechnungsverfahren ist, daß sie auf der Wortstammhäufigkeit und nicht auf den in den Dokumenten 111 vorkommenden Wörtern basieren.
Die Lexikon-Datenbasis 122 besteht hauptsächlich aus den Wortstämmen 126, die durch den Lexikongenerator 121 erzeugt wurden. Zum Beispiel ist die Lexikon-Datenbasis 122 eine alphabetisch geordnete Liste von Wortstämmen 126. Der Index für einen gegebenen Lexikoneintrag oder Wortstamm 126 ist aus der Lexikon-Datenbasis 122 abrufbar. Um ein Wort in der Lexikon-Datenbasis 122 aufzufinden, wird das Wort mit dem Wortstammbildner 124 auf seinen Wortstamm 126 reduziert. Der Einheitlichkeit des Abrufprozesses wegen ist es vorteilhaft, zur Ableitung von Wortstämmen 126 für die Dokumente der Datenbasis 110 und auch für das Abfragedokument 10 dieselbe Stammbildnerregelbasis 125 zu verwenden. Die Lexikon-Datenbasis 122 wird nach dem Wortstamm 126 durchsucht. Wenn der Wortstamm 126 in der Wortschatzdatenbasis 122 aufgefunden wird, dann wird die entsprechende Position bzw. der entsprechende Index als das Ergebnis des Abrufprozesses zurückgegeben.
Die Erfindung umfaßt eine Auswertungskomponente 140 (siehe 4), die die Dokumente 111 der Datenbasis 110 mit dem Abfragedokument 10 vergleicht. Die Auswertungskomponente 140 bestimmt, wie gut das Dokument 111 als eine Antwort für die Benutzerabfrage 10 dient. Die Bestimmung dieser Relevanz ist nicht auf einen Schlüsselwortvergleich oder boolesche Operationen beschränkt, sondern kann vielmehr den gesamten Inhalt von Dokumenten oder komplexen Teilen eines Dokuments berücksichtigen. Die Auswertungskomponente 140 muß jedoch erfindungsgemäß keine Dokumente der Datenbasis 110 in der Form ihrer natürlichen Sprache vergleichen, sondern vergleicht vielmehr die Darstellungsvektoren 144 der Dokumente.
Die Auswertungskomponente 140 besteht aus einem Dokumentenvektorisierer 141 und einer Vektorauswertungsvorrichtung 142. Wie nachfolgend ausführlicher be sprochen wird, stellt der Dokumentenvektorisierer 141 ein Mittel zur Vektorisierung von Dokumenten bereit. Ein Verfahren der Vektorisierung umfaßt zum Beispiel das Kodieren eines Dokuments zu einem Darstellungsvektor 144 unter Verwendung von Informationen aus der Lexikonkomponente 120. Die Vektorauswertungsvorrichtung 142 bestimmt die Relevanz eines Datenbasisdokuments 111 in bezug auf das Abfragedokument 10 durch Auswertung der Darstellungsvektoren 144 der entsprechenden Dokumente. Mit in der Vektorregelbasis 142 hinterlegten Regeln wertet die Vektorauswertungsvorrichtung 142 jedes Dokument 111 in der Datenbasis 110 im Vergleich mit den anderen Dokumenten in der Datenbasis 110 abhängig von der Beschaffenheit der Darstellungsvektoren 144 und dem Darstellungsvektor 144.1 des Abfragedokuments 10 (der auch als der Abfrage-Darstellungsvektor 144.1 bezeichnet wird) aus. Das Ergebnis dieses Vergleichs kann zum Beispiel eine Liste aller Dokumente der Datenbasis 110 sein, die je nachdem, wie gut sie die Kriterien der Abfrage 10 erfüllen, eingestuft werden. Die Ergebnisliste wird als das Resultat 20 bezeichnet.
Gemäß einer Ausführungsform erzeugt der Dokumentvektorisierer 141 einen n-dimensionalen Darstellungsvektor 144 für jedes Dokument, wobei n die Gesamtzahl von Wortstämmen 126 in der Lexikon-Datenbasis 122 ist. Die Lexikon-Datenbasis 122, bei der es sich zum Beispiel um eine alphabetisch sortierte Liste von Wortstämmen 126 handelt, führt für jeden Wortstamm 126 einen eindeutigen Index. Die Lexikon-Datenbasis 122 enthält gemäß einer Ausführungsform der vorliegenden Erfindung alle Wortstämme 126 aus jedem Dokument der Datenbasis 110 sowie aus dem Abfragedokument 10.
Der Dokumentvektorisierer 141 erzeugt einen Darstellungsvektor 144 eines Dokuments, indem zunächst ein n-dimensionaler Vektor gebildet wird, wobei jedes Vektorelement anfänglich auf null gesetzt wird. Das Dokument (aus der Datenbasis 110 oder dem Abfragedokument 10) wird verarbeitet, wobei für jedes Wort in dem Dokument der Wortstamm 126 abgeleitet und der Index des Wortstamms 126 aus der Lexikon-Datenbasis 122 abgerufen wird. Bestimmte Wörter oder Wortgruppen können als für die Indizierung ungeeignet erachtet werden, wie zum Beispiel Artikel oder Wörter wie "der", "für", "in" und dergleichen. Dies kann im voraus bestimmt und in die Stammbildungsregeln programmiert werden.
Jedesmal, wenn der Index eines Wortstamms 126 abgerufen wird, wird das Vektorelement für diesen Index erhöht. Nachdem das Dokument verarbeitet wurde, enthalten die Elemente des Darstellungsvektors 144 des Dokuments somit Informationen darüber, welche Wortstämme 126 in dem Dokument aufgetreten sind, und wie oft. Wenn die Lexikon-Datenbasis 122 zum Beispiel u. a. die Wortstämme "stift" am Index 15, "Bleistift" am Index 16, "Klammer" am Index 30 und "Baum" am Index 55 enthält, dann würde ein Dokument, das fünfmal das Wort "Stift", sechsmal das Wort "Bleistift", zweimal das Wort "Klammer" und keinmal das Wort "Baum" enthält, einen Darstellungsvektor aufweisen, dessen 15tes Element den Wert 5 (Häufigkeit von "Stift"), dessen 16tes Element den Wert 6 (Häufigkeit von "Bleistift"), dessen 30stes Element den Wert 2 (Häufigkeit von "Klammer") und dessen 55stes Element den Wert Null (Häufigkeit von "Baum") aufweist.
Statt für jedes Dokument einen mit Null initialisierter Darstellungsvektor 144 zu erzeugen, kann der Darstellungsvektor 144 bei einer alternativen Ausführungsform eine dynamisch erzeugte Verbundliste sein. Eine Verbundlistenstruktur kann dann wünschenswert sein, wenn die Wortschatz- oder Lexikon-Datenbasis 122 zum Beispiel eine große Zahl von Wortstämmen enthält (d. h. die Anzahl von Elementen n ist groß), die Größe der Dokumente 111, aus denen die Datenbasis besteht, in der Regel jedoch relativ klein ist. In einem solchen Fall kann in der Wortschatzdatenbasis 122 eine große Anzahl von Wortstämmen 126 vorliegen, die in keinem bestimmten Datenbasisdokument 111 erscheinen. Somit würde eine große Anzahl von Elementen des Darstellungsvektors 144 vorliegen, die Null enthalten. Durch Verwendung einer Verbundlistenstruktur könnte der Darstellungsvektor 144 nur solche Daten über Stammwörter 126 enthalten, die tatsächlich in dem Dokument enthalten sind. Zum Beispiel wird ein Stammwort 126 aus dem Dokument 111 abgeleitet, und sein entsprechender Index wird aus der Wortschatzdatenbasis 122 abgerufen. Der Darstellungsvektor 144 speichert den Index und einen Zähler für die Anzahl, wie oft das Stammwort 126 in dem Dokument 111 gefunden wurde. Dieses Paar von Index und Zähler wird direkt mit dem nächsten Paar von Index und Zähler verbunden, für das der indizierte Wortstamm 126 in dem Dokument 111 erscheint.
Die Dokumenten-Darstellungsvektoren 144 der Datenbasis 110 werden mit dem Darstellungsvektor 144.1 des Abfragedokuments 10 verglichen. Dieser Vergleich kann zum Beispiel die Bestimmung eines Relevanzwerts für jedes Dokument ergeben. Die Bereitstellung eines Relevanzwerts ist insofern praxisnah, als sie zweckmäßige Informationen liefert, die zu einem späteren Zeitpunkt zur Einstufung der Suchergebnisse verwendet werden können. Es gibt eine Anzahl bekannter Funktionen, die eine Auswertung bereitstellen können, wie zum Beispiel die Dice-Funktion, die Jacquard-Funktion oder die Cosinusmaß-Funktion.
Diese bekannten Funktionen führen Vektoroperationen aus und werden zur Berechnung der Darstellungsvektoren der Dokumente 111 verwendet. Zum Beispiel wird durch einen n-dimensionalen Vektor 144 ein Punkt in einem n-dimensionalen Vektorraum festgelegt. Die Consinusmaß-Funktion bestimmt den Cosinuswert eines Winkels, welcher von zwei Dokumenten-Darstellungsvektoren innerhalb des n-dimensionalen Vektorraums eingeschlossen wird. Für Cosinuswerte gleich 1 folgt, daß die Dokumente identisch sind. Ebenso gilt, daß je mehr die Cosinuswerte sich dem Wert 1 nähern, um so ähnlicher sind die betrachteten Dokumente. Alternativ zur Cosinusmaßfunktion eignen sich auch die Dice-Funktion und die Jacquard-Funktion als Maßfunktionen. Die Dice-Funktion und die Jacquard-Funktion sind aus dem Stand der Technik bekannt. Sie berechnen jeweils das Skalarprodukt zweier Darstellungsvektoren und eignen sich deshalb zur Bestimmung der Ähnlichkeit zweier Darstellungsvektoren, wobei das Skalarprodukt der Darstellungsvektoren unterschiedlicher aber zueinander identischer Dokumente den Zahlenwert 1 annimmt.
Diese Verfahren verwenden in der Regel jedoch nur die Werte in den Dokumenten-Darstellungsvektoren 144 der Dokumente zur Durchführung ihrer Auswertungen, aber keine anderen Informationen, die zum Vergleich der Dokumenten-Darstellungsvektoren 144 verwendet werden können. Mit der vorliegenden Erfindung können die Dokumente wesentlich genauer miteinander verglichen werden. Zum Beispiel verwendet die Auswertungskomponente 140 Beziehungen zwischen entsprechenden Vektorelementen der miteinander verglichenen Vektoren zur Berücksichtigung spezieller Bedingungen zwischen den beiden Vektordarstellungen. Zur Feststellung verschiedener Beiträge zu dem Relevanzwert können eine Anzahl spezieller Fälle verwendet werden. Zum Beispiel können zur Bestimmung von Relevanzwerten für Dokumente z. B. die folgenden Beziehungen verwendet werden:

(i) ein Wortstamm kommt in dem Abfragedokument nicht vor, und kommt auch nicht in einem Datenbasisdokument vor;
(ii) ein Wortstamm kommt nicht in dem Abfragedokument, aber in dem Datenbasisdokument vor;
(iii) ein Wortstamm kommt in dem Abfragedokument weniger häufig vor als in dem Datenbasisdokument;
(iv) ein Wortstamm kommt in dem Abfragedokument genauso oft vor wie in dem Datenbasisdokument;
(v) ein Wortstamm kommt in dem Abfragedokument häufiger vor als in dem Datenbasisdokument;
(vi) ein Wortstamm kommt in dem Abfragedokument vor, aber nicht in dem Datenbasisdokument.

Die Vektorauswertungsvorrichtung 142 kann Beziehungen wie diese zur Erstellung von Regeln in Vektorregelbasis 143 verwenden. Wenn die Bedingung oder Beziehung nicht erfüllt wird, dann kann ein Relevanzwert des Dokuments 111 entsprechend der Konsequenz oder der Ausgabe der Regelfolge korrigiert werden. Die Konsequenz der Regeln oder der Grad, zu dem der Relevanzwert durch eine Regel korrigiert wird, kann z. B. empirisch bestimmt werden. Wenn zum Beispiel ein Wortstamm 126 sowohl in dem Abfragedokument 10 als auch in dem Datenbasisdokument 110 häufig auftritt, dann könnte der diesem Datenbasisdokument 110 zugewiesene Relevanzwert um einen spezifizierten Betrag vergrößert werden. Wenn ein Wortstamm jedoch häufig in dem Abfragedokument 10, aber nur gelegentlich in dem Datenbasisdokument der Dokumentendatenbasis 110 vorkommt, dann wird der Relevanzwert um einen bestimmten kleineren Betrag vergrößert, da weniger Übereinstimmung zwischen den Dokumenten vorliegt. Wenn ein Wortstamm häufig in dem Abfragedokument, aber niemals in dem Datenbasisdokument vorkommt, dann könnte der Relevanzwert außerdem um einen bestimmten Betrag verkleinert werden.
Während des Auswertungsprozesses kann jedem Dokument auf der Grundlage, wie relevant das Dokument in bezug auf die Abfrage ist, ein Wert zugewiesen werden. Wenn eine Bedingung einer Regel erfüllt wird, dann kann der diesem Dokument zugewiesene Relevanzwert korrigiert werden. Nachdem alle Vektorelemente miteinander verglichen wurden, wird der resultierende Wert des Vergleichs als ein Maß dafür verwendet, wie relevant das Dokument 111 für das Abfragedokument 10 ist.
Als Alternative oder zusätzlich dazu werden einzelnen Wörtern in dem Dokument der Dokumentendatenbasis 110 Signifikanzwerte zur Bestimmung der Relevanz des ganzen Dokuments zugewiesen. Mittels einer Regel wird für eine Bedingung ein bestimmter quantifizierbarer Werts bereitgestellt. Wenn eine Bedingung durch ein bestimmtes Wort erfüllt wird, dann wird diesem Wort in diesem Dokument ein numerischer Wert zugewiesen. Wenn dieses Wort dann häufig vorkommt und einen hohen Relevanzwert aufweist oder zum Beispiel ein Wort mit hoher Identifizierungskraft ist, dann hat dieses eine größere Auswirkung bei der Zuweisung eines Gesamt-Relevanzwerts für das Dokument als Ganzes.
Die oben erwähnten bekannten Ansätze (z. B. Dice-, Jacquard- und Cosinusmaß-Funktionen) können zwischen speziellen Bedingungen oder Beziehungen wie den oben beschriebenen unterscheiden, wenn Vektorelemente verglichen werden. Die Fähigkeit der vorliegenden Erfindung, auf diesem Niveau zu differenzieren, ist in zweierlei Hinsicht wichtig. Erstens ist die Auswertungskomponente 140 gemäß der vorliegenden Erfindung flexibler und kann bei seiner Auswertung genauer sein, indem unter Verwendung vielfältiger Beziehungen oder Regeln wie den oben beschriebenen Unterscheidungen genauer getroffen werden. Zweitens verfügt die Auswertungskomponente 140 über mehr Parameter bei der Feinab stimmvorrichtung 130 zur Anpassung benutzerspezifischer Präferenzen in die Suchkriterien.
Der Auswertungsprozeß umfaßt die Verfahrensschritte zum Vergleich jedes Dokuments aus der Dokumentendatenbasis 110 mit dem Abfragedokument 10 und der Zuweisung eines Relevanzwerts gemäß der Vektorregelbasis 143. Das Resultat 20 dieses Auswertungsprozesses kann z. B. in einer Ergebnisliste eingestuft werden, die das Suchergebnis widerspiegelt. Das Resultat 20 kann zum Beispiel Dokumentnamen oder eine bestimmte andere Dokumentidentifikation enthalten, und zwar in der Reihenfolge gemäß den für jedes Dokument in der Datenbasis 110 bestimmten Relevanzwerten. Eine solche Liste wird dem Benutzer z. B. mittels des Ausgabegeräts vorgelegt oder zur interaktiven Anzeige des eigentlichen Texts der Dokumente, welche bei der Suche eingestuft wurden, auf einem Anzeigegerät, z. B. einem Bildschirmanzeigegerät, dargestellt.
Die Vektorauswertungsvorrichtung 142 und ihre Anwendung der Vektorregelbasis 143 bei der Bestimmung der Relevanz eines Dokuments für das Abfragedokument 10 kann nicht nur auf ganze Dokumente, sondern auch auf Teile von Dokumenten angewandt werden. Zum Beispiel kann ein Absatz eines Dokuments der Datenbasis 110 durch das beschriebene Vektorverfahren dargestellt werden. Dieser Darstellungsvektor 144 eines Teils eines Dokuments der Datenbasis 110 kann mit dem Darstellungsvektor 144.1 des Abfragedokuments 10 (oder einem Teil des Abfragedokuments 10) verglichen werden. Somit kann die Auswertung auf zwei Ebenen durchgeführt werden:

– erstens eine Bestimmung des relevantesten Dokuments (oder der besten n-Dokumente) und
– zweitens eine Bestimmung des relevantesten Teils eines Dokuments oder von Dokumenten. Es ist dadurch möglich, den Benutzer zu spezifischen Teilabschnitten eines Dokuments zu führen, die den Suchkriterien des Benutzers entsprechen.

In die Suchmaschine 100 können spezielle Parsingverfahren 123 integriert sein, die bestimmte Arten von Dokumenten erkennen, die Strukturen und Markierungen aufweisen können, wie zum Beispiel html- oder Latex-Format aufweisende Dokumente. Somit nutzt die Suchmaschine 100 die Textstruktur effizienter aus. Auf diese Weise können zur Aufteilung des Dokuments in auswertbare Abschnitte nicht nur Absätze, sondern auch Abschnitte, Unterabschnitte oder andere Unterteilungen und Markierungen in dem Text verwendet werden.
Wieder mit Bezug auf 1, kann die vorliegende Erfindung wie oben besprochen auch eine Feinabstimmvorrichtung 130 bereitstellen. Eine Feinabstimmvorrichtung 130 ermöglicht dem Benutzer, die Suchmaschine 100 fein und zielgenau einzustellen, um derartig das Resultat 20 der Suche zu beeinflussen. Wenn das Resultat 20 zum Beispiel eine eingestufte Liste der Dokumente 111 ist, kann der Benutzer die eingestufte Liste begutachten und eine Rückmeldung über die Qualität der Ergebnisse geben. Zum Beispiel kann die Ergebnisliste gemäß der Präferenzen des Benutzers umgeordnet und die umgeordnete Liste mittels des Eingabegeräts als Benutzereingabe 30 der Suchmaschine 100 bereitgestellt werden. Unter Verwendung dieser Benutzereingabe 30 modifiziert die Feinabstimmvorrichtung 130 die Regeln der Vektorregelbasis 143, so daß die eingestufte Liste des Resultats 20 entsprechend oder ähnlich wie das Benutzerfeedback 30 eingestuft wird.
Die Feinabstimmvorrichtung 130 kann zur Modifikation der Regeln der Vektorregelbasis 143 einen Evolutionsalgorithmus verwenden. Ein Evolutions-algorithmus passt die Regeln an, welche von der Auswertungskomponente 140 als komplexes stochastisches Suchproblem verwendet werden. Zum Beispiel kann der Benutzer eine Rückmeldung 30 eingeben, indem die Ausgangsdokumente neu eingestuft werden, wobei einem Dokument, in dem ein Wortstamm gelegentlich vorkommt, in dem ein zweiter Wortstamm jedoch nicht vorkommt, eine höhere Relevanz als dem Dokument gegeben wird, in dem beide Wortstämme vorkommen. Der Evolutionsalgorithmus kann einen solchen Faktor erkennen und die Vektorregelbasis 143 so korrigieren, daß die eingestufte Ausgabe dieselbe wie das Benutzerfeedback 30 ist. 5 zeigt ein Flußdiagramm eines beispielhaften Evolutionsalgorithmus. Man betrachte einen Prozeß, bei dem ein Benutzer eine Abfrage 10 eingegeben hat, die Suchmaschine 100 die Dokumente 111 auf der Grundlage einer bestimmten Vektorregelbasis 143 mit der Abfrage 10 verglichen hat und als Resultat 20 eine Rangliste erzeugt hat. Dem Benutzer wird als Feedback 30 eine neu eingestufte Liste bereitgestellt.

Ein Evolutionsalgorithmus zur Modifikation der Vektorregelbasis 143 zur Erzeugung eines Resultats 20, das mit dem Feedback 30 übereinstimmt, weist die folgenden Schritte auf:

Schritt 1	(Block 150): Erzeugen von mehreren Vektorregelbasen, die mit der anfänglichen Vektorregelbasis identisch sind. Eine vollständige Vektorregelbasis 143 wird als ein "Individuum" bezeichnet. Ein Individuum ist zum Beispiel eine geordnete Menge der Ausgangswerte aller Regeln.
Schritt 2	(Block 151): Verändern der zufälligen Ausgangswerte in jedem Individuum, um neue Individuen zu erzeugen.
Schritt 3	(Block 152): Verwenden der neuen Individuen in der Vektorauswertungsvorrichtung 142.
Schritt 4	(Block 153): Vergleichen der ausgegebenen Dokumentenliste jedes neuen Individuums mit dem Benutzerfeedback 30.
Schritt 5	(Block 154): Wenn die ausgegebene Dokumentenliste eines neuen Individuums zur gewünschten Liste führt, Beenden des Prozesses und Auswählen dieses Individuums als die neue Regelmenge für die Auswertungsvorrichtung. Andernfalls mit dem Schritt 6 fortfahren.
Schritt 6	(Block 155): Auswählen der Individuen, die zu Dokumentenlisten führten, die dem Benutzerfeedback 30 ähnlich sind, und Verwerfen der anderen Individuen.
Schritt 7	(Block 156): Erzeugen von neuen Individuen aus den im Schritt 6 ausgewählten Individuen. Zum Beispiel könnten u. a. die folgenden Ansätze verwendet werden: Option 1: Erzeugen neuer Individuen, indem Regeln der im Schritt 6 ausgewählten Individuen zufällig kombiniert werden. Option 2: Zufälliges Verändern bestimmter Ausgangswerte der im Schritt 6 ausgewählten Individuen.
Schritt 8	(Pfeil 158): Rückkehr zum Schritt 3.

Durch Implementierung eines solchen Evolutionsalgorithmus ermöglicht die Suchmaschine dem Benutzer, eine Feedbackeingabe 30 zu geben, mit dem die Suchmaschine die Vektorauswertungskriterien modifizieren kann, so daß die Präferenzen des Benutzers effektiver getroffen werden.
Die Suchmaschine 100 kann wie in 6 gezeigt auf einem Computersystem 160 implementiert werden. Eine Zentralverarbeitungseinheit 161 steuert den Suchmaschinenprozeß, darunter die Durchführung von Routinen, die z. B. in den Speicher 162 des Computers 160 geladen werden. Der Computer 160 enthält außerdem Arbeitsspeicher 163 und ist über ein Datennetz 164 mit einer Datenbasis oder Massenspeicherung 165 verbunden. Der Computer 160 weist ein Anzeigegerät 166 oder ein Ausgabegerät zur Bereitstellung von Ergebnissen für den Benutzer und eine Tastatur 167 oder ein anderes Eingabegerät 167 zur Eingabe von Anweisungen und Feedback durch den Benutzer. Zu den Routinen gehören diejenigen zur Durchführung der oben beschriebenen Operationen zum Suchen von Datenbasisdokumenten zu einer von einem Benutzer eingegebenen Abfrage.
Soweit die Erfindung betreffend die Suchmaschine 100 und ihrer einzelnen Komponenten beschrieben wird, insbesondere die Lexikonkomponente 120, die Auswertungskomponente 140 und die Feinabstimmvorrichtung 130, so kann die Suchmaschine 100 auch auf einer einzigen Rechenmaschine als ein gebündeltes nicht modulares Produkt implementiert werden, wobei die Funktionalitäten nicht diskret auf separate Komponenten verteilt sind. Als Alternative dazu kann die Funktionalität jeder Komponente über mehrere Hardwareteile verteilt werden, wobei verschiedene Komponenten und Unterkomponenten voneinander getrennt sind. Die Suchmaschine könnte auch als Kombination in diskreten Hardware- und diskreten Softwarekomponenten implementiert werden, je nachdem, wie es für die Implementierung der verschiedenen funktionalen Aspekte der Erfindung vorteilhaft ist.
Die Erfindung ist nicht auf die hier beschriebenen spezifischen Ausführungsformen beschränkt, sondern soll auch andere Ausführungsformen mit einschließen. Zum Beispiel können die besprochenen verschiedenen Komponenten und Unterkomponenten in ein einziges Modul implementiert werden oder können sogar weiter in verschiedene Bestandteile unterteilt werden, wobei jeder Bestandteil separat von den anderen Bestandteilen erzeugt wird. Die Funktionalität kann durch verschieden gekennzeichnete Komponenten durchgeführt werden. Zum Beispiel bearbeitet der Lexikongenerator 121 (siehe 3) die Dokumente 111 gemäß einer Ausführungsform der Erfindung im Parsing- und Stammbildungs-Verfahren. Der Vektorisierer 141 (eine Komponente der Auswertungskomponente 140) vektorisiert die Dokumente 111. Die Erfindung umfaßt z. B. eine funktionale Komponente, die die Dokumente 111 im Parsing- und Stammbildungs-Verfahren bearbeitet und vektorisiert, anstatt diese Schritte durch einzelne Komponenten durchführen zu lassen.

Claims

Suchmaschine (100) zum Abrufen von Informationen aus Dokumenten einer Datenbasis (110) auf der Grundlage einer Abfrage (10) eines Benutzers, wobei die Suchmaschine (100) folgendes umfaßt: einen Lexikongenerator zur Erstellung einer Wortschatz- und/oder Lexikondatenbasis (122) von Wortstämmen aus der Datenbasis (110) und aus der Abfrage (10); und eine Auswertungskomponente (140), wobei die Auswertungskomponente (140) einen Dokumentenvektorisierer (141) zur Erzeugung von Dokumenten-Darstellungsvektoren für entsprechende Dokumente der Datenbasis (110) und einen Abfrage-Darstellungsvektor für die Abfrage (10) unter Verwendung der Wortschatz- und/oder Lexikondatenbasis (122) enthält, wobei die Dokumenten-Darstellungsvektoren Daten bezüglich der in den entsprechenden Dokumenten (110) enthaltenen Wortstämme enthalten und der Abfrage-Darstellungsvektor Daten bezüglich der in der Abfrage (10) enthaltenen Wortstämme enthält, wobei die Auswertungskomponente (140) weiterhin eine Vektorregelbasis (142) und eine Vektorauswertungsvorrichtung (143) enthält, wobei die Vektorauswertungsvorrichtung (143) die Dokumenten-Darstellungsvektoren auf der Grundlage der Vektorregelbasis (142) mit dem Abfrage-Darstellungsvektor vergleicht, wobei die Auswertungskomponente die Informationen aus der Datenbasis auf der Grundlage der Abfrage (10) erzeugt.
Suchmaschine (100) nach Anspruch 1, wobei es sich bei den durch die Auswertungskomponente (140) der Suchmaschine (100) erzeugten Informationen um eine Liste mindestens mancher der Dokumente handelt, die gemäß der Relevanz der Dokumente für das Abfragedokument (10) eingestuft werden.
Suchmaschine (100) nach Anspruch 1, wobei die Wortschatz- und/oder Lexikondatenbasis (122) von Wortstämmen einen Index enthält, der jedem der Wort stämme entspricht, und die Dokumenten-Darstellungsvektoren mindestens einen Zähler für jeden Index jedes der Wortstämme umfassen, wobei ein Wert des Zählers angibt, wie oft der Wortstamm, der dem Index entspricht, in den entsprechenden Dokumenten der Datenbasis auftritt.
Suchmaschine (100) nach Anspruch 1, wobei die Wortschatz- und/oder Lexikondatenbasis (122) von Wortstämmen einen Index enthält, der jedem der Wortstämme entspricht, und der Abfrage-Darstellungsvektor mindestens einen Zähler für jeden Index jedes der Wortstämme umfaßt, wobei ein Wert des Zählers angibt, wie oft der Wortstamm, der dem Index entspricht, in der Abfrage vorkommt.
Suchmaschine (100) nach Anspruch 1, wobei die Vektorauswertungsvorrichtung (143) die Dokumenten-Darstellungsvektoren mit dem Abfrage-Darstellungsvektor vergleicht, indem dem Dokumenten-Darstellungsvektor auf der Grundlage von in der Vektorregelbasis (142) angegebenen Bedingungen ein Relevanzwert zugewiesen wird.
Suchmaschine (100) nach Anspruch 1, wobei die Vektorregelbasis (142) Regeln enthält, die die Datenbasisdokumente teilweise auf der Grundlage mit der Abfrage (10) vergleicht, ob bestimmte oder alle oder eine Kombination von Bedingungen erfüllt werden, wobei zu den Bedingungen mindestens eine der folgenden gehören: (i) ein Wortstamm kommt nicht in dem Abfragedokument (10) vor und kommt auch in einem Datenbasisdokument nicht vor; (ii) ein Wortstamm kommt nicht in der Abfrage (10) vor, kommt aber in dem Datenbasisdokument vor; (iii) ein Wortstamm kommt in der Abfrage (10) weniger häufig als in dem Datenbasisdokument vor; (iv) ein Wortstamm kommt in der Abfrage (10) und genauso oft in dem Datenbasisdokument vor; (v) ein Wortstamm kommt in der Abfrage (10) häufiger als in dem Datenbasisdokument vor; und (vi) ein Wortstamm kommt in der Abfrage (10) vor, kommt aber nicht in dem Datenbasisdokument vor.
Suchmaschine (100) nach Anspruch 1, wobei die Wortschatz- und/oder Lexikondatenbasis (122) Wortstammhäufigkeitsdaten enthält, die mit der Häufigkeit des Wortstamms in den Dokumenten der Datenbasis (110) zusammenhängen.
Suchmaschine (100) nach Anspruch 1, wobei die Wortschatz- und/oder Lexikondatenbasis (122) entsprechend jedem Wortstamm einen Signifikanzwert enthält.
Suchmaschine (100) nach Anspruch 1, weiterhin mit einer Feinabstimmvorrichtung (130), wobei die Feinabstimmvorrichtung (130) die Vektorregelbasis (142) auf der Grundlage von externer Benutzerrückmeldung (30) modifiziert.
Suchmaschine (100) nach Anspruch 9, wobei das Feedback (30) eine vom Benutzer eingestufte Liste von Dokumenten umfaßt.
Suchmaschine (100) nach Anspruch 9, wobei die Vektorregelbasis (142) mindestens eine Bedingung enthält, die einen Ausgabewert auf der Grundlage bereitstellt, ob mindestens eine Bedingung durch einen Dokumenten-Darstellungsvektor erfüllt wird, und wobei die Feinabstimmvorrichtung (130) die Vektorregelbasis (142) durch zufälliges Verändern des Ausgangswerts der mindestens einen Bedingung modifiziert.
Verfahren zum Abrufen von Dokumenten aus einer Datenbasis entsprechend einem Abfragedokument (10), wobei das Verfahren folgende Schritte umfaßt: Ableiten einer Wortschatz- und/oder Lexikondatenbasis von Wortstämmen aus jedem Dokument der Datenbasis und dem Abfragedokument; Erzeugen eines Dokumenten-Darstellungsvektors entsprechend jedem Dokument der Datenbasis und eines Abfrage-Darstellungsvektors für das Abfragedokument (10), wobei jeder Dokumenten-Darstellungsvektor Informationen über Wortstämme der Wortschatz- und/oder Lexikondatenbasis enthält, die in dem Dokument enthalten sind, dem der Dokumenten-Darstellungsvektor entspricht, wobei der Abfrage-Darstellungsvektor Informationen über die Wortstämme enthält, die in dem Abfragedokument enthalten sind; Auswerten jedes Dokumenten-Darstellungsvektors relativ zu dem Abfrage- Darstellungsvektor mit Vektor-Auswertungsregeln; Erzeugen einer Ausgabe, die die Auswertung der Dokumenten-Darstellungsvektoren widerspiegelt; und Anzeigen der Ausgabe.
Verfahren nach Anspruch 12, weiterhin mit den folgenden Schritten: Empfangen von Feedback (30), das Präferenzen für die Ausgabe angibt, und Modifizieren der Vektorauswertungsregeln auf der Grundlage des Feedbacks (30), so daß die Ausgabe die in dem Feedback gegebenen Präferenzen besser widerspiegelt.
Verfahren nach Anspruch 12, wobei der Schritt des Erzeugens des Dokumenten-Darstellungsvektors, der jedem Dokument der Datenbasis entspricht, die folgenden Schritte aufweist: Erzeugen eines n-dimensionalen Darstellungsvektors, wobei jedes Element des Darstellungsvektors auf Null initialisiert wird, wobei n die Anzahl von in der Wortschatz- und/oder Lexikondatenbasis enthaltenen Wortstämmen ist; Ableiten des Wortstamms für jedes Wort in dem Dokument; Abrufen des Index des Wortstamms aus der Wortschatz- und/oder Lexikondatenbasis; und Inkrementieren des am Index des Darstellungsvektors gespeicherten Elements, jedesmal, wenn der Index eines Wortstamms abgerufen wird.
Verfahren nach Anspruch 12, wobei der Schritt des Ableitens einer Wortschatz- und/oder Lexikondatenbasis von Wortstämmen aus jedem Dokument der Datenbasis und des Abfragedokuments die folgenden Schritte aufweist: Parsen jedes Dokuments zu einer Liste von Wörtern; Ableiten von Wortstämmen aus den Wörtern durch Vergleichen von Wörtern mit ähnlichen Anfangs-Buchstabenfolgen, aber unterschiedlichen Endungs-Buchstabenfolgen; und Speichern jedes der Wortstämme in der Wortschatz- und/oder Lexikondatenbasis.
Verfahren nach Anspruch 15, wobei der Schritt des Ableitens von Wortstäm men folgende Schritte aufweist: Setzen einer minimalen Wortlänge; Setzen eins Ähnlichkeitsschwellenwerts; Bestimmen, welche Wörter für die minimale Wortlänge übereinstimmende Buchstaben aufweisen und sich längenmäßig um nicht mehr als den Ähnlichkeitsschwellenwert unterscheiden; und Wählen des kürzeren der Wörter als Wortstamm.
Verfahren nach Anspruch 15, wobei der Schritt des Ableitens von Wortstämmen die folgenden Schritte aufweist: Setzen einer minimalen Wortlänge; Setzen eines Ähnlichkeitsschwellenwerts; Bestimmen, welche Wörter für die minimale Wortlänge übereinstimmende Buchstaben aufweisen und sich längenmäßig um nicht mehr als den Ähnlichkeitsschwellenwert unterscheiden; und Auswählen der übereinstimmenden Buchstaben als Wortstamm.
Verfahren nach Anspruch 15, wobei der Schritt des Ableitens von Wortstämmen die folgenden Schritte aufweist: Setzen einer minimalen Wortlänge; Setzen eines Ähnlichkeitsschwellenwerts; Bestimmen, wann Wörter gleicher Länge für mindestens die minimale Wortlänge übereinstimmende Buchstaben aufweisen und für die letzten Buchstaben, die kleiner oder gleich dem Ähnlichkeitsschwellenwert sind, ungleich sind; und Wählen des Worts ohne den ungleichen Teil als Wortstamm.
Verfahren nach Anspruch 12, wobei der Schritt des Auswertens jedes Dokumenten-Darstellungsvektors relativ zu dem Abfrage-Darstellungsvektor die folgenden Schritte aufweist: Zuweisen eines Relevanzwerts zu jedem Dokumenten-Darstellungsvektor auf der Grundlage, ob Bedingungen erfüllt werden, wobei zu den Bedingungen mindestens eine der folgenden gehört: (i) ein Wortstamm kommt nicht in dem Abfrage-Darstellungsvektor vor und kommt auch in dem Dokumenten-Darstellungsvektor nicht vor; (ii) ein Wortstamm kommt nicht in dem Abfrage-Darstellungsvektor vor, kommt aber in dem Dokumenten-Darstellungsvektor vor; (iii) ein Wortstamm kommt in dem Abfrage-Darstellungsvektor weniger häufig als in dem Dokumenten-Darstellungsvektor vor; (iv) ein Wortstamm kommt in dem Abfrage-Darstellungsvektor und genauso oft in dem Dokumenten-Darstellungsvektor vor; (v) ein Wortstamm kommt in dem Abfrage-Darstellungsvektor häufiger als in dem Dokumenten-Darstellungsvektor vor; und (vi) ein Wortstamm kommt in dem Abfrage-Darstellungsvektor vor, kommt aber nicht in dem Dokumenten-Darstellungsvektor vor.
Verfahren nach Anspruch 12, weiterhin mit den folgenden Schritten: Zuweisen eines Signifikanzwerts zu mindestens einem der Wortstämme der Wortschatz- und/oder Lexikondatenbasis und Verwenden des Signifikanzwerts zur Beeinflussung der Auswertung von Dokumenten-Darstellungsvektoren, die den mindestens einen Wortstamm enthalten.
Suchmaschine (100) nach Anspruch 1, wobei der Lexikongenerator zur Erstellung einer Wortschatz- und/oder Lexikondatenbasis weiterhin ein Mittel zum Parsen der Dokumente zu einer Liste von Wörtern und ein Mittel zum Ableiten von Wortstämmen aus der Liste von Wörtern durch Vergleichen einer vorgegebenen Anzahl von Buchstaben in den Wörtern aus der Liste von Wörtern mit anderen Wörtern aus der Liste von Wörtern, wobei jedoch eine Nichtübereinstimmung anderer Buchstaben aus den Wörtern zugelassen wird, enthält.
Computerlesbares Medium mit mehreren darauf gespeicherten Anweisungen, wobei diese Anweisungen solche Anweisungen umfassen, die bei der Ausführung durch einen Prozessor bewirken, daß der Prozessor die folgenden Schritte entsprechend dem Verfahren nach Patentanspruch 12 durchführt: Ableiten einer Wortschatz- und/oder Lexikondatenbasis von Wortstämmen aus Dokumenten einer Datenbasis und einem Abfragedokument; Erzeugen eines Darstellungsvektors, der jedem der Dokumente der Datenbasis entspricht, wobei jeder Darstellungsvektor Informationen über Wortstämme der Wortschatz- und/oder Lexikondatenbasis enthält, die in dem Dokument der Datenbasis enthalten sind, dem der Darstellungsvektor entspricht; Erzeugen eines Abfrage-Darstellungsvektors, der dem Abfrage-Dokument entspricht, wobei der Abfrage-Darstellungsvektor Informationen über die Wortstämme enthält, die in dem Abfrage-Dokument enthalten sind; Auswertung jedes Darstellungsvektors relativ zu dem Abfrage-Darstellungsvektor mit Vektorauswertungsregeln zur Bildung einer Auswertung der Darstellungsvektoren; Erzeugen einer Ausgabe, die die Auswertung der Darstellungsvektoren widerspiegelt; und Anzeigen der Ausgabe.
Computerlesbares Medium nach Anspruch 22, wobei die Anweisungen bei der Ausführung durch den besagen Prozessor bewirken, daß der besagte Prozessor die folgenden weiteren Schritte ausführt: Empfangen von mindestens einer Rückmeldung zur Auswahl von Präferenzen für die Ausgabe, und Modifizieren der Vektorauswertungsregeln auf der Grundlage der Rückmeldung, so daß die Ausgabe die in der Rückmeldung angegebenen Präferenzen besser widerspiegelt.
Computerlesbares Medium nach Anspruch 22, wobei der Schritt des Erzeugens eines Darstellungsvektors entsprechend jedem Dokument der Datenbasis weiterhin folgende Schritte aufweist: Erzeugen eines n-dimensionalen Darstellungsvektors mit n Elementen, wobei jedes Element des Darstellungsvektors auf Null initialisiert wird, wobei n die Anzahl von Wortstämmen in der Wortschatz- und/oder Lexikondatenbasis ist; Ableiten des Wortstamms für jedes Wort in dem Dokument; Abrufen eines dem Wortstamm entsprechenden Index aus der Wortschatz- und/oder Lexikondatenbasis; Inkrementieren des am Index des Darstellungsvektors gespeicherten Elements, jedesmal wenn der Index abgerufen wird.