DE69527331T2

DE69527331T2 - Datenwiedererfindungssystem, Datenverarbeitungssystem, Datenwiedererfindungsverfahren und Datenverarbeitungsverfahren

Info

Publication number: DE69527331T2
Application number: DE69527331T
Authority: DE
Inventors: Mutsumi Fujihara
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 1994-09-13
Filing date: 1995-09-13
Publication date: 2003-02-27
Anticipated expiration: 2015-09-14
Also published as: DE69527331D1; EP0702310A1; US5778371A; EP0702310B1

Description

Hintergrund der Erfindung

1. Gebiet der Erfindung

Diese Erfindung behandelt Datenverarbeitungssysteme und Datenverarbeitungsverfahren, welche Daten einer Codekette (code string) verarbeiten, um alle Vorkommnisse einer spezifizierten Schlüsselkette in der Codekette aufzufinden. Im einzelnen betrifft die Erfindung solche Datenverarbeitungssysteme und -verfahren, welche einen Binärstrukturbaum zur Darstellung von Daten der Codekette verwenden.

2. Beschreibung des Standes der Technik

Datensuchsysteme und Datensuchverfahren wurden vordem entwickelt, um alle Positionen des Auftretens einer spezifizierten Schlüsselkette (Muster) in einer Codekette, wie etwa eine Schriftzeichenkette, aufzufinden. Fig. 55 zeigt das Muster p, welches in der Schriftzeichenkette s aufgefunden wurde. Eine Codeketten-Suchtechnik kann bei Wörterbüchern und Verzeichnissen angewandt werden; im einzelnen wird sie zum Mustervergleich bei einem Texteditor, bei einer Textdatenbank und bei der Spracherkennung, zur Musteranalyse in Anwendungsfeldern, wie DNA-Untersuchungen oder zur Austauschcodierung verwendet.
Das einfachste Codeketten-Suchverfahren beruht darauf, eine Schlüsselkette von Anfang bis zum Ende mit einer Codekette zu vergleichen. Jedoch nimmt die Suchzeit bei dieser Verfahren zu, wenn die Schriftzeichenkette s länger wird.
Um von Beginn an bei größer werdender Schriftzeichenkette s das Anwachsen der Suchzeit zu verhindern, während ein Anwachsen der Zeit bei Zunahme der Trefferhäufigkeit des Musters p geduldet wurde, wurden speziell zur Suche strukturierte Daten verwendet, die basierend auf der eindimensionalen Schriftzeichenkette s erzeugt wurden. Ein Positionsbaum (Majster, M. et. al. 1980), ein Suffix-Baum (McCreght, E. 1976, Chang und Lauher, "Approximte String Matching in Autlinear Expected Time", Proceedings of the anual symposiums on foundations of Computer Scie, St. Louis; 1990), und direkte azyklische Wortgraphen (Blumer, A. et. al. 1985) sind als spezielle für die Datensuche strukturierte Strukturen bekannt.
Der Vorteil diese Datenstrukturen liegt darin, dass (1) kein sehr großer Speicherbereich erforderlich ist; der Speicherbereich ist in etwa proportional zur Länge der Codekette s und (2) keine sehr lange Suchzeit ist erforderlich; die Zeit ist in etwa proportional zur Länge der Schlüsselkette (Muster p) und zur Trefferhäufigkeit.
Im Grunde genommen basieren die Datenstrukturen auf einem Trie (digitaler Suchschlüssel). Wie in Fig. 56 gezeigt, ist ein Trie ein Datenstrukturbaum, bestehend aus einem Hauptverzeichnis, einer Vielzahl von Knotenpunkten und Enden und einer Sequenz von Kennzeichen (Label), welche jedem Rand zwischen jeweils zwei Knotenpunkten von dem Hauptverzeichnis (Stamm) zu einem Endknotenpunkt (Ast) beigefügt sind und die Schriftzeichenkette beschreiben. In dieser Datenstruktur entspricht ein Ast einer Schriftzeichenkette wi (eine komplette Schriftzeichenkette). Zusätzlich wird eine Schriftzeichenkette, die mittels der Kennzeichen auf dem Pfad von dem Hauptverzeichnis zu einem Knotenpunkt x erzeugt wird, als ein Präfix (eine führende Sub-Zeichenkette) einer über die Kennzeichen von dem Hauptverzeichnis zu dem Astknoten erzeugten Schriftzeichenkette betrachtet.
Datenstrukturen, welche zur Datensuche eingesetzt wurden, wie etwa ein Positionsbaum, ein Suffix-Baum oder direkte azyklische Wortgraphen, basieren auf dem oben beschriebenen Trie.
Ein Positionsbaum als eines der Datenstrukturen ist ein Trie, der Subketten-Kennungen (substring identifier) als Schriftzeichenketten verwendet, wobei jede an jeder sequentiellen Position der Codekette s startet. Ein Subketten- Kennung ist als die kleinst möglichste eindeutige Schriftzeichenkette definiert, die an jeder sequentiellen Position startet. Fig. 57 zeigt ein Beispiel einer Tabelle (Lexikon), in welcher Positionen und Subketten-Kennungen für die Codekette "abbabb$" enthalten sind. In dieser Figur stellt das Symbol $ eine Codeattrappe (dummy code) dar, welche zur Identifizierung der Position an das Ende der Codekette hinzugefügt wurde. Fig. 58 zeigt ein Beispiel eines Positionsbaumes, welcher die Dateiliste für die Codekette "abbabb$" darstellt.
Ein Suffix-Baum ist ein Trie, welcher ein Suffix (eine nacheilende Subkette) der Codekette s als die Schriftzeichenkette wi verwendet. Fig. 59 zeigt ein Beispiel eines Suffix-Baumes. Ein Suffix-Baun stellt die einfachste Form eines Tries dar. Dieses zeigt sich darin, dass der Suffix-Baum eine Baumstruktur T darstellt, in welcher die Kennzeichen, die einem Pfad von dem Hauptverzeichnis zu einem Ast (Endknotenpunkt) beigefügt sind, ein Suffix der Codekette s erzeugen. In einem Suffix-Baum entspricht ein Astknotenpunt dem Ende eines Suffix (Ende von s). Die Baumstruktur T weist alle Kombinationen von Pfaden vom Hauptverzeichnis zu einem Astknoten auf und schließt alle erzeugten Suffixe ein. Ein Pfad von dem Hauptverzeichnis zu einem Astknoten über den Knotenpunkt x entspricht einem Suffix der Codekette s mit einer Schriftzeichenkette, die von dem Hauptverzeichnis zu dem Knotenpunkt x als ein Präfix erzeugt wurde.
Ein direkter azyklischer Wortgraph ist ein Graph, der durch das Zusammenlegen einzelner Pfade eines Suffix-Baumes erstellt wurde. Fig. 60 zeigt ein Beispiel eines direkten azyklischen Wortgraphen.
Wenn jedoch die Codekette s in einer herkömmlichen Datenstruktur aktualisiert wird, wächst die erforderliche Zeit zum Aktualisieren der Suchdaten mit dem Anwachsen der Länge der Codekette s an. In einem Suffix-Baum beispielsweise gibt ein Trie alle die Suffixe der Codekette s wieder. Falls lediglich ein Teil der Codekette s abgeändert wird, sind von daher alle Suffixe vor dem abgeänderten Schriftzeichen getroffen und somit der gesamte Trie beeinflusst. Dieses ist umso markanter, je näher das abgeänderte Schriftzeichen an dem Ende der Codekette s liegt.
Wenn beispielsweise das letzte Schriftzeichen "c" der Codekette s in Fig. 59 gelöscht wird, werden drei Grenzen (c) gelöscht und die Kennzeichen an zwei Grenzen (abc) abgeändert. Von daher ist ein herkömmliches Datensuchsystem und ein Datensuchverfahren, welches eine lange Zeit zum Aktualisieren der Daten benötigt, bei Anwendungen nicht geeignet, wo Zeichenketten häufig aktualisiert werden müssen.
Ein weiteres bekanntes Verfahren besteht darin, eine Codekette in eine Vielzahl von Subketten zu zerteilen und für jeweils eine der Subketten einen individuellen Trie zu erzeugen. Jedoch gibt es bei diesem Verfahren zwei Probleme. Ein Problem besteht darin, dass, wenn ein Teil der Codekette, welches einer Schlüsselkette entspricht, zerteilt wird und wenn die erste Hälfte zu einem ersten Trie und die hintere Hälfte zu einem anderen Trie gehört, ist es unmöglich, mittels der Schlüsselkette nach diesem Teil der Codekette zu suchen.
Ein anderes Problem besteht darin, dass bei einer Subkette mit variabler Länge eine Datenverarbeitung, wie etwa Editieren oder Suchen, nicht effizient betrieben werden kann. Beispielsweise verändert sich beim Editieren eine Subkette und variiert in der Länge. Somit ist es bei der Bearbeitung einer Subkette immer notwendig, eine Subkette mit einer bestimmten Position innerhalb der Codekette anzupassen.
Eine Subkette ist schwierig zu verarbeiten, dies gilt nicht nur bei der Suche von Daten, sondern auch für viele andere Felder der Datenverarbeitung, wie etwa für die Datenkompression oder für das Editieren von Schriftzeichenketten. Das Editieren von Schriftzeichenketten (Sätze) ist ein Beispiel für eine Datenverarbeitung von Subketten.
Bei der Verarbeitung von Datenketten an einem Computer ist es notwendig, einen Datenwert in einer Datenzeichenkette gegenüber der Position innerhalb der Datenzeichenkette, wo der Datenwert gespeichert ist, auf Gleichheit, zu prüfen. Im einzelnen ist es notwendig, während des Editierens der Schriftzeichenkette einen Code zu erhalten, der an einer bestimmten Position in einer Schriftzeichenkette liegt; um beispielsweise das hunderste Schriftzeichen von einer Schriftzeichenkette aufzufinden. Andererseits kann die Position von einem einzelnen Code während des Editierens variieren. Zum Beispiel wächst beim Hinzufügen von 10 Schriftzeichen am Beginn einer Schriftzeichenkette die Position eines nachfolgenden Schriftzeichen innerhalb der Schriftzeichenkette um 10 (Schriftzeichen) an.
Die Position eines Datengegenstandes in einer Datenzeichenkette ist nicht immer diskret; es liegt nicht immer die "n-te Position", wie in der obigen Schriftzeichenkette, vor; in vielen Fällen wird ein Intervall verwendet, das mittels einer reellen Zahl im Gleitkomma-Format (flaoting-point-format) dargestellt wird, um einen Bereich eines Datenwertes zu spezifizieren. Beispielsweise wird der Wert eines Signals von einem Schaltkreis durch L (niedrig), H (hoch) und F (gleitend = floating, nicht definiert) dargestellt. Bei der Verarbeitung dieser Werte, beispielsweise in einer Simulation im Zeitreihenzustand (time-series mode), ist es üblich, die Verweilzeit eines Signalwertes als einen reellen Wert zu behandeln und diesen auf einem Computer als einen Gleitkomma-Wert zu behandeln. Bei diesem Anwendungstyp erfolgt das Editieren wie bei einer Schriftzeichenkette. Zusätzlich ist es notwendig, schnell auf Anfragen zu reagieren, wie etwa: Was ist der Datenwert bei einem bestimmten Zeitpunkt, wie lange dauert ein Wert bei einem bestimmten Punkt an, bei welchem Zeitpunkt beginnt ein Datenwert und ob sich ein Datenwert zwischen zwei Zeitpunkten verändert und wie oft, oder ob nicht.
Im folgenden wird unter der Verwendung eines einfachen Beispiels dargestellt, wie schwierig es ist, eine Subkette effizient zu bearbeiten. In diesem Beispiel sei angenommen, dass eine Codekette Schriftzeichen beinhaltet, dessen Werte 0, 1 oder N sind und dass in den meisten Fällen die gleichen Code-Werte kontinuierlich auftreten. Diese Art von Zeichenkette tritt häufig in graphischen Displays auf. Das folgende ist ein Beispiel für diesen Codetyp: [Tabelle 1]
In diesem Beispiel ist 0 in dem Intervall [1..3], n in dem Intervall [4..5], 0 in dem Intervall [6..9], 1 in dem Intervall [10..15] und 0 in dem Intervall [16..16] gespeichert. In diesem Beispiel sei gedacht, dass eine Codekette in eine Sequenz von Codeketten desselben Wertes, d. h. in Intervalle, geteilt wird.
Um diese Daten an einem Computer zu verarbeiten, sieht das direkte Verfahren vor, die Code-Werte sequentiell in aufeinanderfolgende Adressen in einem Speicher abzulegen (erstes Verfahren). Fig. 61 zeigt, wie die Codekette in Tabelle 1 mit dem ersten Verfahren dargestellt wird. In dem ersten Verfahren ist die Position eines jeden Code-Wertes proportional zur Differenz zwischen der Speicheradresse, unter welcher der Code-Wert gespeichert ist, und der Startadresse der Speicherung, wo die Codekette gespeichert ist. Dieses ermöglicht es, die Adresse eines einzelnen Code-Wertes mittels gewöhnlicher Berechnung (Addieren, Subtrahieren, Multiplizieren und Teilen) zu identifizieren.
Das heißt, falls die Startadresse der Speicherung, wo die Codekette gespeichert ist, A ist, dann wird die Adresse des Code-Wertes wie folgt berechnet:

[Formel 1]

Adresse = Position + A - 1
Jedoch weist dieses Verfahren die folgende Probleme auf:
1. Die Daten belegen so viele Speicherzellen, wie Code-Werte vorhanden sind, was die Speichereffizienz herabsetzt. Im einzelnen wird Speicherplatz vergeudet, wenn viele Codes des gleichen Wertes vorhanden sind.
2. Da die Daten mittels mehrfachen Codes (plural codes) gespeichert sind, dauert es lange, einen Bereich von aufeinanderfolgenden Codes des gleichen Wertes zu ermitteln. Das heißt, um einen Bereich von aufeinanderfolgenden Codes des gleichen Wertes zu identifizieren, ist es notwendig, die Code- Werte, jeweils einen pro Zeit, zu lesen und die Anzahl der Code-Wert abzuzählen.
3. Ein Abändern der Länge einer Subkette aufgrund eines Einfügens oder Entfernens bewirkt, dass die Adressen aller Daten, die nach dem Punkt des Einfügens oder Entfernens folgen, vergrößert oder verkleinert werden müssen. Dieses ist ein zeitaufwendiger Prozeß. Beispielsweise zeigt Fig. 62 ein Beispiel, in welchem ein Intervall des Code-Wertes 1 [6..8] unmittelbar hinter dem Code-Wert N an der Position 5 (Adresse A + 4) eingefügt wird. Dieses Einfügen zieht eine Reihe von Arbeitsschritten nach sich; die Daten an den Adressen A + 5 bis A + 15 müssen nämlich zu den Adressen A + 8 bis A + 18 bewegt werden.
4. Weil ein Speicherbereich notwendig ist, der groß genug ist, um die Anzahl der Code-Werte (d. h. die Anzahl der Positionen) zu umfassen, wobei jeder Code-Wert aus einer spezifizierten Anzahl von Bits (Code-Einheit; code unit) besteht, begrenzt ein begrenzter Speicherbereich die Menge der Informationen, die jede Code-Einheit enthalten kann. Falls es jeder Code-Einheit gestattet ist, den Maximalwert an Informationen darzustellen, ist eine ungeheure Menge von Speicherplatz erforderlich. Dieses resultiert in weniger Positionen und in einer gröberen Positionseinteilung (weniger Präzision). Umgekehrt erhöht die geringere Positionseinteilung die Anzahl der Positionen, was eine ungeheure Menge von Speicherplatz erfordert. Von daher können in der Praxis nur diskrete Längen (Positionen), wie etwa Zahlen, dargestellt werden.
Ein anderes Verfahren beruht darauf, Paare in einem aufeinanderfolgenden Speicherbereich in der Reihenfolge, in welcher die Subketten auftreten, abzuspeichern, wobei jedes Paar aus einem Code-Wert und einem Bereich einer Subkette, wo dieser Code aufeinanderfolgend auftritt, besteht (zweites Verfahren). Fig. 63 zeigt die Codekette von Tabelle 1, welche mittels des zweiten Verfahrens abgespeichert ist.
Bei dem zweiten Verfahren hängt der Speicherplatzbedarf von der Anzahl der aufeinanderfolgenden Code-Wertintervalle ab. Das bedeutet, dass es nicht von der Anzahl der Positionen sondern von der Anzahl der Intervalle abhängig ist, was die Speichereffizienz erhöht. Ein kontinuierlicher Bereich von Code-Werten kann durch Daten identifiziert werden. Zusätzlich sind breitere Variationen in der Längenpräzision (Längentyp = diskret oder kontinuierlich) gestattet. Beispielsweise können Gleitkomma-Zahlen einfacher verarbeitet werden.
Wenn die Länge einer Subkette (Intervall) oder die Anzahl der Subketten abgeändert wird, ist es außerdem bei diesem Verfahren notwendig, alle Subkettendaten zu überschreiben, welche der abgeänderten Position folgen. Darüber hinaus ist es zur Identifizierung des Code-Wertes einer einzelnen Position notwendig, den zugehörigen Bereich für diese Position des Wertes, beispielsweise unter Verwendung des binären Suchverfahren, zu suchen.
Ein binärer Suchbaum wird gewöhnlich beim binären Suchverfahren verwendet. Bei diesem Verfahren wird eine Subkette in der Mitte einer Codekette als den Hauptverzeichnisknotenpunkt verwendet. Jeder Knotenpunkt bezeichnet sowohl einen Subkettendatenbereich als auch den Code-Wert der Subkette. Subkettendaten können durch den Startpunkt und den Endpunkt des Bereiches oder nur durch den Startpunkt des Bereiches dargestellt werden, wobei hier der Endpunkt anhand des Startpunktes der nächsten Subkette ermittelt wird. Fig. 64 zeigt ein Beispiel eines Sub-Baumes, der den Daten in Tabelle 1 entspricht. In dieser Figur ist jedem Knotenpunkt der Startpunkt der zugehörigen Subkette (in dem Kreis) und der Codewert der Subkette (unterhalb des Kreises) zugewiesen.
In einem Subbaum, bestehend aus Knotenpunkten, die an dem Ende liegen, entspricht ein Knotenpunkt dieser (zum Beispiel der Knotenpunkt links) der Subkette, die dem oben beschriebenen Knotenpunkt vorausgeht, und der rechte Subbaum entspricht der Subkette, die dem oben beschriebenen Knotenpunkt nachfolgt. Wenn die Position einer Subkette s abgeändert wird, ist es in diesem Fall abermals notwendig, alle Daten abzuändern, die nach dem Abänderungspunkt folgen.
Ferner ist es möglich, Paare in einem aufeinanderfolgenden Speicherbereich in der Reihenfolge, in welcher die Subketten erscheinen, zu speichern, wobei sich jedes Paar aus einem Code-Wert und der Länge der Teilkette, in dem dieser Code aufeinanderfolgend erscheint, zusammensetzt (drittes Verfahren). Fig. 65 zeigt ein Beispiel für Daten, welche mittels des herkömmlichen dritten Verfahrens gespeichert sind. Ein Vorteil dieses Verfahrens besteht darin, dass zum Vergrößern oder Verkleinern einer Teilkette lediglich die Länge von dem Intervall der vergrößerten oder verkleinerten Teilkette abgeändert werden muss. Ein Nachteil dieses Verfahren besteht darin, dass zum Erlangen des Codes an einer bestimmten Position die Längen der Intervalle von dem Startpunkt oder dem Endpunkt dieser zugehörigen Position aufaddiert werden müssen. Zusätzlich kann nicht das binäre Suchverfahren verwendet werden, da die Information über ein bestimmtes Intervall lediglich die Auskunft über die Länge des Intervalls liefert.
Eine lineare Aufstellung kann anstelle der Verwendung eines aufeinanderfolgenden Bereiches benutzt werden; dies ermöglicht es, nicht aufeinanderfolgende Bereiche durch Zeiger zu verbinden (viertes Verfahren). Fig. 66 zeigt eine Datenstruktur, die in dem vierten Verfahren dargestellt ist.
Die vierte Verfahren beseitigt die Notwendigkeit des Übertragens von Daten in einen Speicher, wenn ein einzelnes oder mehrere Intervalle hinzugefügt, gelöscht, geteilt oder zusammengelegt werden. Zum Lokalisieren einer bestimmten Position erfordert dieses Verfahren es jedoch immer noch, die Längen von Intervalle aufzuaddieren.
In Abschnitt 1-2-4-8 der vorliegenden Beschreibung wird im folgenden eine aus dem Stand der Technik bekanntes und in der US-Patentschrift Nr. 5,384,568 offenbartes Verfahren in Bezugnahme auf die vorliegende Erfindung detailliert beschrieben.
Diese Erfindung strebt danach, die Probleme des obig beschriebenen Standes der Technik zu lösen.
Dementsprechend ist es eine Aufgabe dieser Erfindung, ein Datenverarbeitungssystem und ein Datenverarbeitungsverfahren vorzuschlagen, welches. Daten effizient verarbeitet. Dieses Datenverarbeitungssystem und Datenverarbeitungsverfahren sind im einzelnen dazu geeignet, die obig beschriebenen Datensuchsysteme und Datensuchverfahren zu implementieren. Im einzelnen liegt eine weitere Aufgabe dieser Erfindung darin, ein Datenverarbeitungssystem und ein Datenverarbeitungsverfahren vorzuschlagen, welches ein einfaches Aktualisieren von Daten erlaubt. Eine weitere Aufgabe dieser Erfindung liegt darin, ein Datenverarbeitungssystem und ein Datenverarbeitungsverfahren vorzuschlagen, welches den Speicherplatz effizient nutzt.

