JP4921453B2 - Bit string data sorting apparatus, method and program - Google Patents

Description

  The present invention relates to an apparatus, a method, and a program for sorting key data represented by a bit string.

  In recent years, with the progress of informatization of society, large-scale databases are being used in various places. In order to search for a record from such a large database, it is usual to search for an item in the record associated with the stored address of each record using an index key to find a desired record. A character string in full-text search can also be regarded as a document index key.

Since these index keys are expressed by bit strings, it can be said that a database search is reduced to a bit string search.
On the other hand, as a process related to the database, a sort process based on an index key of records in the database is performed. This sort process is also reduced to a bit string sort process.

  Various sort methods have been developed, and the following Patent Document 1 introduces quick sort, radic sort (radix sort), and the like. Patent Document 2 also describes radix sort.

  FIG. 1A is a diagram for explaining the concept of conventional radix sort. According to the radix sort, the key that is the 4-bit bit string to be sorted illustrated in FIG. 1A is sorted by repeating the classification by the bit value at each bit position from the 0th bit to the 3rd bit. The Hereinafter, the concept of the radix sort will be described with reference to FIG. 1A.

  FIG. 1A shows a key column 100 including keys to be sorted. In the example of FIG. 1A, the key “1111” is stored in the storage area in which the key position 101, which is the position of the key included in the key string 100, is 100a (hereinafter referred to as the key position 100a). Exists. In addition, keys “0011”, “1010”, “0001”, and “1110” exist at the key positions 100b, 100c100d, and 100e, respectively.

  As shown in the figure, first, classification by the 0th bit of the key included in the key string 100 is performed by the classification (0th bit) 110a for each bit position. As a result, a 0-bit value 0 set 120a composed of the key “0001” and the key “0011” and a value 1 set 121a composed of the key “1111”, the key “1010”, and the key “1110” are obtained. Next, the set 0a of the value 0 is classified by the value of the first bit by the classification (first bit) 110b for each bit position, and the set 121a of the value 1 is classified by the value of the first bit by the classification (first bit) 110e for each bit position. Done.

  In the classification (first bit) 110b for each bit position, since the first bits of the key “0001” and the key “0011” are both 0, only the set 120b of the value 0 of the first bit is obtained, and 0 bit The same key as the set 120a of the eye value 0 becomes the target of classification by the second bit, and classification by the second bit is performed by the classification (second bit) 110c for each bit position. In the classification (second bit) 110c for each bit position, one key “0001” is obtained as a set 120d of the value 0 of the second bit, so the key of the sorted key string 130 that stores the key that is the minimum value Is stored in a storage area 130a (hereinafter referred to as key position 130a). Similarly, since one key “0011” is obtained as the set 121d of the value 1 of the second bit, it is stored in the key position 130b for storing the key of the next value of the minimum value of the sorted key string 130. Note that the sorted key string is stored from the smaller key in the code order of the key position.

  On the other hand, in the classification of each bit position (first bit) 110e, one key “1010” is obtained as the set 120e of the value 0 of the first bit, which is the next storage position of the sorted key string 130. Stored in key position 130c. Also, a set of the key “1111” and the key “1110” is obtained as the value 1 set 121e of the first bit, and the classification of each bit position (second bit) 110f is based on the value of the second bit. Classification is performed.

  In the classification (second bit) 110f for each bit position, since the second bits of the key “1111” and the key “1110” are both 1, only the set 121f of the value 1 of the first bit can be obtained. The same key as the eye value 1 set 121e is the target of classification by the third bit, and classification by the value of the third bit is performed by the classification (third bit) 110g for each bit position. In the classification (third bit) 110g for each bit position, one key “1110” is obtained as a set 120g of the third bit value 0, so that the key position 130d, which is the next storage position of the sorted key string 130, is obtained. Stored. Similarly, since one key “1111” is obtained as a set 121g of the value 1 of the third bit, it is stored in the key position 130e that is the next storage position of the sorted key string 130.

Through the above processing, the keys in the key string 100 are sorted and stored in the key positions 130a to 130e of the sorted key string 130. However, when sorting is performed by the above-described radix sort method, as shown in the classification for each bit position (first bit) 110b and the classification for each bit position (second bit) 110f shown in FIG. Invalid processing that does not occur occurs.

JP 2002-116907 A JP 2005-316663 A

Therefore, the problem to be solved by the present invention is to provide an efficient sorting method in which invalid processing does not occur in the sort processing of bit string data.

  According to the sorting process of the present invention, a bit string comparison between a key that is a reference and a bit string that is a sort target is performed, a difference bit position that is a bit position that is a different bit value is first obtained, and sorting by the difference bit position is performed. The target key is classified, and the sorted key string is obtained by further repeating the classification based on the difference bit position for the reference key among the plurality of keys classified into the same difference bit position.

  According to the present invention, since the keys are sorted by the difference bit position, invalid processing that does not perform classification does not occur. Therefore, efficient sort processing can be realized.

Hereinafter, the best mode for carrying out the present invention will be described by exemplifying the same key as the key included in the key column 100 shown in FIG. 1A as a sort target key.

FIG. 1B is a diagram for explaining the concept of the sorting process based on the difference bit position according to the embodiment of the present invention. The sort target key string 100 and the sorted key string 130 are the same as those shown in FIG. 1A.

  Each key constituting the key string 100 has a difference bit position of 0 for the minimum value key 148a, the key group 142a whose difference bit position is 2 with respect to the minimum value key, and the minimum value key 148a in the classification 149a based on the difference bit position. The key group 140a is classified as follows. In the illustrated example, the minimum value key 142a is “0001”. Only the key “0011” is included in the key group 142a, and the keys “1010”, “1111”, and “1110” are included in the key group 140a. The minimum value key 148a can be obtained when the key is read from the key string 100 into the input buffer for sorting processing based on the difference bit position.

