Datenkompressionsalgorithmen

Lesezeit: 4 Minuten

Ich habe mich gefragt, ob jemand eine Liste von Datenkomprimierungsalgorithmen hat. Ich weiß im Grunde nichts über Datenkomprimierung und hatte gehofft, mehr über verschiedene Algorithmen zu erfahren und zu sehen, welche die neuesten sind und auf vielen ASICs noch entwickelt werden müssen.

Ich hoffe, einen Datenkomprimierungs-ASIC zu implementieren, der unabhängig von der Art der eingehenden Daten ist (Audio, Video, Bilder usw.).

Wenn meine Frage zu offen ist, lassen Sie es mich bitte wissen und ich werde sie überarbeiten. Vielen Dank

  • Hmmmm, es gibt viele Komprimierungsalgorithmen, nach denen Sie in Bezug auf die “Besten” suchen. Zum Beispiel Geschwindigkeit oder völlig verlustfrei oder höchste Komprimierungsrate? In Bezug darauf, welche ASICs für sie entwickelt wurden, ist das eher eine Forschungsfrage. Ich bin mir sicher, dass die meisten, wenn nicht alle gängigen Komprimierungsalgorithmen eine Art ASIC-Implementierung haben.

    – Nomad101

    9. Mai 2013 um 19:18 Uhr


  • ccs.neu.edu/home/jnl22/oldsite/cshonor/jeff.html

    – taocp

    9. Mai 2013 um 19:19 Uhr

  • @taocp defekter Link

    – nz_21

    17. Mai 2020 um 22:30 Uhr

Benutzeravatar von user123
Benutzer123

Es gibt eine Menge Komprimierungsalgorithmen. Was Sie hier brauchen, ist ein verlustfreier Komprimierungsalgorithmus. Ein verlustfreier Komprimierungsalgorithmus komprimiert Daten so, dass sie dekomprimiert werden können, um genau das zu erreichen, was vor der Komprimierung gegeben war. Das Gegenteil wäre ein verlustbehafteter Komprimierungsalgorithmus. Verlustbehaftete Komprimierung kann Daten aus einer Datei entfernen. PNG-Bilder verwenden eine verlustfreie Komprimierung, während JPEG-Bilder eine verlustbehaftete Komprimierung verwenden können und dies häufig tun.

Zu den bekanntesten Komprimierungsalgorithmen gehören:

ZIP-Archive verwenden eine Kombination aus Huffman-Codierung und LZ77, um schnelle Komprimierungs- und Dekomprimierungszeiten zu erzielen und ziemlich gute Kompressionsverhältnisse.

LZ77 ist so ziemlich eine verallgemeinerte Form von RLE und liefert oft viel bessere Ergebnisse.

Huffman lässt zu, dass die sich am meisten wiederholenden Bytes die geringste Anzahl von Bits darstellen. Stellen Sie sich eine Textdatei vor, die so aussieht:

aaaaaaaabbbbbcccdd

Eine typische Implementierung von Huffman würde zu folgender Karte führen:

Bits Character
   0         a
  10         b
 110         c
1110         d

Die Datei würde also folgendermaßen komprimiert:

00000000 10101010 10110110 11011101 11000000
                                       ^^^^^
                              Padding bits required

18 Bytes werden zu 5. Natürlich muss die Tabelle in der Datei enthalten sein. Dieser Algorithmus funktioniert besser mit mehr Daten: P

Alex Allain hat ein schöner Artikel zum Huffman-Kompressionsalgorithmus, falls das Wiki nicht ausreicht.

