Doublettencheck

Forum for developers

Doublettencheck

Beitragvon Low012 » Mo Nov 17, 2008 8:27 pm

Falls sich jemand mit dem Doublettencheck näher befassen möchte, ich habe mich mal ein bisschen umgesehen:

Ich habe bisher 2 Möglichkeiten gefunden, wie man mit Texten umgehen kann, um auf Doubletten (auch mit kleinen Unterschieden) testen zu können.

Die erste Möglichkeit ist, bestimmte Dinge aus dem Text zu entfernen und dann einen ganz normalen Hash (md5, SHA-1, ...) draus zu machen. Wenn zwei Texte zum gleichen Hash führen, sind sie entweder gleich oder zumindest nicht unabhängig voneinander entstanden.

Die zweite Möglichkeit ist, eine Art Hash zu bilden, wobei sich dieser Wert bei zwei Texten stärker unterscheidet, je unterschiedlicher die Texte sind.

Beispiele für die erste Möglichkeit sind das schon in einem anderen Thread angesprochene Modell von NiX Spam und die von Nutch genutzte TextProfileSignature.

NiX Spam macht mit einem Text das Folgende: Es werden zwei "Fingerabdrücke" eines Textes erstellt. Der erste ist ein Hash über den Text ohne alle Zeichen bis auf Leerzeichen und Zeilenwechsel. Der zweite Hashwert wird über den Text ohne Zahlen, Buchstaben und Zeilenumbrüche gebildet, wobei Unterstriche vorher auch noch durch Punkte ersetzt werden. Ist einer der beiden Werte für zwei Texte gleich, sind sich die Texte wahrscheinlich auch sehr ähnlich oder sie sind gleich. Ist ein Text sehr kurz oder kaum strukturiert, werden alle Zeichenwiederholungen und Zeilenumbrüche entfernt und dann ein Hash gebildet. Die Langversion kann man unter http://www.heise.de/kiosk/archiv/ix/04/05/119_Redundanzanalyse_Aehnliche_Texte_finden_mit_Fuzzy_Checksums kaufen. Ein Nachteil dieser Methode ist, dass vom ursprünglichen Text ja sehr viel verworfen wird. Für die Spamerkennung ist das nützlich, weil Spammer teilweise Emails mit zufällig gewählten oder ausgetauschten Worten gefüllt werden. Wenn man seine Hashdatenbank öfter mal bereingt, was ja nicht weiter stört, da Spam ja oft gehäuft auftaucht, sollte es kaum zu kollisionen kommen. Bei YaCy könnte es aber zu ungewünschten False Positives führen.

Die Nutch-Variante wird auf der folgenden Seite ganz gut beschrieben, weshalb ich nur dahin verlinke: http://lucene.apache.org/nutch/apidocs/org/apache/nutch/crawl/TextProfileSignature.html

Die zweite Möglichkeit ist im Nilsimsa-Algorithmus verwirklicht: http://ixazon.dynip.com/~cmeclax/nilsimsa.html Ich habe den mir noch nicht genauer angesehen. Laut http://archives.devshed.com/forums/java-118/checking-for-duplicates-inside-index-1844692.html soll der Algorithmus irgendwelche Nachteile haben, allerdings ist das Archiv, in dem sich Einzelheiten dazu finden lassen sollen, nicht mehr verfügbar.
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm

Re: Doublettencheck

Beitragvon Orbiter » Mo Nov 17, 2008 11:11 pm

Hallo Marc,

gute Recherche! Die Nutch-Variante finde ich eigentlich recht plausibel. Es ist eine Heuristik, und es könnten sich false positive daraus ergeben. Besonders kitzelig finde ich das Abschneiden der Wörter, die eine zu geringe Termfrequenz haben. Ich würde statt dessen einfach eher die Wörtlänge auf mindestens 3 Buchstaben setzen (dann ist weniger 'Rauschen' drin), und keine Ziffern, sowie Wörter aus einer Blacklist, in der Monatsnamen in vielen Sprachen stehen, zulassen. Dann erwischen wir damit den häufigsten Grund für fehlerhaften Double-Check, das Einblenden von neuen Datumsangaben.
Aber Wörter abschneiden, die eine minimale Termfrequenz haben, ist das richtig (also alle Wörter bsp. die nur ein mal vorkommen)?
Orbiter
 
Beiträge: 5792
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Doublettencheck

Beitragvon Low012 » Di Nov 18, 2008 10:01 am

