Wörter in Textdatei suchen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo!

Ich schreibe gerade an einem Programm (Sprache ist VB.NET; Framework 2.0), in dem nach Stichworten gesucht werden soll. Die Daten stammen aus OCR erkannten Bildern.

Die Stichwortdatei ist derzeit so aufgebaut, dass pro Zeile ein Wort steht und das Vorkommen (also z.B.: „bahnhof“,„1928/117“). Dadurch, dass viele Dokumente durchsuchbar sein sollen, sind in der Datei über 3 Millionen Einträge (bzw. Zeilen).

Jetzt bin ich auf der Suche nach einer Lösung, diesen Datenberg so schnell wie möglich durchsuchen zu können. Bei der Suchfunktion soll man auch Wörter ausschließen können bzw. bei mehreren angegebenen Ausdrücken diese als UND-Verknüpfung auswerten.

Habt ihr Ideen dazu?

mfg
chris

#2

Hallo,

Ich schreibe gerade an einem Programm (Sprache ist VB.NET;
Framework 2.0), in dem nach Stichworten gesucht werden soll.
Die Daten stammen aus OCR erkannten Bildern.

Die Stichwortdatei ist derzeit so aufgebaut, dass pro Zeile
ein Wort steht und das Vorkommen (also z.B.:
„bahnhof“,„1928/117“). Dadurch, dass viele Dokumente
durchsuchbar sein sollen, sind in der Datei über 3 Millionen
Einträge (bzw. Zeilen).

Jetzt bin ich auf der Suche nach einer Lösung, diesen
Datenberg so schnell wie möglich durchsuchen zu können. Bei
der Suchfunktion soll man auch Wörter ausschließen können bzw.
bei mehreren angegebenen Ausdrücken diese als UND-Verknüpfung
auswerten.

Habt ihr Ideen dazu?

Die einfachste Lösung wäre, die Daten alle in eine Datenbank zu schreiben, und die einen Index erstellen lassen, dann kannst du damit eine effiziente Volltextsuche machen.

Die nicht so einfache Lösung wäre, das ganze von Hand zu machen, und damit die Funktionalität der Datenbank nachzuprogrammieren, also quasi das Rad neu zu erfinden.

Ich würde da eher zur ersten Lösung tendieren :wink:

Grüße,
Moritz

#3

Hallo chris,

unabdingbare Voraussetzung ist, dass du die Datei erstmal alphabetisch sortierst. Selbst wenn es eine unformatierte Textdatei bleibt, kannst du anschliessend binär suchen, also zuerst in der Mitte der Datei nachschauen, dann siehst du, ob der Begriff davor (also in der ersten Hälfte) oder danach liegt, usw. usw. Das beschleunigt die Suche schon mal um Grössenordnungen.

Gruss Reinhard

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Hallo,

Die Stichwortdatei ist derzeit so aufgebaut, dass pro Zeile
ein Wort steht und das Vorkommen (also z.B.:
„bahnhof“,„1928/117“). Dadurch, dass viele Dokumente
durchsuchbar sein sollen, sind in der Datei über 3 Millionen
Einträge (bzw. Zeilen).

Jetzt bin ich auf der Suche nach einer Lösung, diesen
Datenberg so schnell wie möglich durchsuchen zu können. Bei
der Suchfunktion soll man auch Wörter ausschließen können bzw.
bei mehreren angegebenen Ausdrücken diese als UND-Verknüpfung
auswerten.

3 Millionen Zeilen?

Ich hab hier mal probeweise den Nietsche-Volltext in
.txt-Format (14,2 Millionen Bytes) getestet, ein
simples

 $start = time();
 local $/; $\_=;
 ++$h{$1},++$total while /(\w+)/g;
 @a = sort{ $h{$a} $h{$b} } keys %h;
 print "N: $total, diff: ", scalar keys %h, "\n", time()-$start, " sec\n";

braucht (mit Programmstart+Einlesen der Datei)
ohne Sortieren der gefundenen unterschiedlichen Worte knapp
2 Sekunden, mit Sortieren knapp 3 Sekunden (Es sind 2,335,569
Worte, davon 93,405 Verschiedene).

Nach diesen knapp 2 Sekunden wären alle vorhandenen Worte
in ~ O(1) zugreifbar (Dictionary/Hash).

Ich halte das schon noch für ein „kleines“ Problem,
dessen Lösung man ohne Weiteres „mal schnell dazubasteln
kann“ :wink:

Kannst Du noch mehr zur Anwendung (Programm) sagen?

Grüße

CMБ

#5

Hallo chris,

vielleicht „Regular Expression“?

Manfred

#6

Hallo!

Kannst Du noch mehr zur Anwendung (Programm) sagen?

Auf einer DVD befinden sich ~8000 jpegs, die von einer alten Zeitschrift eingescannt wurden. Die jpegs wurden auch geOCRt und als einzelne Textdateien gespeichert.

Der Inhalt der Textdateien wurde dann wortweise aufgeteilt und mitsamt der Information von welcher Seite (der Zeitschrift) das Wort stammt in einer einzigen Volltextdatei abgespeichert. Für das Format habe ich im Ursprungsposting ja schon ein Beispiel gegeben. Was noch zu Erwähnen wäre ist, dass Worte ja mehrfach vorkommen können, da pro Zeile ja nur ein Wort und ein Verweis auf die Seite eingetragen ist.

Weiters wurden die Inhaltsverzeichnisse der Zeitschrift per Hand digitalisiert.

Mit dem Programm soll nun durch die Zeitschrift (die Bilder) geblättert werden können (vor, zurück, direkt auf eine Seite springen, einen Jahrgang auswählen). Dazu kann man auch das Inhaltsverzeichnis ansehen und nach bestimmten Kriterien filtern[1] können. Und dann soll man eben auch noch im Volltext nach Stichworten suchen können.

mfg
chris

[1] Dazu lade ich die Inhaltsverzeichnisdaten in eine DataTable, filtere mit Hilfe eines BindingSource und zeige es als Tabelle in einem DataGridView an.

#7

Moien

Jetzt bin ich auf der Suche nach einer Lösung, diesen
Datenberg so schnell wie möglich durchsuchen zu können.

Wie viel Zeit hast du und wie gut sind deine Programmierkenntnisse?

(m = Textlänge, n = Suchstringlänge)

Das ganze Zeug in eine SQL-DB packen und ein Index drüber bauen lassen ist die einfachste Variante. SQL-DBs sind verflucht schnell wenn es um das Finden von Wortanfängen geht. ( suchen in O(log(m)) )

Einen Zacken komplexer wäre es das Prinzip der SQL-DB Indexe nachzubauen (Sortierte Liste mit Präfix/Suffix-Komprimierung). I.d.R. sind die selbstgebauten langsamer oder speicherintensiver als die aus den SQL-DBs.

Aprops Speicher: so ein Index muss einigermassen komplett im RAM liegen, sonst hat eh verloren. Deshalb der Aufwand mit Präfix/Suffix-Komprimierung.

All diese Taktiken haben einen Nachteil: sie finden nur Wortanfänge schnell. Alles andere dauert ewig. Deshalb hat man Suffix-Bäume entwickelt. Diese finden alle Wörter und Wortteile und sind richtig, richtig schnell. Allerdings verbrauchen die auch richtig viel Speicher und die Implementierung ist komplex. ( suchen in O(n + k*c) wobei c die Anzahl der Vorkommnisse ist und k sich im Bereich log(log(m)) bewegt )

Suffix-Arrays mach das gleiche, sind nicht ganz so schnell und auch nicht ganz so komplex. Richtig implementiert sind sie auch nicht ganz so Speicherintensiv.

cu