mikrocontroller.net

Forum: PC-Programmierung Algorithmen für Textindizierung bzw. Schlagwortfindung?


Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Such mal nach Suffix-Tree, das ist ne schicke Datenstruktur die dafuer 
geeignet ist. Bei pfiffiger Implementierung linearer Speicheraufwand

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://swish-e.org/ könntest Du Dir auch mal ansehen, vielleicht musst 
Du das Rad ja gar nicht neu erfinden.

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke, bin dabei, mic da durchzuquälen ...

Frank

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Frank Esselbach (Firma: Q3) (qualidat)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> 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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: pfft.. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: htdig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: htdig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: htdig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> 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.

Autor: htdig (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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 :-)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.