Boolesche Modell des Informationsabrufs

Der Standard) Boolesche Modell des Informationsabrufs (BIR)[1] ist eine klassische Informationsrückgewinnung (IR) Modell und gleichzeitig das erste und meistverteidigte. Es wird von vielen IR -Systemen bis heute verwendet. Der Bir basiert auf Boolesche Logik und klassisch Mengenlehre Da beide Dokumente gesucht werden und die Abfrage des Benutzers als Begriffssätze konzipiert werden (a Modell der Wörter). Das Abrufen basiert darauf, ob die Dokumente die Abfragebegriffe enthalten oder nicht.

Definitionen

Ein Indexbegriff ist ein Wort oder Ausdruck, die sein kann stamm, Beschreibung oder Charakterisierung eines Dokuments, z. B. ein Schlüsselwort für einen Journal -Artikel. Lassen

Seien Sie der Satz aller derartigen Indexbegriffe.

A dokumentieren ist jede Teilmenge von . Lassen

Seien Sie die Menge aller Dokumente.

A Anfrage ist ein boolescher Ausdruck in normaler Form:

wo gilt für Wenn . (Äquivalent, könnte ausgedrückt werden in disjunktive normale Form.))

Wir versuchen, die Set von Dokumenten zu finden, die befriedigt werden . Diese Operation heißt Abruf und besteht aus den folgenden zwei Schritten:

1. Für jeden in Finden Sie das Set von Dokumenten, die befriedigen :
2. Dann wird die Menge der Dokumente, die Q erfüllen, angegeben von:

Beispiel

Lassen Sie beispielsweise die Menge der ursprünglichen (realen) Dokumente sein

wo

= "Bayes 'Prinzip: Das Prinzip, das bei der Schätzung eines Parameters zunächst annehmen sollte, dass jeder mögliche Wert eine gleiche Wahrscheinlichkeit hat (eine gleichmäßige vorherige Verteilung)."

= "Bayesianische Entscheidungstheorie: Eine mathematische Theorie der Entscheidungsfindung, die Nützlichkeits- und Wahrscheinlichkeitsfunktionen vermutet, und nach der die ausgewählte Handlung das Bayes-Gesetz ist, d. H. Der mit dem höchsten subjektiv erwarteten Nutzen. Wenn man unbegrenzte Zeit und Berechnungskraft hätte, um jede Entscheidung zu treffen, wäre dieses Verfahren der beste Weg, um eine Entscheidung zu treffen. "

= "Bayesian Erkenntnistheorie: Eine philosophische Theorie, die besagt, dass der epistemische Status eines Satzes (d. H. Wie gut bewährt oder gut etabliert ist) am besten an der Wahrscheinlichkeit gemessen wird und dass die richtige Möglichkeit, diese Wahrscheinlichkeit zu überarbeiten, durch Bayes'sche Bedingung oder ähnliche Verfahren angegeben wird. Ein Bayesian -Epistemologe würde die Wahrscheinlichkeit verwenden, um die Beziehung zwischen Konzepten wie epistemischer Status, Unterstützung oder erklärender Macht zu definieren und zu untersuchen. "

Lassen Sie das Set von Begriffen sein:

Dann der Satz von Dokumenten ist wie folgt:

wo

Lassen Sie die Abfrage sein:

Dann um die entsprechenden Dokumente abzurufen:
  1. Erstens die folgenden Sätze und von Dokumenten werden erhalten (abgerufen):
  2. Schließlich die folgenden Dokumente werden als Reaktion auf abgerufen

Dies bedeutet, dass das Originaldokument (korrespondierend zu ) ist die Antwort auf .

Wenn es mehr als ein Dokument mit derselben Darstellung gibt, wird jedes solche Dokument abgerufen. Solche Dokumente sind in der BIR (mit anderen Worten, gleichwertig) nicht zu unterscheiden.

Vorteile

  • Sauberer Formalismus
  • Leicht zu implementieren
  • Intuitiver Konzept
  • Wenn das resultierende Dokumentsatz entweder zu klein oder zu groß ist, ist direkt klar, welche Betreiber jeweils einen größeren oder kleineren Satz produzieren.
  • Es gibt (Experten-) Benutzer ein Gefühl der Kontrolle über das System. Es ist sofort klar, warum ein Dokument bei einer Frage abgerufen wurde.