The minimum value key 148a is stored in the key position 130a of the sorted key row 130 as indicated by the dotted arrow 158a in the figure. Further, since there is only one key in the key group 142a, the key group 142a is stored in the key position 130b of the sorted key row 130 as indicated by the dotted arrow 152a in the figure.

Since the key group 140a whose difference bit position with respect to the minimum value key 148a is 0 includes a plurality of keys, as shown in the dotted arrow set 150a in FIG. The minimum value key 148b in 140a and the key group 141b in which the difference bit position between the minimum value key 148b is 1 are classified. In the illustrated example, the minimum value key 148b is “1010”. The key group 141b includes a key “1111” and a key “1110”.

The minimum value key 148b is stored in the key position 130c of the sorted key row 130 as indicated by the dotted arrow 158b in the figure.
Meanwhile, since the key group 141b difference bit position is 1 and the minimum value key 148 b includes multiple keys, as shown in the set 151b of FIG dashed arrows, in the classification 149c by the difference bit position The key group 143c is classified into a key group 143c having a difference bit position of 3 between the minimum value key 148c in the key group 141b and the minimum value key 148c. In the illustrated example, the minimum value key 148c is “1110”. The key group 143c includes only the key “1111”.

The minimum value key 148c is stored in the key position 130d of the sorted key row 130 as indicated by the dotted arrow 158c in the figure. Further, since there is only one key in the key group 143c, the key group 143c is stored in the key position 130e of the sorted key row 130 as indicated by a dotted arrow 153c in the figure.

Through the above processing, the keys of the key string 100 are stored in ascending order at the key positions 130a to 130e of the sorted key string 130, and the sorting process is completed. Since the sorting process according to the present embodiment repeats the classification based on the difference bit position, the key classification is always executed for each classification process. In the above example, the minimum value key is used as a reference key for calculating the difference bit position. However, the maximum value key may be used as a reference key for calculating the difference bit position. In this case, in the example of the sorting target key in FIG. 1B, the maximum value key is the key “1111”, and the maximum value key and the key “3” as the result of the classification process based on the first difference bit position. A key “1010” having a difference bit position of 1 and a key “0011” and “0001” having a difference bit position of 0 is obtained.

  Next, an example of a functional block configuration for realizing the sort processing based on the difference bit position in the present embodiment whose concept has been described with reference to FIG. 1B will be described. In the sorting process based on the difference bit position in the present embodiment, functional blocks that execute processes such as classification 149a, 149b, and 149c based on the difference bit position illustrated in FIG. 1B are prepared for all combinations of keys to be sorted. Obviously, this is feasible. However, this is a waste of resources, and the realization method is not realistic. Therefore, in the present embodiment, the following devices are devised.

  FIG. 2A explains the data structure used in the sort processing based on the difference bit position in the embodiment of the present invention. As shown in FIG. 2A, a key table 309, a difference bit position table 310, a link table 311 and a sorted key table 313 are used.

  The key table 309 is set by reading the sort target key 602 when a sort request is made. In the example of FIG. 2A, as the five keys 602 to be sorted, those included in the key column 100 shown in FIGS. 1A and 1B are read. The head of the reading position 601 in the key table 309 is P0, and is followed by P1, P2, P3, and P4. Although the minimum value key “0001” is set at the reading position P0, it may be set in another area. As indicated by the dotted arrow 689c, the minimum value key is stored at a predetermined position in the sorted key table 313.

The difference bit position table 310 stores the read position 601 of the smallest key among the keys having the same difference bit position with respect to the minimum value key as the parent link 612 for each difference bit position 611. In the example of FIG. 2A, as indicated by a dotted arrow 660a, the smallest key “1010” among the keys “1111”, “1010”, and “1110” whose difference bit position is 0 from the minimum value key “0001”. Read position P3 is stored at a position where the difference bit position 611 of the difference bit position table 310 is zero. Also, as indicated by the dotted arrow 662a, the key having the difference bit position 2 from the minimum value key “0001” is only the key “0011”, and thus the key “0011”.
Read position P2 is stored at a position where the difference bit position 611 of the difference bit position table 310 is 2.

  The link table 311 is for accessing a key having the same differential bit position with respect to the minimum value key. As shown in the figure, a link 622 indicating a key reading position having the same differential bit position is stored with respect to the key reading position 621.

As indicated by the dotted arrow 673b from the difference bit position table 310 to the link table 311, the read position P3 is referred to as the read position 621 with respect to the read position P3 of the minimum value key of the key having the same difference bit position 0. The same as the minimum value key “1010” of the key having the difference bit position 0 with respect to the minimum value key “0001” at the read position of the link table 311 (hereinafter referred to as the read position P3 of the link table 311). The read position P4 of the key table 309 of the key “1110” having the difference bit position 0 is stored.

As indicated by the dotted arrow 674c in the figure, the reading position P1 of the key table 309 of the key “1111” having the same differential bit position 0 is stored at the reading position P4 of the link table 311. Also, as indicated by the dotted arrow 671c in the figure, the reading position P1 of the key table 309 having the same value is stored in the reading position P1 of the link table 311. This indicates that there is no more key having the same differential bit position 0.

Further, as indicated by the dotted arrow 672b from the difference bit position table 310 to the link table 311, the read position P2 of the link table 311 is compared with the read position P2 of the minimum value key of the key having the same difference bit position 2. Stores the reading position P2 of the key table 309 having the same value as the reading position P2 of the link table 311. This indicates that the key “0011” at the reading position P2 in the key table 309 is the smallest key and the last one of the key whose difference bit position is 2 from the minimum value key “0001”. .

The states of the difference bit position table 310 and the link table 311 shown in FIG. 2A described above are obtained by executing the classification 149a based on the difference bit positions shown in FIG. 1B.
As is apparent from the above description, the key table 309 described above is an example of the sort target key storage means of the invention according to claim 1. The difference bit position table 310 and the link table 311 constitute one embodiment of the classification target key difference bit position storage means, and the reading position 601 of the key table 309 corresponds to key identification information.

FIG. 2B is a diagram illustrating a functional block configuration of the bit string data sorting device according to the embodiment of the present invention.
As shown in the figure, the bit string data sorting device 200 includes a difference bit position calculation means 210, a difference bit position classification means 220, a sorted key output means 230, and a control means 240. Hereinafter, an outline of the operation of each unit will be described with reference to the example of FIG. 2A.

  The difference bit position calculation means 210 calculates the difference bit position of the key to be classified by the difference bit position from the keys 602 stored in the key table 309. The control unit 240 sets all the keys stored in the key table 309 as the target of the first classification process. In this case, the key serving as a reference for calculating the difference bit position is the minimum value key “0001” stored at the reading position P0. The sorted key output unit 230 outputs the minimum value key “0001” to the sorted key table 313.

  The difference bit position classification unit 220 writes the difference bit position table 310 and the link table 311 based on the calculation result of the difference bit position calculation unit 210. As a result, the key identification information is classified into a set (P3, P4, P1) with a difference bit position of 0 and a set (P2) with a difference bit position of 2 with the reading position 601 of the key table 309 as a reading position.

  The control unit 240 performs control so that the difference bit position calculation by the difference bit position calculation unit 210 and the classification process by the difference bit position classification unit 220 are repeated for a set including a plurality of keys after classification.

FIG. 3 is a diagram for explaining a hardware configuration example for carrying out the present invention.
Sort processing according to the present invention is performed by a data processing device 301 including at least a central processing unit 302 and a cache memory 303 using a data storage device 308. The data storage device 308 having the key table 309, the difference bit position table 310, the link table 311, and the sorted key table 313 can be realized by the main storage device 305 or the external storage device 306, or via the communication device 307. It is also possible to use a remotely located device connected.

  In the example of FIG. 3, the main storage device 305, the external storage device 306, and the communication device 307 are connected to the data processing device 301 by a single bus 304, but the connection method is not limited to this. In addition, the main storage device 305 can be in the data processing device 301, the key table 309 is in the external storage device 306, and other tables are in the main storage device 305. It is obvious that the hardware configuration can be appropriately selected according to the size of the set of sorting target keys.

  Although not particularly illustrated, it is natural that the temporary storage area of the main storage device 305 corresponding to each process is used in order to use various values obtained during the process in the subsequent process. . In the following description, a value stored or set in the primary storage area may be referred to as a temporary storage area name.

  Next, sorting processing according to an embodiment of the present invention will be described in detail with reference to FIGS. 4A and 4B. Moreover, in the description, it demonstrates using the illustration of FIG. 1B or FIG. 2A suitably.

  FIG. 4A is a diagram for explaining the processing flow of the sorting processing at the first stage of the sorting processing and the output processing of sorted keys in one embodiment of the present invention. It is assumed that a key to be sorted is stored in the key table, and a minimum value key is stored at the top reading position of the key table. That is, the keys included in the key string 100 shown in FIG. 1B are stored in the key table 309 as shown in FIG. 2A.

First, in step S401, the head position of the key table is set to a key table reading position (hereinafter, simply referred to as a reading position). The “reading position of the key table” here is one of the “temporary storage areas corresponding to each processing in order to use various values obtained during the processing in the subsequent processing” described above. . In the following description, it is sometimes omitted that “the key table read position” is a primary storage area (not shown), such as “the head position of the key table is set as the key table read position”. .
With the above setting, in the example of FIG. 2A, P0 is set at the reading position of the key table.

In step S402, the key pointed to by the head position is extracted from the key table as the minimum value key. Here, “take out as a minimum value key” means to set to a minimum value key which is a primary storage area (not shown). In the following, similar notation may be used.

  Proceeding to step S403, the next reading position is set as the reading position. Next, in step S404, it is determined whether all the keys have been processed, that is, whether the classification process at the first stage for all the keys has been completed.

If all the keys have not been processed, the process proceeds to step S405, where the key pointed to by the reading position is extracted from the key table as a sort key, and the reading position is set as the reading position of the sort key. In step S406, the difference bit position between the sort key and the minimum value key is obtained, the sort key is classified by the difference bit position, and the process returns to step S403.
In the process of step S406, the difference bit position table and the link table are set as the classification process in the first stage. Details of the processing will be described later with reference to FIGS. 5A and 5B.

  On the other hand, if it is determined in step S404 that all the keys have been processed, the process branches to step S407, where the minimum value key obtained in step S402 is set in the sorted key table, and the steps after step S408 shown in FIG. 4B are performed. Proceed to the process. With the above processing, the values of the entries in the difference bit position table 310 and the link table 311 are set as illustrated in FIG. 2A. Further, the minimum value key “0001” is stored in the sorted key table 313.

  FIG. 4B is a diagram illustrating a processing flow of the sorting process and the sorted key output process after the first stage of the sort process according to the embodiment of the present invention.

  In step S408, the difference bit position in the difference bit position table, that is, the maximum value of the difference bit position that the sort target key may have is set as an initial value in the difference bit position that is a primary storage area (not shown). In the example of FIG. 2A, 3 is set as the maximum value of the difference bit position.

  In step S409, it is determined whether entries for all the difference bit positions in the difference bit position table have been processed. If processed, the sort process is terminated, and if not processed, the process proceeds to step S410.

In step S410, the parent link is read from the entry indicated by the difference bit position from the difference bit position table. If the parent link is stored in the entry indicated by the difference bit position, the read parent link is set as the parent link which is the primary storage area. That is, a notation such as “read parent link” in the description of this embodiment may mean that the parent link is read and set to a parent link which is a primary storage area (not shown). The same applies to items other than the parent link.
In step S411, it is determined whether the parent link has been set. If it has not been set, the value is decremented by 1 from the difference bit position in step S416, and the process returns to step S409.

  In step S412, the key pointed to by the parent link (key table read position) set in step S410 is extracted from the key table as a sorted key, and the extracted sorted key is set in the sorted key table. As described above, since the key whose read position is stored in the difference bit position table is the minimum value key among the keys classified into the same difference bit position, the sorted key table in step S412. Set to.

  Next, in step S413, the link pointed to by the parent link set in step S410 is read from the link table as the next link. In step S414, the parent link pointed to by the difference bit position in the difference bit position table is deleted, and the flow returns to step S415. move on. Here, the parent link pointed to by the difference bit position in the difference bit position table is deleted because the minimum value key classification process in which the reading position of the key table is the parent link has been completed in step S412, and the difference bit position table no longer exists. This is because the above parent link is not necessary and the influence on the subsequent processing due to this parent link remaining in the difference bit position table is avoided.

