Kurs:Algorithmen und Datenstrukturen/Kapitel 2/ExtraDix

Der Sortieralgorithmus ExtraDix ist eine Erweiterung von Radixsort (Extended raDix). Er ist somit nicht-vergleichsbasiert, stabil und arbeitet indirekt, es wird also zunächst die korrekte Reihenfolge festgestellt und erst dann werden die Datensätze in die korrekte Reihenfolge gebracht. Das Ergebnis der Sortierung befindet sich wahlfrei entweder am Platz der Original-Datensätze (In-placein place) oder in einem Zielarray. Es gibt weder einen Best- noch einen Worst-Case in Bezug auf die Sortierzeit und der zeitliche Aufwand steigt linear mit der Anzahl der Datensätze an. Der Algorithmus kann auf alle gängigen Datentypen angewendet werden. ExtraDix wurde 2009 von Jürgen D. Henning entwickelt; eine Pseudocode- und eine C-Version wurden unter die GNU General Public License gestellt und können von Sourceforge bezogen werden.

Funktionsweise

Klassischerweise wurde Radixsort eingesetzt, um Lochkarten zu sortieren. Hierzu wurde eine Lochkartensortiermaschine zunächst so eingestellt, dass sie die Einerstellen abfragte und die Lochkarten auf zehn Schächte verteilte. Wenn der Stapel abgearbeitet war, wurden die Lochkarten bei Schacht Null beginnend eingesammelt. Dann wurde die Sortiermaschine auf die Zehnerstellen eingestellt und der Sortiervorgang wiederholt. Das Verteilen und Einsammeln wurde solange wiederholt, bis nach der höchstwertigen Stelle sortiert war und somit auch alle Lochkarten. Sollte die Sortierung nicht aufsteigend sondern absteigend sein, dann sammelte man die Lochkarten jeweils in umgekehrter Reihenfolge ein. Bei der Sortierung von Lochkarten arbeitet Radixsort mit 10 verschiedenen Symbolen, nämlich den Ziffern 0 bis 9.

ExtraDix arbeitet fest mit den 256 verschiedenen Symbolen, die man durch ein Byte darstellen kann. Man könnte auch sagen, dass ExtraDix nicht mit dem dezimalen System arbeitet, sondern mit dem 256'er-System; diese Größe bietet sich an, da 'char' den kleinsten Schlüssel darstellt und alle weiteren Datentypen aus einer ganzzahligen Anzahl von Bytes gebildet werden.

Sollen etwa Zeichenketten sortiert werden, so liefert ExtraDix nur deshalb vernünftige Ergebnisse, weil die Interpretationen der Byteinhalte sinnvoll in Listen stehen wie etwa der ASCII-Tabelle. Beinhaltet ein Byte etwa die Ziffer Null, dann muss der Datensatz in den 48zigsten Eimer befördert werden, beinhaltet es ein 'A', dann kommt er in den mit der Nummer 65. Das Verfahren schaut also nicht darauf, was mit dem Inhalt gemeint ist, sondern interpretiert den Inhalt des Byte als positive Zahl zwischen Null und 255.

ExtraDix hebt also die Unterscheidung von Adressen und Daten auf, denn der Inhalt des aktuell betrachteten Byte stellt die Adresse des Zieleimers dar!

Da die Sortierschlüssel im Allgemeinen mehrere Bytes lang sind wird folgende sprachliche Unterscheidung gemacht: Unter einem Sortierdurchgang wird die Sortierung nach einem einzigen Byte aus dem Sortierschlüssel verstanden; es wird also bei allen Datensätzen lediglich dieses eine Byte betrachtet. Unter einem Sortiervorgang wird die Sortierung der ganzen Datensätze nach einem kompletten Sortierschlüssel verstanden. Besteht der Sortierschlüssel aus einer vorzeichenlosen ganzen Zahl (normalerweise aus vier Byte bestehend), dann werden vier Sortierdurchgänge gemacht, um den Sortiervorgang durchzuführen.

Die simulierte Sortiermaschine

Für die Umsetzung von ExtraDix wird eine Sortiermaschine mit 256 Schächten simuliert. Da die Datensätze beim Einsammeln der Datensätze in der Reihenfolge entnommen werden müssen, in der sie in den jeweiligen Schacht einsortiert wurden, werden hierfür FIFO's benutzt.

