Wie führen Suchmaschinen Ergebnisse aus einem invertierten Index zusammen?

Question

Wie führen Suchmaschinen Ergebnisse aus einem invertierten Index zusammen?

Zum Beispiel, wenn ich nach den invertierten Indizes der Wörter "Hund" und "Fledermaus" suchte, würde es zwei riesige Listen jedes Dokumentes geben, das eines der zwei Wörter enthielt.

Ich bezweifle, dass eine Suchmaschine durch diese Listen, ein Dokument nach dem anderen, und versucht, Übereinstimmungen mit den Ergebnissen der Listen zu finden. Was wird algorithmisch getan, um diesen Verschmelzungsprozess zu beschleunigen?

Answer 1

Eigentlich Suchmaschinen tun diese Dokumentlisten zusammenführen. Sie erzielen eine gute Leistung, indem sie andere Techniken verwenden, von denen die wichtigste das Beschneiden ist: zum Beispiel werden die Dokumente für jedes Wort in der Reihenfolge eines abnehmenden PageRank gespeichert und erhalten Ergebnisse, die eine Chance haben, in die ersten 10 zu gelangen Wenn Sie dem Benutzer gezeigt werden, können Sie nur einen ziemlich kleinen Teil der Listen von Hunden und Fledermäusen durchqueren, sagen wir, die ersten Tausend. (Und natürlich gibt es Caching, aber das ist nicht der sehr Abfrageausführungsalgorithmus verwandt)

Außerdem schließlich gibt es nicht dass viele Dokumente über Hunde und über Fledermäuse: auch wenn es Millionen ist, es stellt sich in Sekundenbruchteilen mit einer guten Implementierung.

---

P.S. Ich arbeitete zwar an der führenden Suchmaschine unseres Landes, aber nicht an der Engine unseres Flaggschiff-Produkts, aber ich sprach mit seinen Entwicklern und war überrascht zu wissen, dass Algorithmen zur Ausführung von Abfragen eigentlich ziemlich dumm sind: Es stellt sich heraus, dass man einen riesige Menge der Berechnung in akzeptable Zeit Grenzen. Es ist alles natürlich sehr optimiert, aber es gibt keine Magie und keine Wunder.

Answer 2

Da invertierte Indizes nach docId geordnet sind, können sie sehr schnell zusammengeführt werden. [Wenn eines der Wörter bei docId 23 und dann bei docId 100001 beginnt, können Sie sofort auch in der ersten Liste auf docId 100001 oder höher vorspulen. ]

Da die typischen Belegüberschneidungen bei fast wenigen Millionen liegen, können sie sehr schnell nach Rang sortiert werden. Ich suchte nach 'Hundekatze' [sehr häufige 2 Wörter], die nur 54 Millionen Treffer zurückgab.

Das Sortieren von 10 Millon zufälligen Ganzzahlen dauerte nur 2,3 Sekunden in meinem Mac mit Single-Thread-Code [1 Million dauerte 206 ms!] Und da wir in der Regel nur die Top 10 auswählen müssen, ist nicht einmal die volle Sortierung erforderlich.

Hier ist der Code, wenn jemand die Geschwindigkeit der Sortierung versuchen und zu faul Code schreiben möchte!

import java.lang.*; 
import java.math.*; 
import java.util.*; 

public class SortTest { 
    public static void main(String[] args) { 
    int count = Integer.parseInt(args[0]); 

Random random = new Random(); 
int[] values = new int[count]; 
int[] bogusValues = new int[100000]; //screw cache 
    for(int i = 0; i < values.length;++i) { 
    values[i] = random.nextInt(count); 
} 
for(int i = 0; i < bogusValues.length;++i) { 
    bogusValues[i] = random.nextInt(count); 
} 
long start = System.currentTimeMillis(); 
System.out.println(start); 
     Arrays.sort(values); 
System.out.println(System.currentTimeMillis()); 
System.out.println(System.currentTimeMillis()-start); 
    Arrays.sort(bogusValues); 
} 

}