Announcement

**Jens Schumann** · 11.05.2003, 18:46

Hallo Stephan, 
das Zauberwort heisst SoundEx. Der SoundEx-Algorithmus reduziert einen 
beliebigen String auf 4 Zeichen. Diese 4 Zeichen bestehen aus dem Anfangsbuchstaben 
des Strings und einem 3 stelligen Zahlencode. 
Dadurch ist es z.B. m�glich durch die Eingabe von Meier alle Meyer, Maier, Mayer usw zu finden. 
Die Beschreibung des SoundEx haben ich im Internet gefunden. Daraufhin habe ich mir folgende 
Unit gebastelt. Ob ich den Algorithums absolut fehlerfrei hinbekommen habe weiss ich 
nicht so genau. Jedoch sind die Resultate die ich in meinen Projekten damit erziele 
zu meiner vollsten Zufriedenheit. 
<pre>
unit soundex;
interface
function SoundEx_Simple(const S : String) : String;
function SoundEx_Komplex(const S : String) : String;
function FilterCapitalLetters(const S : String) : String;
function ReplaceUmlaute(const S : String) : String;
implementation
uses Sysutils;
Type
TLArray = Array [65..90] of Byte;
const
// A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y, Z
LArray : TLArray = (0,1,2,3,0,1,2,0,0,2,2,4,5,5,0,1,2,6,2,3,0,1,0,2,0 ,2);
function FilterCapitalLetters(const S : String) : String;
var
iCnt : Integer;
begin
Result:=AnsiUpperCase(S);
iCnt:=1;
While iCnt<=Length(Result) do
begin
If (Ord(Result[iCnt])<65) OR (Ord(Result[iCnt])>90) then
Delete(Result,iCnt,1)
else
Inc(iCnt);
end;
end;
function ReplaceUmlaute(const S : String) : String;
begin
Result:=S;
// Teste ob Sonderzeihen enthalten sind und ersetze sie ->
Result:=StringReplace(Result,'�','AE',[rfReplaceAll]);
Result:=StringReplace(Result,'�','OE',[rfReplaceAll]);
Result:=StringReplace(Result,'�','UE',[rfReplaceAll]);
Result:=StringReplace(Result,'�','ae',[rfReplaceAll]);
Result:=StringReplace(Result,'�','oe',[rfReplaceAll]);
Result:=StringReplace(Result,'�','ue',[rfReplaceAll]);
Result:=StringReplace(Result,'�','SS',[rfReplaceAll]);
// <- Teste ob Sonderzeihen enthalten sind und ersetze sie
end;
function SoundEx_Simple(const S : String) : String;
var
sTmp : String;
iCnt : Integer;
jCnt : Integer;
Entry : Byte;
LetterArray : TLArray;
begin
Result:='';
Entry:=0;
If S='' then Exit;
LetterArray:=LArray;
sTmp:=AnsiUpperCase(S);
Result:=sTmp[1];
iCnt:=2;
Entry:=LetterArray[Ord(sTmp[1])];
While (iCnt)<=Length(sTmp) do
begin
If LetterArray[Ord(sTmp[iCnt])]=Entry then // Ist der n�chste Buchstabe in der gleichen Kategorie ?
Inc(iCnt) // Wenn ja, dann �berspringen
else
Break;
end;
While iCnt<=Length(sTmp) do
begin
If LetterArray[Ord(sTmp[iCnt])]<>0 then
begin
Result:=Result+IntToStr(LetterArray[Ord(sTmp[iCnt])]);
Entry:=LetterArray[Ord(sTmp[iCnt])];
While (iCnt+1)<=Length(sTmp) do
begin
If LetterArray[Ord(sTmp[iCnt+1])]=Entry then // Ist der n�chste Buchstabe in der gleichen Kategorie ?
Inc(iCnt) // Wenn ja, dann �berspringen
else
Break;
end;
end;
If Length(Result)=4 then // SoundExe sind nie l�nger als 4 Zeichen
Break;
Inc(iCnt);
end;
While Length(Result)<4 do // Wenn SoundExe k�rzer als 4 Zeichen sind, dann wird der Rest mit 0 aufgef�llt
Result:=Result+'0';
end;
function SoundEx_Komplex(const S : String) : String;
begin
Result:=StringReplace(S,' ','',[rfReplaceAll]);
Result:=ReplaceUmlaute(Result);
Result:=FilterCapitalLetters(Result);
Result:=SoundEx_Simple(Result);
end;
end.
</pre>
SoundEx_Simple wandlet den String direkt um. 
SoundEx_Komplex wandelt vor der Berechnung alle Zeichen des Strings in Gro�buchstaben (filtert danach alles heraus was kein Gro�buchstabe ist (z.B. Ziffern)) 
um. Zus�tzlich werden noch alle Sonderzeichen ersetzt. 
<

**Jens Schumann** · 11.05.2003, 18:47

