Ich habe einen Korpus von 900.000 Saiten. Sie variieren in der Länge, haben aber eine durchschnittliche Anzahl von etwa 4.500 Zeichen. Ich muss den effizientesten Weg finden, den Würfelkoeffizienten jeder Zeichenkette so zu berechnen, wie er sich auf jede zweite Zeichenkette bezieht. Leider führt dies dazu, dass der Würfelkoeffizientenalgorithmus etwa 810.000.000.000 Mal verwendet wird.
Was ist der beste Weg, um dieses Programm für mehr Effizienz zu strukturieren? Offensichtlich kann ich die Berechnung der Würfel der Abschnitte A und B und dann B und A verhindern - dies halbiert jedoch nur die erforderliche Arbeit. Sollte ich in Betracht ziehen, einige Abkürzungen zu verwenden oder eine Art Binärbaum zu erstellen?
Ich verwende die folgende Implementierung des Würfelkoeffizientenalgorithmus in Java:
%Vor%Mein ultimatives Ziel ist es, eine ID für jeden Abschnitt auszugeben, der einen Würfelkoeffizienten größer als 0,9 mit einem anderen Abschnitt hat.
Vielen Dank für Ihren Rat!
Machen Sie einen einzigen Durchlauf über alle Strings und bauen Sie eine HashMap auf, die jedes Bigramm auf eine Menge der Indizes der Strings abbildet, die dieses Bigramm enthalten. (Gegenwärtig bauen Sie das Bigramm-Set 900.000-mal redundant für jeden String.)
Machen Sie dann einen Durchgang über alle Mengen und erstellen Sie eine HashMap von [index, index] -Paaren zu Common-Bigramm-Zählungen. (Die letztere Karte sollte keine redundanten Schlüsselpaare enthalten, wie [1,2] und [2,1] - speichern Sie einfach das eine oder das andere.)
Diese beiden Schritte können leicht parallelisiert werden. Wenn Sie einen Beispielcode benötigen, lassen Sie es mich wissen.
HINWEIS Eine Sache jedoch: Aus den 26 Buchstaben des englischen Alphabets können insgesamt 26x26 = 676 Bigramme gebildet werden. Viele davon werden nie oder fast nie gefunden werden, da sie nicht den Regeln der englischen Rechtschreibung entsprechen. Da Sie Mengen von Bigrammen für jeden String aufbauen und die Strings so lang sind, werden Sie in jedem String wahrscheinlich fast die gleichen Bigramme finden. Wenn Sie Listen von Bigrammen für jeden String erstellen würden (mit anderen Worten, wenn die Häufigkeit jedes Bigrams gezählt wird), ist es wahrscheinlicher, dass Sie tatsächlich dazu in der Lage wären messen Sie den Grad der Ähnlichkeit zwischen Strings, aber dann würde die Berechnung des Koeffizienten von Dice, wie in dem Artikel von Wikipedia angegeben, nicht funktionieren; Sie müssten eine neue Formel finden.
Ich schlage vor, dass Sie weiter nach Algorithmen suchen, um die Ähnlichkeit zwischen Strings zu bestimmen, versuchen Sie, einige davon zu implementieren, und führen Sie sie auf einer kleineren Menge von Strings aus, um zu sehen, wie gut sie funktionieren.
Sie sollten mit einer Art von Ungleichung kommen wie: D (X1, X2) & gt; 1-p, D (X1, X3) & lt; 1-q und p D (X2, X3) & lt; 1-q + p. Oder etwas ähnliches. Wenn nun 1-q + p & lt; 0.9, dann müssen Sie wahrscheinlich D (X2, X3) nicht auswerten.
PS: Ich bin mir über diese genaue Ungleichheit nicht sicher, aber ich habe das Gefühl, dass dies richtig ist (aber ich habe nicht genug Zeit, um die Ableitungen jetzt zu machen). Suchen Sie nach einigen der Ungleichungen mit anderen Ähnlichkeitsmaßen und sehen Sie, ob einige von ihnen für den Würfel-Koeffizienten gültig sind.=== Auch ===
Wenn es Elemente in Menge A gibt und wenn Ihre Schwelle r (= 0,9) ist, dann sollte Menge B eine Anzahl von Elementen haben, die so sein sollten, dass: r * a / (2-r) & lt; = b & lt; = (2-r) * a / r. Dies sollte die Notwendigkeit für viele Vergleiche IMHO beseitigen. Sie können die Strings wahrscheinlich nach Länge sortieren und das oben beschriebene Fenster verwenden, um Vergleiche zu begrenzen.
Haftungsausschluss zuerst: Dadurch wird nicht die Anzahl der Vergleiche reduziert, die Sie vornehmen müssen. Aber das sollte einen Würfelvergleich schneller machen.
1) Erstellen Sie Ihre HashSets nicht bei jedem Aufruf von diceCoefficient ()! Es sollte die Dinge erheblich beschleunigen, wenn Sie es nur einmal für jeden String tun und das Ergebnis herum halten.
2) Da es Ihnen nur wichtig ist, ob ein bestimmtes Bigramm vorhanden in der Zeichenfolge ist, könnten Sie mit einem BitSet mit einem Bit für jedes mögliche Bigramm und nicht mit einer vollständigen HashMap auskommen. Die Koeffizientenberechnung würde dann vereinfacht werden, um zwei Bit-Sätze zu verknüpfen und die Anzahl der gesetzten Bits im Ergebnis zu zählen.
3) Oder, wenn Sie eine große Anzahl möglicher Bigramme (Unicode, vielleicht?) haben - oder monotone Strings mit nur jeweils einer Handvoll Bigramms - könnte ein sortiertes Array von Bigrammen schnellere, platzsparendere Vergleiche liefern / p>
Ist ihr Zeichensatz irgendwie eingeschränkt? Wenn dies der Fall ist, können Sie die Zeichenanzahl anhand ihres Codes in jeder Zeichenfolge berechnen und diese Zahlen vergleichen. Nach einer solchen Vorberechnung (es belegt 2 * 900K * S Bytes Speicher [wenn wir annehmen, dass kein Zeichen mehr als 65K Zeit in derselben Zeichenkette gefunden wird], wobei S eine andere Zeichenzahl ist). Dann würde die Berechnung des Koeffizienten O (S) Zeit benötigen. Sicher, das wäre hilfreich, wenn S & lt; 4500.
Tags und Links algorithm string multithreading