Binary tree flag bit arrangement and partitioning method and apparatus

• US 5,628,002 A
• Filed: 11/02/1992
• Issued: 05/06/1997
• Est. Priority Date: 11/02/1992
• Status: Expired due to Fees

• Current Assignee: Luther J. Woodrum
• Original Assignee: Luther J. Woodrum
• Inventors: Woodrum, Luther J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US07/970,399
• Time in Patent Office: 1,646 Days
• Field of Search: 395/600, 395/800, 395/898
• US Class Current: 1/1
• CPC Class Codes: G06F 2207/222 Binary data tree
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence

Abstract

Arrangement of fields in binary tree nodes provides a minimal storage encoding storing fixed and variable length keys in factored form in a multilevel tree. A locating method, and apparatus embodying that method, directed by an argument key, which may or may not be stored in the tree, traces a path following arcs upward or downward between nodes in said binary tree, starting from the top node or any other node, until it finds either the argument key or the delta arc where said argument key would be inserted into said tree. The novel binary tree encoding also provides for path tracing starting at a data backpointer field, which allows accessing of neighboring data entries in collating sequence order.

Claims

1. A method for sorting three keys into two sets, comprising the steps of

computing the three exclusive-OR differences or similarities in values between each of three pairs of keys,

comparing for value the differences or similarities to each other, outputs of said comparing steps thereby determining according to a prescribed rule

a partition of the three keys into said two sets in which every key in one set is lexicographically greater than every key in the other set.

2. A method for sorting a set of three keys into two sets according to claim 1 wherein said prescribed rule comprises the steps of

selecting the minimum of said differences or the maximum of said similarities,

thereby grouping two of said keys having said smallest difference or maximum similarity in a first set and the third said key in a second set.

3. A method for sorting three character-string keys into a first set and a second set in which every key in one set is lexicographically either less or greater as the choice may be than every key in the other set,

said first set containing two of the keys and said second set containing the third remaining key,

comprising the steps of

computing the three exclusive-OR differences between each pair of keys,

comparing the three differences to each other to determine the pair of said keys having the smallest difference,

whereupon said pair of said keys having said smallest difference are assigned to said first set and the remaining key is assigned to said second set.

4. A system for computing three output signals from a new key, a low key, and a high key, said keys being character-strings, said three output signals forming part of a control logic controlling a locating step in a binary tree containing keys in lexicographical order, said system comprising a mask for determining the highest order bit position where the corresponding bits in the three keys or key words are not all equal, and means for mask determined key bits then determining the relationship between the new key and the other two keys.

5. In a system for sorting a new and two lexicographically-ordered character-string keys into two sets in which every key in one set is lexicographically greater than every key in the other set;

means for simultaneously generating signals representative of the exclusive-or difference or similarity of the value of each key with respect to the other, and means for grouping according to its value the new key with the low or the high key or by itself.

6. In a system for sorting a new key and lexicographically-ordered character two, into two sets;

first, second and third means for exclusive-ORing the new and the low keys, the new and the high keys, and the low and the high keys, respectively; and

first, second and third means for comparing the outputs of the first and second exclusive-ORing means, of the first and third exclusive-ORing means, and of the second and third exclusive-ORing means, respectively, to develop output signals determining the partitioning the three keys into two sets.

7. In a system for sorting a new key and lexicographically-ordered character two keys, into two sets:

first, second and third means for NANDING the new and the low and the high keys, for exclusive-ORing the new and the low and the high keys, and for ANDing the output of the first and second means; and

first, second and third means for ANDing the output of the third means, with the respective of the new, low and high keys, to develop output signals determining the partitioning the three keys into two sets.

8. A method for sorting a set of character-string keys into two sets, a low set and a high set, where each of said keys in said low set is numerically or lexicographically smaller than each of said keys in said high set, comprising:

mask computation steps including;

preliminary steps of;

ORing all keys together to form an ORed value, and

ANDing all keys together to form an ANDed value,

subtracting or XORing said ANDed value output of said preliminary steps with or from said ORed value output of said preliminary steps to form an intermediate result from which a mask may be computed, and

computing from said intermediate result a mask containing all zero bits if said keys used to form said mask are equal and if not equal then all zero bits except a one in the bit position corresponding to the highest order one-bit in said intermediate result;

and a partitioning step ANDing said mask with each of said keys and a zero result assigns a key to a low set and a non-zero result assigns the key to a high set,

where as a consequence all of said keys is said low set are numerically or lexicographically less than any key in said high set.

9. A method according to claim 8, wherein each partitioning step examines only a portion of said keys corresponding to an arbitrary word size, said partitioning steps being performed first using only the first word of each of said keys until sets of keys containing only equal first words are obtained, then using each subsequent word of said words in said keys for further partitioning, thereby providing a sorting method using only word operations to sort keys longer than a word, said word operations being capable of being performed much faster than operations operating on all bits of said keys.

