Hallo, ich will eine Datenbank für PDF-Dateien anlegen: - Datenbank MySQL - OCR für grafische Inhalte: Tesseract - Textanalyse: pdf2txt Frontend muss ich noch schreiben, ist aber kein Problem. Was mir ein Problem bereitet, ist die Bildung einer Suchwort-Datenbank. Natürlich könnte ich, wie "Lieschen Müller" einfach drauflos und alle Worte irgendwie abspeichern und durchsuchen ... Ich bin mir aber sicher, dass es da wesentlich ausgereiftere Algorithmen gibt, die mit weiger Speicher auskommen und schneller sind. Nur gefunden habe ich zu dem Thema wenig öffentliches Wissen, geschweige denn Beispielcode o.ä. Hat hier jmd. einen Tip für mich? Danke. Frank
Such mal nach Suffix-Tree, das ist ne schicke Datenstruktur die dafuer geeignet ist. Bei pfiffiger Implementierung linearer Speicheraufwand
http://swish-e.org/ könntest Du Dir auch mal ansehen, vielleicht musst Du das Rad ja gar nicht neu erfinden.
Danke, bin dabei, mic da durchzuquälen ... Frank
Wenn du eh schon mysql hast, nimm doch einfach den dort mitgelieferten fulltext-index... Aufwand ist dann minimal... einmalig den Index in der Datenbank anlegen, Abfragen gehen dann über match ... against ... (in boolean mode) http://dev.mysql.com/doc/refman/5.1/de/fulltext-search.html
Danke, der Hinweis auf MySQL ist sehr schön, da muss ich mir nicht selber das Hirn martern. Aber ich habe da eine Frage, das habe ich nicht so richtig verstanden: Muss der einmal indizierte Text selber in der Datenbank bleiben oder kann man den anschließend löschen und nur der Index bleibt? Bei "dicken" Dokus bläht sich die Datenbank sonst schnell über die Maßen auf. Bisher experimentiere ich mit einer Substantiv-Extraktion ohne Doubletten, die ich anschließend indizieren möchte. Aber im Englischen wird die Substantiv-Erkennung schwierig, wegen der Kleinschreibung ... (Die Luther-Bibel von 1912 hat z.B. ca 4000 verschiedene Substantive in 4,2 MB ASCII-Code, dazu braucht mein Algorithmus ca. 7 Minuten) Frank
Frank schrieb: > (Die Luther-Bibel von 1912 hat z.B. ca 4000 verschiedene Substantive in > 4,2 MB ASCII-Code, dazu braucht mein Algorithmus ca. 7 Minuten) Scheint mir nicht wirklich effizient zu sein
Christopher D. schrieb: > Frank schrieb: > >> (Die Luther-Bibel von 1912 hat z.B. ca 4000 verschiedene Substantive in >> 4,2 MB ASCII-Code, dazu braucht mein Algorithmus ca. 7 Minuten) > > Scheint mir nicht wirklich effizient zu sein Kann mich nicht mehr erinnern, ob das die Luther Bibel war. Aber ich hab mal meinem Auszubildenden ein C++ Programm schreiben lassen, um ihn an std::map heranzuführen. Er sollte die Bibel einlesen und die einzelnen Worte in eine map speichern. Das ganze C++ Programm war keine 20 Zeilen lang und brauchte keinesfalls 7 Minuten. Eher so irgendwas um die 7 Sekunden.
>> Scheint mir nicht wirklich effizient zu sein
Damit wollte ich jetzt auch nicht prahlen. Die lange Zeit liegt mit
Sicherheit daran, dass ich die Resultate direkt in eine sichtbare
Listbox eintrage und auch den Test, ob es den Eintrag bereits gibt,
dummerweise über den Inhalt der Listbox mache. Ist halt derzeit nur eine
Algorithmus-Studie ... ich melde mich nach der Optimierung nochmal. :-)
Frank
Spar dir den Selbstbau, es gibt genug Volltext-Suchmaschinen die dir die Arbeit abnehmen können: - Lucene: Java, sehr ausgereift - Ferret: C/Ruby, Funktionsumfang teilw. besser als Lucene, leider etwas verbugt und Entwicklung eingeschlafen - Xapian: C++ - Sphinx: für direkte Indizierung von SQL-Datenbanken optimiert Wenn du sowieso MySQL verwendest, dann wäre der schon genannte MySQL-Fulltext-Index das einfachste. Der Text muss da komplett in der Datenbank bleiben, aber das sollte heutzutage wirklich kein großes Problem sein.
Die Listbox... wenn man was anhaengt, das den reservierten speicher auslutscht, so wird neuer speicher alloziert, alles kopiert und next... Nie Verarbeitung mit sichtbaren elementen machen.
Ich finde die fertigen Suchmaschinen teilweise sehr schlecht was die Performance und auch die Möglichkeiten der Selektion Abfragesprache angeht und insofern lohnt der Selbstbau mit wenig schon. Nicht umsonst ist Google schnell zum Platzhirsch gworden. Es ist mit einem SQL-System MSSQL, PostgreSQL, MySQL leicht möglich einen extrem schnellen Indexer zu bauen. Eine Tabelle enthält alle Schlüsselworte des Sekundärindex eine zweite enthält die Referenzen zum Original und eine dritte stellt die Verknüpfung her. Eine vierte könnte optional den Rang abbilden. Abfragezeiten von unter 1 Millisekunde sind immer drin solange man einen Bogen um MS-Access macht. MySQL funktioniert gut in der Volltextsuche solange die Datenbank nicht zu gross wird, dann bricht es ein oder stürzt sogar ab. Es sollte eben auch möglich sein im produktiven Betrieb Updates zu fahren.
Ganz so einfach ist es nicht, wenn man an den Funktionsumfang einer richtigen Suchmaschine herankommen will (Suche nach Phrasen, Pre- und Postfix-Wildcards, ähnliche Wörter, Sortierung großer Ergebnismengen nach Relevanz, usw.). Die Idee einer SQL-basierten Suchmaschine interessiert mich schon länger, ich bin nur nicht überzeugt dass sich die Datenstruktur sinnvoll auf eine relationale Datenbank abbilden lässt.
>Die Idee einer SQL-basierten Suchmaschine >interessiert mich schon länger, ich bin nur nicht überzeugt dass sich >die Datenstruktur sinnvoll auf eine relationale Datenbank abbilden >lässt. Vertrau mir da mal ausnahmsweise, noch besser probiere es selbst mal aus. Als Programmierer habe ich die Mächtigkeit eines SQL-Servers selbst auch lange Zeit unterschätzt. Schließlich waren die "Datenbankprofis" in meinem Kreis auch irgendwo unfähig ein C-Programm mit Funktionalität herzustellen. Es sind Menschen, die Verwaltungsprogramme schreiben: Daten eingeben und wieder ausgeben ohne eine Operation und ohne ein Ergebnis. Das "Problem" wie man eine Liste im Fenster scrollt war nicht in ihrem Repertoire: Schau da nimmst du den x-ten Eintrag und gibst die folgenden 20 Stück aus. Beim Scrollen nach unten fängst du mit dem (x+1)-ten an. Was ich sagen möchte: Die Datenbankproggis in meinem Bekanntenkreis sind auch keine echten Datenbankprofis. Wie dem auch sei: Also derartige Aufgaben selbst via C-Programm besser, fehlerfreier und effizienter zu realisieren ist zwar prinzipiell möglich aber nicht in einem Tag. Das beste aber unbezahlbare Dingens ist nach meinem Eindruck nach wie vor Oracle, Postgres ist nicht schlecht. Der MS-SQL-Server, also von Sybase, ist irgendwo. So ein Dingens wie PostgreSQL oder auch der SQL-Server oder "derby.jar" kann nichts besser und effizienter als Einträge nach einem Primärschlüssel finden. Ein einzelner "Join" über viele geeignet angelegte Tabellen ist unglaublich effizient. Es wird ja auch nur ein Cursor geliefert... Zugegeben das Denken in "n-Tupeln" ist gänzlich anders als beim Programmieren und den Zugang kriegt man auch ohne eine entsprechende Einführung und Problemstellungen aus der Praxis nicht an einem Tag. Es sieht zunächst wenig leistungsfähig aus und gerade Leute, die niemals programmieren werden können kommen zu überraschend kreativen und effektiven Lösungen. Der Programmierer verarbeitet in seinem Programm nur eine einzige Tabelle. Den Inhalt möchte er in den Speicher laden und dort mit einer anderen Map verknüpfen. Dazwischen finden sich noch Routinen um aus dem Text einen float zu machen.
Wenn es unbedingt sein muss sich selber eine Volltextsuche zu schreiben, dann würde ich auch SQL nehmen. Wenn man aber mit fertigen Suchmaschinen konkurrieren möchte, dann sehe ich keine guten Chancen für SQL. 1 Mio. Dokumente, je 100 Wörter, macht 100 Mio. Einträge in der Wort-Dokument-Zuordnung. Wenn nach zwei Wörtern gesucht werden soll, dann müssen für zwei Wörter die entsprechenden Dokumente herausgesucht, vereinigt, für jedes Dokument ein Relevanzmaß berechnet und das ganze sortiert werden. Das ist nicht wirklich wofür relationale Datenbanken optimiert sind, oder?
>Das ist nicht wirklich wofür relationale Datenbanken >optimiert sind, oder? Also ich glaube doch. Wozu sind SQL-Datenbanken eigentlich sonst gut. Wenn die Daten in einer Baumstruktur vorliegen sollten, dann ist es nicht optimal. Aber eine Abbildung mit rekursiver Datendefinition in SQL wäre dennoch möglich. Die meisten Möglichkeiten bietet Oracle. Da wurden beispielsweise verteilte Datenbanken(-dateien) eingebracht, um die Beschränkungen der Festplattengrösse der damaligen Computer zu überwinden. Man kann Informationen auf 1-Bitebene speichern oder unter einer grösseren Zahl Zugriffsmethoden bei einer Tabelle wählen. Interbase, Access und hsql und vielleicht noch ein paar andere, die ich nicht kenne sind nicht gut realisiert, dafür lohnt es sich nicht. > 1 Mio.Dokumente, je 100 Wörter, macht 100 Mio. Einträge in der > Wort-Dokument-Zuordnung. Nein, die 100 Wörter kommen in jedem Dokument oft vor, beispielsweise die Artikel oder das Wort des Monats. Aber egal, irgendwie muss man es ja sowieso speichern und dafür sind halbwegs gute SQL-Systeme schließlich konstruiert worden. Das relationale Modell soll "Redundanz" vermeiden helfen, sogenannte Sequenzen. Deswegen kann ein gut organisierter Tabellensatz das Optimum der Abbildung sein. Google speichert immer auch den Originaltext im sog. Cache ab. Beim auffinden einer Phrase wird im zweiten Schritt darauf zurückgegriffen. Google kennt da jedenfalls nix, die speichern alles. Performance geht denen über alles. Also Google funktioniert zwar sehr wahrscheinlich nicht mit SQL aber das ist Zufall, meines Erachtens. Recht hast du vermutlich schon, der Preis, den man für die eine gute Performance zahlen muss, der schlägt sich in irrsinnig grossen Dateien nieder. Nur ob es einer mit einer eigenen Datendatei hinterher kompakter hinkriegt als z.B. via Postgres unter Ausnutzung der Möglichkeiten da hege ich Zweifel.
>> 1 Mio.Dokumente, je 100 Wörter, macht 100 Mio. Einträge in der >> Wort-Dokument-Zuordnung. > > Nein, die 100 Wörter kommen in jedem Dokument oft vor, beispielsweise > die Artikel oder das Wort des Monats. Dein Beitrag enthält 186 unterschiedliche Wörter, das sind 186 Datensätze (beitrag_id, wort_id). > Aber egal, irgendwie muss man es > ja sowieso speichern Es geht nicht darum die Dokumente irgendwie zu speichern (gespeichert werden müssen sie sowieso), sondern einen Index anzulegen der sich effizient abfragen lässt.
>Es geht nicht darum die Dokumente irgendwie zu speichern (gespeichert >werden müssen sie sowieso), sondern einen Index anzulegen der sich >effizient abfragen lässt. Tja, was ist effizient. Mit Lucene habe ich z.B. schon gearbeitet und war mir im Vergleich zu langsam. Es bietet eigentlich nur ein Gerüst, eine Architektur. Am einfachsten ist lineare Suche und man braucht auch nicht viel zu speichern. Die Performance ist manchmal gar nicht so schlecht. www.leo.org mit agrep, find unter Linux. Manchmal muss es sogar sein, gerade wenn man nicht sicher ist, ob die gesuchte Datei schon im Index ist. Da ich mich mit der Thematik schon lange mehrfach beschäftigt habe, kenne ich die gängigen Techniken. http://de.wikipedia.org/wiki/Volltextsuche bietet einen Überblick und das habe ich auch schon mal alles in C, PHP und Access gemacht. Mein erster Entwurf hat wie htdig mit gdbm funktioniert. Ich habe auch viele Interessen und Projekte und möchte eigentlich nicht den Rest meines Lebens Suchmaschinen vorantreiben. Also meinen Beitrag verstehe ich als Anstoss, es einmal mit, sagen wir mysql zu probieren. Was du unter Möglichkeiten angesprochen hast, also das Ausformulieren einer Abfragesprache, das ist für mich kein Thema, weil ich eben schon oft Lispinterpreter und eigene Compiler für verschiedene Dialekte nachprogrammiert habe. SQL nimmt einem vieles ab, z.B. wildcardsuche. Du hast völlig Recht. Die Dateien werden riesengross und die Abbildung ist vielleicht nicht optimal. Ich hatte beim Entwurf aber eine Art Vollassoziativspeicher als Leitgedanken, es ist völlig egal wie es realisiert wird, nur die Funktionalität sollte entwickelt werden, es war ein KI-Projekt. Ranking ist eine Methode das Chaos bei den Ergebnissen einzudämmen eine andere ist das was ich entwickeln wollte. Und die Performance im Googlemodus ist wirklich sehr beeindruckend, zumindest habe ich das so erlebt. Ich habe das Dingens vor Publikum demonstriert (vielleicht so wie Frank Farian) mit Abfragezeiten unterhalb einer 1msec bei 1-MIO Einträge und nur ein müdes Lächeln geerntet, begleitet mit der höflichen Frage, ob es das auf einer Homepage gibt. Die Ergebnisse beim Rumblättern hätte ich in einem Cache versteckt. So sind sie halt die Leute, juckt mich heute nicht mehr. Es hat auch Leute gegeben, die sich bei mir schriftlich bedankt haben, weil es sie beruflich weitergebracht hätte. Auch die Erfahrung mit kostenfreier Software ist so, das einem die Ansprüche wachsen und es dann Leute gibt die Lucene für Wikipedia zunächst anpassen und dann aber verbessern müssen. Es gibt kein Tischlein deck dich. Trotzdem erreicht ein Opensourceprojekt manchmal einen beachtlichen Reifegrad und da kann es passieren, dass man mit seinem eigenen Zeugs die Zeit praktisch 100% in den Sand gesetzt hat. Was bleibt sind Erfahrungen und Fragmente, meistens nicht direkt nützlich im Leben. Als Person wird man bewertet, ob man für die Deutsche Bank geknechtet hat oder es in "seinem stillen Kämmerlein" gemacht hat, letzteres zählt nicht. Allerdings ich stehe da sowas von drüber :-)
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.