Wie man einen einfachen invertierten index?

Ich möchte erstellen Sie eine einfache Funktion Indizierung der Suchmaschine, ohne API, wie Lucene. In den invertierten index, brauche ich nur zu erfassen, grundlegende Informationen zu jedem Wort, z.B. docID, position und freqence.

Nun, ich habe mehrere Fragen:

  1. Welche Art von Daten Struktur wird Häufig für den Aufbau invertierter index? Mehrdimensionale Liste?

  2. Nach Aufbau des index, wie es zu schreiben in Dateien? Welche Art von format in der Datei? Wie eine Tabelle? Wie beim index-Tabelle auf Papier?

InformationsquelleAutor der Frage Munichong | 2012-09-20

  1. 31

    Sehen Sie eine sehr einfache Implementierung eines invertierten index und Suche in TinySearchEngine.

    Für Ihre erste Frage, wenn Sie wollen, bauen Sie ein einfaches (Speicher) invertierten index die einfache Datenstruktur ist eine Hash-Tabelle wie diese:

    val invertedIndex = new collection.mutable.HashMap[String, List[Posting]]

    oder ein Java-esque:

    HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>();

    Den Hashwert ordnet jedem Begriff/Wort/token eine Liste von Postings. Ein Posting nur ein Objekt repräsentiert ein vorkommen eines Wortes in einem Dokument:

    case class Posting(docId:Int, var termFrequency:Int)

    Indexing ein neues Dokument ist nur eine Frage der tokenisierung (Trennung in Token/Worte) und für jedes token legen Sie eine neue Buchung in die richtige Liste der hash-map. Natürlich, wenn eine Buchung bereits vorhanden ist, für diesen Begriff in spezifischer SAP-docId ab, erhöhen Sie die termFrequency. Es gibt andere Wege, dies zu tun. Für die in-memory-invertierte Indizes das ist OK, aber für die on-disk-Indizes würden Sie wahrscheinlich wollen, legen Sie Postings einmal mit der richtigen termFrequency statt aktualisieren Sie es jedes mal.

    Bezüglich deiner zweiten Frage, es gibt in der Regel zwei Fälle:

    (1) Sie haben ein (fast) unveränderliches index. Sie index alle Ihre Daten einmal und wenn Sie haben neue Daten können Sie einfach neu indizieren. Es gibt keine Notwendigkeit, Echtzeit-Indizierung und viele Male in einer Stunde, zum Beispiel.

    (2) neue Dokumente eintreffen, die ganze Zeit, und Sie müssen zu suchen, die neu eingetroffene Dokumente so bald wie möglich.

    Für Fall (1) Sie können mindestens 2 Dateien:

    1 - Inverted Index-Datei. Es listet zu jedem Begriff alle Postings (docId/termFrequency Paare). Hier dargestellt im Klartext, aber in der Regel als binäre Daten gespeichert.

     Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq>
 Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq>
 Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq>
 Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq>
 ...
 TermN<docId5,termFreq><docId7,termFreq>

    2 - Die offset-Datei. Speichert bei jedem Begriff, den offset zu finden, die invertierte Liste in der invertierten Datei index. Hier bin ich vertreten den offset in Zeichen, aber Sie werden normalerweise speichern von binären Daten, so dass der offset wird in Byte. Diese Datei kann in den Speicher geladen beim Systemstart. Wenn Sie brauchen, um lookup-ein Begriff, invertierte Liste, die Sie lookup den offset und Lesen Sie die invertierte Liste aus der Datei.

    Term1 -> 0
Term2 -> 126
Term3 -> 222
....

    Zusammen mit diesen 2 Dateien, die Sie kann (und meist wird) Datei(en) zum speichern jeder Begriff ist IDF und jedes Dokument, das die norm.

    Für Fall (2), ich werde versuchen, kurz zu erklären, wie Lucene (und damit Solr und ElasticSearch) es tun.

    Datei-format können die gleichen sein, wie oben erklärt. Der Haupt-Unterschied ist, wenn Sie index neue Dokumente, die in Systemen wie Lucene, anstatt den index neu erstellen von Grund auf, die Sie erstellen Sie einfach eine neue mit nur der neuen Dokumente. Also jedes mal, wenn Sie haben, um den index etwas, Sie tun es in einer neuen getrennt-index.

    Zum ausführen einer Abfrage in diesem "gesplittet" index können Sie die Abfrage ausführen, die gegen jeden anderen index (parallel) und fasse die Ergebnisse zusammen, die vor der Rückgabe an den Benutzer.

    Lucene nennt dies "kleine" Indizes segments.

    Die offensichtliche Sorge hier ist, dass Sie bekommen eine Menge von kleinen Segmenten sehr schnell. Um dies zu vermeiden, müssen Sie eine Richtlinie für die Zusammenführung der Segmente und Erstellung von größeren Segmenten. Zum Beispiel, wenn Sie mehr als N segments Sie können entscheiden, verschmelzen alle Segmente, die kleiner als 10 KBs zusammen.

    InformationsquelleAutor der Antwort Felipe Hummel

Schreibe einen Kommentar