Ich habe eine große Datei, in der (Text-)Daten zeilenweise drin stehen.
Diese Datei ist sortiert (Zeile für Zeile).
Diese Datei ist einige 100 GB groß.
Es sind über 1 Milliarde (10^9) sortierte Datensätze.
Jetzt möchte ich darin suche, ob ein bestimmter Datensatz bereits
enthalten ist oder nicht.
Ich verwende bereits Hashes, damit ich aus den Datensätzen
(alle gleich lange, etwa 200 Bytes) einen kurzen Werte erhalte.
Ich verwende bereits Intervall-Schachtelung, damit ich schneller
an die Datensätze komme.
Da die Datei auch zum Transfer und der Verarbeitung recht groß ist,
habe ich sie gzipped (mittels gzip).
Ist es bei gzip möglich, z.B. in der Mitte der Datei
mit dem Entpacken anzufangen oder finde ich da nicht oder schlecht
den richtigen Einsprungspunkt. Benötige ich Informationen,
die nur am Anfang vorhanden sind?
Gibt es vielleicht einen anderen Packer/Entpacker, der so etwas
kann?
Oder hat jemand einen anderen Trick, wie ich die Daten etwas
kleiner bekomme und trotzdem noch damit arbeiten kann?
Wäre es eigentlich grundsätzlich denkbar, solch eine Datei
eine Datenbank zu befördern? A la MySQL? Oder wäre Datenbanken
mit so etwas maßlos überfordert und würden ein Vielfaches
an Rechenleistung brauchen, um damit zu arbeiten, als
wenn ich weiß, wie die Daten aufgebaut sind und optimaler
darauf zugreifen kann?
Gzip ist eigentlich gut geeignet für Dein Vorhaben: Du kannst einen
Kompressionsstrom an einem beliebigen Punkt neu starten. Du kannst dann
später ab diesem Punkt wieder direkt mit dem entpacken beginnen ohne das
beachten zu müssen was an Daten davor steht.
Du könntest also z.B. jede 100. Zeile einen neuen Kompressionsstrom
beginnen lassen und Dir in einer Indextabelle die entsprechenden
Byte-Positionen merken. Jetzt kannst Du diese Punkte dann direkt
anspringen und von dort ab entpacken.
Ich würde nicht jede Zeile einen neuen Kompressionsstrom beginnen, da
dann die Packrate darunter leidet.
Datenhungrig schrieb:> Da die Datei auch zum Transfer und der Verarbeitung recht groß ist,> habe ich sie gzipped (mittels gzip).
Und du meinst, das trägt irgendwie zu einem schnelleren Zugriff bei?
Wenn du Originaldatei als Binärdatei öffnest, solltest du nach etwa 31
Seek-Operationen beim richtigen Datensatz sein. Das ist doch nicht sooh
schlimm. Und auf eine aktuelle Festplatte passen immerhin noch etliche
von deinen Dateien drauf.
Du könntest dir anschauen wie git das macht, die tun sowas ähnliches. Da
gibt es ein pack-file und einen Index für das pack-file. Mehr dazu steht
in den man-pages für git-repack, git-pack-objects und git-index-pack.
Vielleicht ist ein ähnliches Vorgehen ja auch für deinen Fall sinnvoll?
Gerd E. schrieb:> Gzip ist eigentlich gut geeignet für Dein Vorhaben:
Genauer: Das Kompressionsverfahren, also eher die zlib (www.zlib.net).
Das Programm dazu musst du selbst schreiben. Ansonsten würde ich Gerds
Vorgehensweise unterstützen...
Wonach sind die Daten sortiert? Du könntest die Datei entsprechend ihrer
Indexierung splitten und ähnlich dem Alphabet für jeden Index/Sortierung
(Buchstaben, Zahlen, erstes Byte, was auch immer) eine Datei anlegen.
Verglichen mit dem Alphabet brauchst du bei optimaler Verteilung der
Daten nur ein 1/26 der Zeit als wenn du deine Datei als ganzes hast.
Außerdem ist das Datei-Handling wesentlich einfacher da die einzelnen
Dateien nur ein "paar" GB groß sind. Welchen Kompressionsfaktor
erreichst du? Oftmals ist eine Kompression bei solchen Daten nicht
zielführend. Eine (SQL-) Datenbank in dieser Größe dürfte m.M.n. dein
System sprengen.
Datenhungrig schrieb:> Oder hat jemand einen anderen Trick, wie ich die Daten etwas> kleiner bekomme und trotzdem noch damit arbeiten kann?
Hast du derzeit irgendein relevantes Problem in Bezug auf den
Speicherbedarf auf der Festplatte und/oder die Zugriffszeit?
Beschreibe doch mal die Textdaten genauer: Wie mächtig ist das Alphabet?
Also sind die Textdaten beispielsweise nur formatierte Zahlen? Dann
könnte man das Alphabet auf die Zeichen '0' .. '9' (ggf.
Dezimaltrenner/Vorzeichen) eindampfen, also effektiv eine binäre
Speicherform wählen. Das würde Speicherplatz und letztlich auch
Zugriffs-/Parserzeit sparen. Ganz erheblich sogar.
Jens schrieb:> Verglichen mit dem Alphabet brauchst du bei optimaler Verteilung der> Daten nur ein 1/26 der Zeit als wenn du deine Datei als ganzes hast.
Das ist falsch. Die Zeit zum suchen fällt in diesem Fall im Dateisystem
an und nicht im eigentlichen Programmcode, gebraucht wird sie aber
trotzdem. Das kann man sich ganz einfach klar machen: Wenn ich jeden
Datensatz als eine leere Datei mit entsprechendem Namen anlege würde ich
nach deinem Argument keinerlei Zeit brauchen (und weitergedacht auch
keinen Speicherplatz, weil die Dateien ja alle 0 Byte groß sind).
Viel effizienter als eine binäre Suche in einer sortieren Liste wird man
wohl nicht werden. Sind ja dann nur log2(n) Schritte nötig, hier also
ca. 30 Schritte. Etwas Zeit lässt sich wohl noch sparen, wenn man für
die ersten paar Schritte einen vollständigen Index aufbaut der komplett
in den RAM passt. Darauf lässt sich dann in konstanter Zeit zugreifen,
aber viel spart man damit nicht.
Die Information, die jetzt wichtig wäre ist: Wie oft und wie schnell
muss auf die Daten zugegriffen werden. Je stärker man versucht zu
komprimieren um so länger wird wohl die Zugriffszeit.
>Wäre es eigentlich grundsätzlich denkbar, solch eine Datei>eine Datenbank zu befördern? A la MySQL? Oder wäre Datenbanken>mit so etwas maßlos überfordert und würden ein Vielfaches>an Rechenleistung brauchen, um damit zu arbeiten, als>wenn ich weiß, wie die Daten aufgebaut sind und optimaler>darauf zugreifen kann?
Datenbanken wäre für sowas schon sinnvoll, da man ja indizieren kann,
womit die Suche dann "rasend" schnell wird. Allerdings braucht der Index
aber auch Platz, was man aber wieder durch Datenkompression kompensieren
kann.
Paar 100Gb sind (je nach DB) kein Problem.
R2 D2 schrieb:> Jens schrieb:>> Verglichen mit dem Alphabet brauchst du bei optimaler Verteilung der>> Daten nur ein 1/26 der Zeit als wenn du deine Datei als ganzes hast.>> Das ist falsch. Die Zeit zum suchen fällt in diesem Fall im Dateisystem> an und nicht im eigentlichen Programmcode, gebraucht wird sie aber> trotzdem. Das kann man sich ganz einfach klar machen: Wenn ich jeden> Datensatz als eine leere Datei mit entsprechendem Namen anlege würde ich> nach deinem Argument keinerlei Zeit brauchen (und weitergedacht auch> keinen Speicherplatz, weil die Dateien ja alle 0 Byte groß sind).
Kommt drauf an. Wenn wie angenommen die Verteilung optimal ist, heißt
das letztlich, dass mit dem ersten Suchzeichen der Dateiname bekannt
ist. Ob jetzt die gesamte Datei geöffnet wird (von mir aus auch ab der
passenden Position, wenn es einen Index gibt) oder der Dateiname zuvor
erst aus einem Array mit 26 Einträgen geholt werden muss (Zugriff in
konstanter Zeit) und dann vom Betriebssystem geöffnet wird, ist egal.
Das OS sucht in jedem Fall erst mal die Datei...
> Viel effizienter als eine binäre Suche in einer sortieren Liste wird man> wohl nicht werden. Sind ja dann nur log2(n) Schritte nötig, hier also> ca. 30 Schritte. Etwas Zeit lässt sich wohl noch sparen, wenn man für> die ersten paar Schritte einen vollständigen Index aufbaut der komplett> in den RAM passt. Darauf lässt sich dann in konstanter Zeit zugreifen,> aber viel spart man damit nicht.
log(log(n)) wären mit Interpolation Search u.U. möglich wenn's gut
läuft.
> Die Information, die jetzt wichtig wäre ist: Wie oft und wie schnell> muss auf die Daten zugegriffen werden. Je stärker man versucht zu> komprimieren um so länger wird wohl die Zugriffszeit.
"Searching BWT compressed text with the Boyer-Moore algorithm and binary
search" und ähnliche Verfahren könnten vielleicht noch interessant sein
http://corpus.canterbury.ac.nz/research/search_bwt.pdf
Datenhungrig schrieb:> Oder hat jemand einen anderen Trick, wie ich die Daten> etwas kleiner bekomme und trotzdem noch damit arbeiten> kann?
Sicher, unzählige.
Es wäre aber hilfreich, den Aufbau Deiner Datensätze zu
kennen.
Datensätze mit völlig zufälligen Bytes benötigen
(trivialerweise) zur Codierung 8Bit je Byte.
Datensätze mit zufälligem Text (A-Za-z0-9 .) benötigen
6Bit je Byte.
Datensätze aus Integerzahlen benötigen 3.x Bit je Byte.
Datensätze, die deutschen Text enthalten, benötigen
asmyptotisch 1.6Bit je Zeichen.
poste mal ein paar Beispielzeilen deiner Daten.
Je nach Aufbau reduziert sich ja bei Benutzung eines RDBMS durch
Normalisierung die Datenmenge ja auch deutlich.
Datenhungrig schrieb:> Ich habe eine große Datei, in der (Text-)Daten zeilenweise drin> stehen.> Diese Datei ist sortiert (Zeile für Zeile).> Diese Datei ist einige 100 GB groß.> Es sind über 1 Milliarde (10^9) sortierte Datensätze.
Ich würde mir mal eher Gedanken machen solchen Datenmengen anders zu
verwalten als in einer Textdatei, das ist doch Steinzeit-IT auf
Stümperniveau.
Datenhungrig schrieb:> ...>> Wäre es eigentlich grundsätzlich denkbar, solch eine Datei> eine Datenbank zu befördern? A la MySQL? Oder wäre Datenbanken> mit so etwas maßlos überfordert und würden ein Vielfaches> an Rechenleistung brauchen, um damit zu arbeiten, als> wenn ich weiß, wie die Daten aufgebaut sind und optimaler> darauf zugreifen kann?
PostgreSQL z.B. kann das:
Maximum Database Size Unlimited
Maximum Table Size 32 TB
Maximum Row Size 1.6 TB
Maximum Field Size 1 GB
Maximum Rows per Table Unlimited
Maximum Columns per Table 250 - 1600 depending on column types
Maximum Indexes per Table Unlimited
Andere DBs können das natürlich auch, aber von den großen, "freien" wäre
PostgreSQL, zumindest zum jetzigen Zeitpunkt, mein Favorit.
Albrecht H. schrieb:> PostgreSQL z.B. kann das:> ...
Welchen Vorteil soll hier eine Datenbank bringen? einen Sinnvollen Index
in einer extra Datei sollte für diese Anwendung ausreichend sein.
Er will ja nur schnell eine Datensatz aus einer großen Menge
selektieren. Dafür braucht man keine Datenbank.
Er müsste dafür auch regelmäßig die Textdatei in die Datenbank landen.
Für sinnvolle Vorschläge müsste man mehr Wissen über die Daten haben,
wenn z.b. mehre Millionen Zeilen mit den gleichen 10 Zeichen anfangen,
dann könnte man das schon sparsamer speichern.
Peter II schrieb:> Albrecht H. schrieb:>> PostgreSQL z.B. kann das:>> ...>> Welchen Vorteil soll hier eine Datenbank bringen? einen Sinnvollen Index> in einer extra Datei sollte für diese Anwendung ausreichend sein.>
Der OP hat gefragt ob das funktioniert und das tut es. Ein Vorteil der
mir sofort einfällt wäre der Transfer einer 100GB-Datei von Ort A nach
Ort B, der könnte entfallen, es müssten zukünftig nur noch einzelne
Datensätze übers Netz transportiert werden.
Und wenn man erst mal alles in einer Datenbank hat, fallen einem ja
gleich noch 10 weitere Dinge ein, die man schon immer gerne gehabt
hätte, die einem aber bisher als zu umständlich erschienen.
> Er will ja nur schnell eine Datensatz aus einer großen Menge> selektieren. Dafür braucht man keine Datenbank.> Er müsste dafür auch regelmäßig die Textdatei in die Datenbank landen.>> Für sinnvolle Vorschläge müsste man mehr Wissen über die Daten haben,
Richtig.
> ...
