PureBoard

Ich habe ein paar 10tausend kleine Textdateien, Länge so im Schnitt zwischen 5 und 15 normalen Zeilen (Es handelt sich um kurze Gesprächsprotokolle). Funktionieren soll das Programm so: Man gibt einige (zwei bis höchstens vier) Suchwörter ein und in einer Maske erscheinen die Texte, die diese Suchwörter enthalten. Das ganze muß sehr flott gehen, die Antwortzeiten müssen also nahezu "null" sein. Sinn der Sache soll sein: In den Dateien steckt eine Menge Fachwissen, auf das zur Beantwortung einer aktuellen Frage schnell zugegriffen werden können soll.

Wie macht man so etwas? Überlegt habe ich mir bislang: Ich extrahiere alle verschiedenen Wörter und speichere diese Wörter als Schlüsselworte in einer Map zusammen mit der Nr. der Datei, in der sie vorkommen (Irrelevante Wörter wie Artikel pp. werden aussortiert, gleichfalls anhand einer wie auch immer generierten Liste), zB:

Abnahme
10/500/1339/5528/29835/

Ich schätze, daß dies einige tausend (oder 10tausende?) Einträge ergibt.

Anschließend wird der zweite Suchbegriff aufgerufen und die Dateinummern auf Übereinstimmungen beim ersten Suchbegriffs untersucht (Wie macht man das schnellstmöglich, wenn es zu einem Begriff schlimmstenfalls hunderte von Dateieinträgen gibt?) und die Datei dann bei einem Treffer angezeigt usw.

Hat jemand Erfahrung mit einem solchen System, ist so etwas praktisch sinnvoll anwendbar und wie sieht es mutmaßlich mit der Laufzeit aus?

Ist es (etwa wegen Rechtschreibfehlern oder Wortflexionen) erfahrungsgemäß sinnvoll oder notwendig, die Suchwörter nicht im Original zu speichern und zu durchsuchen, sondern in einer gewichteten Form (z.B: Ersetzung von ie durch i, von Umlauten durch Vokale, Streichung von Doppelbuchstaben, Streichung von Flexionsendungen)?

Noch 'was: Die wichtigste Funktion wäre möglicherweise, die Suchwörter auf Knopfdruck (Button) an den IE oder Firefox & Google zu übergeben (wenn man nichts findet ), wie macht man denn so etwas?

Syntacks_Error hat geschrieben:Ich habe ein paar 10tausend kleine Textdateien, Länge so im Schnitt zwischen 5 und 15 normalen Zeilen (Es handelt sich um kurze Gesprächsprotokolle). Funktionieren soll das Programm so: Man gibt einige (zwei bis höchstens vier) Suchwörter ein und in einer Maske erscheinen die Texte, die diese Suchwörter enthalten. Das ganze muß sehr flott gehen, die Antwortzeiten müssen also nahezu "null" sein. Sinn der Sache soll sein: In den Dateien steckt eine Menge Fachwissen, auf das zur Beantwortung einer aktuellen Frage schnell zugegriffen werden können soll.

Wie macht man so etwas? Überlegt habe ich mir bislang: Ich extrahiere alle verschiedenen Wörter und speichere diese Wörter als Schlüsselworte in einer Map zusammen mit der Nr. der Datei, in der sie vorkommen (Irrelevante Wörter wie Artikel pp. werden aussortiert, gleichfalls anhand einer wie auch immer generierten Liste), zB:

Abnahme
10/500/1339/5528/29835/

Ich schätze, daß dies einige tausend (oder 10tausende?) Einträge ergibt.

Anschließend wird der zweite Suchbegriff aufgerufen und die Dateinummern auf Übereinstimmungen beim ersten Suchbegriffs untersucht (Wie macht man das schnellstmöglich, wenn es zu einem Begriff schlimmstenfalls hunderte von Dateieinträgen gibt?) und die Datei dann bei einem Treffer angezeigt usw.

Dafür gibt es Datenbanksysteme und Stoppwortlisten . Das Backend eines Datenbanksystems besteht grob gesagt aus Paging, Nutzer- und Rechteverwaltung, Baumstrukturen (siehe B*, ISAM, Red/Black, AVL Baum), Hashing und Parallelisierungstechniken sowie ggf. Kompression und Verschlüsselung.

Syntacks_Error hat geschrieben:Hat jemand Erfahrung mit einem solchen System, ist so etwas praktisch sinnvoll anwendbar und wie sieht es mutmaßlich mit der Laufzeit aus?

Ist es (etwa wegen Rechtschreibfehlern oder Wortflexionen) erfahrungsgemäß sinnvoll oder notwendig, die Suchwörter nicht im Original zu speichern und zu durchsuchen, sondern in einer gewichteten Form (z.B: Ersetzung von ie durch i, von Umlauten durch Vokale, Streichung von Doppelbuchstaben, Streichung von Flexionsendungen)?

Siehe Google: Ein Vorschlag vom System, wie die Suchbegiffe auszusehen hätten wäre wohl ideal.

Syntacks_Error hat geschrieben:Noch 'was: Die wichtigste Funktion wäre möglicherweise, die Suchwörter auf Knopfdruck (Button) an den IE oder Firefox & Google zu übergeben (wenn man nichts findet ), wie macht man denn so etwas?

Das mit den B*, ISAM, Red/Black, AVL Baum pp. habe ich mir mal angesehen, verstehen tue ich da garnichts, ich bin halt nur ein einfacher Hobbyprogrammierer vom Lande Habe aber mal ein Testsystem gebastelt, mit einfacher Wortindizierung und Dateisatznummer über Listen geht das erstaunlich flott.

Gehen tut auch das mit dem Google-Aufruf, aber nur mit Einschränkung:

Dieses "runprogram" gibt als Ergebnis immer eine "1" aus, ich kann den Browser aber mit killprogram(1)/closeprogram(1) nicht beenden, das gibt einen Fehler. Das allerdings auch, wenn ich das Programm über "Verzeichnis\firefox.exe" aufrufe. Stimmt da etwas mit der run-Funktion nicht?

Gibt es eine Möglichkeit, die Suchworte einer laufenden Instanz des Browsers zu übergeben, damit man den nicht immer neu starten muß?

Syntacks_Error hat geschrieben:Das mit den B*, ISAM, Red/Black, AVL Baum pp. habe ich mir mal angesehen, verstehen tue ich da garnichts, ich bin halt nur ein einfacher Hobbyprogrammierer vom Lande Habe aber mal ein Testsystem gebastelt, mit einfacher Wortindizierung und Dateisatznummer über Listen geht das erstaunlich flott.

Gehen tut auch das mit dem Google-Aufruf, aber nur mit Einschränkung:

Dieses "runprogram" gibt als Ergebnis immer eine "1" aus, ich kann den Browser aber mit killprogram(1)/closeprogram(1) nicht beenden, das gibt einen Fehler. Das allerdings auch, wenn ich das Programm über "Verzeichnis\firefox.exe" aufrufe. Stimmt da etwas mit der run-Funktion nicht?

Gibt es eine Möglichkeit, die Suchworte einer laufenden Instanz des Browsers zu übergeben, damit man den nicht immer neu starten muß?

Gibt bei mir nicht immer nur 1 aus.

Das braucht wohl die zusätzlichen Optionen, dann gibt es eine richtige Nummer zurück. Das Programm zu beenden funktioniert aber immer noch nicht (Jedenfalls nicht bei mir, Firefox): Das Teil interessiert das Killen überhaupt nicht .... Oder wird da ein anderer Parameter als das Ergebnis von RunProgram() benötigt? Bei IsProgram() ist das aber offenbar richtig.

Unter UNIX würde man dazu erst gar kein Programm schreiben, sondern da einfach mit grep (bzw egrep wenn du mit Regular Expressions suchen willst) verwenden.

Unter Windows könntest du halt versuchen, dir einen Ersatz für grep zu bauen, ggf. mit GUI.

Ich würde einfach Datei für Datei in den Speicher lesen, und dann halt mit CompareMemory() drübergehen (). Du musst natürlich darauf achten, dass dein Such-String im selben Encoding vorliegt wie die zu durchsuchende Datei.

Wenn du RegEx haben willst, dann lies es als String mit fixer Länge in den Speicher, damit du dir keine Sorgen um Chr(0) machen musst, und geh halt mit MatchRegularExpression() bzw ExtractRegularExpression() drüber.

Wenn die Dateien eine bestimmte Größe (z.B. 20MB) überschreiten, dann würde ich die Dateien blockweise (z.B. in 20MB-Blöcken) einlesen, damit das Ganze nicht zuviel RAM verbraucht. Beim Einlesen solltest du die Blöcke um die Länge des jeweiligen Suchbegriffs minus 1 "überlappen" lassen, damit dir keien Treffer an den Grenzen den Blöcke entegehen. Wenn du also nach "Katze" suchst, lies zuerst den Block von Byte 0 bis Byte 20971519 ein, und danach von 20971514 bis 41943035 ein. Wenn du mit Unicode arbeitest, musst du natürlich den Überlappungsbereich doppelt so groß machen, und du gehst nach jedem CompareMemory() nicht 1, sondern eben 2 Byte "vorwärts".

Thorium, Remi Meier oder einer der anderes ASM-Experten können dir sicher noch ein paar Kniffe zeigen und Tipps geben, damit das Ganze mit noch ein paar CPU-Zyklen weniger auskommt...

N.B. Das ist jetzt nur Theorie, ich hab das jetzt nich praktisch durchprobiert.

Grüße
Pascal

//EDIT: Für AND-Suchen natürlich nur die Dateien nach Suchbegriff2$ durchsuchen, in denen du schon Suchbegriff1$ gefunden hast!

Syntacks_Error hat geschrieben:Wie macht man so etwas? Überlegt habe ich mir bislang: Ich extrahiere alle verschiedenen Wörter und speichere diese Wörter als Schlüsselworte in einer Map zusammen mit der Nr. der Datei, in der sie vorkommen (Irrelevante Wörter wie Artikel pp. werden aussortiert, gleichfalls anhand einer wie auch immer generierten Liste), zB:
[...]

Da bist du auf der richtigen Spur. Es gibt da einige, ziemlich einfache
Algorithmen, die das ganze beschleunigen und weiter treiben.
Das Thema nennt sich "Information Retrieval" und kann gegoogelt
werden
http://de.wikipedia.org/wiki/Information-Retrieval
Es gibt verschiedene Modelle, momentan hört sich deines nach einem
einfachen Booleschen Modell an. Wenn du noch ein Ranking der Dokumente
nach Relevanz möchtest, kann man mit einem simplen Modell mit der WDF
( http://de.wikipedia.org/wiki/Within-document_Frequency )
und der IDF ( http://de.wikipedia.org/wiki/Inverse_Dokumenthäufigkeit )
kombiniert zur TF-IDF ( http://de.wikipedia.org/wiki/TF-IDF ) Gewichtungs-
funktion, ein solches erreichen.

Stemming und Stopwords sind so einfach zu implementieren, dass sie nicht
fehlen dürfen:
http://de.wikipedia.org/wiki/Stemming
http://de.wikipedia.org/wiki/Stoppwort

Mit ein paar wenigen Speicheroptimierungen entsteht dadurch ein Wort-
index von ein paar KBs bis wenige MBs, welche man locker durchsuchen
kann.

Ich weiss, dass diese Antwort keine direkte Lösung ist, aber vielleicht
interessiert dich das Thema genug, damit du den Links folgst und ev.
noch etwas weiter nachforschst.
Ein gutes Buch dafür wäre wohl "An Introduction to Information Retrieval":
http://www.informationretrieval.org/

hardfalcon hat geschrieben:Thorium, Remi Meier oder einer der anderes ASM-Experten können dir sicher noch ein paar Kniffe zeigen und Tipps geben, damit das Ganze mit noch ein paar CPU-Zyklen weniger auskommt...

Wow, ich wurde erwähnt
Muss da aber sagen, dass ich ohne grosse Optimierungen sogar in
Python eine Reaktionszeit von <1s erreicht habe. Es geht hier also in
erster Linie um die Algorithmen.


Ich hoffe, meine Antwort ist nicht ganz sinnfrei.

greetz
remi

Unter Windows nennt sich grep (mehr oder weniger) find und findstr, ich denke aber, das ist nicht wirklich praktikabel für den Sachbearbeiter von der Stange

Ich habe es erstmal so gemacht:

Ich habe testweise diverse 10-tausende Dateien in einer Datei zusammengeführt (die störten mich irgendwie), das ergab so 100 MB. Die laufende Nummer jedes Datensatzes in der Datei wird in einer Map mit seiner Anfangsposition in der Datei (loc(datei)) gepeichert.

Dann werden die einzelnen Worte extrahiert (ca. 2 Mio) und mit der Nr. des Datensatzes, in dem sie vorkommen, in einer Liste gespeichert. Alles in Kleinschreibung, alles Nicht-Alphanumerisches wird mit RegExpr entfernt, Umlaute und ß werden substituiert. Aus der Liste werden doppelte Wörter und einige gramatikalische Varianten entfernt, ihre Datensatznummern dem Datensatznummerrstring des verbleibenden Wortes mit einem Trennzeichen hinzugefügt. Ergibt also etwa ein Element:

haus
20350/15887/9003/2872/539/34/....

wobei dann da auch die Datensatznummern von Hauses, Häuser, Häusern und so drinstehen.

Das Ganze wird einmal nach Wörtern sortiert, und dann wird auch noch der Datensatzstring jedes Wortes sortiert (Das rückwärts, damit später die neuesten Datensätze zuerst gefunden werden).

Eine Liste und keine Map ist das, weil später nicht nur genaue Übereinstimmungen gefunden werden sollen, sondern auch Worte, die das Suchwort nur enthalten. Eine Map geht ja nur mit exakten Schlüsselworten.

Diese Indexliste enthält dann alle verschiedenen Wörter (gut 80.000) mit den Datensatznummern, in denen sie vorkommen.

Dauert alles in Allem knappe 40 Sekunden.

Für die Suche erstelle ich dann daraus erstmal eine Liste, in der die Adresse jedex x-ten (ich habe erstmal so jedes 200ste genommen) Elements zusammen mit seinem Wort gespeichert ist.

Bei der Suche wird zunächst diese letzte Liste durchlaufen, bis der dortige Worteintrag größer ist als das Suchwort (das natürlich auch RegExpr-mäßig pp. bearbeitet wird). Ein Element zurück ergibt eine Position vor dem dem ersten gesuchten Wort der Indexliste mit der entsprechenden Adresse in der Indexdatei. Dieses Element der Indexliste wird dann über die Adresse direkt angesprungen. Das erspart es, die Indexliste jedesmal ganz von vorne zu durchlaufen. Im Durchschnitt müßten dann bis zum ersten Worttreffer (Indexelemente/200 + Indexelement(200/2)) durchlaufen werden (bei 80000 Einträgen also 6000) anstatt Indexelemente/2 (das wären 40.000), oder wie ist das? Allerdings scheint diese Einsprungmethode testmäßig nicht spürbar schneller zu sein als das Durchlaufen der Indexliste immer von Anfang an, merkwürdig.

Dann wird die Indexliste durchlaufen und für jedes Suchwort das gefundene Wort zusammen mit dem String mit den Dateinummern in einer weiteren Liste gespeichert (Der erste Treffer natürlich auch). In der Liste stehen dann die Datensatznummern der Datensätze, in denen der gesuchte Begriff vorkommt.

Bei mehreren Suchwörter wird das für jedes Suchwort gemacht.

Dann wird noch ne' Liste mit den Nummern der Datensätze generiert, in der alle Suchworte vorkommen . Es werden also die Datennummernstrings auf Gemeinsamkeiten getestet, das entfällt natürlich, wenn es nur ein Suchwort gibt.

Und nun wird in der allerersten Liste, dem Dateisatzindex nachgekuckt, in welcher Dateiposition (loc()) die jeweiligen Datensätze der großen Datendatei stehen, die werden angesprungen und die Datensätze werden angezeigt.

Ich weiß ja nicht, ob das alles wirklich so praktisch ist, aber die Suchzeit beträgt (für maximal 30 gefundene Datensätze, mehr kuckt man sich eh' nicht an) maximal 30 Millisekunden (Intel 3 GHZ), je nachdem wieviele Suchwörter verwendet werden (praktisch sind es ja allenfalls 3) und wieviele Listenelemente durchlaufen werden müssen. Meistens sind es 15 Millixsec, manchmal werden "0" behauptet, ebenso, wenn kein Datensatz gefunden wird. Ich denke mal, das ist nicht so schlecht dafür, daß aus einer 100 MB-Datei eben nicht nur genaue Wortübereinstimmungen gefunden werden. Sonst ginge es rein über Maps sicher noch schneller.

Die gesamten Originaldaten, um die es geht, sind alledings noch ein bißchen größer. Und wenn das alles (Bis auf die Suchworteingabe) auf dem Server läuft, kann es natürlich auch noch anders aussehen, aber im Prinzip dürfte es funktionieren.

Firefox killen klappt aber immer noch nicht, ich habe noch ein paar andere Methoden ausprobiert, aber die müssen da irgend etwas eingebaut haben ...

Erstmal danke für die Hilfe.