[Suchverfahren] Die Existenz eines Strings in einer Menge von Strings pruefen

7 Beiträge19.07.2009Archiviert
WhiteDragon19.07.2009 · Beitrag #20243
Mitglied seit: 01.02.2005
Forenbeiträge: 196
Besuche: 678
Hey Leute.

Ich will in einem meiner Programme herausfinden, ob ein gewisser String in einer Menge von Strings auftaucht. Ich habe insgesamt Daten von 160086 Strings mit durchschnittlich 12 Zeichen pro String. Ich will nun also herausfinden ob einer dieser 160086 Strings mein gesuchter String str ist.

Meine Frage: Was fuer ein Suchverfahren wuerdet ihr empfehlen? Einen Binaerbaum oder einen 2-3-4-Baum oder eine andere Art von Baum? Lineare Suche in einer Liste hab ich schon ausgeschlossen, da ich sehr viele Strings auf ein Match in diesem Datensatz pruefen will (Das werden leicht _wesentlich_ mehr, als ich Datensaetze hab. ungefaehr 6.22702e+09 ist eine Zahl, an der man sich so orientieren kann) Im Moment neige ich dazu eine Hash-Tabelle zu implementieren, ich hab allerdings mit so grossen Datenmengen keine Erfahrung. Obwohl die 160086 Strings ja nicht sooo viel Daten sind. Wenn ihr eure Meinung schreibt, koennt ihr natuerlich auch gerne weitere Informationen posten. Zum Beispiel koenntet ihr bei einer Hash-Tabelle anmerken, welche Funktion ihr zum hashen benutzen wuerdet oder dergleichen. Meine Strings bestehen uebrigens nur aus printable-ASCII-Zeichen, wenn das jemanden etwas nuetzt.

PS: Ich will die Sache schon selbst implementieren. Da sowas immer relativ einfach ist und ich gerne Programmiere, will ich nicht unbedingt eine Library fuer die Suche benutzen oder aehnliches. Mir geht es hier eher um eine Diskussion, welcher Suchansatz sich wohl am besten eignet.

PPS: Weil ich gerade im Internet dauernd sehe, dass ich einen Suchalgorithmus suche und einen Link auf einen Sortieralgorithmus finde: Natuerlich ist das Einordnen in irgendwas auch von Bedeutung. Aber das ist eine Arbeit die nur einmal gemacht wird und deswegen nicht weiter relevant. Selbst wenn es 20 Minuten dauert die paar Daten einzuordnen ist mir das ziemlich egal. (Mal abgesehen davon, dass fuer gewisse Suchverfahren eine gewissen Dateneinordnung natuerlich noetig ist). Was ich zum Beispiel nicht suche waere ein Link zu Quicksort.

Vielen Dank schon vorneweg.
WhiteDragon.




[ Bearbeitet ]
dmesg19.07.2009 · Beitrag #20244
Mitglied seit: 24.06.2006
Forenbeiträge: 120
Besuche: 3907
Es kommt ein bisschen drauf an, was du vorhast, wenn du nur einmail String(s) suchst, kannst du auch jedes Element in deiner unsortierten Liste abrufen, das ist effektiver als jedes Element erstmal in eine bestimmte Datenstruktur zu quetschen (dort womoeglich auch noch diverse Vergleich- und Rotieroperationen durchzufuehren) ist wesen uneffektiver als wenn du die Liste nur einmal durchgehst.

Wenn du allerdings oeffters mal nach Strings suchst, dann nimm Trie, die sind extrem gut bei Negativsuchen: http://en.wikipedia.org/wiki/Trie
WhiteDragon19.07.2009 · Beitrag #20245
Mitglied seit: 01.02.2005
Forenbeiträge: 196
Besuche: 678
Hey.

Okay, das hoert sich tatsaechlich interessant an. Hab mir sowas aehnliches schon ueberlegt. Ist auf jeden Fall ein Probieren aus.

Nunja, ich suche 6.22702e+09 verschiedene Strings in meinem Datensatz von 160086 Strings. Da die 160086 nur einmal eingelesen und damit auch nur einmal eingeordnet werden sollen und dann die Existenz von ca. 6.22702e+09 (oder mehr) Strings geprueft werden soll, ist eine unsortierte Liste eher schlecht. (Ich hab das mal getestet. Wenn ich in der Datenbank mit 160086 Strings nur 1000 mal einen String suche brauche ich dafuer durchschnittlich fuenf Sekunden. Da ich aber wesentlich mehr Strings suchen muss, geht das fuer meine Anzahl an Strings leicht in die Tage) Das mit dem Trie hoert sich nicht schlecht an. Vor allem weil auch die Einordnung sehr einfach ist. Das werde ich wohl mal probieren.

Thnx.
WhiteDragon.
[ Bearbeitet So, 19. Jul 2009, 19:43 ]
prom23.07.2009 · Beitrag #20269
Avatar
Mitglied seit: 28.04.2009
Forenbeiträge: 5
Besuche: 153
Ich habe im Umgang mit Datenmengen im Bereich von grob 200.000 Datenelementen zu je etwa einem Kilobyte mit Hashtabellen in Java und auch in Perl sehr gute Erfahrungen gemacht. Einsatzzweck war Suchen, Sortieren und das Ausfiltern von Duplikaten.
Die Gefahr von Kollisionen sollte man aber auf jeden Fall berücksichtigen und ggfs. einen Treffer durch einen vollständigen Stringvergleich verifizieren.

Grüße
Peter
Kuba26.07.2009 · Beitrag #20276
Avatar
Mitglied seit: 06.02.2005
Forenbeiträge: 103
Besuche: 2470
Hashtabellen mit Java sind ein gutes Stichwort. Habe das auch einmal umgesetzt, aber mit sehr wenigen Datensätzen.
Vorgehensweise wäre dann die - genauer gesagt - LinkedHashMap zu füllen und dann folgendermaßen zu iterieren:

[cli]for (String key : LHS.keySet()) {
if (gesString.equals(key)) {
// Falls die beiden Strings übereinstimmen
}
}
[/cli]

Hoffe, dass stimmt ungefähr so (-> direkt vom Brain geladen :D)

Gruß
WhiteDragon27.07.2009 · Beitrag #20277
Mitglied seit: 01.02.2005
Forenbeiträge: 196
Besuche: 678
Hey.

Danke noch fuer die beiden Antworten. Also ich hab jetzt einen trie schon implementiert. Eine Hash-Tabelle werde ich auch noch implementieren und dann mal die Performance der beiden im Vergleich posten, falls hier jemand sein Interesse aeussert.

Da ich die Verfahren in C selbst implementieren will: Eignet sich irgendeine Hash-Funktion besonders gut um einen String zu hashen? Ich bin mal gespannt, ob die Hashtabelle hier den Trie schlagen kann. Da meine Datengroessen sehr klein sind (ein paar Bytes) und nicht wie bei dir Prom einige Kilobytes faellt der Zeitaufwand um den Hash zu bilden groesser ins Gewicht gegenueber der normalen Vergleichszeit als bei grossen Dateigroessen wo es laenger braucht 2 Daten zu vergleichenm.

Mit freundlichen Gruessen,
WhiteDragon.
Feuermonster19.08.2009 · Beitrag #20325
Avatar
Mitglied seit: 08.02.2008
Forenbeiträge: 53
Besuche: 142
Ich kann noch folgenden Link empfehlen: http://burtleburtle.net/bob/hash/doobs.html

Vielleicht hilft er dir.