Fordern Sie weitere Informationen an. Dieses Thema ist verdammt umfangreich.

  • Ich frage nur aus Neugier: Gibt es Komprimierungsalgorithmen, die Muster in den Daten erkennen können? Zum Beispiel: ababab.

    – Novak

    9. Mai 2013 um 20:04 Uhr


  • Das ist eine etwas komplexere Version von RLE, oder genauer gesagt, LZ77 😛 (Damit meine ich, dass LZ77 das handhabt, aber es wird normalerweise nichts tun, es sei denn, die Manipulation eines Datenteils wird die Datei verkleinern)

    – Benutzer123

    9. Mai 2013 um 20:05 Uhr


  • @ Magtheridon96, wow, vielen Dank. Kennen Sie Ressourcen, die Leistungsmerkmale dieser Algorithmen auf verschiedenen Plattformen zeigen? Zum Beispiel, wie schnell jemand Huffman zum Laufen bringen konnte und ob es sich um eine Software- oder Hardwareimplementierung handelte? Ich möchte eine Hardware-Datenkomprimierungseinheit implementieren (wenn ich es für sinnvoll halte), die eine erhebliche Verbesserung gegenüber einer Softwareimplementierung bieten würde.

    – Veridian

    13. Mai 2013 um 15:46 Uhr

  • @Magtheridon96, muss ich statistische Informationen über die eingehenden Daten im Voraus wissen? Ich plane nur den Umgang mit binären Daten.

    – Veridian

    13. Mai 2013 um 15:54 Uhr

  • @FábioDuqueSilva Nun, ich weiß nicht, wie Implementierungen das machen, aber ich weiß, dass es mit O (1) -Leerzeichen möglich ist, weil Sie eine zusätzliche Ganzzahl hinzufügen können, um die Füllbits ganz am Ende zu verfolgen (dh zusammen mit dem Tabelle speichern Sie eine zusätzliche Ganzzahl: 5)

    – Benutzer123

    4. März 2020 um 12:27 Uhr

Mein Papier Ein Überblick über architektonische Ansätze zur Datenkomprimierung in Cache- und Hauptspeichersystemen (Dauerlink hier) überprüft viele Komprimierungsalgorithmen und auch Techniken für deren Verwendung in modernen Prozessoren. Es überprüft sowohl wissenschaftliche als auch kommerzielle Komprimierungsalgorithmen/-techniken, sodass Sie möglicherweise einen finden, der noch nicht in ASIC implementiert wurde.

Benutzeravatar von sma
klein

Hier sind einige verlustfreie Algorithmen (mit denen die Originaldaten perfekt wiederhergestellt werden können):

  • Huffman-Code
  • LZ78 (und LZW-Variante)
  • LZ77
  • Arithmetische Codierung
  • Ablauf
  • Vorhersage mit teilweiser Übereinstimmung (ppm)

Viele der bekannten Formate wie png oder gif verwenden Varianten oder Kombinationen davon.

Auf der anderen Seite gibt es auch verlustbehaftete Algorithmen (kompromittiert die Genauigkeit, um Ihre Daten zu komprimieren, funktioniert aber oft ziemlich gut). Hochmoderne verlustbehaftete Techniken kombinieren unter anderem Ideen aus der Differenzcodierung, Quantisierung und DCT.

Um mehr über Datenkomprimierung zu erfahren, empfehle ich https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7. Es ist ein sehr zugänglicher Einführungstext. Die 3. Auflage gibt es als pdf online.

Es gibt eine Menge Datenkomprimierungsalgorithmen. Wenn Sie nach etwas Enzyklopädischem suchen, empfehle ich die Handbuch der Datenkomprimierung von Salomon u.

Meine beste Vermutung ist, dass die ASIC-basierte Komprimierung normalerweise für eine bestimmte Anwendung oder als spezialisiertes Element eines SoC und nicht als eigenständiger Komprimierungschip implementiert wird. Ich bezweifle auch, dass die Suche nach einem “neuesten und besten” Komprimierungsformat hier der richtige Weg ist – ich würde erwarten, dass Standardisierung, Reife und Eignung für einen bestimmten Zweck wichtiger sind.

Der LZW- oder Lempel-Ziv-Algorithmus ist ein großartiger verlustfreier Algorithmus. Pseudocode hier: http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html

1401920cookie-checkDatenkompressionsalgorithmen

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy