DE60107964T2

DE60107964T2 - Vorrichtung zur kodierung und dekodierung von strukturierten dokumenten

Info

Publication number: DE60107964T2
Application number: DE60107964T
Authority: DE
Inventors: Cedric Thienot; Claude Seyrat
Original assignee: Expway SA
Current assignee: Expway SA
Priority date: 2000-09-06
Filing date: 2001-08-31
Publication date: 2005-05-25
Anticipated expiration: 2021-09-01
Also published as: PT1316220E; DK1316220T3; US8015218B2; EP1316220B1; US20040013307A1; US20110283183A1; ES2234878T3; JP4653381B2; FR2813743B1; WO2002021848A1; FR2813743A1; ATE285656T1; AU2001287796A1; EP1316220A1; DE60107964D1; JP2004508647A

Description

Die vorliegende Erfindung betrifft ein Verfahren zur Komprimierung/Dekomprimierung von strukturierten Dokumenten.
Sie beschäftigt sich insbesondere, aber nicht ausschließlich, mit der Übertragung von Dokumenten, wie Bildern oder Sequenzen von Bildern, von Bild- oder Tondaten, durch digitale Datenübertragungsnetze sowie mit der Speicherung solcher Dokumente.
Gegenwärtig gibt es mehrere Algorithmen zur Komprimierung eines digitalen Dokuments. Es sind bestimmte Komprimierungsalgorithmen bekannt, um die binären Daten des Dokuments direkt zu behandeln, ohne den Typus dieser Daten zu berücksichtigen. Diese Algorithmen haben den Vorteil, jedes Dokument behandeln zu können, sind aber wenig leistungsfähig (wenig erhöhtes Komprimierungsverhältnis), um voluminöse Dokumente zu behandeln, die im Allgemeinen dem Ton- oder Bildtypus entsprechen.
Darüber hinaus sind Komprimierungsalgorithmen bekannt, die wirksamer sind, aber speziell an einem Datentyp angepasst sind, zum Beispiel, dem Bild- oder Tontypus, derart, dass sie nicht verwendbar oder leistungsfähig sind, wenn sie an Dokumenten angewendet werden, die nicht ausschließlich Daten enthalten, für welche sie bekannt sind.
Nun enthalten die im Datennetz verwendeten und zirkulierenden Dokumente zunehmend mehrere in einer Struktur integrierte Informationstypen.
Ein strukturiertes Dokument ist eine Sammlung von Informationseinheiten, die jeweils einem Typ zugeordnet sind und untereinander in prinzipiell hierarchischen Beziehungen zusammengesetzt sind. Diese Dokumente verwenden eine Strukturierungssprache, wie SGML, HTML, XML, die insbesondere erlaubt, die das Dokument bildenden unterschiedlichen Informationseinheiten zu unterscheiden. Im Ge gensatz dazu werden in einem sogenannten linearen Dokument die Informationen zum Inhalt des Dokuments mit Informationen zur Präsentation oder zur Typisierung vermengt.
So enthält ein strukturiertes Dokument Zeichen zur Trennung der unterschiedlichen Informationseinheiten des Dokuments. Im Falle der Formate SGML, XML oder HTML haben diese "Baken" genannten Zeichen die Form "<XXXX>" und "</XXXX>", wobei das erste Zeichen den Anfang der Informationseinheit "XXXX" angibt und das zweite das Ende dieser Einheit. Eine Informationseinheit kann aus mehreren Informationseinheiten von niedrigerem Niveau zusammengesetzt sein. So weist ein strukturiertes Dokument ein hierarchisches oder baumartiges Strukturschema auf, wobei jeder Knoten eine Informationseinheit darstellt und mit einem Knoten auf einem höheren hierarchischen Niveau verbunden ist, der eine Informationseinheit darstellt, welche die Informationseinheiten von niedrigerem Niveau enthält. Die am Zweigende dieser Baumstruktur liegenden Knoten stellen Informationseinheiten dar, welche Daten eines vordefinierten Typs enthalten, die nicht in Informations-Untereinheiten zerlegt werden können.
Eine strukturiertes Dokument ist im Allgemeinen einem sogenannten Strukturschema zugeordnet, welches in Form von Regeln die Struktur und den Informationstyp jeder Informationseinheit des Dokuments definiert. Ein Schema wird aus verschachtelten Gruppen von Strukturen von Informationseinheiten gebildet, wobei diese Gruppen geordnete Sequenzen, geordnete oder nicht geordnete Gruppen von alternativen Elementen oder Gruppen von notwendigen Elementen sein können.
So ist ein strukturiertes Dokument einem Strukturschema zugeordnet und enthält Trennungszeichen, die in Form von Text- oder Binär-Daten dargestellt sind, wobei diese die Informationseinheiten begrenzenden Zeichen selbst weitere Informationseinheiten enthalten können, die durch die Zeichen begrenzt werden. Daraus ergibt sich, dass ein auf diese Weise strukturiertes Dokument nicht nur Textdaten, sondern ebenso auch jedem anderen Typ von Information umfassen kann (zum Beispiel Tondaten, Bilddaten, etc.). Folglich sind die für einen Datentyp spezifischen Komprimierungsalgorithmen wenig wirksam und schlecht angepasst, um diesen Dokumenttyp zu behandeln.
Die vorliegende Erfindung hat zum Ziel, diese Nachteile zu vermindern. Zu diesem Zweck schlägt sie ein Verfahren zur Komprimierung und Dekomprimierung eines strukturierten Dokuments vor, das wenigstens einem baumartig verzweigten Strukturschema zugeordnet ist und verschachtelte Strukturelemente aufweist, welche Informationseinheiten darstellen, wobei die Strukturelemente in drei Kategorien unterteilt sind, nämlich strukturierte Stammelemente, die in Elementgruppen und in strukturierte oder nicht strukturierte Basiselemente, die den Elementen auf dem untersten Niveau in der Struktur entsprechen, zerlegt sind, wobei jedes Basiselement und Stammelelement einem Informationstyp zugeordnet ist.
Gemäß der Erfindung ist dieses Verfahren dadurch gekennzeichnet, dass wenigstens ein Informationstyp der Basiselemente zuvor einem angepassten Komprimierungsalgorithmus zugeordnet wird, wobei das Verfahren die folgenden Schritte aufweist:

