2 String zeichenweise vergleichen (nach Wahrscheinlichkeit)

Hallo zusammen,

ich hoffe Ihr könnt' mir weiterhelfen, ich stehe gerade voll auf dem Schlauch und weiß nicht mehr weiter...

Ich habe hier 2 Strings, es sind eigentlich Straßennamen aus einem Straßenverzeichnis. Nun haben Straßenverzeichnisse so die Angewohnheit, dass die Straßen teilweise nicht eindeutig da drin stehen und ich nach einer bestimmten Wahrscheinlichkeit filtern will.

Sprich:
Wenn String 1 zu 95% mit String 2 übereinstimmt dann Erfolg, wenn nicht dann Fehler.

Also habe ich nun meine 2 Strings:

string 1="Musterstraße"
string 2="Musterstrasse"

Hat jemand von euch eine Idee, wie man so einen Algorithmus entwickeln kann. Ich war schon soweit und habe eine Schleife geschrieben welche mir zeichenweise den String vergleicht. Diese Schleife geht auch so lange gut, bis er an die fehlerhafte Stelle kommt. Mir fehlt da irgendwie der grundsätzliche Durchbruch des ganzen:

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

double string_vergleich(string string1, string string2)
{
     int i=0;  
     double wahrscheinlichkeit=0;
     double stimmt=0;
     double zeichen=0;

     if (string1.size()<string2.size())
     {
         for(i=0;i<string1.size();i++)
         {
              if (string1[i]==string2[i]) stimmt++;
              zeichen++;
         }
     }

     else
     {
         for(i=0;i<string2.size();i++)
         {
              if (string2[i]==string1[i]) stimmt++;
              zeichen++;
         }
     }

     wahrscheinlichkeit=stimmt/zeichen*100;

     return wahrscheinlichkeit;
}

int main(int argc, char *argv[])
{
    string test1="ADOLFHOYERSTRAßE";
    string test2="ADOLFHOYERSTRAßE";
    double wahrscheinlichkeit=90;
    double ergebnis=0;

    ergebnis=string_vergleich(test1,test2);

    system("PAUSE");
    return EXIT_SUCCESS;
}

Das Programm läuft bei 100%tiger Übereinstimmung durch, sollten die strings nicht übereinstimmen, dann hängt die Wahrscheinlichkeit von der fehlerhaften Stelle ab, je weiter vorne das passiert, umso geringer ist die Wahrschienlichkeit.

Kann mir da vielleicht jemand einen Tip geben, wie man 2 Strings zeichenweise vergleicht?

Ich danke euch...

cya
Der Marco

Der Marco schrieb:

[...]Kann mir da vielleicht jemand einen Tip geben, wie man 2 Strings zeichenweise vergleicht?[...]

Benutze operator[] und dann die char-Vergleichsoperatoren.

*D*Evil

guck dir mal Game Programming Gems 6 an ... da steht genau darüber ein wunderschöner Artikel ... kannst sogar den Grad der Ähnlichkeit, nach dem gesucht werden soll, angeben.

ich danke euch 2 erstmal für eure Antworten, ich werde mir das alles mal anschauen...

cya
der Marco

GreyHound

na die Geschichten wie ß=ss, ä=ae, ö=oe etc. kannste ja ohne wahrscheinlichkeit durchprüfen wenn so ein Zeichen/Kombination in der Liste/Eingabe vorkommt. Und wenn dann immer noch nix gefunden wird noch wegen möglichen Tippfehlern deine Prozentuale Gleichheit benutzen.

Bindestriche zum Beispiel in der Eingabe und beim Vergleichen mit der Liste gleichma durch "" ersetzen. Da kannste noch mit recht genauen Mitteln die Trefferquote erhöhen.

Str. str. Strasse, Straße vielleicht auch ganz aus dem Vergleich nehmen.

Dann vergleichst nur noch Haupt[str.] mit Haupt[straße] ohne dass die Schreibweise ne Rolle spielt , you know what i mean?

Th

Wenn du es (professionell) angehen willst, solltest du dir mal Edit-Distanzen anschauen (ich habe z.B. auf dessen Grundlage meine Diplomarbeit zum Thema Pattern-Matching in Gen-Sequenzen geschrieben).

http://de.wikipedia.org/wiki/Levenshtein-Distanz

Hallo,

also das mit der Großschreibung und der Bereinigung des Straßennamens und aller Sonderzeichen habe ich bereits gemacht.

Die 2 Strings in dem Quelltext sind bereits bereinigt, da ist der ganze Schrott schon rausgeflogen.

Ich habe mir testweise einen Algorithmus geschrieben, welcher auf 100%tige Übereinstimmung prüft und die Fehler dann ausgibt. Unter Berücksichtung dass ich alle Straßennamen bereinigt habe konnte ich von 14700 Straßennamen 13700 Straßennamen zuordnen und finden.

Bleiben also noch 1000 übrig, die entweder jemand manuell durchschauen müsste oder die ich noch mit einem Algorithmus filtern könnte...

Aber ich denke die wird jemand manuell durchschauen...

Ich danke euch für eure Hilfe...

cya
Der Marco

Wobei die Levenshtein-Distanz ist ja eigentlich genau das was ich suche.

cya