Zusammenfassung der Erfindung

Die obige Aufgabe wird erfindungsgemäß durch den Patentanspruchs 1 gelöst, in dem ein Datenverarbeitungssystem vorgeschlagen wird zur Verarbeitung von Daten einer in eine Sequenz von Intervallen eingeteilten Codekette, in der zum Auffinden einer spezifizierten Position in der Codekette jedes Intervall eine durch die Anzahl der Code-Elemente in dem Intervall definierte Länge hat, wobei das Datenverarbeitungssystem eine Binärstrukturbaum- Erzeugungseinrichtung umfasst zum Erstellen eines binären Strukturbaumes, welcher eine Vielzahl von Knotenpunkte aufweist, die entsprechende Positionen der Intervalle in der. Codekette darstellen, wobei die Knotenpunkte jeweils einem der Intervalle der Codekette zugewiesen sind, und wobei die Knotenpunkte von einem Hauptverzeichnisknoten des Strukturbaumes zu Astknoten davon in einer baumartigen Struktur verbunden sind, und wobei jeder Knotenpunkt zwischen dem Hauptverzeichnisknoten und den Astknoten ein Hauptverzeichnisknoten eines Subbaumes darstellt und mit einem vorhergehenden Knotenpunkt verbunden ist, der als linker Ableger-Knotenpunkt (left-child node) definiert ist, welcher einem Intervall in der Codekette entspricht, das dem Intervall vorhergeht, welches dem genannten Knotenpunkt entspricht, und/oder mit einem nachfolgenden Knotenpunkt verbunden ist, der als rechter Ableger-Knotenpunkt (right-child node) definiert ist, welcher einem Intervall in der Codekette entspricht, das dem Intervall folgt, welches dem genannten Knotenpunkt entspricht, wobei das Datenverarbeitungssystem dadurch gekennzeichnet ist, dass jedem Knotenpunkt eine partielle Intervall-Länge zugewiesen wird, welche definiert ist als die Summe aus der Länge des Intervalls, das dem genannten Knotenpunkt entspricht, und den Intervallen, die - falls vorhanden - den Knotenpunkten an der Astseite des genannten Knotenpunktes entsprechen, eine Einrichtung (vorhanden ist) zum Identifizieren des Knotenpunktes, der dem Intervall entspricht, welches die spezifizierte Position enthält, durch eine vom Hauptverzeichnisknoten beginnende Verarbeitung der Knotenpunkte, wobei die Einrichtung folgendes umfasst: eine Einrichtung zum Selektieren des linken Ableger- Knotenpunktes des aktuellen Knotenpunktes als den nächstaktuellen Knotenpunkt, falls die spezifizierte Position geringer oder gleich der partiellen Intervall-Länge des linken Ableger-Knotenpunktes ist; eine Einrichtung zum Selektieren des rechten Ableger- Knotenpunktes als den nächstaktuellen Knotenpunkt und zum Aktualisieren der Darstellung der spezifizierten Position des rechten Ableger-Knotenpunktes relativ zum aktuellen Knotenpunkt, falls die spezifizierte Position größer ist als die partielle Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Intervall- Länge des rechten Ableger- Knotenpunktes; und eine Einrichtung zum Identifizieren, dass die spezifizierte Position in dem Intervall enthalten ist, welches dem aktuellen Knotenpunkt entspricht, falls die spezifizierte Position größer als die partielle Intervall-Länge des linken Ableger- Knotenpunktes und geringer als oder gleich der partiellen Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Länge des rechten Ableger- Knotenpunktes ist.
Die Erfindung des Patentanspruches 20 stellt eine verfahrenstechnische Umsetzung der Erfindung aus Patentanspruch 1 dar und ist ein Datenverarbeitungsverfahren zum Verarbeiten von Daten einer Codekette, die in eine Sequenz von Intervallen eingeteilt ist, wobei jedes Intervall eine über die Anzahl der Code-Elemente in dem Intervall definierte Länge aufweist, um eine spezifizierte Position in der Codekette aufzufinden, wobei das Datenverarbeitungsverfahren einen Binärstrukturbaum-Erzeugungsprozess zum Erzeugen eines Binärstrukturbaumes (31) umfasst, wobei der Binärstrukturbaum eine Vielzahl von Knotenpunkte aufweist, welche die jeweiligen Positionen der Intervalle in der Codekette entsprechen, wobei die Knotenpunkte zu jeweils einem der Intervalle in der Codekette zugeordnet sind; die Knotenpunkte von einem Hauptverzeichnisknoten des Baumes zu dessen Astknoten in einer baumartigen Struktur verbunden sind; jeder Knotenpunkt zwischen dem Hauptverzeichnisknoten und den Astknoten ein Hauptverzeichnisknoten eines Subbaumes darstellt und zu einem vorhergehenden Knotenpunkt verbunden ist, welcher als der linke Ableger-Knotenpunkt definiert ist, der einem Intervall in der Codekette entspricht, das dem Intervall vorhergeht, welches dem besagten Knotenpunkt entspricht, und/oder zu einem nachfolgenden Knotenpunkt verbunden ist, welcher als der rechte Ableger-Knotenpunkt definiert ist, der einem Intervall in der Codekette entspricht, das dem Intervall nachfolgt, welches dem besagten Knotenpunkt entspricht, wobei das Datenverarbeitungsverfahren dadurch gekennzeichnet, dass jeder Knotenpunkt einer partiellen Intervall-Länge zugeteilt ist, welche definiert ist als die Summe aus der Länge des Intervalls, das dem besagten Knotenpunkt entspricht, und den Längen der Intervalle, die den - falls vorhandenen - Knotenpunkten an der Astseite des besagten Knotenpunktes entsprechen; ein Identifizieren des Knotenpunktes, der dem Intervall entspricht und der die spezifizierte Position einschließt, durch eine wie folgt beschriebene Verarbeitung der Knotenpunkte beginnend von dem Hauptverzeichnisknoten: Selektieren des linken Ableger-Knotenpunktes des aktuellen Knotenpunktes als den nächstaktuellen Knotenpunkt, falls die spezifizierte Position weniger als oder gleich der partiellen Intervall-Länge des linken Ableger-Knotenpunktes ist; Selektieren des rechten Ableger-Knotenpunktes als den nächstaktuellen Knotenpunkt; Aktualisieren der Darstellung der spezifizierten Position gemäß der Position des rechten Ableger-Knotenpunktes relativ zu dem aktuellen Knotenpunkt, falls die spezifizierte Position größer als die partielle Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Intervall-Länge des rechten Ableger-Knotenpunktes ist; und Identifizieren, dass die spezifizierte Position in dem Intervall eingeschlossen ist, welches dem aktuellen Knotenpunkt entspricht, falls die spezifizierte Position größer als die partielle Intervall-Länge des linken Ableger- Knotenpunktes und weniger als oder gleich der partiellen Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Länge des rechten Ableger-Knotenpunktes ist.
Erfindungsgemäß, wie in den Patentansprüchen 1 und 20 beansprucht, kann die Position eines Knotenpunktintervalls innerhalb der Codekette während der Suchens oder einiger anderer Verarbeitungsvorgängen berechnet werden, basierend auf der Intervall-Länge des vorhergehenden (nachfolgenden) Knotenpunktes. Die Netz-Intervall-Länge eines Knotenpunktes kann durch die Subtraktion der Gesamtheit der Intervall-Längen der vorhergehenden und nachfolgenden Knotenpunkte von der partiellen Intervall-Länge des Knotenpunktes berechnet werden. Von daher kann das Code-Element bei einer spezifizierten Position innerhalb der Codekette einfach durch einen Vergleich der spezifizierten Position mit der Position und der Intervall-Länge eines jeden Knotenpunktes identifiziert werden.
Ferner kann die positionale Beziehung zwischen Knotenpunkten mittels der Beziehung zwischen den Knotenpunkten dargestellt und die Position eines jeden Knotenpunktes mittels der partiellen Intervall-Längen anderer Knotenpunkte berechnet werden. Dieses bedeutet, dass sich eine Abänderung in einem Teil eines Intervalls lediglich auf den abgeänderten Knotenpunkt und einem oder mehreren Knotenpunkten auf dem Pfad von diesem Knotenpunkt zu dem Hauptverzeichnis auswirkt, so dass die Abänderungsprozedur vereinfacht wird.
Erfindungsgemäß, wie in den Patentansprüchen 1 und 20 beansprucht, benötigt das System so viele Datenblöcke wie Intervalle, da ein Knotenpunkt für jedes Intervall vorgesehen ist, dadurch wird der Bedarf aufgehoben, so viele Speichereinheiten wie Knotenpunkte zu benötigen, wodurch die Speichernutzeffizienz vergrößert wird. Im einzelnen benötigt ein Binärstrukturbaum, in welchem Datenspeicherungsbereiche für die Knotenpunkte mittels Zeiger verbunden sind, keinen großen aufeinanderfolgenden Bereich, wodurch der Speicherplatz effizient genutzt wird. Die Fähigkeit, eine Präzision (precision) für jedes Intervall am besten geeignet zu nutzen, gestattet es dem Anwender, beliebige Typen von Intervalldaten, wie etwa Gleitkomma-Daten, zu benutzen.
Erfindungsgemäß, wie in den Ansprüchen 2 und 21 beansprucht, identifiziert die Intervall-Sucheinrichtung ein Intervall, in welchem eine spezifizierte Position enthalten ist, indem der aktuelle Knotenpunkt sequentiell von dem Hauptverzeichnis zu Knotenpunkten niedrigerer Ebene bewegt wird, jeweils eine Ebene pro Zeit, um den Bereich des aktuellen Knotenpunktes mit der spezifizierten Position zu vergleichen.
Die Erfindung von den Patentansprüchen 2 und 21 kann durch das Berechnen des Bereiches des aktuellen Knotenpunktes, basierend auf der Länge des nachfolgenden Knotenpunktes, symmetrisch angewandt werden.
Erfindungsgemäß, wie in den Patentansprüchen 3 und 22 beansprucht, wird die (Netz-)Intervall-Länge eines Knotenpunktes und die partielle Intervall-Länge des vorhergehenden Knotenpunktes oder des nachfolgenden Knotenpunktes des Knotenpunktes aufaddiert, wenn der aktuelle Knotenpunkt von dem spezifizierten Knotenpunkt zu dem Hauptverzeichnisknotenpunkt, ein Knotenpunkt pro Zeit, bewegt wird. Dieser Prozeß bestimmt die Position des spezifizierten Knotenpunktes durch die Intervall-Längen der Knotenpunkte, die zur Rechten oder Linken des spezifizierten Knotenpunktes in L- C-R-Ordnung vorliegen. Erfindungsgemäß, wie in den Patentansprüchen 3 und 22 beansprucht, erlaubt es diese einfache Prozedur, die Position des spezifizierten Knotenpunktes zu identifizieren, was es ermöglicht, verschiedene Arten von Verarbeitungen durchzuführen.
Erfindungsgemäß, wie in Patentanspruch 4 beansprucht, kann das Intervall des spezifizierten Knotenpunktes einfach identifiziert werden, wenn der spezifizierte Knotenpunkt zum Hauptverzeichnis wird und wenn das linke Ende des Intervalls für die gesamte binäre Baumstruktur 0 ist; d. h., die Anfangsposition ist die nachfolgende Position (+1) der partiellen Intervall-Länge des linken Ablegers des spezifizierten Knotenpunktes, und die abschließende Position ist die Position, welche durch die Subtraktion der partiellen Intervall-Länge des rechten Ablegers des spezifizierten Knotenpunktes von der partiellen Intervall-Länge des spezifizierten Knotenpunktes ermittelt wird.
Eine Erfindung gemäß Anspruch 5 ist ein Datenverarbeitungssystem gemäß Anspruch 1, welches ferner eine Binärstrukturbaum-Aktualisierungseinrichtung umfasst zum dem Inhalt der Abänderung entsprechenden Aktualisieren des Binärstrukturbaumes, wenn das Intervall abgeändert wird.
Die Erfindung von Patentanspruch 23 setzt die Erfindung von Patentanspruch 5 vom verfahrenstechnischen Standpunkt aus um und stellt ein Datenverarbeitungsverfahren gemäß den Ansprüchen 20, 21 oder 22 dar, welches ferner einen Binärstrukturbaum-Aktualisierungsverfahrensschritt umfasst zum dem Inhalt der Abänderung entsprechenden Aktualisieren des Binärstrukturbaumes, wenn das Intervall abgeändert wird.
Gemäß der Erfindung, wie in den Ansprüchen 5 und 23 beansprucht, aktualisiert die Binärstrukturbaum- Aktualisierungseinrichtung einen Binärstrukturbaum, wenn ein Intervall abgeändert wird und beseitigt die Bedarf einer Regenerierung des Binärstrukturbaumes.
Eine Erfindung gemäß Patentanspruch 6 ist ein Datenverarbeitungssystem gemäß Anspruch 5, wobei die Binärstrukturbaum-Aktualisierungseinrichtung folgendes umfasst: Eine Intervalllängen-Änderungseinrichtung zum Abändern der Intervall-Länge; eine Entfernungseinrichtung zum Entfernen des Knotenpunktes, welcher einem vom Binärstrukturbaum gelöschten Intervall entspricht, wenn das Intervall aus der Codekette entfernt worden ist; und eine Hinzufügungseinrichtung zum Hinzufügen eines einem hinzugefügten Intervall entsprechenden Knotenpunktes, wenn ein Intervall hinzugefügt wird.
Erfindungsgemäß, wie in den Ansprüchen 6 und 24 beansprucht, aktualisiert die Intervalllängen-Änderungseinrichtung, die Entfernungseinrichtung oder die Hinzufügungseinrichtung den Binärstrukturbaum, wenn eine Intervall-Länge abgeändert, ein Intervall entfernt oder ein Intervall hinzugefügt wird. Eine Kombination dieser Einrichtungen gestattet die Durchführung von komplexen Verarbeitungen; beispielsweise können die Intervalle in einer Codekette ausgetauscht werden.
Erfindungsgemäß, wie in Anspruch 7 beansprucht, müssen, auch wenn die Länge eines Intervalls abgeändert wird, lediglich die Knotenpunkte von diesem Knotenpunkt zu dem Hauptverzeichnis abgeändert werden. Im Gegensatz zu einem herkömmlichen System beseitigt das Datenverarbeitungssystem die Anforderung, dass alle Knotenpunkte, die den dem abgeänderten Knotenpunkt nachfolgenden Intervallen entsprechen, bewegt werden müssen, was die Datenverarbeitungseffizienz steigert.
Erfindungsgemäß, wie in Anspruch 8 beansprucht, ist die Verarbeitung vereinfacht, weil nicht mehr der Bedarf besteht, dass die partiellen Intervall-Längen - ausgenommen die des Hauptverzeichnisses - abgeändert werden müssen.
Eine Erfindung gemäß Anspruch 9 ist ein Datenverarbeitungssystem gemäß Anspruch 6, wobei die Hinzufügungseinrichtung zu dem Binärstrukturbaum die Knotenpunkte, welche dem hinzuzufügendem Intervall entsprechen, hinzufügt, die Verbindungssequenz der Knotenpunkte einstellt und die Intervall-Länge eines jeden Knotenpunktes einstellt.
Erfindungsgemäß, wie in Anspruch 9 beansprucht, stellt die Hinzufügungseinrichtung die Verbindungssequenz und die Intervall-Längen der Knotenpunkte ein, damit die Integrität des Binärstrukturbaumes erhalten bleibt.
Erfindungsgemäß, wie in Patentanspruch 10 beansprucht, werden die Intervall-Längen einfach durch ein Hinzufügen der Länge des hinzugefügten Intervalls zu jedem Knotenpunkt auf dem Pfad vom Erzeuger (parent) des hinzugefügten Knotenpunktes bis hin zum Hauptverzeichnis eingestellt.
Eine Erfindung gemäß Patentanspruch 11 ist ein Datenverarbeitungssystem gemäß Anspruch 6, wobei die Hinzufügungseinrichtung eine Einrichtung umfasst, um die Knotenpunkte, welche unmittelbar einer Position vorhergehen und nachfolgen, an welcher ein Knotenpunkt hinzugefügt werden muß, zu dem Hauptverzeichnisknotenpunkt mittels Ausbreitung zu bewegen, jeweils ein Knotenpunkt pro Zeit. Die Hinzfügungseinrichtung umfasst ferner eine Einrichtung zum Hinzufügen des Knotenpunktes, welcher einem hinzuzufügendem Intervall entspricht, an einer Position, die unmittelbar dem unmittelbar-vorhergehenden Knotenpunkt nachfolgt oder an einer Position, die unmittelbar vor dem unmittelbar-nachfolgenden Knotenpunkt liegt. Die Hinzufügungseinrichtung umfasst ferner eine Einrichtung zum Hinzufügen der Intervall-Länge des hinzugefügten Knotenpunktes zu der partiellen Intervall-Länge des unmittelbar vorhergehenden oder unmittelbar-nachfolgenden Knotenpunktes des hinzugefügten Knotenpunktes, falls es erforderlich ist.
Erfindungsgemäß, wie in Anspruch 11 beansprucht, wird das Verarbeiten vereinfacht, weil partielle Intervall-Längen lediglich für eine geringe Anzahl von Knotenpunkten, einschließlich des Hauptverzeichnisknotenpunktes, abgeändert (Zunahme) werden müssen.
Eine Erfindung gemäß Patentanspruch 12 ist ein Datenverarbeitungssystem gemäß Anspruch 6, wobei die Hinzufügungseinrichtung folgendes umfasst: eine Einrichtung, um den Knotenpunkt, der dem hinzuzufügendem Intervall entspricht, zu dem Binärstrukturbaum mit der Intervall-Länge des Knotenpunktes des Wertes 0 hinzuzufügen; eine Einrichtung, um den hinzugefügten Knotenpunkt zu dem Hauptverzeichnisknoten des Binärstrukturbaumes mittels Ausbreitung zu bewegen; und eine Einrichtung, um die partielle Intervall-Länge des zu dem Hauptverzeichnisknoten bewegten Knotenpunktes um die Intervall-Länge des hinzugefügten Intervalls zu erhöhen.
Erfindungsgemäß, wie in Anspruch 12 beansprucht, wird das Verarbeiten beschleunigt, da die partielle Intervall-Länge eines Knotenpunktes unter Verwendung des gewünschten Hinzufügalgorithmus nur einmal erhöht werden muss.
Eine Erfindung gemäß Patentanspruch 13 ist ein Datenverarbeitungssystem gemäß Anspruch 6, wobei die Entfernungseinrichtung folgendes umfasst: eine Einrichtung zum Entfernen des Knotenpunktes des zu löschenden Intervalls vom Binärstrukturbaum; eine Einrichtung zum Einstellen der Verbindung zwischen den Knotenpunkten; und eine Einrichtung zum Einstellen der Intervall-Länge eines jeden Knotenpunktes.
Erfindungsgemäß, wie in Anspruch 13 beansprucht, stellt die Entfernungseinrichtung die Knotenpunkteverbindungssequenz und die Intervall-Längen ein, um die Integrität des Binärstrukturbaumes, wie etwa die Sequenz der verbleibenden Intervalle, zu erhalten.
Eine Erfindung gemäß Patentanspruch 14 ist ein Datenverarbeitungssystem gemäß Anspruch 6, wobei die Entfernungseinrichtung folgendes umfasst: eine Einrichtung, um die Knotenpunkte, die dem zu entfernenden Intervall entsprechen, zu dem Hauptverzeichnisknoten mittels Ausbreitung zu bewegen; eine Einrichtung, um den Knotenpunkt, welcher dem zu entfernenden Knotenpunkt unmittelbar vorhergeht oder nachfolgt, zu dem Hauptverzeichnisknoten mittels Ausbreitung zu bewegen; eine Einrichtung zum Erhöhen der partiellen Intervall-Länge des unmittelbar vorhergehenden oder unmittelbar nachfolgenden Knotenpunktes, welcher der Hauptverzeichnisknoten ist, um die Intervall-Länge des zu entfernenden Knotenpunktes; und eine Einrichtung zum Entfernen des zu entfernenden Knotenpunktes.
Erfindungsgemäß, wie in Anspruch 14 beansprucht, wird das Verarbeiten beschleunigt, da lediglich die Knotenpunkte des Hauptverzeichnisses während des Entfernungsvorganges eingestellt werden müssen.
Eine Erfindung gemäß Patentanspruch 15 ist ein Datenverarbeitungssystem gemäß Anspruch 5, welches ferner eine Struktureinstellungs-Einrichtung zum Einstellen der Struktur des Binärstrukturbaumes mittels eines Abänderns der Verbindungssequenz der Knotenpunkte umfasst.
Die Erfindung von Anspruch 25 ist eine verfahrenstechnische Umsetzung der Erfindung gemäß Anspruch 15 und stellt ein Datenverarbeitungsverfahren nach Anspruch 23 dar, welches ferner einen Struktureinstellungsprozess umfasst, um die Struktur des Binärstrukturbaumes durch ein Abändern der Verbindungssequenz der Knotenpunkte einzustellen.
Erfindungsgemäß, wie in den Ansprüchen 15 und 25 beansprucht, hält die Struktureinstellung nur einen bestimmten Teil des Binärstrukturbaumes davon ab, vergrößert zu werden, wodurch eine Vielzahl von Pfaden, jeweils von dem Hauptverzeichnis bis zum Knotenpunkt, gleich lang gemacht werden. Dadurch wird verhindert, dass die Datenverarbeitungszeit nur deshalb anwächst, weil der zugehörige Pfad zu lang ist, weshalb verschiedene Arten der Datenverarbeitung effizienter gestaltet werden, wie etwa das Suchen oder das Aktualisieren.
Erfindungsgemäß, wie in Patentanspruch 16 beansprucht, wird die Struktureinstellung gemäß dem Status des Binärstrukturbaumes durchgeführt, weil eine Vielzahl von Verarbeitungsarten kombiniert werden, um die Struktur eines spezifizierten Bereiches des Binärstrukturbaumes abzuändern.
Eine Erfindung gemäß Patentanspruch 17 ist ein Datenverarbeitungssystem nach Anspruch 15, wobei die Struktureinstellungs-Einrichtung eine Einrichtung zum Einstellendes Binärstrukturbaumes mittels Ausbreitung umfasst, wodurch ein Zielknotenpunkt, welcher eines der Knotenpunkte ist, zu dem Hauptverzeichnisknoten bewegt wird.
Erfindungsgemäß, wie in Anspruch 17 beansprucht, wird ein Zielknotenpunkt mittels Ausbreitung zum Hauptverzeichnis bewegt, und gleichzeitig wird in den meisten Fällen die Länge eines Pfades von einem Knotenpunkt, welcher auf dem Pfad von Zielknotenpunkt zum ursprünglichen Hauptverzeichnis liegt, reduziert. Aufgrund dieses werden verschiedene Arten der Verarbeitung für den Binärstrukturbaum beschleunigt.
Erfindungsgemäß, wie in Anspruch 18 beansprucht, werden getrennt voneinander eine Art von Binärstrukturbaum erzeugt, welche die Sequenz der Zeilen darstellt, und eine andere Art von Binärstrukturbaum erzeugt, welche den Inhalt einer jeden Zeile darstellt. Wenn entweder die Sequenz der Zeilen oder der Inhalt der Zeilen abgeändert wird, bedarf es von daher kein Abändern der jeweils anderen Art des Binärstrukturbaumes. Dies steigert die Effizient der Codekettenverarbeitung.
Erfindungsgemäß, wie in Anspruch 19 beansprucht, können Daten als einen einzelnen einfach-strukturierten Binärstrukturbaum dargestellt werden. Zusätzlich, wie erfindungsgemäß in Anspruch 19 beansprucht, können aufeinanderfolgende Schriftzeichen oder Leerzeichen durch einen einzelnen Knotenpunkt dargestellt werden, was sowohl die Verarbeitungseffizient als auch die Speichereffizient steigert.
Andere und weitere Zwecke, Funktionen und Vorteile der vorliegenden Erfindung werden durch die nachfolgende detaillierte Beschreibung besser verstanden werden.

