ABAKUS

Pamela hat geschrieben:Ich glaube nicht, dass es irgendeiner Suchmaschinen jemals gelingen wird, doppelten Content auch nur ansatzweise vollständig zu erkennen.

Ich denke, es muss dafür nicht eine Seite mit allen anderen verglichen werden, vielmehr braucht man - schließlich sind die Seiten ja indexiert - nur einen Grenzwert von sagen wir 5 oder 10 Begriffen festlegen, die sich überschneiden müssen. Vorab kann man natürlich auch alle Seiten aus anderen Sprachen ausschließen usw. Durch einen geeigneten Algorithmus kann man den notwendigen Aufwand sicher weiter reduzieren. Außerdem dürfte jeder Bot ja auch prüfen, ob eine Seite unverändert ist oder nicht. Das wäre dann ja der Fall und bei einer unterschiedlichen IP könnte er Alarm schreien. Nur so ein paar Ideen - reines Probieren, wie du es annimmst, hat natürlich keine Chance.

Pamela hat geschrieben:Um von sich behaupten zu können, dass man alle doppelten Inhalte findet, müsste man jede Webseite weltweit mir jeder anderen Seite vergleichen.

Es gibt effizientere Lösungsansätze die Du aus den Google Patenten entnehmen kannst:
Detecting duplicate and near-duplicate files
System and method for detecting duplicate and similar documents
Gruss

Hallo Pamela,

man muss auf der Suche nach DC nicht jedes Dokument mit jeder möglichen Kombination aller anderen Dokumente vergleichen, sondern nur mit jedem anderen. Wenn n die Anzahl der Internetseiten ist (eher in der Größenordnung mehrere Milliarden), muss man also nicht n! Vergleiche durchführen, sondern nur (n über 2), also ca. n². Das ist natürlich immer noch zu viel, aber erscheint schon greifbarer. Damit sind wir bei O(n²)

Ein weiterer Ansatz, den Aufwand zu verringern, ist, von jedem Dokument einen Hashwert zu berechnen (MD5, SHA o.ä.). Das geht in O(1) für ein Dokument, bzw. O(n) für alle, und verschlechtert somit den Aufwand nicht. Anschließend sortiert man die Dokumente nach dem berechneten Hashwert. Das geht in O(n*log n).

Nun muss man in dieser Liste nur noch nach Duplikaten suchen, was in einer sortierten Liste sehr schnell geht. Neue Dokumente können mit Aufwand O(log n) auf Duplikate hin geprüft werden.

Damit ist der limitierende Faktor beim erstmaligen erstellen der Liste O(n*log n), wenn man bereits eine Liste hat, und diese kontinuierlich pflegt (was bei Google wohl der Fall ist), kann man sogar in O(log n) auf DC prüfen. Dann spielt die Größe des Internets kaum noch eine Rolle.

Um die Ergebnisse einer solchen Suche zu verbessern, berechnet man am besten für jedes Dokument mehrere Hash-Werte (z.B. einen aus Titel + Description, einen aus den ersten 5 Absätzen usw.).

Findet man eine Übereinstimmung des Hashwertes von zwei Dokumenten, kann man diese sicherhaitshalber immer noch genauer unter die Lupe nehmen. Auch im Falle von Kollisionen in Hashverfahren macht dieser Schritt Sinn.

Mehr über
Hashverfahren: https://de.wikipedia.org/wiki/Hash-Funktion
Suchverfahren: https://de.wikipedia.org/wiki/Suchverfahren
Sortierverfahren: https://de.wikipedia.org/wiki/Sortierverfahren
Landau-Notation: https://de.wikipedia.org/wiki/Landau-Symbole

Viele Grüße,

Dan

Da liegst du aber ganz weit daneben, Schalberger.
Wenn die Dateien 100% identisch sind, ist die Idee mit den Hashwerten super, aber sobald sie nur leicht abgewandelt sind kommst du da nicht weiter.

man muss auf der Suche nach DC nicht jedes Dokument mit jeder möglichen Kombination aller anderen Dokumente vergleichen, sondern nur mit jedem anderen.

Jep! Da liegst du richtig. Es werden (n-1)+(n-2)+(n-3)+...+(n-n) < n² Vergeliche benötigt.

Konstantin

k-weddige hat geschrieben: Da liegst du aber ganz weit daneben, Schalberger.
Wenn die Dateien 100% identisch sind, ist die Idee mit den Hashwerten super, aber sobald sie nur leicht abgewandelt sind kommst du da nicht weiter.

Richtig. Deswegen auch der Vorschlag, für jedes Dokument verschiedene Hash-Werte zu berechnen. (Titel + Description, einzelne Absätze usw.) Im Übrigen wird das der Grund sein, dass Google trotzdem große Probleme hat, DC zuverlässig aufzuspüren.

Schöne Grüße,

Dan

