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
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 :-)
