Im Kontext von In-Memory-Datenbanksystemen nehmen leichtgewichtige Kompressionsalgorithmen eine entscheidende Rolle ein, um eine effiziente Speicherung und Verarbeitung großer Datenmengen im Hauptspeicher zu realisieren. Verglichen mit klassischen Komprimierungstechniken wie z.B. Huffman erzielen leichtgewichtige Kompressionsalgorithmen vergleichbare Kompressionsraten aufgrund der Einbeziehung von Kontextwissen und erlauben eine schnellere Kompression und Dekompression. Die Vielfalt der leichtgewichtigen Kompressionsalgorithmen hat in den letzten Jahren zugenommen, da ein großes Optimierungspotential über die Einbeziehung des Kontextwissens besteht. Um diese Vielfalt zu bewältigen haben wir uns mit der Modularisierung von leichtgewichtigen Kompressionsalgorithmen beschäftigt und ein allgemeines Kompressionsschema entwickelt. Durch den Austausch einzelner Module oder auch nur eingehender Parameter lassen sich verschiedene Algorithmen einfach realisieren.:1 Einleitung 1
2 Modularisierung von Komprimierungsmethoden 5
2.1 Zum Literaturstand 5
2.2 Einfaches Schema zur Komprimierung 7
2.3 Weitere Betrachtungen 11
2.3.1 Splitmodul und Wortgenerator mit mehreren Ausgaben 11
2.3.2 Hierarchische Datenorganisation 13
2.3.3 Mehrmaliger Aufruf des Schemas 15
2.4 Bewertung und Begründung der Modularisierung 17
2.5 Zusammenfassung 17
3 Modularisierung für verschiedene Kompressionsmuster 19
3.1 Frame of Reference (FOR) 19
3.2 Differenzkodierung (DELTA) 21
3.3 Symbolunterdrückung 23
3.4 Lauflängenkodierung (RLE) 23
3.5 Wörterbuchkompression (DICT) 24
3.6 Bitvektoren (BV) 26
3.7 Vergleich verschiedener Muster und Techniken 26
3.8 Zusammenfassung 30
4 Konkrete Algorithmen 31
4.1 Binary Packing 31
4.2 FOR mit Binary Packing 33
4.3 Adaptive FOR und VSEncoding 35
4.4 PFOR-Algorithmen 38
4.4.1 PFOR und PFOR2008 38
4.4.2 NewPFD und OptPFD 42
4.4.3 SimplePFOR und FastPFOR 46
4.4.4 Anmerkungen zur differenzkodierten Daten 49
5.4 Simple-Algorithmen 49
4.5.1 Simple-9 49
4.5.2 Simple-16 50
4.5.3 Relative-10 und Carryover-12 52
4.6 Byteorientierte Kodierungen 55
4.6.1 Varint-SU und Varint-PU 56
4.6.2 Varint-GU 56
4.6.3 Varint-PB 59
4.6.4 Varint-GB 61
4.6.5 Vergleich der Module der Varint-Algorithmen 62
4.6.6 RLE VByte 62
4.7 Wörterbuchalgorithmen 63
4.7.1 ZIL 63
4.7.2 Sigmakodierte invertierte Dateien 65
4.8 Zusammenfassung 66
5 Eigenschaften von Komprimierungsmethoden 69
5.1 Anpassbarkeit 69
5.2 Anzahl der Pässe 71
5.3 Genutzte Information 74
5.4 Art der Daten und Arten von Redundanz 74
5.5 Zusammenfassung 77
6 Zusammenfassung und Ausblick 79
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:28790 |
| Date | January 2015 |
| Creators | Hildebrandt, Juliana |
| Contributors | Habich, Dirk, Damme, Patrick, Lehner, Wolfgang, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | doc-type:masterThesis, info:eu-repo/semantics/masterThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds