Data compression method, data retrieval method, data retrieval apparatus, recording medium, and data packet signal

• US 20010022792A1
• Filed: 01/22/2001
• Published: 09/20/2001
• Est. Priority Date: 01/25/2000
• Status: Abandoned Application

• Current Assignee: KEIO University, Sony Corporation (Sony Group Corp.)
• Original Assignee: KEIO University, Sony Corporation (Sony Group Corp.)
• Inventors: Maeno, Tamaki, Asano, Akira
• Application Number:
  US09/766,919
• Publication Number:
  US 20010022792A1
• Time in Patent Office: Days
• US Class Current: 370/521
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

A method of generating a data packet having main data and compressed search data for efficiently retrieving the main data, a retrieval method and a retrieval apparatus for efficiently retrieving the main data by a search key given by plural data packets, a recording medium in which these plural data packets are recorded, and a data packet signal having main data and compressed search data for efficiently retrieving the main data.

Claims

1. A data compression method for efficiently retrieving key data for retrieving main data and compressing a data amount of said key data to be recorded on a recording medium, comprising the steps of:

comparing first key data composed of a first number of characters with second key data composed of a second number of characters which is greater than said first number of characters of said first key data;

on the basis of a result of the comparison between said first key data and said second key data, detecting the number of matching characters between said first key data and said second key data, deleting a character matching said first key data from said second key data, and generating a data packet having said number of matching characters and a mismatching character obtained by deleting said character matching said first key data from said second key data; and

recording said data packet to said recording medium.

2. The data compression method according to

claim 1

, wherein said first key data and said second key data are located in the neighborhood of each other in a predetermined arrangement rule.

3. The data compression method according to

claim 1

, wherein said recording medium has a plurality of storage area each having a predetermined storage size, said method further comprising the steps of:

selecting one piece of key data from at least one of said data packets to be recorded on each of said plurality of recording areas on said recording medium; and

recording said key data selected for each of said plurality of recording areas on said recording medium by relating said key data to each of said plurality of recording areas.

4. A data retrieval method for retrieving main data in a data packet configured by said main data and compressed key data configured by the number of duplicate characters between key data associated with said main data and neighborhood key data and a mismatching character obtained by deleting a duplicate character from said key data, on the basis of an inputted search key and said compressed key data, comprising the steps of:

retrieving said data packet in which said key data are equal to said mismatching character;

detecting a mismatching portion between a mismatch character of said compressed key data in said data packet retrieved in the retrieving step and said search key; and

if said mismatching portion is detected between said mismatch character of said compressed key data and said search key, detecting a mismatching portion between a mismatch character of said compressed key data of a data packet adjacent to said data packet and said detected mismatching portion.

5. The data retrieval method according to

claim 4

, wherein said recording medium having a plurality of storage areas each having a predetermined storage size and a plurality of storage area search keys for searching said plurality of storage areas, the step of retrieving said data packet in which said key data are equal to said mismatching character further comprising the step of:

searching forehand the storage area in the neighborhood of the storage area in which the retrieved data packet is stored, on the basis of said search key and said storage area search key.

6. The data retrieval method according to

claim 4

, wherein the data packets recorded on said recording medium are arranged in accordance with a predetermined arrangement rule.

7. A data retrieval apparatus for retrieving main data from a recording medium recording a data packet configured by said main data and compressed key data configured by the number of duplicate characters between key data associated with said main data and neighborhood key data and a mismatching character obtained by deleting a duplicate character from said key data, on the basis of an inputted search key and said compressed key data, said data retrieval apparatus comprising:

recording medium access means for reading said data packet from said recording medium;

retrieval means for retrieving said data packet in which said key data are equal to said mismatching character;

mismatch detecting means for detecting a mismatching character portion between a mismatching character in said compressed key data in a predetermined data packet and an inputted character string for comparison; and