Ich habe hier mal zwei Seiten rausgesucht, die den gleichen Inhalt haben, aber ein unterschiedliches "Drumherum":

http://de.wikipedia.org/wiki/Yacy
http://wissen.spiegel.de/wissen/dokumen ... ik=artikel

Vielleicht helfen die ja, herauszufinden, was man bei einem Check mit Hash weglassen muss und was in die Berechnung eingehen sollte. Es fällt zum Beispiel auf, dass viele Elemente, die in beiden Dokumenten verschieden sind, Links sind. Auf anderen Seiten mit unterschiedlichen Menüs und gleichem Text sollte es ja nicht anders sein. Es wäre also zu überlegen, ob es sinnvoll wäre, den Teil zwischen <a> und </a> nicht zum Text zu zählen. Menübestandteile, die keine Links sind (z.B. Überschriften von Kategorien) könnte man ausschließen, indem man nur Wörter als Text akzeptiert, die in Sätzen stehen. (Dann braucht man allerdings auch eine Ausweichstrategie für Seiten ganz ohne Satzzeichen.) Zusätzlich zu den Monatsnamen sollten auch noch die Namen von Wochentagen unter den Tisch fallen. Auf der Spiegel-Seite wird der Wochentag beim Datum eingeblendet.

Wochen- und Monatsnamen lassen sich eventuell automatisch aus den Übersetzungen von freier Software (z.B. phpBB) auslesen oder wir könnten Wikipedia nutzen, indem wir mit dem Artikel zu einem Monat oder Wochentag in einer uns bekannten Sprache anfangen und ein Skript dann den Links zu den anderssprachigen Artikeln folgen lassen. Soweit ich das gesehen habe, wird der entsprechende Block mit Links in allen Sprachen mit <div id="p-lang" class="portlet"> eingeleitet. Auf http://de.wikipedia.org/wiki/Dienstag findet man in der linken Spalte auf jeden Fall eine beeindruckende Zahl von Übersetzungen.

edit: Hier noch zwei Dokumente, die ich bis jetzt nur überflogen habe, die aber eventuell nützliche Informationen enthalten:
http://www.hpl.hp.com/techreports/2005/ ... 5-42R1.pdf
http://www.ir.iit.edu/~abdur/Research/Duplicate.html
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm

Re: Doublettencheck

Beitragvon Orbiter » Mo Nov 19, 2012 11:27 pm

rumpel..rumpel..altes Thema raus....:!!

jetzt bin ich am Doublettencheck dran, und jawohl es wird die Nutch-Routine TextProfileSignature sein, die jetzt in Solr verbaut ist und also in einer verlinkten Library drin ist.
Im Source Code von org.apache.solr.update.processor.TextProfileSignature ists beschrieben:
org.apache.solr.update.processor.TextProfileSignature hat geschrieben:- remove all characters except letters and digits, and bring all characters to lower case,
- split the text into tokens (all consecutive non-whitespace characters),
- discard tokens equal or shorter than MIN_TOKEN_LEN (default 2 characters),
- sort the list of tokens by decreasing frequency,
- round down the counts of tokens to the nearest multiple of QUANT = QUANT_RATE * maxFreq, whereQUANT_RATE is 0.01f
- by default, and <code>maxFreq</code> is the maximum token frequency). If maxFreqis higher than 1, then QUANT is always higher than 2 (which means that tokens with frequency 1 are always discarded).
- tokens, which frequency after quantization falls below QUANT, are discarded.
- create a list of tokens and their quantized frequency, separated by spaces, in the order of decreasing frequency.
- This list is then submitted to an MD5 hash calculation.

Das wird zunächst mal benutzt um einen entsprechenden Hash in den Index zu schreiben, was danach damit passiert ist wieder ein anderes Thema!

Beispiel:
- man benutzt den Ähnlichkeitshash nicht als Double-check Ersatz sondern nur um Suchergebnislisten einzuschränken. Dann vermeidet man Fehler beim Doublettencheck wo der Check 'zu viel' herausgelöscht hat'
- man benutzt den Ähnlichkeitshash um die Dokumente die angeblich ähnlich sind miteinander im Index zu verlinken, um somit Subsumptionen (einer hat von einem anderen abgeschrieben) erkennbar zu machen.
- ?
Orbiter
 
Beiträge: 5792
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main


Zurück zu YaCy Coding & Architecture

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste

cron