In step S415, it is determined whether the next link read in step S413 is the same as the parent link set in step S410.
If it is determined in step S415 that the next link and the parent link are the same, the process returns to step S409 via step S416 described above.
By the loop processing from step S409 to step S416 described above, the sorted keys are extracted and stored in the sorted key table in descending order of the difference bit positions. Since the value of the key with the larger difference bit position is closer to the value of the minimum value key, the sorted key can be stored in the sorted key table in ascending order by extracting the sorted key in descending order of the difference bit position. it can.

  In step S415, it is determined that the next link and the parent link are the same when the key having the difference bit position in which the parent link is stored has only the key having the parent link as the reading position of the key table. In the example of FIG. 2A, the read position 621 of the link table 311 is P2, and the link 622 is P2. Further, in the example of FIG. 1B, this corresponds to the case where the key group 142a is composed of only the key “0011” and the classification process for the key group 142a is not performed. In this case, since it means that the classification process for the difference bit position whose parent link is stored in the difference bit position table is completed, the value 1 is reduced from the difference bit position, and step S409 for the next difference bit position is performed. The process proceeds to ~ S415. In the example of FIG. 1B, processing is performed for the key group 140a at the difference bit position 0.

  On the other hand, if it is determined in step S415 that the next link and the parent link are not the same, the process proceeds to step S417, and a plurality of keys having the same differential bit position (set in step S408 or step S416) are subordinated. Is further classified according to the difference bit position. Details of the processing in step S417 will be described later with reference to FIG. 5C.

When it is determined that the next link and the parent link are not the same, in the example of FIG. 2A, the read position 621 of the link table 311 is P3 and the link 622 is P4. In the example of FIG. 1B, classification 149b and 149c based on difference bit positions is executed for a plurality of keys in the key group 140a.
In step S417, the difference bit position table and the link table are reset, and the process returns to step S408. Then, the process for the set differential bit position of the parent link in the reset differential bit position table is repeated.

The above-described processing is repeated until it is determined in step S409 that all the differential bit position entries in the differential bit position table have been processed, and when the determination is obtained, sorting of the sorting target keys is completed. The process is terminated.
The process illustrated in FIG. 4B is a process in which the key used as a reference for calculating the difference bit position is the minimum key, the process is performed in the descending order of the difference bit positions, and the sorted keys are extracted in the ascending order. However, as described above, when the key used as the reference for calculating the difference bit position is the maximum key, the reading position of the maximum key among the keys having the same difference bit position with respect to the reference key It was a parent link, that can be taken out sorted key in descending order by performing the forward processing descending the difference bit position will be apparent to those skilled in the art by the description of the specification and drawings.

Next, with reference to FIG. 5A and FIG. 5B, processing for classifying keys in one embodiment of the present invention will be described. What is described in FIGS. 5A and 5B is a detailed processing flow of the processing in step S406 shown in FIG. 4A and the processing in step S524 shown in FIG. 5C described later.
FIG. 5A is a diagram for explaining the processing flow of the previous stage of the processing for classifying the keys in one embodiment of the present invention.

As shown in the figure, in step S501, the key set as the sort key and the key set as the minimum value key are compared as a bit string, and the bit position of the first non-matching bit viewed from the upper 0 bit is represented as a difference bit. Set to position. The sort key is set in step S405 shown in FIG. 4A or step S522 shown in FIG. 5C described later, and is a target key for the classification process shown in FIGS. 5A and 5B.

Next, in step S502, the parent link indicated by the difference bit position set in step S501 is read from the difference bit position table, and in step S503, it is determined whether the parent link has been set. If the parent link has not been set, the process proceeds to step S504, where the sort key read position is set to the parent link pointed to by the difference bit position in the difference bit position table. In step S505, the sort key read position is pointed to. The sorting key reading position is set for the link, and the process is terminated.

  In the difference bit position table, the read position of the smallest key among the keys having the same difference bit position as described above is stored as the parent link. However, in the process of step S504, the first sort key is stored. As the temporary minimum value key, the read position of the sort key is set to the parent link pointed to by the difference bit position in the difference bit position table. Once the parent link has been set, that is, when the determination in step S503 is that the parent link has been set, the process proceeds to the subsequent processing shown in FIG. 5B, and the minimum value key is updated by comparing the sort key and the minimum value key. Finally, among the keys having the same difference bit position, the read position of the smallest key is stored as a parent link in the difference bit position table.

  Note that the sort key reading position in the processing of step S504 is set in step S405 shown in FIG. 4A or in step S523 shown in FIG. 5C described later.

FIG. 5B is a diagram for explaining the processing flow of the latter stage of the processing for classifying the keys in one embodiment of the present invention.

  As shown in the figure, in step S506, the key pointed to by the parent link is read from the key table as the parent sort key, and in step S507, it is determined whether the sort key is smaller than the parent sort key.

If it is determined in step S507 that the sort key is smaller than the parent sort key, the process advances to step S508 to set the sort key read position to the parent link pointed to by the difference bit position in the difference bit position table, and in step S509, the sort key of the link table. The parent link obtained in step S502 is set to the link pointed to by the read position, and the process ends.