Um das zuverlässig machen zu können müsstest du aber so viele Hashwerte erstellen, dass du es auch ganz sein lassen kanst. Wenn z.B. von jedem Absatz ein Hash erstellt wird, würde ja ein geändertes Wort pro Absatz reichen, das System auszutricksen.
Ein Titel, wie "Home", oder ein Absatz, der aus einem Zitat besteht, würde eine Fehlalarn auslösen.
Das ist einfach nicht machbar.
Außerdem ist eine überbewertung von DC in einer Welt, in der die Hälfte der Nachrichten von Nachrichtendiensten geliefert und 1:1 übernommen werden, IMHO einfach nicht sinnvoll.

Konstantin

PS: Der Aufwand beim Vergleichen ist sogar &#920;(n²), da (n-1)+(n-2)+(n-3)+...+(n-n)=1/2*n². (Wenn ich mich jetzt nicht verrechnet habe)

Pamela hat geschrieben:...
Keine Ahnung wie viele HTML-Seiten es weltweit gibt, aber wenn man als Schätzwert 100.000.000 Seiten annimmt, müsste man nun die Fakultät aus der Zahl 100.000.000 berechnen und diese Zahl ist so gigantisch groß, dass die Festplatte des Abakus-Servers nicht ausreichen würde um diese Zahl auszuschreiben.

Ich glaube hier sind einfach Grenzen gesetzt, die nicht zu überwinden sind und meine Erfahrungen bestätigen dies.
...

/*IRONIE*/google kauft sich 1.000.000 indische Kindersklaven und setzt sie an 1.000.000 Rechner. Jeder muß 20 h am Tag alle 20 Sekunden ne neue Website aufrufen. Wenn er ein Duplikat entdeckt bekommt er ne Handvoll Reis. Was denkst Du, wie schnell die das rausfinden?

Naja, wenn geradliniges hashing (gesamt oder in einfachen Bröckchen) sinnvolle Ergebnisse ergäbe, bräuchte man auch keine Patente

Für eine brauchbare Vergleichbarkeit muss erstmal ordentlich Komplexität und Rauschen raus aus den Dokumenten, d.h. Preprocessing mit z.B.
- alle Formatiermerkmale raus,
- Normierung von Schreibweisen,
- Stoppwörter raus,
- unbekannte Wörter raus,
- Synonym-Mapping (Ersatz bekannter in etwa synonymer Wörter oder gleich Phrasen durch einen Repräsentanten)

Das Ergebnis ist schon stark vereinfacht, aber noch eine (fast) lesbare Tokenliste. Zum Vergleich braucht man etwa die Abfolge nicht - die ist dafür eher störend. Weiter normieren kann man da, in dem man z.B. (je nach Länge ganz ober abschnittsweise) nach Häufigkeiten sortiert. Damit kommt man schon in die Richtung recht brauchbarer Fingerprints, die sich z.B. über geeignete Hashes vergleichen lassen.

Wenn ich die Patente beim (sehr) raschen Drübergucken recht verstanden habe, wird auch in etwa so gearbeitet. Die Intelligenz steckt freilich in Details.

Das interessante dabei ist, dass
1. viel schon bei der Indexierung eh auftritt, dadurch nicht viel extra kostet,
2. der Vergleichsaufwand in der Praxis auch nicht unbedingt gross als Extra zu Buche schlagen muss; da lässt sich viel sinnvoll dividieren.

Eine Sortierung findet ja spätestens bei der Aufbereitung von Suchergebnissen bereits statt und rückt ähnliche Dokumente nah beisammen. Führt man Dublettenvergleiche "cross sites" (anhand der vorberechneten Signaturen) etwa erst auf diesen Ergebnismengen durch, reduziert man nicht nur allen möglichen Overhead, sondern stiefelt auch nur bröckchenweise durch (was im Kleinen immer noch 1/2n^2 bedeutet, aber im Grossen im Grenzwert auf 1/2n*log n läuft) UND man kümmert sich nur um den relevanten Teil des Raums (!!).

Vergleiche "intra site" lassen sich schon vorher erledigen (was ja auch passiert) und reduzieren den Raum bereits gewaltig. Ebenso sind andere kleine Teile des Raums je nach Details der SuMa an einigen anderen Stellen des Prozesses beieinander, so dass da auch im Kleinen gefiltert werden kann.

Sauber angestellt liegen einzelne Vergleiche irgendwo in eh vorhandenen Prozessen, schlagen also mit Faktoren zu Buche. Die Kunst ist, die klein zu halten. Insgesamt denke ich nicht, dass DC-Erkennung als Feature im gesamten Prozess grosse eigene Herausforderungen an die Resourcen oder Performance stellt. Evtl. kann man über alles gesehen sogar eine Performance-Verbesserung postulieren, nämlich wenn genügend Dupes vorhanden sind, dass die Reduktion den Raum für andere Operationen messbar ausdünnt

Die Güte steht und fällt dabei mit der Güte der Signatur, und die Chose ist O(n).

@Pamela,

Wer sagt das Google oder die anderen Suchmaschinen alles (also 100.000.000 Seiten) überprüfen müssen ? es reicht völlig die Top 30 zu vergleichen, das was danach kommt ist eh "scheiß" egal ...

Und wenn man das dann nur bei den " beliebten & komerziellen" Keys macht, wird die Zahl doch recht übersichtlich