– syntaktische Analyse des Strukturschemas des Dokuments,
– die Kompilierung des Strukturschemas im Hinblick darauf, einen Automaten mit endlicher Anzahl von Zuständen pro Stammelement zu erhalten, wobei jeder Automat die Zustände aufweist, die untereinander durch Übergänge verbunden sind und jeweils die Elemente der Struktur darstellen, und
– die Komprimierung des zu komprimierenden strukturierten Dokuments, welche die Ausführung der Automaten mit endlicher Anzahl von Zuständen an dem Dokument und die Ausführung des Komprimierungsalgorithmus umfasst, wenn die Informationseinheit mit einem dem Algorithmus zugeordneten Informationstyp in dem zu komprimierenden Dokument aufgefunden wird.

Aufgrund der Kompilierung des Strukturschemas wird die Struktur des Dokuments in einer sehr kompakten Weise dargestellt und infolgedessen ist jede Informationseinheit, die einem Basiselement der Struktur entspricht, einem Informationstyp zugeordnet, und sie kann durch den besser an ihren Typ angepassten Komprimierungsalgorithmus behandelt werden. Auf diese Weise werden diese Daten, wenn das Dokument zum Beispiel Text-, Bilddaten und Tondaten enthält, diese Daten in dem strukturierten Dokument perfekt markiert und einem Strukturelement auf niedrigem Niveau und einem Typus zugeordnet. Im Verlauf der Ausführung der Automaten werden diese das Vorhandensein von Informationseinheiten mit einem Basistyp, der einem Komprimierungsalgorithmus zugeordnet ist, erfassen und nacheinander die korrespondierenden Algorithmen auf diese Daten anwenden, um korrespondierende binäre Informationssequenzen zu erhalten, die eine nach der anderen in das sich aus der Komprimierung ergebende Dokument eingefügt werden.
Ferner ist es im Falle einer Datenübertragung nicht notwendig, wenn die übertragenen Dokumente immer das gleiche Strukturschema aufweisen, dieses bei jeder Übertragung des Dokuments zu übertragen, wodurch mit Hilfe des Verfahrens gemäß der Erfindung ein zusätzlicher Gewinn hinsichtlich des Komprimierungsgrades erhalten wird. Diese Übertragung ist auch überflüssig, wenn das Schema vom Empfänger des Dokuments vorher gekannt wird. Wenn es sich zum Beispiel um ein Dokument in HTML handelt, ist es niemals nötig, selbst beim ersten Mal, das Schema des Dokuments zu kodieren.
Jeder Automat mit endlichen Zuständen muss eine Zustandsmenge umfassen, wobei jeder Zustand einer Gruppe von Eintrittsereignissen und einer Übergangsfunktion, die für jedes Eintrittsereignis die Menge von aktiven Zuständen des Automaten bestimmt, zugeordnet ist. In Anbetracht dieser Definition kann man sich zahlreiche Darstellungen, zum Beispiel unter Berücksichtigung von Umwandlungstabellen, und zwar einer jedes Eintrittsereignis angebenden Tabelle pro Zustand, der mit einem folgenden Zustand korrespondierenden Tabelle oder auch von Korrespondenztabellen, und zwar einer Tabelle pro Automat, die ebenso viele Zeilen und Spalten aufweist, wie Zustände im Automat vorhanden sind, wobei jede Zelle der Tabelle die Beschreibung des Übergangs zwischen den zwei korrespondierenden Zuständen enthält.
Bei der Dekomprimierung wird das Strukturschema in der gleichen Weise behandelt, um die Automaten zu bestimmen, die zur Komprimierung beigetragen haben, und den Inhalt des komprimierten Dokuments zu analysieren, und zwar im Hinblick darauf, ein Dokument im Ursprungsformat herzustellen, das eine wenigstens äquivalente, wenn nicht identische, Struktur aufweist, wobei die Dekomprimierungsalgorithmen, die den bei der Komprimierung verwendeten Komprimierungsalgorithmen entsprechen, ausgeführt werden, um die Ursprungs-Informationseinheiten ausgehend von binären Informationssequenzen, wieder herzustellen, die in dem komprimierten Dokument markiert sind.
In dem Falle, in welchem das Strukturschema mit dem Dokument übertragen werden muss, umfasst das Verfahren gemäß der Erfindung in vorteilhafter Weise einen Übertragungsschritt für das Strukturschema, welches das ursprüngliche, das nach der Transformation und Normierung erhaltene oder auch das nach der Kompilierung erhaltene sein kann.
Gemäß einer Besonderheit der Erfindung wird jede Informationseinheit in dem komprimierten Dokument in der Weise aufgefunden, dass ein direkter Zugriff auf eine spezielle Informationseinheit erlaubt ist, ohne dass es notwendig wird, die der zu dekomprimierenden Einheit voraus gehenden Informationseinheiten zu dekomprimieren.
Gemäß einer weiteren Besonderheit der Erfindung ist jedes Element des Strukturschemas ferner einer Zahlengruppe möglicher Erscheinungshäufigkeiten zugeordnet, welche die Häufigkeitszahl angibt, mit der eine Informationseinheit mit diesem Strukturelement in der Informationseinheit an einer Stelle unmittelbar über derjenigen, zu der sie gehört, auftauchen kann.
Das Verfahren gemäß der Erfindung kann einen Schritt zur Optimierung des Strukturschemas des Dokuments umfassen, der darin besteht, die Zahl der hierarchischen Niveaus der Strukturelementgruppen zu reduzieren. Diese Optimierung erlaubt es, das Strukturschema zu vereinfachen, vermindert aber die Wirkung der Komprimierungsbehandlung.
Eine Ausführungsform des Verfahrens gemäß der Erfindung wird nachfolgend beschrieben, rein beschreibend und nicht beschränkend, in Bezug auf angehängte Zeichnungen, in welchen:
1 den Ablauf der verschiedenen Verfahrensschritte gemäß der Erfindung in Form eines Blockdiagramms darstellt;
2a, 2b und 2c ein Strukturschema in Form eines Baumes graphisch darstellen;
3 ein Strukturschema zeigt, das unter Anwendung eines Reduktionsverfahrens gemäß der Erfindung am in 2 dargestellten Strukturschema erhalten wird;
4a, 4b und 4c ein Strukturschema zeigen, das unter Anwendung eines weiteren Reduktionsverfahrens gemäß der Erfindung am in 2 dargestellten Strukturschema erhalten wird;
5a bis 5c jeweils drei Automaten mit endlichen Zuständen darstellen, die durch das Verfahren gemäß der Erfindung erhalten und genutzt werden;
6 einen weiteren Automaten darstellt, der ein Verfahren zum Optimieren darstellt, das durch das Verfahren gemäß der Erfindung genutzt wird;
7a und 7b zwei Automaten darstellen, die mit Hilfe des Verfahrens gemäß der Erfindung ausgehend von einem speziellen Strukturschema erhalten werden; und
8 eine Anwendung eines Reduktionsverfahrens an in den 7a und 7b darstellten Automaten darstellt.
Die 1 stellt einen Ablauf unterschiedlicher Schritte des Verfahrens gemäß der Erfindung dar.
Dieses Verfahren ist dafür bekannt, ein strukturiertes Dokument zu behandeln, das aus einem Strukturschema 1 gebildet wird, welches die Struktur des Dokuments und der strukturierten Informationen 2 des Dokuments definiert.
In der Sprache XML Schema präsentiert ein Strukturschema zum Beispiel die folgende Form:
Dieses Schema gibt an, dass das mit "C" bezeichnete Element eine komplexe Struktur präsentiert, die gebildet wird durch ein mit "a2" bezeichnetes erstes Element vom Booleschen Zahlentyp, das optional ist, ein mit "a1" bezeichnetes zweites Element vom natürlichen Zahlentyp, das immer in der Struktur vorhanden ist, und eine mit "A" und "B" bezeichnete alternative Elementegruppe der jeweiligen Typen "TA" und "TB", wobei eines dieser beiden Elemente nur ein einziges Mal in der Struktur vorhanden ist.
Die Typen "TA" und "TB" sind in dem Strukturschema des Dokuments durch eine analoge Formulierung definiert.
In einer allgemeinen Weise verwendet man die folgenden Elementegruppen, um eine Struktur des Dokuments zu definieren:

