Sie sind nicht angemeldet.

Zypressen Hügel

Junior Schreiberling

  • »Zypressen Hügel« ist der Autor dieses Themas

Beiträge: 244

Registrierungsdatum: 22.12.2001

1

14.10.2002, 20:39

java... strings vergleichen?

hallo, ihr chefprogrammierer da draussen. ist irgendjemand schon mal auf eine art algorithmus gestoßen, mit dessen hilfe die ähnlichkeit von strings verglichen oder bewertet werden könnte und kann den dann auch noch erklären? es geht mir insbesondere darum, eine liste von namen bzw. textbausteinen (von leuten getippt, die froh sein können, wenn sie sich nicht bei ihrem eigenen namen verschreiben) mit einer datenbank abzugleichen und ähnliche textbausteine / namen einander zuzuordnen nach dem grad ihrer ähnlichkeit... man, kann ich vielleicht komplizierte sätze schreiben.

ich bin bereits soweit, fehlende oder zuviel getippte zeichen und positionsfehler einzelner buchstaben innerhalb eines wortes bewerten zu können, aber ich suche immer noch verzweifelt nach einem richtig eleganten algorithmus dafür. hat jemand ne idee?
Man kann auch ohne Spass Alkohol haben 8)

  • »Joachim« ist männlich

Beiträge: 2 863

Registrierungsdatum: 11.12.2001

Wohnort: Hämelerwald

Beruf: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

14.10.2002, 20:49

Tippfehler und Dreher sind eine Sache, aber falls du eher auf fehlertolerante Suche bezüglich der Aussprache Wert legst (was IMHO mehr Sinn macht, da es das häufigere Problem ist), dann sollte dir das Stichwort "Soundex-Algorithmus" weiterhelfen.

So wird dann ein Herr Schmidt auch dann gefunden, wenn man nach "schmitt" sucht.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Zypressen Hügel

Junior Schreiberling

  • »Zypressen Hügel« ist der Autor dieses Themas

Beiträge: 244

Registrierungsdatum: 22.12.2001

3

14.10.2002, 21:54

danke, joachim. ohne schleimen zu wollen, aber dass man sich auf deine hilfe verlassen kann, war ja klar :)

wobei ich zugeben muss, dass ich keinen bock habe, den soundex-algo zu implementieren, aber durch den tipp bin ich auf "plain string similarity" gestoßen (tu-berlin). ma schaun, ob sich der so leicht implementieren lässt wie ich mir das vorstelle...
Man kann auch ohne Spass Alkohol haben 8)

paradroid

Junior Schreiberling

Beiträge: 231

Registrierungsdatum: 28.02.2002

4

15.10.2002, 08:27

Ich werfe hier nochmal ein paar Stichworte in den Raum:

Hamming-Abstand
Levenshtein-Abstand
Edit-Distance

Sollte erstmal genug sein ;)

Wer mehr wissen will, sollte vielleicht die Vorlesung "Zeichenketten" bei Prof. Parchmann in betracht ziehen.

# transmission terminated #

paradroid

Junior Schreiberling

Beiträge: 231

Registrierungsdatum: 28.02.2002

5

15.10.2002, 10:37

Ich komme ja nicht umhin: So kompliziert ist Soundex (in der Englischen Variante) nun auch nicht. Hier meine C++-Referenz-Implementation:

#include <string>
#include <iostream.h>

int main(int argc,char **argv)
{
string key(argv[1]);

int i;
char start=key[0];

for(i=0; i<key.size(); i++)
{
switch(key)
{
case 'B': key[i]='1'; break;
case 'b': key[i]='1'; break;
case 'F': key[i]='1'; break;
case 'f': key[i]='1'; break;
case 'P': key[i]='1'; break;
case 'p': key[i]='1'; break;
case 'V': key[i]='1'; break;
case 'v': key[i]='1'; break;

case 'C': key[i]='2'; break;
case 'c': key[i]='2'; break;
case 'G': key[i]='2'; break;
case 'g': key[i]='2'; break;
case 'J': key[i]='2'; break;
case 'j': key[i]='2'; break;
case 'K': key[i]='2'; break;
case 'k': key[i]='2'; break;
case 'Q': key[i]='2'; break;
case 'q': key[i]='2'; break;
case 'S': key[i]='2'; break;
case 's': key[i]='2'; break;
case 'X': key[i]='2'; break;
case 'x': key[i]='2'; break;
case 'Z': key[i]='2'; break;
case 'z': key[i]='2'; break;

case 'D': key[i]='3'; break;
case 'd': key[i]='3'; break;
case 'T': key[i]='3'; break;
case 't': key[i]='3'; break;

case 'L': key[i]='4'; break;
case 'l': key[i]='4'; break;

case 'M': key[i]='5'; break;
case 'm': key[i]='5'; break;
case 'N': key[i]='5'; break;
case 'n': key[i]='5'; break;

case 'R': key[i]='6'; break;
case 'r': key[i]='6'; break;

case 'H': if(i>0) { key.erase(i,1); i--; } break;
case 'h': if(i>0) { key.erase(i,1); i--; } break;
case 'W': if(i>0) { key.erase(i,1); i--; } break;
case 'y': if(i>0) { key.erase(i,1); i--; } break;

default: key[i]='y'; break;
}
}

for(i=0; i<key.size(); i++)
{
if(i<key.size()-1 && key[i]==key[i+1])
{
key.erase(i,1);
i--;
}
}

key[0]=start;

for(i=1; i<key.size(); i++)
{
if(key[i]=='y')
{
key.erase(i,1);
i--;
}
}

while(key.size()<4) key+='0';
if(key.size()>4) key=key.substr(0,4);

cout<<key<<endl;

return 0;
}

# transmission terminated #