Local File Search Engine
1.0.0
Dies ist eine grundlegende Implementierung einer auf Python basierenden Dateisuchmaschine zur Beantwortung von Abfragen in Textdateien auf einem lokalen System. Wir haben „tf-idf-Termgewichtung“ und „Kosinusähnlichkeit“ verwendet, um die Relevanz der übereinstimmenden Dokumente einzustufen. TF-IDF-Berechnungen werden vorberechnet, was die Suche erheblich beschleunigt. Um die Suche zu beschleunigen, wurde auch Stemming (Porter Stemmer) verwendet. Es wird eine grundlegende Benutzeroberfläche bereitgestellt, die die Tkinter-Bibliothek von Python verwendet.
python2 createIndex_tfidf.py stopwords.dat testIndex.dat titleIndex.dat
createIndex_tfidf.py wird nur einmal ausgeführt, um die tdf-idf-Werte für den Korpus zu berechnen
python2 queryIndex_tfidf.py stopwords.dat testIndex.dat titleIndex.dat
Insgesamt werden in diesem Schritt drei verschiedene Dateien erstellt:
titleIndex.dat
In dieser Datei wird die eindeutige docId (Dokument-ID) gespeichert, die jedem Dokument im Korpus zugewiesen ist.
testIndex.dat
Dabei wird eine Indexdatei erstellt (auch als invertierte Indexdatenstruktur bezeichnet), die Informationen zu allen eindeutigen Begriffen (außer Stoppwörtern) enthält, die in allen Dokumenten vorkommen. Jedes Dokument erhält eine eindeutige ID, die bei 0 beginnt und im TitelIndex gespeichert ist. dat. Die Informationen zu einem Begriff werden wie folgt in der Indexdatei gespeichert: term|docID0:pos1,pos2;docID1:pos3,pos4,pos5;…..|tf0,tf1,tf2...|idf Hier tf0,tf1,tf2 stellt die Begriffshäufigkeit des Begriffs in docID0, docID1 bzw. docID2 dar. idf stellt die inverse Dokumenthäufigkeit dar und pos1 stellt die Position des Begriffs im jeweiligen Dokument dar und so weiter.
Linien.dat
In dieser Datei werden Informationen über die Zeilen gespeichert, in denen der Begriff in verschiedenen Dokumenten vorkommt. Diese Zeileninformationen werden wie folgt dargestellt: term|docID0:line1,line2;docID1:line3,line4,line5
Vor der Erstellung dieser Dateien werden alle Begriffe der Dokumente in der Stoppwortliste überprüft. Wenn ein Begriff in Stoppwörtern vorkommt, wird er übersprungen, andernfalls werden seine Informationen in diesen oben genannten Dateien gespeichert. Außerdem wird jeder Begriff von Porter Stemmer entstammt, bevor er dem Index hinzugefügt wird.
Dabei werden zunächst alle Informationen aus den Dateienlines.dat,titleIndex.dat und testIndex.dat noch einmal mithilfe eines Wörterbuchs in Python zurückgespeichert.
Nun werden folgende verschiedene Arten von Abfragen unterstützt:
Ein-Wort-Abfragen (OWQ) Hierbei handelt es sich um eine Einzelbegriffsabfrage. Die Ausgabe ist eine Liste von Dokumenten, die den gesuchten Begriff enthalten, zusammen mit den Zeilennummern, in denen der Begriff im jeweiligen Dokument vorkommt.
Mehrwortabfragen (MWQ) Die Eingabe in MWQ ist eine Folge von Wörtern und die Ausgabe ist die Liste der Dokumente, die einen der Abfragebegriffe zusammen mit den Zeilennummern enthalten.
Phrasenabfragen (PQ) Die Eingabe in PQ ist wiederum eine Folge von Wörtern, und die passenden Dokumente sind diejenigen, die alle Abfragebegriffe in der angegebenen Reihenfolge enthalten.
Nachdem wir nun die Liste der Dokumente gefunden haben, in denen die Abfrage vorhanden ist, ist es an der Zeit, sie in eine Rangfolge zu bringen. Das hier verwendete Ranking-Schema basiert auf tf-idf. Tf-Idf ist ein Gewichtungsschema, das jedem Begriff in einem Dokument eine Gewichtung zuweist, die auf seiner Begriffshäufigkeit (tf) und der inversen Dokumenthäufigkeit (idf) basiert. Die Begriffe mit höheren Gewichtungswerten werden als wichtiger angesehen. Es ist eines der beliebtesten Gewichtungsschemata beim Information Retrieval.
Die Termhäufigkeit (tf) eines Termes ist dokumentspezifisch. Dabei handelt es sich im Wesentlichen um die Häufigkeit des Vorkommens des Begriffs t im Dokument D. Es ist ziemlich logisch, tf als Parameter zu wählen, da ein Begriff umso wichtiger wird, je häufiger er im Dokument vorkommt. Wir können ein Dokument durch einen Vektor darstellen, dessen Größe gleich der Nummer ist. Anzahl eindeutiger Begriffe im Dokument und jeder Wert gibt die Anzahl des Begriffs im angegebenen Dokument an. Die Darstellung von Dokumenten als Vektoren in einem gemeinsamen Vektorraum wird als Vektorraummodell bezeichnet und ist für die Informationsbeschaffung von grundlegender Bedeutung. Aber hier gibt es einen Nachteil. Mit zunehmender Größe des Dokuments nimmt das Gewicht von tf zu, da die Häufigkeit der Begriffe zunimmt. Daher wird ein Dokument, das dieselben Informationen enthält wie ein anderes Dokument und mehr als einmal kopiert wurde, als wichtiger angesehen. Um diesen Nachteil zu beseitigen, dividieren wir jeden Wert in einem Vektor durch seine Norm, sodass der Vektor ein Einheitsvektor wird.
Wir können die Gewichtung eines Begriffs im Dokument nicht nur anhand der Begriffshäufigkeiten berechnen, da tf alle Begriffe als gleich wichtig ansieht. Einige Begriffe kommen jedoch seltener vor und sind diskriminierender als andere. Wenn wir tf lediglich als Maß für die Rangfolge verwenden und nach einem Thema wie Schallwellen suchen, erhalten wir möglicherweise viele Dokumente, die Lichtwellen und andere Wellen enthalten, da die Häufigkeit des Begriffs der einzige Parameter ist.
Um diesen Effekt abzuschwächen, verwenden wir die umgekehrte Dokumenthäufigkeit. Die Dokumenthäufigkeit eines Begriffs ist im Wesentlichen die Anzahl der Dokumente, die den Begriff enthalten. Die inverse Dokumenthäufigkeit (idf) eines Begriffs ist also die Anzahl der Dokumente im Korpus geteilt durch die Dokumenthäufigkeit eines Begriffs. Im Allgemeinen wurde festgestellt, dass der Faktor von idf ziemlich groß ist und bessere Ergebnisse erzielt werden, wenn wir log(idf) verwenden. Da es sich bei log um eine zunehmende Funktion handelt, können wir sie verwenden, ohne unsere Ergebnisse zu beeinträchtigen.
Wir haben sowohl tf als auch idf definiert und können diese nun kombinieren, um die endgültige Bewertung eines Begriffs t in Dokument d zu ermitteln. Wir werden das Dokument erneut als Vektor darstellen, wobei jeder Eintrag das tf-idf-Gewicht des entsprechenden Begriffs im Dokument darstellt. Das tf-idf-Gewicht eines Begriffs t in Dokument d ist einfach die Multiplikation seines tf mit seinem idf.
Jetzt haben wir die Vektoren jedes Dokuments basierend auf der TF-IDF-Gewichtung erstellt. Es ist an der Zeit, eine Anfrage mit den angegebenen Dokumentvektoren zu beantworten. Zunächst erstellen wir einen Abfragevektor selbst auf einer ähnlichen Basis wie den Dokumentvektor, dh basierend auf dem TF-IDF-Score (unter Berücksichtigung der Abfrage eines Dokuments selbst). Da wir nun unseren Abfragevektor bereit haben, werden wir alle Dokumente finden, in denen unsere Abfrage vorhanden ist. Jetzt nehmen wir das Skalarprodukt des Abfragevektors und des Dokumentvektors, in dem die Abfrage vorhanden ist. Je höher das Skalarprodukt ist, desto ähnlicher ist der Abfragevektor mit dem Dokumentvektor, was bedeutet, dass der Winkel zwischen dem Dokumentvektor und dem Abfragevektor kleiner ist. Diese Technik zum Finden der Ähnlichkeit zwischen Abfrage und Dokument wird Kosinusähnlichkeit genannt.