Kurze Beschreibung der Zeichnungen

Fig. 1 ist ein Blockdiagramm, welches die Konfiguration des Datenverarbeitungssystem in einer ersten Ausführungsform dieser Erfindung zeigt;
Fig. 2 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung;
Fig. 3 erklärt den Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung;
Fig. 4 ist ein Flussdiagramm, welches die Prozedur zum Aufsuchen von Daten in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 5 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Aufsuchen);
Fig. 6 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Aufsuchen);
Fig. 7 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Aufsuchen);
Fig. 8 ist ein Beispiel eines Flußdiagramms, welches die Prozedur zur Identifizierung eines Intervalls zeigt, das einem spezifizierten Knotenpunkt in der ersten Ausführungsform dieser Erfindung entspricht;
Fig. 9 ist ein weiteres Beispiel eines Ablaufdiagramns, welches die Prozedur zur Identifizierung eines Intervalls zeigt, das in der ersten Ausführungsform dieser Erfindung einem spezifizierten Knotenpunkt entspricht;
Fig. 10 ist ein funktionelles Blockdiagramm, das ein Beispiel einer Gerätekonfiguration zeigt, die zum Aufsuchen in der ersten Ausführungsform dieser Erfindung geeignet ist;
Fig. 11 ist ein Ablaufdiagramm, welches eine Prozedur zum Abändern einer Intervall-Länge in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 12 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Abändern der Intervall-Länge);
Fig. 13 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Abändern der Intervall-Länge);
Fig. 14 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Abändern der Intervall-Länge);
Fig. 15 ist ein Ablaufdiagramm, welches die Vorgehensweise zum Hinzufügen oder Entfernen eines Knotenpunktes in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 16 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Hinzufügen eines Intervalls);
Fig. 17 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Hinzufügen eines Intervalls);
Fig. 18 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Hinzufügen eines Intervalls);
Fig. 19 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Hinzufügen eines Intervalls);
Fig. 20 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Entfernen eines Intervalls);
Fig. 21 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Entfernen eines Intervalls);
Fig. 22 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Entfernen eines Intervalls);
Fig. 23 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Einstellen der Struktur);
Fig. 24 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Einstellender Struktur);
Fig. 25 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Einstellen der Struktur);
Fig. 26 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Einstellen der Struktur);
Fig. 27 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Einstellen der Struktur);
Fig. 28 zeigt ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung (Einstellen der Struktur);
Fig. 29 ist ein Diagramm, welches ein Beispiel eines Binärstrukturbaumes in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 30 ist ein konzeptionelles Diagramm, welches das Datenformat eines jeden Knotenpunktes in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 31 ist ein konzeptionelles Diagramm, welches zeigt, wie die Knotenpunkte in einem Teil des Binärstrukturbaumes in Fig. 29 mittels Zeiger in der ersten Ausführungsform dieser Erfindung verbunden sind;
Fig. 32 ist ein Diagramm, welches den Binärstrukturbaum in Fig. 29 zeigt, bei dem in der ersten Ausführungsform dieser Erfindung die Doppelrotation (Zick-Zick) angewandt wurde;
Fig. 33 ist ein Diagramm, welches die Daten und Zeiger des Knotenpunktes d und dessen untergeordneten Knotenpunkten in Fig. 31 in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 34 ist ein Diagramm, welches den Binärstrukturbaum in Fig. 32 zeigt, bei dem in der ersten Ausführungsform dieser Erfindung die Doppelrotation (Zick-Zack) angewandt wurde;
Fig. 35 ist ein Diagramm, welches den Binärstrukturbaum in Fig. 34 zeigt, bei welchem die Doppelrotation (Zick-Zack) in dem ersten Ausführungsbeispiel dieser Erfindung angewandt wurde;
Fig. 36 ist ein Diagramm, welches den Binärstrukturbaum in Fig. 35 zeigt, bei dem die Rotation in der ersten Ausführungsform dieser Erfindung angewandt wurde;
Fig. 37 ist ein Diagramm, welches einen Teil des Binärstrukturbaumes zeigt, bevor ein Intervall durch Ausbreitung in der ersten Ausführungsform dieser Erfindung hinzugefügt wurde;
Fig. 38 ist ein Diagramm, welches den Binärstrukturbaum aus Fig. 37 zeigt, bei dem in dem ersten Ausführungsbeispiel dieser Erfindung Ausbreitung angewandt wurde;
Fig. 39 ist ein Diagramm, welches den Binärstrukturbaum zeigt, bei dem ein Intervall mittels Ausbreitung in der ersten Ausführungsform dieser Erfindung hinzugefügt wurde;
Fig. 40 ist ein Diagramm, welches den Binärstrukturbaum zeigt, bei dem in dem in Fig. 38 gezeigten Binärstrukturbaum die Ausbreitung am Knotenpunkt R angewandt wurde, welcher der Knotenpunkt ist, der unmittelbar dem Hinzufügungspunkt in der ersten Ausführungsform dieser Erfindung nachfolgt;
Fig. 41 ist ein Diagramm, welches den Binärstrukturbaum zeigt, bei dem der Knotenpunkt X als der rechte Ableger des Knotenpunktes L in der ersten Ausführungsform dieser Erfindung hinzugefügt wurde;
Fig. 42 ist ein Diagramm, welches den in Fig. 40 gezeigten Binärstrukturbaum zeigt, wobei der Knotenpunkt L keinen rechten Ableger aufweist und der Knotenpunkt L des linken Ablegers des Knotenpunktes X in der ersten Ausführungsform dieser Erfindung ist;
Fig. 43 ist ein Diagramm, welches den in Fig. 40 gezeigten Binärstrukturbaum zeigt, wo der Knotenpunkt L keinen rechten Ableger aufweist und der Knotenpunkt X der rechte Ableger des Knotenpunktes L in der ersten Ausführungsform dieser Erfindung darstellt;
Fig. 44 ist ein Diagramm, welches den Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung zeigt, in dem der Knotenpunkt X zum Entfernen zu dem Hauptverzeichnisknoten mittels Ausbreitung bewegt werden muß;
Fig. 45 ist ein Diagramm, welches den Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung zeigt, in welchem der Knotenpunkt R, der dem zu entfernenden Knotenpunkt X unmittelbar nachfolgt, zum Hauptverzeichnisknoten mittels Ausbreitung bewegt wurde;
Fig. 46 ist ein Diagramm, welches den Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung zeigt, von dem der Knotenpunkt X entfernt worden ist;
Fig. 47 ist ein Diagramm, welches ein Muster-ausbalancierten Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung zeigt;
Fig. 48 ist ein Diagramm, welches die Information zeigt, die in einem Knotenpunkt in einem Muster-ausbalancierten Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung enthalten ist;
Fig. 49 ist ein Diagramm, welches den in Fig. 47 gezeigten Baum zeigt, wo (einen Knotenpunkt darstellend) ein neues Intervall x zu der Linken des Intervalls, welches durch den Knotenpunkt f in der ersten Ausführungsform dieser Erfindung dargestellt wird, eingefügt wurde;
Fig. 50 (a) ist ein Diagramm, welches eine Art des Abgleichens (Promotion) darstellt, wenn Bedingung 2 in der ersten Ausführungsform dieser Erfindung nicht erfüllt ist;
Fig. 50 (b) ist ein Diagramm, welches eine Art des Abgleichens (einfache Rotation) zeigt, wenn Bedingung 2 in der ersten Ausführungsform dieser Erfindung nicht erfüllt ist;
Fig. 50 (c) ist ein Diagramm, welches eine Art des Abgleichens (doppelte Rotation) zeigt, wenn Bedingung 2 in der ersten Ausführungsform dieser Erfindung nicht erfüllt ist;
Fig. 51 ist ein Diagramm, welches den Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung zeigt, bei dem die Knotenpunktfarben abgeändert wurden;
Fig. 52 ist ein Diagramm, welches den Binärstrukturbaum in der ersten Ausführungsform dieser Erfindung zeigt, in welchem die einfache Rotation angewandt wurde und die Knotenpunktfarben abgeändert wurden;
Fig. 53 zeigt einen Binärstrukturbaum in einer zweiten Ausführungsform dieser Erfindung;
Fig. 54 zeigt einen Binärstrukturbaum in einer dritten Ausführungsform dieser Erfindung;
Fig. 55 zeigt ein Beispiel eines Musters in einer Schriftzeichenkette, welche in einem herkömmlichen Codeketten- Suchverfahren verwendet wird;
Fig. 56 zeigt ein Beispiel eines konventionellen Tries;
Fig. 57 ist eine Tabelle, welche die Korrespondenz zwischen Codeketten und Positionen in einem herkömmlichen Codeketten- Suchverfahren zeigt;
Fig. 58 zeigt ein Beispiel eines herkömmlichen Positionsbaumes;
Fig. 59 zeigt ein Beispiel eines herkömmlichen Suffix- Baumes;
Fig. 60 zeigt ein Beispiel eines herkömmlichen direkten azyklischen Wortgraphen;
Fig. 61 zeigt ein Beispiel von Daten, welche in einem ersten herkömmlichen Verfahren verwendet werden;
Fig. 62 zeigt ein Beispiel von Daten, welche in einem ersten herkömmlichen Verfahren (Einfügen) verwendet werden;
Fig. 63 zeigt ein Beispiel von Daten, welche in einem zweiten herkömmlichen Verfahren verwendet werden;
Fig. 64 zeigt ein Beispiel eines herkömmlichen Binärstrukturbaumes;
Fig. 65 zeigt ein Beispiel von Daten, welche in einem dritten herkömmlichen Verfahren verwendet werden; und
Fig. 66 zeigt ein Beispiel von Daten, welche in einem vierten herkömmlichen Verfahren verwendet werden.

Bezugszeichenliste:

1: Codekette
2: Erste Sub-Zeichenkette
3: Zweite Sub-Zeichenkette
4: Dividiereinrichtung
5: Erste Dateilistendaten
6: Zweite Dateilistendaten
7: Erzeugungseinrichtung
31: Binärstrukturbaum
32: Binärstrukturbaum-Erzeugungseinrichtung
33: Intervall-Sucheinrichtung
34: Binärstrukturbaum-Aktualisierungseinrichtung
41: Intervalllängen-Abänderungseinrichtung
42: Hinzufügungseinrichtung
43: Entfernungseinrichtung
45: Struktur-Einstellungseinrichtung

Detailierte Beschreibung

Unter Bezugnahme der beigefügten Zeichnungen ist dort eine bevorzugte Ausführungsform (von nun an Ausführungsform genannt) dieser Erfindung gezeigt. Es sei bemerkt, dass die nachstehend beschriebene Ausführungsform in einem Computer implementiert ist und dass jede Funktion dieser Ausführungsform durch eine Prozedur ausgeführt wird (Programm), welche diesen Computer steuert.
Jede in dieser Spezifikation bezeichnete "Einrichtung" bezieht sich auf ein konzeptionelles Äquivalent einer jeden Funktion dieser Ausführungsform; das bedeutet, es gibt nicht überall eine 1 : 1 Korrespondenz zwischen Einrichtungen und bestimmten Teilen der Hardware - oder Software-Routinen. Ein Teil der Hardware umfasst manchmal verschiedene Einrichtungen. Beispielsweise dient ein Computer als eine Einrichtung, wenn eine Anweisung ausgeführt wird, aber er dient auch als eine andere Einrichtung, wenn andere Anweisungen ausgeführt werden. Zusätzlich kann eine Einrichtung in einigen Fällen durch eine Anweisung, aber auch in anderen Fällen durch eine Vielzahl von Anweisungen ausgeführt sein.
Von daher beschreibt diese Spezifikation eine Ausführungsform mit der Zuhilfenahme von virtuellen Schaltungsblöcken (Einrichtungen), wobei jeder bei dieser Ausführung seine eigene Funktion hat. Es sei bemerkt, dass eine Ausführungsform, welche durch einen Computer ausgeführt wird, nur ein Beispiel darstellt; alles oder ein Teil dieser Erfindung kann, falls möglich, in einem elektronischen Schaltkreis, wie etwa ein Maß-Chip (custom-chip) (maßangefertigter integrierter Schaltkreis) zusammengepackt werden. Der in dieser Ausführungsform verwendete Computer umfasst gewöhnlich eine CPU (Zentrale Prozessoreinheit) und einen Hauptspeicher bestehend aus einem RAM (random access memory), Ein Computer jeglicher Größe, beispielsweise ein Mikrocomputer, Personalcomputer, Kleincomputer, Workstation oder Großrechner kann hierfür verwendet werden.
Typischerweise weist der Computer Eingabevorrichtungen, wie etwa eine Tastatur und eine Maus, externe Speichereinheiten, wie etwa eine Festplatte, Ausgabevorrichtungen, wie etwa ein CRT-Display oder ein Drucker und andere erforderliche Eingabe/Ausgabe-Steuerungsschaltungen auf.
Der Computer kann in verschiedenen Konfigurationen gebaut sein, und eine oder mehrere Komponenten können hinzugefügt, abgeändert oder entfernt sein, soweit dieses die Konfiguration nicht von den Charakteristika dieser. Erfindung abrückt. Beispielsweise kann die Ausführung in einem Computernetzwerk aufgebaut sein, in dem eine Vielzahl von Computern untereinander verbunden sind. Verschiedene Arten von CPU's können eingesetzt werden, eine Vielzahl von CPU's können zur gleichen Zeit benutzt werden oder eine einzelne CPU kann inder Zeitteilverfahrensweise (time-sharing Art) verwendet werden, um nebeneinander herlaufend eine Vielzahl von Prozesse zu verarbeiten. Andere Arten von Eingabevorrichtungen können verwendet werden (Markierungsvorrichtungen, wie etwa ein Touch Screen, Light Pen und Track Ball, Bildeingabevorrichtungen, wie etwa ein Digitizer, Bildleser und Videokamera, Spracherkennungsvorrichtungen oder andere Typen von Sensoren). Andere externe Speichervorrichtungen können benutzt werden (Floppy Disk Laufwerke, RAM-Kartenleser, magnetische Bandvorrichtungen, Optical-Disc-Votrichtungen, magnetooptische Disc-Vorrichtung (MO), Bubble Memory-Vorrichtungen und Flash Memory-Karten). Andere Ausgabevorrichtungen können benutzt werden (Flüssigkristallbildschirm, Plasmabildschirm- Vorrichtungen, Videoprojektoren, LED-Display-Vorrichtungen, Sprachgeneratoren und Sprachsynthesizer).
Bei einer typischen Software-Konfiguration dieses Computers läuft ein Programm, welches jede Funktion dieser Ausführung ausführt, als ein Anwendungsprogramm unter dem Operationssystem (OS). Typischerweise erzeugt die Maschinensprache durch Kompilieren das benutzte Programm, das in einer High-Level-Sprache oder im Assempler-Format codiert ist. Jedoch ist die Software-Konfiguration dieses Computers frei und kann sofern diese Erfindung implementiert ist, abgeändert werden. Beispielsweise braucht nicht immer das Operationssystem (OS) verwendet werden und eine beliebige Programmiersprache kann benutzt werden. Ein Interpreter (serielle interpretierende Ausführung), wie etwa Basic, kann benutzt werden, um ein Programm zu codieren.
Das Programm kann in einer beliebigen Speichervorrichtung abgelegt sein. Es könnte in einem ROM (read-only memory) oder in einer externen Speichervorrichtung, wie etwa eine Festplatte, geschehen; im letzteren Fall wird das Programm in den Hauptspeicher geladen (Lesen), wenn der Computer oder der Prozess gestartet wird. Ferner kann das Programm in eine Vielzahl von Module eingeteilt sein, welche in einer externen Speichervorrichtung gespeichert sind. In diesem Fall werden lediglich die für die Verarbeitung notwendigen Module in den Hauptspeicher geladen. Jedes Programmmodul sollte auf einer dafür bestgeeigneten Speichervorrichtung abgelegt sein.
Die Sequenz der Schritte einer Prozedur, die in dieser Ausführungsform verwendet wird, kann abgeändert sein, eine Vielzahl von Schritten können nebeneinander herlaufend ausgeführt werden, oder diese Schritte können in einer verschiedenen Abfolge immer dann ablaufen, wenn das Programm ausgeführt wird, sofern diese Schritte nicht von den Charakteristika dieser Erfindung abweichen. Die Möglichkeit, die Abfolge der Ausführungen abzuändern, ist mittels der menügelenkten Schnittstelle implementiert, welche es dem Anwender erlaubt, die Verarbeitung, welche er ausführen möchte, auszuwählen.
Die in dieser Spezifikation genannte "Eingabe" schließt nicht nur die Eingabe von Daten ein, sondern auch andere Arten von Bearbeitungen, welche nah mit der Dateneingabe verbunden sind. Sie schließt den Zurückwiderhall (echo-back), die Modifikation und die Bearbeitung von eingegangenen Daten ein. Auch die in dieser Spezifikation gezeichnete "Ausgabe" schließt nicht nur die Ausgabe von Daten ein, sondern auch andere Arten von Verarbeitungen, welche nahe mit der Datenausgabe verbunden sind. Sie schließen den Eintrag von Ausgabebereichen oder Anweisungen zur Bildschirm-Scrolling ein. Auch können Eingabe und Ausgabe in einer interaktiven Eingabe/Ausgabe-Operation integriert sein, und durch diese integrierte Operation kann der Anwender die durchzuführende Verarbeitung selektieren, spezifizieren oder identifizieren.
Daten (Information) oder Datenspeichervorrichtungen, die in dieser Spezifikation bezeichnet wurden, können in dem Computer in verschiedenen Arten existieren. Beispielsweise können Daten, welche in dieser Spezifikation beschrieben werden, als auf einer Festplatte befindlich, im Hauptspeicher, in einer externen Speichereinheit, in einem CPU-Register oder in einem Zwischenspeicher sein. Zusätzlich können die Daten in verschiedenen Formen gehalten werden. Beispielsweise können Daten in einem File oder in einem Speicher oder auf einer Diskette gespeichert sein, um den direkten Zugriff über physikalische Adressen zu ermöglichen. Der Code einer Textzeichenfolge kann in Schriftzeichen oder Wörtern dargestellt sein. Daten können für unterschiedliche Zeitperioden gespeichert sein; sie können sich nach einer spezifizierten Zeit verflüchtigen. Daten, welche nicht abgeändert werden müssen, wie beispielsweise Dateilistendaten, können in der ROM gespeichert sein.
In dieser Spezifikation setzen Bezüge zu einem speziellen Teil nicht voraus, dass nur dieses Teil verwendet wird. Das bedeutet, dass in dieser Erfindung allgemeine Gegenstände, welche zur Ausführung dieser Erfindung benötigt werden, wie etwa Zeiger, Zähler, Flaggen, Parameter und Speicher, als notwendig verwendet werden.
Sofern nicht anderweitig spezifiziert, wird Information, welche für jeden Teil dieser Ausführung notwendig ist, von anderen Teilen bezogen, welche die Information beinhalten. Beispielsweise kann Information durch den Zugriff auf Variablen oder auf in einem Speicher gehaltenen notwendigen Informationen erhalten werden. Informationen können erweitert oder gelöscht werden, nicht nur durch Löschen der Information von einem Speicherbereich, sondern auch durch das Setzen einer Flagge, welche das Löschen dieser Information anzeigt.

