Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Zypressen Hügel

Junior Schreiberling

  • "Zypressen Hügel" started this thread

Posts: 244

Date of registration: Dec 22nd 2001

1

Monday, October 14th 2002, 8:39pm

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)
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Monday, October 14th 2002, 8:49pm

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
  • Send private message

Zypressen Hügel

Junior Schreiberling

  • "Zypressen Hügel" started this thread

Posts: 244

Date of registration: Dec 22nd 2001

3

Monday, October 14th 2002, 9:54pm

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)
  • Send private message

paradroid

Junior Schreiberling

Posts: 231

Date of registration: Feb 28th 2002

4

Tuesday, October 15th 2002, 8:27am

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 #
  • Send private message

paradroid

Junior Schreiberling

Posts: 231

Date of registration: Feb 28th 2002

5

Tuesday, October 15th 2002, 10:37am

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 #
  • Send private message