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

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
turbo
Lazarusforum e. V.
Beiträge: 99
Registriert: Mo 6. Feb 2012, 17:20
OS, Lazarus, FPC: ubuntu 10.10, L 0.9.28.2, FPC 2.4.0
CPU-Target: x86_64
Wohnort: Oldenburg (Oldb)

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

Beitrag von 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
gerichteter, azyklischer Graph für Strings: http://en.wikipedia.org/wiki/DAWG
Übersicht Lazarus unterstützter in memory Datenbanken ohne Server und Client : http://wiki.freepascal.org/Databases#Su ... _databases
Assoziative Arrays: viewtopic.php?f=10&t=2781&p=30359&hilit=IndexOf#p30359

Könnte brauchbar sein:

Turbo Power B-Tree Filer für Turbo Pascal/Delphi: http://sourceforge.net/projects/tpbtreefiler/

Scheint nicht zu passen:
BWT Volltextsuche: http://de.wikipedia.org/wiki/Burrows-Wh ... sformation
Memory Mapped Files: Das wird nichts gemappt sondern stumpf in den Speicher geladen.
ZIP https://de.wikipedia.org/wiki/ZIP_%28Dateiformat%29 https://de.wikipedia.org/wiki/Lempel-Zi ... lgorithmus
Zuletzt geändert von turbo am So 9. Sep 2012, 14:55, insgesamt 4-mal geändert.
Liebe Grüße
turbo

Benutzeravatar
theo
Beiträge: 10467
Registriert: Mo 11. Sep 2006, 19:01

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

Beitrag von theo »

Wozu ist denn die Silben ID gedacht? Hash?

turbo
Lazarusforum e. V.
Beiträge: 99
Registriert: Mo 6. Feb 2012, 17:20
OS, Lazarus, FPC: ubuntu 10.10, L 0.9.28.2, FPC 2.4.0
CPU-Target: x86_64
Wohnort: Oldenburg (Oldb)

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

Beitrag von 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.
Liebe Grüße
turbo

Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

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

Beitrag von Scotty »

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

Socke
Lazarusforum e. V.
Beiträge: 3158
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

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

Beitrag von Socke »

turbo hat geschrieben: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?
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

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

-Michael

Bora4d
Beiträge: 290
Registriert: Mo 24. Dez 2007, 13:14
OS, Lazarus, FPC: WinXP-Pro-Sp3, Xubuntu 12.04, (Laz 1.1-SVN Mai2012, FPC 2.6.1 / 2.6.0-Linux)
CPU-Target: AMD64X2

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

Beitrag von 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
Beiträge: 572
Registriert: Mi 25. Mär 2009, 21:12
OS, Lazarus, FPC: Laz trunk / fpc latest release / Win and other
CPU-Target: mostly 32 bit

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

Beitrag von 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 )

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
Lazarusforum e. V.
Beiträge: 7178
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

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

Beitrag von 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?
MFG
Michael Springwald

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von mschnell »

Ich glaube, ZIP macht so etwas ähnliches.

-Michael

turbo
Lazarusforum e. V.
Beiträge: 99
Registriert: Mo 6. Feb 2012, 17:20
OS, Lazarus, FPC: ubuntu 10.10, L 0.9.28.2, FPC 2.4.0
CPU-Target: x86_64
Wohnort: Oldenburg (Oldb)

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

Beitrag von 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.

pluto hat geschrieben: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?
Liebe Grüße
turbo

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

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

Beitrag von 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
Lazarusforum e. V.
Beiträge: 99
Registriert: Mo 6. Feb 2012, 17:20
OS, Lazarus, FPC: ubuntu 10.10, L 0.9.28.2, FPC 2.4.0
CPU-Target: x86_64
Wohnort: Oldenburg (Oldb)

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

Beitrag von turbo »

danke, jetzt habe ich es verstanden
Liebe Grüße
turbo

martin_frb
Beiträge: 572
Registriert: Mi 25. Mär 2009, 21:12
OS, Lazarus, FPC: Laz trunk / fpc latest release / Win and other
CPU-Target: mostly 32 bit

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

Beitrag von martin_frb »

turbo hat geschrieben: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
Beiträge: 290
Registriert: Mo 24. Dez 2007, 13:14
OS, Lazarus, FPC: WinXP-Pro-Sp3, Xubuntu 12.04, (Laz 1.1-SVN Mai2012, FPC 2.6.1 / 2.6.0-Linux)
CPU-Target: AMD64X2

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

Beitrag von 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.

Antworten