Strings schnell auf Ähnlichkeit überprüfen

[DieHardMan]

Hi,

ich muss in einer ListView doppelte und ähnliche Eintrage finden und hab das mit dem Levenshtein Algorithmus aus der Code Library versucht, klappt ja ganz vorzüglich, nur leider VIEL zu langsam.

Eine Listview enthält entweder komplett nur PlainText zum vergleichen, z.B.

Zitat:

Leonard Nimoy alias Mr.Spock kann den typischen "Spock-Gruß" nicht mehr. Auf Grund einer Gelenkkrankheit ist das Abspreizen der Finger für den 74-Jährigen mittlerweile zu schmerzhaft. Jetzt nutzte Nimoy diesen Zustand für einen Werbedeal.

Hamburg - Der Schauspieler Leonard Nimoy, bekannt durch seine Rolle in der Fernsehserie "Star Trek", hat Arthritis. Der "Vulkanier-Gruß", bei dem Mittel- und Ringfinger der rechten Hand seitlich abgespreizt werden, wurde neben den angespitzten Ohren zum Markenzeichen des treuesten Gefährten von Captain Kirk, dem Chef des Raumschiffs "Enterprise".

oder komplett nur HTML Code, z.B.

Zitat:

<FONT color=#d60000>49,99 &euro;</FONT>
<FONT face="Arial, sans-serif" size=2>
- Dampfdruck: 4 bar
- Sicherheitsverschluss
- rutschfester Korkhandgriff
- Dauer-Dampfstrahl - für große Dampfmenge ohne Unterbrechung
- senkrechte Dampfausgabe möglich
- 3 Jahre Garantie
- Mit Service-Adresse

Die Lösung muss also mit beidem umgehen können. Die Längen sind sehr unterschiedlich und betragen ca. 1.000 - 15.000 Zeichen. Es müssen maximal 50 Items verglichen werden.

Weiß da jemand eine Lösung?

[stoxx]

Das ist auch das langsamste, was Du da hast:

Zitat:

Zitat:

1.3 Naiver Ansatz - Nested Loop
Der einfachste Ansatz zur Lösung des Problems wäre die Bildung des Kreuzproduktes
der beiden Relationen (S x T) und die anschließende Anwendung der Distanzfunktion
D auf jedes einzelne Tupelpaar(si, tj). Der Berechnungsaufwand dafür liegt allerdings
meist außerhalb des Möglichen, da er quadratisch ist. Bei jeweils 10.000 Tupeln pro
Relation ergibt sich schon ein Wert von 100.000.000 Vergleichen.

von Link: http://mordor.prakinf.tu-ilmenau.de/...tringJoins.pdf

Such mal unter Google nach folgenden Begriffen:

"Similarity String Joins q-grams"

Fertigen Delphi Code wirst Du da aber wahrscheinlich nicht finden, bleibt oft nur die Arbeit, eventuell C Quellen nach Delphi zu portieren.

Gruß stoxx

[DieHardMan]

Glaub das is zu hoch für mich, aber könnte man nicht beim ersten String alle Wörter anhand des Trennzeichens ' ' zählen und dann diese im zweiten String suchen und je nachdem wieviele gefunden werden, das Prozentual ausrechnen?! Wird zwar nicht genau sein, aber für meine Zwecke sollte es reichen.

[Flocke]

Zitat:

Zitat von DieHardMan

... das mit dem Levenshtein Algorithmus aus der Code Library versucht, klappt ja ganz vorzüglich, nur leider VIEL zu langsam.

Hast du dir auch die Optimierungen durchgelesen, die ich hier aufgeführt habe (den Text unter dem Quelltext). Wenn du eine feste Schranke hast (x% Abweichung), dann brauchst du viele Strings überhaupt nicht miteinander zu vergleichen.

[DieHardMan]

Ja hab ich, habs auch versucht aber irgendwie net hinbekommen.

Delphi-Quellcode:

procedure TfrmMain.Button1Click(Sender: TObject);
var
  i, a, Minimum, Maximum, Distance, MaxDistance, LengthFirstString,
    LengthSecondString: Integer;
begin
  MaxDistance := 15;

  For i := 0 to lstRSSData.Items.Count - 1 do
  begin
    LengthFirstString := Length(lstRSSData.Items.Item[i].SubItems.Strings[3]);
    Minimum := LengthFirstString - (MaxDistance * LengthFirstString div 100);
    Maximum := LengthFirstString + (MaxDistance * LengthFirstString div 100);

    For a := i to lstRSSData.Items.Count - 1 do
      If a <> i then
      begin
        LengthSecondString := Length(lstRSSData.Items.Item[a].SubItems.Strings[3]);
        If (LengthSecondString >= Minimum) and
          (LengthSecondString <= Maximum) then
        begin
//          ShowMessage(IntToStr(LengthFirstString) + #13#10 + IntToStr(temp1) +
//            #13#10 + IntToStr(temp2));
          distance := Levenshtein(lstRSSData.Items.Item[i].SubItems.Strings[3],
            lstRSSData.Items.Item[a].SubItems.Strings[3]);
          If distance <= maxdistance then
            ShowMessage('Duplicate text found!' + #13#10#13#10 + 'i' +
              IntToStr(i) + ': ' + #13#10 +
              lstRSSData.Items.Item[i].SubItems.Strings[2] +
              #13#10#13#10 + 'a' + IntToStr(a) + ': ' + #13#10 +
              lstRSSData.Items.Item[a].SubItems.Strings[2] + #13#10#13#10 +
              'Difference: ' +  IntToStr(distance) + ' %');
        end;
      end;
  end;
end;

[Flocke]

Was genau funktioniert denn da nicht? Sieht doch schon ganz gut aus.

Ein paar Kommentare:

15% Abweichung ist eine Welt. Das sind bei Längen von 1.000-15.000 Zeichen bis zu 150-2.250 unterschiedliche Zeichen. Vielleicht solltest du die Toleranzgrenze heruntersetzen, dafür aber die Strings vorher `glätten´ (HTML Markup entfernen, nur Kleinschreibung, alle Leer- und Interpunktionszeichen durch ein einziges Leerzeichen ersetzen, usw.)

Der Zugriff über Subitems.Strings[3] ist wohl nicht der schnellste. Eventuell solltest du die Strings vorher in ein TStringList kopieren. Wenn du aber wirklich nur ca. 50 Einträge hast, dann wird sich das wohl nicht lohnen.

[DieHardMan]

Zitat:

Was genau funktioniert denn da nicht?

Naja er findet jetzt nur Strings mit genau 15% Abweichung, aber keine unter 15%, aber ich denk mal ich muss nur Minimum auf 0 setzen.

Zitat:

15% Abweichung ist eine Welt.

Das war jetzt nur ein Testwert, mein Abweichungswert wird bei 10% liegen.

Zitat:

dafür aber die Strings vorher `glätten´ (HTML Markup entfernen, nur Kleinschreibung, alle Leer- und Interpunktionszeichen durch ein einziges Leerzeichen ersetzen, usw.)

Beim Markup muss ich schaun, wie schnell das geht, ob es sich überhaupt lohnt, die anderen Ratschläge werd ich befolgen, danke.