1 Mio. Strings zerlegen, speichern, indexieren, zählen

[turbo]

Moin,

könnt Ihr mir bitte Schlagworte für meine Recherche nach Datenstrukturen und Algorithmen nennen.
Es geht am Ende um so etwas Ähnliches wie eine Analyse eines Textes, welche Silben am häufigsten vorkommen. Die Silben sollen später darauf untersucht werden, in wie weit sie als Schlagwort im Index des Buches geeignet sind.

Gegeben:
1 Mio string[255], z.B. 'abcdefg'
Man stelle sich die Strings als Zeilen eines Buches vor.
Die Daten liegen auf Festplatte vor und werden häufig erweitert. Zur Vereinfachung gehen wir davon aus, dass die Daten komplett im RAM gehalten werden.
Es wird keine Datenbank verwendet. Die Daten werden bevorzugt als Array im RAM gehalten, da nachfolgende Operation davon profitieren sollen.

Die Strings sollen zerlegt werden in alle Teilstrings der Mindestlänge 3:
abc
abcd
abcde
abcdef
abcdefg
bcd
bcde
bcdef
bcdefg
...
efg
Die Teilstrings sind so ähnlich wie Wörter bzw. Silben von Wörtern. Es gibt keine Leerzeichen im Text, die man als Worttrenner ansehen könnte. Durch diese Vorgehensweise wird die Anzahl der Silben sehr groß sein. Das ist mir bewusst.

Das Ergebnis soll eine Struktur mit ca. diesem Zeilenaufbau im RAM sein:
Silbe, Silben-ID als 64 Bit Integer, Häufigkeit der Silbe im Text, ID bzw. Pointer auf die Textstelle, die "Silbe" enthält
'abc',123456,37,Pointer

Die Zeilen sollen einzeln indexiert werden nach Silbe und Häufigkeit (später auch nach Soundex und Kölner Phonetik von Silbe). Nach Silben-ID ist sortiert. Die Indize liegen im RAM und werden bei Programmende auf Platte geschrieben.

Die anschließende Bewertung der Silben wird dann so erfolgen:
Länge der Silbe (absteigend), Anzahl der Häufigkeit (absteigend), Silbe (aufsteigend)


Warum das ganze:
Der Benutzer soll später in einer Suchfunktion Silben eingeben, z.B. "abcd"
Das Programm soll dann zurückliefern:
Anzahl Treffer zu "abcd": 1.284 (wird im Hintergrund hochgezählt, die ersten Treffer werden angezeigt)
Anzahl Treffer für höherwertige Schlagworte: "abcdef" 7 Treffer, "abcef" 35 Treffer (wird im Hintergrund nach und nach ermittelt)
Anzahl ähnlicher Treffer nach soundex "abce": 32 (wird im Hintergrund hochgezählt, keine Trefferanzeige)
Anzahl ähnlicher Treffer nach Kölner Phonetik "abct": 75 (wird im Hintergrund hochgezählt, keine Trefferanzeige)

Angestrebte Laufzeit für die Anzeige des ersten Treffers: ca. 0,1 Sekunden
Für die ersten 50 Treffer: ca. 0,2 Sekunden

Laufen soll das Programm später auf:
- Windows 7 64 Bit und
- Ubuntu 12.04 64 Bit
- Intel i5 als Minimum, eventuell auch i7


Gesucht:
Ideen zu Datenstrukuren, Algorithmen oder alternativen Ansätzen
Schlagworte für meine Recherchen

Danke schön.


Meine ToDo-Liste:
DIPLOMARBEIT Bidirektionale indexbasierte Suche in Texten aus 2010: http://www.google.de/url?sa=t&rct=j&q=b ... umYUe9-RdA" onclick="window.open(this.href);return false;
gerichteter, azyklischer Graph für Strings: http://en.wikipedia.org/wiki/DAWG" onclick="window.open(this.href);return false;
Übersicht Lazarus unterstützter in memory Datenbanken ohne Server und Client : http://wiki.freepascal.org/Databases#Su ... _databases" onclick="window.open(this.href);return false;
Assoziative Arrays: http://www.lazarusforum.de/viewtopic.ph ... xOf#p30359" onclick="window.open(this.href);return false;

Könnte brauchbar sein:
Turbo Power B-Tree Filer für Turbo Pascal/Delphi: http://sourceforge.net/projects/tpbtreefiler/" onclick="window.open(this.href);return false;

Scheint nicht zu passen:
BWT Volltextsuche: http://de.wikipedia.org/wiki/Burrows-Wh ... sformation" onclick="window.open(this.href);return false;
Memory Mapped Files: Das wird nichts gemappt sondern stumpf in den Speicher geladen.
ZIP https://de.wikipedia.org/wiki/ZIP_%28Dateiformat%29" onclick="window.open(this.href);return false; https://de.wikipedia.org/wiki/Lempel-Zi ... lgorithmus" onclick="window.open(this.href);return false;

[theo]

Wozu ist denn die Silben ID gedacht? Hash?

[turbo]

Die Silben-ID soll einen Zeitbezug und einen Zähler enthalten.
Da viele Daten im RAM gehalten werden, rechne ich damit, dass vielleicht nicht immer alles auf Platte geschrieben werden kann. Mit den Daten aus der ID weiß ich, ab welcher Position ein Index neu aufgebaut werden muss.
Für bestimmte Operationen reicht es außerdem, wenn ich IDs verwende. Dann brauche ich nicht auf die aufwändigeren Stringoperationen zurückzugreifen.
Die ID würde ich auch für Indize verwenden.

[Scotty]

Vielleicht hilft dir das: http://en.wikipedia.org/wiki/DAWG" onclick="window.open(this.href);return false;
Ansonsten schätze ich, dass IndexOf() / Find() und auch "for i:=0 to 10E6 do if pos(aSearch,aStringlist)" im Subsekundenbereich fertig sind.

[Socke]

Es wird keine Datenbank verwendet.

Du weißt schon, dass es genau das ist, was du vorhast?
Meine Empfehlung: alles in eine SQLite3-Datenbank neuerer Version hineinschieben; Volltext-Suchindex erstellen und ab dafür. Die Silbentrennung kannst du ja vorher noch von deinem Programm machen lassen, aber warum willst du den ganzen Kram mit Datenhaltung, -suche und Zugriff nochmal extra programmieren?

[mschnell]

Wenn es um Geschwindigkeit geht: es gibt auch lokale Memory-Residente Datenbanken.

-Michael

[Bora4d]

Hört sich wie Funktionsweise einer Suchmaschine an
Schau mal in Internet nach "NonSQL". Da gibts bestimmt Techniken oder Algorithmen, die du verwenden kannst.

[martin_frb]

Also zunaecht musst du sicher stellen, das die Daten komplett ins Memory passen.