10. A method according to claim 8, further comprising the steps of:

setting at the beginning of every-set partitioning with all zeros as an initial value the ORed result and with all ones as an initial value the ANDed result,

performing separately said intermediate ORed and ANDed result computation steps to the keys of the low set to obtain a low set pair intermediate ORed and ANDed results and performing separately said intermediate ORed and ANDed result computation steps to the keys of the high set to obtain a high set pair of ORed and ANDed result;

said computation of said ANDed and said ORed intermediate results of said partitioning step for said keys in both said low and said high sets being effected by means of a single AND and a single OR for each said key in either said high or said low set, said single AND and said single OR being performed concurrently with said partitioning step;

when all keys have been partitioned, computing a mask for further partitioning said low set and computing a mask for further partitioning said high set from said ANDed and ORed intermediate results for said low and high sets respectively; and

applying said partitioning step again recursively to said high or said low sets, until only sets containing only equal keys obtain;

thus providing computation of said ANDed and said ORed intermediate results in advance of the actual partitioning use of them while partitioning each said set of keys into a low and a high set, resulting in a sorted set or keys.

11. A method according to claim 10, wherein said partitioning steps are being performed independently on each of said high and said low sets, thereby providing a sorting method capable of sorting a number of keys in a time equal to or less than a constant multiple of the number of bits in the longest of any said keys.

12. A system for computing three output signals from a new key, a low and high key, said keys being character-strings said three output signals forming part of a control logic controlling a locating step in lexicographically-ordered binary tree, said system comprising

a bitwise parallel NAND function of three input words,

a bitwise parallel OR function of three input words,

five bitwise parallel AND functions of two input words,

two BIT REVERSAL functions accepting an input word and making available an output equal to said input word with the bits in said input word reversed from low order to high order,

a twos complementer having an input word and an output word which is the twos complement of said input word, and

three funnel OR logic functions, each having a word of input and a single output bit signal, said output signal having a value of one if any of the bits in said input word has a value of one.

13. A method for controlling the steps of a locating procedure operating on a selected node of a binary tree in response to an input key, said selected node having stored fields,

said binary tree node providing a partition of a set of stored keys sorted into a low set and a high set in which every key in one set is lexicographically greater than every key in the other set,

said stored fields enabling access of a low key and a high key for any node,

said low key being the lowest of all of said keys in said low set,

said high key being the lowest of all said keys in said high set,

said low set containing only keys less than said high key,

said high set containing only keys less than said high key,

said selected node providing pointers to a low node and a high node for partitioning said low and said high sets respectively,

said locating procedure comprising the steps of selecting said low node as a next node or selecting said high node as a next node or retaining said selected node as the output of said locating procedure,

said controlling method comprising the steps of computing the exclusive-OR difference between said low key and said high key, computing the exclusive-OR difference between said input key and said low key, computing the exclusive-OR difference between said input key and said high key, determining which of the three said differences is numerically smallest, if said difference between said input key and said low key is said smallest difference then said selecting low node step in said locating procedure is executed, if said difference between said input key and said high key is said smallest difference then said selecting high node step in said locating procedure is executed, if said difference between said low key and said high key is said smallest difference then said retaining said selected node step in said locating procedure is executed whereupon said locating procedure terminates,

said locating procedure steps and control being repeated until said locating procedure terminates,

whereupon said selected node is the output of said locating procedure.

14. A method for controlling the steps of a locating procedure operating on a selected node of a binary tree in response to an input key, said selected node having stored fields,

said binary tree node providing a partition of a set of stored keys sorted into a low set and a high set in which every key in one set is lexicographically either less or greater as the choice may be than every key in the other set,

said stored fields enabling access of a low key and a high key for any node,

said low key being the lowest of all of said keys in said low set,

said high key being the lowest of all of said keys in said high set,

said low set containing only keys less than said high key,

said high set containing only keys not less than said high key,

said selected node providing pointers to a low node and a high node for partitioning said low and said high sets respectively,

said locating procedure comprising the steps of selecting said low node as a next node or selecting said high node as a next node or retaining said selected node as the output of said locating procedure,

said controlling method comprising the steps of computing the exclusive-OR difference between said low key and said high key, computing the exclusive-OR difference between said input key and said low key, computing the exclusive-OR difference between said input key and said high key, determining which of three said differences is numerically smallest.

15. In a system for computing a minimal difference, compare function of three input character-string words NEW, LOW, and HIGH, and having four output signals enabling the three words NEW, LOW, AND HIGH to be sorted into two sets,

each said input word comprising an unsigned binary value,

said LOW input word having been predetermined to be numerically less than said HIGH input word,

said system for computing a minimal difference compare function comprising

