Data sort method, data sort apparatus, and data sort program

• US 7,103,596 B2
• Filed: 03/04/2002
• Issued: 09/05/2006
• Est. Priority Date: 07/27/2001
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nagata, Masahiko, Matsuura, Masataka, Tabata, Yoko, Hara, Yasuhisa, Abe, Fumirou
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US10/086,696
• Publication Number:
  US 20030033278A1
• Time in Patent Office: 1,646 Days
• Field of Search: 707 1- 7, 707/10, 707100-102, 707/104.1, 707200-205, 700/90, 700/213, 700/219, 700/223, 700/245, 382/229, 382/232
• US Class Current: 1/1
• 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
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A data sort method, apparatus, and program to receive a character string of sort key items specified as keys of a data sort process, generate an automaton corresponding to a record whose final transition state corresponds to the character string, determine the order specified by the character string by scanning the automaton, and determine the order of the records corresponding to the character string.

Claims

1. A data sort method of rearranging records according to a specified sort key item in an ascending/descending order, comprising:

an automaton generating step of generating, in a main memory, an automaton which receives a character string of a sort key item of each record read successively from outside, and which is a set of state transition tables with a hierarchical tree structure whose hierarchical depth is equal to a maximum number of characters of a character string of a sort key item of each record, and whose transition table corresponds to each character of a character string of the sort key item of each record, and also whose state transition table contains links to next stage state transition tables each of which corresponds to a next character of a character string of the sort key item of each record in an ascending/descending order according to each of the next characters, and which associates a record identifier of each record with a final state transition table corresponding to the final character of a character string of the sort key item of the record; and

an order value tuple generating step of generating an order value tuple which is a set of a record identifier of the record and an order value which is obtained by arranging the records in an ascending/descending order by scanning the automaton in order of contained links in the state transition tables giving priority to the depth direction of the hierarchy of the state transition tables.

2. The data sort method according to claim 1, wherein

there are a plurality of sort key items, and said order value tuple is a set of a plurality of order values and a record identifier.

3. The data sort method according to claim 2, further comprising:

a sort table generating step of generating a sort table on which the order value tuples are arranged in a predetermined order.

4. The data sort method according to claim 1, further comprising:

a sort table generating step of generating a sort table on which the order value tuples are arranged in a predetermined order.

5. The data sort method according to claim 4, wherein

in said sort table generating step, a sort order sort table on which order values are arranged in an ascending or descending order is generated.

6. The data sort method according to claim 4, wherein

in said sort table generating step, a record order sort table on which record identifiers are arranged in an ascending or descending order is generated.

7. The data sort method according to claim 6, wherein

there are a plurality of sort key items, and a record order sort table is generated based on a plurality of order value tuples which is a set of a plurality of order values and a record identifier, and further comprising:

an automaton generating step of generating an automaton for assuming that a row of a plurality of order values of the record order sort table is a character string belonging to the record identifier, and receiving the character string as a plural order value key character string for all tuples on the record order sort table; and

a general order value tuple generating step of scanning the automaton, and generating a general order value tuple which is a set of the record identifier and a newly ordered general order value as a general order for the plurality of sort keys.

8. The data sort method according to claim 1, further comprising:

a record identifier setting step of recording a tuple for association between a starting address of a record and a record identifier for identification of the record for each record read from input data.

9. The data sort method according to claim 1, further comprising:

a key data preprocessing step of converting input sort key item data into a key character string appropriate for said automaton generating step according to a key condition relating to a sort method for each specified sort key item.

10. A data sort apparatus which rearranges records according to a specified sort key item in an ascending/descending order, comprising:

an automaton generating unit generating, in a main memory, an automaton which receives a character string of a sort key item of each record read successively from outside, and which is a set of state transition tables with a hierarchical tree structure whose hierarchical depth is equal to a maximum number of characters of a character string of a sort key item of each record, and whose transition table corresponds to each character of a character string of the sort key item of each record, and also whose state transition table contains links to next stage state transition tables each of which corresponds to a next character of a character string of the sort key item of each record in an ascending/descending order according to each of the next characters, and which associates a record identifier of each record with a final state transition table corresponding to the final character of a character string of the sort key item of the record; and

an order value tuple generating unit generating an order value tuple which is a set of a record identifier of the record and an order value which is obtained by arranging the records in an ascending/descending order by scanning the automaton in order of contained links in the state transition tables giving priority to the depth direction of the hierarchy of the state transition tables.

11. A data sort program for directing a computer to perform a data sorting process of rearranging records according to a specified sort key item in an ascending/descending order, comprising:

an automaton generating step of generating, in a main memory, an automaton which receives a character string of a sort key item of each record read successively from outside, and which is a set of state transition tables with a hierarchical tree structure whose hierarchical depth is equal to a maximum number of characters of a character string of a sort key item of each record, and whose transition table corresponds to each character of a character string of the sort key item of each record, and also whose state transition table contains links to next stage state transition tables each of which corresponds to a next character of a character string of the sort key item of each record in an ascending/descending order according to each of the next characters, and which associates, a record identifier of each record with a final state transition table corresponding to the final character of a character string of the sort key item of the record; and

an order value tuple generating step of generating an order value tuple which is a set of a record identifier of the record and an order value which is obtained by arranging the records in an ascending/descending order by scanning the automaton in order of contained links in the state transition tables giving priority to the depth direction of the hierarchy of the state transition tables.

12. A computer-readable storage medium storing the program according to claim 11.

13. A data sort apparatus which rearranges records according to a specified sort key item in an ascending/descending order, comprising:

automaton generating means for generating, in a main memory, an automaton which receives a character string of a sort key item of each record read successively from outside, and which is a set of state transition tables with a hierarchical tree structure whose hierarchical depth is equal to a maximum number of characters of a character string of the sort key item of each record, and whose transition table corresponds to each character of a character string of the sort key item of each record, and also whose state transition table contains links to next stage state transition tables each of which corresponds to a next character of a character string of the sort key item of each record in an ascending/descending order according to each of the next characters, and which associates a record identifier of each record with a final state transition table corresponding to the final character of a character string of a sort key item of the record; and

order value tuple generating means for generating an order value tuple which is a set of a record identifier of the record and an order value which is obtained by arranging the records in an ascending/descending order by scanning the automaton in order of contained links in the state transition tables giving priority to the depth direction of the hierarchy of the state transition tables.