Wenn das OS memory swappen muss, ist das wesentlich langsamer, als wenn die App selbst, kontrolliert Daten auslagert. Es gibt naemlich speziell optimierte strukturen fuer den FAll das auf Disk ausgelagert werden muss. (zB http://en.wikipedia.org/wiki/B-tree" onclick="window.open(this.href);return false; )

Fuer die Suche (pre-fix suche) benoetigst Du einen Tree. Da kommen verschiedene in Frage Prefix/Binary oder mixture.

Fuer das erzeugen des Tree, und zaehlen, kann (optional) zusaetlich eine Hashtabelle helfen (Speed, aber nur wenn genug Memory)

[pluto]

Irgendwie ist mir nicht ganz klar, wozu das ganze dienen soll. Gibt es vielleicht noch mehr Anwendungsbeispiele?
Auch die Angestreptezeit halte ich für sehr zweifelhaft.

Meinst du sowas in etwa wie bei google? man gibt ein Wort ein und der Sucht im Hintergrund nach einen Passenden Wort, was du meinen könntest und schlägt die ersten Wörter vor?

[mschnell]

Ich glaube, ZIP macht so etwas ähnliches.

-Michael

[turbo]

Moin,

schon mal vielen Dank für die Hinweise. Ich haben am Ende des ersten Beitrags schon einige Punkte notiert.

Zu Datenbanken:
Alles von der Festplatte ist zu langsam.
Man kann schlecht mit ihnen rechnen. Dafür sind sie einfach nicht gemacht.
Das letzte mal, dass ich mich mit Datenbanken beschäftigt habe, ist gut 20 Jahre her.
Bevor ich mich in aktuelle Systeme eingearbeitet habe, ist das wenige, was ich wirklich brauche, längst selbst programmiert.
Wenn ich für die inmemory Datenbanken eine gute deutsche Dokumentation finde, schaue ich mir die an.

Ins Memory passen:
Ich sehe das auch so, dass man besser selber kontrolliert, ob bzw. was auf Disk ausgelagert wird. Das OS swappt bei mir nicht. Dafür ist genug RAM da.

Auch die Angestreptezeit halte ich für sehr zweifelhaft.
Meinst du sowas in etwa wie bei google? man gibt ein Wort ein und der Sucht im Hintergrund nach einen Passenden Wort, was du meinen könntest und schlägt die ersten Wörter vor?

Die 0,1 Sekunden betreffen im wesentlichen die Suche nach einer Silbe. In einem AVL-Baum findet man in o log n Schritten. Das ist schon machbar. Der Aufbau von Indizes ist in den 0,1 Sekunden nicht enthalten.

Ja, das ist wie bei Google. Durch die Zerlegung in Silben und Zählung derselben sollen die Wörter ermittelt werden, die dann zur Auswahl vorgeschlagen werden.


Den Hinweis auf ZIP habe ich nicht verstanden. Was ist damit gemeint?

[mschnell]

Viele Kompressions-Algotithmen (vermutlich auch ZIP) suchen nach mehrfach wiederkehrenden Daten-Abschnitten.

Dafür wird versucht, solche Abschnitte (sowas wie "Silben" oder "Wörter") in den Daten zu finden. Diese werden mit einem Code identifiziert.

Später werden dann in der gepackte Datei neben den Tabellen Silben->Codes nur noch die Codes hingeschrieben, die dann beim Entpacken zu den Silben expandiert werden.

-Michael

[turbo]

danke, jetzt habe ich es verstanden

[martin_frb]

Moin,
Die 0,1 Sekunden betreffen im wesentlichen die Suche nach einer Silbe. In einem AVL-Baum findet man in o log n Schritten. Das ist schon machbar. Der Aufbau von Indizes ist in den 0,1 Sekunden nicht enthalten.

Ja, das ist wie bei Google. Durch die Zerlegung in Silben und Zählung derselben sollen die Wörter ermittelt werden, die dann zur Auswahl vorgeschlagen werden.

Das (alphabetisch) erste, oder ersten 50, sind auf diese weise zu *schnell* finden.

Wenn zum Beisbiel der user "ab" getippt hat (or worse "a"), dann kanns du im tree schnell die Node finden, unter der alle "Silben" mit diesem Anfang sind.
Der Zweig enthaelt dann Millionen nodes fuer die vollen Silben (mit diesem start). Und die sind (wie der gesammte tree) alphabetisch sortiert.

Wenn du in diesen Millionen, den Eintrag mit dem groestem Zaehler suchst, oder den Laengsten, dann wird das komplizierter.

Da muss jede node im Tree Zusatz Daten haben.

[Bora4d]

Du solltest auch über Memory Mapped Files nachdenken. Damit kann man auch wie mit dem RAM arbeiten.
z.B. wenn ein Zielrechner nicht genügend RAM hat, dann kann dein Programm zumindest mit weniger Performance arbeiten anstatt gar nicht.