|
QuickBasic Tutorials In diesem Tutorial soll die Problematik Datenkomression behandelt werden. Die 3 gebräuchlichsten Kompressionsformen bzw. -methoden sind RLE (Run Lenght Encoding) zu deutsch: Lauflängenkodierung, der Huffman-Algorithmus und der LZW-Algorithmus. Diese unterschiedlichen Vorgehens- und Funktionsweisen sollen hier näher beschrieben werden. Das Tutorial basiert zum Teil auf einem im Internet veröffentlichten Projektbericht von Daniel Seifert. Huffman-Kompressionsalgorithmus LZW-Kompressionsalgorithmus
Dies ist der einfachste Kompressionsalgorithmus. Wie eventuell bereits aus dem Namen ersichtlich ist, werden in der zu packenden Datei Bytes gesucht, welche mehrmals hintereinander auftreten. Wurde solch eine Zeichenkette (z.B. ,,aaaaaa'') gefunden, wird nicht sie, sondern ihre ,,Beschreibung'' in die Ausgabedatei geschrieben. Dazu wird ein speziell für diesen Zweck reserviertes Zeichen in die Ausgabedatei geschrieben (im vorliegenden Fall durch die Konstante ,,RLE_ESCAPE'', die standardmäßig den Wert 255 beinhaltet, beschrieben). Im darauffolgenden Byte wird dann in die Ausgabedatei geschrieben, wie oft genau das Zeichen, welches schließlich im dritten Byte gespeichert wird, denn eigentlich hintereinander an dieser Stelle auftritt. Das obengenannte Beispiel (,,aaaaaa'') würde also folgendermaßen in die Ausgabedatei geschrieben, <RLE_ESCAPE> <7> <a>. Zeichen, die vereinzelt stehen, werden ohne besondere Behandlung in die Ausgabedatei geschrieben, zum Beispiel ,,abc'' als ,,abc''. Eine Ausnahme macht hier der sogenannte Escapecharacter, also RLE_ESCAPE. Da beim Dekomprimieren dieser Datei vom Dekompressionsalgorithmus erwartet wird, daß die beiden folgenden Bytes beschreiben, welches Byte wie oft folgt, ist es nicht möglich, den Escapecharacter, falls er so in der Datei auftaucht, ,,nur so'' in die Ausgabedatei zu schreiben. Es ist demzufolge nötig, ihn speziell zu kodieren. Das passiert, indem einfach in die Ausgabedatei geschrieben wird, daß der Escapecharacter RLE_ESCAPE genau einmal vorkommt, <RLE_ESCAPE> <1> <RLE_ESCAPE>. Anwendung RLE ist ein relativ selten verwendeter Kompressionsalgorithmus, da er nur bei bestimmten Dateien einen akzeptablen Kompressionswert erreicht. Dies sind im allgemeinen Bilder (zum Beispiel lassen sich .bmp Bilder relativ gut mit diesem Algorithmus packen, insbesondere, wenn im Bild große einfarbige Bereiche zu finden sind). Bei einer ,,normalsterblichen'' Textdatei oder einem ausführbaren Programm ist RLE aber normalerweise wenig von Nutzen. Schwachstellen Wie im vorigen Abschnitt bereits erwähnt, ist RLE nicht besonders für ausführbare Programme geeignet. Dies trifft auf andere Binärdateien, welche nicht einen großen Prozentsatz von gleichbleibenden Bytefolgen besitzen, ebenfalls zu. Begründet liegt das darin, daß in solchen Dateien die Wahrscheinlichkeit, auf den Escapecharacter zu stoßen, naturgemäß größer ist. Den ASCII-Code 255 findet man in puren Textdateien zum Beispiel überhaupt nicht, in Binärdateien kommt er dagegen sehr häufig vor. Da aber jedes Auftreten des Escapecharacters in der Eingabedatei zur Folge hat, daß drei Bytes in die Ausgabedatei geschrieben werden, ist es durchaus möglich, daß die Ausgabedatei nicht nur unwesentlich größer als die Eingabedatei ist - nicht gerade eine gute Komprimierung. Abhilfe würde hier schaffen, den Escapecharacter zu wechseln - zum Beispiel immer abwechselnd ASCII-Code 222 und 255. Aber das hilft auch nur begrenzt. Besser ist, hier auf einen ,,moderneren'' Algorithmus umzusteigen. zurück nach oben
Dieser Kompressionsalgorithmus, nach seinem ,,Erfinder'' benannt, geht an das Problem, Dateien (mit beliebigem Inhalt) zu packen, anders heran als RLE. Wenn man sich eine beliebige Datei anschaut, wird man feststellen, daß bestimmte Zeichen öfter auftauchen als andere. Nehmen wir zum Beispiel an, daß uns die folgende, kurze Textdatei vorliegt, welche nur ein Wort beinhaltet: Die Verteilung der einzelnen Zeichen sieht folgendermaßen aus,
Wie zu sehen ist, kommen 'i' und 's' wesentlich häufiger vor als 'M' und 'p'. Es liegt also (mehr oder weniger) nahe, die unterschiedlichen Zeichen mit unterschiedlicher Länge zu speichern. Mit Länge ist hier gemeint, daß das Zeichen 'i' in der Ausgabedatei mit weniger Bits beschrieben wird, als zum Beispiel das Zeichen 'M'. Statisch Beim ,,Statischen Huffmanalgorithmus'' steht bereits vorher fest, welches Zeichen durch wieviel Bits (und insbesondere, durch welche Bits) codiert wird. Der Vorteil ist, daß sich so der Algorithmus auch leicht auf Hardwareebene implementieren läßt und dadurch ziemlich schnell wird. So findet diese Huffman-Variante z.B. in Faxmaschinen ihre Anwendung. Der Nachteil besteht andererseits darin, daß die vorgegebene Verteilung nicht unbedingt auf die zu packenden Daten zutrifft, so daß nicht die höchstmögliche Kompression erreicht wird. Dynamisch Beim ,,Dynamischen Huffmanalgorithmus'' werden die Bitfolgen für die einzelnen Zeichen erst zur Laufzeit ermittelt. Die Erstellung eines Huffman-Baumes Nachdem ermittelt wurde, welches Zeichen wie häufig vorkommt, wird aus diesen Informationen der Huffman-Baum gewonnen. Dazu legt man für jedes in der Textdatei vorhandene Zeichen eine Struktur an.
Wie gesagt, wird gezählt, welches Zeichen wie oft vorkommt. Für jedes Zeichen, welches mindestens einmal in der zu packenden Datei vorkommt, wird solch eine Struktur vom Typ HuffNode angelegt. Dabei sind ,,left'' und ,,right'' ungesetzt. Bei den so gewonnenen ,,Baumblättern'' (maximal 256 an der Zahl), handelt es sich um die Basis des aufzubauenden Huffman-Baumes. Aus diesen ,,Blättern'' wird jetzt der Baum gewonnen. Dazu wird sich eines relativ simplen Algorithmus' bedient.
Die Kompression einer Datei Nachdem wir nun den Huffman-Baum für die zu packende Datei aufgebaut haben, können wir die Datei endlich komprimieren. Um die Arbeit zu erleichtern, fügen wir hier aber noch einen anderen Schritt ein. Und zwar erstellen wir erst einmal eine sogenannte Übersetzungstabelle. Dies ist ein Array, welches für jedes im ASCII-Zeichensatz vorkommende Zeichen bestimmt, mit wieviel Bits und mit welchen Bits das betreffende Zeichen kodiert wird. Damit erleichtern wir uns die Arbeit ungemein, da wir so nicht bei jedem Zeichen aus der Datei wieder den ganzen Baum nach dem Zeichen durchsuchen müssen. Nachdem wir diese Übersetzungstabelle angelegt haben, sieht sie für unser Beispiel folgendermaßen aus:
Um die Datei nun zu komprimieren, lesen wir sie Byte für Byte. Für jedes gelesene Byte suchen wir aus unserer Tabelle den entsprechenden Bitwert heraus und schreiben ihn in die Datei. Um dies zu ermöglichen, immerhin ist das bit-weise Beschreiben einer Datei im Allgemeinen in Programmiersprachen nicht vorgesehen, wird eine extra dafür geschriebene Routine benutzt. Diese speichert unter Zuhilfenahme eines 4 Byte (32 Bit) langen Buffers zu schreibende Bits bis zum Erreichen der Bytegrenze. Somit ist es ohne Probleme möglich, 3 Bits in eine Datei zu schreiben. Die Dekompression einer Datei Um eine Huffman-gepackte Datei wieder zu dekomprimieren, ist es unerläßlich, daß der zum Komprimieren benutzte Huffman-Baum bekannt ist. Das impliziert, daß der Huffman-Baum vom Kompressionsalgorithmus mitgespeichert werden soll (es sei denn, es handelt sich um den statischen Huffman-Algorithmus, wo der Huffman-Baum ja festgelegt ist). Um den Huffman-Baum zu speichern. reicht es, von jedem ASCII-Zeichen die Häufigkeit abzulegen. Auf diese Weise kann der Baum mittels der selben Funktion wie beim Komprimieren wieder aufgebaut werden. Negativ ist hierbei, daß die komprimierte Datei dadurch um exakt 1 Kilobyte länger wird. Beim Dekomprimieren von Huffman-gepackten Daten ist, neben dem Huffman-Baum, noch eine weitere Information wichtig, um die Daten wieder in den Originalzustand versetzen zu können: die Länge der Datei im unkomprimierten Zustand. Die Notwendigkeit, diese Information zu besitzen, rührt daher, daß wir beim Packen nicht Bytes, sondern Bits schreiben. So kann es häufig passieren, daß die gepackten Daten eigentlich nur 100,5 Byte lang sind, aber naturgemäß 101 Byte in die Datei geschrieben wurden. Die 4 überflüssigen Bits dürfen aber beim Dekomprimieren nicht beachtet werden, da sonst unter Umständen die dekomprimierte Datei um ein paar Zeichen länger ist - was, abhängig vom Dateityp, durchaus negative Folgen haben kann. Während wir beim Komprimieren eine Übersetzungstabelle erstellt haben, um nicht immer auf den Huffman-Baum zugreifen zu müssen, ist das beim Dekomprimieren nicht möglich, was aber auch nicht unbedingt ein Problem darstellt. Im Gegenteil, es ist vielmehr günstig, den Huffman-Baum direkt zu benutzen. Wir stellen uns zum Dekomprimieren einen imaginären Cursor vor, der auf die verschiedenen ,,Blätter'' des Huffman-Baums zeigen kann. Zu Beginn zeigt der Cursor auf den Kopf des Baumes. Nun wird das erste Bit gelesen (da es nicht möglich ist, bitweise aus einer Datei zu lesen, wird, wie gewohnt, byteweise gelesen und die diversen Bits aus dem gelesenen Byte extrahiert). Abhängig davon, ob das gelesene Bit gesetzt ist oder nicht, verzweigt der Cursor im Baum nach ,,links'' oder nach ,,rechts''. Diese Aktion wird mit den nächsten Bits wiederholt. Sollte der Cursor dabei irgendwann eines der untersten ,,Blätter'' erreichen, mithin eines, welches weder nach ,,links'' noch nach ,,rechts'' verzweigt (,,left'' und ,,right'' zeigen auf keine weitere HuffNode-Struktur), so wird das entsprechende Zeichen (,,key'') in die Ausgabedatei geschrieben und der Cursor wird wieder auf den Kopf des Baumes gesetzt. Die Dekomprimierung wird beendet, wenn die Zählvariable den Wert erreicht, der für die Größe der Datei angegeben wurde. Adaptive Huffman Beim adaptiven Huffman wird der Huffman-Baum auch erst während der Komprimierungsphase erstellt. Im Gegensatz zum dynamischen Huffman wird hier der Huffman-Baum aber laufend verändert. Auf diese Weise ist es möglich, sich unterschiedlichen Verteilungen der Zeichen in der zu packenden Datei anzupassen. zurück nach oben
Bei der LZW-Komprimierung, benannt nach ihren ,,Entdeckern'' Lempel, Ziv und Welch, wird ein Wörterbuch benutzt, um die Datei zu komprimieren. Beim Huffman-Algorithmus wurde stets nur die Häufigkeit der einzelnen Zeichen beachtet. Keinerlei Aufmerksamkeit wurde dabei der Tatsache geschenkt, daß im allgemeinen nach gewissen Zeichen gewisse andere Zeichen folgen. So ist zum Beispiel die Wahrscheinlichkeit, daß in einem deutschen Text nach dem Buchstaben 'q' der Buchstabe 'u' folgt, sehr groß. Auch wiederholen sich, insbesondere in Texten, gewisse Wörter immer wieder. Die Idee hinter dem LZW-Kompressionsalgorithmus besteht nun darin, sich wiederholende Textpassagen, oder mithin Bytefolgen, kürzer zu kodieren. Dazu wird das oben erwähnte Wörterbuch verwendet. Je nach dessen Größe können bessere oder schlechtere Kompressionsraten erzielt werden. Im allgemeinen wird ein Wörterbuch mit einer maximalen Zahl von 4096 Einträgen benutzt. Dadurch beschränkt sich die Zahl der Bits des Index, der benötigt wird, um alle Einträge abzudecken, auf 12. Im Grundstadium ist das Wörterbuch mit 256 Wörtern belegt, nämlich gerade den Zeichen aus dem ASCII-Codesatz. Die gepackte Datei besteht also nur aus 12-bittigen Werten, die entweder ein bestimmtes ASCII-Zeichen bedeuten (0... 255) oder eine bestimmte Zeichenkettenfolge. Komprimierung Wie bereits erwähnt, ist das Wörterbuch auf den Plätzen 0 bis 255 mit den entsprechenden ASCII-Codes bereits vorbelegt. Nun wird begonnen, die zu komprimierende Datei Byte für Byte einzulesen. Wir benötigen zwei zusätzliche Variablen, die Zeichenkette ,,text'' und die Integer-Variable ,,last'', welche beide am Anfang leer, bzw. mit 0 belegt, sind.
Um diesen Ablauf etwas verständlicher zu machen, soll er an einem Beispiel noch einmal dargelegt werden. Wir nehmen an, daß wir eine Textdatei mit folgendem Inhalt komprimieren wollen: TestTestTestAm Anfang sieht unser Wörterbuch folgendermaßen aus,
Der nächste freie Eintrag befindet sich bei Index 256. ,,text'' ist leer und ,,last'' ist 0. Wir lesen jetzt das erste Zeichen, das ,,T'', und hängen es an die Zeichenkette ,,text'', wodurch diese jetzt den Buchstaben ,,T'' enthält. Anschließend überprüfen wir, ob ein Wörterbucheintrag existiert, der identisch mit ,,text'' ist. Wir finden einen solchen Eintrag an Position 84, und setzen demzufolge ,,last'' auf 84. Nun lesen wir das nächste Byte, das ,,e''. Wieder hängen wir das gelesene Zeichen an ,,text'', wodurch dieses jetzt ,''Te'' beinhaltet. Diesmal finden wir aber keinen Eintrag im bisher vorhandenen Wörterbuch, welcher mit ,,text'' identisch ist. Aus diesem Grund schreiben wir ,,last'' (also 84) als 12-bit Wert in die Ausgabedatei. Wir legen desweiteren einen neuen Eintrag an. Der nächste freie Eintrag befindet sich bei 256 und wird jetzt zu
Anschließend setzen wir ,,text'' auf das zuletzt gelesene Zeichen, also ,,text'' = ,,e''. Daraus folgt, daß ,,last'' = 101. Nun wiederholen wir dieselbe Prozedur mit dem nächsten Zeichen, dem ,,s''. Die nächsten Schritte sollen nur grob dargestellt werden:
In der Datei stehen letztlich die folgenden Werte: 84, 101, 115,116, 256, 258, 260, 116. Wir haben also nichts gewonnen (8 mal 12 bits sind gerade 12 Bytes). Aber dies ist ja auch nur ein kleines Beispiel. Wäre der Text länger, so hätte sich sogar eine bessere Komprimierungsrate als bei Huffman gezeigt. Aber worum es bei LZW geht, sieht man auch hier bereits. Schritt 1 bis 3 sind noch nichts ,,Besonderes'', da wir hier das Wörterbuch erst mit geeigneten Werten füllen. Aber bei Schritt 4 und 5 sehen wir bereits das erste Mal, daß diesmal nicht nur ein Zeichen in 12 Bit gepackt wird, sondern zwei, da diese Zeichenkette bereits einmal vorkam. Mit der Zeit füllt sich das Wörterbuch, und die gespeicherten Zeichenketten werden länger. Damit läßt sich dann auch eine bessere Kompressionsrate erreichen. Sollte das Wörterbuch irgendwann einmal voll sein, so wird der Rest der Datei mit den bereits vorliegenden Einträgen komprimiert. Optimierungsmöglichkeit Der Nachteil bei dem eben erwähnten Verfahren ist, daß offensichtlich sehr viele Zeichenketten im Speicher gehalten werden müssen. Diese können, wie bereits erwähnt, mitunter recht lang werden. Aus diesem Grund ist es auch nötig, vorher großzügig Speicher zu reservieren. Desweiteren ist die andauernde Handhabung von langen Zeichenketten und die Unmengen von Vergleichen ebendieser Zeichenketten ziemlich zeitaufwendig. Aus diesem Grund wird der oben beschriebene Ablauf in der Praxis in dieser Hinsicht optimiert. Wie vielleicht bereits ersichtlich, haben alle neu ins Wörterbuch aufgenommenen Zeichenketten ein gemeinsames Merkmal: Es existiert bereits ein Eintrag, der identisch ist mit der Zeichenkette, wenn deren letztes Zeichen entfernt würde. Das heißt, wenn die Zeichenkette ,,abcdef'' im Wörterbuch vorkommt, dann kommen unter Garantie auch die Zeichenketten ,,ab'', ,,abc'', ,,abcd'' und ,,abcde'' vor, da dieser Algorithmus gerade auf diese Art und Weise funktioniert. Es liegt also nahe, neue Zeichenketten nicht komplett abzuspeichern, sondern bloß deren letzten Buchstaben und einen Zeiger auf den Eintrag im Wörterbuch, wo die anderen Buchstaben bereits vorkommen. Damit benötigt man pro Eintrag nur noch 3 Byte: 1 Byte für das ASCII-Zelchen und 2 Bytes für den 12-bit langen Index des Zeichenkettenanfanges. Unser Beispiel sähe also dann folgendermaßen aus:
Der Wert ,,-1'' beim Vorgänger bedeutet, daß es keinen Vorgänger gibt, es handelt sich hier also um den Anfangsbuchstaben. Wir sehen also, daß bei der neuen Methode der Eintrag 262 nicht mehr ,,Test'' enthält, sondern nur noch den Endbuchstaben ,,t'' und einen Zeiger auf die ersten Buchstaben. nämlich 260. 260 wiederum enthält nur das ,,s'' und einen Zeiger auf ,,Te'', usw., bis irgendwann einmal ein Zeichen ohne Vorgänger erreicht wird. Wenn ein neues Zeichen gelesen wird, wird es nicht mehr an ,,text'' angehangen. In Wirklichkeit existiert die Variable ,,text'' gar nicht mehr, da wir nur noch eine Variable brauchen, die dieses gelesene Zeichen enthält. Wollen wir nun überprüfen, ob ein gelesener String bereits im Wörterbuch vorhanden ist, so wird überprüft, ob ein Eintrag mit demselben ASCII-Zeichen existiert, dessen Vorgänger identisch mit dem in ,,last'' gespeicherten Wert ist. Optimierungsmöglichkeit Mit der oben beschriebenen Optimierungsmöglichkeit haben wir den Speicherbedarf des LZW-Algorithmus bereits drastisch eingeschränkt. Auch die Suche nach passenden Wörterbucheinträgen ist dadurch schneller geworden - allerdings noch nicht schnell genug. Noch immer werden Unmengen von Einträgen miteinander verglichen und das Komprimieren großer Datenmengen dauert immer noch relativ lange. Die zweite Optimierungsmöglichkeit versucht, die Anzahl der nötigen Vergleiche zu reduzieren, indem ein Hashing-Algorithmus benutzt wird, um neue Einträge abzulegen oder zu suchen. Sollte ein gesuchter Eintrag existieren, so wird er mit Hashing wesentlich schneller gefunden als ohne. Ein Hashing-Algorithmus macht nichts weiter, als neue Einträge abhängig von ihrem InhaIt an bestimmte Stellen des Wörterbuches zu setzen (z.B. ist der Index identisch mit einer berechneten Prüfsumme). Sollte die Stelle bereits besetzt sein, so wird der berechnete Index auf eine bestimmte Art und Weise (z.B. Addition) verändert. Dies wird solange wiederholt, bis eine freie Stelle gefunden wird. Der Vorteil ist, daß beim Suchen eines Eintrages ebenfalls diese Prüfsumme berechnet wird und die Plätze, wo sich der Eintrag höchstwahrscheinlich befindet, eher durchsucht werden als die anderen Plätze. Dies führt im Falle des Vorhandenseins des Eintrages zu einer stark reduzierten Anzahl von Vergleichen von Einträgen und demzufolge zu einem drastischen Geschwindigkeitsgewinn. Optimierungsmöglichkeit Bei großen Dateien passiert es schnell, daß sich das Wörterbuch rasch füllt. Dadurch ist nicht gewährleistet daß das Ende der Datei optimal komprimiert wird, da die Wörterbucheinträge aus dem Anfang der Datei zusammengestellt wurden. Es wäre in diesem Fall also günstiger, mehr Wörterbucheinträge zur Verfügung zu haben. Hier gibt es mehrere Möglichkeiten:
Dekomprimierung Ein großer Vorteil von LZW gegenüber Huffman ist die Tatsache, daß LZW das Wörterbuch nicht abspeichern muß. Dies würde aufgrund der Größe (4096 mal 3 Bytes = 12 Kilobyte) auch unzumutbar sein. Beim Dekomprimieren ist LZW in der Lage, daß Wörterbuch eigenständig wieder aufzubauen. Zu Beginn reicht es, daß Wörterbuch mit den Anfangswerten (die 256 ASCII-Zeichen auf den Einträgen 0 bis 255) zu füllen. Nun wird ein Index aus der komprimierten Datei gelesen und die Zeichenkette, die an der entsprechenden Stelle des Wörterbuches steht, wird in die Ausgabedatei geschrieben. Anschließend wird ein neuer Eintrag angelegt, und zwar besteht dieser aus der Zeichenkette, die sich aus der vorletzten geschriebenen Zeichenkette und dem Anfangsbuchstaben der eben geschriebenen Zeichenkette zusammensetzt. Als Beispiel soll unser oben komprimiertes Beispiel wieder dekomprimiert werden:
Wie leicht zu sehen ist, wird auf diese Art und Weise das Wörterbuch auf exakt die gleiche Art und Weise wie bei der Komprimierung gefüllt. Ausnahmefehler bei der Dekomprimierung: Unter ganz bestimmten Bedingungen kann es passieren daß beim Komprimieren ein Indexwert in die Ausgabedatei geschrieben wird, welcher beim Dekomprimieren noch gar nicht belegt ist. Würde keine Vorsorge gegen diesen Ausnahmefall getroffen werden, würde es nicht mehr möglich sein, die Daten in ihren Originalzustand zurückzuführen. Glücklicherweise gibt es jedoch nur einen solchen Ausnahmefehler und deshalb kann er sehr leicht abgefangen werden. Auftreten tut dieser Fehler zum Beispiel bei der Datei, die den Text ,,exexaexaexaex'' enthält. Nehmen wir an, daß vorbelegte Wörterbuch sieht diesmal folgendermaßen aus: 1 = ,,e'', 2 = ,,x'' und 3 = ,,a''. Der nächste freie Index wäre also 4.
Das Entpacken würde jetzt folgendermaßen ablaufen:
Nun ist guter Rat teuer. Der 8. Eintrag ist nämlich noch leer ... Auftreten tut dieser Fehler immer in Situationen, wo ein Text in der Form <xyz> <a> <xyz> <a> <xyz> ... steht, wobei <xyz> eine beliebige Zeichenkette, die bereits im Wörterbuch steht, und <a> ein beliebiges Zeichen ist. Sollte dem Dekomprimierungsalgorithmus ein Fall unterkommen, wo auf einen nicht existierenden Eintrag verwiesen wird, so legt er einen neuen Eintrag an (den mit dem gelesenen Index). Dieser ist identisch mit dem Eintrag, der zuletzt in die Datei geschrieben wurde. Zusätzlich wird das erste Zeichen dieses Eintrages noch hintenan gehangen. Anschließend wird der neue Eintrag in die Datei geschrieben. Im vorliegenden Fall wäre Eintrag 8 also Eintrag 6 plus das erste Zeichen von Eintrag 6, also gerade ,,exae''. zurück nach oben |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||