– SEQ: Diese definiert eine Liste geordneter Elemente, die alle in dem Dokument und in der angegebenen Reihenfolge erscheinen müssen,
– CHO: Diese definiert eine alternative Elementegruppe, wobei ein einzelnes Element der Gruppe erscheinen muss,
– ET: Diese definiert eine Elementegruppe, die immer in dem Dokument und in irgendeiner Reihenfolge, die nicht modifiziert werden muss, erscheinen muss,
– ET_NO: Diese definiert eine Elementegruppe, die immer in dem Dokument in irgendeiner Reihenfolge, die nicht wichtig ist, vorhanden sein muss, und
– ANY: Diese umfasst irgendein Element aus all den möglichen Elementen, die in dem Dokument gefunden werden können.

Gemäß der Erfindung wird am Schritt 11 des Verfahrens analysiert und transformiert, um syntaktische Bäume 4 zu erhalten, und zwar ein Baum pro Strukturelement. Der einem Strukturelement TC entsprechende syntaktische Baum wird durch die folgende Formel symbolisiert: TC → ((a11..1{int} &no a20..1{bool} )1..1, (A1..1{TA} | B1..1{TB} )1..1)1..1 (1)in welcher:
"→" angibt, dass TC der Name ist, der der nach diesem Symbol definierten Struktur gegeben wird,
"()" die Prioritäten angibt, mit welchen die Elementegruppen gelesen werden müssen,
"," einer Elementegruppe vom Sequenz-Typ (SEQ entspricht,
"|" eine alternative Elementegruppe (DHO) darstellt
"&" eine Elementegruppe des Typs ET darstellt,
"&_no" eine nicht geordnete Elementegruppe des Typs ET darstellt,
"{}" einem Element ein Namen eines Strukturelements oder ein Basistyps (zum Beispiel ganzzahlig oder boolesch) zuordnet, und
"A^x..y" angibt, dass das Element A in dem Dokument x- bis y-mal wiederholt wird, wobei y gleich "*" sein kann, was einen unbestimmten Wert darstellt.
Diese Formulierung verwendet auch das Symbol $", welches irgendein Element (ANY) darstellt.
Die Formel (1) kann durch den in 2c dargestellten Baum dargestellt werden, wobei dieser Baum ein Stammelement "TC" 43 umfasst, das ein einzelnes Erscheinen einer Sequenz-Gruppe 44 bildet. Diese Gruppe umfasst ein einzelnes Erscheinen einer nicht geordneten "ET"-Gruppe 45 und ein einzelnes Erscheinen einer alternativen Gruppe 46.
Die Gruppe 45 wird von einem einzelnen Erscheinen einer mit "a1" bezeichneten ganzen Zahl und einer mit "a2" bezeichneten booleschen Zahl gebildet, und die
Gruppe 46 umfasst ein einzelnes Erscheinen eines mit "A" bezeichneten Elements des Typs "TA" und eines Elements "B" des Typs "TB".
Die im Schritt 11 erhaltenen Typen "TA" und "TB" sind zum Beispiel durch die folgenden Formeln gegeben: TA → ((a31..1{int} & a40..1{int} )1..1, (X1..1{TC} , Y1..1{TC} )1..1)1..1 (2) TB → (a11..1{bool} ), a50..1{bool} )1..1 (3)und durch die jeweils in den 2a und 2b gezeigten Bäume wiedergegeben.
Der Typ "TA" 31 umfasst eine einzelne Gruppe 32 des Sequenz-Typs, die aus zwei einzelnen Gruppen 33, 34 jeweils des Typs ET bzw. SEQ gebildet ist. Die Gruppe 33 umfasst zwei einzelne Erscheinungen des ganzzahligen Typs, die jeweils mit "a3" und "a4" bezeichnet sind. Die Gruppe 34 umfasst zwei einzelne Erscheinungen des Typs "TC", die jeweils mit "X" und "Y" bezeichnet sind.
Der Typ "TB" 39 wird aus einer einzelnen Gruppe 40 des Sequenz-Typs gebildet, die zwei boolesche Zahlen umfasst, die jeweils mit "a1" und "a5" bezeichnet sind.
Obwohl in der vorstehenden Beschreibung der Name jedes Elements und seines Typs unterschieden worden sind, wendet sich das Verfahren gemäß der Erfindung ebenso an Strukturierungssprachen, die nicht diese Unterscheidung aufweisen.
Im Übrigen müssen die Strukturelemente deterministisch sein, das heißt, ein Element soll nicht in mehreren unterschiedlichen Weisen interpretiert werden können. Zum Beispiel weiß man in dem Schema "(a | (a, b))", in dem Fall, in welchem "a" erscheint, nicht, ob "b" danach erscheinen soll. Es gibt deshalb Algorithmen, die durch das Verfahren gemäß der Erfindung angewendet werden können, um ein nicht deterministisches Schema in ein deterministisches Schema umzuwandeln. Es kann zum Beispiel Bezug genommen werden auf die Druckschriften ["Regular expressions into finite automata" Brüggemann-Klein, Anne, Extended Abstract in I. Simon, Hrsg., LATIN 1992, S. 97–98. Springer-Verlag, Berlin 1992. Full Versions in Theoretical Computer Science 120: 197–213, 1993]. So kann das vorstehende Schema zum Beispiel ersetzt werden durch "(a, b^0..1)".
Am folgenden Schritt 12 des Verfahrens gemäß der Erfindung können die Elemente des in syntaktische Bäume transformierten Strukturschemas zunächst einer Behandlung zur Reduktion oder Vereinfachung unterzogen werden.
Diese Reduktionsbehandlung besteht darin, eine globale Abflachung zu bewirken, indem ein einzelner syntaktischer Baum 51 aus allen Bäumen 31, 39 und 43 erzeugt wird, wie dies in 3 dargestellt ist.
Dieser Baum repräsentiert im Grunde ein Verzeichnis aller Elementtypen, die in dem Dokument zusammentreffen können, wobei diese Elemente in einer Gruppe 52 des alternativen Typs zusammengefasst sind, die wenigstens einmal (1..*) in dem Dokument erscheint. In diesem Baum sind die Elemente des komplexen Typs "A", "B", "X" und "Y" einem Typ "ANY" zugeordnet, und das Element "a1 ", das zweimal (in den Elementen "TB" und "TC") mit unterschiedlichen Typen erscheint, ist einem gemäß der Sprache YML als "pcdata" abgekürzten Typ oder dem Element-Typ in dem Ausgangsdokument, zum Beispiel einem Text, zugeordnet. Eine gleiche Informationseinheit kann somit auf unterschiedliche Weise dargestellt werden: Zum Beispiel kann eine binäre Sequenz auch als eine Zeichenkette oder eine ganze Zahl angesehen werden.
Alternativ besteht diese Reduktionsbehandlung darin, die syntaktischen Bäume örtlich abzuflachen, um Bäume zu erhalten, die in den 4a bis 4c mit 31', 39' und 53' dargestellt sind.
In jeder dieser Figuren wurden die Gruppen 32 bis 34 (2a), 40 (2b) und 44 bis 46 (2c) jeweils durch eine Gruppe 53, 55, 54 des alternativen Typs ersetzt, die wenigstens einmal (1..*) auftritt.
Die Bäume "TA", "TB" und "TC" können ferner einer zusätzlichen Behandlung unterzogen werden, um die Mehrdeutigkeiten zu unterdrücken, die in dem Strukturschema auftreten.
Am Schritt 12 unterziehen sich die Bäume "TA"; "TB" und "TC" gleichermaßen einer Normierungs-Behandlung, die darin besteht, das Schema so neu zu ordnen, dass eine einheitliche Reihenfolge der Elemente des Schemas erhalten wird. Diese Behandlung beeinflusst eine binäre Zahl an den verschiedenen Knoten der infolge der voraus gegangenen Behandlungen erhaltenen syntaktischen Bäume. Diese Zahl wird bei der Komprimierung des korrespondierenden Elements verwendet.
Diese Normierungs-Behandlung besteht darin, jeder Gruppe eine Signatur zuzuweisen, die aus der Verkettung des Namens der Gruppe mit der Signatur aller vorher geordneten Elemente und Untergruppen der Gruppe gebildet wird. Auf diese Weise wird der Gruppe 53 in 4 die Signatur "CHO.a3.a4.X.Y" (oder"|a3.a4.X.Y") zugeordnet.
Für diese Normierungs-Behandlung wird berücksichtigt, dass die geordneten Gruppen (SEQ bereits normiert sind. Die zu normierenden Gruppen sind daher die Gruppen des alternativen Typs ("CHO") und die Gruppen "ET" und "ET_NO". Diese Behandlung umfasst die folgenden Schritt für jede Gruppe G, die aus Untergruppen g_i und den Elementen e_i zusammengesetzt ist:

– die Normierung der möglichen Untergruppen g_i der Gruppe G, vor dem Normieren der Gruppe G, wobei der Normierungs-Algorithmus rekursiv ist,
– die Zuweisung von möglichen Elementen e_i der Gruppe G vor den Untergruppen g_i,
– die Zuweisung von Elementen e_i in einer vordefinierten Ordnung,
– die Zuweisung der Untergruppen g_i in der vordefinierten Ordnung, und
– die Bestimmung der Signatur der Gruppe G, die durch die Verkettung aller Signaturen dieser Komponenten (Elemente und Untergruppen) gemäß der infolge der voraus gegangenen Schritte etablierten Ordnung gegeben wird.

Die vordefinierte Ordnung der Zuweisung von Komponenten der Gruppe kann eine alphanumerische Ordnung ihrer jeweiligen Signaturen sein oder eine Ordnung, die von ihrer minimalen Erscheinungszahl aus abfällt, wobei die Komponenten mit der gleichen minimalen Erscheinungszahl dann durch eine alphanumerische Ordnung eingeordnet werden.
Es wird angemerkt, dass diese Normierungs-Behandlung in dem Verfahren gemäß der Erfindung nicht notwendig ist. Die Ordnung der Erscheinung der Komponenten in dem Schema kann im Übrigen konserviert werden.
Der folgende Schritt 13 des Verfahrens besteht darin, Automaten mit endlichen Zuständen 5 zu erzeugen. Diese Behandlung besteht darin, für jeden syntaktischen Baum eine Basisgruppe von Automaten zu erzeugen, und zwar ein Automat pro Gruppe eines syntaktischen Baumes, um dann diese Basisautomaten zu kombinieren.
In 5a umfasst der Automat einer sequentiellen Gruppe (SEQ von n Elementen mit den Signaturen m1, m2,..., mn auf dem unmittelbar unteren hierarchischen Niveau n+2 Zustände, die mit 0 bis n+1 bezeichnet sind und in der Figur durch die Kreise symbolisiert sind, wobei jeder Knoten mit seinem Nachfolger durch einen Übergang verbunden ist, der durch einen Bogen symbolisiert ist, der einem Element der Gruppe entspricht und durch die Signatur des Elements bezeichnet ist, wobei der letzte Übergang F (in Richtung des Zustands n+1) das Ende der Gruppe markiert.
In 5b umfasst der Automat eine Gruppe des alternativen Typs (CHO) der n Elementen von Signaturen m1, m2,..., mn, auf dem unmittelbar unteren hierarchischen Niveau einen Anfangszustand, der mit "0" bezeichnet ist, und n Endzustände, die mit 1 bis n bezeichnet sind, wobei der Zustand 0 mit den Endzuständen 1 an n bzw. durch n Übergänge entsprechend dem jeweiligen n-Elementen der Gruppe verbunden ist.
In 5c umfasst der Automat eine Gruppe ET aus n-Elementen von Signaturen m1, m2,..., mn am unmittelbar unteren hierarchischen Niveau 1+n+n*(n–1)+n*(n-1)*(n–2)+...+n! Zustände, die alle möglichen Kombinationen von n-Elementen repräsentieren.
Ein solcher Automat kann durch einen einfachen Algorithmus erzeugt werden, wie demjenigen, der folgt:
Der Automat einer Gruppe ET_NO aus n-Elementen mit den Signaturen m1, m2,..., mit auf dem unmittelbar unteren hierarchischen Niveau kann selbst eine SEQ sein, sobald man akzeptiert, Information betreffend der Ordnung für die Erscheinung von Elementen in der Gruppe betreffend zu verlieren oder dass diese fixiert ist.
Diese Automaten (im Falle der Gruppen des Typs CHO, ET und ET_NO) können unter Anwendung einer Behandlung zur Vermeidung von optionalen Elementen optimiert werden, das heißt, deren Gesamtheit möglicher Erscheinungen hat die Form (0..k). Diese Regel reflektiert die Tatsache, dass jedes Element, das einer Anzahl von Erscheinungen, mindestens Null, zugeordnet ist, nicht zwingend codiert wird. Wie in 6 dargestellt ist, besteht diese Behandlung darin, einen Übergang zwischen dem Zustand "1", der unmittelbar stromaufwärts eines optionalen Elements "2" liegt und den Zuständen "3", die unmittelbar stromabwärts dieses Elements liegen, hinzu zu fügen, wobei dieser neue Übergang der Signatur "m3" des Elements zugeordnet ist, das mit dem Zustand korrespondiert, an welchem dieses mündet. Wenn einer der unmittelbar stromabwärts liegenden Zustände auch einem optionalen Element zugeordnet ist, muss auch ein Übergang in Richtung aller Zustände vorgesehen werden, die unmittelbar stromabwärts dieses Zustands liegen.
Diese Behandlung kann durch den folgenden Algorithmus ausgeführt werden:
Es wird angemerkt, dass die auf diese Weise für ein Strukturschema erzeugten Automaten ineinander verschachtelt sind. Nämlich in den Automaten, die dem in 2 dargestellten Beispielschema entsprechen, wird, wenn der Typ TC (Elemente X und Y) in dem Automaten, der dem Typ TA31 entspricht, wieder getroffen wird, der Automat, der dem Typ TC43 43 entspricht, vollständig ausgeführt, bevor die Ausführung des dem Typ TA entsprechenden Automaten fortgesetzt wird.
Der folgende Schritt 14 des Verfahrens gemäß der Erfindung besteht darin, die vorher erhaltenen Automaten zu reduzieren und zu transformieren.
Man kann auf diese Weise Automaten eines gleichen syntaktischen Baumes (und nicht Automaten unterschiedlicher Bäume, wie es die einen oder anderen behaupten) in der Weise fusionieren, wie dies mit Bezug auf die 7a und 7b ausgedrückt wird.
Diese Figuren zeigen die Automaten, die in Übereinstimmung mit dem Verfahren gemäß der Erfindung aus dem Strukturelement (a₁ ^0..*,(b₁ | b₂)^0..**).erzeugt worden sind. Der erste Automat (7a) entspricht einer Gruppe SEQ (","), während der zweite Automat (7b) einer alternativen Gruppe (" ") entspricht.
Im Verlaufe der Ausführung dieser Automaten zieht das Erreichen des Zustands 2 im ersten Automaten die Ausführung des zweiten Automaten mit sich, und der Ankunft am Endzustand 1 oder 2 in dem zweiten Automaten folgt die Fortsetzung der Ausführung des ersten Automaten, das heißt, die Ausführung des Übergangs F zwischen dem Zustand 2 und dem Endzustand 3 des ersten Automaten.
Die Fusionsbehandlung der zwei Automaten erlaubt, den in 8 dargestellten Automaten zu erhalten, in welchem jede Alternative der Gruppe CHO durch einen Übergang dargestellt ist, der der Signatur "cho.b1.b2" der Gruppe zugeordnet ist, verkettet mit der Signatur "b1", "b2" des Elements der Gruppe, wie dies in alternativer Wahl dargestellt ist.
Im Verlauf dieses Schrittes 14 können die Automaten auch einer Behandlung zur Minimierung der Zahl der Zustände unterzogen werden, zum Beispiel unter Anwendung eines Hopcroft-Algorithmusses, dann einer Behandlung zur Normierung, um die normierten Automaten 6 zu erhalten.
Am Ausgang dieser Behandlung werden die Übergänge am Anfang jedes Knotens von 0 bis n nummeriert.
Der folgende Schritt 15 besteht darin, das Dokument 2 wieder einzulesen, um die Daten zu komprimieren, die es enthält, indem die Automaten die Struktur des Dokuments ausführen, und zwar im Hinblick darauf, eine Folge von binären Sequenzen zu erhalten, in welchem der komprimierte Wert jedes Elements oder Gesamtheit von Basisinformationen des Dokuments findet. Gemäß einem ersten Codierungstyp liegen die binären Sequenzen in der Form (K.N.V_1..V_N)_c vor, und zwar für jedes Element oder jede Elementegruppe e, wobei N die Zahl von Erscheinungen des Elements e oder die Zahl der aufeinander folgenden Informationseinheiten ist, die dem Element e entsprechen, K die Zahl des Übergangs ist, der es erlaubt hat, das Element e zu erhalten, und V_1..V_N die jeweiligen Werte sind, die möglicherweise aus N-Erscheinungen des Elements e komprimiert werden. Wenn e eine Elementegruppe ist, wird ihr Wert V in ebenso viele binäre Sequenzen (K.N.V) zerlegt, wie sie Elemente enthält. Jedoch kann in bestimmten Fällen N weg gelassen werden, insbesondere dann, wenn diese Zahl fix ist. Das gleiche gilt für K in dem Falle, in welche es nur einen einzigen Bogen aus Richtung eines Zustandes gibt, zum Beispiel in einer Gruppe des Sequenz-Typs.
Zuvor kann ein allgemeiner Kopf des komprimierten Dokuments realisiert werden, der mehrere kodierte Parameter umgruppiert, die bei der Beschreibung des Dokuments nützlich sind. So kann ein solcher Kopf eine Signatur des oder der Schemas/Schemen verwendeten Struktur/en und eine Gesamtheit von Parametern umfassen, welche die verwendete Codierung beschreiben, wie zum Beispiel:

– einen Parameter, der angibt, ob die Codierung der Länge jedes Elements in dem Dokument obligatorisch oder optional oder nicht vorhanden ist,
– einen Parameter, der angibt, ob die Elemente Untertypen sein können oder nicht, das heißt, einem präziseren Typ als dem Basistyp zugeordnet sind, und
– einen Parameter, der den Codierungstyp angibt, der für die Erscheinungszahl verwendet wird.

Jedes Informationselement des Dokuments kann auch einem Kopf zugeordnet sein, wobei sein Vorhandensein und seiner Natur in dem Kopf des Dokuments präzisiert ist.
Der Kopf eines Elements kann auch die kodierte Länge desselben umfassen, in der Weise, dass bei der Dekomprimierung des Dokuments ein Zugriff auf ein spezielles Element erlaubt wird, ohne alle voraus gehenden Dokumente in dem Dokument zu dekomprimieren. Die Elementenköpfe werden in das Dokument zum Beispiel genau vor der Codierung des Wertes der Elemente eingefügt.
In allgemeiner Weise besteht die Komprimierung des Dokuments darin, das Dokument sequentiell auszulesen, indem die Automaten des Schemas ausgeführt werden, was ferner erlaubt, zu verifizieren, dass die Struktur des Dokuments dem kompilierten Schema entspricht.
Im Verlauf dieser Behandlung erscheint ein Code der Erscheinungszahl jedes Elements in dem Dokument. Zu diesem Zweck wendet man die folgenden Regeln an.
In dem Falle, in welchem die Erscheinungszahl eines Elements e definiert wird durch (i..j) unterscheidet man die folgenden Fälle:
Wenn j unterschiedlich ist von "*" und i unterschiedlich ist von 0, wird die Codierung in zwei Teile zerlegt, nämlich (i..i) und (0..j-i), wobei der erste Teil nicht codiert wird, denn diese Formulierung spezifiziert, dass i Erscheinungen notwendig sind. Der zweite Teil wird in |log₂(j–i+1)| Bits codiert.
Wenn j unterschiedlich ist von "*" und i gleich 0 ist, wird die Codierung der Erscheinungszahl zwischen 1 und j ausgeführt, und zwar in |log₂(i)| Bits, denn wenn diese Codierung notwendig ist, bedeutet dies, dass es wenigstens ein Element e in dem Dokument gibt.
Wenn j gleich "*" ist, verwendet man eine Codierungstechnik wie ASNI, gemäß welcher das erste Oktett angibt, auf wie viele Oktetts die Codierung durchgeführt wird, und die folgenden Oktetts enthalten den Wert der Erscheinungszahl. Man kann auch das im Wert hohe Bit jedes Oktetts verwenden, um anzugeben, ob es das letzte Oktett der Codierung der Erscheinungszahl ist oder nicht, wobei die folgenden siebten Bits jedes Oktetts dazu dienen, die Erscheinungszahl zu codieren.
Alternativ kann man einen weiteren Codierungstyp wählen, in welchem es nicht notwendig ist, die Erscheinungszahl der Elemente eines Strukturschemas einzuführen. Gemäß diesem Codierungstyp führt man einen sogenannten "Entweichungs"- oder "esc"-Typ ein, der den Endzustand der Automaten angibt. Es ist dann notwendig, vorher eine Transformation an den vorher erhaltenden Automaten anzuwenden. Diese Transformation besteht darin, an jedem Zustand der Automaten einen Übergang zurück in Richtung des vorher gehenden Zustands hinzu zu fügen und einen Übergang "esc" in Richtung eines Endzustands hinzu zu fügen, der das Ende der Ausführung des Automaten markiert. Die Codierung von Elementen muss dann nicht mehr als die Form (KV) haben, wobei die Codierung eines Automaten sich durch die Zahl K_esc des Übergangs "esc" beendet.
Im Grunde ist dieser Codierungstyp nur interessant für die Codierung von komplexen Formen und für Elemente, die nicht die maximale Erscheinungszahl haben. Sie ist insbesondere ganz und gar an die Codierung von Gruppen des alternativen Typs angepasst, die eine Anzahl von 2^p unterschiedliche Elemente aufweisen, wobei p eine ganze Zahl ist.
Dieser Codierungstyp kann mit dem vorher gehenden kombiniert werden. Es reicht dann dafür aus, im Kopf des komprimierten Dokuments ein Bit anzuzeigen und den Stellen der Codierung zuzuweisen, an denen sich die Erscheinungszahl finden lassen soll.
Gemäß der Erfindung ist wenigstens ein Basistyp von Informationseinheiten des Dokuments einem externen Komprimierungsmodul 16 zugeordnet. Auf diese Weise werden bei dem Auslesen des Dokuments die jeweiligen wieder erkannten Informationseinheiten analysiert, und wenn ein Typ von Informationseinheit einem externen Komprimierungsmodul 16 zugeordnet ist, wird dieses auf den Inhalt der Informationseinheit und das Resultat der in das komprimierte Dokument eingefügten Komprimierung als Wert der entsprechenden Informationseinheit eingefügt.
Die externen Komprimierungsmodule können zum Beispiel die Norm "mp3" für die Toninformationen anwenden, "jpeg" für die Bilder und "MPEG1" oder "MPEG2" für die Bilddaten.
Wenn irgendein Komprimierungsmodul nicht einem Typ einer Informationseinheit zugeordnet wird, kann man ein Komprimierungsmodul in Abwesenheit verwenden oder die Informationseinheiten, diesem Typ, wie er in dem Anfangsdokument aufgetreten ist, aufweisen, wieder verwenden.
Wenn in dem Kopf des Dokuments angegeben ist, dass die Codierung der Länge optional oder obligatorisch ist, werden die Elemente einem Kopf in dem komprimierten Dokument zugeordnet, der die Länge in der Zahl von Bits des Wertes des Elements enthält. Diese Besonderheit erlaubt einen direkten Zugriff auf ein Element des komprimierten Dokuments, ohne vorher die Elemente in dem Dokument dekomprimiert zu haben, indem mit Hilfe von Automaten nur die jeweiligen Längen dieser Elemente bis zu dem gesuchten Element ausgelesen werden.
Die Länge der Elemente kann in folgender Weise codiert werden.
In dem Fall, in welchem im Kopf des Elements angegeben ist, dass die Codierung der Länge der Elemente obligatorisch ist, wird die Länge L der Elemente in einer Zahl von Bits mit Hilfe der folgenden Formel berechnet: L = 8*p+h (4)wobei p die Zahl von Oktetts (in ASNI-Codierung oder unter Verwendung von höherwertigen Bits jedes Oktetts, das zum Codieren dieser Zahl verwendet wird) darstellt, das verwendet wird, um die Länge des Elements zu codieren, und h die Zahl von Bits darstellt, die diese Länge (h <8) noch haben.
Es ist anzumerken, dass das externe Komprimierungsmodul 16, das verwendet wird, um die Codierung des Wertes eines Elements auszuführen, dafür diese Länge liefern kann.
In dem Falle, in welchem die Codierung der Länge der Elemente nicht obligatorisch ist, gibt der Wert des ersten Bits, der mit dem Wert des Elements übereinstimmt, an, ob die folgenden Bits die Länge des Elements darstellen oder nicht.
Wenn die Elemente Untertypen (angegeben im Kopf des Dokuments) sein können, werden die möglichen neuen Typen in einem im komprimierten Dokument angeordneten Kopf des Dokuments unmittelbar vor dem Wert des Elements eingefügt. Das erste Bit gibt an, ob der Typ des Elements unterschiedlich vom erwarteten Typ ist oder nicht. In dem ersten Fall enthalten die folgenden Bits in dem Kopf des Elements den Code des neuen Typs, wobei dieser Code bestimmt wird, indem alle möglichen Untertypen des Basistyps des Elements nummeriert werden, wobei diese Bezifferung durch die Codierung der Struktur des Dokuments gegeben wird.
In genauerer Weise wird die Codierung eines Elements in drei Grundschritten ausgeführt.
Am ersten Schritt werden die von jedem Knoten ausgehenden Bogen nummeriert. Dieser Schritt ist fakultativ, wenn es nur einen einzigen Bogen am Ausgang des Knotens gibt. Wenn dort n-Bögen abgehen, wird jedem dieser Bögen eine Zahl zugeordnet, die durch die bei der Normierung (Schritt 14) zugewiesenen Ordnung der Bögen gegeben wird. Diese Zahl wird auf n-Bits codiert, wobei n' 2^n–1 < n ≤ 2^n' bedeutet.
Auf diese Weise wird, wenn n Übergänge vom Zustand E hervor gehen, jeder Übergang auf |log₂(n–1)|+1 Bits codiert werden.
Am zweiten Schritt codiert man die Erscheinungszahl jedes Unterautomaten, wie dies vorher beschrieben wurde.
Am dritten Schritt codiert man den Unterautomaten. Diese Behandlung kann durch den folgenden Algorithmus formuliert werden:
Zum Beispiel gibt es für die Codierung der Erscheinung "a₂ a₃ a₁ a₁ a₃" des Automaten (a₁ | a₂ | a₃)^(0..*) drei abgehende Bögen. Die Nummerierung der Bögen wird somit auf zwei Bits ausgeführt. Folglich ist das Resultat der Codierung das Folgende in dem Fall, in welchem die Anzahl von Erscheinungen codiert werden: 0000 0101 01 Va2 10 Va3 00 Va1 00 Va1 10 Va3 in welchem "0000 0101" den binären Wert der Erscheinungszahl darstellt, nämlich 5, und V_a1, V_a2 und V_a3 jeweils die Werte der Erscheinungen von a1, a2 und a3 sind.
In dem Fall, in welchem die Erscheinungszahl nicht codiert wird: 01 Va2 10 Va3 00 Va1 00 Va1 10 Va3 11entspricht 11 der Zahl des Übergangs des Ausgangs "esc".

In dem Beispiel der 7a, 7b mündet die Codierung der Erscheinung "b₂ b₁ a₁" des Automaten (a₁ ^0..*, (b₁ | b₂)^0..*) in dem folgenden Resultat (in dem Fall, in welchem die Zustände nicht fusioniert sind):

0000 0010	Erscheinungszahl der Folge (hier 2 mal)
1	Codierung des Bogens "cho.b₁.b₂"
0000 0010	Erscheinungszahl der Gruppe "cho.b1.b2" (hier 2 mal).
1	Codierung des Bogens b₂ in der Gruppe "cho.b1.b2"
V_b2	Codierung des Wertes von b₂.
0	Codierung des Bogens b, in der Gruppe "cho.b1.b2"

V_b1	Codierung des Wertes von b₁.
0	Codierung des Bogens a₁
0000 0001	Erscheinungszahl von a₁
V_a1	Codierung des Wertes von a₁.
1	Codierung des Bogens am Ausgang F

In dem Fall, in dem die Zustände fusioniert sind (8):

0000 0010	Erscheinungszahl der Folge
10	Codierung des Bogens "cho.b₁.b₂-b₂"
0000 0010	Erscheinungszahl der Gruppe "cho.b1.b2"
V_b2	Codierung des Wertes von b₂.
0	Codierung des Bogens b₁ in der Gruppe "cho.b1.b2"
V_b1	Codierung des Wertes von b₁.
00	Codierung des Bogens a₁
0000 0001	Erscheinungszahl von a₁.
V_a1	Codierung des Wertes von a₁.
10	Codierung des Bogens am Ausgang F.

Es kann notwendig sein, eine Neuordnung des Automaten auszuführen, insbesondere dann, wenn das Schema in der Weise interpretiert oder neu geordnet worden ist, dass die Codierung im Falle der Gruppe ET_NO optimiert wird.
Wenn die Ordnung der Zuweisungen nicht sinnvoll ist ( wie in der Sprache XML), kann man eine Codierung ausführen, welche die Attribute der Elemente in einer vorbestimmten Ordnung neu ordnet, zum Beispiel gemäß einer alphanumerischen Ordnung, dabei der Tatsache folgend, ob sie benötigt werden oder nicht. Diese Anordnung erlaubt es, gleichermaßen die Größe der komprimierten Beschreibung zu reduzieren.
Die Behandlung der Dekomprimierung eines auf diese Weise erhaltenen Dokuments wird ausgeführt, indem die Schritte 11 bis 15 auf das Strukturschema des Dokuments ausgeführt werden, um die Automaten zu erhalten, indem dann der Schritt 15' der Decodierung oder der Dekomprimierung des Dokuments ausgeführt wird, wobei dieser Schritt darin besteht, das komprimierte Dokument unter Ausführung von im Laufe der Schritte 11 bis 14 erhaltenen Automaten zu durchlaufen, in der Weise, dass der Typ und der Name der in dem Dokument wieder gefundenen komprimierten Informationselemente bestimmt werden kann. Die Werte von Elementen, die mit Hilfe der Module 16 zur externen Komprimierung erhalten worden sind, werden mit Hilfe von korrespondierenden Dekomprimierungsmodulen 16' dekomprimiert.
Es wird angemerkt, dass, wenn mehrere Dokumente mit dem gleichen Strukturschema behandelt (komprimiert oder dekomprimiert) werden sollen, die Schritte 11 bis 15 nur ein einziges Mal ausgeführt werden, alleine die Schritte 15 und 16 (oder 15' und 16') müssen bei jedem zu behandelnden Dokument angewendet werden.
Figurenbeschreibung Fig. 1
Fig. 3

Claims

Verfahren zur Komprimierung und Dekomprimierung eines strukturierten Dokuments, das wenigstens einem baumartig verzweigten Strukturschema (1; 31, 39, 43) zugeordnet ist, welches eine Struktur des Dokuments definiert und verschachtelte Strukturelemente (32, 33, 34, 40, 44, 45, 46, a3, a4, X, Y, a1, a5, a1, a2, A, B) aufweist, die Informationseinheiten des Dokuments repräsentieren, wobei die Strukturelemente in drei Kategorien unterteilt sind, nämlich strukturierte Stammelemente (31, 39, 43), Elementgruppen (32, 33, 34, 40, 44, 45, 46) und strukturierte (X, Y, A, B) oder nicht-strukturierte (a3, a4, a1, a5, a1, a2) Basiselemente, die den Elementen auf dem untersten Niveau in der Struktur entsprechen, wobei jedes Basiselement einem Informationstyp zugeordnet ist, dadurch gekennzeichnet, dass wenigstens ein Informationstyp der Basiselemente zuvor einem angepassten Komprimierungsalgorithmus (16) zugeordnet wird, wobei das Verfahren die folgenden Schritte aufweist: – syntaktische Analyse (11) des Strukturschemas des Dokuments, – die Compilierung (13) des Strukturschemas im Hinblick darauf, einen Automaten mit endlicher Anzahl von Zuständen (5) pro Stammelement zu erhalten, wobei jeder Automat die Zustände ("0", "1" ...; "n") aufweist, die untereinander durch Übergänge ("m 1 ", "m2",...; "mn") verbunden sind, welche jeweils die Elemente der Struktur repräsentieren, und – die Komprimierung (15) des zu komprimierenden strukturierten Dokuments (2), welche die Ausführung der Automaten mit endlicher Anzahl von Zuständen (5) an dem Dokument und die Ausführung des Komprimierungsalgorithmus (16) umfasst, wenn die Informationseinheit mit einem dem Algorithmus zugeordneten Informationstyp in dem strukturierten Dokument (2) aufgefunden wird.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass im Hinblick auf die Dekomprimierung des komprimierten Dokuments (10) dieses umfasst die Ausführung von Schritten (11, 12, 13) aus dem Strukturschema (1), um die Automaten (5) zu bestimmen, die der Komprimierung ausgesetzt waren, die Ausführung (15') von Automaten (5) an dem komprimierten Dokument (10), um den Inhalt desselben zu analysieren, um ein Dokument wieder im Ursprungsformat mit einer wenigstens äquivalenten Struktur herzustellen, wobei die Dekomprimierungsalgorithmen (16'), die den bei der Komprimierung (15) verwendeten Komprimierungsalgorithmen (16) entsprechen, ausgeführt werden, um die Informationseinheiten des strukturierten Ursprungsdokuments (2) aus binären Informationssequenzen wieder herzustellen, die in dem komprimierten Dokument während der Ausführung der Automaten aufgefunden wurden.
Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass in dem Falle, in welchem das Strukturschema (1) mit dem Dokument übertragen werden muss, das Verfahren gemäß der Erfindung einen Schritt zur Übertragung des Strukturschemas (5) umfasst.
Verfahren nach einem der Ansprüche 1 bis 3, dadurch gekennzeichnet, dass dieses einen Schritt zur Normierung (12) des Strukturschemas (5) des Dokuments aufweist, sodass eine vordefinierte Einzelfolge von Elementen des Schemas erhalten wird.
Verfahren nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, dass jede Informationseinheit in dem komprimierten Dokument aufgefunden wird, sodass ein direkter Zugriff auf eine spezielle Informationseinheit erlaubt wird, ohne dass es notwendig wird, die der zu dekomprimierenden Einheit voraus gehenden Informationseinheiten zu dekomprimieren.
Verfahren nach einem der Ansprüche 1 bis 5, dadurch gekennzeichnet, dass jedes Element des Strukturschemas ferner einer Zahlengruppe über mögliche Auftrittshäufigkeiten zugeordnet ist, welche die Häufigkeitszahl angibt, mit der eine Informationseinheit mit diesem Strukturelement in der Informationseinheit an einer Stelle unmittelbar über derjenigen, zu der es gehört, auftauchen kann.
Verfahren nach einem der Ansprüche 1 bis 6, dadurch gekennzeichnet, dass es einen Schritt zur Optimierung des Strukturschemas des Dokuments umfasst, bestehend darin, die Zahl der hierarchischen Niveaus der Strukturelementgruppen zu reduzieren.
Verfahren nach einem Ansprüche 1 bis 7, dadurch gekennzeichnet, dass das komprimierte Dokument (10) für jede Informationseinheit des Ursprungsdokuments eine Übergangsnummer, die dem der Informationseinheit zugeordneten Strukturelement entspricht, und den binären Wert der komprimierten Informationseinheit umfasst.
Verfahren nach Anspruch 8, dadurch gekennzeichnet, dass in dem komprimierten Dokument (10) jedes Strukturelement aus wenigstens einem Teil der Strukturelemente des Strukturschemas einer Auftrittshäufigkeitszahl der Informationseinheiten in dem Dokument zugeordnet ist.
Verfahren nach Anspruch 8 oder 9, dadurch gekennzeichnet, dass in dem komprimierten Dokument (10) das Ende einer Gruppe von mehreren Auftritten von Informationseinheiten des gleichen Typs durch eine binäre Sequenz markiert wird, die eine Übergangsnummer zu einem Endzustand repräsentiert.