[1. Erste Ausführungsform]

[1-1. Konfiguration der ersten Ausführungsform]

Die erste Ausführungsform entspricht einem Datenverarbeitungssystem (entspricht Patentansprüche 1-17) und ein Datenverarbeitungsverfahren (entspricht Ansprüchen 20-25), welches auf diesem Datenverarbeitungssystem ausgeführt wird. Fig. 1 ist ein Blockdiagramm, welches die Konfiguration der ersten Ausführungsform zeigt.
Es ist ein Ziel der ersten Ausführungsform, ein Datenverarbeitungssystem und ein Datenverarbeitungsverfahren, welches die Verarbeitung von Daten effizient betreibt, zur Verfügung zu stellen. Dieses Datenverarbeitungssystem und ein Datenverarbeitungsverfahren sind im einzelnen dafür geeignet, das oben beschriebene Datensuchsystem und Datensuchverfahren auszuführen. Das Datenverarbeitungssystem und das Datenverarbeitungsverfahren der ersten Ausführungsform verwenden nämlich eine Subkette als ein Intervall um ferner die Effizienz von verschiedenen Arten von Verarbeitungen einschließlich des Datensuchens zu steigern.
Da die Inhalte einer Teilkette innerhalb eines Dateilistenbaumes eines Datensuchsystems und eines Datensuchverfahrens umgespeichert (restored) werden kann, verwendet das Datenverarbeitungssystem und -verfahren in dieser Ausführungsform keine Codekette, sondern eine erste und zweite Subkette einer Codekette.
Genauer gesagt liegt ein Ziel der ersten Ausführungsform darin, ein Datenverarbeitungssystem und -verfahren vorzuschlagen, dessen Datenabänderungsprozedur einfach verläuft. Ein weiteres Ziel der ersten Ausführungsform besteht darin, ein Datenverarbeitungssystem und -verfahren anzugeben, welches die Speicherkapazität effizienter nutzt.
Gemäß Fig. 1 weist das Datenverarbeitungssystem der ersten Ausführungsform eine Binärstrukturbaum-Erzeugungseinrichtung 32 zum Erzeugen des Binärstrukturbaumes 31 auf, welcher den Bereich eines jeden Intervalls basierend auf den Intervallen in einer Codekette darstellt; ferner weist die erste Ausführungsform eine Intervall-Sucheinrichtung 33 zur Suche eines Intervalls, das einer spezifizierten Position übereinstimmend mit dem Binärstrukturbaum 31 entspricht, und die Binärstrukturbaum-Aktualisierungseinrichtung 34 zum Aktualisieren des Binärstrukturbaumes 31 in Anlehnung an den Inhalten einer Abänderung, wenn ein Intervall abgeändert wird.
Die Binärstrukturbaum-Aktualisierungseinrichtung 34 weist der Reihe nach die Intervalllängen-Änderungseinrichtung 41 auf zum Abändern einer Intervall-Länge, die Entfernungseinrichtung 42 auf zum Entfernen eines Knotenpunktes, welcher einem gelöschten Intervall entspricht, und die Hinzufügungseinrichtung 43 auf zum Hinzufügen eines Knotenpunktes, welcher einem hinzugefügten Intervall entspricht. Ferner weist das Datenverarbeitungssystem in der sechsten Ausführungsform die Struktureinstellungseinrichtung 45 zum Einstellen der Struktur eines Binärstrukturbaumes durch Abändern der Verbindungssequenz der Knotenpunkte auf.

[1-2. Betrieb und Effekte der ersten Ausführungsform]

Die erste Ausführungsform, welche die obige Konfiguration aufweist, führt die folgende Operation durch: Es erlaubt dem Anwender, eine Codekette, welche eine Vielzahl von Intervalle beinhaltet, zu speichern, einen Codewert an einer spezifizierten Position innerhalb der Codekette zu erhalten sowie eine Codekette gemäß den Bedürfnissen des Anwenders zu bearbeiten.

[1-2-1. Binärstrukturbaum-Erzeugungsprozess]

Als Erstes erzeugt die Binärstrukturbaum-Erzeugungseinrichtung 32 den Binärstrukturbaum 31, welcher den Bereich eines jeden Intervalls übereinstimmend mit den Intervalle in der Codekette darstellt. Der Binärstrukturbaum kann auch unter der Verwendung der Hinzufügungseinrichtung 43 erzeugt werden, indem immer dann, wenn ein Intervall eingegeben wird, ein Knotenpunkt hinzugefügt wird. Eine Codekette und die Intervalle können beispielsweise über die Tastatur eingegeben werden. Der Binärstrukturbaum 31 ist eine baumartige Datenstruktur bestehend aus Knotenpunkten, wobei jeder Knotenpunkt einem Intervall entspricht, der von dem Hauptverzeichnisknoten zu den Enden verbunden ist. An der Endseite eines jeden Knotenpunktes ist der vorhergehende Knotenpunkt, welcher dem vorhergehenden Intervall des Knotenpunktes entspricht, und/oder der nachfolgenden Knotenpunkt, welcher dem nachfolgenden Intervall des Knotenpunktes entspricht, verbunden. Auch ist in jedem Knotenpunkt die Summe aus der Intervall-Länge des Knotenpunktes selber und der gesamten Intervall-Länge der Knotenpunkte an der Endseite des Knotenpunktes (Sub-Baum) festgesetzt. Diese Summe wird partielle Intervall-Länge genannt.
Fig. 2 zeigt ein Beispiel des Binärstrukturbaumes 31, welcher in der ersten Ausführungsform verwendet wird, und Fig. 3 beschreibt den Binärstrukturbaum 31 in Fig. 2. Gemäß diesen Figuren ist der Binärstrukturbaum 31 der ersten Ausführungsform ein Baum bestehend aus Knotenpunkten A, B, C, D und E, welche den Intervallen [1..3], [4..5], [6..9], [10..15] bzw. [16..16] entsprechen, wobei diese an den Knotenpunkt B als den Hauptverzeichnisknoten angeschlossen sind. An die Endseite des Knotenpunktes B sind der Knotenpunkt A, welcher dem Intervall [1..3] entspricht, das dem Knotenpunkt B vorhergeht, und die Knotenpunkte D, C und E, welche den Intervalle entsprechen, die dem Knotenpunkt B nachfolgen, angeschlossen. Zusätzlich ist an der Endseite des Knotenpunktes D der Knotenpunkt C angeschlossen, welcher dem Intervall entspricht, das den Knotenpunkten D und E vorhergeht, welche dem Intervall, das Knotenpunkt D nachfolgt, entsprechen.
In jedem der Knotenpunkte A, B, C, D und E sind die partiellen Intervall-Längen 3, 16, 4, 11 und 1 festgesetzt, wobei jede die Summe aus der Länge des Knotenpunktes selber und die Gesamtlängen der Knotenpunkte an der Endseite dieses Knotenpunktes darstellt. In dem Knotenpunkt D beispielsweise ist die Summe (11) aus der Länge (6) des Intervalls [10..15], das dem Knotenpunkt D entspricht, und den Gesamtlängen (4 und 1) der Intervalle [6..9] und [16..16] festgesetzt.
Das Datenverarbeitungssystem in der ersten Ausführungsform, welches wie oben beschrieben einen Knotenpunkt für jedes Intervall aufweist, benötigt so viele Datenblöcke wie Intervalle und eliminiert somit den Bedarf nach so vielen Speichereinheiten wie vorhandenen Knotenpunkten (Positionen), wodurch die Speicherplatznutzeffizienz anwächst. Im einzelnen erfordert ein Binärstrukturbaum, in welchem Datenspeicherungsbereiche für die Knotenpunkte mittels Zeiger verbunden sind, keinen großen aufeinanderfolgenden Bereich und verwendet von daher den Speicher effizient. Das Vermögen, eine Präzision (precision) für jedes Intervall am geeignetsten zu nutzen, erlaubt es dem Anwender, jegliche Arten von Intervall- Daten, wie etwa Fliesskommadaten zu verwenden.
In diesem Datenverarbeitungssystem kann die Position des Intervalls eines Knotenpunktes während der Suche oder einiger anderer Verarbeitungen basierend auf der Intervall-Länge des vorhergehenden (nachfolgenden) Knotenpunktes berechnet werden. Die Netz-Intervall-Länge eines Knotenpunktes kann über die Subtraktion der Gesamtheit der Intervall-Längen der vorhergehenden und nachfolgenden Knotenpunkte, die in dem Sub- Baum, der an den Knotenpunkt angeschlossen ist, enthalten sind, von der partiellen Intervall-Länge des Knotenpunktes berechnet werden. Die Intervall-Länge des vorhergehenden (nachfolgenden) Knotenpunktes kann aus der partiellen Intervall-Länge des linken (rechten) Ablegers ermittelt werden. Von daher kann der Code an einer spezifizierten Position innerhalb der Codekette einfach durch den Vergleich der spezifizierten Position mit der Position und der Intervall-Länge eines jeden Knotenpunktes identifiziert werden.
Von daher kann die Intervall-Position eines Knotenpunktes mittels der Gesamtheit der Intervall-Längen der vorhergehenden (nachfolgenden) Knotenpunkte berechnet werden. Ferner kann die positionale Beziehung zwischen den Knotenpunkten mittels der Beziehung zwischen den Knotenpunkten dargestellt werden, wobei die Position eines jeden Knotenpunktes über die partielle Intervall-Länge anderer Knotenpunkte berechnet werden können. Das bedeutet, dass ein Abändern in einem Teil eines Intervalls sich lediglich auf den abgeänderten Knotenpunkt und einem oder mehreren Knotenpunkten in dem Pfad von diesem Knotenpunkt zu dem Hauptverzeichnisknoten auswirkt, so dass die Abänderungsprozedur vereinfacht wird. Genauer gesagt, selbst wenn die Länge eines Intervalls abgeändert wird, ist die erforderliche Datenverarbeitungszeit näherungsweise proportional zu dem Logarithmus der Anzahl der Intervalle.

[1-2-2. Intervall-Suchprozess]

Fig. 4 ist ein Flussdiagramm, welches die von dem Datenverarbeitungssystem der ersten Ausführungsform verwendete Suchprozedur zeigt. Um das Intervall, zu dem eine spezifizierte Position innerhalb der Codekette gehört, während der Suche oder anderer Verarbeitungen zu identifizieren, führt die Intervall-Sucheinrichtung 33 die folgende Prozedur durch während der aktuelle Knotenpunkt, der mittels des Zeigers angezeigt wird, von dem Hauptverzeichnisknoten zu Knotenpunkten niedrigerer Ebene (Schritt 241) bewegt wird, eine Ebene pro Zeit.
Die Intervall-Sucheinrichtung 33 berechnet den Bereich des aktuellen Knotenpunktes basierend auf den Intervall-Längen des aktuellen Knotenpunktes und der Knotenpunkte niedrigerer Ebenen (Schritt 242), und vergleicht den berechneten Bereich mit der spezifizierten Position. Falls die spezifizierte Position dem berechneten Bereich vorangeht (Schritt 243), bewegt die Intervall-Sucheinrichtung 33 den aktuellen Knotenpunkt zu dem vorhergehenden Knotenpunkt (Schritt 244); falls die spezifizierte Position dem berechneten Bereich nachfolgt (Schritt 245), bewegt die Intervall-Sucheinrichtung 33 den aktuellen Knotenpunkt zu dem nachfolgenden Knotenpunkt (Schritt 246); falls die spezifizierte Position in dem berechneten Bereich enthalten ist (Schritt 247), befindet sich der spezifizierte Bereich in dem aktuellen Knotenpunkt (Schritt 248).
Diese Prozedur wird wie folgt ausgeführt: Es sei angenommen, die Variable P enthält die spezifizierte Position und die Variable n enthält einen Zeiger, der zu dem aktuellen Knotenpunkt zeigt (von nun an wird der aktuelle Knotenpunkt durch n dargestellt).
Während dieses Prozesses wird die substantiell spezifizierte Position in dem gesamten Baum nicht abgeändert. Jedoch wenn der aktuelle Knotenpunkt sich nach unten bewegt, wird die Darstellung der spezifizierten Position basierend auf der relativen Position des aktuellen Knotenpunktes aktualisiert.
Falls n einen vorhergehenden Knotenpunkt aufweist (von nun als "linker Ableger" bezeichnet) und falls Formel 2 gilt,

[Formel 2]

P ≤ Partielle Intervall-Länge des linken Ablegers von n
ändert die Intervall-Sucheinrichtung 33 den Knotenpunkt n zum linken Ableger von n ab.
Wenn der Knotenpunkt n einen nachfolgenden Knotenpunkt aufweist (von nun an als "rechter Ableger" bezeichnet) und falls Formel 4 gilt,

[Formel 4]

P > (Partielle Intervall-Länge von n - Partielle Intervall-Länge des rechten Ablegers von n)
ändert die Intervall-Sucheinrichtung 33 P zu:

[Formel 6]

P - (Partielle Intervall-Länge von n - Partielle Intervall-Länge des rechten Ablegers von n)
und ändert den Knotenpunkt n in den rechten Ableger von n ab.
Wenn dieser Prozess beendet ist und wenn Formel 7 und Formel 9 gilt,

[Formel 7]

(Partielle Intervall-Länge des linken Ablegers von n) < P

[Formel 9]

P ≤ (Partielle Intervall-Länge von n - Partielle Intervall-Länge des rechten Ablegers von n)
stellt n einen Knotenpunkt dar, der dem Intervall entspricht, welches die spezifizierte Position enthält. Das bedeutet, dass das Intervall des aktuellen Knotenpunktes die spezifizierte Position einschließt, wenn die spezifizierte Position dem Intervall nachfolgt, welches dem aktuellen Knotenpunkt vorhergeht, und wenn die spezifizierte Position innerhalb der Netz-Intervall-Länge des aktuellen Knotenpunktes ist.
Falls n keinen linken Ableger hat und falls Formel 11

[Formel 11]

P ≤ 0
oder falls n keinen rechten Ableger hat und falls Formel 13

[Formel 13]

P > 0
gilt, ist das Intervall, welches die spezifizierte Position enthält, noch nicht gespeichert. Das bedeutet, dass die spezifizierte Position in keinem Intervall enthalten ist, falls es vor dem ersten Knotenpunkt oder hinter dem letzten Knotenpunkt liegt. Dieses kann unabhängig von dem Vorhandensein eines rechten oder linken Ablegers gesagt werden, wenn n den Hauptverzeichnisknoten darstellt.
Im übrigen ist das Intervall, welches durch den wiederhergestellten Knotenpunkt dargestellt wird, gegeben durch: [Spezifizierte Position - (P - Partielle Intervall- Länge des linken Ablegers von n) + Δ(Minimale positionale Einheit) .. Spezifizierte Position + Partielle Intervall-Länge von n - Partielle Intervall-Länge des rechten Ablegers von n - P)].
In dem Binärstrukturbaum in Fig. 2 beispielsweise ist der Knotenpunkt, welcher das Intervall, das die spezifizierte Position 8 enthält, darstellt, mittels des Nachfolgens der Knotenpunkte identifiziert, wie in den Fig. 5, 6 und 7 gezeigt. In dem identifizierten Knotenpunkt stellt n [8 - (3 - 0) + 1 .. 8 + (4 - 0 - 3)] = [6 .. 9] dar (Fig. 7).
Wie bereits beschrieben, vergleicht in dem Datenverarbeitungssystem der ersten Ausführungsform die Intervall-Sucheinrichtung 33 die spezifizierte Position mit dem Bereich des aktuellen Knotenpunktes, während der aktuelle Knotenpunkt nach unten hin, eine Ebene pro Zeit, von dem Hauptverzeichnisknoten bewegt wird. Diese einfache Prozedur identifiziert ein Intervall, welches die spezifizierte Position enthält, was verschiedene Arten von Verarbeitungen, wie etwa das Suchen erleichtert.

[1-2-3. Knotenpunkt-Intervall Identifikationsprozess]

In dieser Ausführungsform ist es ferner möglich, ein Intervall zu identifizieren, welches einem Knotenpunkt entspricht, der spezifiziert ist. Die nachstehend beschriebene Prozedur identifiziert die Position eines Intervalls. Ein rechtes Intervall oder ein linkes Intervall (gesamtes Intervall) bedeutet, dass das spezifizierte Intervall an der rechten oder an der linken Seite des Hauptverzeichnisknoten-Intervalls liegt.
Um ein Knotenpunkt-Intervall zu identifizieren, wird der aktuelle Knotenpunkt sequentiell von dem spezifizierten Knotenpunkt zu seinem Erzeugerknotenpunkt bewegt, bis der Hauptverzeichnisknoten erreicht wird. Während der aktuelle Knotenpunkt bewegt wird, wird entweder die linke Intervall- Länge, welche die Gesamtzahl der Längen der Knotenpunkte ist, die dem spezifizierten Knotenpunkt vorhergehen, oder die rechte Intervall-Länge, welche die Gesamtzahl der Längen der Knotenpunkte ist, die dem spezifizierten Knotenpunkt nachfolgen, erhalten (Ansprüche 3, 22). Fig. 8 ist ein Ablaufdiagramm, welches ein Beispiel einer Prozedur zur Identifizierung des Intervalls, das dem spezifizierten Knotenpunkt entspricht, zeigt.
In dieser Prozedur wird zunächst die partielle Intervall-Länge des linken Ablegers des aktuellen Knotenpunktes, der spezifiziert ist, auf die linke Intervall-Länge festgelegt (Schritt 281). Es sei daran erinnert, dass das linke Intervall (Länge) das gesamte Intervall (Länge) darstellt, das dem spezifizierten Knotenpunkt vorhergeht.
Dann werden die folgenden Schritte solange wiederholt, bis der aktuelle Knotenpunkt zum Hauptverzeichnisknoten wird (Schritt 282). Das bedeutet, dass der aktuelle Knotenpunkt mit dem alten aktuellen Knotenpunkt als den Ablegerknotenpunkt zu seinem Erzeuger bewegt wird (Schritt 283). Zu dieser Zeit wird, wenn der Ablegerknotenpunkt, welcher der alte aktuelle Knotenpunkt war, der rechte Knotenpunkt des aktuellen Knotenpunktes ist (Schritt 284), die Summe aus der Netz- Intervall-Länge des aktuellen Knotenpunktes und der partiellen Intervall-Länge des linken Ablegers des aktuellen Knotenpunktes berechnet (Schritt 286), und die Summe wird zu der linken Intervall-Länge hinzugefügt (Schritt 286).
Es sei darauf hingewiesen, dass die partielle Intervall-Länge eines Knotenpunktes die Gesamtmenge (Intervall-Länge) der Netz-Intervall-Länge der Knotenpunkte darstellt, die in dem an dem Knotenpunkt verwurzelten Sub-Baum enthalten sind. Die Summe aus der Netz-Intervall-Länge des aktuellen Knotenpunktes und der partiellen Intervall-Länge des linken Ablegers des aktuellen Knotenpunktes wird durch die Subtraktion der partiellen Intervall-Längen des rechten Ablegers (der alte aktuelle Knotenpunkt) von der partiellen Intervall-Länge des aktuellen Knotenpunktes berechnet.
Wenn der aktuelle Knotenpunkt zum Hauptverzeichnisknoten wird (Schritt 282), befindet sich das linke Ende des spezifizierten Knotenpunktes unmittelbar links von dem linken Intervall; d. h., er wird durch das Hinzufügen von 1 zu der linken Intervall-Länge berechnet (Schritt 287). Falls ein Intervall mittels einer Fliesskomma-Zahl dargestellt wird, ist der Wert der linken Intervall-Länge das linke Ende des Intervalls. Das rechte Ende des spezifizierten Knotenpunktes wird durch das Zufügen der Netz-Intervall-Länge des spezifizierten Knotenpunktes zur linken Intervall-Länge erhalten (Schritt 288).
Das rechte Intervall des spezifizierten Knotenpunktes (die Gesamtzahl der Intervalle, die dem Intervall nachfolgen, welches dem spezifizierten Knotenpunkt entspricht) beginnt bei der Position, welche dem Wert des rechten Endes des spezifizierten Knotenpunktes nachfolgt (Hinzufügen einer 1), und endet an dem Ende des gesamten Intervalls, das durch den Binärstrukturbaum dargestellt wird. Dieses Ende wird durch den Wert der partiellen Intervall-Länge des Hauptverzeichnisknotens dargestellt.
Fig. 9 ist ein weiteres Beispiel eines Ablaufdiagramms einer Prozedur zur Identifizierung eines Intervalls, das dem spezifizierten Knotenpunkt entspricht. In der in Fig. 8 gezeigten Prozedur wird das linke Intervall bestimmt, welches an der linken Seite des spezifizierten Knotenpunkt-Intervalls liegt, und die rechte Seite des spezifizierten Knotenpunkt- Intervalls wird auf die linken Intervall-Länge basierend berechnet. In der in Fig. 9 gezeigten Prozedur werden die Längen sowohl des rechten Intervalls als auch des linken Intervalls ermittelt, und das Intervall des spezifizierten Knotenpunktes wird als ein Intervall zwischen diesen beiden Intervallen bestimmt.
Bei dieser Prozedur wird der spezifizierte Knotenpunkt zunächst als aktueller Knotenpunkt mit der partiellen Intervall-Länge des linken Ablegers des aktuellen Knotenpunktes, welche die linke Intervall-Länge ist, und mit der partiellen Intervall-Länge des rechten Ablegers des aktuellen Knotenpunktes, welche die rechte Intervall-Länge ist, festgesetzt (Schritt 291). Dann werden die nachfolgenden Schritte solange wiederholt, bis der aktuelle Knotenpunkt zum Hauptverzeichnisknoten wird (Schritt 292).
Der aktuelle Knotenpunkt wird zu seinem Erzeuger mit dem alten aktuellen Knotenpunkt als den Ableger-Knotenpunkt bewegt (Schritt 293). Und, wenn der alte aktuelle Knotenpunkt der rechte Ableger ist (Schritt 295), die Summe aus der Netz- Intervall-Länge des neuen aktuellen Knotenpunktes und der partiellen Intervall-Länge des linken Ablegers des neuen aktuellen Knotenpunktes wird zur linken Intervall-Länge addiert (Schritt 296); wenn der alte aktuelle Knotenpunkt der linke Ableger darstellt (295), wird die Summe aus der Netz- Intervall-Länge des neuen aktuellen Knotenpunktes und aus der partiellen Intervall-Länge des rechten Ablegers des neuen aktuellen Knotenpunktes zur rechten Intervall-Länge addiert (Schritt 297). Die Summe aus der Netz-Intervall-Länge des aktuellen Knotenpunktes und aus der partiellen Intervall-Länge des linken (rechten) Ablegers des aktuellen Knotenpunktes wird berechnet, indem die partiellen Intervall-Längen des rechten (linken) Ablegers von der partiellen Intervall-Länge des aktuellen Knotenpunktes subtrahiert wird.
Wenn der aktuelle Knotenpunkt zum Hauptverzeichnisknoten wird (Schritt 292), dann ist das Intervall des spezifizierten Knotenpunktes als das Intervall zwischen dem linken und dem rechten Intervall identifiziert (Schritt 298). Das rechte Ende des spezifizierten Knotenpunktes kann durch die Subtraktion der rechten Intervall-Länge von der partiellen Intervall-Länge des Hauptverzeichnisknotens berechnet werden.
In der ersten Ausführungsform wird die gesamte Intervall-Länge eines vorhergehenden (nachfolgenden) Knotenpunktes sequentiell aufaddiert, wenn sich, wie obig beschrieben, der aktuelle Knotenpunkt von dem spezifizierten Knotenpunkt zum Hauptverzeichnisknotenpunkt bewegt. Dieser Prozess ermittelt die Position des spezifizierten Knotenpunktes, indem die Intervall-Längen der Knotenpunkte, welche rechts oder links zu dem spezifizierten Knotenpunkt liegen, verwendet werden. Diese in der sechsten Ausführungsform vorgesehene einfache Prozedur erlaubt es, die Position des spezifizierten Knotenpunktes zu identifizieren, was es ermöglicht, verschiedene Arten von Verarbeitungen durchzuführen (Ansprüche 3, 25).
Fig. 10 ist ein funktionelles Blockdiagramm, welches ein Beispiel einer Geräteteilekonfiguration (hardware configuration) für den Einsatz in der obig beschriebenen Suche zeigt. Das bedeutet, es gibt genauso viele Informationsbereiche wie Knotenpunkte, wobei jeder Bereich aus einem Zeiger-Speicherbereich P und dem partiellen Intervall- Längen-Speicherbereich L besteht. Diese Bereiche sind in einer Anordnung mit fixierten Längen enthalten. Die Knotenpunkte sind mittels bidirektionalen Zeigern verknüpft, was es erlaubt, die Zeiger-Speicherbereiche mit dem Verweis zu versehen, bidirektional zu arbeiten.
Um ein Suchen durchzuführen, ordnet der Steuerungsbereich C zur Referenz jedem Knotenpunkt Zeiger zu und der Betriebsabschnitt A greift auf die partielle Intervall-Länge eines jeden Knotenpunktes zu, um die Intervall-Längen zu berechnen. Der Zeiger oder die Speicheradresse des aktuellen Knotenpunktes ist in dem aktuellen Register CR gespeichert. Informationen über die Knotenpunkte, wie etwa Informationen über einen alten Knotenpunkt, nachdem der aktuelle Knotenpunkt bewegt worden ist, sind in dem Hilfsregister SR gespeichert. Das Intervall-Längen-Register LR wird verwendet, um, falls erforderlich, die partiellen Intervall-Längen zu berechnen.
Geräteteile, die diese Konfiguration aufweisen, können in verschiedenen Arten von nachfolgend beschriebenen Prozessen verwendet werden.