means for gating said NEW and LOW inputs to a first exclusive-OR mechanism, means for gating said NEW and said HIGH inputs to a second exclusive-OR mechanism, means for gating said LOW and HIGH inputs to a third exclusive mechanism,

means for gating said output of said first exclusive-OR mechanism to a first input of a first comparing mechanism, means for gating said output of said second exclusive-OR mechanism to a second input of said first comparing mechanism,

means for gating said output of said first exclusive-OR mechanism to a first input of a second comparing mechanism,

means for gating said output of said third exclusive-OR mechanism to a second input of said second comparing mechanism,

means for gating said output of said second exclusive-OR mechanism to a first input of a third comparing mechanism,

means for gating said output of said third exclusive-OR mechanism to a second input of said third comparing mechanism, means for gating said NEW input to a first input of a fourth comparing mechanism, and

means for gating said LOW input to a second input of said fourth comparing mechanism,

said comparing mechanisms outputting signals for sorting the three words into two sets.

16. A system according to claim 15, wherein

means for gating said LESS output signal from said first comparing mechanism signal to a first input signal of a first AND logic mechanism,

means for gating said LESS output signal from said second comparing mechanism to a first input of a second AND logic mechanism,

means for gating said GREATER output signal from said first comparing mechanism to a first input of a third AND logic mechanism,

means for goring said LESS output signal from said third comparing mechanism to a second input of said first AND logic mechanism,

means for gating said LESS output signal from said third comparing mechanism to a second input of said third AND logic mechanism,

means for goring said GREATER output signal from said second comparing mechanism to a first input of a fourth AND logic mechanism,

means for gating said GREATER output signal from said second comparing mechanism to a first input of a fifth AND logic mechanism,

means for gating said GREATER output signal from said third comparing mechanism to a second input of said second AND logic mechanism,

means for gating said GREATER output signal from said third comparing mechanism to a second input of said fourth AND logic mechanism,

means for gating said GREATER output signal from said third comparing mechanism to a second input of said fifth AND logic mechanism,

means for gating an output signal of said first AND logic mechanisms to a first input of a first OR logic mechanism,

means for gating an output signal of said second AND logic mechanism to a second input of said first OR logic mechanism,

means for gating said LESS outputs signal from said fourth comparing mechanism to a third input of said fourth AND logic mechanism, and

means for gating said GREATER output signal of said fourth comparing mechanism to a third input of said fifth AND logic mechanism.

17. A system for computing three output signals from a new key, a low key, and a high key, said three output signals forming part of a control logic controlling a locating step in a binary tree, said system comprising

a bitwise parallel NAND function of three input words,

a bitwise parallel OR function of three input words,

five bitwise parallel AND functions of two input words,

two BIT REVERSAL functions accepting an input word and making available an output equal to said input word with the bits in said input word reversed from low order to high order,

a twos complementer having an input word and an output word which is the twos complement of said input word,

three funnel OR logic functions, each having a word of input and a single output bit signal, said output signal having a value of one if any of the bits in said input word has a value of one,

said new key, said low key, and said high key providing three words of input,

said new key input being gated to said NAND logic mechanism as a first word of input,

said low key input word being gated to said NAND logic mechanism as a second word of input,

said high key input word being gated to said NAND logic mechanism as a third word of input,

said new key input being gated to said OR logic mechanism as a first word of input,

said low key input word being gated to said OR logic mechanism as a second word of input,

said high key input word being gated to said OR logic mechanism as a third word of input,

output word of said NAND logic mechanism being gated to said first AND logic mechanism as a first input word,

output word of said OR logic mechanism being gated to said first AND logic mechanism as a second input word,

output word of said first AND logic mechanism being gated through said first said bit reversal mechanism,

output word of said first bit reversal logic mechanism being gated as an input word to said twos complementer logic mechanism,

output of said twos complementer logic mechanism being gated as an input word to said second bit reversal logic mechanism,

output of said second bit reversal logic mechanism being gated as a first input word to said second AND logic mechanism,

output of said first AND logic mechanism being gated as a second input word to second said AND logic mechanism,

output of said second AND logic mechanism being gated as a first word of input to said third AND logic mechanism, as a first word of input to said fourth AND logic mechanism, and as a first word of input to said fifth AND logic mechanism,

said new input key being gated to said third AND logic mechanism as a second word of input,

said low input key being gated to said fourth AND logic mechanism as a second word of input,

said high input key being gated to said fifth AND logic mechanism as a second word of input,

output of said third AND logic mechanism being gated to said first funnel OR logic mechanism,

output of said fourth AND logic mechanism being gated to said second funnel OR logic mechanism,

output of said fifth AND logic mechanism being gated to said third funnel OR logic mechanism,

output of said first funnel OR logic mechanism providing an output signal S1,

output of said second funnel OR logic mechanism providing an output signal S2,

output of said third funnel OR logic mechanism providing an output signal S3,