control means for controlling said retrieval means so that said data packet in which said key data are equal to said mismatching character is retrieved, detecting a mismatching portion between the retrieved data packet and said inputted search key by controlling said mismatch detecting means, and, if said mismatching portion is found, detecting, by controlling said mismatch detecting means, a mismatching portion between the detected mismatching portion and a data packet adjacent to the data packet retrieved by said retrieval means read by controlling said recording medium access means.

8. The data retrieval apparatus according to

claim 7

, further comprising display means for displaying main data contained in said data packet retrieved by said search key under the control of said control means.

9. The data retrieval apparatus according to

claim 7

, further comprising input means for inputting said search key, said controls means retrieves said data packet on the basis of said search key inputted from said input means.

10. The data retrieval apparatus according to

claim 7

, wherein said data packet further having sub data associated with said main data, said data retrieval apparatus displaying said sub data on said display means before displaying said retrieved main data.

11. The data retrieval apparatus according to

claim 7

, wherein said recording medium has a plurality of packet recording areas each having a predetermined recording size for recording at least one of said data packets and an identification data recording area recording identification data for identifying at least one of said data packets recorded in said plurality of packet recording areas, said identification data being recorded in relation to each of said plurality of packet recording areas,

said data retrieval apparatus further comprising identification data access means for reading said identification data from said identification data recording area, and

said control means controlling said identification data access means on the basis of said inputted search key to start a retrieval from the packet recording area in the neighborhood of the packet recording area in which the data packet to be retrieved is recorded.

12. A data retrieval apparatus for retrieving main data from a recording medium recording a data packet configured by said main data and compressed key data configured by the number of duplicate characters between key data associated with said main data and neighborhood key data and a mismatching character obtained by deleting a duplicate character from said key data, on the basis of an inputted search key and said compressed key data, said data retrieval apparatus comprising:

recording medium access means for reading said data packet from said recording medium;

operator means for inputting said search key;

display means for displaying said retrieved main data;

compressed key data retrieving means for retrieving said compressed key data from said data packet read from said recording medium;

first comparing means for comparing a mismatching character of said compressed key data with said search key;

holding means for holding, on the basis of a result of the comparison made by said comparing means, the number of mismatching characters between the mismatching character of said compressed key data with said search key;

second comparing means for comparing the number of characters held in said holding means with data indicative of the number of compressed characters; and

control means for controlling said first comparing means so as to compare said search key inputted from said operator means with the number of mismatching characters of the compressed key data retrieved by said compressed key data retrieving means, holding in said holding means the number of matching characters between said search key obtained by comparison by said first comparing means and said compressed key data, comparing said mismatching character of an adjacent data packet with a character string of said search key to be found mismatching by said comparing means, and displaying said main data thus retrieved onto said display means.

13. A data packet signal having main data and a retrieval character string for retrieving said main data, comprising:

a main data signal portion;

a mismatching signal portion remaining after compression of a matching character portion between key data for retrieving said main data and key data for another piece of main data; and

a compressed character count signal portion indicative of the number of characters of the compressed data.

14. The data packet signal according to

claim 13

, further comprising a header word portion indicative of a content of said main data.

15. The data packet signal according to

claim 13

, wherein said mismatching signal portion is omitted by the compression when said key data for retrieving said main data are equal to said key data of said another main data.

16. The data packet signal according to

claim 13

, further comprising:

a header signal indicative of the start of said data packet signal;

a header word end signal indicative of the end of said header word signal; and

a main data start signal indicative of the start of said main data.

17. A recording medium recording a data packet having main data and compressed data for retrieving said main data, said data packet comprising:

said main data;

mismatching data remaining after deleting a matching character between retrieval data for retrieving said main data and retrieval data for retrieving main data of a neighboring data packet; and

the number of compressed characters indicative of the number of characters deleted as a result of the matching.

18. The recording medium according to

claim 17

, wherein the neighboring retrieval data for compression are data packet located before said data packet arranged in accordance with a predetermined arrangement rule.

19. The recording medium according to

claim 17

, wherein said data packet further having a header word for identifying said main data.

20. The recording medium according to

claim 17

, further having a block key data recording area for recording block key data for retrieving a block in which one or more of said data packets are put together.