Sollen etwa 1.000 Datensätze sortiert werden, müßte jeder FIFO so groß sein, dass im Zweifelsfalle alle Datensätze in ihm gespeichert werden könnten. Dieses Problem wird umgangen, indem eine zentrale Speicherverwaltung verwendet wird, und sich die 256 FIFO's die 1.000 Speicherstellen teilen. Zu Beginn eines Sortiervorgangs wird entsprechend der Anzahl der Datensätze dynamisch entsprechend viel Speicher vom Betriebssystem angefordert.

Bei Radixsort wird für jedes Byte des Schlüssels jeweils der ganze Datensatz (Lochkarte) bewegt. Wenn man wahlfreien Zugriff auf die Eingabedatensätze hat, ist dies nicht notwendig. Es genügt, wenn man in dem FIFO lediglich die Datensatznummer einträgt. Und in welches FIFO die Datensatznummer eingetragen werden soll, ergibt sich jeweils ganz einfach aus dem Wert, den das aktuell betrachtete Byte des Sortierschlüssels hat.

Intern sind die FIFO's als verkettete Liste angelegt und die Verwaltung dieser Liste erfolgt über ein Array, in dem jeweils auf das erste und auf das letzte Element eines FIFO's verwiesen wird; und in den Elementen des FIFO findet man lediglich die Datensatznummern der Eingabedatensätze und die Zeiger auf das Folgeelemente im aktuellen FIFO. Hierdurch läßt sich ein einfacher und sehr schneller Zugriff realisieren.

Klassischerweise werden bei Radixsort nach einem Sortierdurchgang die einzelnen Datensätze eingesammelt, um sie anschliessend dem nächsten Sortierdurchgang zuzuführen. Da eine per Software realisierte Sortiermaschine nur etwas Speicherplatz kostet, arbeitet ExtraDix mit zwei FIFO-Registern und sortiert die Daten beim Einsammeln gleich in den anderen Satz von FIFOs ein. Diese Register werden abwechselnd als Ziel benutzt.

Sortierung nach natürlichen Zahlen

Auf PC's wird eine natürliche Zahl durch vier Byte repräsentiert, wobei das erste Byte das niederwertigste ist und das vierte Byte das höchstwertigste. Die Sortierung beginnt beim niederwertigsten Byte, also dem ersten.

Zu Beginn eines Sortiervorgangs werden alle Datensätze in das erste FIFO des zweiten Registers eingetragen, wodurch sie in der Originalreihenfolge für den ersten Sortierdurchgang verfügbar werden.

Im ersten Sortierdurchgang wird jeweils das niederwertigste Byte des Sortierschlüssels betrachtet. Bei jedem Sortierdurchgang werden der Reihe nach die FIFO's des anderen Registers ausgelesen; in diesem Fall stehen alle Referenzen im ersten FIFO. Es wird die Originalposition des Datensatzes in den Eingabedaten aus dem FIFO ausgelesen, ein Zeiger auf diesen Datensatz berechnet und das niederwertigste Byte des Schlüssels gelesen. Der Inhalt des Bytes gibt die Nummer des Ziel-FIFO an, wohin die Datensatznummer geschrieben wird.

Es folgen noch drei weitere Sortierdurchgänge. Abschliessend werden die FIFO's der Reihe nach ausgelesen und man bekommt die Datensatznummern in der Reihenfolge, wie sie einer korrekten Sortierung entsprechend anzuordnen wären. Die Datensätze können entweder in dieser Reihenfolge in ein Zielarray eingetragen werden, oder mit ein wenig Mehraufwand (zwei Integerhilfsarrays um sich zu merken, wohin ein Datensatz verschoben wurde, weil sein Platz für das Ergebnis benötigt wurde) kann man die Datensätze auch innerhalb des Eingabearrays umkopieren.

Es ist einsichtig, dass der Zeitzuwachs linear ist, denn jedes Byte der Sortierschlüssel wird exakt nur ein einziges mal betrachtet / bearbeitet und die Anzahl der Bytes steigt linear mit der Anzahl der Datensätze.

Die Sortierung von natürlichen Zahlen die aus einem, zwei oder acht Bytes bestehen erfolgt sinngemäß.

Sortierung von vorzeichenbehafteten ganzen Zahlen

Für die niederwertigen Bytes einer ganzen Zahl ändert sich nichts an dem Algorithmus, aber für das Byte mit dem Vorzeichen ist eine besondere Behandlung notwendig, denn wenn das höchstwertige Bit gesetzt ist, würde man mit einem negativen Index in die FIFO-Verwaltung gehen. Also wird einfach der Wert 128 zu dem Byteinhalt addiert. Hierdurch wird der Wertebereich in den positiven Bereich transponiert, wobei die Werterelationen aber beibehalten werden.

Der Zeitbedarf zur Sortierung von vorzeichenbehafteten ganzen Zahlen unterscheidet sich nicht vom dem für natürliche Zahlen.

Sortierung von Bytefolgen

Bei Bytefolgen / Zeichenketten ist die Konvention, dass das erste Byte das höchstwertige Zeichen enthält. ExtraDix fordert, dass alle Bytefolgen nominell gleich lang sind, und beginnt die Sortierung mit dem letzten Byte. Wurde nach dem ersten Byte sortiert, so ist der Sortiervorgang abgeschlossen.

Da jedes Byte aus jeder Bytefolge nur ein einziges mal betrachtet wird, ergibt sich wieder die sehr hohe Sortiergeschwindigkeit zusammen mit einem linearen Zeitzuwachs.

Sortieren von Strings

In C gilt die Konvention, dass Strings immer mit einem Nullbyte (Inhalt ist die binäre Null) abgeschlossen werden, es darf also beliebiger Datenmüll hinter diesem Nullbyte stehen. Sortiert man Strings als Bytefolgen, kann hier scheinbar der Effekt auftreten, dass die Sortierung nicht stabil erscheint; dies liegt daran, dass hinter dem Nullbyte nach zufälligem Datenschrott sortiert wurde, der für den Nutzer nicht direkt sichtbar ist.

Da in der Praxis das Datenfeld für einen String deutlich länger ist, als der durchschnittliche String, würde sehr viel Aufwand betrieben werden, um nach diesem Datenmüll zu sortieren. Um hier eine deutliche Beschleunigung der Verarbeitung zu erreichen, wurde ein eigener Modus für die Stringsortierung eingeführt, der für Strings bis 255 Byte Länge geeignet ist.

Hierfür wird ein weiteres Register eingeführt, in dem die Verweise auf die Datensätze entsprechend der Länge der Strings zu Beginn der Sortierung gespeichert werden. Vor dem Auslesen aus einem Register wird geprüft, ob es Datensätze gibt, wo der String so lang ist, dass jetzt nach seinem letzten Zeichen sortiert werden würde. Durch dieses Vorgehen wird die Stabilität des Verfahrens bewahrt, denn es verhält sich so, als ob alle Bytes hinter dem Nullbyte gleichfalls den Wert Null gehabt hätten, also immer in der gleichen Reihenfolge im Eimer Null gelandet wären.

Ist die Größe des Bereiches zur Speicherung von Strings beispielsweise 24 + 1 Byte lang, der durchschnittliche String aber nur sechs Byte lang, ergibt sich folgende Situation: würden die Strings wie Bytesequenzen sortiert, würde 75% der Rechenleistung dafür verwendet werden, um nach Datenschrott zu sortieren. In der Variante für Strings hat man einen Sortiervorgang, um nach Stringlänge zu sortieren und anschliessend nur den Aufwand, als hätten alle Strings die Durchschnittslänge.

Ein praktischer Nebeneffekt ergibt sich dadurch, dass das Leerzeichen in der ASCII-Tabelle vor den Ziffern und Buchstaben steht. Werden nämlich Strings mit Wortfolgen sortiert, steht „Der artige“ vor „Derartige“, was der normalen lexikalischen Betrachtung entspricht.

Da in der ASCII-Tabelle die Kleinbuchstaben erst hinter dem Block der Großbuchstaben stehen, wird das Sortierergebnis nicht den Erwartungen entsprechen, insbesondere da Umlaute erst hinter dem Block der Kleinbuchstaben stehen. Für eine lexikalische Sortierung ist es erforderlich eine eindeutige Umsetzungstabelle zu definieren, alle Zeichen in den Schlüsseln über diese Tabelle zu ersetzen, die Sortierung durchzuführen und abschliessend die Vertauschung der Zeichen rückgängig zu machen.

Sortierung nach Gleitkommazahlen

Nach IEEE P754 wird eine 32-Bit-Gleitkommazahl folgendermaßen aufgebaut:

  MMMMMMMM MMMMMMMM MMMMMMME EEEEEEEV 
 +--------+--------+--------+--------+
  0        8        16       24     31

wobei M für die Mantisse steht, E für den Exponenten und V für das Vorzeichen der Zahl. Eine 64-Bit-Gleitkommazahl stellt sich folgendermaßen dar:

  MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMMMMM MMMMEEEE EEEEEEEV 
 +--------+--------+--------+--------+--------+--------+--------+--------+
  0        8        16       24       32       40       48       56     63

Bei der Sortierung von Integerwerten war es so, dass das Vorzeichen nur bei der Abhandlung des höchstwertigen Bytes berücksichtigt werden mußte. Aufgrund der internen Darstellung von Gleitkommazahlen ist es hier erforderlich, das Vorzeichen bei der Behandlung von jedem einzelnen Byte zu berücksichtigen.

Allerdings ist es nicht notwendig zu unterscheiden, ob ein Bit zur Mantisse gehört oder zum Exponenten, denn die Gleitkommazahl ist in der binären Darstellung normalisiert; bei Dezimalzahlen wäre das Äquivalent, dass die Kommaposition solange verschoben wird, bis man eine Darstellung der Form 0,xxxx * 10^yy erhält. Man kann sich diesen Sachverhalt gut dadurch veranschaulichen, dass RadixSort stabil sortiert und auch bitweise angewendet werden könnte. Jedes zu behandelnde Bit hätte eine höhere Wertigkeit als das vorhergehende, wobei es egal ist, ob das Bit zur Mantisse gehört oder zum Exponenten. Die einzige Ausnahme bildet mal wieder das Vorzeichenbit. Normalerweise ist eine binäre 1 größer als eine binäre 0, doch hier ist es anders herum, weshalb das Byte mit dem Vorzeichen zweimal behandelt werden muss.

Gleitkommazahlen einfacher Genauigkeit

Zunächst wird nach allen vier Bytes sortiert, wobei jedes mal auch das Vorzeichenbit berücksichtigt wird; ist es gesetzt, wird die Eimernummerierung für diesen Schlüssel invertiert. Dass beim vierten Byte das Vorzeichenbit in die Sortierung eingeht, kann ignoriert werden. Abschliessend erfolgt noch die Sortierung nach dem Vorzeichen. Für die Sortierung von 32-Bit-Gleitkommazahlen sind also 5 Sortierdurchgänge notwendig.

Gleitkommazahlen doppelter Genauigkeit

Zunächst wird nach allen acht Bytes sortiert, wobei jedes mal auch das Vorzeichenbit berücksichtigt wird; ist es gesetzt, wird die Eimernummerierung für diesen Schlüssel invertiert. Dass beim achten Byte das Vorzeichenbit in die Sortierung eingeht, kann ignoriert werden. Abschliessend erfolgt noch die Sortierung nach dem Vorzeichen. Für die Sortierung von 32-Bit-Gleitkommazahlen sind also 9 Sortierdurchgänge notwendig.

Speicherplatzbedarf

Für die Sortierung werden zwei FIFO-Verwaltungen benötigt. Jede FIFO-Verwaltung hat 256 Einträge, die jeweils aus zwei Integerzahlen bestehen, nämlich das erste Element des FIFO's und das letzte Element. Eine normale Integerzahl hat 4 Bytes, also benötigt eine FIFO-Verwaltung 2 kBytes. Für beide FIFO-Verwalungen werden insgesamt 4 kByte benötigt, egal wieviele Datensätze sortiert werden sollen.

Jeder FIFO-Eintrag besteht aus der Originalposition des Datensatzes und der Verkettung zum nächsten Element des gleichen FIFO. Ein einzelner Eintrag hat 8 Bytes; da zwei FIFO-Register verwaltet werden, ergibt sich der dynamisch benötigte Speicherplatz bei n Datensätzen zu S = n * 8.

Soll die Sortierung nicht in ein Zielarray hinein erfolgen, sondern innerhalb des Arrays, werden zwei Hilfarrays der Länge n benötigt, in denen gespeichert wird, wohin ein Datensatz umkopiert wurde, als sein Speicherplatz zum Schreiben des Ergebnisses benötigt wurde.

Zusammenfassend kann man sagen, dass der zusätzliche Speicherplatzbedarf mit maximal

 S = 4kByte + 24 * n 