The processing in step S508 described above is performed in order to set the read position of the smaller key among the keys having the same difference bit position in the parent link pointed to by the difference bit position in the difference bit position table. To update the parent link. Then, the process of step S509 sets the parent link set in the difference bit position table to the link of the link table pointed to by the read position of the sort key newly set in the difference bit position table. The information for tracing the reading position in the key table of the key having the same differential bit position is held.

  On the other hand, if it is determined in step S507 that the sort key is not smaller than the parent sort key, the process proceeds to step S510, and the link pointed to by the parent link is read from the link table as the next link. In step S511, the next link and the parent link are the same. judge.

  If it is determined in step S511 that the next link and the parent link are the same, in step S512, the read position of the sort key is set to the link indicated by the parent link in the link table. In step S513, the sorting key reading position is set in the link indicated by the sorting key reading position in the link table, and the process ends.

  On the other hand, if it is determined in step S511 that the next link and the parent link are not the same, the process advances to step S514 to set the sort key reading position to the link pointed to by the parent link in the link table. In step S515, the next link obtained in step S510 is set to the link pointed to by the read position of the sort key in the link table, and the process ends.

  The determination in step S511 described above is the same as the determination as to whether there is only one classified key among keys having the same differential bit position. If there is only one classified key, the read position is stored in the link of the link table indicated by the read position of this key. Therefore, it is updated at the read position of the sort key, and the read position of the sort key is set in the link of the link table pointed to by the read position of the sort key to indicate that the sort key is the last classified key at that time. When there are two or more classified keys, the sort key read position is inserted between the link relationship between the parent link and the next link expressed in the link table by the processing of step S514 and step S515.

Next, with reference to FIG. 5C, a detailed processing flow of processing for further classifying a plurality of keys having the same difference bit position in the embodiment of the present invention, which is processing in step S417 shown in FIG. 4B, will be described. To do.
FIG. 5C is a diagram illustrating a detailed process flow of a process of further classifying a plurality of keys having the same differential bit position in the embodiment of the present invention.

  As shown in the drawing, in step S521, the sorted key is set as the minimum value key. The sorted key is obtained in step S412 shown in FIG. 4B, and serves as a reference key for calculating the difference bit position of the sort key in step S524 described later.

Proceeding to step S522, the key pointed to by the next link is extracted from the key table as a sort key, and the next link is set as the read position of the sort key. In step S523, the link pointed to by the next link is read from the link table and saved in the save area. The next link in step S522 is a link indicated by the parent link read from the link table in step S413 shown in FIG. 4B. In the case of the classification processing of the key having the difference bit position 0 in the example of FIG. 2A, the parent link is P3, the next link is P4, and the link pointed to by the next link and saved in the save area is P1.

  In step S523, the link pointed to by the next link is saved in the next step S524, in which the sorting key set in step S522 is classified based on the difference bit position with respect to the minimum value key set in step S521. This is because the value of the link pointed to by the next link in the link table is rewritten, so that it is saved in advance and the processing using the link pointed to by the next link after step S524 is normally performed.

  In step S524, the process of obtaining the difference bit position between the sort key and the minimum value key and classifying the sort key based on the difference bit position, which has been described in detail with reference to FIGS. 5A and 5B, is executed.

  In step S525, it is determined whether the next link and the save link match. If the evacuation link matches the next link, the process ends because there are no remaining keys to be classified having the same differential bit position.

  On the other hand, if it is determined in step S525 that the save link does not match the next link, the save link is set as the next link in step S526, and the process returns to step S522, and the newly set next link is set as the key table read position. The classification process is continued using the key to be sorted as the sort key to be classified.

  The loop processing of steps S522 to S526 described above is repeated until the save link matches the next link, that is, until there is no key to be classified, and the processing is ended when there is no key to be classified.

  The best embodiment of the present invention has been described in detail above. In the following, in order to further facilitate the understanding of the present invention, the processing of the example of FIGS. 1B and 2A will be described with reference to FIGS. 6A to 7.

FIG. 6A is a diagram for explaining the data flow of the first-stage processing for extracting keys in ascending order according to an embodiment of the present invention.
FIG. 6A shows a data flow for setting the keys included in the key column 100 in the key table 309.

  The key “1111” at the key position 100a is set to the reading position P1 of the key table 309 as indicated by the dotted arrow 651a. Similarly, the key “0011” at the key position 100b is set to the read position P2 of the key table 309 as indicated by the dotted arrow 651b, and the key “1010” at the key position 100c is indicated by the dotted arrow 651c. The key “1110” at the key position 100e is set at the reading position P3 in the key table 309 as indicated by the dotted arrow 651e. The key “0001” at the key position 100d is set at the reading position P0 in the key table 309 as the minimum value key as indicated by the dotted arrow 651d.

  FIG. 6A (b) shows a state in which the minimum value key is extracted as the sorted key in the first-stage classification process, and the sorting target key is classified by the difference bit position using the minimum value key as a reference key. . It is similar to that shown previously in FIG. 2A. The minimum value key “0001” set at the head reading position P0 of the key table 309 is set at the head writing position 640a of the sorted key table 313 as indicated by an arrow 689c.

  Also, as indicated by the dotted arrow 660a in the figure, the read position P3 of “1010”, which is the smallest key among the three keys whose difference bit position is 0, is the parent of the difference bit position 0 of the difference bit position table 310. The read position P2 of “0011”, which is one key having a difference bit position of 2 and the smallest key, is stored as a link in the difference bit position 2 of the difference bit position table 310 as a parent link.

  In the link table 311, as indicated by dotted arrows 673 b and 672 b, the read position of the key having the same difference bit position is stored in the read position 621 of the parent link set in the difference bit position table 310. . That is, P4 is stored as the link 622 at the reading position 621 pointed to by the parent link P3, and P2 is stored as the link 622 at the reading position 621 pointed to by the parent link P2.

  As indicated by a dotted arrow 674c, P1 is stored as the link 622 at the reading position 621 pointed to by the link P4, and the same reading position P1 is stored as the link 622 at the reading position 621 pointed to by the link P1. This indicates that there are no more keys with the same differential bit position 0. That is, the key “1111” at the reading position P1 in the key table 309 is the last key in the link table 311 at the same differential bit position.

The fact that P2 is stored in the link 622 with the reading position 621 being P2 corresponds to the fact that the key “0011” at the reading position P2 in the key table 309 is the only key in the link table 311 at the same differential bit position. is doing.
The setting of the difference bit position table 310 and the link table 311 shown in (b) of FIG. 6A will be described in detail later with reference to FIG.

  FIG. 6C shows a key group including the key “0011” having the parent link P2 whose difference bit position 611 is 2 as a reading position among the key groups classified in the first-stage classification processing (actual Is a diagram for explaining the flow of storing the minimum value key “0011” in the sorted key table 313 as a sorted key.

  The parent link 612 is extracted in descending order of the difference bit position 611 of the difference bit position table 310. In the example shown in the figure, the parent link P2 of the entry whose difference bit position 611 indicated by the arrow 682 is 2 is extracted, and as shown by the arrow 682b in the figure, the key is read from the reading position 601 indicated by the parent link P2 in the key table 309. “0011” is read and written to the write position 640b of the sorted key table 313 as indicated by an arrow 682c.

  On the other hand, since the link 622 stored in the reading position 621 of the link table 311 corresponding to the parent link P2 indicated by the arrow 672b is the same P2 as the parent link 612, no further classification regarding the difference bit position 2 is performed. Therefore, the parent link P2 stored in the difference bit position 2 of the difference bit position table 310 is deleted so as not to hinder subsequent processing.

FIG. 6B is a diagram for explaining the data flow of the middle stage processing for extracting the keys in ascending order according to the embodiment of the present invention.
FIG. 6B (d) shows a case where the classification process for the difference bit position 0 is started as shown by the arrow 680a in the figure following the process for the difference bit position 2 shown in (c) of FIG. 6A. This is the state of the difference bit position table 310 and the link table 311. This state is the same as that shown in (b) of FIG. 6A except that the parent link P2 is deleted from the entry of the difference bit position 2 in the difference bit position table. However, the value of the entry at the reading position P2 in the link table 311 is unnecessary and is omitted.

  FIG. 6B (e) shows the flow of the classification process of the key whose difference bit position is 0 when the minimum value key “0001” shown in FIG. 6A (b) is used as a reference key. is there. In the illustration of FIG. 1B, it corresponds to the classification 149b by the difference bit position.

The parent link P3 at the difference bit position 0 of the difference bit table 310 indicated by the arrow 680a is extracted, and the key table 309 is indicated by the dotted arrow 683d from the key table 309 with P3 indicated by the dotted arrow 683b as the reading position. stored key to the reading position P3 for "1010", that is set in sorted key 650 keys are temporary storage area is taken out as sorted key in step S412 shown in FIG. 4B pointed to parent link P3, further The data is written to the writing position 640c of the sorted key table 313.

  On the other hand, the key “1010” which is the minimum value key among the keys having the same differential bit position 0 with respect to the key “0001” which is the minimum value key among the previous classification target keys set in the sorted key 650. , And the difference bit position 1 between the keys “1111” and “1110” having the same difference bit position 0 is calculated, and P4 which is the reading position of the smaller key as indicated by the dotted arrow 661a in the figure. Is stored as the parent link 612 in the entry whose difference bit position 621 is 1 in the difference bit position table 310.

  Further, as shown by an arrow 674b, the read position P1 is stored in the link 622 of the link table 311 pointed to by the parent link P4, and the link of the link table 311 pointed to by the read position P1 has the same P1 as shown by the arrow 671c. Is stored.

  FIG. 6B (f) shows the flow of the classification process of the key whose difference bit position is 3 when the minimum value key “1010” shown in (e) of FIG. 6B is used as a reference key. is there. In the example of FIG. 1B, it corresponds to the classification 149c by the difference bit position.

  The parent link P4 at the difference bit position 1 of the difference bit table 310 indicated by the arrow 681a is taken out, and the key table 309 is indicated by the dotted arrow 684d from the key table 309 with P4 indicated by the dotted arrow 684b as the reading position. The key “1110” stored at the read position P4, that is, the key pointed to by the parent link P4 is extracted as the sorted key in step S412 shown in FIG. 4B and set to the sorted key 650 which is the primary storage area. It is written at the write position 640d of the completed key table 313.

On the other hand, for the key “1010” that is the minimum value key among the previous classification target keys set as the sorted key 650, the key “1110” that is the minimum value key among the keys having the same difference bit position 1 is set. ”And the difference bit position 3 between the key“ 1111 ”having the same difference bit position 1 is calculated, and the smaller one, that is, P1 which is the read position of the only key, as indicated by the dotted arrow 662a in FIG. The difference bit position 621 in the difference bit position table 310 is stored as an parent link 612 in an entry whose number is 3.
Further, as indicated by an arrow 671b, the link 622 in the link table 311 indicated by the parent link P1 stores P1 having the same value as the parent link.

FIG. 6C is a diagram for explaining the data flow of the final stage processing for extracting the keys in ascending order according to the embodiment of the present invention. That is, only the parent link P1 of the entry of the difference bit position 3 is stored in the difference bit position table 310 by the process shown in FIG. 6B (f).

  Since the parent link 612 is extracted in descending order of the difference bit position 611 of the difference bit position table 310, in the example shown in the figure, the parent link P1 of the entry whose difference bit position 611 indicated by the arrow 683a is 3 is extracted, As shown by the arrow 681b, the key “1111” is read from the reading position 601 indicated by the parent link P1 of the key table 309 and written to the writing position 640e of the sorted key table 313 as shown by the arrow 681c.

On the other hand, since the link 622 stored in the reading position 621 of the link table 311 corresponding to the parent link P1 indicated by the arrow 671b is the same P1 as the parent link 612, no further classification regarding the difference bit position 3 is performed. Therefore, the parent link P1 stored in the difference bit position 3 of the difference bit position table 310 is deleted.
Then, all the parent links in the difference bit position table 310 are deleted, and the processes for all the difference bit positions are completed, so all the processes are ended.

FIG. 7 is a diagram for explaining the data flow of the first-stage classification process, that is, the setting of the difference bit position table 310 and the link table 311 shown in FIG. 6A (b).
FIG. 7A shows an initial state in which the key 602 is set in the key table 309 and nothing is set in the difference bit position table 310 and the link table 311.

The key “0011” stored at the reading position P2 is omitted. As for the key “0011”, the key whose difference bit position is 2 with respect to the minimum value key “0001” is the only one. Therefore, since the setting regarding the read position P2 of the difference bit position table and the link table 311 is completed at one time in steps S504 and S505 shown in FIG. 5A, it is omitted because it is easy to understand the setting.

  FIG. 7B shows a data flow of processing relating to the key “1111” stored at the reading position P1 of the key table 309. As indicated by dotted lines 680d and 681d, the difference bit position 0 is calculated by bit string comparison with the minimum value key “0001” stored at the reading position P0, and as indicated by the dotted arrow 660a, The reading position P1 is set at the difference bit position 0. Further, as indicated by a dotted arrow 671b, P1 is set at the reading position P1 of the link table 311.

  FIG. 7C shows a data flow of processing relating to the key “1010” stored at the reading position P3 of the key table 309. As indicated by dotted lines 680d and 683d, the difference bit position 0 is calculated by bit string comparison with the minimum value key “0001” stored at the read position P0. Then, the size comparison with the key “1111” having the parent link P1 set to the difference bit position 0 in the difference bit position table 310 as the reading position is performed in step S507 shown in FIG. 5B. Since the key at the reading position P3 is smaller, the entry at the difference bit position 0 in the difference bit position table 310 is updated to the reading position P3 as indicated by the dotted arrow 660a. Further, as indicated by a dotted arrow 673b, P1 is set at the reading position P3 of the link table 311. By this setting, as shown by an arrow 671c, a link relationship is maintained in which the difference bit positions of the key at the reading position P3 and the key at the reading position P1 are the same.

FIG. 7D shows a data flow of processing relating to the key “1110” stored at the reading position P4 of the key table 309. As indicated by dotted lines 680d and 684d, the difference bit position 0 is calculated by bit string comparison with the minimum value key “0001” stored at the read position P0. Then, the comparison with the key “1010” having the parent link P3 set to the difference bit position 0 in the difference bit position table 310 as the reading position is performed in step S507 shown in FIG. 5B. Since the key of the reading position P4 is larger, the reading position P3 of the difference bit position 0 in the difference bit position table 310 is not updated as indicated by the dotted arrow 660a. However, as indicated by the dotted arrow 673b, the entry at the reading position P3 in the link table 311 is updated to P4. Then, as indicated by an arrow 674c, P1 is set at the reading position P4 of the link table 311. By this setting, as indicated by arrows 674c and 671c, a link relationship is maintained in which the difference bit positions of the key at the reading position P3, the key at the reading position P4, and the key at the reading position P1 are the same.
The difference bit position table 310 and the link table 311 are set by the first-stage classification process according to the above data flow (the reading position P2 is omitted).

Although the best mode for carrying out the present invention has been described in detail above, it is obvious to those skilled in the art that the embodiment of the present invention is not limited thereto and can be variously modified.
In addition, it is obvious that the bit string data sorting apparatus of the present invention can be constructed on a computer by a storage unit having the data structure illustrated in FIG. 2A and a program that causes the computer to execute the processes illustrated in FIGS. 4A and 4B.
Therefore, the program and a computer-readable recording medium recording the program are included in the embodiment of the present invention.
By using the new bit string data sorting method provided by the present invention described in detail above, it is possible to sort bit string data at higher speed.

It is a figure explaining the concept of the conventional radix sort. It is a figure explaining the concept of the sort process by the difference bit position in one embodiment of this invention. It is a figure explaining the data structure used by the sort process by the difference bit position in one embodiment of this invention. It is a figure explaining the functional block structure of the bit string data sorting apparatus in one embodiment of this invention. It is a figure explaining the hardware structural example for implementing this invention. It is a figure explaining the processing flow of the classification | category process of the first step of the sort process in one embodiment of this invention, and the output process of the sorted key. It is a figure explaining the processing flow of the classification | category process after the first stage of the sort process in one embodiment of this invention, and the output process of the sorted key. It is a figure explaining the process flow of the front | former stage of the process which classifies the key in one embodiment of this invention. It is a figure explaining the process flow of the back | latter stage of the process which classifies the key in one embodiment of this invention. It is a figure explaining the processing flow of the process which further classify | categorizes the some key which has the same difference bit position in one embodiment of this invention. It is a figure explaining the data flow of the process of the first step which takes out the key in ascending order in one embodiment of this invention. It is a figure explaining the data flow of the process of the middle stage which takes out the key in ascending order in one embodiment of this invention. It is a figure explaining the data flow of the final stage process which takes out the key in ascending order in one embodiment of this invention. It is a figure explaining the flow of data of the classification process of the first rank.

Explanation of symbols

100 Key sequence 130 Sorted key sequence 149a, 149b, 149c Classification by difference bit position 200 Bit string data sort device 210 Difference bit position calculation means 220 Difference bit position classification means 230 Sorted key output means 240 Control means 301 Data processing apparatus 302 Central Processing device 303 Cache memory 304 Bus 305 Main storage device 306 External storage device 307 Communication device 308 Data storage device 309 Key table 310 Difference bit position table 311 Link table 313 Sorted key table

Claims (10)

In the bit string data sort device that performs the sort process of the key to be sorted represented by the bit string,
Sort target key storage means for storing the sort target key;
The bit that is initially different by the bit string comparison between the key that is the classification target of the classification process that constitutes the sort process stored in the sort target key storage unit and the key that is the reference among the keys that are the classification target A difference bit position calculation means for obtaining a difference bit position as a value;
Classification target key difference bit position storage means for storing identification information of a key having the difference bit position for each difference bit position obtained by the difference bit position calculation means;
For each difference bit position obtained by the difference bit position calculation means, the identification information of the key having the difference bit position is written in the classification target key difference bit position storage means, so that the key to be classified is the same difference. Differential bit position classification means for classifying into sets having bit positions;
When there is one key having the same differential bit position classified by the differential bit position classification means, that key is used, and when there are a plurality of keys having the same differential bit position, it becomes a reference in the next classification process. Sorted key output means for outputting keys as sorted keys,
And control means for controlling the difference bit position calculating means, before Symbol differencing bit position classifying means and the sorted key output means,
With
The control means includes
The difference bit position calculation means sets the classification target in the first processing of the difference bit position calculation means as a whole sort target key, and thereafter has the same difference bit position classified by the difference bit position classification means. Repeatedly determining the difference bit position as a classification target of a set of keys including a plurality of
The difference bit position classification means repeats classifying into a set having the same difference bit position for each difference bit position obtained by the difference bit position calculation means,
Each time the sorted bit output means classifies the difference bit position classifying means into a set having the same difference bit position for each difference bit position, the key in the case where there is one key having the same difference bit position and to output the key serving as the reference as a sorted key,
Controlling the difference bit position calculation means, the difference bit position classification means and the sorted key output means ,
A bit string data sorting apparatus characterized in that a key serving as a reference among the keys to be classified is a minimum value key having a minimum value or a maximum value key having a maximum value among keys to be classified . The bit string data sorting device according to claim 1 ,
The information for identifying the key is a reading position that is an address of the key in the sort target key storage unit in which the key is stored,
The classification target key difference bit position storage means stores the minimum for each difference bit position between the key to be classified and the minimum value key or the maximum value key that is a reference key among the classification target keys. Among the keys having the same difference bit position with respect to the value key or the maximum value key, a difference bit position table storing the parent link which is the reading position of the minimum or maximum key, and the key of the reading position for each reading position And a bit table data sorting device comprising a link table for storing a link which is a reading position of a key having the same differential bit position. In the bit string data sorting device according to claim 2 ,
A link having the key table read position of the key having the same differential bit position as the link table read position is set as the link table read position, and the link set in the read position is followed. The read position of the last key among the keys having the same differential bit position is set to refer to the read positions of the sort target key storage means for all the keys having the same differential bit position. The bit string data sorting device is characterized in that the read position of the last key is stored in the link. In the bit string data sorting device according to claim 3,
The control means has the same difference bit as the key in which the difference bit position classification means uses the parent link stored in the difference bit position as a reading position in descending or ascending order of the difference bit position in the difference bit position table. A bit string data sorting device, characterized in that control is performed so as to repeatedly classify sets having positions. In the bit string data sorting method for sorting the sort target key represented by the bit string,
A sort target key storage step of storing the sort target key in a sort target key storage means for storing the sort target key;
The bit that is initially different by the bit string comparison between the key that is the classification target of the classification process that constitutes the sort process stored in the sort target key storage unit and the key that is the reference among the keys that are the classification target A difference bit position calculation step for obtaining a difference bit position as a value;
For each difference bit position obtained in the difference bit position calculation step, the identification target key difference bit position storage means writes the identification information of the key having the difference bit position to make the key to be classified the same difference bit. A differential bit position classification step for classifying into sets having positions;
If there is a single key having the same differential bit position classified in the differential bit position classification step, that key is used, and if there are a plurality of keys having the same differential bit position, it becomes a reference in the next classification process. A sorted key output step for outputting the key as a sorted key;
And a control step of controlling the difference bit position calculation step, before Symbol differencing bit position classification step and the sorted key output step,
With
The control step includes
A set of keys including a plurality of keys having the same difference bit position classified in the difference bit position classification step after the difference bit position calculation step is executed with the classification target in the first process as a whole sort target key Repeating the difference bit position calculation step for the classification target,
Repeating the difference bit position classification step for classifying into a set having the same difference bit position for each difference bit position obtained in the difference bit position calculation step;
Each time the difference bit position classification step classifies into a group having the same difference bit position for each difference bit position, the sorted key output step is a key when there is one key having the same difference bit position. and to output the key serving as the reference as a sorted key, the difference bit position calculation step, which controls the said difference bit position classification step and the sorted key output step,
Among the keys to be classified, the reference key is a minimum value key that takes the minimum value or a maximum value key that takes the maximum value among the keys to be classified,
A bit string data sorting method characterized by the above. The bit string data sorting method according to claim 5,
The information for identifying the key is a reading position that is an address of the key in the sort target key storage unit in which the key is stored,
The classification target key difference bit position storage means stores the minimum for each difference bit position between the key to be classified and the minimum value key or the maximum value key that is a reference key among the classification target keys. Among the keys having the same difference bit position with respect to the value key or the maximum value key, a difference bit position table storing the parent link which is the reading position of the minimum or maximum key, and the key of the reading position for each reading position And a bit table data sorting method comprising a link table for storing a link which is a reading position of a key having the same differential bit position. The bit string data sorting method according to claim 6,
A link having the key table read position of the key having the same differential bit position as the link table read position is set as the link table read position, and the link set in the read position is followed. The read position of the last key among the keys having the same differential bit position is set to refer to the read positions of the sort target key storage means for all the keys having the same differential bit position. The bit string data sorting method is characterized in that the read position of the last key is stored in the link. The bit string data sorting method according to claim 7,
In the control step, the difference bit position classification step is the same difference bit as a key that uses the parent link stored in the difference bit position as a reading position in descending or ascending order of the difference bit position in the difference bit position table. A bit string data sorting method characterized by controlling so as to repeatedly classify a set having a position.   A program for causing a computer to execute the bit string data sorting method according to any one of claims 5 to 8. A computer-readable storage medium storing a program for causing a computer to execute the bit string data sorting method according to any one of claims 5 to 8.

Images