Nachteile

  • Genaue Übereinstimmung kann zu wenige oder zu viele Dokumente abrufen
  • Es ist schwer, eine Abfrage in einen booleschen Ausdruck zu übersetzen
  • Alle Begriffe sind gleich gewichtet
  • Eher wie Datenabruf als Informationsrückgewinnung
  • Abrufen auf der Grundlage von Binärentscheidungskriterien ohne Begriff der teilweisen Übereinstimmung
  • Es wird keine Rangfolge der Dokumente bereitgestellt (Abwesenheit einer Bewertungsskala)
  • Der Informationsbedarf muss in einen booleschen Ausdruck übersetzt werden, den die meisten Benutzer als unangenehm empfinden
  • Die von den Benutzern formulierten Booleschen Abfragen sind am häufigsten zu simpel
  • Das Modell gibt häufig entweder zu wenige oder zu viele Dokumente als Antwort auf eine Benutzerabfrage zurück

Datenstrukturen und Algorithmen

Aus reiner formaler mathematischer Sicht ist der BIR unkompliziert. Aus praktischer Sicht sollten jedoch mehrere weitere Probleme gelöst werden, die sich auf Algorithmen und Datenstrukturen beziehen, z. B. beispielsweise die Auswahl der Begriffe (manuelle oder automatische Auswahl oder beides). Stamm, Hash -Tische, inverted Datei Struktur und so weiter.[2]

Hash -Sets

Eine andere Möglichkeit besteht darin, Hash -Sets zu verwenden. Jedes Dokument wird durch eine Hash -Tabelle dargestellt, die jede einzelne Begriff dieses Dokuments enthält. Da die Hash -Tabellengröße in Echtzeit mit Addition und Entfernung von Begriffen zunimmt und abnimmt, belegt jedes Dokument viel weniger Speicherplatz. Es wird jedoch eine Leistungsabwehr verzeichnen, da die Vorgänge komplexer sind als mit Bitvektoren. Über die schlimmste Leistung kann sich von O (on) zu(n2). Im Durchschnitt wird die Leistungsverschwendung nicht so viel schlimmer sein als Bitvektoren und die Raumnutzung ist viel effizienter.

Signaturdatei

Jedes Dokument kann von zusammengefasst werden durch Blütefilter Darstellung der Wörtermenge in diesem Dokument, die in einer Bitstring mit fester Länge gespeichert ist und als Signatur bezeichnet wird. Die Signaturdatei enthält eine solche überlagerter Code Bitstring für jedes Dokument in der Sammlung. Jede Abfrage kann auch von a zusammengefasst werden Blütefilter Darstellung der Wörter in der Abfrage, die in einer Bitstrierung derselben festen Länge gespeichert ist. Die Abfragebitstring wird gegen jede Signatur getestet.[3][4][5]

Die angegangene Signaturdatei wird in verwendet Bitfunnel.

Inverted Datei

Eine umgekehrte Indexdatei enthält zwei Teile: ein Vokabular, das alle in der Sammlung verwendeten Begriffe enthält, und für jeden bestimmten Begriff ein invertiertes Index, in dem jedes Dokument aufgeführt ist, in dem dieser Begriff erwähnt wird.[3][4]

Verweise

  1. ^ Lancaster, F.W.; Fayen, z. (1973), Informationsabruf online, Melville Publishing Co., Los Angeles, Kalifornien
  2. ^ Wartik, Steven (1992). "Boolesche Operationen". Datenstrukturen und Algorithmen zum Abrufen von Informationsabrechnungen. Prentice-Hall, Inc. ISBN 0-13-463837-9. Archiviert von das Original 2013-09-28.
  3. ^ a b Justin Zobel; Alistair Moffat; und Kotagiri Ramamohanarao."Invertierte Dateien gegen Signaturdateien für die Textindexierung".
  4. ^ a b Bob Goodwin; et al."Bitfunnel: Überprüfung von Unterschriften für die Suche". 2017.
  5. ^ Richard Startin."Bitspelzsignaturen und Blütenfilter".
  • Lashkari, A.H.; Mahdavi, F.; Ghomi, V. (2009), "Ein Boolean -Modell für Informationsabruf für Suchmaschinen", Internationale Konferenz für Informationsmanagement und Ingenieurwesen 2009 2009, S. 385–389, doi:10.1109/icime.2009.101, ISBN 978-0-7695-3595-1