recht moderat ausfällt.

Verarbeitungsgeschwindigkeit

Unabhängig vom Datentyp des Sortierschlüssel gilt, dass jedes Byte vom Sortierschlüssel eines jeden Datensatzes nur ein einziges mal betrachtet wird; enthält ein Schlüsselbyte ein Vorzeichen, einen Teil der Mantisse oder einen Teil des Exponenten, so wird dieses Byte für jeden dieser Aspekte einmal behandelt. Beim Eintragen in ein FIFO und beim Auslesen wird jeweils eine if-Abfrage gemacht sowie einige triviale Berechnungen. Da zudem indirekt sortiert wird, ergibt sich eine sehr hohe Geschwindigkeit. Sollte es irgendwann möglich sein, einen Algorithmus zu entwickeln, der mit weniger Rechenschritten auskommt, so wird der Unterschied der Geschwindigkeiten nur minimal sein können.

Aus dem Ablauf des Algorithmus ergibt sich zudem, dass der zeitliche Aufwand für eine Sortierung völlig unabhängig von einer Vorsortierung ist. Es gibt also weder einen Worts-Case noch einen Best-Case und bei der Sortierung nach einem bestimmten Datentyp dauert die Abarbeitung von jedem Schlüssel exakt gleich lange.

Bei jedem Sortierdurchgang müssen die 256 FIFOs des aktuellen Registers zurück gesetzt werden und am Ende des Sortierdurchgangs müssen die 256 FIFOs des aktuellen Registers ausgelesen werden. Dieser Aufwand muss unabhängig von der Anzahl der zu sortierenden Datensätze betrieben werden. In der graphischen Darstellung macht sich dieser Overhead als Sockel bemerkbar, also die Minimalzeit, die ExtraDix benötigt.

Um einen Vergleich mit Quicksort durchführen zu können wurde eine Datei mit einer Million Datensätzen erzeugt; die Datensätze hatten eine Länge von 54 Byte und enthielten quasi zufällige Daten in den gängigen Grundtypen. Als Testrechner wurde ein PC mit 1,8 GHz verwendet und die Tabelle mit den Testdaten wurde vor jedem Sortiervorgang in den Arbeitsspeicher geladen. Die für den Vergleich verwendeten Programme stehen gleichfalls zum Download bereit.

Die Implementierung von Quicksort wurde entsprechend diesem Pseudocode in C realisiert. Da die Sortierzeit bei Quicksort von einer Vorsortierung abhängt, haben diese Kurven keinen gleichförmigen Verlauf; Ausreisser wurden gelöscht und zugunsten von Quicksort interpoliert. Da die benötigte Zeit bei ExtraDix linear mit der Anzahl ansteigt und bei Quicksort mit n*ln(n), wird der zeitliche Vorteil von ExtraDix bei steigenden Anzahlen immer größer.

Es bleibt noch die Frage zu beantworten, ab welcher Anzahl von Datensätzen der Einsatz von ExtraDix lohnend erscheint. Für die beiden folgenden Diagramme wurden in Hunderter-Schritten bis zu 2.000 Datensätze sortiert und die Zeiten in Mikrosekunden gemessen. Schon ab ein paar hundert Datensätzen spielt der Überhang, der für die FIFO-Verwaltung notwendig ist, keine wesentliche Rolle mehr.

Aufruf der ExtraDix Funktion

Die Sortierfunktion ExtraDix ist reentrant-fähig. Sie hat nur einen Aufruf-Parameter und zwar einem Zeiger auf eine Struktur des Typs ED_SortInfo.

struct ED_SortInfo
  {
  int   SortOrder;                      // Sortierrichtung
  int   ColType;                        // Typ des Schlüssels
  int   ColStart;                       // Byteposition, wo der Schlüssel beginnt
  int   ColWidth;                       // Breite des Schlüssels
  int   NumLines;                       // Anzahl der zu sortierenden Datensätze
  int   LineSize;                       // Länge eines Datensatzes
  void* Source;                         // Zeiger auf die Eingabedatensätze
  void* Dest;                           // Zeiger auf Speicherplatz für das Ergebnis
  }

Wird ExtraDix etwa Teil einer dynamischen Library, dann wird der Sourcecode übersetzt, bevor bekannt sein kann, wie die zu sortierenden Datensätze aufgebaut sind. Der Aufruf mußte also so gestaltet werden, dass er für jede Sortieraufgabe geeignet ist.

