Algorithmus für "unscharfe Suche" gesucht



  • Hallo!

    Ich soll demnächst in der Schule einen Vortrag halten. Dabei soll es um einen Algorithmus zur "unscharfen Suche" gehen. Ich soll den Algorithmus erklären und ein kleines Beispiel (in C++) vorführen.

    Mein Problem, ich google mich zu Tode, es ist die Suche nach der Nadel im Heuhaufen.

    Hat jemand einen Link, wo ich solche einen Algorithmus finden kann? Wenn's geht ein einfacher, weil ich muss ihn ja noch erklären und meine Zuhörer müssen ihn dann auch verstehen.

    Besten Dank!

    Ralph



  • In Deinem Fall würde ich mich gar nicht auf fertige Algorithmen abstützen, die guten arbeiten mit Neuronalen Netzen und Fuzzy, das kapiert kein As im Rahmen Deiner Präsentation.

    Eine einfache Idee kann so aussehen:

    Du tokenisierst einen String nach einem einfachen Schema:

    - ie, i wird zu i
    - ei, ai, ay, ey wird zu ei
    - y, ü wird zu i
    - mm, m wird zu m
    - nn, n wird zu n
    - s, ß, ss wird zu s
    - sch, st, sp wird zu sch
    - d, dd, t, tt wird zu d
    - ä, ae, e wird zu e
    - usw, denk Dir noch mehr aus, am besten ein Alphabet aufschreiben und nach solchen Aussprachemustern suchen.

    Diese Umcodierung in eine Funktion packen.

    Und dann wandelst Du Suchstring und den String aus Deinem Datenvorrat mit dieser Funktion um und vergleichst nicht Originaldaten, sondern die umcodierten Daten auf Gleichheit.

    Fertig ist Deine Demo einer "unscharfen phonetischen Suche". Als Beispiel führst Du vor, daß Meyer auch gefunden wird, wenn man nach Maier sucht.

    Alle sind glücklich, und verständlich bleibt es auch.

    Dann erklärst Du am Ende, daß diese Funktion im Regelfall mit komplexen Datenbanken und auf Basis von Neuronalen Netzen, künstlicher Intelligenz oder Fuzzy-Logik basieren.

    => Jeder versteht wie die Idee ist.



  • Hallo!

    Ich hab nach langem Suchen auch im I-Net was dazu gefunden http://vhb.fh-regensburg.de/ad/kursdateien/pdf/ad_script.pdf, was auch in Deine Richtung geht.

    Wenn ich Dich jetzt richtig verstanden habe, dann müßte dieser Vergleich immer pro Wort stattfinden?!? Oder anders gesagt, wenn ich einen ganzen Text durchsuchen möchte, dann brauch ich noch eine Funktion, die mir den Text in einzelne Wörter zerlegt (z.B. anhand von Leerzeichen) und diese dann einzeln zum prüfen übergibt?

    Ralph



  • Hi,

    in welcher Klasse und welchem Fach sollst du das denn machen?

    ChrisM



  • Ich dachte jetzt eher an eine kleine Datenbank mit Vornamen, Namen und Adressen... aber für Texte muß man es so machen wie Du sagst und zerlegen.



  • ChrisM schrieb:

    Hi,

    in welcher Klasse und welchem Fach sollst du das denn machen?

    ChrisM

    Tagsüber muss ich leider arbeiten aber aus reinem privatem Interesse und natürlich wegen der Kariere geh ich abends zur Schule und mache dort meinen Techniker in Informatik, Schwerpunkt technische Informatik. Und das Fach nennt sich, so glaube ich zumindest, strukturierte Programmierung oder so. Letztendlich halt C++ lernen.

    Ralph



  • Marc++us schrieb:

    Ich dachte jetzt eher an eine kleine Datenbank mit Vornamen, Namen und Adressen... aber für Texte muß man es so machen wie Du sagst und zerlegen.

    Gut nun kenn ich mein Ziel 😉

    Danke! Ralph



  • Zum Suchen ist es zum Beispiel auch sinnvoll f durch ph zu ersetzen. Wegen den Delfinen oder such mal in der Bibel nach Josef...



  • Wenn ich das richtig verstanden hab aus den obigen Beispielen, dann geht's darum eine Suchfunktion zu entwerfen die nicht auf die exakte Schreibweise achtet, oder wie ?

    Zu dem Thema würde mir spontan SoundEx einfallen, einfach mal googlen, oder das Beispiel unten ansehen (hab ich vor einiger Zeit mal irgendwo gefunden, funktioniert aber super):

    void CPersonFindDlg::Soundex(char* name, char* code)
    {
    	char *zeichen = "abcdefghijklmnopqrstuvwxyz";
    	char *codes =   "0123012*02245501262301*202";
    	char firstcode;
    	int trenner=0;
    
    	code[0]=name[0];
    
    	for (int k=0;k<26;k++)
    	{
    		if (name[0]==zeichen[k])
    		{
    			firstcode=codes[k];
    			break;
    		}
    	}
    
    	int position=1;
    
    	for (int i=1;name[i]!='\0' && position<4;i++)
    		for (int k=0;k<26;k++)
    			if (zeichen[k]==name[i])
    			{
    				if (codes[k]=='*') break;
    
    				if (codes[k]=='0')
    				{
    					trenner=1;
    					break;
    				}
    
    				if (trenner==0)
    				{
    					if (position==1 && firstcode==codes[k]) break;
    
    					else if (codes[k]==code[position-1]) break;
    				}
    
    				code[position]=codes[k];
    				position++;
    				trenner=0;
    				break;
    			}
    
    			for (;position<4;position++) code[position]='0';
    
    			code[4]='\0';
    }
    


  • Hallo!

    Das SoundEx klingt auch nicht schlecht. Ich werd mal den Lehrer fragen, was ihm mehr zusagt.

    Erstmal soweit besten Dank!

    Ralph


Log in to reply