Vergleichen von 2 Strings (prozentual)

[Chillkröte]

das problem ist aber noch bei solchen strings

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.

[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??

[Sir Rufo]

Zitat von hans ditter:

@ 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

[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.

[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... ), heisst, den Quellcode so schmal wie möglich zu halten.

[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.

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...