Ich verwende den SoundEx um fehlertolerant nach Namen zu suchen. Daf�r spendiere ich der Tabelle ein zus�tzliches Feld 
f�r den SoundEx des Namens. 
Wenn Du fehlertolerant innerhalb einer Beschreibung suchen m�chtest, m�sstest Du f�r jedes Wort der Beschreibung einen SoundEx bilden. 
Wie sich das auf die Performance auswirkt, w�re zu testen.<br&gt

**Bernd Schulz** · 12.05.2003, 08:33

Hallo! 
Soundex hat so seine kleinen Probleme mit nicht englischsprachigen Namen. Der deutsche Meier mit allen seinen Auspr�gungen wird da gerne mal abweichend kodiert. 
Ebenso werden die (nicht g�nzlich unwichtigen) Endsilben praktisch vollkommen ignoriert. 
Als Quelle sei hier auf http://www.las-inc.com/soundex/ verwiesen. 
 
Eine Alternative sind Double Metaphone, die etwas mehr auf Sprachspezifika eingehen. Eine L�sung f�r MS SQL ist zu finden unter: 
http://cpan.cbn.net.id/modules/by-category/11_String_Lang_Text_Proc/Text/ 
 
BYE BERN

**Martin Krause** · 12.05.2003, 08:50

Hallo,

die Anmerkung von Bernd ist zwar richtig, aber ich habe mal soundex bei einer Gro�en Kundendatenbank, mit Email-Bestellung eingesetzt,
also d.h.: email importieren, Besteller-Angaben in der DB suchen, wenn gefunden, Kundennummer �bernehmen, sonst neue Kundennummer.
und ich mu�te sagen, der Fehler quozient lag unter 0,01 % und das finde ich schon richtig gut.

Also w�rd ich sagen : probieren geht �ber studieren. :-)

Gru� Marti

**Bernd Schulz** · 12.05.2003, 21:48

Hallo! 
Also die Probleme waren nicht bei Meier (das hatte ich wohl falsch in Erinnerung) sondern z.B. bei Namen mit z oder tz :
<PRE>
Name Soundex Double
Schulz S420 SLTS
Schultz S432 SLTS
Schultzenheimer S432 SLTSN
Schulzenheimer S425 SLTSN
</PRE>
Die Performance ist bei Soundex besser, da "weniger" gemacht wird. 
Aber die Treffer sind sprachlich bei DoublemetaPhone besser. 
Gerade aus diesem Grund haben wir unsere Anwendung (200-300 tausend Adressen, verschlagwortete Manuskripte ca. 50 tausend) auf DoubleMetaPhone umgestellt und sind eigentlich sehr zufrieden. 
BYE BERN

**Stephan Schneider** · 14.05.2003, 09:15

Hallo,

Danke f�r die rege Beteiligung.

Ich habe z.B. 50 Tabellen, die alle ein Feld namens Beschreibung haben. Jede dieser Tabellen hat eine bestimmte Anzahl an Datens�tzen (u.U. > 50000). Der Benutzer gibt einen Begriff ein und nun beginnt die gro�e Suche: Wie w�rde aber die Suche mit Soundex/Metaphone �ber die Tabellen/Datens�tze konkret im Code aussehen? Sind diese Iterationen nicht sehr laufzeitbeintr�chtigend?

Stepha

**Bernd Schulz** · 14.05.2003, 11:01

Je nachdem, wie viel Wartezeit Du Deinen Anwendern zumuten willst kannst Du entweder: 
(In der Beschreibung phonetisch durch soundex oder DoubleMetaPhone ersetzen) 
1. Ein Feld Beschreibung_Soundex zuf�gen und nun alle Worte aus Beschreibung in phonetisch umwandeln und den "phonetischen"-Satz im Feld Beschreibung_Phonetisch ablegen. Zugriff via select * from table where beschreibung_phonetisch like '%'+MeinPhonetischesSuchwort+'%'. Das kann dann schon mal etwas dauern!!! 
 
2. Eine Wortdatenbank f�r die Beschreibung anlegen. Jedes Wort aus der Beschreibung in phonetisch umwandeln und in der Wortdatenbank mit Referenz auf die Herkunft (Tabelle und Datensatz) eintragen. Dauert etwas l�nger beim Aufbau ist dann aber im Zugriff sehr fix. (Plattenplatz sollte eine untergeordnete Rolle spielen) 
 
Wir verwenden Version 2, die unter MS SQL 2000 mit Hilfe von Triggern und StoredProcs trotz allem akzeptabel fix bei der Erfassung ist. 
 
BYE BERN

**VolkerJ** · 16.05.2003, 09:04

Hallo Bernd, 
ich habe ein �hnliches Problem wie Stephan, ich habe Datenbank f�r die Medizin und nun soll der Benutzer ein Schlagwort eingeben und als Ergebnis alle �hnlichen Eintr�ge wie bei Google angezeigt bekommen.
Bin gerade dran den Soundex einzubinden und zu testen, kannst du mir mehr Infos zu dem Phonetischen ... geben ?
Es sollte halt schon eine exakte Abfrage werden.

 
Gruss Volke