[1-2-4. Binärstrukturbaum Aktualisierungsprozess]

Wenn ein Intervall abgeändert wird, aktualisiert die Binärstrukturbaum-Aktualisierungseinrichtung 34 den Binärstrukturbaum 31 abhängig von dem Inhalt der Abänderung. Da in der ersten Ausführungsform der Binärstrukturbaum 31 in dieser Weise abgeändert wird, wenn ein Intervall sich verändert, bedarf es nicht, den Binärstrukturbaum 31 neu zu generieren.
Wenn in der ersten Ausführungsform die Länge eines Intervalls in der Codekette abgeändert wird, ändert die Intervalllängen- Änderungseinrichtung 41 die entsprechende Intervall-Länge in dem Binärstrukturbaum 31 ab. Wenn ein Intervall von der Codekette entfernt wird, entfernt die Entfernungseinrichtung 42 den Knotenpunkt von dem Binärstrukturbaum 31, welcher dem entfernten Intervall entspricht. Wenn zu der Codekette ein Intervall hinzugefügt wird, fügt die Hinzufügungseinrichtung 43 den Knotenpunkt zu dem Binärstrukturbaum 31 hinzu, welcher dem hinzugefügten Intervall entspricht.
Bei der ersten Ausführungsform aktualisiert die Intervalllängen-Änderungseinrichtung, die Entfernungseinrichtung oder die Hinzufügungseinrichtung den Binärstrukturbaum 31, wenn eine Intervall-Länge abgeändert, ein Intervall gelöscht oder hinzugefügt wird. Eine Kombination dieser Einrichtungen erlaubt es, komplexe Verarbeitungen durchzuführen; beispielsweise können die Intervalle in einer Codekette ausgetauscht werden.

[1-2-4-1. Intervall-Längen Änderungsprozess]

Wenn die Länge eines Intervalls abgeändert ist, wird die partielle Intervall-Länge eines jeden Knotenpunktes von diesem Knotenpunkt zu dem Hauptverzeichnisknoten mittels des abgeänderten Wertes abgeändert.
Fig. 11 ist ein Ablaufdiagramm, welches die Prozedur zum Abändern einer Intervall-Länge zeigt: Gemäß der Darstellung in dieser Figur wird der Zielknotenpunkt zunächst als aktueller Knotenpunkt gesetzt (Schritt 311). Danach wird der aktuelle Knotenpunkt in Richtung des Hauptverzeichnisknotens bewegt (Schritt 312), solange, bis er der Hauptverzeichnisknoten wird (Schritt 314), während die partielle Intervall-Länge eines jeden aktuellen Knotenpunktes mittels eines spezifizierten Abänderungswertes anwächst oder abnimmt.
Das bedeutet, dass, selbst wenn die Länge eines Intervalls in der ersten Ausführungsform abgeändert wird, lediglich die Knotenpunkte von diesem Knotenpunkt bis zu dem Hauptverzeichnisknoten abgeändert werden brauchen. Entgegen einem herkömmlichen System wird bei dem Datenverarbeitungssystem in der sechsten Ausführungsform die Anforderung beseitigt, all die Knotenpunkte zu bewegen, die den Intervallen entsprechen, welche den abgeänderten Knotenpunkt nachfolgen, was die Datenverarbeitungseffizienz steigert.
Wenn beispielsweise das Intervall mit der Länge von 4 ([6..9]) in ein Intervall mit der Länge 2 ([6..7]) gemäß dem in Fig. 22 gezeigten Beispiels abgeändert wird, werden die partiellen Intervall-Längen der Knotenpunkte B, C und D gemäß der Darstellung in Fig. 32 um 2 vermindert. Falls das Bestreben bestand, einen Knotenpunkt zu suchen, der dem Intervall entspricht, das die Position 8 enthält (Fig. 33 und 34), beträgt das Ergebnis danach Knotenpunkt D und nicht Knotenpunkt C. Das von dem Knotenpunkt D dargestellte Intervall ist [8 - (3 - 2) + 1 .. 8 + (9 - 1 - 3)] = [8 .. 13].
Die nachfolgenden Abschnitte beschreiben die Prozedur zum Hinzufügen und Entfernen eines Intervalls. Fig. 15 ist ein Ablaufdiagramm, welches die Prozedur zum Hinzufügen und Entfernen eines Intervalls in der ersten Ausführungsform zeigt.

[1-2-4-2. Intervall Hinzufügungsprozess]

Wenn ein Intervall hinzugefügt wird, fügt die Hinzufügungseinrichtung 43 zu dem Binärstrukturbaum 31 für ein Intervall, das hinzugefügt werden muss, ein Knotenpunkt hinzu (Schritt 351), stellt die Knotenpunkt-Verbindungssequenz (Schritt 352) und die Intervall-Länge eines jeden Knotenpunktes ein (Schritt 353). In der ersten Ausführungsform stellt die Hinzufügungseinrichtung 43 die Intervall-Längen ein, um die Integrität des Binärstrukturbaumes 31 sicherzustellen.
Sämtliche bekannte Verfahren zum Hinzufügen eines Knotenpunktes können kompatibel verwendet werden. In Fig. 2 beispielsweise wird der neue Knotenpunkt in einem der in den Fig. 16, 17 und 18 gezeigten Wege hinzugefügt, wenn ein Intervall [10..12] mit der Länge von 3 vor dem Intervall [10..15] hinzugefügt wird, wobei die Intervalle [10..15] und [16..16] zu den Intervallen [13..18] bzw. [19..19] bewegt werden.
Um die Intervall-Länge einzustellen, findet die Hinzufügungseinrichtung 43 die Summe der partiellen Intervall- Längen der Ableger (0 falls kein Ableger existiert) und die Länge des hinzuzufügenden Intervalls auf und verwendet das Ergebnis als die partielle Intervall-Länge des Knotenpunktes. Auch fügt die Hinzufügungseinrichtung 43 die Länge des neuen Intervalls zu jedem Knotenpunkt in dem Pfad von dem Erzeuger des neuen Knotenpunktes zu dem Hauptverzeichnisknoten hinzu.
In der ersten Ausführungsform sind die Intervall-Längen einfach durch das Hinzufügen der Länge des neuen Intervalls zu jedem Knotenpunkt auf dem Pfad von dem Erzeuger des hinzugefügten Knotenpunktes zu dem Hauptverzeichnisknoten eingestellt. Fig. 19 zeigt den Binärstrukturbaum 31, zu welchem ein Knotenpunkt an der Position β gemäß Fig. 17 hinzugefügt wurde.

[1-2-4-3. Intervall Entfernungsprozess]

Beim Entfernen eines Intervalls entfernt die Entfernungseinrichtung 42 von dem Binärstrukturbaum 31 den Knotenpunkt, welcher dem Intervall, das entfernt werden muß, entspricht, die Entfernungseinrichtung stellt die Verbindung zwischen den Knotenpunkten her und, falls notwendig (Schritt 354), stellt es die partiellen Intervall-Längen ein (Fig. 35 /Schritt 353). In der ersten Ausführungsform stellt die Entfernungseinrichtung 42 die Verbindungssequenz der Knotenpunkte und die Intervall-Längen ein, um die Integrität des Binärstrukturbaumes 31, wie etwa die Sequenz der verbleibenden Intervalle, zu gewähren.
Sämtliche bekannte Verfahren zum Entfernen und Einstellen können kompatibel verwendet werden. Wenn beispielsweise der Knotenpunkt D von dem Binärstrukturbaum 31 in Fig. 19 entfernt ist, kann die Struktur nach der Entfernung aussehen wie in Fig. 20 oder Fig. 21 gezeigt. Die nachfolgende Diskussion ist auf den Fall gerichtet, wo nur Knotenpunkte, dessen Erzeugerknotenpunkte nach der Entfernung abgeändert wurden, die Ablegerknotenpunkte des entfernten Knotenpunktes darstellen. In anderen Fällen wird der Binärstrukturbaum, falls notwendig, während der Struktureinstellung gemäß der nachstehenden Beschreibung vor oder nach der Knotenpunktentfernung abgeändert.
Als erstes wird für jeden Knotenpunkt auf dem Pfad von dem Erzeuger des entfernten Knotenpunktes zu dem Hauptverzeichnisknoten (nur B in Fig. 20) die partielle Intervall-Länge durch (Partielle Intervall-Länge des gelöschten Knotenpunktes) - (Partielle Intervall-Länge des dem gelöschten Knotenpunkt vorhergehenden Knotenpunktes (linker Ableger)) - (Partielle Intervall-Länge des dem gelöschten Knotenpunkt nachfolgenden Knotenpunktes (rechter Ableger)) reduziert, was die Netzintervall-Länge des entfernten Knotenpunktes darstellt.
Dann wird für jeden Knotenpunkt des Pfades beginnend bei dem Knotenpunkt, welcher der Erzeugerknotenpunkt eines vorhergehenden Ablegers des entfernten Knotenpunktes und nicht der Erzeugerknotenpunkt des entfernten Knotenpunktes darstellt (zum Beispiel X), und bei einem anderen Ableger endend (dessen Erzeuger die vorhergehenden Erzeuger des entfernten Knotenpunktes sind) (zum Beispiel C), die partielle Intervall- Länge des ehemaligen Ablegers (zum Beispiel E) zur partiellen Intervall-Länge hinzugefügt.
Fig. 22 zeigt den Binärstrukturbaum 31, von dem ein Knotenpunkt entfernt wurde.

[1-2-4-4. Struktureinstellungs-Prozess]

Beim Hinzufügen oder Entfernen eines Intervalls, ändert die Struktureinstellungseinrichtung 45 die Verbindungssequenz der Knotenpunkte, um die Balance der Anzahl der Knotenpunkte in dem Binärstrukturbaum 31 sicherzustellen (Schritt 355).
Dieses Struktureinstellungsverfahren vermeidet, dass ein bestimmter Teil des Binärstrukturbaumes 31 anwächst, indem eine Vielzahl von Pfaden erstellt wird, wobei jeder Pfad von dem Hauptverzeichnisknoten zu einem Knotenpunkt läuft und in etwa gleichlang ist. Auf diese Weise vermeidet die Einrichtung, dass die Datenverarbeitungszeit anwächst, nur weil der zugehörige Pfad zu lang ist, von daher werden verschiedene Arten von Datenverarbeitungen, wie etwa das Suchen oder Aktualisieren effizienter. Ein anderes Struktureinstellungsverfahren beseitigt Variationen in den Verarbeitungszeiten beim Suchen, Hinzufügen und Entfernen für einen Binärstrukturbaum.
Die Struktureinstellung ist bei der Knotenpunktentfernung, Hinzufügung oder Verweisung notwendig. Eine Vielzahl von Struktureinstellungsverfahren sind bekannt. Jedes dieser kann benutzt werden. Die partiellen Intervall-Längen sollten gemäß dem zu verwendenden Struktureinstellungsverfahren eingestellt werden, wenn die Baumstruktur abgeändert ist. Die Länge eines Pfades von dem Hauptverzeichnisknoten zu einem Knotenpunkt ist gewöhnlich mittels der Struktureinstellung so gewählt, dass sie proportional zu dem Logarithmus der gesamten Anzahl von Knotenpunkten ist. Aus diesem Grund ist die Zeit, die für eine Verarbeitung notwendig ist, wie etwa das Suchen und Einstellen der Intervall-Länge und Struktur, in etwa proportional zu dem Logarithmus der Gesamtanzahl von Intervallen.
Die Rotation, Doppelrotation (Zick-Zick) oder Doppelrotation (Zick-Zack), welche die Knotenpunktesequenz und die Struktur eines spezifizierten Bereichs des Binärstrukturbaumes 31 aufrechterhält, wird bei der Struktureinstellungsprozedur als eine Operationseinheit verwendet. Die gültige Struktureinstellungsprozedur besteht aus diesen Einheiten.
Das Nachfolgende zeigt ein Beispiel, in welchem eine herkömmliche Struktureinstellungsprozedureinheit zu dem ganzen oder einem Teil eines Pfades von dem Hauptverzeichnisknoten zu einem Knotenpunkt angewandt wird. Das Durchführen einer Rotation an dem Binärstrukturbaum 31 in Fig. 23 resultiert in dem Binärstrukturbaum 31 gemäß Fig. 24. Das Durchführen einer Doppelrotation (Zick-Zick) an dem Binärstrukturbaum 31 in Fig. 25 resultiert in dem in Fig. 26 gezeigten Binärstrukturbaum 31. Das Durchführen der Doppelrotation (Zick-Zack) an dem Binärstrukturbaum 31 in Fig. 27 resultiert in dem Binärstrukturbaum 31, der in Fig. 28 gezeigt ist.
Es sei angenommen, dass für jeden Knotenpunkt n die partielle Intervall-Länge vor der Abänderung S(n) und die partielle Intervall-Länge nach der Abänderung SS(n) sei. Die partielle Intervall-Länge SS(n), welche in jedem Knotenpunkt nach Ausführung einer Operationseinheit gesetzt werden muß, wird wie folgt berechnet; basierend auf der partiellen Intervall- Länge S(n), bevor die Operationseinheit ausgeführt wird. Es sei zu beachten, dass die Knotenpunkte mit der Ausnahme von X, Y und Z nicht abgeändert werden müssen.
Die Berechnung für die Rotation wird wie folgt durchgeführt:

[Formel 15]

SS(X) = S(X) - S(Y) + S(B)
SS(Y) = S(X)
Die Berechnung für die Doppelrotation (Zick-Zick) wird wie folgt durchgeführt:

[Formel 16]

SS(X) = S(X) - S(Y) + S(B)
SS(Y) = S(X) - S(Z) + S(C)
SS(Z) = S(X)
Die Berechnung für die Doppelrotation (Zick-Zack) wird wie folgt durchgeführt:

[Formel 17]

SS(X) = S(X) - S(Y) + S(B)
SS(Y) = S(Y) - S(Z) + S(C)
SS(Z) = S(X)
Die partielle Intervall-Länge kann ebenso berechnet werden, nachdem die Netzintervall-Länge von X, Y und Z berechnet wurden. Die Netzintervall-Länge T(n) für einen Knotenpunkt n wird wie folgt berechnet:

[Formel 18]

Für die Rotation:
T(X) = S(X) - S(Y) + S(A)
T(Y) = S(Y) - S(B) - S(C)
SS(X) = T(X) + S(A) + S(B)
SS(Y) = T(Y) + SS(X) + S(C)

[Formel 19]

Für Zick-Zick:
T(X) = S(X) - S(Y) - S(A)
T(Y) = S(Y) - S(Z) - S(B)
T(Z) = S(Z) - S(D) - S(C)
SS(X) = T(X) + S(A) + S(B)
SS(Y) = T(Y) + SS(X) + S(C)
SS(Z) = T(Z) + SS(Y) + S(D)

[Formel 20]

Für Zick-Zack:
T(X) = S(X) - S(Y) - S(A)
T(Y) = S(Y) - S(Z) - S(D)
T(Z) = S(Z) - S(C) - S(B)
SS(X) = T(X) + S(A) + S(B)
SS(Y) = T(Y) + S(C) + S(D)
SS(Z) = T(Z) + SS(X) + SS(Y)
Bei der ersten Ausführungsform wird die Struktureinstellung gemäß dem Status des Binärstrukturbaumes 31 durchgeführt, da eine Vielzahl von Verarbeitungsarten kombiniert sind, um die Struktur eines spezifizierten Bereiches des Binärstrukturbaumes 31 abzuändern.
Genauer gesagt existieren zwei Struktureinstellungsverfahren. Ein Verfahren verhindert, dass ein Binärstrukturbaum vertikal anwächst, um die Zeit für eine Operation innerhalb einer spezifizierten Zeit zu halten (z. B. rot-schwarz Baum/red- black tree). Das andere Verfahren reduziert die gesamte Zeit für eine Operation (d. h., es reduziert die Durchschnittszeit für eine Operation), obwohl das Verfahren die Zeit für eine Operation nicht innerhalb einer spezifizierten Zeit hält (z. B. Ausweitungsbaum/splay tree). In beiden Fällen kann ein Abändern der Struktur durch eine Kombination der oben beschriebenen Prozessarten (Operationseinheiten) durchgeführt werden.

[1-2-4-5. Beispiel für Struktureinstellung]