Die zu sortierenden Daten befinden sich im Arbeitsspeicher an der durch Source angegeben Position. Da Datensätze im Allgemeinen eigene Struktur-Definitionen haben, die ExtraDix natürlich nicht kennen kann, wird als neutrale Lösung ein Zeiger vom Typ 'void' verwendet. Jeder Datensatz hat die Länge LineSize und es sind insgesamt NumLines Zeilen, die sortiert werden sollen. Man kann also auch Teilbereiche von Arrays sortieren!

Da sich ExtraDix nicht um die Inhalte der Datensätze kümmert, genügt es zu wissen, wo sich der Sortierschlüssel innerhalb des Datensatzes befindet und mit welcher Variante des Algorithmus gearbeitet werden soll. Die Variante wird mittels ColType ausgewählt. Als Typen sind Strings möglich, vorzeichenlose ganze Zahlen, vorzeichenbehaftete ganze Zahlen und Gleitkomma-Zahlen mit zwei verschiedenen Genauigkeiten. Da sich auf verschiedenen Rechnern, Compilern und Programmiersprachen die Interpretationen unterscheiden, muss zusätzlich angegeben werden, an welcher Stelle im Datensatz der Schlüssel beginnt und wieviele Bytes der Schlüssel umfasst.

Über SortOrder, das die Werte ED_ASCEND oder ED_DESCEND annehmen kann, wird eingestellt, ob das kleinste Element am Anfang der Ergebnisliste stehen soll oder ob absteigend sortiert werden soll.

Die letzte Komponente in der Struktur ist Dest, der Zeiger auf die Position im Arbeitsspeicher wo das Ergebnis gespeichert werden soll. Hat dieser Zeiger den Inhalt NULL, dann werden die Datensätze innerhalb der Eingabedaten umgestellt. Hat Dest einen hiervon abweichenden Wert, wird das Ergebnis ab der angegebenen Adresse abgespeichert. Es liegt in der Verantwortung des Nutzers, dass hierdurch keine Konflikte entstehen.

Die Angaben, wo sich der Schlüssel innerhalb des Datensatzes befindet, sind etwas kompliziert. Der Grund hierfür ist, dass die Prozessoren nicht jeden Datentyp an beliebiger Adresse erlauben. Beispielsweise müssen Integerwerte mit vier Byte Länge immer an einer Adresse anfangen, die ohne Rest durch vier teilbar ist; liegt die Adresse an einer anderen Stelle, wird das Programm abgebrochen. Damit dies nicht passiert, fügt der Compiler Füllbytes in den Strukturen ein und jeder Compiler macht dies gegebenenfalls anders. Dieses Einfügen von Bytes wird Padding genannt. Damit Programme, die ExtraDix nutzen, ohne Änderungen auf unterschiedlichen Platformen laufen können, sollte man die Komponenten der Struktur soweit möglich vom Compiler bestimmen lassen. Beispiele hierfür finden sich in der Testsuite, die zum Download bereit liegt.

duale Lizenz

Die Wirkungsweise des Algorithmus wurde mittels Pseudocode beschrieben und in ein C-Programm umgesetzt. Beides wurde unter die GNU General Public License gestellt. Möchte jemand ExtraDix nutzen und auch an Dritte weiter geben, ohne sein eigenes Programm unter die GPL zu stellen, so kann er mit dem Autor einen individuellen Lizenzvertrag abschliessen.

So, wie der Autor eines Romanes sein geistiges Eigentum nicht dadurch verliert, dass jemand sein Werk kopiert, den Darstellern andere Namen gibt oder das Werk in eine andere Sprache übersetzt, so wird auch das geistige Eigentum an diesem Code von ExtraDix betrachtet: Jede Übersetzung des Pseudocodes in eine natürliche Sprache oder in eine Programmiersprache, inklusive ihrer Kompilate, muss selbst wieder unter die GPL gestellt werden.

Werden Programme mit ExtraDix verbunden, durch Einbindung von Quelltext, Verlinkung mittels einer statischen oder dynamischen Library oder durch Einsatz in einem Server-Prozess oder einem Betriebssystem, die die Funktionalität von ExtraDix zur Verfügung stellen, so muß dieses Programm gleichfalls unter die GPL gestellt werden, falls Kopien an Dritte weiter gegeben werden.