[QUIZ#1] Unscharfe Suche

[Matthias Reitinger]

Quiz #1
Unscharfe Suche

Regeln
Die Regeln und der Ablauf der Quizrunde können wie immer in der entsprechenden Ankündigung eingesehen werden. Bitte lest sie euch aufmerksam durch, da sie alle wichtigen Informationen enthält.

Abgabe
Die Abgabe erfolgt wie immer im Abgabeforum. Abgabefrist ist Sonntag, der 21. September 2008 um ca. 20 Uhr.

Das Problem
Der Suchmaschinenbetreiber Hupf entwickelt zur Zeit einen neuen Browser namens "Titan". Als "Killerfeature" soll der Benutzer mit der browserinternen Suchfunktion auch eine sogenannte unscharfe Suche durchführen können. Deine Aufgabe besteht nun darin, einen entsprechenden Algorithmus für einen Prototypen des Browsers zu implementieren.

Die Unschärfe entsteht dadurch, dass es keine exakte Übereinstimmung geben muss, sondern nur alle Zeichen des Suchbegriffes in der gegebenen Reihenfolge in der Zeichenfolge vorkommen müssen. Als Beispieldatensatz steht eine Liste US-amerikanischer Präsidenten zur Verfügung. Das Programm soll diese Liste einlesen und alle Einträge ausgeben, die durch eine unscharfe Suche nach dem als Kommandozeilenparameter übergebenen Begriff gefunden werden.

Erweiterung
Als zusätzliches Feature sollen in der Ausgabe die übereinstimmenden Teile markiert werden (siehe Beispiele). Die Implementierung dieser Erweiterung ist euch freigestellt.

Beispiele
Eingabe:

George Bush

Erwartete Ausgabe (einfach):

George H. Bush
George W. Bush

Erwartete Ausgabe (erweitert):

<George> H. <Bush>
<George> W. <Bush>

Eingabe:

JFK

Erwartete Ausgabe (einfach):

John F. Kennedy

Erwartete Ausgabe (erweitert):

<J>ohn <F>. <K>ennedy

Eingabe:

oooo

Erwartete Ausgabe (einfach):

Theodore Roosevelt
Woodrow Wilson

Erwartete Ausgabe (erweitert):

The<o>d<o>re R<oo>sevelt
W<oo>dr<o>w Wils<o>n

Vielen Dank an Gumbo für die Einsendung dieser Aufgabe!

 

[OnlyFoo]

Die Suche nach oooo sollte auch noch Woodrow Wilson ausspucken.

 

[Back2toxic]

Grover Cleveland steht 2 mal in der Liste, wundert euch also nicht falls dieser Name doppelt in euren Ergebnissen auftaucht

 

[KD3]

Soll die Suchanfrage über Datei oder Datenbank laufen?

 

[Alexander Schuc]

Soll die Suchanfrage über Datei oder Datenbank laufen?

Da die Aufgabenstellung von einem fiktiven Browser ausgeht, wäre es über eine eingelesene Datei wohl sinnvoller.

 

[Gumbo]

Soll die Suchanfrage über Datei oder Datenbank laufen?

Es geht um die Implementierung des Suchalgorithmus. Die Basisdaten können deswegen als bereits in einer Variable des bevorzugten Typs gegeben betrachtet werden.

 

[FBIagent]

Erweiterung
Als zusätzliches Feature sollen in der Ausgabe die übereinstimmenden Teile markiert werden (siehe Beispiele). Die Implementierung dieser Erweiterung ist euch freigestellt.

Heißt soviel wie muss nicht implementiert sein?

 

[Matthias Reitinger]

Die Suche nach oooo sollte auch noch Woodrow Wilson ausspucken.

Vielen Dank für den Hinweis, ich habe das Beispiel entsprechend angepasst.

Grover Cleveland steht 2 mal in der Liste, wundert euch also nicht falls dieser Name doppelt in euren Ergebnissen auftaucht

Ja, stimmt, sollte aber auch nicht stören

Heißt soviel wie muss nicht implementiert sein?

Genau. Wenn dir die Erweiterung zu kompliziert ist, musst du sie nicht implementieren. Was natürlich nicht heißt, dass man es nicht trotzdem probieren sollte

 

[Gumbo]

Heißt soviel wie muss nicht implementiert sein?

Eigentlich musst du gar nichts implementieren. Die Teilnahme ist ja freiwillig.
Die Erweiterung ist als Zusatzaufgabe für diejenigen gedacht, die nach Erledigen der ersten Aufgabe noch eine weitere Herausforderung suchen.

 

[Nils Hitze]

Wuild, sehr schöne Aufgabe die ihr das rausgesucht habt, da bin ich ja fast versucht, wenn ich nicht soviel zu tun hätte .. mal gucken. Bin jedenfalls gespannt wie das Ergebniss der Übung aussieht.