Character string retrieval system using index and unit for making the index

• US 5,357,431 A
• Filed: 01/25/1993
• Issued: 10/18/1994
• Est. Priority Date: 01/27/1992
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Miyabe, Kyouko, Tsubokura, Takashi, Suzuki, Hiroshi, Nakahara, Masaru, Nakada, Masahiro, Itami, Satoshi, Utsumi, Kenichi, Komura, Satoshi
• Primary Examiner(s): McElheny, Jr., Donald E.
• Application Number:
  US08/008,810
• Time in Patent Office: 631 Days
• Field of Search: 364/419.13, 364/419.12, 364/419.11, 364/419.14, 395/145, 395/148
• US Class Current: 715/201
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A character string retrieval system retrieves a character string corresponding to a retrieval key input thereto from a text file including a plurality of characters. The system includes an index indicating position data identifying a position of each of characters in the text file and indicating next character data identifying either a character or a character string formed of a plurality of characters arranged next to each of the characters in the text file, a selecting unit for selecting a first character from characters forming the character string corresponding to the retrieval key, a determining unit for determining, with reference to said index, whether or not a character or a character string next to the first character, selected by said selecting unit, in the retrieval key is equal to a character or a character string identified by the character data corresponding to the first character; and output unit for outputting a retrieval result when said determining unit determines that a character or a character string next to the first character in the retrieval key is equal to a character or a character string identified by the character data corresponding to the first character, the retrieval result being obtained based on the position data corresponding to the first character in said index.

Claims

1. A character string retrieval system for retrieving a character string corresponding to a retrieval key input thereto from a text file including a plurality of characters, said system comprising:

an index indicating position data identifying a position of each of characters in the text file and indicating next character data identifying either a character or a character string formed of a plurality of characters arranged next to each of the characters in the text file;

selecting means for selecting a first character from characters forming the character string corresponding to the retrieval key;

determining means for determining, with reference to said index, whether or not a character or a character string next to the first character, selected by said selecting means, in the retrieval key is equal to a character or a character string identified by the character data corresponding to the first character; and

output means for outputting a retrieval result when said determining means determines that a character or a character string next to the first character in the retrieval key is equal to a character or a character string identified by the character data corresponding to the first character, the retrieval result being obtained based on the position data corresponding to the first character in said index.

2. A system as claimed in claim 1, wherein the first character selected by said selecting means is a character positioned at a head of the retrieval key.

3. A system as claimed in claim 1, wherein said selecting means has a frequency table provided with frequency data for each of the characters in the text file, the frequency data indicating a frequency with which each of the characters appears in the text file, said selecting means selecting, with reference to the frequency table, a character corresponding to a minimum frequency data as the first character.

4. A system as claimed in claim 3, wherein the frequency data is arranged in a predetermined order in said frequency table, and position data and the next character data in said index are respectively arranged in an order corresponding to the order for the frequency data.

5. A system as claimed in claim 4, wherein the frequency data is arranged in an increasing order from a minimum value.

6. A system as claimed in claim 3, wherein said frequency table is provided with information for coupling the frequency data for each of the characters to the position data and the next character data in said index, and wherein said determining means searches in said index the position data and the next character data for the first character using said information provided in said frequency table.

7. A system as claimed in claim 1, wherein one or a plurality of items of the position data corresponding to each character and number data are listed, in said index, under each item of the next character data corresponding to each character, the number data indicating a number of items of the position data corresponding to each character.

8. A system as claimed in claim 7, wherein said index includes a table listing characters included in the text file, each of the characters listed in said table being coupled to corresponding next character data.

9. A system as claimed in claim 8, said table is provided with frequency data for each of the characters listed in said table, the frequency data indicating a frequency with which each of the characters appears in the text file, said selecting means selecting, with reference to the frequency data in said table, a character corresponding to a minimum frequency data as the first character.

10. A system as claimed in claim 7, wherein said selecting means selects as the first character, with reference to said index, a character corresponding to an item of the next character data under which a smallest number of items of the position data is listed.

11. A character string retrieval system for retrieving a character string corresponding to a retrieval key input thereto from a text file including a plurality of characters, said system comprising:

an index indicating position data identifying a position of each of characters in the text file and indicating next character data identifying either a character or a character string formed of a plurality of characters arranged next to each of the characters in the text file;

selecting means for selecting a first character from characters forming the character string corresponding to the retrieval key;

first determining means for determining, with reference to said index, whether or not a character or a character string next to the first character, selected by said selecting means, in the retrieval key is equal to a character or a character string identified by the next character data corresponding to the first character;