Das Nachfolgende zeigt einen Ausweitungsbaum (Ausweitung/splaying) als ein Beispiel für die Struktureinstellung (Anspruch 17) und beschreibt, wie eine Ausweitung die Struktur eines Binärstrukturbaumes abändert und wie die partielle Intervall-Länge eines jeden Knotenpunktes während dieses Abänderns geändert wird.
Eine Ausweitung ändert die Struktur eines Binärstrukturbaumes ab, so dass sämtliche einzelnen Knotenpunkte (Ziel- Knotenpunkte) Hauptverzeichnisknoten werden (Referenz: Robert Endre Tarjan. "4.3 Self-Adjusting binary trees (Seiten 53-56)" in Data Structures and Network Algorithmus). Die Ausweitung wird gewöhnlich zur Knotenpunkte Suche, Hinzufügung oder. Entfernung angewandt; im einzelnen wird sie an einem Knotenpunkt angewandt, wo eine Schlüsselanpassungsbedingung (key match condition) während der Suche entsteht (oder an einem Knotenpunkt, der als letzter aufgerufen wurde, wenn keine Schlüsselanpassungsbedingung entsteht), sie wird an einem Knotenpunkt angewandt, der während der Knotenpunkthinzufügung hinzugefügt wurde, oder sie wird an dem Erzeugerknotenpunkt eines Knotenpunktes angewandt, welcher während der Knotenpunktentfernung entfernt wurde.
Während der Ausweitung wird eines der Rotation, Doppelrotation (Zick-Zick) und Doppelrotation (Zick-Zack), welches die Bedingung erfüllt, wiederholt angewandt, mit dem Zielknotenpunkt als den Knotenpunkt, der am weitesten von dem Hauptverzeichnisknoten entfernt ist, bis der Zielknotenpunkt der Hauptverzeichnisknoten wird.
Fig. 29 zeigt ein Beispiel eines Binärstrukturbaumes. In dieser Figur deutet ein Kreis einen Knotenpunkt an und ein Dreieck einen Sub-Baum, dessen Hauptverzeichnisknoten mittels eines Kreises bezeichnet ist. Binärstrukturbaumdaten wie diese sind in einem Listenformat strukturiert, in dem die Datengegenstände in den Knotenpunkten mittels Zeiger verbunden sind. Fig. 30 ist ein konzeptionelles Diagramm, welches das Format von Daten zeigt, die in jedem Knotenpunkt enthalten sind. Gemäß dieser Figur weisen die in jedem Knotenpunkt enthaltenen Daten einen Zeiger zu dem rechten Ableger, einen Zeiger zu dem linken Ableger, einen Zeiger zu einem Knotenpunkt höherer Ebene (Erzeuger) und die partielle Intervall-Länge des Knotenpunktes auf.
Fig. 31 ist ein konzeptionelles Diagramm, welches zeigt, wie Datengegenstände in den Knotenpunkten, welche ein Teil des in Fig. 29 gezeigten Binärstrukturbaumes sind, mittels Zeiger verbunden sind.
Gemäß dieser Figur wird die partielle Intervall-Länge eines jeden Knotenpunktes (a, b, c, A, B, C) mittels eines Symbols dargestellt, welches unmittelbar von einer Zahl gefolgt wird, wie etwa a1, b1, c1, A1, B1 und C1. Wenn die partielle Intervall-Länge a1 aktualisiert ist, folgt dem Symbol a ein neuer Index, wie etwa a2 oder a3.
Das Nachfolgende zeigt ein Beispiel einer Ausführung der Ausweitung bei einem in Fig. 29 gezeigten Knotenpunkt a. Die Netzintervall-Länge des Knotenpunktes a vor der Ausweitung wird durch die Subtraktion der partiellen Intervall-Länge (F1) des Knotenpunktes F, welcher der rechte Ableger des Knotenpunktes a ist, und der partiellen Intervall-Länge (E1) des Knotenpunktes E, welcher der linke Ableger des Knotenpunktes a ist, von der partiellen Intervall-Länge des Knotenpunktes a (a1) wie im folgenden gezeigt berechnet.

[Formel 21]

a1 - F1 - E1
Während der Ausführung der Ausweitung, wird zunächst die Doppelrotation (Zick-Zick) an die Knotenpunkte a, b, c, E und D angewandt. Diese Operation ersetzt den Knotenpunkt a mit dem Knotenpunkt c und bewegt den Knotenpunkt a zu der Position des rechten Ablegers des Knotenpunktes d. Fig. 32 zeigt, wie der Binärstrukturbaum nach der Doppelrotation (Zick-Zick) aussieht.
Diese Operation ändert die partiellen Intervall-Längen der Knotenpunkte c, b und a, welche mittels dick gezeichneten Kreisen indiziert sind wie folgt:

[Formel 22]

c2 = c1 - b1 + D1.
b2 = c1 - a1 + E1
a2 = c1
Wenn die Ausweitung angewandt wird, wird der Binärstrukturbaum restrukturiert, indem die Zeiger abgeändert werden, welche die Datengegenstände verknüpfen, die in den Knotenpunkten enthalten sind. Fig. 33 zeigt, wie die Zeiger in den Datengegenständen des Knotenpunktes d und die Knotenpunkte niedrigerer Ebene in Fig. 31, welche gemäß der Fig. 32 restrukturiert wurden, verknüpft sind. In dieser Figur wurde der Knotenpunkt a, welcher der rechte Ableger des Knotenpunktes d ist, und die Knotenpunkte niedrigerer Ebene abgeändert, während der Knotenpunkt B, welcher der linke Ableger des Knotenpunktes d ist, nicht abgeändert wurde.
Dann wird die Doppelrotation (Zick-Zack) an die Knotenpunkte a, d, e, F und b angewandt. Diese Operation ersetzt den Knotenpunkt a mit dem Knotenpunkt e und bewegt den Knotenpunkt. a zu der Position des rechten Ablegers des Knotenpunktes f. Fig. 34 zeigt, wie der Binärstrukturbaum nach einer Doppelrotation (Zick-Zack) ausschaut, nachdem diese an den in Fig. 32 gezeigten Binärstrukturbaum angewandt wurde.
Diese Operation ändert die partiellen Intervall-Längen der Knotenpunkte e, d und a, welche durch fett gezeichnete Kreise indiziert sind, wie folgt ab:

[Formel 23]

e3 = e1 - d1 + F1
d3 = d1 - a2 + b2
a3 = e1
Dann wird die Doppelrotation (Zick-Zack) an die Knotenpunkte a, f, g und e angewandt. Diese Operation ersetzt den Knotenpunkt a mit dem Knotenpunkt g und bewegt den Knotenpunkt a zu der Position des linken Ablegers des Knotenpunktes h. Fig. 35 zeigt, wie der Binärstrukturbaum ausschaut, nachdem die Doppelrotation (Zick-Zack) an dem in Fig. 34 gezeigten Binärstrukturbaum angewandt wurde.
Diese Operation ändert die partiellen Intervall-Längen der Knotenpunkte g, f und a, welche durch fett gezeichnete Kreise indiziert sind, wie folgt ab:

[Formel 23]

g4 = g1 - f1 + e3
f4 = f1 - a3 + d3
a4 = g1
Letztendlich wird die Rotation an die Knotenpunkte a, h und g angewandt. Diese Operation ersetzt den Knotenpunkt a mit dem Knotenpunkt h und bewegt den Knotenpunkt a zu der Position des Hauptverzeichnisknotens. Fig. 36 zeigt, wie der Binärstrukturbaum ausschaut, nachdem die Rotation an dem in Fig. 35 gezeigten Binärstrukturbaum angewandt wurde.
Diese Operation ändert die partiellen Intervall-Längen der Knotenpunkte h und a, die durch fett gezeichnete Kreise indiziert sind, wie folgt ab:

[Formel 25]

h5 = h1 - a4 + g4
a5 = h1
In diesem Beispiel bewegt die Ausführung der Ausweitung den Zielknotenpunkt a zu dem Hauptverzeichnisknoten und reduziert gleichzeitig die Länge eines Pfades von dem Knotenpunkt b, c, d, e, f oder g, welche auf dem Pfad von dem Zielknotenpunkt a zu dem alten Hauptverzeichnisknoten h lagen, zu dem Hauptverzeichnisknoten, und ermöglicht es dadurch, verschiedene Arten von Operationen an diesem Binärstrukturbaum sehr schnell auszuführen (Anspruch 17). Ein Vergleich des Binärstrukturbaumes vor der Ausweitung (Fig. 29) mit dem Binärstrukturbaum nach der Ausweitung (Fig. 36) zeigt an, dass die Länge eines Pfades von einem jeden Knotenpunkt zu dem Hauptverzeichnisknoten, wie im folgenden gezeigt, abgeändert wurde.
Während der Durchführung dieser Ausbreitung wird die partielle Intervall-Länge eines jeden Knotenpunktes wie nachstehend berechnet, basierend auf der partiellen Intervall-Länge eines jeden Knotenpunktes vor der in Fig. 29 gezeigten Ausbreitung. Für Knotenpunkt b gilt:

[Formel 26]

b2 = c1 - a1 + E1
Für Knotenpunkt c gilt:

[Formel 27]

c2 = c1 - b1 + D1
Für Knotenpunkt d gilt:

[Formel 28]

d3 = d1 - a2 + b2
Diese Formeln sind wie folgt erweitert:

[Formel 29]

d1 - (c1) + (c1 - a1 + E1)
Terme werden wie folgt eliminiert:

[Formel 30]

d1 - a1 + E1
Für den Knotenpunkt e gilt:

[Formel 31]

e3 = e1 - d1 + F1
Für den Knotenpunkt f gilt:

[Formel 32]

f4 = f1 - a3 + d3
Diese Formeln werden wie folgt erweitert:

[Formel 33]

f4 = f1 - (e1) + (d1 - a1 + E1)
Die Formel wird wie folgt abgeändert:

[Formel 34]

f4 = f1 - e1 + d1 - a1 + E1
Ähnlich für den Knotenpunkt g:

[Formel 35]

g4 = g1 - f1 + e3

[Formel 36]

g4 = g1 - f1 + e1 - d1 + F1
Daher gilt für Knotenpunkt h:

[Formel 37]

h5 = h1 - a4 + g4
Diese Formel wird wie folgt erweitert:

[Formel 38]

h5 = h1 - (g1) + (g1 - f1 + e1 - d1 + F1)
Terme werden wie folgt eliminiert:

[Formel 39]

h5 = h1 - f1 + e1 - d1 + F1
Die Netzintervall-Länge eines Knotenpunktes nach der Ausweitung wird durch die Subtraktion der partiellen Intervall-Länge (h5) des Knotenpunktes h, welcher der rechte Ableger des Knotenpunktes a ist, und der partiellen Intervall- Länge (f4) des Knotenpunktes f, welcher der linke Ableger des Knotenpunktes a ist, von der partiellen Intervall-Länge (a5) des Knotenpunktes a berechnet:

[Formel 40]

a5 - h5 - f4
Diese Formel wird wie folgt erweitert:

[Formel 41]

h1 - (h1 - f1 + e1 - d1 + F1) - (f1 - e1 + d1 - a1 + E1)
Terme werden wie folgt eliminiert:

[Formel 42]

a1 - F1 - E1
Es sei darauf hingewiesen, dass diese Formel äquivalent zur Formel 21 ist, welche die Netzintervall-Länge vor der Ausbreitung angibt.
Umgekehrt ergibt sich für die Summe der Längen der Intervalle zur Linken des Knotenpunktes a in Fig. 29, wo der Binärstrukturbaum vor der Ausbreitung gezeigt ist, wie folgt:

[Formel 43]

E1 + (b1 - a1) + (c1 - b1) + (d1 - c1) + (f1 - e1)
Terme werden wie folgt eliminiert:

[Formel 44]

E1 - a1 + d1 - e1 + f1
Dieses ist gleich der partiellen Intervall-Länge (f4) des Knotenpunktes f nach der Ausbreitung, was anzeigt, dass die relative Position des Intervalls des Knotenpunktes a nicht durch das Ausbreiten beeinträchtigt wird.

[1-2-4-6. Anwendung der Ausbreitung]

Das oben beschriebene Ausbreiten erlaubt es, die folgende Prozedur für verschiedene Arten der bereits beschriebenen Verarbeitung zu benutzen. Zunächst bewegt das Ausführen des Ausbreitens am Binärstrukturbaum den spezifizierten Knotenpunkt zu dem Hauptverzeichnisknoten (Anspruch 21), wenn ein Intervall identifiziert wird, das einem spezifizierten Knotenpunkt entspricht.
Dies macht es einfach, den spezifizierten Knotenpunkt, welcher nun der Hauptverzeichnisknoten ist, zu identifizieren, weil die Anfangsposition und die Endposition wie folgt identifiziert sind. Wenn die linksseitige Endposition des gesamten Intervalls 0 ist, ist die Anfangsposition die Position, welche unmittelbar der partiellen Intervall-Länge des linken Ablegers des spezifizierten Knotenpunktes folgt, und die Endposition ist die Position, welche dem Wert entspricht, der sich durch die Subtraktion der partiellen Intervall-Länge des rechten Ablegers des spezifizierten Knotenpunktes von der partiellen Intervall-Länge des spezifizierten Knotenpunktes ergibt.
Beim Abändern der Intervall-Länge wird die Ausbreitung an den Knotenpunkt, dessen Intervall-Länge abgeändert werden muss, angewandt, um den Knotenpunkt zum Hauptverzeichnisknotenpunkt zu machen. Dann wird die partielle Intervall-Länge des Knotenpunktes vergrößert oder verkleinert (Anspruch 8). Diese Prozedur beseitigt die Notwendigkeit, die partielle Intervall- Länge eines Knotenpunktes, der nicht ein Hauptverzeichnisknoten ist, abzuändern, was die Verarbeitung einfacher gestaltet.
Beim Hinzufügen eines Knotenpunktes und Einstellen der zugehörigen partiellen Intervall-Längen wird die Ausbreitung an den Knotenpunkten angewandt, die unmittelbar vor und hinter dem Knotenpunkt, welcher hinzugefügt werden muss, um diese, einer nach dem anderen, zum Hauptverzeichnisknotenpunkt zu machen. Dann ist der unmittelbar vor dem hinzuzufügenden Knotenpunkt befindliche Knotenpunkt der linke Ableger und der Knotenpunkt, welcher dem hinzuzufügendem Knotenpunkt unmittelbar nachfolgt, der rechte Ableger. Die partielle Intervall-Länge des hinzuzufügenden Knotenpunktes wird durch das Addieren der Länge des neuen Intervalls zu den partiellen Intervall-Längen des rechten und linken Ablegers berechnet (Anspruch 11).
Beispielsweise zeigt Fig. 37 ein Teil eines Binärstrukturbaumes bevor ein Intervall durch Ausbreitung hinzugefügt wird. Es sei angenommen, dass dieser Teil des Binärstrukturbaumes an einer Nicht- Hauptverzeichnisknotenposition innerhalb eines größeren Binärstrukturbaumes angeordnet sei. Wie in dieser Figur gezeigt, wird ein durch den Knotenpunkt X angezeigtes Intervall unmittelbar hinter dem Intervall hinzugefügt, welches dem Knotenpunkt L entspricht. In diesem Fall sollte er Knotenpunkt X an die linksmöglichste Position in dem Sub-Baum, dessen Hauptverzeichnisknoten der rechte Ableger des Knotenpunktes L ist, als der linke Ableger des linksten Knotenpunktes des durch R angezeigten Sub-Baumes hinzugefügt werden. Folglich ist dieses äquivalent zum Hinzufügen des Knotenpunktes X zwischen den Knotenpunkten L und R.
Zunächst wird das Ausbreiten ausgeführt, um den Knotenpunkt R zum Hauptverzeichnisknotenpunkt zu machen; der Knotenpunkt R ist der Knotenpunkt, welcher unmittelbar nach dem Knotenpunkt X kommen wird. Dann wird die Ausbreitung durchgeführt, um den Knotenpunkt L zum Hauptverzeichnisknotenpunkt zu machen; der Knotenpunkt L ist der Knotenpunkt, welcher unmittelbar vor dem Knotenpunkt X kommen wird. Fig. 38 zeigt, wie der Binärstrukturbaum ausschaut, nachdem die Ausbreitung zweifach für den in Fig. 37 gezeigten Binärstrukturbaum ausgeführt wurde. Dann wird der Knotenpunkt X hinzugefügt mit dem Knotenpunkt L, welcher der linke Ableger und der unmittelbar nachfolgende Knotenpunkt R der rechte Ableger ist. Fig. 39 zeigt, wie der Binärstrukturbaum, nachdem das Intervall mittels Ausbreitung hinzugefügt wurde, ausschaut.
Die partielle Intervall-Länge des Knotenpunktes X in Fig. 39 wird durch das Addieren der Länge des neuen Intervalls zu der partiellen Intervall-Länge des Knotenpunktes L (des Hauptverzeichnisknotenpunktes) in Fig. 58 berechnet, wo der Binärstrukturbaum nach der Ausbreitung gezeigt ist. Die partielle Intervall-Länge des Knotenpunktes L in Fig. 39 wird durch das Subtrahieren der partiellen Intervall-Länge des Knotenpunktes R von der partiellen Intervall-Länge des Knotenpunktes L in Fig. 38 berechnet.
In Fig. 37 kann zunächst die Ausbreitung an dem Knotenpunkt L ausgeführt werden, nachfolgend von der Ausbreitung an dem Knotenpunkt R, um den in Fig. 40 gezeigten Binärstrukturbaum herzustellen, und dann kann der Knotenpunkt X als der rechte Ableger des Knotenpunktes L hinzugefügt werden. Fig. 41 zeigt den Binärstrukturbaum, zu welchem der Knotenpunkt X als der rechte Ableger des Knotenpunktes L hinzugefügt wurde. In diesem Zustand sind die Knotenpunkte auf dem Pfad von den Erzeugern des Knotenpunktes X zu dem Hauptverzeichnisknoten die Knotenpunkte L und R. Dieses bedeutet, dass, wenn die partiellen Intervall-Längen abgeändert werden (Anwachsen), müssen nur diese und wirklich nur diese beiden Knotenpunkte abgeändert werden, was die Prozedur vereinfacht (Anspruch 11).
Diese Operation kann symmetrisch in Fig. 40 angewandt werden, wo der Knotenpunkt X als der rechte Ableger des Knotenpunktes L hinzugefügt werden kann.
Falls in Fig. 40 der Knotenpunkt L keinen rechten Ableger aufweist (d. h., dort existiert kein rechtsseitiger Sub-Baum, dessen Hauptverzeichnisknoten der Knotenpunkt R ist), dann kann der Knotenpunkt X als der rechte Ableger des Knotenpunktes L, wie in Fig. 43 gezeigt, benutzt werden, genauso gut, wie der Knotenpunkt L als den linken Ableger des Knotenpunktes X, wie in Fig. 42 gezeigt, verwendet werden kann.
Zusätzlich, wenn die Knotenpunkthinzufügung und die damit verbundene Einstellung der partiellen Intervall-Längen beteiligt sind, kann die Verarbeitung wie folgt durchgeführt werden. Zunächst wird ein Knotenpunkt, welcher dem neuen Intervall entspricht, mittels eines beliebigen Verfahrens mit der Netzintervall-Länge des Knotenpunktes hinzugefügt werden, der 0 ist. Die partielle Intervall-Länge des hinzugefügten Knotenpunktes ist die Summe der partiellen Intervall-Längen der rechten und linken Ableger. Dann wird die Ausbreitung angewandt, um den hinzugefügten Knotenpunkt zu dem Hauptverzeichnisknoten des Binärstrukturbaumes zu bewegen, und die partielle Intervall-Länge des Knotenpunktes, der zu dem Hauptverzeichnisknoten bewegt wurde, wird durch die Netzintervall-Länge des hinzugefügten Intervalls vergrößert (Anspruch 12). Das bedeutet, dass die partielle Intervall- Länge des Knotenpunktes lediglich einmal während der Ausführung eines gewünschten Hinzufügungs-Algorithmus vergrößert werden muss, was die Verarbeitungsgeschwindigkeit anwachsen lässt.
Die Ausbreitung kann ebenso verwendet werden, um Knotenpunkte (Intervalle) zu entfernen. Um dieses zu tun, muss zunächst der zu löschende Knotenpunkt mittels Ausführung der Ausbreitung zu dem Hauptverzeichnisknoten bewegt werden. Fig. 44 zeigt, wie der Binärstrukturbaum ausschaut, nachdem der Knotenpunkt X, welcher gelöscht werden soll, mittels Ausführung der Ausbreitung zu dem Hauptverzeichnisknoten bewegt wurde. In dieser Figur entspricht der zu löschende Knotenpunkt X dem Intervall unmittelbar vor dem Knotenpunkt R.
Dann wird der Knotenpunkt R unmittelbar hinter dem zu löschenden Knotenpunkt X durch Ausführung der Ausbreitung zu dem Hauptverzeichnisknoten bewegt. Fig. 45 zeigt, wie der Binärstrukturbaum ausschaut, nachdem der Knotenpunkt R, welcher unmittelbar dem zu löschenden Knotenpunkt X folgt, mittels Anwendung der Ausbreitung zu dem Hauptverzeichnisknoten bewegt wurde. Auch wurde die partielle Intervall-Länge des Knotenpunktes R, welcher nun der Hauptverzeichnisknoten darstellt, durch die Netzintervall- Länge des Knotenpunktes X vermindert und der Knotenpunkt X ist letztendlich entfernt (Anspruch 14). Fig. 46 zeigt, wie der Binärstrukturbaum ausschaut, nachdem der Knotenpunkt X entfernt worden ist. Dieses bedeutet, dass lediglich die partielle Intervall-Länge des Hauptverzeichnisknotenpunktes während des Entfernens eingestellt werden muss, was die Verarbeitungsgeschwindigkeit anwachsen lässt.

