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?
:
Bearbeitet durch User
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.
vergesst den thread. der Op hat seit der Frage hier nix mehr gesagt.
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. > ...
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.