second determining means for determining whether or not a character string formed of the characters in the retrieval key is in a predetermined region in the text file, said region including a position identified by the position data for the first character; and

output means for outputting a retrieval result when said second determining means determines that the character string is in the region in the text file, the retrieval result being obtained based on the position data corresponding to the first character in said index.

12. A system as claimed in claim 11, wherein the first character selected by said selecting means is a character positioned at a head of the retrieval key.

13. A system as claimed in claim 11, wherein said selecting means has a frequency table indicating frequency data for each of the characters in the text file, the frequency data indicating a frequency with which each of the characters appears in the text file, said selecting means selecting, with reference to the frequency table, the first character which is a character corresponding to a minimum frequency data.

14. A system as claimed in claim 13, wherein the frequency data is arranged in a predetermined order in said frequency table, and position data and the next character data in said index are respectively arranged in an order corresponding to the order for the frequency data.

15. A system as claimed in claim 14, wherein the frequency data is arranged in an increasing order from a minimum value.

16. A system as claimed in claim 13, wherein said frequency table is provided with information for coupling the frequency data for each of the characters to the position data and the next character data in said index, and wherein said determining means searches in said index the position data and the next character data for the first character using said information provided in said frequency table.

17. A system as claimed in claim 11, wherein one or a plurality of items of the position data corresponding to each character and number data are listed, in said index, under each item of the next character data corresponding to each character, the number data indicating a number of items of the position data corresponding to each character.

18. A system as claimed in claim 17, wherein said index includes a table listing characters included in the text file, each of the characters listed in said table being coupled to corresponding next character data.

19. A system as claimed in claim 18, said table is provided with frequency data for each of the characters listed in said table, the frequency data indicating a frequency with which each of the characters appears in the text file, said selecting means selecting, with reference to the frequency data in said table, the first character which is a character corresponding to a minimum frequency data.

20. A system as claimed in claim 17, wherein said selecting means selects, with reference to said index, the first character which is a character corresponding to an item of the next character data under which a smallest number of items of the position data are listed.

21. A unit for making an index used in a character string retrieval system for retrieving a character string corresponding to a retrieval key input thereto from a text file including a plurality of characters, said index indicating position data identifying a position of each of characters in the text file and indicating next character data identifying either a character or a character string formed of a plurality of characters arranged next to each of the characters in the text file, said unit comprising:

searching means for successively searching characters in the text file one by one;

detecting means for detecting a predetermined number of characters arranged, in the text, next to a character searched by said searching means;

listing means for listing the position data identifying a position at which the character searched by said searching means is positioned in the text file and listing the next character data identifying one or a plurality of characters detected by said detecting means, so that the index indicating the position data and the next character data is made.

22. A unit as claimed in claim 21, wherein said detecting means detects one character arranged, in the text file, next to the character searched by said searching means.

23. A unit as claimed in claim 21, wherein said detecting means detects a plurality of characters arranged, in the text file, next to the character searched by said searching means.

24. A unit as claimed in claim 21, wherein said detecting means has number setting means for setting a number of characters to be detected by said detecting means.

25. A unit as claimed in claim 21, wherein said searching means has region setting means for setting a region in the text file, said searching means searching characters in said region.

26. A unit as claimed in claim 25, wherein said region setting means has means for setting an initial position of the region and an end position of the region.

27. A unit as claimed in claim 21, further comprising:

determining means for determining whether or not the position data and the next character data corresponding to a character searched by said searched means are needed in the index, wherein the position data and next character data are listed by said listing means when the determining means determines that the position data and the next character data are needed in the index.

28. A unit for making an index used in a character string retrieval system for retrieving a character string corresponding to a retrieval key input thereto from a text file including a plurality of characters, said index indicating frequency data for each of the characters in the text file, the frequency data indicating a frequency with which each of the characters appears in the text file, said unit comprising:

searching means for successively searching characters in the text file one by one;

counting means for counting a number of appearances of a character in the text file, said character being searched by said searching means; and

listing means for listing the frequency data corresponding to a count value obtained by said counting means, so that the index indicating the frequency data is made.

29. A unit as claimed in claim 28, wherein said searching means has region setting means for setting a region in the text file, said searching means searching characters in said region.

30. A unit as claimed in claim 29, wherein said region setting means has means for setting an initial position of the region and an end position of the region.

31. A unit as claimed in claim 28, further comprising:

determining means for determining whether or not the frequency data corresponding to a character searched by said searching means is needed in the index, wherein the frequency data is listed by said listing means when the determining means determines that the frequency data is needed in the index.