[1-2-4-7. Abgeglichener Binärstrukturbaum]

Das Nachfolgende erklärt detaillierter, wie die partielle Intervall-Länge eines jeden Knotenpunktes während der Binärstrukturbaum-Einstellung (Abgleich/rebalancing) abgeändert wird, wenn ein abgeglichener (balanced) Binärstrukturbaum, einer der abgeglichenen Suchbäume, als ein Binärstrukturbaum, der Intervalle darstellt, verwendet wird (Referenz: Robert Endre Tarjan. "4.2 Balanced binary trees (Seiten 48-53)" in Data Structures and Network Algorithmus).
Arbeitsschritte zum Abgleich nach dem Einfügen oder Entfernen eines Knotenpunktes sind:
(a) Promotion, Demotion
(b) Einfache Rotation
(c) Doppelte Rotation einschließlich zwei einfacher Rotationen
Das Abgleichen wird durch sequentielles Anwenden einer Kombination dieser Operationen durchgeführt.
Diese Operationen ändern die partielle Intervall-Längen wie folgt ab: (a) Die Promotion und Demotion, welche nicht die Struktur des Binärstrukturbaumes abändern, ändern nicht die partielle Intervall-Länge ab. (b) Die einfache Rotation ist äquivalent zur Rotation in dieser Erfindung. Von daher wird die obig angegebene Formel 15 verwendet, um die partielle Intervall-Länge zu ändern. (c) Die doppelte Rotation ist äquivalent zur Doppelrotation (Zick-Zack) dieser Erfindung. Von daher wird die obig gegebene Formel 17 verwendet, um dieses Abändern der partiellen Intervall-Länge durchzuführen.
Der Abgleich nachdem ein Knotenpunkt eingefügt wurde, erfordert eine Reihe von Promotionsoperationen, welche bei bis zu drei einfachen Rotationen enden (Seite 51 in der oben angegebenen Referenz).
Das Nachfolgende beschreibt ein Beispiel des Abgleichens nach der Einfügung. Der Baum in Fig. 47 wird als ein Beispiel eines abgeglichenen Binärstrukturbaumes verwendet. In diesem Baum weist jeder Knotenpunkt einen Zahlenrang, wie etwa 1 oder 2 gemäß Fig. 47 auf. Der Rang des Knotenpunktes x wird durch rang(x) dargestellt. Der Erzeuger des Knotenpunktes x wird durch p(x) dargestellt und der Erzeuger des Erzeugers des.
Knotenpunktes x (grandparent) ist durch p2(x) dargestellt. Dann muss das Folgende erfüllt sein:
(1) Wenn der Knotenpunkt x den Erzeuger hat:

[Formel 45]

Bedingung 1:

rang(x) ≤ rang(p(x)) ≤ rang(x) + 1
(2) Wenn der Knotenpunkt x den Erzeuger des Erzeugers hat:

[Formel 46]

Bedingung 2:

rang(x) < rang(p2(x))
(2) Wenn der Knotenpunkt x ein externer Knotenpunkt ist:

[Formel 47]

Bedingung 3:

rang(x) = 0
und wenn der Knotenpunkt x den Erzeuger hat:
rang(p2(x)) = 1
Ein Knotenpunkt, dessen Erzeuger einen Rang aufweist, der größer ist als 1 des Knotenpunktes oder der undefiniert ist, wird als ein schwarzer Knotenpunkt (black node) bezeichnet, während ein Knotenpunkt, dessen Erzeuger einen Rang gleich dem des Knotenpunktes aufweist als ein roter Knotenpunkt (red node) bezeichnet wird. In Fig. 47 wird ein schwarzer Knotenpunkt durch eine durchgehende Linie dargestellt, während ein roter Knotenpunkt durch eine gestrichelte Linie dargestellt wird.
Informationen an einem Knotenpunkt in diesem Baum enthalten ein 1-Bitfeld, wo die Farbe des Knotenpunktes gespeichert ist. Fig. 48 zeigt das Informationsformat an einem Knotenpunkt in dem abgeglichenen Binärstrukturbaum-Beispiel. Die Knotenpunkte in diesem Baum sind mittels Zeiger wie in Fig. 33 verknüpft. In der nachfolgenden Diskussion wird die partielle Intervall- Länge eines jeden Knotenpunktes (a, b, c) durch das gleiche Symbol, welches unmittelbar von einer numerischen Fußnote (a1, b1, c1) gefolgt wird, dargestellt. Wenn die partielle Intervall-Länge a1 aktualisiert ist, folgt dem Symbol eine neue numerische Fußnote, wie etwa a2 und a3.
Wenn beispielsweise ein neues (ein Knotenpunkt darstellendes) Intervall x zur Linken des Intervalls eingefügt wird, welches durch den Knotenpunkt f des Baumes in Fig. 47 dargestellt wird, wird der Baum zunächst zu dem einen in Fig. 49 gezeigten Baum geändert.
In diesem Fall wird die partielle Intervall-Länge eines jeden Knotenpunktes wie in Kapitel "1-2-4-2. Intervall Hinzufügungsschritt" erklärt abgeändert:

[Formel 48]

f2 = f1 + x1
g2 = g1 + x1
f2 = e1 + x1
b2 = b1 + x1
Weil der hinzugefügte Knotenpunkt x und seine Erzeuger beide rote Knotenpunkte sind, folgt für die Ränge folgendes:

[Formel 49]

rang(x) = rang(f) = rang(g)
Dieses widerspricht der Bedingung 2 (Formel 46), was bedeutet, dass eine Struktureinstellung erforderlich ist.
Fig. 50 zeigt ein Re-Abgleichen, das durchgeführt wird, wenn Bedingung 2 nicht erfüllt ist. Das heißt, die Knotenpunkte x, f, g und h in Fig. 49 gehören zu (a) in Fig. 50. Von daher ist die Farbe des Knotenpunktes g auf Rot abgeändert und die Farben der Ableger-Knotenpunkte f und h werden von Rot zu Schwarz abgeändert, so dass rang(g) eine Ebene höher als die anderen Knotenpunkte liegt. Fig. 51 zeigt, wie der Binärstrukturbaum ausschaut, nachdem die Knotenpunkt-Farben sich abgeändert haben.
In diesem Zustand wurden beide Knotenpunkte g und sein Erzeugerknotenpunkt e rot, was eine weitere Einstellung erfordert. Das heißt, weil der Knotenpunkt a schwarz ist, entsprechen die Knotenpunkte g, e, b und a zu (b) in Fig. 50 (symmetrisch). Von daher wird eine einfache Rotation einmal angewandt, um den Knotenpunkt b zu rot und den Knotenpunkt e zu schwarz abzuändern. Fig. 52 zeigt, wie der Binärstrukturbaum ausschaut, nachdem eine einfache Rotation angewandt und die Knotenpunkt-Farben abgeändert wurden.
Dieses ist die Rotation an den Knotenpunkten e und b und die partiellen Intervall-Längen werden wie folgt abgeändert:

[Formel 50]

b3 = b2 - e2 + c2
e3 = b2
In Fig. 52 sind die Widersprüche zu den Bedingungen 1, 2 und 3 gelöst und eine Struktureinstellung (Re-Abgleichen) ist durchgeführt.
In der obigen Struktureinstellung gilt für die Netz-Intervall- Längen der Knotenpunkte e und b in Fig. 47, wo der Binärstrukturbaum vor der Knotenpunkte-Einfügung gezeigt ist, das folgende:

[Formel 51]

e:
e1 - c1 - g1
b:
b1 - a1 - e1
Es sei darauf hingewiesen, dass die Netz-Intervall-Längen der Knotenpunkte e und b in Fig. 52, wo der Binärstrukturbaum nach dem Einfügen eines Knotenpunktes und nach der Struktureinstellung gezeigt ist, als das gleiche wie zuvor verbleiben, wie im folgenden beschrieben:

[Formel 52]

e:
e3 - b3 - g2 = b2 - (b2 - e2 + c1) - (g1 + x1) = e2 - c1 - g1 - x1 = (e1 + x1) - c1 - g1 - x1 = e1 - c1 - g1
b:
b3 - a1 - c1 = (b2 - e2 + c1) - a1 - c1 = (b1 + x1) - (e1 + x1) - a1 = b1 - a1 - e1

[1-2-4-8. Vergleich mit dem Stand der Technik]

Aus dem Stand der Technik ist eine Lösung bekannt, welche es erlaubt, die Sequenz eines Knotenpunktes aus dem Knotenpunkt in dem Binärstrukturbaum zu ermitteln (US-Patent 5,384,568). Dieser Stand der Technik (von nun an als "früheres System" bezeichnet) stimmt mit der vorliegenden Erfindung insofern überein, inwiefern aufeinanderfolgende Knotenpunkte verarbeitet werden. Jedoch verarbeitet das frühere System lediglich die Sequenz der Knotenpunkte und keine Intervalle; in dem früheren System enthält jeder Knotenpunkt die Anzahl der Knotenpunkte eines Sub-Baumes, dessen Hauptverzeichnisknoten der Knotenpunkt selbst ist. Die vorliegende Erfindung ist dem früheren System darin überlegen, dass Intervalle verarbeitet werden.
Zusätzlich verfolgt das frühere System ein Pfad von einem spezifizierten Knotenpunkt zu dem Hauptverzeichnisknoten, um die Sequenzanzahl des spezifizierten Knotenpunktes aus seiner Adresse zu berechnen; jedoch kann es einen Knotenpunkt nicht suchen, wenn ein Wert innerhalb eines Intervalls gegeben ist. Die vorliegende Erfindung ist dem früheren System darin überlegen, dass es einen Knotenpunkt suchen kann, wenn ein Wert innerhalb eines Intervalls gegeben ist. Um dieses Suchen auszuführen, benutzt die vorliegende Erfindung ein Verfahren, welches von dem benutzten Verfahren in dem früheren System sich unterscheidet; es verfolgt nämlich einen Pfad von dem Hauptverzeichnisknoten zu dem spezifizierten Knotenpunkt.
Das frühere System fügt einen Knotenpunkt nur zu einem Anfang (linksmöglichste Position) hinzu, entfernt einen Knotenpunkt lediglich von dem Ende (rechtsmöglichste Position) und bewegt während der Aktualisierungsoperation jeden Knotenpunkt zu dem Anfang (linksmöglichste Position); jedoch fügt oder entfernt es keinen Knotenpunkt zu oder von anderen Positionen. Die vorliegende Erfindung ist dem früheren System darin überlegen, das es einen Knotenpunkt (Intervall) zu oder von sämtlichen Positionen hinzufügen oder entfernen kann.

[2. Zweite Ausführungsform]

Ein Binärstrukturbaum, welcher Text darstellt, kann in dem Datenverarbeitungssystem konfiguriert werden, in welchem Text, der aus einer Vielzahl von Zeilen besteht, festgehalten wird. Die zweite Ausführungsform entspricht Anspruch 18. Das bedeutet, dass der erste Binärstrukturbaum die Sequenz der Zeilen darstellt. Dieser Binärstrukturbaum enthält eine Vielzahl von Knotenpunkten, wobei jeder einer Zeile mit der Intervall-Länge eines jeden Knotenpunktes von 1 entspricht. Ein zweiter Binärstrukturbaum stellt eine Code-Zeichenkette einer jeden Zeile dar. Jeder Zweit-Binärstrukturbaum ist mit dem entsprechenden Knotenpunkt in dem ersten Binärstrukturbaum durch einen Zeiger verbunden.
Fig. 53 zeigt einen Binärstrukturbaum, welcher die folgenden Zeilen darstellt:
xyz
st
(leere Zeile)
(leere Zeile)
abcdef
In der zweiten Ausführungsform werden der erste Binärstrukturbaum, welcher die Sequenz der Zeilen darstellt, und jeder der Zweit-Binärstrukturbäume, welche den Inhalt einer jeden Zeile darstellen, separat erzeugt. Von daher besteht nicht das Bedürfnis, den anderen Binärstrukturbaumtypen abzuändern, wenn entweder die Sequenz der Zeilen oder der Inhalt einer jeden Zeile abgeändert ist. Diese stellt sicher, dass die Verarbeitung der Code- Zeichenkette effizient erfolgt.
Wenn der Anwender Code-Zeichenketten mit einem Texteditor oder einem anderen Programm bearbeitet, ist es notwendig, die Anzahl der Zeilen (Intervall) relativ zu einem der Enden (Start oder Ende) einer Code-Zeichenkette zu spezifizieren und die Anzahl eines Codes relativ zu einem der Enden der Zeile zu spezifizieren, bevor der Zugriff des durch diesen bestimmten Code erfolgt. Es ist ferner notwendig, einen bestimmten Code abzuändern und eine Vielzahl von Schriftzeichen vor oder hinter dem entsprechenden Schriftzeichen einzufügen oder zu entfernen. Zusätzlich müssen Zeilen geeignet sein, hinzugefügt oder entfernt zu werden. Das Datenverarbeitungssystem in der siebten Ausführungsform ist für diese Art von Verarbeitung geeignet.
Die Darstellung eines fortlaufenden Bereiches des gleichen Codes mittels eines einzelnen Knotenpunktes mit der Intervall- Länge von 2 oder länger, lässt die Speicher- und Verarbeitungseffizienz ferner anwachsen.

[3. Dritte Ausführungsform]

Es ist möglich, eine Code-Zeichenkette, wie etwa ein Text, welcher eine Vielzahl von Zeilen enthält, mit einem einzelnen Binärstrukturbaum darzustellen. Die dritte Ausführungsform entspricht Anspruch 19. In diesem Fall ist die Maximalanzahl von Schriftzeichen einer Zeile auf eine große Zahl, n, fixiert und Leerzeichen werden in den Positionen eingesetzt, die keine Schriftzeichen enthalten. Ein Binärstrukturbaum setzt sich aus einer Sequenz von Code-Zeichenketten beginnend am Start (oder am Ende) zusammen. Dann beginnt der j-te Code von dem Beginn der Zeile i bei einer Position in dem gesamten Text, die durch die folgende Formel dargestellt wird:

[Formel 53]

(i - 1) · n + j
Fig. 54 ist ein Beispiel eines Binärstrukturbaumes, welcher den obigen Text mit n als 10 darstellt. Auf diese Weise können Daten mittels eines einzelnen, einfach strukturierten Binärstrukturbaumes dargestellt werden. Da eine Sequenz einer Vielzahl der gleichen Schriftzeichen oder eine Sequenz von Leerzeichen durch einen einzelnen Knotenpunkt mit dem Schriftzeichen als Label und mit der Intervall-Länge, welche die Anzahl der nachfolgenden Schriftzeichen darstellt, dargestellt werden, wächst zusätzlich die Verarbeitungs- und Speichereffizienz an. Beispielsweise werden in Fig. 54 aufeinanderfolgende acht Leerzeichen und zwei Leerzeilen als 28 Leerzeichen mittels eines einzelnen Knotenpunktes dargestellt. Das Datenverarbeitungssystem in der dritten Ausführungsform ist im einzelnen dazu geeignet, wenn Daten viele Sequenzen der gleichen Codes enthalten.
Zusätzlich ermöglicht es das Komprimieren von Bit- Zeichenkettendaten, wie etwa ein Faksimilebild (facsimile image), indem unter der Verwendung eines Binärstrukturbaumes in der dritten Ausführungsform sämtliche Bits in der Bit- Zeichenkette als 1 oder 0 identifizieren werden. Dieses ist verschieden von einer herkömmlichen Technik.
Eine Bit-Zeichenkette enthält nämlich gewöhnlich eine Vielzahl von Nullen und Einsen, welche abwechselnd auftreten. Bei einem herkömmlichen Verfahren erfolgt das Komprimieren der Bit-Daten durch ein sequentielles Aufzeichnen der Anzahl der aufeinanderfolgenden Nullen und Einsen (Lauflängen-Decoding/run-length-encoding). Bei diesem Lauflängen-Decoding-Verfahren ist es notwendig, sämtliche vorangehende Bits zu speichern oder die Längen der Intervalle aufzurechnen, um den Wert eines Bits (0 oder 1) zu bestimmen oder um einen Teil der Daten, welcher in der Mitte der Daten auftaucht, zu suchen. Als Kontrast zu diesem Verfahren benötigt ein Binärstrukturbaum in der dritten Ausführungsform lediglich so viele Knotenpunkte wie Anzahl von Intervallen, und ermöglicht es zusätzlich, den Wert eines Bits, der sich in der Mitte der Daten befindet, zurückzusetzen oder zu bestimmen.

[4. Andere Ausführungsformen]

Diese Erfindung ist nicht auf die hier beschriebenen bevorzugten Ausführungsformen beschränkt, sondern kann in anderen spezifizierten Formen ohne sich von den wesentlichen Eigenschaften hiervon zu entfernen ausgeführt werden, wie etwa solche nachstehend beschriebenen.
Beispielsweise können sämtliche Arten von Schriftzeichen, wie etwa japanische Schriftzeichen oder Hankul-alphabetische Schriftzeichen in einer Code-Zeichenkette verwendet werden, obwohl in den obigen Ausführungsformen lediglich alphabetisch aufeinanderfolgende Wörterbuchdaten oder Bäume, welche alphabetische Schriftzeichen enthalten, verwendet wurden. Des weiteren ist eine Code-Zeichenkette in dieser Erfindung nicht an eine Schriftzeichenkette beschränkt. Es kann ein beliebiger Typ von Code sein, wie etwa ein Sprachmustercode oder ein DNA- Basislayout-Code. Des weiteren kann eine Sub-Zeichenkette in einer Code-Zeichenkette indirekt verarbeitet werden, beispielsweise durch das Markieren einer Grenze mittels eines Zeigers. Dieses Verfahren beseitigt die Notwendigkeit, einen Teil von Code-Zeichenkettendaten zu verarbeiten, beispielsweise durch die Übergabe dieser in einen anderen Speicherbereich.
Das Label, welches an einer Grenze oder an einem Knotenpunkt in einem Baum oder Binärstrukturbaum zugefügt wurde, braucht nicht ein Ein-Schriftzeichen-Code zu sein.
Daten können ebenso durch ein Anpassen in der nacheilenden (trailing) Zeichenkette basierend auf der vorderen Zeichenkette gesucht werden, obwohl Daten durch ein Anpassen in der führenden (leading) Zeichenkette basierend auf der hinteren Zeichenkette in der Sub-Zeichenkette wieder abgerufen werden können. In diesem Fall sollten in dieser Spezifikation "nacheilende Zeichenkette" und "führende Zeichenkette" ausgetauscht werden. Während der Verarbeitung werden Schriftzeichen von dem Ende einer Schlüssel-Zeichenkette erhalten. Der führende (vorangehende) Knotenpunkt und der nacheilende (nachfolgende) Knotenpunkt in der ersten Ausführungsform sollten ebenso ausgetauscht werden.
Von daher stellt diese Erfindung ein Datenverarbeitungssystem bereit, welches Daten effizient bearbeitet.

Claims

1. Ein Datenverarbeitungssystem zur Verarbeitung von Daten einer in eine Sequenz von Intervallen eingeteilten Codekette, in der zum Auffinden einer spezifizierten Position in der Codekette jedes Intervall eine durch die Anzahl der Code- Elemente in dem Intervall definierte Länge hat, wobei das Datenverarbeitungssystem eine Binärstrukturbaum- Erzeugungseinrichtung (32) umfasst zum Erstellen eines binären Strukturbaumes (31), welcher eine Vielzahl von Knotenpunkten aufweist, die entsprechende Positionen der Intervalle in der Codekette darstellen,

wobei die Knotenpunkte jeweils einem der Intervalle der Codekette zugewiesen sind,

und wobei die Knotenpunkte von einem Hauptverzeichnisknoten des Strukturbaumes zu Astknoten davon in einer baumartigen Struktur verbunden sind,

und wobei jeder Knotenpunkt zwischen dem Hauptverzeichnisknoten und den Astknoten ein Hauptverzeichnisknoten eines Subbaumes darstellt und mit einem vorhergehenden Knotenpunkt verbunden ist, der als linker Ableger-Knotenpunkt (left-child node) definiert ist, welcher einem Intervall in der Codekette entspricht, das dem Intervall vorhergeht, welches dem genannten Knotenpunkt entspricht, und/oder mit einem nachfolgenden Knotenpunkt verbunden ist, der als rechter Ableger-Knotenpunkt (right-child node) definiert ist, welcher einem Intervall in der Codekette entspricht, das dem Intervall folgt, welches dem genannten Knotenpunkt entspricht,

dadurch gekennzeichnet, dass

jedem Knotenpunkt eine partielle Intervall-Länge zugewiesen wird, welche definiert ist als die Summe aus der Länge des Intervalls, das dem genannten Knotenpunkt entspricht, und den Intervallen, die - falls vorhanden - den Knotenpunkten an der Astseite des genannten Knotenpunktes entsprechen,

eine Einrichtung (vorhanden ist) zur Identifizierung des Knotenpunktes, der dem Intervall entspricht, welches die spezifizierte Position enthält, durch eine vom Hauptverzeichnisknoten beginnende Verarbeitung der Knotenpunkte, wobei die Einrichtung folgendes umfasst:

eine Einrichtung zum Selektieren des linken Ableger- Knotenpunktes des aktuellen Knotenpunktes als den nächstaktuellen Knotenpunkt, falls die spezifizierte Position geringer oder gleich der partiellen Intervall-Länge des linken Ableger-Knotenpunktes ist;

eine Einrichtung zum Selektieren des rechten Ableger- Knotenpunktes als den nächstaktuellen Knotenpunkt und zum Aktualisieren der Darstellung der spezifizierten Position des rechten Ableger-Knotenpunktes relativ zum aktuellen Knotenpunkt, falls die spezifizierte Position größer ist als die partielle Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Intervall-Länge des rechten Ableger- Knotenpunktes; und

eine Einrichtung zum Identifizieren, dass die spezifizierte Position in dem Intervall enthalten ist, welches dem aktuellen Knotenpunkt entspricht, falls die spezifizierte Position größer als die partielle Intervall-Länge des linken Ableger- Knotenpunktes und geringer als oder gleich der partiellen Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Länge des rechten Ableger- Knotenpunktes ist.

2. Ein Datenverarbeitungssystem nach Anspruch 1, ferner mit einer Intervall-Sucheinrichtung (33) zum Identifizieren, welches Intervall in der Sequenz von Intervallen die spezifizierte Position in der Codekette enthält, wobei die Intervall- Sucheinrichtung folgendes aufweist:

eine Einrichtung zum Selektieren des aktuellen Knotenpunktes mittels eines Zeigers;

eine Einrichtung zum Bewegen des Zeigers von dem Hauptverzeichnisknoten zu einem der Astknoten;

eine Einrichtung zum Berechnen des Bereiches von Positionen in der Codekette des Intervalls, das dem aktuellen Knotenpunkt entspricht, basierend auf der Intervall-Länge des vorhergehenden Knotenpunktes und/oder basierend auf der Intervall-Länge des nachfolgenden Knotenpunktes, welcher direkt mit der Astknotenseite des aktuellen Knotenpunktes oder eines Knotenpunktes niedrigeren Levels, welcher der nachfolgende Knotenpunkt ist, verbunden ist;

eine Einrichtung zum Vergleichen des derart mit der spezifizierten Position berechneten Bereiches;

eine Einrichtung zum Bewegen des Zeigers zu dem vorhergehenden Knotenpunkt als den nächsten aktuellen Knotenpunkt, wenn die spezifizierte Position dem berechneten Bereich vorausgeht;

eine Einrichtung zum Bewegen des Zeigers zu dem nachfolgenden Knotenpunkt als den nächstaktuellen Knotenpunkt, wenn die spezifizierte Position dem berechneten Bereich nachfolgt; und

eine Einrichtung zum Identifizieren, dass die spezifizierte Position in dem Intervall enthalten ist, welches dem aktuellen Knotenpunkt entspricht, wenn die spezifizierte Position in dem berechneten Bereich enthalten ist.

3. Ein Datenverarbeitungssystem nach Anspruch 1, ferner eine Identifizierungseinrichtung umfassend zum Identifizieren, welches Intervall in der Sequenz von Intervallen einem spezifizierten Knotenpunkt entspricht, der ein beliebiger Knotenpunkt in dem Binärstrukturbaum (31) ist, wobei die Identifizierungseinrichtung folgendes aufweist:

eine Einrichtung zum Bewegen des Zeigers von dem aktuellen Knotenpunkt zu dessen Hauptverzeichnisknoten, welcher ein Knotenpunkt höheren Levels des aktuellen Knotenpunktes ist, einen Knotenlevel pro Zeit, bis der Hauptverzeichnisknoten erreicht ist;

eine Einrichtung zum Aufaddieren der Intervall-Länge des aktuellen Knotenpunktes und der partiellen Intervall-Länge des vorhergehenden Knotenpunktes oder des dem aktuellen Knotenpunkt folgenden Knotenpunktes immer dann, wenn der aktuelle Knotenpunkt bewegt wird, abhängig davon, ob ein Ableger-Knotenpunkt, welcher vor der Bewegung des Zeigers der aktuelle Knotenpunkt ist, der vorhergehende Knotenpunkt oder der nachfolgende Knotenpunkt ist; und

eine Einrichtung zum Identifizieren des Intervalls, welches dem aktuellen Knotenpunkt entspricht, indem eine oder beide der linken Intervall-Länge, welche die gesamte Intervall-Länge der in L-C-R-Reihenfolge dem aktuellen Knotenpunkt vorhergehenden Knotenpunkten ist, oder eine rechte Intervall- Länge, welche die gesamte Intervall-Länge der in L-C-R- Reihenfolge dem aktuellen Knotenpunkt nachfolgenden Knotenpunkten ist.

4. Ein Datenverarbeitungssystem nach Anspruch 1, ferner eine Identifizierungseinrichtung umfassend zum Identifizieren, welches Intervall in der Sequenz der Intervalle einem spezifizierten Knotenpunkt entspricht, welcher ein beliebiger Knotenpunkt in dem Binärstrukturbaum (31) ist, wobei die Identifizierungseinrichtung den aktuellen Knotenpunkt zum Hauptverzeichnisknoten mittels Ausbreiten bewegt.

5. Ein Datenverarbeitungssystem nach einem der Ansprüche 1, 2 oder 3, ferner eine Binärstrukturbaum- Aktualisierungseinrichtung (34) umfassend, zum dem Inhalt der Abänderung entsprechenden Aktualisieren des Binärstrukturbaumes (31), wenn das Intervall abgeändert wird.

6. Ein Datenverarbeitungssystem nach Anspruch 5, wobei die Binärstrukturbaum-Aktualisierungseinrichtung (34) folgendes umfasst:

eine Intervalllängen-Änderungseinrichtung (41) zum Abändern der Intervall-Länge;

eine Entfernungseinrichtung (42) zum Entfernen des einem vom Binärstrukturbaum (31) gelöschten Intervall entsprechenden Knotenpunktes, wenn das Intervall aus der Codekette gelöscht worden ist; und

eine Hinzufügungseinrichtung (43) zum Hinzufügen eines einem zum Binärstrukturbaum hinzugefügten Intervall entsprechenden Knotenpunktes, wenn ein Intervall zu der Codekette hinzugefügt wurde.

7. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Intervalllängen-Änderungseinrichtung (41) eine Einrichtung zum Abändern der partiellen Intervall-Länge eines jeden Knotenpunktes umfasst, wobei das Abändern der Reihe nach von dem Knotenpunkt, welcher dem Intervall entspricht, dessen Länge abgeändert werden muss, zu dem Hauptverzeichnisknoten erfolgt, und zwar um einen dem der abgeänderten Länge gleichen Wert.

8. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Intervalllängen-Änderungseinrichtung (41) eine Einrichtung zum Bewegen des Knotenpunktes, welcher dem Intervall entspricht, dessen Länge abgeändert werden muss, zum Hauptverzeichnisknoten mittels Ausbreitung, und zum Vergrößern oder Verkleinern der partiellen Intervall-Länge des Hauptverzeichnisknotens um einen der abgeänderten Länge entsprechenden Wert.

9. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Hinzufügungseinrichtung (43) folgendes umfasst:

eine Einrichtung zum Hinzufügen des Knotenpunktes, welcher dem hinzuzufügenden Intervall entspricht, zum Binärstrukturbaum (31);

eine Einrichtung zum Einstellen der Verbindungssequenz der Knotenpunkte; und

eine Einrichtung zum Einstellen der Intervall-Länge eines jeden Knotenpunktes.

10. Ein Datenverarbeitungssystem nach Anspruch 9, wobei die Hinzufügungseinrichtung (43) eine Einrichtung umfasst, um die Summe aus der partiellen Intervall-Länge des hinzugefügten Knotenpunktes und der partiellen Intervall-Länge des Knotenpunktes niedrigeren Levels des aktuellen Knotenpunktes als partielle Intervall-Länge des hinzugefügten Knotenpunktes zu benutzen, und für die Knotenpunkte auf dem Pfad von dem Erzeuger-Knoten, zum welchem der hinzugefügte Knotenpunkt direkt verbunden ist, als ein Knotenpunkt niedrigeren Levels zu dem Hauptverzeichnisknoten zu benutzen, und eine Einrichtung, um die Intervall-Länge des hinzugefügten Knotenpunktes zu der partiellen Intervall-Länge eines jeden Knotenpunktes hinzuzufügen.

11. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Hinzufügungseinrichtung (43) folgendes umfasst:

eine Einrichtung, um die Knotenpunkte, die einer Position unmittelbar vorhergehen und nachfolgen, an welcher ein Knotenpunkt hinzugefügt werden muss, mittels Ausbreiten von jeweils einem Knotenpunkt zum Hauptverzeichnisknoten zu bewegen,

eine Einrichtung, um den Knotenpunkt hinzufügen, der einem Intervall entspricht, das hinzugefügt werden muss, an einer Position, die unmittelbar dem unmittelbar-vorhergehendem Knotenpunkt folgt, oder an einer unmittelbar vor dem unmittelbar-nachfolgendem Knotenpunkt liegenden Position;

und eine Einrichtung zum Hinzufügen der Intervall-Länge des hinzugefügten Knotenpunktes zu der partiellen Intervall-Länge des unmittelbar vorhergehenden oder unmittelbar nachfolgenden Knotenpunktes des hinzugefügten Knotenpunktes, falls es erforderlich ist.

12. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Hinzufügungseinrichtung (43) folgendes umfasst:

eine Einrichtung, um den Knotenpunkt, der dem hinzuzufügendem Intervall entspricht, zu dem Binärstrukturbaum mit der Intervall-Länge des Knotenpunktes mit dem Wert 0 hinzuzufügen;

eine Einrichtung, um den hinzugefügten Knotenpunkt zu dem Hauptverzeichnisknoten des Binärstrukturbaumes mittels Ausbreiten zu bewegen; und

eine Einrichtung, um die partielle Intervall-Länge des Knotenpunktes, welcher zu dem Hauptverzeichnisknoten bewegt wurde, um die Intervall-Länge des hinzugefügten Intervalls zu erhöhen.

13. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Entfernungseinrichtung (42) folgendes umfasst:

eine Einrichtung zum Entfernen des Knotenpunktes des zu entfernenden Intervalls vom Binärstrukturbaum;

eine Einrichtung zum Einstellen der Verbindung zwischen den Knotenpunkten; und

eine Einrichtung zum Einstellen der Intervall-Länge eines jeden Knotenpunktes.

14. Ein Datenverarbeitungssystem nach Anspruch 6, wobei die Entfernungseinrichtung (42) folgendes umfasst:

eine Einrichtung zum Bewegen der dem zu entfernenden Intervall entsprechenden Knotenpunkte zu dem Hauptverzeichnisknoten mittels Ausbreiten,

eine Einrichtung zum Bewegen des dem zu entfernenden Knotenpunkt unmittelbar vorhergehenden oder nachfolgenden Knotenpunktes zu dem Hauptverzeichnisknoten mittels Ausbreiten;

eine Einrichtung zum Verringern der partiellen Intervall-Länge des unmittelbar vorhergehenden oder unmittelbar nachfolgenden Knotenpunktes, welcher der Hauptverzeichnisknoten ist, um den Wert der Intervall-Länge des zu entfernenden Knotenpunktes; und

eine Einrichtung zum Entfernen des Knotenpunktes, der entfernt werden muss.

15. Ein Datenverarbeitungssystem nach Anspruch 5, ferner folgendes umfassend: Eine Struktureinstellungs-Einrichtung (45) zum Einstellen der Struktur des Binärstrukturbaumes (31) mittels eines Abänderns der Verbindungssequenz der Knotenpunkte.

16. Ein Datenverarbeitungssystem nach Anspruch 15, wobei die Struktureinstellungs-Einrichtung (45) eine Einrichtung zur geleiteten Rotation, Doppel-Rotation (Zick-Zick) und Doppel- Rotation (Zick-Zack) umfasst, als eine Struktureinstellungsprozedur zum Abändern der Struktur während des Beibehaltens der Sequenz der Knotenpunkte des Binärstrukturbaumes (31).

17. Ein Datenverarbeitungssystem nach Anspruch 15, wobei die Struktureinstellungs-Einrichtung (45) eine Einrichtung zum Einstellen des Binärstrukturbaumes mittels Ausbreitens umfasst, wodurch ein Zielknotenpunkt, welcher ein beliebiger der Knotenpunkte ist, zu dem Hauptverzeichnisknoten bewegt wird.

18. Ein Datenverarbeitungssystem nach Anspruch 2, wobei:

die Codekette ein Text ist, welcher eine Vielzahl von Zeilen von Schriftzeichen als Code-Elemente beinhaltet;

die Intervalle in der Codekette die in dem Text enthaltenden Zeilen sind; und

die Binärstrukturbaum-Erzeugungseinrichtung (32) eine Einrichtung umfasst, um einen ersten Binärstrukturbaum zu erzeugen, der eine Vielzahl von Knotenpunkten aufweist, welche der Sequenz der Zeilen entsprechen, wobei die Knotenpunkte des ersten Binärstrukturbaumes zu jeweils einer der Zeilen in dem Text zugeordnet sind, und um einen zweiten Binärstrukturbaum zu erzeugen, der eine Vielzahl von Knotenpunkte aufweist, die der Sequenz der Code-Elemente in jeder Zeile entsprechen, wobei die Knotenpunkte des zweiten Binärstrukturbaumes jeweils zu einem der Schriftzeichen in der besagten Zeile zugeordnet sind.

19. Ein Datenverarbeitungssystem nach Anspruch 2, wobei:

die Codekette ein Text ist, der eine Vielzahl von Zeilen von Schriftzeichen als Code-Elemente beinhaltet, wobei die Zeilen eine feste Länge aufweisen, und wobei

die Binärstrukturbaum-Erzeugungseinrichtung (32) eine Einrichtung umfasst, um ein leeres Schriftzeichen an eine Position in der Codekette zu setzen, wo in dem Text kein Schriftzeichen vorhanden ist, und eine Einrichtung umfasst, um den Binärstrukturbaum (31) zu erzeugen, indem jede Subkette des Textes mit einem einzelnen Knotenpunkt vertreten wird, wobei der Knotenpunkt eine Sequenz von Schriftzeichen und/oder leeren Schriftzeichen aufweist, welche aufeinanderfolgend in der besagten Subkette als ein Kennzeichen des Knotenpunktes auftreten, und wobei der Knotenpunkt die Anzahl der aufeinanderfolgenden Schriftzeichen in der besagten Subkette als die Länge des Intervalls hat, das dem Knotenpunkt entspricht.

20. Ein Datenverarbeitungsverfahren zum Verarbeiten von Daten einer Codekette, die in eine Sequenz von Intervallen eingeteilt ist, wobei jedes Intervall eine über die Anzahl der Code-Elemente in dem Intervall definierte Länge aufweist, um eine spezifizierte Position in der Codekette aufzufinden, wobei das Datenverarbeitungsverfahren einen Binärstrukturbaum- Erzeugungsprozess zum Erzeugen eines Binärstrukturbaumes (31) umfasst, wobei der Binärstrukturbaum eine Vielzahl von Knotenpunkte aufweist, welche die jeweiligen Positionen der Intervalle in der Codekette entsprechen, wobei

die Knotenpunkte zu jeweils einem der Intervalle in der Codekette zugeordnet sind;

die Knotenpunkte von einem Hauptverzeichnisknoten des Baumes zu dessen Astknoten in einer baumartigen Struktur verbunden sind;

jeder Knotenpunkt zwischen dem Hauptverzeichnisknoten und den Astknoten ein Hauptverzeichnisknoten eines Subbaumes darstellt und zu einem vorhergehenden Knotenpunkt verbunden ist, welcher als der linke Ableger-Knotenpunkt definiert ist, der einem Intervall in der Codekette entspricht, das dem Intervall vorhergeht, welches dem besagten Knotenpunkt entspricht, und/oder zu einem nachfolgenden Knotenpunkt verbunden ist, welcher als der rechte Ableger-Knotenpunkt definiert ist, der einem Intervall in der Codekette entspricht, das dem Intervall nachfolgt, welches dem besagten Knotenpunkt entspricht,

dadurch gekennzeichnet, dass:

jeder Knotenpunkt einer partiellen Intervall-Länge zugeteilt ist, welche definiert ist als die Summe aus der Länge des Intervalls, das dem besagten Knotenpunkt entspricht, und den Längen der Intervalle, die den - falls vorhandenen - Knotenpunkten an der Astseite des besagten Knotenpunktes entsprechen;

ein Identifizieren des Knotenpunktes, der dem Intervall entspricht und der die spezifizierte Position einschließt, durch eine wie folgt beschriebene Verarbeitung der Knotenpunkte beginnend von dem Hauptverzeichnisknoten:

Selektieren des linken Ableger-Knotenpunktes des aktuellen Knotenpunktes als den nächstaktuellen Knotenpunkt, falls die spezifizierte Position weniger als oder gleich der partiellen Intervall-Länge des linken Ableger-Knotenpunktes ist;

Selektieren des rechten Ableger-Knotenpunktes als den nächstaktuellen Knotenpunkt;

Aktualisieren der Darstellung der spezifizierten Position gemäß der Position des rechten Ableger-Knotenpunktes relativ zu dem aktuellen Knotenpunkt, falls die spezifizierte Position größer als die partielle Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Intervall-Länge des rechten Ableger-Knotenpunktes ist; und

Identifizieren, dass die spezifizierte Position in dem Intervall eingeschlossen ist, welches dem aktuellen Knotenpunkt entspricht, falls die spezifizierte Position größer als die partielle Intervall-Länge des linken Ableger- Knotenpunktes und weniger als oder gleich der partiellen Intervall-Länge des aktuellen Knotenpunktes abzüglich der partiellen Länge des rechten Ableger-Knotenpunktes ist.

21. Ein Datenverarbeitungsverfahren nach Anspruch 20, ferner einen Intervall-Suchprozess umfassend, das zum Identifizieren dient, welches Intervall in der Sequenz der Intervalle die spezifizierte Position in der Codekette einschließt, wobei der Intervall-Suchprozess in der Reihenfolge aus folgenden Schritten besteht:

Selektieren des aktuellen Knotenpunktes mittels eines Zeigers;

Bewegen des Zeigers von dem Hauptverzeichnisknoten zu einem der Astknoten;

Berechnen des Bereiches der Positionen in der Codekette des Intervalls, welches dem aktuellen Knotenpunkt entspricht, basierend auf der Intervall-Länge des vorhergehenden Knotenpunktes und/oder des nachfolgenden Knotenpunktes, welcher direkt mit der Astknotenseite des aktuellen Knotenpunktes verbunden ist;

Vergleich des derart berechneten Bereiches mit der spezifizierten Position;

Bewegen des Zeigers zu dem vorhergehenden Knotenpunkt als den nächstaktuellen Knotenpunkt, wenn die spezifizierte Position der berechneten Auswahl nachfolgt; und

Identifizieren, dass die spezifizierte Position in dem Intervall enthalten ist, das dem aktuellen Knotenpunkt entspricht, wenn die spezifizierte Position in dem berechneten Bereich enthalten ist.

22. Ein Datenverarbeitungsverfahren nach Anspruch 20, ferner einen Identifizierungsprozess umfassend, zum Identifizieren, welches Intervall in der Sequenz der Intervalle mit dem spezifizierten Knotenpunkt übereinstimmt, welcher eines der in dem Binärstrukturbaum (31) gegebenen Knotenpunkte ist, wobei der Identifizierungsprozess aus folgenden Schritten besteht:

Aufaddieren der Intervall-Länge des aktuellen Knotenpunktes und der partiellen Intervall-Länge des vorhergehenden Knotenpunktes oder des nachfolgenden Knotenpunktes des aktuellen Knotenpunktes immer dann, wenn der aktuelle Knotenpunkt bewegt wird, abhängig davon, ob entweder ein Ableger-Knotenpunkt, welcher der aktuelle Knotenpunkt vor der Bewegung ist, der vorhergehende oder der nachfolgende Knotenpunkt darstellt; und

Identifizieren des Intervalls, welches dem aktuellen Knotenpunkt entspricht, durch Berechnen einer linken Intervall-Länge, welche die gesamte Intervall-Länge der Knotenpunkte ist, die dem aktuellen Knotenpunkt in L-C-R- Reihenfolge vorhergehen, und/oder einer rechten Intervall- Länge, welche die gesamte Intervall-Länge der Knotenpunkte ist, die dem aktuellen Knotenpunkt in L-C-R-Reihenfolge nachfolgen.

23. Ein Datenverarbeitungsverfahren nach Anspruch 20, 21 oder 22, ferner einen Binärstrukturbaum-Aktualisierungsprozess zum dem Ausmaß der Abänderung entsprechenden Aktualisieren des Binärstrukturbaumes (31), wenn das Intervall abgeändert wird.

24. Ein Datenverarbeitungsverfahren nach Anspruch 23, wobei der Binärstrukturbaum-Aktualisierungsprozess folgendes umfasst:

Ein Intervalllängen-Änderungsprozess (Schritt 353) zum Abändern der Intervall-Länge;

Ein Löschungsprozess (Schritt 351) zum Entfernen des Knotenpunktes, welcher einem gelöschten Intervall entspricht, von dem Binärstrukturbaum, wenn das Intervall aus der Codekette gelöscht wird; und

ein Hinzufügungsprozess (Schritt 351) zum Hinzufügen eines Knotenpunktes, welcher einem hinzugefügten Intervall entspricht, zum Binärstrukturbaum, wenn ein Intervall zu der Codekette hinzugefügt wird.

25. Ein Datenverarbeitungsverfahren nach Anspruch 23, ferner einen Struktureinstellungsprozess (Schritt 355) umfassend, zum Einstellen der Struktur des Binärstrukturbaumes (31) durch ein Abändern der Sequenz der Verbindung der Knotenpunkte.