Bit string data sorting apparatus, sorting method, and program

A bit string data sort method for sort processing of keys to be sorted, which keys are expressed as bit strings, comprising:

• a keys-to-be-sorted storage step that stores the keys to be sorted in a keys-to-be-sorted storage means;
• a difference bit position calculating step that obtains a difference bit position, which is a position of a first differing bit found by a bit string comparison between a key stored in the keys-to-be-sorted storage means, which key is an object of a classification in classification processing that constitutes the sort processing, and a reference key taken from among keys subject to the classification;
• a difference bit position classifying step that, for each difference bit position obtained by the difference bit position calculating step, by writing identification information for the keys with that difference bit position into a key-to-be-classified difference bit position storage means, classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position;
• a sorted key outputting step that outputs a key as a sorted key if there is only one key with the same difference bit position classified by the difference bit position classifying step and if there is a plurality of keys with the same difference bit position, outputs from among the plurality of keys as the sorted key the reference key in a next classification processing;
• and
• a control step that controls the difference bit position calculating step, the difference bit position classifying step, and the sorted key outputting step so that
• the difference bit position calculating step obtains the difference bit position by taking all of the keys to be sorted as the object of the classification in an initial processing, and thereafter repeatedly obtains the difference bit position by taking a group of keys consisting of a plurality of keys, which group is classified at the difference bit position classifying step as having the same difference bit position, as the object of a further classification, and
• the difference bit position classifying step repeatedly classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position for each difference bit position obtained at the difference bit position calculating step, and
• the sorted key outputting step outputs the key as the sorted key when the difference bit position classifying step, for each difference bit position, classifies keys into a group with the same difference bit position.

A bit string data sort apparatus for sort processing of keys to be sorted, which keys are expressed as bit strings, comprising:

• a keys-to-be-sorted storage means that stores the keys to be sorted;
• a difference bit position calculating means that obtains a difference bit position, which is a position of a first differing bit found by a bit string comparison between a key stored in the keys-to-be-sorted storage means, which key is an object of a classification in classification processing that constitutes the sort processing, and a reference key taken from among keys subject to the classification;
• a key-to-be-classified difference bit position storage means that, for each difference bit position obtained by the difference bit position calculating means, stores identification information for the keys with that difference bit position;
• a difference bit position classifying means that, for each difference bit position obtained by the difference bit position calculating means, by writing the identification information for the keys with that difference bit position into the key-to-be-classified difference bit position storage means, classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position;
• a lower n bit sorting means that sorts keys in each group of keys with the same difference bit position classified by the difference bit position classifying means, by using n bits in each key that are positioned lower than the same difference bit position, in the sequence of difference bit positions;
• and
• a sorted key outputting means that outputs, as sorted keys, the reference key and the keys sorted by the lower n bit sorting means for each difference bit position in difference bit position sequence.

A bit string data sort method for sort processing of keys to be sorted, which keys are expressed as bit strings, comprising:

• a keys-to-be-sorted storage step that stores the keys to be sorted in a keys-to-be-sorted storage means;
• a difference bit position calculating step that obtains a difference bit position, which is a position of a first differing bit found by a bit string comparison between a key stored in the keys-to-be-sorted storage means, which key is an object of a classification in classification processing that constitutes the sort processing, and a reference key taken from among keys subject to the classification;
• a difference bit position classifying step that, for each difference bit position obtained by the difference bit position calculating step, by writing identification information for the keys with that difference bit position into a key-to-be-classified difference bit position storage means, classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position;
• a lower n bit sorting step that sorts keys in each group of keys with the same difference bit position classified at the difference bit position classifying step, by using n bits in each key that are positioned lower than the same difference bit position, in the sequence of difference bit positions;
• and
• a sorted key outputting step that outputs, as sorted keys, the reference key and the keys sorted at the lower n bit sorting step for each difference bit position in difference bit position sequence.

A bit string data sort apparatus for sort processing of keys to be sorted, which keys are expressed as bit strings, comprising:

• a keys-to-be-sorted storage means that stores the keys to be sorted;
• a key grouping means that, by a magnitude comparison between a reference key, which is an arbitrary key among all the keys to be sorted, and the keys other than the reference key stored in the keys-to-be-sorted storage means, splits the keys into a group of keys smaller than the reference key and a group of keys larger than the reference key;
• a difference bit position calculating means that obtains a difference bit position, which is a position of a first differing bit found by a bit string comparison between a key stored in the keys-to-be-sorted storage means, which key is an object of a classification in classification processing that constitutes the sort processing, and a reference key taken from among keys subject to the classification;
• a key-to-be-classified difference bit position storage means that, for each difference bit position obtained by the difference bit position calculating means, stores identification information for the keys with that difference bit position;
• a difference bit position classifying means that, for each difference bit position obtained by the difference bit position calculating means, by writing of identification information for the keys with that difference bit position into the key-to-be-classified difference bit position storage means, classifies the keys subject to the classification with the same difference bit position into groups;
• a sorted key outputting means that outputs a key as a sorted key if there is only one key with the same difference bit position classified by the difference bit position classifying means and, if there are a plurality of keys with the same difference bit position, outputs from among the plurality of keys a key to be the reference key in the next classification processing as the sorted key;
• and
• a control means that controls the key grouping means, the difference bit position calculating means, the difference bit position classifying means, and the sorted key outputting means so that, in the initial classification processing,
• the key grouping means splits the keys into a group of keys smaller than the reference key and a group of keys larger than the reference key, by means of a magnitude comparison between the reference key and all the key other than the reference key, and
• the difference bit position calculating means obtains the difference bit position between the reference key and the keys other than the reference key, and
• the difference bit position classifying means, for each difference bit position obtained by the difference bit position calculating means, writes the identification information for the keys with that difference bit position to the keys-to-be-classified difference bit position storage means for both the group of keys smaller than the reference key and the group of keys larger than the reference key, and
• in the following classification processing, for each of the groups smaller and larger than the reference key,
• the difference bit position calculating means repeatedly obtains a difference bit position by making for keys classified by the difference bit position classifying means as having the same difference bit position group consisting of a plurality of keys to be the object of a further classification, and
• the difference bit position classifying means repeatedly classifies groups with the same difference bit position for each difference bit position obtained by the difference bit position calculating means, and
• the sorted key outputting means outputs the key as the sorted key when the difference bit position classifying means, for each difference bit position, classifies the keys into a group with the same difference bit position.

A bit string data sort method for sort processing of keys to be sorted, which keys are expressed as bit strings, comprising:

• a keys-to-be-sorted storage step that stores the keys to be sorted in a keys-to-be-sorted storage means;
• a key grouping step that, by a magnitude comparison between a reference key, which is any arbitrary key among all the keys to be sorted, and the keys other than the reference key stored in the keys-to-be-sorted storage means, splits the keys into a group of keys smaller than the reference key and a group of keys larger than the reference key;
• a difference bit position calculating step that obtains a difference bit position, which is a position of a first differing bit found by a bit string comparison between a key stored in the keys-to-be-sorted storage means, which key is an object of a classification in classification processing that constitutes the sort processing, and a reference key taken from among keys subject to the classification;
• a difference bit position classifying step that, for each difference bit position obtained by the difference bit position calculating step, by writing identification information for the keys with that difference bit position into a key-to-be-classified difference bit position storage means, classifies the keys subject to the classification into groups of keys so that keys in each of the groups have same difference bit position;
• a sorted key outputting step that outputs a key as a sorted key if there is only one key with the same difference bit position classified by the difference bit position classifying step and if there is a plurality of keys with the same difference bit position, outputs from among the plurality of keys as the sorted key the reference key in a next classification processing;
• and
• a control step that controls the key grouping step, the difference bit position calculating step, the difference bit position classifying step, and the sorted key outputting step so that, in the initial classification processing,
• the key grouping step splits the keys into a group of keys smaller than the reference key and a group of keys larger than the reference key, by means of a magnitude comparison between the reference key and all the key other than the reference key, and
• the difference bit position calculating step obtains the difference bit position between the reference key and the keys other than the reference key, and
• the difference bit position classifying step, for each difference bit position obtained at the difference bit position calculating step, writes the identification information for the keys with that difference bit position to the keys-to-be-classified difference bit position storage means for both the group of keys smaller than the reference key and the group of keys larger than the reference key, and
• in following classification processing, for each of the groups smaller and larger than the reference key,
• the difference bit position calculating step repeatedly obtains a difference bit position by making for keys classified at the difference bit position classifying step as having the same difference bit position group consisting of a plurality of keys to be the object of a further classification, and
• the difference bit position classifying step repeatedly classifies groups with the same difference bit position for each difference bit position obtained at the difference bit position calculating step, and
• the sorted key outputting step outputs the key as the sorted key when the difference bit position classifying step, for each difference bit position, classifies the keys into a group with the same difference bit position.