**Bernd Schulz** · 16.05.2003, 11:00

Hallo! 
Ich wei� jetzt nicht so genau, was Du wissen m�chtest?!? 
Source, Probleme, Quellen im Internet und Kurzanleitungen f�r die Programmierung sind hier im Thread eigentlich gesammelt verf�gbar. 
Google liefert eniges an Quellen, wenn man nach Soundex oder DoubleMetaPhone (manchmal auch double metaphone) sucht. 
Was genau fehlt Dir denn noch? 
BYE BERN

**Stephan Schneider** · 16.05.2003, 13:13

Danke f�r die Diskussion!

@Bernd: Deine Beispiele zielen auf eine �nderung des Datenmodells ab, eigentlich etwas, was ich vermeiden m�chte. Jedesmal wenn ein Beschreibungstext gepostet wird, muss das Soundex-Pendant in das entsprechende Feld geschrieben werden. Geht mal ein Index auf eine Beschreibung verloren, ist eine Reorganisation n�tig. Aus meiner Sicht ein enormer Aufwand.

Grunds�tzlich w�rde beim Suchen eine Iteration ablaufen (Pseudocode):<pre>
for I := 0 to Tabellen - 1 do begin
S := SoundEx(Tabelle[I].Beschreibung);
if Vergleichsalgorithmus(S, Suchstring) = Ergebnis then...
end;</pre>

W�rde diese Iteration nicht die Performance dr�cken? Als Vergleichsalgorithmus w�rde ich die Damerau-Levenshtein-Metrik nehmen. Ich habe aber hier leider keine Erfahrungswerte.

Stepha

**VolkerJ** · 16.05.2003, 14:38

Hi,
hat jemand die fertige udf von Soundex da ?
Bei mir l�uft die nicht.
 
Wenn ja bitte an 
[email protected] 
mailen. 
Danke Volke

**VolkerJ** · 16.05.2003, 16:05

Hi, 
habe die Soundex.dll nun zum laufen bekommen aber bin etwas entt�uscht. 
Als Test habe ich mal 4 Datens�tze mit dem Name "Daniel" eingef�gt. 
1. Daniel 
2. Daiel 
3. Danie 
4. aniel 
5. Danielr 
Result tat war nur 1 = Daniel 
Gibt es keine andere M�glichkeit noch �hnlichkeiten zu suchen ? 
 
Volke

**Bernd Schulz** · 17.05.2003, 17:46

@Stephan 
Enth�lt das Feld Beschreibung nicht einen kompletten deutschen Satz?!?! 
Wie willst Du denn eine �berpr�fung in einer (auch nur halbwegs) annehmbaren Zeit hinbekommen, ohne die DB zu erweitern? 
Damerau-Levenshtein-Metrik: das war mir zu heftig. Hast Du da jetzt Erfahrungen mit? Welche Ergebnisse bekommt man denn da so? 
Hattest Du nicht gesagt, da� Du Oracle verwendest? Da gibt doch mit absoluter Sicherheit Trigger und alles andere was man so braucht, oder?!? Einer Realisierung allein auf Basis der Datenbank sollte dann doch kein Problem sein. Deine Bedenken mit dem verlorenen Index sind dann doch nicht meht so relevant?!? 
Und immer allerschlimmsten Fall l��t sich bei Realisierung mit einem Update Trigger der Index sehr fix wieder aufbauen. update tabelle set beschreibung = beschreibung und los gehts! 
BYE BERN

**Bernd Schulz** · 17.05.2003, 17:55

@Volker 
Ich nehme mal an, da� Du InterBase verwendest oder? 
Klar gibt es noch andere M�glichkeiten phonetisch zu suchen : 
Soundex 
DoubleMetaPhone 
Damerau-Levenshtein-Metrik 
sind da sicherlich nur einige M�glichkeiten. 
(Sieh Dir mal diese komplette Diskussion an) 
Deine Probleme mit soundex kann Du auch noch mal in meinem geposteten Link weiter oben wiederfinden. 
Dort ist auch der Link zu DoubleMetaPhone. Die stored procedure l��t sich eigentlich recht einfach lesen und es sollte nicht zu schwer sein mal eine Delphi Funktion daraus zu zaubern. 
Ansonsten bleibt dann selbermachen f�r eine phonetische Suche sch = s; tz = z; ss=s usw.. 
Es hilft �brigens immer sich mal die Ergebnisse von phonetischen Funktionen direkt anzusehen. Das wird Dir bei Deinem Daniel Beispiel sicherlich weiterhelfen! 
BYE BERN

Announcement

Fehlertolerante Schlagwortsuche

Fehlertolerante Schlagwortsuche

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment