Vergleichen von 2 Strings (prozentual)

[Chillkröte]

Hallo
ich sitze jetzt von seit einiger zeit vor dem Problem, 2 Strings prozentual zu vergleichen.
Diese Funktion bietet das zwar schon an, jedoch ist das Ergebnis nicht befriedigend.
Es geht um folgende strings (aus der luft gegriffen)

Code:

"sdfsd-fgdfdf Hier.Der.Beispiel.Text-sdf-dff-ddd"

"Hier der Beispiel Text"

bei der oben verlinkten Funktion wird nur bis zum Ende des kürzeren Strings verglichen und demzufolge kommt kein vernünftiges Ergebnis bei raus.

Hat jemand Lösungsvorschläge?

[mkinzler]

Was verstehst du unter "prozentual Vergleicehn"?

[daywalker9]

Ich würde dem Link zu folge tippen, zu wieviel Prozent die Strings identisch sind..

[Chillkröte]

@daywalker9
genau

Delphi-Quellcode:

function DoStringMatch(s1, s2: string): Double;
var
  i, iMin, iMax, iSameCount: Integer;
begin
  iMax := Max(Length(s1), Length(s2));
  iMin := Min(Length(s1), Length(s2));
  iSameCount := -1;
  for i := 0 to iMax do
  begin
//    if i > iMin then
//      break;
    if s1[i] = s2[i] then
      Inc(iSameCount)
//    else
//      break;
  end;
  if iSameCount > 0 then
    Result := (iSameCount / iMax) * 100
  else
    Result := 0.00;
end;

so müsste das eig gehen
(gleichheit bei 12%)
irgendwie steh ich momentan echt aufn schlauch...

[Chillkröte]

das problem ist aber noch bei solchen strings

Delphi-Quellcode:

doStringMatch('exp_onkelcharliexvid_s06e24','Onkel Charlie S06 E24');

gleichheit = 0, was ja auch logisch ist, da die zeichen nicht übereinstimmen

[stahli]

Schau mal hier, ob´s Dir was hilft.
Mit einer kleinen Anpassung könnten auch Teiltexte akzeptiert werden.

[hans ditter]

Ich würde erstmal die beiden Längen der Strings ermitteln, dann eine Schleife für die Länge des längeren Strings einsetzten.
In der Schleife dann überprüfen, ob die überprüften Buchstaben an der Stelle gleich sind, wenn ja, dann in die eine Variable (z.B. BuchsGleich) speichern, wenn nicht, in eine andere.
Am Ende dann die Länge des längeren Strings durch 100 und mal die gleichen (bzw. ungleichen, wenn man auf prozentuale Ungleichheit prüfen möchte) Buchstaben nehmen.

Ungetesteter Code!!

Delphi-Quellcode:

var BuchsGleich, BuchsUngleich, Länge: Integer;//Länge = Länge der Schleife
    string1, string2: String;//deine beiden Strings
    lString1, lString2: integer;//Länge deiner beiden Strings
    helpStr1, helpStr2: string;//braucht man zum Vergleichen
    CopyStart: integer;//Startposition des Kopiervorgangs
begin
  lString1:=length(string1);    lString2:=length(string2);
  if lString1 > lString2 then Länge:=lString1
  else Länge:=lString2;
  CopyStart:=0;
  for i:=1 to Länge do//hier beginnt deine Prüfschleife
  begin
    helpStr1:=LowerCase(Copy(string1,CopyStart,1));   helpStr2:=LowerCase(Copy(string2,CopyStart,1));
    {die beiden Zeichen herauslösen, LowerCase notwendig, da man dann auch solche Strings vergleichen kann: 'BAUM' und 'baum'}
    if helpStr1 = helpStr2 then BuchsGleich:= BuchsGleich + 1
    else BuchsUngleich:= BuchsUngleich + 1;
    CopyStart:=CopyStart + 1;
  end
end

[Sir Rufo]

Ich habe hier den Quelltext zu einer Fuzzy-Suche, die ergibt bei deinem Beispiel eine Übereinstimmung von 55.21%

Delphi-Quellcode:

unit insFuzzy;

interface

function FuzzyMatching( const SearchIn, SearchStr : string ) : extended;

implementation

const
  MaxParLen = 255;

  (***************************************************************************)

function PrepareTheString( const OriginStr : string; var ConvStr : string )
  : Integer;
  var
    i : Integer;
  begin
    ConvStr := OriginStr;

    for i := 1 to Length( OriginStr ) do
      begin
        ConvStr[ i ] := UpCase( ConvStr[ i ] );
        if ( ConvStr[ i ] < '0' ) then
          ConvStr[ i ] := ' '
        else
          case ConvStr[ i ] of
            Chr( 196 ) :
              ConvStr[ i ] := Chr( 228 );
            Chr( 214 ) :
              ConvStr[ i ] := Chr( 246 );
            Chr( 220 ) :
              ConvStr[ i ] := Chr( 252 );
            Chr( 142 ) :
              ConvStr[ i ] := Chr( 132 );
            Chr( 153 ) :
              ConvStr[ i ] := Chr( 148 );
            Chr( 154 ) :
              ConvStr[ i ] := Chr( 129 );
            ':' :
              ConvStr[ i ] := ' ';
            ';' :
              ConvStr[ i ] := ' ';
            '<' :
              ConvStr[ i ] := ' ';
            '>' :
              ConvStr[ i ] := ' ';
            '=' :
              ConvStr[ i ] := ' ';
            '?' :
              ConvStr[ i ] := ' ';
            '[' :
              ConvStr[ i ] := ' ';
            ']' :
              ConvStr[ i ] := ' ';
          end;
      end;

    PrepareTheString := i;
  end;

(***************************************************************************)

function NGramMatch( const TextPara, SearchStr : string;
  SearchStrLen, NGramLen : Integer; var MaxMatch : Integer ) : Integer;

  var
    NGram : string[ 8 ];
    NGramCount : Integer;
    i, Count : Integer;

  begin
    NGramCount := SearchStrLen - NGramLen + 1;
    Count := 0;
    MaxMatch := 0;

    i := 1;
    while i <= NGramCount do
      begin
        NGram := Copy( SearchStr, i, NGramLen );
        if ( NGram[ NGramLen - 1 ] = ' ' ) and ( NGram[ 1 ] <> ' ' ) then
          Inc( i, NGramLen - 3 ) (* Wird in der Schleife noch erhoeht! *)
        else
          begin
            Inc( MaxMatch, NGramLen );
            if Pos( NGram, TextPara ) > 0 then
              Inc( Count );
          end;
        Inc( i );
      end;

    NGramMatch := Count * NGramLen;
  end;

(***************************************************************************)

function FuzzyMatching( const SearchIn, SearchStr : string ) : extended;

  var
    SStr : string;
    TextPara : string;
    TextBuffer : string;
    TextLen : Integer;
    SearchStrLen : Integer;
    NGram1Len : Integer;
    NGram2Len : Integer;
    MatchCount1 : Integer;
    MatchCount2 : Integer;
    MaxMatch1 : Integer;
    MaxMatch2 : Integer;
    Similarity : extended;
    BestSim : extended;

  begin

    BestSim := 0.0;

    if ( SearchIn <> '' ) and ( SearchStr <> '' ) then
      begin
        SearchStrLen := PrepareTheString( SearchStr, SStr );
        NGram1Len := 3;
        if SearchStrLen < 7 then
          NGram2Len := 2
        else
          NGram2Len := 5;

        TextBuffer := SearchIn;
        TextLen := PrepareTheString( TextBuffer, TextPara ) + 1;
        TextPara := Concat( ' ', TextPara );

        if TextLen < MaxParLen - 2 then
          begin
            MatchCount1 := NGramMatch( TextPara, SStr, SearchStrLen, NGram1Len,
              MaxMatch1 );
            MatchCount2 := NGramMatch( TextPara, SStr, SearchStrLen, NGram2Len,
              MaxMatch2 );
            Similarity := 100.0 * ( MatchCount1 + MatchCount2 ) /
              ( MaxMatch1 + MaxMatch2 );
            if Similarity > BestSim then
              BestSim := Similarity;
          end;
      end;

    RESULT := BestSim;

  end;

end.

[hans ditter]

@ Sir Rufo
Mein Gott ist die Funktion lang... ist der Aufwand wirklich nötig, um 2 Strings miteinander zu vgl??

[stahli]

Meine liefert bei

"sdfsd-fgdfdf Hier.Der.Beispiel.Text-sdf-dff-ddd" : "Hier der Beispiel Text" = 95%
und
"exp_onkelcharliexvid_s06e24" : "Onkel Charlie S06 E24" = 94%


PS: Wie lang die Funktion ist, ist doch egal ;-)
Und ob eine Ähnlichkeit von 0 logisch ist oder nicht, kommt wohl immer auf die jeweiligen Ansprüche an.

[Sir Rufo]

Zitat:

Zitat von hans ditter (Beitrag 1052146)

@ Sir Rufo
Mein Gott ist die Funktion lang... ist der Aufwand wirklich nötig, um 2 Strings miteinander zu vgl??

Wenn Du einen Fuzzy-Vergleich haben möchtest -> JA
Ansonsten -> NEIN

Mit einem Fiat 500 komm ich auch an, mit einem Lambo Diablo auch, macht aber mehr Spaß (gut säuft auch Sprit wie Hulle)
Entscheide was du möchtest ;)

[hans ditter]

Ja, im Prinzip schon, aber ich bin der Ansicht, dass man Probleme mit möglichst wenigen Wörtern umschreibt (das war metaphorisch gemeint... :D), heisst, den Quellcode so schmal wie möglich zu halten.

[Chillkröte]

@stahli, danke für diese Prozeduren: Übereinstimmung von 94%
jetzt muss ich mich durch den code kämpfen, um den zu verstehen

@sir rufo, hans ditter
danke ich werd mir auch die mal angucken

[Sir Rufo]

Ob der entsprechende Such-Algorithmus deinen Ansprüchen genügt kannst du nur herausfinden, wenn du mehrere Suchbeispiele durch die Algorithmen laufen lässt.

Wichtig ist dabei nicht nur Beispiele zu nehmen mit erwarteten Treffern, sondern auch negativ Beispiele, wo ein möglichst geringer Treffer-Wert geliefert werden soll.

Je nach Anwendungsfall kann es auch notwendig sein unterschiedliche Algorithmen zu kombinieren.

Meine Funktion liefert z.B. bei "Peter und der Wolf" und "Peter Wolf und der" 100% Treffer-Quote
Ist ja eben Fuzzy-Logic

Wenn ich solche Treffer nicht haben möchte, dann kann ich die Fuzzy-Suche knicken.

Vielleicht sollten wir mal solche String-Vergleicher sammeln inkl. einer Test-Suite, wo man unterschiedliche Vergleichs-Strings einträgt und dann die Ergebnisse vergleichen und verknüpfen kann.

Dann kann man sich den besten Algorithmus(-Cocktail) raussuchen.

[himitsu]

Es gibt auch noch die Levenshtein-Distanz, welcher die Anzahl der nötigen Änderungen zählt, welche man braucht um aus dem einen den anderen String zu machen.

Je kleiner die Zahl, umso gleicher sind die Strings.

Delphi-Quellcode:

Prozent = 100 * LevenshteinDistanz div Max(Length(Str1), Length(Str2))

.



Auch SoundEx prüft auf gewisse Ähnlichkeiten.



Wenn Groß-/Kleinschreibung egal sind und der Algorithmus dieses mit auswertet, dann halt vorher noch beide String durch AnsiUpperCase jagen.

Wenn Sonderzeichen egal sind und diese ebenfalls vom Algo beachtet werden, dann diese eben vorher entfernen/rausfiltern.

(oder den Algo entsprechend abändern)




Also im Prinzip müßte man erstmal genau definieren was du unter "gleich" verstehst
und daraus leitet sich dann der nötige Algorithmus ab, welchen man verwenden könnte.

[Chillkröte]

