LAUTHER, Ulrich (Käthe-Bauer-Weg 6, München, 80686, DE)
Patentansprüche
1. Verfahren zur Erzeugung eines die Differenz zwischen einem ersten Datenfile und einem zweiten Datenfile kodierenden Delta-Files, bei welchem Verfahren eine Menge von in den bei ¬ den Datenfiles in teilweiser übereinstimmung vorhandenen Teildatenstrings ( "Pseudo-Matches" ) bestimmt und ein Graph modelliert wird, bei dem jeder Netzknoten einen auf dem ersten Datenfile basierenden Datenverarbeitungsschritt zur Er- zeugung eines Datenbytes des zweiten Datenfiles repräsen ¬ tiert, wobei in dem Graphen jeder einem Datenbyte des zweiten Datenfiles zugeordnete Netzknoten mit allen Netznoten, welche einem unmittelbar vorangehenden Datenbyte des zweiten Datenfiles zugeordnet sind, durch Netzkanten verbunden wird, und den Netzknoten und Netzkanten jeweils ein Kostenwert zugewie ¬ sen wird, bei welchem Verfahren ein kostenoptimierter Pfad im Graphen ermittelt wird, welcher für alle Datenbytes des zwei ¬ ten Datenfiles nur einen Netzknoten pro Datenbyte enthält, und auf Basis des kostenoptimierten Pfads ein Delta-File ge- neriert wird, welcher eine der sukzessiven Folge von Netzkno ¬ ten im kostenoptimierten Pfad entsprechende Abfolge von Da ¬ tenverarbeitungsschritten und deren Datenfelder enthält.
2. Verfahren nach Anspruch 1, bei welchem die auf dem ers- ten Datenfile basierenden Datenverarbeitungsschritte zur Er ¬ zeugung eines Datenbytes des zweiten Datenfiles jeweils auf ein Pseudo-Match bezogen sind.
3. Verfahren nach Anspruch 2, bei welchem die auf dem ers- ten Datenfile basierenden Datenverarbeitungsschritte zur Er ¬ zeugung eines Datenbytes des zweiten Datenfiles ADD- Operationen und Diff-Operationen umfassen, wobei durch eine ADD-Operation das Lesen eines dieser ADD-Operation zugeordneten Datenfeldes aus dem Delta-File und dessen Speichern an einer Position im zweiten Datenfile, welche der Position des Datenbytes entspricht, dem die ADD-Operation zugeordnet ist, bewirkt wird, und wobei durch eine auf ein Pseudo-Match bezo ¬ gene DIFF-Operation ein Speichern eines Summen-Datenbytes, summiert aus einem Datenfeld der DIFF-Operation und einem entsprechenden Datenbyte des Pseudo-Matches des ersten Daten ¬ files, an einer Position im zweiten Datenfile, welche der Position des Datenbytes entspricht, dem die DIFF-Operation zu- geordnet ist, bewirkt wird.
4. Verfahren nach einem der Ansprüche 1 bis 3, bei welchem ein Zeilen und Spalten umfassender matrizenförmiger Graph modelliert wird, wobei sukzessive Spalten des Graphen den suk- zessiven Datenbytes des zweiten Datenfiles zugeordnet werden.
5. Verfahren nach einem der Ansprüche 1 bis 4, bei welchem jedem Netzknoten ein Kostenwert zugewiesen wird, welcher ungleich Null ist, wenn der dem Netzknoten zugeordnete Zustand ein von Null verschiedenes Datenbyte im Delta-File erzeugt und Null ist, wenn der dem Netzknoten zugeordnete Zustand ein zu Null gleiches Datenbyte im Delta-File erzeugt.
6. Verfahren nach einem der Ansprüche 1 bis 5, bei welchem jeder Netzkante ein Kostenwert zugewiesen wird, welcher Null ist, wenn die durch eine Netzkante verbundenen Netzknoten zu gleichen oder kompatiblen Pseudo-Matches gehören, und ungleich Null ist, wenn die durch eine Netzkante verbundenen Netzknoten zu verschiedenen Pseudo-Matches gehören.
7. Verfahren nach einem der Ansprüche 1 bis 6, bei welchem die Erzeugung der Pseudo-Matches die folgenden Schritte um- fasst :
Erzeugen einer Menge von in den beiden Datenfiles vor- handenen, insbesondere maximalen, exakt übereinstimmenden Teildatenbereichen ("Matches") ;
Ermitteln von Matches deren Positionen im ersten und im zweiten Datenfile jeweils um den gleichen Betrag differieren ("kompatible Matches"); - Erzeugen von Pseudo-Matches jeweils durch Zusammenfassen von mehreren kompatiblen Matches zu einem zusammenhängenden Datenbereich .
8. Verfahren nach einem der Ansprüche 1 bis 7, bei welchem eine Verkleinerung von Pseudo-Matches auf Basis eines Kosten ¬ vergleichs von Kosten, welche auftreten, wenn ein Match innerhalb der Lücke eines Pseudo-Matches verwendet oder igno- riert wird, erfolgt.
9. Verfahren nach einem der Ansprüche 1 bis 8, bei welchem aus den Pseudo-Matches eine Menge nicht-überlappender Pseudo ¬ Matches, welche die überdeckung des zweiten Datenfiles mit exakten Matches maximiert, gewählt wird.
10. Verfahren nach einem der Ansprüche 1 bis 9, bei welchem der Delta-File komprimiert wird.
11. Maschinenlesbarer Programmcode für eine elektronische
Datenverarbeitungseinrichtung, welcher Steuerbefehle enthält, die die elektronische Datenverarbeitungseinrichtung zur Durchführung eines Verfahrens nach einem der Ansprüche 1 bis 10 veranlassen.
12. Speichermedium mit einem darauf gespeicherten maschinenlesbaren Programmcode gemäß Anspruch 11. |
Beschreibung
Verfahren zur Erzeugung eines größenoptimierten Delta-Files
Heutzutage ist es oftmals notwendig, Software oder Betriebs ¬ daten zum Ausführen einer Applikation oder zum Betreiben von Geräten, wie beispielsweise Mobilfunkgeräte oder auf Fahrzeu ¬ gen mitgeführte, automatische Mauterfassungseinrichtungen, zu ändern, um hierdurch beispielsweise Fehler zu beheben und verbesserte oder weitere Funktionen zu implementieren ("Soft ¬ ware-Upgrade" oder "Software-Update").
Insbesondere für den Fall, dass die aktuelle Version der Software oder Betriebsdaten über eine Schnittstelle mit ver- gleichsweise langsamer und/oder teurer Datenübertragung (beispielsweise eine Luftschnittstelle im Mobilfunk) übertragen werden soll, ist es unter Umständen sinnvoll, nicht den kompletten Datensatz zu übertragen, sondern eine andere Vorgehensweise zu wählen, bei der lediglich die "Differenz" zwi- sehen der älteren Version und der jüngeren Version übertragen wird, und anschließend mithilfe der übertragenen Differenz die jüngere Version aus der schon vorhandenen älteren Version generiert wird.
Zu diesem Zweck ist beispielsweise aus dem US-Patent
Nr. 6,401,239 die Erzeugung eines Delta-Files durch einen Delta-File-Generator eines ersten Computers (Server) bekannt. Der Delta-File, welcher die Differenz zwischen der ersten Version und der zweiten Version eines Datenfiles kodiert, wird an einen zweiten Computer (Client) übertragen, auf dem die erste Version des Datenfiles gespeichert ist, wobei mit ¬ tels einer Wiederherstellungseinrichtung die zweite Version des Datenfiles aus dessen erster Version und dem Delta-File generiert wird.
Ein zentrales Problem hierbei ist die Erzeugung eines Delta- Files möglichst geringer Größe, um hierdurch die zur übertra ¬ gung des Delta-Files notwendige übertragungszeit beziehungs-
weise die hierbei verursachten übertragungskosten zu minimieren .
Die Erzeugung eines Delta-Files ist beispielsweise in Walter F. Tichy, "The String-to-String Correction Problem with Block Moves", ACM Trans, on Computer Systems, Vol. 2, No. 4, Nov. 1984, Seiten 309-321, beschrieben.
Zur Erläuterung des dort beschriebenen Verfahrens wird Bezug auf Fig. 1 genommen. Demnach werden zwei verschiedene Datenfiles, von denen der eine (beispielsweise eine jüngere Versi ¬ on eines Datenfiles) aus dem anderen (beispielsweise eine äl ¬ tere Version des Datenfiles) mittels eines Delta-Files gene ¬ riert werden soll, als zwei Datenstrings, SO und Sl bezeich- net, aufgefasst. Um einen Delta-File zu erzeugen, wird zu ¬ nächst eine Menge nicht-überlappender, maximaler (exakter) "Matches" gesucht, das heißt Teildatenstrings mit identischen Zeichen und maximaler Länge, die sowohl in SO als auch in Sl, wenn auch an unterschiedlichen Positionen der jeweiligen Da- tenstrings, auftreten.
Das Ergebnis ist eine Folge von Matches und Lücken, welche beispielhaft in Fig. 1 für Sl (in Fig. 1 oben) und für SO (in Fig. 1 unten) dargestellt ist. Durch die beiden in Fig. 1 eingezeichneten Pfeile sind als Beispiel zwei exakt matchende Teildatenstrings gekennzeichnet.
Anschließend wird auf Basis der gefundenen, exakt überein ¬ stimmenden Teildatenstrings ein Delta-File generiert, welcher aus einer Folge an dem ersten Datenfile SO sukzessiv durchzu ¬ führender Datenverarbeitungsschritte (Operationen oder Befehle) besteht, hier COPY- und ADD-Operationen, wobei eine COPY- Operation jeweils aus den exakt übereinstimmenden Datenbereichen und eine ADD-Operation jeweils aus den zwischen den ex- akt übereinstimmenden Datenbereichen befindlichen Lücken resultiert .
Ein COPY-Befehl, welcher in dem dargestellten Beispiel typischer Weise die Syntax "COPY <Länge> «Dffset in S0> <Offset in Sl>" hat, bewirkt ein Kopieren eines exakt übereinstimmenden Datenbereichs, welcher sich in dem Datenstring SO an der Position «Dffset in S0> befindet und die Länge <Länge> hat, nach Sl und zwar an der Position «Dffset in Sl>. Andererseits bewirkt ein ADD-Befehl, welcher typischer Weise die Syntax "ADD <Länge> <Daten von Sl>" aufweist, ein Hinzufügen von Daten der Länge <Länge>, welche im Delta-File mitgeführt werden müssen, in die Lücken zwischen den exakt übereinstimmenden
Datenbereichen in Sl. Auf diese Weise kann der zweite Datenfile Sl durch "Abarbeiten" der sukzessiven Folge von COPY- und ADD-Operationen aus dem ersten Datenfile generiert werden .
Bei dem dargestellten Verfahren bestimmt sich aus der Größe der exakt übereinstimmenden Datenbereiche die Größe des Del ¬ ta-Files, wobei größere Matches das Volumen der im Delta-File zu transportierenden Daten verringern. Die Berechnung einer überdeckung mit maximalen Matches kann heutzutage mithilfe moderner Datenstrukturen, wie sie beispielsweise aus der Bio ¬ informatik zur Berechnung sehr langer DNA-Stränge bekannt sind, in sehr effizienter Weise erfolgen. Der erzeugte Delta- File wird vor einer übertragung typischer Weise komprimiert und vor dem Update- bzw. Upgrade-Prozess dekomprimiert.
Das aufgezeigte Verfahren hat den Nachteil, dass unter Um ¬ ständen sehr viele sukzessiv abzuarbeitende Datenverarbei ¬ tungsschritte im Delta-File enthalten sein müssen, um einen zweiten Datenfile aus einem ersten Datenfile zu generieren.
Dieser Nachteil kann behoben werden, wenn anstatt mit in den beiden Datenfiles exakt übereinstimmenden Teildatenbereichen mit lediglich annähernd gleichen beziehungsweise gering von- einander verschiedenen Datenbereichen, so genannten "PseudoMatches" gearbeitet wird.
In diesem Fall wird in einem Delta-File für jedes Pseudo ¬ Match Byte-weise die Differenz der gering unterschiedlichen Teildatenbereiche gespeichert, wobei die Differenz-Bytes, welche sich aus den exakt übereinstimmenden Daten eines Pseu- do-Matches ergeben, Null sind, während die Differenz-Bytes, welche aus den voneinander verschiedenen Daten eines PseudoMatches resultieren, im Allgemeinen von Null verschieden sind. Die Differenz für einen Pseudo-Match besteht weitgehend aus Nullen (Null-Bytes) und ist somit hoch komprimierbar.
Auf Basis der ermittelten pseudo-matchenden Teildatenstrings wird im Anschluss daran ein Delta-File generiert, welcher aus einer Folge von sukzessiv am ersten Datenfile durchzuführenden Datenverarbeitungsschritten besteht, nämlich DIFF- und ADD-Operationen, wobei eine DIFF-Operation jeweils aus den annähernd übereinstimmenden Datenbereichen und ein ADD-Befehl jeweils aus den zwischen diesen befindlichen Lücken resultiert .
Ein DIFF-Befehl bewirkt durch Byte-weise Addition seiner
Bytes zu den entsprechenden Werten im ersten Datenfile bei Vorliegen eines Null-Bytes in der Differenz ein Kopieren von Daten des ersten Datenfiles (von der dem Null-Byte entspre ¬ chenden Position des ersten Datenfiles an die entsprechende Position des zweiten Datenfiles) und bei Vorliegen eines
Nicht-Null-Bytes ein Kopieren der Summe aus dem Byte des ers ¬ ten Datenfiles und der Daten aus dem DIFF-Befehl an die entsprechende Position in dem zweiten Datenfile.
Im Vergleich zu Delta-Files, welche auf exakt übereinstimmen ¬ den Datenbereichen (Matches) beruhen, kann durch die Verwendung von nur annähernd übereinstimmenden Datenbereichen (Pseudo-Matches) die Anzahl der Pseudo-Matches und damit die Anzahl der im Delta-File zu übertragenden Datenverarbeitungs- Operationen deutlich reduziert werden.
Die Verwendung von Pseudo-Matches kann dem Programmcode des frei verfügbaren Software-Tools "bsdiff" entnommen werden, welcher jedoch nicht weiters dokumentiert ist.
Grundsätzlich ist bei der Verwendung von Pseudo-Matches ein Trade-off zwischen wenigen langen Pseudo-Matches mit vielen Nicht-Null-Bytes und vielen kurzen Pseudo-Matches mit wenigen Nicht-Null-Bytes zu finden. Während der erst genannte Fall für die Datenkompression schlechter ist, ist er in Hinblick auf die geringere Menge an Datenverarbeitungsbefehlen vorteilhaft. Andererseits ist der letzt genannte Fall für die Datenkompression besser, während er nachteilig in Hinblick auf die größere Menge an Datenverarbeitungsbefehlen ist .
Demnach liegt bei der Erzeugung von auf Pseudo-Matches basie ¬ renden Delta-Files ein Optimierungsproblem vor, das die Auswahl der zu verwendenden Matches und ihre Zusammenfassung zu Pseudo-Matches zum Gegenstand hat. In dem oben erwähnten Software-Tool bsdiff wird zu diesem Zweck eine kaum durch- schaubare Heuristik eingesetzt.
Die Aufgabe der vorliegenden Erfindung liegt darin, ein Verfahren zur Erzeugung eines Delta-Files anzugeben, mit welchem eine Optimierung der Größe (Datenvolumen) des Delta-Files er- reicht werden kann.
Diese Aufgabe wird nach dem Vorschlag der Erfindung durch ein Verfahren zur Erzeugung eines Delta-Files mit den Merkmalen von Anspruch 1 gelöst. Vorteilhafte Ausgestaltungen der Er- findung sind durch die Merkmale der Unteransprüche angegeben.
Erfindungsgemäß ist ein Verfahren zur Erzeugung eines die Differenz zwischen einem ersten Datenfile und einem zweiten Datenfile kodierenden Delta-Files (Delta-Patch) gezeigt, wo- bei die beiden Datenfiles jeweils als Datenstrings (Datense ¬ quenzen) aufgefasst werden.
In dem erfindungsgemäßen Verfahren wird zunächst eine Menge von in den beiden Datenfiles in teilweiser übereinstimmung vorhandenen Datenteilstrings ( "Pseudo-Matches" ) bestimmt und auf Basis der Pseudo-Matches der Delta-File generiert. Die Grundidee des erfindungsgemäßen Verfahrens besteht nun darin, dass im Rahmen der Graphentheorie ein Netzwerk (Graph) mit Netzknoten und die Netzknoten verbindenden Netzkanten modelliert wird, wobei jeder Netzknoten einen "Zustand" eines Da ¬ tenbytes der sukzessiven Anordnung von Datenbytes des zweiten Datenfiles repräsentiert. Zudem wird jeder einem Datenbyte zugeordnete Netzknoten mit allen Netznoten, welche einem unmittelbar vorangehenden Datenbyte zugeordnet sind, durch Netzkanten verbunden. Durch die Zuweisung von Kostenwerten zu den Netzknoten und Netzkanten kann durch Verbinden der Netz- knoten mit Quelle und Senke ein kostenoptimierender Pfad durch das Netzwerk ermittelt werden, welcher in der übertragung auf die zugeordneten Zustände der Datenbytes des zweiten Datenfiles einem größenoptimierten Delta-File entspricht. Vorteilhaft wird der Delta-File anschließend komprimiert.
"Zustände" von Datenbytes sind mögliche, auf Datenbytes des ersten Datenfiles basierende Datenverarbeitungsschritte (Ope ¬ rationen oder Befehle) , welche in Verbindung mit zu den Datenverarbeitungsschritten gehörenden Datenfeldern der Erzeu- gung von Datenbytes des zweiten Datenfiles dienen. Solche Da ¬ tenverarbeitungsschritte können beispielsweise "ADD-Operationen " und jeweils auf einen Pseudo-Match bezogene "DIFF-Operationen" sein. Die ADD-Operation bewirkt hierbei das Lesen des zugehörigen Datenbytes aus dem Delta-File (In- put) und dessen Speichern an der laufenden Position im zweiten Datenfile, die anschließend aktualisiert wird. Anders ausgedrückt, bewirkt die ADD-Operation das Lesen eines dieser ADD-Operation zugeordneten Datenfeldes aus dem Delta-File und dessen Speichern an einer Position im zweiten Datenfile, wel- che der Position des Datenbytes entspricht, dem die ADD- Operation zugeordnet ist. Die jeweils auf einen verschiedenen Pseudo-Match bezogenen DIFF-Operationen bewirken ein Speichern einer der jeweiligen Verwendung des Pseudo-Matches ent-
sprechenden Byte-weisen Summe der Datenbytes (aus dem ersten Datenfile und Dateninhalt des DIFF-Befehls) an der laufenden Position im zweiten Datenfile. Anders ausgedrückt, bewirkt die auf ein Pseudo-Match bezogene DIFF-Operation ein Spei- ehern eines Summen-Datenbytes, summiert aus einem Datenfeld (Byte) der DIFF-Operation und einem entsprechenden Datenbyte des Pseudo-Matches des ersten Datenfiles, an einer Position im zweiten Datenfile, welche der Position des Datenbytes ent ¬ spricht, dem die DIFF-Operation zugeordnet ist. Um die ver- schiedenen Zustände der Datenbytes des zweiten Datenfiles als Netzknoten modellieren zu können, werden mögliche Datenverarbeitungsschritte (insbesondere alle) zur Erzeugung von Daten ¬ bytes des zweiten Datenfiles auf Basis von Datenbytes des ersten Datenfiles ermittelt. Besonders vorteilhaft werden die Datenverarbeitungsschritte, wie DIFF-Operationen, auf Pseudo ¬ Matches bezogen.
Bei einer vorteilhaften Art und Weise der Modellierung des Graphen werden die Netzknoten matrixförmig angeordnet, wobei sukzessive Spalten der matrixförmigen Anordnung von Netzknoten den sukzessiven Datenbytes (Bytesequenz) des zweiten Datenfiles zugeordnet werden. Hierbei ist es vorteilhaft, wenn innerhalb einer Spalte, verschiedene Zeilen den verschiedenen Zuständen eines selben Datenbytes des zweiten Datenfiles zu- geordnet werden.
Vorteilhaft wird zur Ermittlung eines kostenoptimierten Pfads durch den Graphen jedem Netzknoten ein Kostenwert zugewiesen, welcher ungleich Null ist, wenn der dem Netzknoten zugeordne- te Zustand ein von Null verschiedenes Datenbyte im Delta-File erzeugt, und andernfalls Null ist, wenn der dem Netzknoten zugeordnete Zustand ein zu Null gleiches Datenbyte (Null- Datenbyte) im Delta-File erzeugt. Ferner wird jeder Netzkante vorteilhaft ein Kostenwert zugewiesen, welcher Null ist, wenn die durch eine Netzkante verbundenen Netzknoten zu gleichen oder kompatiblen Pseudo-Matches gehören, und andernfalls un ¬ gleich Null ist, wenn die durch eine Netzkante verbundenen
Netzknoten zu verschiedenen Pseudo-Matches gehören, also beispielsweise ein neuer DIFF- oder ADD-Befehl nötig wird.
Ist der Graph in der dargestellten Weise erstellt, wird ein kostenoptimierter Pfad im Graphen ermittelt, welcher die Summe aus der Anzahl der Nicht-Null-Bytes und Kosten der Datenverarbeitungsschritte, wie ADD- und DIFF-Operationen, mini ¬ miert. Ein zulässiger Pfad darf hierbei für alle Datenbytes des zweiten Datenfiles nur einen Netzknoten pro Datenbyte enthalten.
Aus dem ermittelten kostenoptimierten Pfad wird ein Delta- File generiert, welcher eine der sukzessiven Folge von Datenbytes des zweiten Datenfiles entsprechende Abfolge von den Netzknoten des kostenoptimierten Pfads zugeordneten Datenverarbeitungsschritten, wie ADD- oder DIFF-Operationen, enthält.
Durch das erfindungsgemäße Verfahren kann somit ein auf Pseu ¬ do-Matches basierender größenoptimierter Delta-File zur Gene- rierung eines zweiten Datenfiles aus einem ersten Datenfile erzeugt werden. Durch den größenoptimierten Delta-File können übertragungszeit und -Kosten für den Delta-File in vorteil ¬ hafter Weise vermindert werden. Das erfindungsgemäße Verfah ¬ ren eignet sich demnach insbesondere für die Erzeugung von Delta-Files zur übertragung mithilfe von Schnittstellen, welche über eine geringe Datenübertragungsrate verfügen und/oder hohe Datenübertragungskosten verursachen.
Bei einer weiteren vorteilhaften Ausgestaltung des erfin- dungsgemäßen Verfahrens kann die Erzeugung der Pseudo-Matches in der Weise erfolgen, dass zunächst eine Menge von in den beiden Datenfiles in exakter übereinstimmung vorhandenen Teildatenbereichen ("Matches") ermittelt wird. Hierbei han ¬ delt es sich vorteilhaft um maximale Matches mit maximaler Länge. Anschließend werden jene Matches ermittelt, deren Po ¬ sitionen im ersten und im zweiten Datenfile jeweils um den gleichen Betrag differieren, so genannte "kompatible Mat ¬ ches", und Pseudo-Matches jeweils durch Zusammenfassen mehre-
rer kompatibler Matches zu einem einzelnen zusammenhängenden Datenbereich erzeugt.
Bei einer weiteren vorteilhaften Ausgestaltung des erfin- dungsgemäßen Verfahrens kann eine Verkleinerung von PseudoMatches auf Basis eines Kostenvergleichs von Kosten, welche auftreten, wenn ein Match innerhalb der Lücke eines Pseudo ¬ Matches verwendet oder ignoriert wird, erfolgen.
Bei einer weiteren vorteilhaften Ausgestaltung des erfindungsgemäßen Verfahrens wird aus den Pseudo-Matches eine Men ¬ ge nicht-überlappender Pseudo-Matches erzeugt, welche die überdeckung des zweiten Datenfiles mit exakten Matches maxi- miert .
Die Erfindung erstreckt sich ferner auf einen maschinenlesba ¬ ren Programmcode (Computerprogramm) für eine elektronische Datenverarbeitungseinrichtung, welcher Steuerbefehle enthält, die die elektronische Datenverarbeitungseinrichtung zur Durchführung eines wie oben beschriebenen, erfindungsgemäßen Verfahrens veranlassen.
Darüber hinaus erstreckt sich die Erfindung auf ein Speichermedium (Computerprogrammprodukt) mit einem darauf gespeicher- ten maschinenlesbaren Programmcode für eine elektronische Da ¬ tenverarbeitungseinrichtung, welcher Steuerbefehle enthält, die die elektronische Datenverarbeitungseinrichtung zur Durchführung des oben beschriebenen, erfindungsgemäßen Verfahrens veranlassen.
Die Erfindung wird nun anhand eines Ausführungsbeispiels nä ¬ her erläutert, wobei Bezug auf die beigefügten Figuren genommen wird.
Fig. 1 zeigt in einer schematischen Darstellung exakt übereinstimmende Teildatenstrings (Matches) zweier Daten ¬ files .
Fig. 2 zeigt in einer schematischen Darstellung einen Graphen des erfindungsgemäßen Verfahrens, in dem Zustände von Daten-Bytes als Netzknoten modelliert sind.
Fig. 1 wurde bereits eingangs beschrieben, weshalb sich eine nähere Erläuterung hier erübrigt .
Gemäß dem dargestellten und erläuterten Ausführungsbeispiel besteht das erfindungsgemäße Verfahren aus mehreren Schrit- ten, die nun im Einzelnen erläutert werden:
In dem Ausführungsbeispiel soll ein auf Pseudo-Matches basie ¬ render Delta-File generiert werden, mithilfe dessen ein zwei ¬ ter Datenfile aus einem ersten Datenfile erzeugt werden kann. Der zweite Datenfile kann hierbei ein Datenfile zum Updaten oder Upgraden des ersten Datenfiles sein.
Schritt 1 : Ermittlung exakter Matches
In Schritt 1 wird zunächst der zweite Datenfile mit einer Folge von maximalen exakten Matches, das heißt vollständig übereinstimmenden Datenbereichen der beiden Datenfiles, welche eine maximale Datenlänge aufweisen, möglichst vollständig überdeckt .
Zum schnellen Auffinden solcher exakten Matches kann beispielsweise ein Verfahren verwendet werden, welches in U. Manber, E. W. Myers, "Suffix arrays : a new method for on ¬ line string searches", SIAM J. Comput . 22(5), 1993, Seiten 935-948, beschrieben ist.
Demnach wird aus dem ersten Datenfile zunächst eine Anordnung von Teildatenstrings, ein so genanntes "Suffix-Array" , näm ¬ lich eine sortierte Menge, welche alle Suffixes (Teildaten- strings) eines Datenstrings enthält, ermittelt.
Beispielsweise enthält der Datenstring "foo" die Suffixes "foo", "oo" und "o". Das Suffix-Array wird als ein Array von
sortierten Indizes der Substrings gespeichert, im vorliegen ¬ den Beispiel (0, 2, 1) für "foo", "o" und "oo" .
Zum Aufbau eines Suffix-Arrays und zur Suche von maximal matchenden Teildatenstrings sind effiziente Algorithmen im Stand der Technik verfügbar und dem Fachmann als solche bekannt .
Ist eine Suffix-Array erstellt, so wird der zweite Datenfile von Anfang bis Ende durchlaufen, wobei (exakte) Matches er ¬ kannt und in einer Liste gespeichert werden. Dieser Schritt kann beispielsweise durch den folgenden Pseudo-Code beschrie ¬ ben werden:
build suffix array SA from old file; List matches; int new_size = length of new file; int scan = 0; while (scan < new_size) { (posO, length) = find_maximum_match (SA, scan); if (length > 0) { matches . append (new Match (posO, scan, length)); scan+=length; } eise scan++;
Die Prozedur find_maximum_match sucht nach einem maximalen Match (exakt übereinstimmenden Teildatenbereich) im ersten Datenfile bezüglich des Teildatenstrings, der auf der Positi ¬ on scan im zweiten Datenfile beginnt. Sie gibt die Position im ersten Datenfile und die Länge der übereinstimmung zurück. Im Erfolgsfall (Länge > 0) wird der Match in der Liste der Matches gespeichert und im zweiten Datenfile kann die ent- sprechende Länge übersprungen werden. Andernfalls wird die scan-Position um das Inkrement 1 erhöht. Folgen solcher nicht-matchender Schritte entsprechen den Lücken in Fig. 1.
Zu diesem Algorithmus können beispielsweise zwei Modifikatio ¬ nen durchgeführt werden:
Modifikation 1: Wenn ein Match Ml gefunden wird, der unmittelbar (das heißt ohne Lücke) auf einen vorausgehenden Match MO folgt, wird ge ¬ prüft, ob Ml rückwärts ausgedehnt werden kann, da die Positi ¬ on "scan-1" im vorangegangenen Schleifendurchlauf nicht untersucht wurde. Ist dies der Fall, und ist das resultierende Ml länger als das entsprechend reduzierte Ml, dann ist es vorteilhaft, wenn diese Modifikation durchgeführt wird, da längere Matches zu bevorzugen sind.
Modifikation 2: Wenn die Länge eines Matches unterhalb einer vorgegebenen
Schranke liegt, wird geprüft, ob ein Löschen dieses Matches die Kosten erhöhen würde: falls nein, wird dieser Match gelöscht, um das Speichern einer hohen Anzahl kleiner nutzloser Matches zu vermeiden; falls ja, wird dieser Match nicht ge- löscht. Als "Kosten" wird hier der Beitrag zur Länge des komprimierten Delta-Files angesehen. Diese wird näherungswei ¬ se bestimmt durch die Anzahl der Nicht-Null-Bytes im Delta- File plus Kostenanteile für die einzelnen COPY-, ADD- and DIFF-Befehle.
Schritt 2 : Erzeugung von Pseudo-Matches
In Schritt 2 werden Pseudo-Matches aus den in Schritt 1 er ¬ mittelten (exakten) Matches generiert. Hierbei werden kompa- tible exakte Matches jeweils zu einem Pseudo-Match zusammen- gefasst, wobei als kompatible exakte Matches solche exakten Matches betrachtet werden, deren Positionen ("posO") im ers ¬ ten Datenfile und deren Positionen ("posl") im zweiten Datenfile um den gleichen Betrag differieren. (In Fig. 1 betrach- tet, haben kompatible exakte Matches zueinander parallele Pfeile.) Wenn die Differenz des zweiten Datenfiles zu dem ersten Datenfile gebildet wird, kann lediglich die Lücke zwi ¬ schen den kompatiblen exakten Matches Nicht-Null-Bytes erzeu-
gen. Anders ausgedrückt, es sind alle exakten Matches kompa ¬ tibel, für die die Differenz (posl-posO) den gleichen Wert hat.
Um die Pseudo-Matches zu erzeugen, werden alle exakten Mat ¬ ches nach dieser Differenz (posl-posO) sortiert, wobei eine Folge von Bündeln mit gleicher Differenz erhalten wird. Jedes dieser Bündel entspricht einem Pseudo-Match .
Bei dieser Vorgehensweise gehört jeder exakte Match genau zu einem Pseudo-Match. Pseudo-Matches können sich gegenseitig überlappen, wobei ein exakter Match der kompatiblen exakten Matches eines Pseudo-Matches in die Lücke der kompatiblen ex ¬ akten Matches eines anderen Pseudo-Matches fällt.
Schritt 3 : Aufspalten von Pseudo-Matches
Die in Schritt 2 durch Zusammenfassen von kompatiblen exakten Matches erzeugten Pseudo-Matches können mitunter sehr lang sein, und demnach große (nur teuer zu schließende) Lücken enthalten. Es wird daher in Schritt 3 jede Lücke innerhalb eines Pseudo-Matches und die Matches (aus anderen Pseudo ¬ Matches) innerhalb dieser Lücke untersucht. Hierbei werden die Kosten verglichen, die entstehen, wenn das Match inner- halb der Lücke eines Pseudo-Matches verwendet wird (dabei entstehen zwei DIFF-Befehle) und die Kosten, die auftreten, wenn es ignoriert wird (dabei entstehen zusätzliche Nicht ¬ Null-Bytes im Delta-File) . Für den Fall, dass erstgenannte Kosten niedriger sind, wird der Pseudo-Match aufgeteilt; für den Fall dass zweitgenannte Kosten niedriger sind, wird der Pseudo-Match nicht aufgeteilt.
Schritt 4 : Auswahl von Pseudo-Match-Kandidaten
In Schritt 4 wird eine Menge viel versprechender Pseudo ¬ Matches für Schritt 5 des Verfahrens ausgesucht. Hierbei wird aus der Menge aller (im Allgemeinen) überlappender PseudoMatches eine nicht-überlappende Teilmenge (oder Kette) von
Pseudo-Matches bestimmt, die die überdeckung des zweiten Da ¬ tenfiles mit exakten Matches maximiert oder - äquiva ¬ lent hierzu - die Länge der Lücken minimiert.
Hierzu wird von der Tatsache ausgegangen, dass in einer opti ¬ malen Kette C n von n Pseudo-Matches pi, p 2 , ...p n jede Teilkette C 1 von i Pseudo-Matches pi, p 2 , -Pi ebenfalls eine optimale Teilkette sein muss. Daher kann die optimale Kette C n als Er ¬ weiterung einer optimalen Teilkette c n -i gefunden werden.
Hieraus ergibt sich ein dynamisches Programm für die Bestim ¬ mung der optimalen Kette, das leicht durch einen Durchlauf von links nach rechts über die Pseudo-Matches realisiert wer ¬ den kann, wenn man zunächst die Pseudo-Matches nach ihren linken und rechten Enden sortiert und in jedem Pseudo-Match die überdeckung einer optimalen Kette speichert, die mit die ¬ sem Pseudo-Match endet.
Im folgenden beispielhaften Pseudo-Code ist "cover(g)" die Anzahl matchender Bytes eines Pseudo-Matches "g", also die Gesamtlänge der exakten Matches, aus denen der Pseudo-Match besteht; "total_cover (g) " ist die Gesamtlänge der Matches ei ¬ ner Kette von Pseudo-Matches, deren Element g ist.
List starting; List ending; add all Pseudo-Matches to lists starting and ending; sort list starting by left end; sort list ending by right end; Pseudo*e = ending. first ();
Pseudo*best_ending = 0; int best_cover = 0; for all pseudos s sorted by left end {
// maintain best group e ending before s: while (right end of e < left end of s) { if (total_cover (e) > best_cover) { best_cover = total_cover (e) ; best_ending = e;
} e = successor of e in list ending_groups; } pred(s) = best_ending; // let s point to best_ending total_cover (s) = cover(s) + total_cover (best_ending) ;
Es kann nunmehr der Pseudo-Match mit maximalem Wert "to- tal_cover" gesucht werden, wobei den Rückwärtszeigern "pred" gefolgt wird, um so die ganze optimale Kette zu durchlaufen.
Schritt 5 : Zuordnung der Bytes des zweiten Datenfiles zu Pseudo-Match-Kandidaten
Dies ist der Hauptoptimierungsschritt des erfindungsgemäßen Verfahrens. Hierbei wird für jedes Byte des zweiten Datenfi ¬ les entschieden, ob es einem Pseudo-Match zugeordnet wird und falls ja, welchem.
Für den Fall, dass ein Byte des zweiten Datenfiles einem Pseudo-Match zugeordnet wird, wird es Teil einer DIFF- Operation und die Differenz zwischen dem Wert dieses Bytes und dem Wert des entsprechenden Bytes im ersten Datenfile wird gespeichert. Für den alternativen Fall, dass ein Byte des zweiten Datenfiles einem Pseudo-Match nicht zugeordnet wird, wird es Teil einer ADD-Operation und sein Wert wird ge ¬ speichert .
Falls das einem Pseudo-Match zugeordnete Byte zu den exakt übereinstimmenden Datenbereichen des Pseudo-Matches gehört, ist die Differenz Null; andernfalls ist die Differenz nicht Null. Bei Elementen der ADD-Operationen kann die Differenz von Null verschieden sein. Ziel einer Optimierung ist es, die Anzahl dieser von Null verschiedenen Bytes zu minimieren, da sie die Kompressibilität des resultierenden Delta-Files ver ¬ ringern .
Die Anzahl der Nicht-Null-Bytes ist jedoch nur ein Teil der Zielfunktion. Ein anderer Teil der Zielfunktion ist der Speicherbedarf für die DIFF- und ADD-Operationen, also für Opera- tionscode, Positions- und Längenangaben. Ob für ein Byte ein neuer Befehl abgesetzt werden muss, hängt von den Entschei ¬ dungen für dieses Byte und das vorangehende Byte ab, das heißt, es muss der gesamte Kontext betrachtet werden.
In Schritt 5, dem Kern des erfindungsgemäßen Verfahrens, erfolgt die Entscheidung, ob und welchem Pseudo-Match ein Byte des zweiten Datenfiles zugeordnet wird, durch dynamische Pro ¬ grammierung, oder äquivalent, durch die Berechnung eines kürzesten (das heißt kostenoptimierten) Pfads in einem Graphen, welcher wie folgt modelliert wird.
Es wird nun Bezug auf Fig. 2 genommen, worin in einer schematischen Darstellung ein Graph des dynamischen Programms des erfindungsgemäßen Verfahrens veranschaulicht ist. Zudem ist in Fig. 2 die sukzessive Folge von Bytes des zweiten Datenfi ¬ les dargestellt.
Zur Modellierung des Graphen von Fig. 2 werden die möglichen Zustände der Datenbytes der sukzessiven Folge von Datenbytes des zweiten Datenfiles als Netzknoten aufgefasst. Hierbei werden für jedes Byte des zweiten Datenfiles, wie in Fig. 2 beispielhaft für die sukzessiven Bytes (i-1), (i) und (i+1) dargestellt ist, k Netzknoten in den vertikalen Spalten des Graphen (in Fig. 2, k=4) angeordnet, welche jeweils den Zu- ständen eines jeweiligen Datenbytes des zweiten Datenfiles entsprechen. Dies sind für das Datenbyte (i-1) die Zustände (i-l)i, (i-1) 2, (i-1) 3 und (i-l) 4 , für das Datenbyte i die Zu ¬ stände (i)i, (i)∑, (i)3, und (i)4, und für das Datenbyte (i+1) die Zustände (i+l)i, (i+l) 2 , (i+l) 3 und (i+l) 4 .
Mögliche Zustände eines jeden Datenbytes des zweiten Datenfi ¬ les können sein: ein ADD-Befehl, welcher bewirkt, dass dieses Datenbyte aus dem Input (Delta-File beziehungsweise Datenfeld
des ADD-Befehls) gelesen wird, und DIFF ma tch D -Befehle, welche jeweils bewirken, dass das Summen-Byte, summiert aus der Dif ¬ ferenz dieses Datenbytes zu dem Datenbyte in der entsprechen ¬ den Position im ersten Datenfile, welche der Verwendung von Pseudo-Match j entspricht, und dem entsprechenden Datenbyte im ersten Datenfile gespeichert wird.
In dem Graphen wird jedem Netzknoten ein Kostenwert verschieden von Null, beispielsweise 1, oder Null zugeordnet, je nachdem ob dieser Zustand ein Nicht-Null-Byte oder ein Null- Byte im Delta-File erzeugt .
Zudem wird jeder einem Datenbyte zugeordneter Netzknoten des Graphen mit jedem dem unmittelbar vorhergehenden Datenbyte zugeordneten Netzknoten durch Netzwerkkanten verbunden. Den
Netzwerkkanten wird ebenfalls ein Kostenwert zugeordnet, näm ¬ lich Null, wenn die beiden verbundenen Netzknoten zu gleichen oder kompatiblen Pseudo-Matches gehören und ungleich Null, beispielsweise 1, im anderen Fall, wenn eine neue Operation notwendig wird. Im letztgenannten Fall werden die Kosten dieser Operation eingetragen.
Für den erstellten Graphen mit zugeordneten Kostenwerten für Netzknoten und Netzkanten wird mittels eines Algorithmus ein kürzester (kostenoptimierter) Pfad im Graphen ermittelt.
Ein Pfad durch dieses Netzwerk, der genau einen Netzknoten aus jeder Spalte enthält, entspricht einer zulässigen Folge von DIFF- und ADD-Operationen, die alle Datenbytes abdeckt und somit einen korrekten Delta-File erzeugt. Der kürzeste Pfad aller solcher Pfade minimiert die Summe aus der Anzahl der Nicht-Null-Bytes und der Kosten der ADD- und DIFF- Befehle. Ein solcher kürzester (kostenoptimierter) Pfad im Graphen kann durch einen wie unten dargestellten Algorithmus zur Ermittlung eines kürzesten Pfads erfolgen.
Obwohl es k n verschiedene Pfade für einen zweiten Datenfile der Länge n gibt, kann der kürzeste Pfad auf Grund der spe-
ziellen Struktur des Graphen in O(k 2 n) Schritten gefunden werden. Dies ist im folgenden Pseudo-Code beispielhaft darge ¬ stellt:
for all positions i = 1 ... n of the new file { update set of candidate matches; allocate one node per candidate; for all nodes v at current position { int best_cost = ∞; for all nodes w at previous position { cost_w_v = total_cost (w) + cost (w,v) + cost (V) ; if (cost_w_v) < best_ . cost) { best_cost = = cost_v _w; best_pred = = w;
}
} pred (v) = best_pred; total_cost (V) =best_ _cost ; } }
Nachdem alle Positionen bearbeitet wurden (Hauptschleife im obigen Pseudo-Code), wird aus der letzten Spalte der Netzkno- ten mit dem kleinsten Wert "total_cost" gewählt und den
"pred-Zeigern" (in Fig. 2 fett eingezeichnet) rückwärts ge ¬ folgt, um den kürzesten (billigsten) Pfad zu identifizieren. Anschließend werden entsprechend den Byte-Zuordnungen längs dieses Pfads die ADD- und DIFF-Operationen des Delta-Files erzeugt.
Im Weiteren werden weitere Modifikationen des erfindungsgemäßen Verfahrens beschrieben:
Modifikation 3: Menge der Pseudo-Match-Kandidaten und ihre Pflege
Da der Zustand eines Netzknotens der Zuordnung des betreffen ¬ den Datenbytes zu einem Pseudo-Match entspricht, ist es vor ¬ teilhaft, eine Menge geeigneter Pseudo-Matches bereit zu hal ¬ ten und beim Durchlaufen obigen Pseudo-Code zu pflegen. Hier- zu wird in diese Menge zum einen der Pseudo-Match aus der in Schritt 4 "Auswahl von Pseudo-Match-Kandidaten" berechneten Kette aufgenommen, der die aktuelle Position überdeckt; zum anderen wird eine vorgebbare Anzahl von Matches aus der Umge ¬ bung der aktuellen Position aufgenommen. Beim übergang zu ei- ner neuen Position wird diese Menge aktualisiert, das heißt, zurück liegende Elemente verlassen die Menge und voraus lie ¬ gende Matches werden eingefügt.
Modifikation 4: Reduktion des Speicherbedarfs des Verfahrens
Wird das Verfahren so wie beschrieben implementiert, müssen k x n Netzknoten gespeichert werden, von denen jeder die akkumulierten Kosten des besten Pfads durch diesen Netzknoten, den Zeiger auf den Vorgänger-Netzknoten im besten Pfad und einen Zeiger auf den zugehörigen Match enthält. Dies sind 12k Datenbytes pro Input-Datenbyte und daher für große Input- Files vergleichsweise viel. Hinzu kommt noch der Speicherbe ¬ darf für k 2 n Kanten. Dies kann durch vier Modifikationen des Grundalgorithmus vermieden werden:
Modifikation 4.1:
Das "total_cost "-Feld wird nur in den Netzknoten der aktuel ¬ len und der vorausgehenden Spalte benötigt. Es werden daher zwei Knotentypen verwendet, ein großer Knotentyp mit einem "total_cost "-Feld für diese speziellen Spalten und einen kleinen Knotentyp für "alte" Spalten.
Modifikation 4.2:
Es wird die Anzahl der kürzesten Pfade gespeichert, zu denen ein Netzknoten gehört, also die Anzahl eingehender fetter Kanten, wie in Fig. 2 dargestellt ist. Wenn nach Bearbeitung
von Spalte i dieser Wert für einen Netzknoten in Spalte (i-1) Null ist, so kann dieser gelöscht werden. Dabei wird im Vor ¬ gänger-Netzknoten dieser Wert dekrementiert und gegebenenfalls dieser Netzknoten ebenfalls gelöscht, und so weiter.
Modifikation 4.3:
Es wird in den Netzknoten ein Längenfeld eingeführt, das zu ¬ nächst den Kostenwert 1 erhält. Wenn ein aktueller Knoten "u" und sein Vorgänger-Netzknoten "v" sich auf den gleichen (oder zwei kompatible) Match (es) beziehen, lässt man den "pred"- Zeiger von "u" auf "pred(v)" zeigen, reduziert die Anzahl kürzester Pfade in "v" um 1 und erhöht die Länge in "u" um die Länge von "v" . Anschließend können "v" und der Vorgänger möglicher Weise gelöscht werden. Ein Knoten repräsentiert jetzt nicht mehr ein einzelnes Datenbyte, sondern eine Folge von Datenbytes, die gleich behandelt werden, also einen Pseu- do-Match. Dies reduziert den Speicherbedarf dramatisch.
Modifikation 4.4:
Kanten werden nicht gespeichert, sondern ihre Kostenwerte werden "on-the-fly" ermittelt, wenn sie benötigt werden.
Next Patent: A COOKING AID COMPOSITION OBTAINED THROUGH THERMAL PROCESSING