Wie arbeitet eine Suchmaschine?

[-error-]

hallo,

Ich bin immer wieder erstaunt wie gezielt man mit Google suchen kann. Meistens bekomme ich genau das was ich gesucht habe.
Aber wie funktioniert eine solche Suchmaschiene? Ist das ein großer Server der alle im Netz befindlichen Seiten runterlädt, auf dem man dann beim Suchen zugreift?

[mapel110]

es gibt mehrere arten von suchmaschinen.

zum einen suchen sie über automatisch erstellte indizes, wobei dann um das sortieren ein recht grosses geheimnis gemacht wird, damit sich halt niemand einen vorteil verschaffen kann.

zum anderen gibts dann auch noch redaktionell betreute suchmaschinen, wie zb yahoo auf jedenfall eine ist. d.h. es überarbeiten leute mehr oder weniger manuell die indizes und sortieren nach kategorien.

hm, bei chip.de gabs mal nen artikel darüber.

[mirp]

Hier dürfte man alles darüber finden:

http://www.suchfibel.de/

[GloomY]

Eine ähnliche Frage kam vor kurzem im Mod-Forum auf. Ich kopiere mal meine Antwort von da:

Da man bei großen Datenmengen nicht erst zur Laufzeit (Anfragezeit) alle Daten komplett durchsuchen kann, weil das viel zu lange dauern würde, muss man sicherstellen, dass die relevanten Daten wenigstens schnell gefunden werden (ohne komplettes Durchsuchen ). Dafür erzeugt man einen Index, bei dem für jedes in den Daten vorkommendes Wort alle Stellen gespeichert werden, an denen dieses vorkommt. Man arbeitet hier mit einer Hash-Funktion (*), da sich der Hash-Wert eines Wortes sehr schnell erzeugen und nachgucken lässt.

Für jedes vorkommende Wort wird also ein Hash-Wert erzeugt. Verschiedene Wörter können gleiche Hash-Werte haben (wegen (*) ). Für jeden Hash-Wert wird eine Liste mit den zugehörigen Wörtern erzeugt und für jedes Wort eine Liste mit den zugehörigen Fundstellen.
Wenn man einmal die Hash-Tabelle erzeugt hat und nach Seiten mit einem bestimmten Wort sucht, so muss man nur den Hash-Wert des Wortes erzeugen und dann hat man über die zuvor erstellte Tabelle schnell alle Postings mit diesem Wort gefunden, welche man dann in Null-Komma-Nix noch sortieren und ausgeben kann.

http://www.forum-3dcenter.net/vbulletin/attachment.php?s=&postid=1258474

(*) Eigentlich ist das keine echte Hash-Funktion, da diese nicht eindeutig ist. Man kann also mit einem gegebenen Hash-Wert nicht mehr auf das Wort zurückschliessen, was hier aber sowieso nicht gefragt ist.

[Endorphine]

Um das Wort "Hash" mal zu entzaubern: es handelt sich hierbei um Quersummen, die mathematisch etwas aufwändiger gestaltet wurden, um sicherzustellen, dass die Chance minimiert wird, dass zwei verschiedene Datenströme die gleiche Quersumme ergeben.

Da man von der Quersumme nicht mehr auf die Ursprungsdaten schliessen kann (zumindest nicht mit endlichem Aufwand und einer guten kryptographischen Quersumme wie MD4/MD5 oder gar SHA-1/SHA2) spricht man auch von "Einweghashes".

Solche kryptographischen Quersummen werden wie der Name schon sagt auch gern im Zusammenhang mit Kryptographie verwendet. Sie bieten sich auch zur Authentifikation mittels Passwörtern/Passphrasen an. Dabei wird dann nur noch der Hash gespeichert und bei einer Passwort-/Passphraseabfrage nur der gespeicherte Hash mit dem Hash des eingegebenen Passworts verglichen.

[GloomY]

Ein Hash ist im allgemeinen Falle eine bijektive Funktion, d.h. jedem Element aus der Definitionsmenge wird genau ein Element aus der Wertemenge zugeordnet (und umgekehrt!). Für endliche Mengen kann man auch sagen, dass ein Hash eine Permutation ist (im Sinne der linearen Algebra).

Für den Fall einer Suchmaschine ist das aber nicht brauchbar, da die Hash-Tabelle im schlimmsten Fall so groß wird wie die zu durchsuchenden Daten. Das bringt dann keinen Geschwindigkeitsgewinn mehr.
Daher verwendet man eine Funktion, die nur noch surjektiv ist, d.h. mehreren Elementen aus der Def.-Menge wird ein Funktionswert zugeordnet. Im Sinne der obigen Definition ist das aber keine echte Hash-Funktion mehr.

Bei einer solchen Pseudo-Hash-Funktion kann man im Allgemeinen selbst mit unendlich großem Aufwand (sprich: unmöglich) bei einem gegebenen Funktionswert nicht mehr das dazugehörige Element aus der Definitionsmenge herausfinden, denn es kann ja sein, dass mehrere Elemente den gleichen Funktionswert zugewiesen bekommen haben.

Für die Erstellung der Hash-Funktion verwendet man oftmals den "Schmidschen Hash" (s.u.). Um den Wert der Hash-Funktion dann noch auf den Wertebereich der Hash-Funktion zu beschränken (es soll ja beliebige Wortlänge zugelassen werden) rechnet man das Ergebnis noch modulo einer Zahl n. Damit n Teilerfremd zu B ist (s.u.), nimmt man gewöhnlich die größte Primzahl, die kleiner als der höchstmögliche Funktionswert ist (im obigen Beispiel 19997 statt 20000).

[DocEW]

Original geschrieben von Powerd by ATI
Aber wie funktioniert eine solche Suchmaschiene? Ist das ein großer Server der alle im Netz befindlichen Seiten runterlädt, auf dem man dann beim Suchen zugreift?
Genau das hoffe ich in meiner Vorlesung "Multimediaretrieval I" dieses Semester zu erfahren! :D
Also, wenn du's wirklich wissen willst...schau dir sowas auch mal an! Da geht's allerdings nicht nur um Texte, sondern eben um "Multimedia", also auch Bilder und Ton ("In welchem Lied kommen diese Töne hintereinander vor?").

[-error-]

^^^^
Währe ne Möglichkeit! Aber die hier geposteten Seiten haben mir schon einiges verständlicher gemacht.