ok ich erklär erstmal wofür ich das brauch.
vielleicht wird es dadurch klarer

wie ihr vielleicht schon festgestellt habt geht es um Videos und Filme.
Einige davon könnten in oben genannten Dateinamen abgespeichert worden sein.
Dazu habe ich eine Liste mit den normalen Dateinamen.

Diese sollen jetzt verglichen werden.
Demnach wäre die Fuzzy-Funktion nicht brauchbar. Sie liefert zwar ein relativ positives Ergebnis, aber die Reihenfolge wird dabei nicht betrachtet.

Reihenfolge und Zeichen sind demnach ausschlaggebend

die groß- und kleinschreibung spielt durch AnsiUpperCase bzw LowerCase keine Rolle
genauso wie sonderzeichen wie punkte oder unterstriche
das müsste man dann anpassen

[hans ditter]

hm, Groß- und Kleinschreibung ist aber schon wichtig, wenn du 2 Dateinamen vergleichen willst...
Es könnte ja sein, dass sich jemand vertippt hat und statt 'Bourne Ultimatum', 'Bourne uLtimatum' geschrieben hat. Dann weicht die Gleichheit schon ab, obwohl es sich (wahrscheinlich) um den gleichen Film handelt...

[mkinzler]

Dann könnte mn ja vorher beide Strings in Groß- oder Kleinbuchstaben wandeln.
U.U. wäre auch SoudEx dass richtige

[Chillkröte]

wenn man das eintippt und gleichzeitig die Konvertierung beider strings zu
BOURNE ULTIMATUM stattfindet ist die gleichheit wieder gegeben

es geht eig nur darum, ob der dateiname "blablablaaaaa-Film[oder Video]name.blablabla" dem Film- oder Videonamen aus der liste gleicht

[mkinzler]

Zitat:

und gleichzeitig die Konvertierung beider strings zu
BOURNE ULTIMATUM stattfindet ist die gleichheit wieder gegeben

Das meinte ich mit in Großbuchstaben wandeln

[Chillkröte]

dein eintrag hab ich gar nicht gesehen, sorry
ok danke dann werd ich mir auch das nochmal angucken

[himitsu]

In diesem Fall würde ich wohl Levenshtein-Distanz etwas abwandeln, so daß zusätzliche Zeichen, im Dateinamen, eine geringere Wertigkeit besitzen.

[mkinzler]

Es kommt darauf an, ob die Ähnlichkeit im Geschriebenen oder in der der Aussprache untersucht werden sollen

[Chillkröte]

wie meinst du das?

[DeddyH]

Maier -> Meier -> Meyer -> Mayer

[Sir Rufo]

Im Anhang mal ein Vergleicher für Fuzzy und StahliSuche

Als Ergebnis wird die Ähnlichkeit und (in Klammern) die benötigten Ticks zum Berechnen

Zum Compilieren sollte der Ausgabepfad auf "..\bin" gestellt werden und der Suchpfad sollte um "..\lib" erweitert werden.

In der Datei "bin\Data.txt" kannst du dann die gewünschten Vergleichs-Texte eingeben und vergleichen lassen.

Code:

SearchIn,SearchTxt
Hier wird gesucht,Das hier wird gesucht
...,...

[Chillkröte]

@mkinzler
achso, ne das spielt eigentlich keine rolle

@sir rufo
danke^^

Also folgende Funktionen wären möglich:
1. Stahli-Suche
2. Fuzzy-Vergleich
3. SoudEx?
4. Vorschlag von hans ditter
5. Levenshtein-Distanz (bisschen umwandeln)
6. Funktion von den Schweizern

1. betrachtet die Reihenfolge & Zeichen
2. betrachtet die Zeichen
3.-5. weiß ich nicht (ungetestet)
6. betrachtet Reihenfolge, nur sinnvoll, wenn die Länge der Strings gleich ist bzw. wenn sie gleich anfangen

edit: SoundEx hierfür nicht geeignet, da die strings unterschiedlich ausfallen können, unterschiedliche längen, zusatzzeichen besitzen und mit sonderzeichen und ähnlichen versehen sind