said output signals S1, S2, and S3 comprising control signals for controlling a locating step in a binary tree.

18. A system for computing a minimal difference compare function of three input words NEW, LOW, and HIGH, and having four output signals,

each said input word comprising an unsigned binary value,

said LOW input word having been predetermined to be numerically less than said HIGH input word,

said system for computing a minimal difference compare function comprising:

means for gating said NEW and LOW inputs to a first parallel exclusive-OR mechanism, means for gating said NEW and said HIGH inputs to a second parallel exclusive-OR mechanism, means for gating said LOW and HIGH inputs to a third exclusive-OR mechanism,

each said exclusive-OR mechanism comprising means for forming the parallel exclusive-OR of corresponding bits from said inputs to form an output comprising exactly the same number of bits as each said input,

means for gating said output of said first exclusive-OR mechanism to a first input of a first comparing mechanism, means for gating said output of said second exclusive-OR mechanism to a second input of said first comparing mechanism,

means for gating said output of said first exclusive-OR mechanism to a first input of a second comparing mechanism,

means for gating said output of said third exclusive-OR mechanism to a second input of said second comparing mechanism,

means for gating said output of said second exclusive-OR mechanism to a first input of a third comparing mechanism,

means for gating said output of said third exclusive-OR mechanism to a second input of said third comparing mechanism,

means for gating said NEW input to a first input of a fourth comparing mechanism,

means for gating said LOW input to a second input of said fourth comparing mechanism,

each said comparing mechanism comprising means for comparing each said first comparing mechanism input to each said second comparing mechanism input as unsigned binary numbers,

each said comparing mechanism thereby generating three output signals LESS, EQUAL, and GREATER, activating said LESS output signal if said first input of said each comparing mechanism is less than said second input of said each comparing mechanism,

activating said EQUAL output signal if said first input of said each comparing mechanism is equal to said second input of said each comparing mechanism input,

activating said GREATER output signal if said first input to said each comparing mechanism is greater than said second input to said each comparing mechanism,

means for gating said LESS output signal from said first comparing mechanism signal to a first input signal of a first AND logic mechanism,

means for gating said LESS output signal from said second comparing mechanism to a first input of a second AND logic mechanism,

means for gating said GREATER output signal from said first comparing mechanism to a first input of a third AND logic mechanism,

means for gating said LESS output signal from said third comparing mechanism to a second input of said first AND logic mechanism,

means for gating said LESS output signal from said third comparing mechanism to a second input of said third AND logic mechanism,

means for gating said GREATER output signal from said second comparing mechanism to a first input of a fourth AND logic mechanism,

means for gating said GREATER output signal from said second comparing mechanism to a first input of a fifth AND logic mechanism,

means for gating said GREATER output signal from said third comparing mechanism to a second input of said second AND logic mechanism,

means for gating said GREATER output signal from said third comparing mechanism to a second input of said fourth AND logic mechanism,

means for gating said GREATER output signal from said third comparing mechanism to a second input of said fifth AND logic mechanism,

means for gating an output signal of said first AND logic mechanisms to a first input of a first OR logic mechanism,

means for gating an output signal of said second AND logic mechanism to a second input of said first OR logic mechanism,

means for gating said LESS output signal from said fourth comparing mechanism to a third input of said fourth AND logic mechanism,

means for gating said GREATER output signal of said fourth comparing mechanism to a third input of said fifth AND logic mechanism,

whereupon said first OR mechanism provides an output signal representing the fact that said NEW input word is associated with words like said LOW word,

said third AND logic mechanism output signal representing the fact that said NEW word is associated with words like said HIGH word,

said fourth AND logic mechanism providing an output signalling that said NEW word is numerically smaller than said LOW word and numerically smaller than said HIGH word and the insertion point is determined,

said fifth AND logic mechanism providing an output signalling that the insert edge has been found and said NEW word is numerically higher than both said LOW word and said HIGH word,

whereupon all of above said mechanisms and means provide four output signals of said minimal difference comparing mechanism, said four output signals comprising said output signal of said first OR logic mechanism, said output signal of said third AND logic mechanism, said output signal of said fourth AND logic mechanism, and said output signal of said fifth AND logic mechanism,

said output signals providing control signals for a binary tree locating step, wherein

said output of said first OR logic mechanism providing a control signal directing said locating step to process nodes in a low subtree of a selected node,

said output of said third AND logic mechanism providing a control signal directing said locating step to process nodes in a high subtree of said selected node,

said output of said fourth AND logic mechanism providing a control signal directing said locating step to terminate with a signal indicating an insertion is to be performed on an edge in said binary tree where said NEW data number is a low successor of a new insertion node,

said output of said fifth AND logic mechanism providing a control signal to said locating step to terminate with a signal indicating an insertion is to be performed on an edge going to said selected node where said NEW data number is a high successor of said new node.