Source: http://www.patentsencyclopedia.com/app/20130086086
Timestamp: 2017-10-21 21:51:49
Document Index: 536017073

Matched Legal Cases: ['art 1', 'art 2', 'art 1', 'art 2', 'art 3', 'art 3', 'art 4', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 6', 'art 7', 'art 1', 'art 2', 'art 1', 'art 2', 'art 1', 'art 2', 'art 3', 'art 4', 'art 1', 'art 2', 'art 3', 'art 4', 'art 5', 'art 6', 'art 7', 'art 1', 'art 2']

INFORMATION GENERATING COMPUTER PRODUCT, APPARATUS, AND METHOD; AND INFORMATION SEARCH COMPUTER PRODUCT, APPARATUS, AND METHOD - Patent application
Patent application title: INFORMATION GENERATING COMPUTER PRODUCT, APPARATUS, AND METHOD; AND INFORMATION SEARCH COMPUTER PRODUCT, APPARATUS, AND METHOD
Inventors: Masahiro Kataoka (Tama, JP) Masahiro Kataoka (Tama, JP) Fujitsu Limited (Kawasaki-Shi, JP)
Patent application number: 20130086086
A computer-readable recording medium stores a program causing a computer to execute an information generating process that includes tabulating an appearance frequency for each designated word in an object file group in which character strings are described; identifying for each designated word and based on the appearance frequency tabulated for the designated word, a rank in descending order up to a target appearance rate for the designated words; detecting in an object file selected from the object file group, specific designated words among the identified ranks; and generating for each of the detected specific designated words, index information that indicates the presence/absence of the specific designated word in each object file among the object file group.
1. A computer-readable recording medium stores a program causing a computer to execute an information generating process comprising: tabulating an appearance frequency for each designated word in an object file group in which character strings are described; identifying for each designated word and based on the appearance frequency tabulated for the designated word, a rank in descending order up to a target appearance rate for the designated words; detecting in an object file selected from the object file group, specific designated words among the identified ranks; and generating for each of the detected specific designated words, index information that indicates the presence/absence of the specific designated word in each object file among the object file group.
2. The computer-readable recording medium according to claim 1, wherein the detecting includes detecting the specific designated words by a longest match search using an object character in the object file, as a starting character.
3. A computer-readable recording medium stores a program causing a computer to execute an information generating process comprising: tabulating an appearance frequency for each single character in an object file group in which character strings are described; identifying based on each appearance frequency tabulated for each single character, a rank in descending order up to a target appearance rate; detecting in an object file selected from the object file group, specific single characters among the identified ranks; and generating for each of the detected specific single characters, index information that indicates the presence/absence of the specific single characters in each object file among the object file group.
4. The computer-readable recording medium according to claim 1, wherein the tabulating includes tabulating an appearance frequency for each single character in the object file group, the identifying includes identifying based on each appearance frequency tabulated for each single character, a rank in descending order up to a target appearance rate for the single characters, the detecting includes detecting in the object file selected from the file group, specific single characters among the identified ranks, and the generating includes generating for each of the specific single character among the identified ranks, index information that indicates the presence/absence of the specific single character in each of object file among the object file group.
5. The computer-readable recording medium according to claim 4, causing the computer to execute dividing into an upper bit character code and a lower bit character code, a character code of a single character ranked lower than the identified ranks, wherein the generating includes generating for each upper bit character code, index information that indicates the presence/absence of the upper bit character code in each object file among the object file group and generating for each lower bit character code, index information that indicates the presence/absence of the lower character code in each the object file among the object file group.
6. The computer-readable recording medium according to claim 4, wherein the generating includes generating for each multi-character string that is a sequence of specific single characters among the identified ranks, index information that indicates the presence/absence of the multi-character string in each object file among the object file group.
7. The computer-readable recording medium according to claim 5, wherein the generating includes generating for each multi-character string that is a sequence of a specific single character among the identified ranks and the upper bit character code, index information that indicates the presence/absence of the multi-character string in each object file among the object file group.
8. The computer-readable recording medium according to claim 5, wherein the generating includes generating for each multi-character string that is a sequence of the lower bit character code and a specific single character among the identified ranks, index information that indicates the presence/absence of the multi-character string in each object file among the object file group.
9. The computer-readable recording medium according to claim 5, wherein the generating includes generating for each multi-character string that is a sequence of the upper bit character code and the lower bit character code, index information that indicates the presence/absence of the multi-character string in each object file among the object file group.
10. A computer-readable recording medium stores a program causing a computer to execute an information search process comprising: receiving input of a search character string; identifying an object file that includes the search character string, by referring to index information indicating for each object file among an object file group in which character strings are described, the presence/absence of specific designated words that are among designated words present in the object file group and among ranks in descending order up to a target appearance rate for the designated words; searching the identified object file for information related to the search character string; and outputting a search result.
11. A computer-readable recording medium stores a program causing a computer program to execute an information search process comprising: receiving input of a search character string; identifying an object file that includes each single character making up the search character string, by referring to index information that indicates for each object file among an object file group in which character strings are described, the presence/absence of designated single characters that are among single characters present in the object file group and among ranks in descending order up to a target appearance rate for the single characters; narrowing down identified object files to object files that include each single character making up the search character string; searching the object files that include each single character making up the search character string, for information related to the search character string; and outputting a search result.
12. The computer-readable recording medium according to claim 10, wherein the identifying includes, when no object file includes the specific designated words, identifying an object file that includes each single character making up the search character string, by referring to index information indicating for each object file among the object file group, the presence/absence of specific single characters that are among single characters present in the object file group and among ranks in descending order up to a target appearance rate for the single characters.
13. The computer-readable recording medium according to claim 12, causing the computer to execute dividing into an upper bit character code and a lower bit character code, a character code of a single character that does not correspond to the specific single characters among single characters making up the search character string, wherein the identifying includes identifying an object file that includes the upper bit character code, by referring to index information indicating for each object file among the object file group, the presence/absence of the upper bit character code and identifying an object file that includes the lower bit character code, by referring to index information indicating for each object file among the object file group, the presence/absence of the lower bit character code.
14. The computer-readable recording medium according to claim 12, wherein the identifying includes identifying for each multi-character string that is a sequence of single characters among single characters present in the object file group and within a rank in descending order corresponding to a target appearance rate for the single characters, an object file that includes each multi-character string making up the search character string, by referring to index information indicating for each object file among the object file group, the presence/absence of the multi-character strings, and the narrowing down includes narrowing down identified object files to object files having each single character and multi-character string making up the search character string.
15. The computer-readable recording medium according to claim 13, wherein the identifying includes: identifying for each multi-character string that is a sequence of a specific single character and the upper bit character code, an object file that includes the multi-character string that is a sequence of the designated single character and the upper bit character code making up the search character string, by referring to index information indicating the presence/absence of multi-character strings in each object file among the object file group, identifying for each multi-character string that is a sequence of the lower bit character code and a specific single character, an object file that includes the multi-character string that is a sequence of the lower bit character code and the designated single character making up the search character string, by referring to the index information indicating the presence/absence of multi-character strings in each object file among the object file group, and identifying for each multi-character string that is a sequence of the upper bit character code and the lower bit character code, an object file that includes the multi-character string that is a sequence of the upper bit character code and the lower bit character code making up the search character string, by referring to the index information indicating the presence/absence of multi-character strings in each object file among the object file group, and the narrowing down includes narrowing down identified object files to object files having each single character, upper bit character code, lower bit character code, and multi-character string making up the search character string.
16. An information generating apparatus comprising a processor configured to: tabulate an appearance frequency for each designated word in an object file group in which character strings are described; identify for each designated word and based on the appearance frequency tabulated for the designated word, a rank in descending order up to a target appearance rate for the designated words; detect in an object file selected from the object file group, specific designated words among the identified ranks; and generate for each of the detected specific designated words, index information that indicates the presence/absence of the specific designated word in each object file among the object file group.
17. An information search apparatus comprising a processor configured to: receive input of a search character string; identify an object file that includes the search character string, by referring to index information indicating for each object file among an object file group in which character strings are described, the presence/absence of specific designated words that are among designated words present in the object file group and among ranks in descending order up to a target appearance rate for the designated words; search the identified object file for information related to the search character string; and output a search result.
18. An information generating method executed by a computer, the information generating method comprising: tabulating an appearance frequency for each designated word in an object file group in which character strings are described; identifying for each designated word and based on the appearance frequency tabulated for the designated word, a rank in descending order up to a target appearance rate for the designated words; detecting in an object file selected from the object file group, specific designated words among the identified ranks; and generating for each of the detected specific designated words, index information that indicates the presence/absence of the specific designated word in each object file among the object file group.
19. An information search method executed by a computer, the information search method comprising: receiving input of a search character string; identifying an object file that includes the search character string, by referring to index information indicating for each object file among an object file group in which character strings are described, the presence/absence of specific designated words that are among designated words present in the object file group and among ranks in descending order up to a target appearance rate for the designated words; searching the identified object file for information related to the search character string; and outputting a search result.
[0001] This application is a continuation application of International Application PCT/JP2010/059150, filed on May 28, 2010 and designating the U.S., the entire contents of which are incorporated herein by reference.
[0002] The embodiments discussed herein are related to a computer product, an information generating apparatus, an information search apparatus, an information generating method, and an information search method for generating index information indicating the presence/absence of characters and basic words to perform a search by using the index information.
[0003] A bitmap type full-text search technique is conventionally known that rapidly generates a full-text search index such as a character component table (see, for example, Japanese Laid-Open Patent Publication Nos. H1-181329, H3-174652, and H5-174064). Since morphological analysis is not performed in the conventional bitmap type full-text search techniques, the index can be rapidly generated and bitmaps can be compressed. A typical Japanese-language dictionary includes about 240,000 entries and is described with about 6000 to 8000 characters and therefore, has about 6000 to 8000 bitmaps for single characters.
[0004] However, the conventional techniques described above have a problem in that bitmaps of single characters lead to lower efficiency in the narrowing down of object items because hiragana, katakana, and alphabetic characters included in items (records) appear at higher frequencies.
[0005] If bitmaps of two-character strings are added, the volume of data increases and considerable memory is consumed. Volume reduction by hashing generates search noise. Therefore, the efficiency of narrowing down bitmaps drops, resulting in slower search speeds.
[0006] On the other hand, character strings forming words in alphabetic, hiragana, and katakana characters etc., generate search noise due to connection of characters. For example, the sentence "that is a pen", which includes the English substantive verb "is" and indefinite article "a", cannot be searched. Particularly, since the alphabetic character "a" appears at a very high frequency, if a search is performed for the indefinite article "a", almost all the example sentences and words are searched as candidates.
[0007] In this regard, it is conceivable that a bitmap is generated for each basic word used as an entry word of a dictionary such as and . However, this causes a problem in that no hit is retrieved by searching for character strings other than basic words. For example, when a search is performed for a character string even if files including character strings , , and are present, the corresponding files cannot be identified since the search is not performed for or . As described above, so-called parting occurs between the end character of the basic word and the starting character of the basic character .
[0008] Although candidate files can be identified by searching for basic words ending with and basic words starting with to cover all the mutual combinations of bitmaps, and the bitmaps can be read to perform an AND operation, not much can be expected in terms of the narrowing down of candidate files because of search noise generated by the hashing of the bitmaps and the time required for a series of processes such as searching among keywords.
[0009] According to an aspect of an embodiment, a computer-readable recording medium stores a program causing a computer to execute an information generating process that includes tabulating an appearance frequency for each designated word in an object file group in which character strings are described; identifying for each designated word and based on the appearance frequency tabulated for the designated word, a rank in descending order up to a target appearance rate for the designated words; detecting in an object file selected from the object file group, specific designated words among the identified ranks; and generating for each of the detected specific designated words, index information that indicates the presence/absence of the specific designated word in each object file among the object file group.
[0012] FIG. 1 is an explanatory diagram of an example of information generation in an information generating apparatus (part 1);
[0013] FIG. 2 is an explanatory diagram of an example of division of a non-specific character;
[0014] FIG. 3 is an explanatory diagram of an example of information generation in the information generating apparatus (part 2);
[0015] FIG. 4 is a block diagram of a hardware configuration of the information generating apparatus according to the embodiments;
[0016] FIG. 5 is a block diagram of an example of a functional configuration of the information generating apparatus;
[0017] FIG. 6 is an explanatory diagram of a map generation example (part 1);
[0018] FIG. 7 is an explanatory diagram of a map generation example (part 2);
[0019] FIG. 8A is an explanatory diagram of a map generation example (part 3, first half);
[0020] FIG. 8B is an explanatory diagram of a map generation example (part 3, second half);
[0021] FIG. 9 is explanatory diagram of a map generation example (part 4);
[0022] FIG. 10 is a flowchart of an information generation process procedure of an information generating apparatus 500;
[0023] FIG. 11 is a flowchart of a detailed process procedure of a tabulation process (step S1001) depicted in FIG. 10;
[0024] FIG. 12 is a flowchart of a detailed process procedure of a tabulation process for an object file Fi (step S1103) depicted in FIG. 11;
[0025] FIG. 13 is a flowchart of a detailed process procedure of a basic word tabulation process (step S1202) depicted in FIG. 12;
[0026] FIG. 14 is a flowchart of a detailed process procedure of a longest match search process (step S1301) depicted in FIG. 13;
[0027] FIG. 15 is a flowchart of a detailed process procedure of a map assignment number determination process (step S1002) depicted in FIG. 10;
[0028] FIG. 16 is a flowchart of a detailed process procedure of a map generation process (step S1003) depicted in FIG. 10;
[0029] FIG. 17 is a flowchart of a detailed process procedure of a map generation process for the object file Fi (step S1603) depicted in FIG. 16;
[0030] FIG. 18 is a flowchart of a detailed process procedure of a specific basic word appearance map generation process (step S1702) depicted in FIG. 17;
[0031] FIG. 19 is a flowchart of a detailed process procedure of a specific single character appearance map generation process (step S1703) depicted in FIG. 17;
[0032] FIG. 20 is a flowchart of a detailed process procedure of a divided character code appearance map generation process (step S1903) depicted in FIG. 19;
[0033] FIG. 21 is a flowchart of a detailed process procedure of a multi-character string appearance map generation process (step S1704) depicted in FIG. 17;
[0034] FIG. 22 is a flowchart of a detailed process procedure of a multi-character string identification process (step S2101) depicted in FIG. 21;
[0035] FIG. 23 is a block diagram of an example of a functional configuration of the information search apparatus;
[0036] FIG. 24 is an explanatory diagram of an example (part 1) of an information search process;
[0037] FIG. 25 is an explanatory diagram of an example (part 2) of the information search process;
[0038] FIG. 26 is an explanatory diagram of an example (part 3) of the information search process;
[0039] FIG. 27 is an explanatory diagram of an example (part 4) of the information search process;
[0040] FIG. 28 is an explanatory diagram of an example (part 5) of the information search process;
[0041] FIG. 29 is an explanatory diagram of an example (part 6) of the information search process;
[0042] FIG. 30 is an explanatory diagram of an example (part 7) of the information search process;
[0043] FIG. 31 is a flowchart of an information search process procedure of an information search apparatus 2300;
[0044] FIG. 32A is a flowchart (part 1) of a detailed process procedure of a file identification process (step S3104) depicted in FIG. 31;
[0045] FIG. 32B is a flowchart (part 2) of a detailed process procedure of the file identification process (step S3104) depicted in FIG. 31;
[0046] FIG. 33 is a flowchart of a detailed process procedure of a longest match search process (step S3202) depicted in FIG. 32B;
[0047] FIG. 34 is a flowchart of a detailed process procedure of a file identification process using a multi-character string appearance map M5 (step S3216) depicted in FIG. 32B;
[0048] FIG. 35 is an explanatory diagram of map projection;
[0049] FIG. 36 is a flowchart of an information search process procedure when using appearance maps segmented into multiple pieces due to addition of object files; and
[0050] FIG. 37 is a flowchart of a portion of the file identification process (step S3104) in the information search process (step S3602) depicted in FIG. 36.
[0051] An information generating program, an information search program, an information generating apparatus, an information search apparatus, an information generating method, and an information search method according to the present invention will be described in detail with reference to the accompanying diagrams.
[0052] The information generating program, the information generating apparatus, and the information generating method will be described.
[0053] FIG. 1 is an explanatory diagram of an example of information generation in the information generating apparatus (part 1). In FIG. 1, an object file group F is a collection of object files. The object files are electronic data in which character strings are described. The object files are electronic data such as dictionaries, electronic books, and web pages, for example, and are described in text, HyperText Markup Language (HTML), and Extensible Markup Language (XML) formats.
[0054] The information generating apparatus executes four phases including (A) tabulation from the object file group F, (B) sorting in descending order of appearance frequency, (C) extraction until the rank of a target appearance rate, and (D) map generation. Basic words and single characters will be described separately hereinafter.
[0055] (A1) First, the information generating apparatus reads the object file group F and counts the appearance frequencies of basic words. A basic word means a preliminarily designated word in a word group. For example, in the case of a dictionary, entry words correspond to the basic words. The information generating apparatus refers to a basic word structure formed by collecting basic words and, if an object file includes a character string matching a basic word in the basic word structure, the information generating apparatus adds one to the appearance frequency of the basic word (default value is zero). The basic word structure is a data structure in which basic words are described.
[0056] (B1) Once the tabulation of basic words is completed for the object file group F, the information generating apparatus sorts a basic word appearance frequency table 101 in descending order of the appearance frequency and ranks the basic words in descending order from the highest appearance frequency.
[0057] (C1) The information generating apparatus refers to the basic word appearance frequency table 101 after the sorting at (B1) and extracts the basic words ranked up to a target appearance rate Pw. For example, the information generating apparatus calculates the appearance rate for each rank by using the sum of appearance frequencies (the total appearance frequency) of all the basic words as the denominator and takes the running total of the appearance frequencies in descending order from the basic word ranked in the first place as the numerator.
[0058] For example, assuming that the total appearance frequency is 50000 and that the cumulative appearance frequency of basic words from the first place to the x-th place is 45000, the appearance frequency until the x-th place is (45000/50000)×100=90 [%]. If the target appearance rate Pw is 90 [%], the basic words ranked in the top x are extracted. The basic words extracted at (C1) are referred to as "specific basic words (group)" so as to distinguish the words from original basic words.
[0059] (D1) Lastly, the information generating apparatus generates a specific basic word appearance map M1 for the specific basic word group. The specific basic word appearance map M1 is index information in bitmap format indicating the presence/absence of the specific basic words in each object file for each specific basic word. If a specific basic word appears at least once in each object file, the corresponding bit of the object file is turned on and if a specific basic word never appears, the corresponding bit of the object file is kept off.
[0060] In this description, if a "bit is turned on", a value of the bit turns to "1" and if a "bit is turned off", a value of the bit turns to "0". If a "bit is turned on", a value of the bit may turn to "0" and if a "bit is turned off", a value of the bit may turn to "1". Single characters will be described.
[0061] (A2) The information generating apparatus reads the object file group F and counts the appearance frequencies of single characters. A single character is a character represented by a character code of a predetermined bit length. For example, the single characters are characters of UCS/Unicode Transformation Format (UTF) 16-bit character codes. The information generating apparatus refers to a single character structure formed by collecting single characters and if an object file includes a single character matching a single character in the single character structure, the information generating apparatus adds one to the appearance frequency of the single character (default value is zero). The single character structure is a data structure in which single characters are described.
[0062] (B2) Once the tabulation of single characters is completed for the object file group F, the information generating apparatus sorts a single character appearance frequency table 102 in descending order of the appearance frequency. Therefore, the table is sorted in order from the highest appearance frequency and single characters are ranked in order from the highest appearance frequency.
[0063] (C21) The information generating apparatus refers to the single character appearance frequency table 102 after the sorting at (B2) to extract the single characters ranked up to a target appearance rate Pc. For example, the information generating apparatus calculates an appearance rate to each rank by using the sum of appearance frequencies (the total appearance frequency) of all the single characters as the denominator and a running total of the appearance frequencies in descending order from the single character ranked in the first place as the numerator.
[0064] For example, assuming that the total appearance frequency is 50000 and that the cumulative appearance frequency of single characters from the first place to the y-th place is 40000, the appearance frequency until the y-th place is (50000/40000)×100=80 [%]. If the target appearance rate Pc is 80 [%], the single characters ranked in the top y are extracted. The single characters extracted at (C21) are referred to as "specific single characters (group)" so as to distinguish the characters from original single characters.
[0065] (C22) Among single characters, single characters excluded from the specific single character group (hereinafter, "nonspecific single character (group)") have an appearance frequency lower than the specific single characters and therefore, the character code thereof is divided. For example, a character code of a nonspecific single character is divided into upper bits and lower bits.
[0066] For example, if the single character is represented by a UTF 16-bit character code, the character code is divided into an upper 8 bits and a lower 8 bits. In this case, the upper 8 bits and the lower 8 bits are each represented by a code from 0x00 to 0xFF. The upper bits of the character code are referred to as an "upper bit character code (group)" and the lower bits of character code are referred to as a "lower bit character code (group)".
[0067] (D2) The information generating apparatus generates a specific single character appearance map M2 for the specific single character group extracted at (C21). The specific single character appearance map M2 is index information that is in bitmap format and for each specific single character, indicates the presence/absence of the specific single characters in each object file. If a specific single character appears at least once in an object file, the corresponding bit of the object file is turned on and if the specific single character does not appear in the object file, the corresponding bit of the object file is kept off.
[0068] (D3) The information generating apparatus generates an upper bit character code appearance map M3 for the upper bit character code group resulting at (C22). The upper bit character code appearance map M3 is index information that is in bitmap format and for each upper bit character code, indicates the presence/absence of the upper bit character codes in each object file. Although both the upper bit character codes and the lower bit character codes are represented in a range from 0x00 to 0xFF, the corresponding bit of the object file is turned on in the upper bit character code appearance map M3 when a code appears as an upper bit character code and not as a lower bit character code.
[0069] (D4) The information generating apparatus also generates a lower bit character code appearance map M4 for the lower bit character code group resulting at (C22). The lower bit character code appearance map M4 is index information that is in bitmap format and indicates the presence/absence of the lower bit character codes in each object file for each lower bit character code. Although both the upper bit character codes and the lower bit character codes are represented in a range from 0x00 to 0xFF, the corresponding bit of the object file is turned on in the lower bit character code appearance map M4 when a code appears as a lower bit character code and not as an upper bit character code.
[0070] Since the specific basic words and the specific single characters are limited by the target appearance rates Pw and Pc, various appearance map can be generated in the smallest map size necessary by setting the target appearance rates Pw and Pc according to purpose and application. In other words, if a record is assigned to all the basic words and single characters on the maps, a basic word or single character having a lower appearance frequency generates a longer bit string of "0", generating waste in the maps.
[0071] Therefore, the map size can be reduced by setting the target appearance rates Pw and Pc according to purpose and application and by registering the specific basic words and the specific single characters corresponding to the target appearance rates Pw and Pc to generate the maps. A basic word excluded from the specific basic words causes no problem because each of single characters making up the basic word is set in the specific single character appearance map M2. A non-specific single character causes no problem because the character is divided and set in the upper bit character code appearance map M3 and the lower bit character code appearance map M4.
[0072] The continuity of characters can be set in a multi-character string appearance map M5 described later and therefore causes no problem. As described above, non-specific basic words can be set in the specific single character appearance map M2, the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5. Therefore, the presence of non-specific basic words can be determined by the logical AND of these appearance maps.
[0073] Although the phases of (A) to (D) may be performed separately for the basic words and the single characters, map generation can be accelerated by simultaneously performing the phases in parallel while shifting characters one-by-one to identify the basic words and the single characters.
[0074] FIG. 2 is an explanatory diagram of an example of division of a non-specific character. In FIG. 2, (A) a non-specific single character and (B) a non-specific single character are taken as examples for description. The character code of is "9D82" and is therefore divided into upper bits "0x9D" and lower bits "0x82". Similarly, the character code of is "5146" and is therefore divided into upper bits "0x51" and lower bits "0x46".
[0075] FIG. 3 is an explanatory diagram of an example of information generation in the information generating apparatus (part 2). (D5) As depicted in FIG. 3, the information generating apparatus also generates the multi-character string appearance map M5 at the phase (D) of FIG. 1. A multi-character string is a character string that is a sequence of two or more characters. For example, is a two-character string of the specific single character and the specific single character . The single character is a non-specific single character and is therefore divided into an upper bit character code "0x9D" and a lower bit character code "0x82". Such a sequence of an upper bit character code and a lower bit character code is also a two-character string.
[0076] A character string is a three-character string of an upper bit character code "0x9D", a lower bit character code "0x82", and a specific single character The character boundary between and is a two-character string of the lower bit character code "0x82" and the specific single character . Similarly, a character string is a four-character string of specific single characters and , the upper bit character code "0x9D", and the lower bit character code "0x82". The character boundary between and is a two-character string of the specific single character and the upper bit character code "0x9D". For simplicity, a two-character string is used in this description.
[0077] FIG. 4 is a block diagram of a hardware configuration of the information generating apparatus according to the embodiments. As depicted in FIG. 4, the information generating apparatus includes a central processing unit (CPU) 401, a read-only memory (ROM) 402, a random access memory (RAM) 403, a magnetic disk drive 404, a magnetic disk 405, an optical disk drive 406, an optical disk 407, a display 408, an interface (I/F) 409, a keyboard 410, a mouse 411, a scanner 412, and a printer 413, respectively connected by a bus 400.
[0078] The CPU 401 governs overall control of the information generating apparatus. The ROM 402 stores therein programs such as a boot program. The RAM 403 is used as a work area of the CPU 401. The magnetic disk drive 404, under the control of the CPU 401, controls the reading and writing of data with respect to the magnetic disk 405. The magnetic disk 405 stores therein data written under control of the magnetic disk drive 404.
[0079] The optical disk drive 406, under the control of the CPU 401, controls the reading and writing of data with respect to the optical disk 407. The optical disk 407 stores therein data written under control of the optical disk drive 406, the data being read by a computer.
[0080] The display 408 displays, for example, data such as text, images, functional information, etc., in addition to a cursor, icons, and/or tool boxes. A cathode ray tube (CRT), a thin-film-transistor (TFT) liquid crystal display, a plasma display, etc., may be employed as the display 408.
[0081] The I/F 409 is connected to a network 414 such as a local area network (LAN), a wide area network (WAN), and the Internet through a communication line and is connected to other apparatuses through the network 414. The I/F 409 administers an internal interface with the network 414 and controls the input and output of data with respect to external apparatuses. For example, a modem or a LAN adaptor may be employed as the I/F 409.
[0082] The keyboard 410 includes, for example, keys for inputting letters, numerals, and various instructions and performs the input of data. Alternatively, a touch-panel-type input pad or numeric keypad, etc. may be adopted. The mouse 411 is used to move the cursor, select a region, or move and change the size of windows. A track ball or a joy stick may be adopted provided each respectively has a function similar to a pointing device.
[0083] The scanner 412 optically reads an image and takes in the image data into the information generating apparatus. The scanner 412 may have an optical character reader (OCR) function as well. The printer 413 prints image data and text data. The printer 413 may be, for example, a laser printer or an ink jet printer.
[0084] FIG. 5 is a block diagram of an example of a functional configuration of the information generating apparatus. An information generating apparatus 500 includes a setting unit 501, a tabulating unit 502, a rank identifying unit 503, a detecting unit 504, a dividing unit 505, and a generating unit 506. For example, functions of the setting unit 501 to the generating unit 506 are implemented by the CPU 401 executing programs stored in a storage device such as the ROM 402, the RAM 403, the magnetic disk 405, and the optical disk 407 depicted in FIG. 4, or by the I/F 409.
[0085] The setting unit 501 has a function of setting the target appearance rates Pw and Pc. For example, the setting unit 501 stores into a storage device, the target appearance rates Pw and Pc input via operation of the keyboard 410 and the mouse 411.
[0086] The tabulating unit 502 tabulates the appearance frequency of each designated word in the object file group F in which character strings are described. For example, as depicted in FIG. 1, the tabulating unit 502 refers to the basic word structure to search for a basic word having a given single character as the starting character by a longest match search from the given single character. A record of the basic word acquired by the longest match search is added and registered to the basic word appearance frequency table 101. If the basic word has already been added and registered, the addition and registration are not necessary. The tabulating unit 502 then adds one to the appearance frequency in the record of the basic word acquired by the longest match search.
[0087] The tabulating unit 502 tabulates the appearance frequency of each single character in the object file group F in which character strings are described. For example, as depicted in FIG. 1, the tabulating unit 502 refers to the single character structure to add and register to the single character appearance frequency table 102, a record for a given single character. If a record has already been added and registered, the addition and registration are not necessary. The tabulating unit 502 then adds one to the appearance frequency in the record of the given single character.
[0088] The rank identifying unit 503 identifies for each designated word and based on an appearance frequency tabulated by the tabulating unit 502 for each designated word, a rank in descending order up to a target appearance rate. For example, the rank identifying unit 503 identifies for each basic word set by the setting unit 501, a rank in descending order up to the target appearance rate Pw. Therefore, as described with reference to FIG. 1, the basic word appearance frequency table 101 is sorted in descending order of appearance frequency.
[0089] The rank of interest is set to the x-th place and, while x is incremented from x=1, the cumulative appearance frequency of a basic word group ranked first to x-th is divided by the total appearance frequency of all the basic words to calculate an appearance rate up to the x-th place. If the calculated appearance rate is within the target appearance rate Pw, x is incremented to calculate an appearance rate up to the x-th place again.
[0090] If the target appearance rate Pw is exceeded, x is decremented by one to identify the rank (value of x after decrement) within the target appearance rate Pw. As a result, the basic word group from the basic word of the first place to the basic word of the rank corresponding to the target appearance rate Pw in descending order of appearance frequency is defined as the specific basic word group.
[0091] The rank identifying unit 503 identifies for each single characters and based on an appearance frequency tabulated by the tabulating unit 502 for each single character, a rank in descending order up to a target appearance rate. For example, the rank identifying unit 503 identifies for each of the single characters set by the setting unit 501, a rank in descending order up to the target appearance rate Pc. Therefore, as described with reference to FIG. 1, the single character appearance frequency table 102 is sorted in descending order of appearance frequency.
[0092] The rank of interest is set to the y-th place and, while y is incremented from y=1, the cumulative appearance frequency of a single character group ranked first to y-th is divided by the total appearance frequency of all the single characters to calculate an appearance rate up to the y-th place. If the calculated appearance rate is within the target appearance rate Pc, y is incremented to calculate an appearance rate up to the y-th place again.
[0093] If the target appearance rate Pc is exceeded, y is decremented by one to identify the rank (value of y after decrement) within the target appearance rate Pc. As a result, the single character group from the single character of the first place to the single character of the rank corresponding to the target appearance rate Pc in descending order of appearance frequency is defined as the specific single character group.
[0094] The detecting unit 504 detects in an object file selected from among the object file group F, specific designated words among the ranks identified, in descending order up to a target appearance rate, by the rank identifying unit 503. For example, a given single character within the object file is shifted one-by-one from the top. At this time, a specific basic word having the given single character as the starting character is detected by the longest match search from the specific basic word group identified by the rank identifying unit 503.
[0095] The detecting unit 504 detects in an object file selected from among the object file group F, specific single characters among the ranks identified by the rank identifying unit 503. For example, given single characters within the object file is shifted one-by-one from the top. At this time, a given single character matching a specific single character identified by the rank identifying unit 503 is detected.
[0096] The dividing unit 505 divides into upper bits and lower bits, the character code of a single character ranked lower than the ranks identified by the rank identifying unit 503. For example, as depicted in FIG. 2, a nonspecific single character is divided into divided character code, including an upper bit character code of the eight upper bits and a lower bit character code of the eight lower bits.
[0097] The generating unit 506 generates for each of the specific designated words detected by the detecting unit 504, index information indicating the presence/absence of the specific designated word in each object file. For example, the generating unit 506 generates the specific basic word appearance map M1 indicating the presence/absence of the specific basic words in each object file for each of the specific basic words detected by the detecting unit 504.
[0098] The generating unit 506 generates for each of the specific single characters detected by the detecting unit 504, index information indicating the presence/absence of the specific single character in each object file. For example, the generating unit 506 generates the specific single character appearance map M2 indicating the presence/absence of the specific single characters in each object file for each of the specific single characters detected by the detecting unit 504.
[0099] The generating unit 506 generates for each upper bit character code obtained by the dividing unit 505, index information (the upper bit character code appearance map M3) indicating the presence/absence of upper bit character code in each object file. The generating unit 506 generates for each of lower bit character code obtained by the dividing unit 505, index information (the lower bit character code appearance map M4) indicating the presence/absence of the lower bit character code in each object file.
[0100] The generating unit 506 generates for each of the multi-character strings, index information (the multi-character string appearance map M5) indicating the presence/absence of the multi-character string in each object file. A multi-character string includes, for example, a multi-character string of specific single characters among the ranks identified by the rank identifying unit 503 or a multi-character string that is a mixture of a specific single character and a divided character. For example, a two-character string includes a two-character string of specific single characters.
[0101] A two-character string includes a multi-character string that is a sequence of a specific single character and an upper bit character code in this order. A two-character string includes a multi-character string that is a sequence of a lower bit character code and a specific single character in this order. A two-character string includes a multi-character string that is a sequence of an upper bit character code and a lower bit character code in this order (i.e., a nonspecific divided character). A two-character string includes a multi-character string that is a sequence of a lower bit character code and an upper bit character code in this order (i.e., a boundary of two nonspecific divided characters). In the multi-character string appearance map M5, a bit is turned on for an object file in which such a multi-character string appears.
[0102] An example of map generation will be described. In this example, the number of connected characters in a multi-character string is two. In the map generation, when a single character, a two-character string, or a basic word appears for the first time, a map thereof (a string of n bits for the file numbers of 1 to n (values are "0")) is generated and the bit of a current object file Fi is turned on. On the other hand, if the map has already been generated for objective files F1 to F(i-1), the bit of the current object file Fi is turned on.
[0103] FIG. 6 is an explanatory diagram of a map generation example (part 1). In FIG. 6, it is assumed that a character string is described in the object file Fi. In the map generation, a starting character is defined as the object character, which is shifted one-by-one toward the end. In FIG. 6, a character indicated by an arrow is the object character.
[0104] (A) First, a starting character is the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since this is the starting character, the two-character string appearance map M5 is not generated. A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0105] (B) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0106] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0107] (C) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0108] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word .
[0109] (D) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0110] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0111] (E) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0112] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word .
[0113] (F) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0114] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0115] (G) The object character is shifted by one character to define as the object character. The object character is a specific single character and, therefore, the specific single character appearance map M2 of the specific single character is specified. Since the bit of the object file Fi is already turned on at (B) in the specific single character appearance map M2 of the object character , nothing is done. Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0116] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0117] (H) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0118] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a designated basic word having the object character as the starting character is performed on having the object character as the starting character. Since is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word .
[0119] (I) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0120] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0121] FIG. 7 is an explanatory diagram of a map generation example (part 2). FIG. 7 depicts a map generation example when a divided character code is involved. If a single character is divided, a divided character code is handled and shifted as one character. In FIG. 7, it is assumed that a character string is described in the object file Fi.
[0122] (A) First, a starting character is the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since this is the starting character, the two-character string appearance map M5 is not generated. A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0123] (B) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to the two-character string appearance map M5 of the two-character string is specified.
[0124] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0125] (C) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0126] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0127] (D) The object character is shifted by one character to define as the object character. The object character is not a specific single character and therefore, the character code "0x8131" of the object character is divided into an upper bit character code "0x81" and a lower bit character code "0x31". The upper bit character code "0x81" is defined as the object character and the upper bit character code appearance map M3 of the upper bit character code "0x81" is specified. The bit of the object file Fi is turned on ("0"→"1") in the upper bit character code appearance map M3 of the upper bit character code "0x81". Since a two-character string 0x81" is acquired when the object character is shifted to the upper bit character code "0x81", the two-character string appearance map M5 of the two-character string 0x81" is specified.
[0128] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string 0x81". A longest match search for a specific basic word having the object character "0x81" as the starting character is performed for "0x81 0x31 having the object character "0x81" as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0129] (E) The object character is shifted by one character to define the lower bit character code "0x31" as the object character. The lower bit character code appearance map M4 of the lower bit character code "0x31" is specified. The bit of the object file Fi is turned on ("0"→"1") in the lower bit character code appearance map M4 of the lower bit character code "0x31". Since a two-character string "0x81 0x31" is acquired when the object character is shifted to the lower bit character code "0x31", the two-character string appearance map M5 of the two-character string "0x81 0x31" is specified.
[0130] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "0x81 0x31". A longest match search for a specific basic word having the object character "0x31" as the starting character is performed for "0×31 having the object character "0x31" as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0131] (F) The object character is shifted by one character to define as the object character. The object character is not a specific single character and therefore, the character code "0xE985" of the object character is divided into an upper bit character code "0xE9" and a lower bit character code "0x85". The upper bit character code "0xE9" is defined as the object character and the upper bit character code appearance map M3 of the upper bit character code "0xE9" is specified.
[0132] The bit of the object file Fi is turned on ("0"→"1") in the upper bit character code appearance map M3 of the upper bit character code "0xE9". Since a two-character string "0x31 0xE9" is acquired when the object character is shifted to the upper bit character code "0xE9", the two-character string appearance map M5 of the two-character string "0x31 0xE9" is specified.
[0133] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "0x31 0xE9". A longest match search for a specific basic word having the object character "0xE9" as the starting character is performed for "0xE9 0x85 having the object character "0xE9" as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0134] (G) The object character is shifted by one character to define the lower bit character code "0x85" as the object character. The lower bit character code appearance map M4 of the lower bit character code "0x85" is specified. The bit of the object file Fi is turned on ("0"→"1") in the lower bit character code appearance map M4 of the lower bit character code "0x85". Since a two-character string "0xE90x85" is acquired when the object character is shifted to the lower bit character code "0x85", the two-character string appearance map M5 of the two-character string "0xE9 0x85" is specified.
[0135] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "0xE9 0x85". A longest match search for a specific basic word having the object character "0x85" as the starting character is performed for "0x85 having the object character "0x85" as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0136] (H) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string "0x85 is acquired when the object character is shifted to the two-character string appearance map M5 of the two-character string "0x85 is specified.
[0137] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "0x85 . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0138] (I) The object character is shifted by one character to define as the object character. The object character is a specific single character and therefore, the specific single character appearance map M2 of the specific single character is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character . Since a two-character string is acquired when the object character is shifted to , the two-character string appearance map M5 of the two-character string is specified.
[0139] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string . A longest match search for a specific basic word having the object character as the starting character is performed for having the object character as the starting character. Since no longest matching specific basic word exists in this case, the specific basic word appearance map M1 is not generated.
[0140] FIGS. 8A and 8B are explanatory diagrams of a map generation example (part 3). In FIGS. 8A and 8B, it is assumed that an alphabetic character string "thatquadratureisquadratureaquadraturepen" is described in the object file Fi. In this example, "quadrature" denotes a blank. A blank is handled as one character.
[0141] (A) First, a starting character "t" is the object character. The object character "t" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "t" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "t". Since this is the starting character, the two-character string appearance map M5 is not generated.
[0142] A longest match search for a specific basic word having the object character "t" as the starting character is performed for "thatquadratureisquadratureaquadraturepen" having the object character "t" as the starting character. Since "that" (pronoun) is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word "that" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word "that".
[0143] (B) The object character is shifted by one character to define "h" as the object character. The object character "h" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "h" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "h". Since a two-character string "th" is acquired when the object character is shifted to "h", the two-character string appearance map M5 of the two-character string "th" is specified.
[0144] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "th". Since a forward match search is emphasized in the case of English words, a longest match search for a specific basic word is not performed from the middle of a character string of an English word.
[0145] (C) The object character is shifted by one character to define "a" as the object character. The object character "a" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "a" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "a". Since a two-character string "ha" is acquired when the object character is shifted to "a", the two-character string appearance map M5 of the two-character string "ha" is specified.
[0146] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "ha".
[0147] (D) The object character is shifted by one character to define "t" as the object character. The object character "t" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "t" is specified. Since the bit of the object file Fi is already turned on at (A) in the specific single character appearance map M2 of the object character "t", nothing is changed. Since a two-character string "at" is acquired when the object character is shifted to "t", the two-character string appearance map M5 of the two-character string "at" is specified.
[0148] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "at".
[0149] (E) The object character is shifted by one character to define "quadrature" as the object character. The object character "quadrature" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "quadrature" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "quadrature". Since a two-character string "quadrature" is acquired when the object character is shifted to "quadrature", the two-character string appearance map M5 of the two-character string "tquadrature" is specified.
[0150] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "tquadrature".
[0151] (F) The object character is shifted by one character to define "i" as the object character. The object character "i" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "i" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "i". Since a two-character string "quadraturei" is acquired when the object character is shifted to "i", the two-character string appearance map M5 of the two-character string "quadraturei" is specified.
[0152] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "quadraturei". A longest match search for a specific basic word having the object character "i" as the starting character is performed for "quadratureisquadratureaquadraturepen" having the object character "i" as the starting character. Since "is" (substantive verb) is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word "is" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word "is".
[0153] (G) The object character is shifted by one character to define "s" as the object character. The object character "s" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "s" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "s". Since a two-character string "is" is acquired when the object character is shifted to "s", the two-character string appearance map M5 of the two-character string "is" is specified.
[0154] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "is".
[0155] (H) The object character is shifted by one character to define "quadrature" as the object character. The object character "quadrature" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "quadrature" is specified. Since the bit of the object file Fi is already turned on at (E) in the specific single character appearance map M2 of the object character "quadrature", nothing is changed. Since a two-character string "quadrature" is acquired when the object character is shifted to "quadrature", the two-character string appearance map M5 of the two-character string "squadrature" is specified.
[0156] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "squadrature".
[0157] (I) The object character is shifted by one character to define "a" as the object character. The object character "a" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "a" is specified. Since the bit of the object file Fi is already turned on at (C) in the specific single character appearance map M2 of the object character "a", nothing is changed. Since a two-character string "quadraturea" is acquired when the object character is shifted to "a", the two-character string appearance map M5 of the two-character string "quadraturea" is specified.
[0158] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "quadraturea". A longest match search for a specific basic word having the object character "a" as the starting character is performed for "aquadraturepen" having the object character "a" as the starting character. Since "a" (indefinite article) is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word "a" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word "a".
[0159] (J) The object character is shifted by one character to define "quadrature" as the object character. The object character "quadrature" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "quadrature" is specified. Since the bit of the object file Fi is already turned on at (E) in the specific single character appearance map M2 of the object character "quadrature", nothing is done. Since a two-character string "aquadrature" is acquired when the object character is shifted to "quadrature", the two-character string appearance map M5 of the two-character string "aquadrature" is specified.
[0160] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "aquadrature".
[0161] (K) The object character is shifted by one character to define "p" as the object character. The object character "p" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "p" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "p". Since a two-character string "quadraturep" is acquired when the object character is shifted to "p", the two-character string appearance map M5 of the two-character string "quadraturep" is specified.
[0162] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "quadraturep". A longest match search for a specific basic word having the object character "p" as the starting character is performed for "pen" having the object character "p" as the starting character. Since "pen" (pen) is retrieved as the longest match in this case, the specific basic word appearance map M1 of the specific basic word "pen" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word "pen".
[0163] (L) The object character is shifted by one character to define "e" as the object character. The object character "e" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "e" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "e". Since a two-character string "pe" is acquired when the object character is shifted to "e", the two-character string appearance map M5 of the two-character string "pe" is specified.
[0164] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "pe".
[0165] (M) The object character is shifted by one character to define "n" as the object character. The object character "n" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "n" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "n". Since a two-character string "en" is acquired when the object character is shifted to "n", the two-character string appearance map M5 of the two-character string "en" is specified.
[0166] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "en".
[0167] FIG. 9 is explanatory diagram of a map generation example (part 4). In FIG. 9, it is assumed that an English word "internal" is described in the object file Fi.
[0168] (A) First, a starting character "i" is the object character. The object character "i" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "i" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "i". Since this is the starting character, the two-character string appearance map M5 is not generated. A longest match search for a specific basic word having the object character "i" as the starting character is performed for "internal" having the object character "i" as the starting character.
[0169] Although "internal" is not a specific basic word and is not retrieved as the longest match, "inter" (inter) is retrieved as the longest match in this case and therefore, the specific basic word appearance map M1 of the specific basic word "inter" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific basic word appearance map M1 of the specific basic word "inter".
[0170] (B) The object character is shifted by one character to define "n" as the object character. The object character "n" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "n" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "n". Since a two-character string "in" is acquired when the object character is shifted to "n", the two-character string appearance map M5 of the two-character string "in" is specified.
[0171] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "in".
[0172] (C) The object character is shifted by one character to define "t" as the object character. The object character "t" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "t" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "t". Since a two-character string "nt" is acquired when the object character is shifted to "t", the two-character string appearance map M5 of the two-character string "nt" is specified.
[0173] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "nt".
[0174] (D) The object character is shifted by one character to define "e" as the object character. The object character "e" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "e" is specified. Since a two-character string "te" is acquired when the object character is shifted to "e", the two-character string appearance map M5 of the two-character string "te" is specified.
[0175] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "te".
[0176] (E) The object character is shifted by one character to define "r" as the object character. The object character "r" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "r" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "r". Since a two-character string "er" is acquired when the object character is shifted to "r", the two-character string appearance map M5 of the two-character string "er" is specified.
[0177] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "er".
[0178] (F) The object character is shifted by one character to define "n" as the object character. The object character "n" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "n" is specified. Since the bit of the object file Fi is already turned on at (B) in the specific single character appearance map M2 of the object character "n", nothing is changed. Since a two-character string "rn" is acquired when the object character is shifted to "n", the two-character string appearance map M5 of the two-character string "rn" is specified.
[0179] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "rn".
[0180] (G) The object character is shifted by one character to define "a" as the object character. The object character "a" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "a" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "a". Since a two-character string "na" is acquired when the object character is shifted to "a", the two-character string appearance map M5 of the two-character string "na" is specified.
[0181] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "na".
[0182] (H) Lastly, the object character is shifted by one character to define "1" as the object character. The object character "1" is a specific single character and therefore, the specific single character appearance map M2 of the specific single character "1" is specified. The bit of the object file Fi is turned on ("0"→"1") in the specific single character appearance map M2 of the specific single character "1". Since a two-character string "al" is acquired when the object character is shifted to "l", the two-character string appearance map M5 of the two-character string "al" is specified.
[0183] The bit of the object file Fi is turned on ("0"→"1") in the two-character string appearance map M5 of the two-character string "al".
[0184] FIG. 10 is a flowchart of an information generation process procedure of the information generating apparatus 500. The information generating apparatus 500 executes a tabulation process (step S1001), a map assignment number determination process (step S1002), and a map generation process (step S1003). Details of the tabulation process (step S1001), the map assignment number determination process (step S1002), and the map generation process (step S1003) will be described later.
[0185] FIG. 11 is a flowchart of a detailed process procedure of the tabulation process (step S1001) depicted in FIG. 10. First, the information generating apparatus 500 sets a file number i to i=1 (step S1101) and reads the object file Fi (step S1102). The information generating apparatus 500 executes a tabulation process for the object file Fi (step S1103). The information generating apparatus 500 determines whether the file number i satisfies i>n (n is the total number of the object files F1 to Fn) (step S1104).
[0186] If i>n is not satisfied (step S1104: NO), the information generating apparatus 500 increments i (step S1105) and returns to step S1102. On the other hand, if i>n is satisfied (step S1104: YES), the information generating apparatus 500 goes to the map assignment number determination process (step S1002) and terminates the tabulation process (step S1001). With this tabulation process (step S1001), the tabulation process for the object file Fi (step S1103) can be executed for each of the object files Fi.
[0187] FIG. 12 is a flowchart of a detailed process procedure of the tabulation process for the object file Fi (step S1103) depicted in FIG. 11. First, the information generating apparatus 500 sets the starting character of the object file Fi as the object character (step S1201) and executes a basic word tabulation process (step S1202). The information generating apparatus 500 then increases the number of appearances of the object character by one in the single character appearance frequency table 102 (step S1203). The information generating apparatus 500 determines whether the object character is the end character of the object file Fi (step S1204).
[0188] If the object character is not the end character of the object file Fi (step S1204: NO), the information generating apparatus 500 shifts the object character toward the end by one character (step S1205) and returns to step S1202. On the other hand, if the object character is the end character of the object file Fi (step S1204: YES), the information generating apparatus 500 goes to step S1104 and terminates the tabulation process for the object file Fi (step S1103). With this tabulation process for the object file Fi (step S1103), the appearance frequencies of the basic words and the single characters present in the object file group F can be tabulated.
[0189] FIG. 13 is a flowchart of a detailed process procedure of the basic word tabulation process (step S1202) depicted in FIG. 12. The information generating apparatus 500 executes a longest match search process (step S1301) and determines whether a longest matching basic word exists (step S1302). If a longest matching basic word exists (step S1302: YES), the information generating apparatus 500 increases the number of appearances of the longest matching basic word by one in the basic word appearance frequency table 101 (step S1303) and goes to step S1203.
[0190] On the other hand, if no longest matching basic word exists (step S1302: NO), the information generating apparatus 500 goes to step S1202. As a result, the basic word tabulation process (step S1202) is terminated. With this basic word tabulation process (step S1202), since the basic words can be counted by the longest match search process (step S1301), a basic word of a longer character string can preferentially be counted.
[0191] FIG. 14 is a flowchart of a detailed process procedure of the longest match search process (step S1301) depicted in FIG. 13. First, the information generating apparatus 500 sets c=1 (step S1401). C is the number of characters from the object character (including the object character). C=1 means only the object character. The information generating apparatus 500 then searches the basic word character structure for a basic word forward-matching an object character string of c characters from the object character (step S1402). The information generating apparatus 500 determines whether a basic word exists from the results of the search (step S1403). If no basic word is hit as a result of the binary search (step S1403: NO), the information generating apparatus 500 goes to step S1406.
[0192] On the other hand, if a basic word is hit as a result of the binary search (step S1403: YES), the information generating apparatus 500 determines whether the hit basic word completely matches the object character string (step S1404). If not (step S1404: NO), the information generating apparatus 500 goes to step S1406. On the other hand, if the hit basic word completely matches (step S1404: YES), the information generating apparatus 500 retains in a storage device, the basic word as a longest matching candidate (step S1405) and goes to step S1406.
[0193] At step S1406, the information generating apparatus 500 determines whether the binary search has been completed for the object character string (step S1406). For example, the information generating apparatus 500 determines whether the binary search has been performed for the last basic word. If the binary search has not been completed (step S1406: NO), the information generating apparatus 500 goes to step S1402 and continues until the binary search is completed.
[0194] On the other hand, if the binary search for the object character string has been completed (step S1406: YES), the information generating apparatus 500 determines whether a c-th character is the end character of the object file Fi (step S1407). If the c-th character is the end character of the object file Fi (step S1407: YES), the information generating apparatus 500 goes to step S1410. On the other hand, if the c-th character is not the end character of the object file Fi (step S1407: NO), the information generating apparatus 500 determines whether c>cmax is satisfied (step S1408). Cmax is a value preliminarily set as the upper limit number of characters of the object character string.
[0195] If c>cmax is not satisfied (step S1408: NO), the information generating apparatus 500 increments c (step S1409) and returns to step S1402. On the other hand, if c>cmax is satisfied (step S1408: YES), the information generating apparatus 500 determines whether a longest matching candidate exists (step S1410). For example, the information generating apparatus 500 determines whether at least one longest matching candidate is retained in the memory at step S1405.
[0196] If longest matching candidates are present (step S1410: YES), the information generating apparatus 500 determines the longest character string among the longest matching candidates as the longest matching basic word (step S1411). The information generating apparatus 500 goes to step S1302. On the other hand, if no longest matching candidate exists at step S1410 (step S1410: NO), the information generating apparatus 500 goes to step S1302. As a result, the longest match search process (step S1301) is terminated. With this longest match search process (step S1301), the longest character string of the completely matching character strings can be retrieved as a basic word from among the basic words in the basic word structure.
[0197] FIG. 15 is a flowchart of a detailed process procedure of the map assignment number determination process (step S1002) depicted in FIG. 10. First, the information generating apparatus 500 sorts the basic word appearance frequency table 101 indicating the appearance frequency for each basic word and the single character appearance frequency table 102 indicating the appearance frequency for each single character, obtained from the tabulation process (step S1001) in descending order of appearance frequency (step S1501). The information generating apparatus 500 refers to the sorted basic word appearance frequency table 101, sets an appearance rank Rw of basic words to Rw=1 (step S1502), and counts a cumulative appearance number Arw up to the appearance rank Rw (step S1503). The information generating apparatus 500 determines whether the following expression (1) is satisfied (step S1504).
Arw>PwxAw (1)
Where, Aw is the total number of appearances of the tabulated basic words.
[0198] If expression (1) is not satisfied (step S1504: NO), the information generating apparatus 500 increments the appearance rank Rw (step S1505) and returns to step S1503. Therefore, the appearance rank Rw is continuously lowered until expression (1) is satisfied.
[0199] If expression (1) is satisfied (step S1504: YES), the information generating apparatus 500 sets a map assignment number Nw of the basic words to Nw=Rw-1 (step S1506). The map assignment number Nw means the number of records (lines) of the specific basic word appearance map M1.
[0200] The information generating apparatus 500 sets an appearance rank Rc of the single characters to Rc=1 (step S1507) and counts the cumulative appearance number Arc up to the appearance rank Rc (step S1508). The information generating apparatus 500 determines whether the following expression (2) is satisfied (step S1509).
Arc>Pc×Ac (2)
Where, Ac is the total number of appearances of the tabulated single characters.
[0201] If expression (2) is not satisfied (step S1509: NO), the information generating apparatus 500 increments the appearance rank Rc (step S1510) and returns to step S1508. Therefore, the appearance rank Rc is continuously lowered until expression (2) is satisfied.
[0202] If expression (2) is satisfied (step S1509: YES), the information generating apparatus 500 sets a map assignment number Nc of the single characters to Nc=Rc-1 (step S1511). The map assignment number Nc means the number of records (lines) of the specific single character appearance map M2. Subsequently, the information generating apparatus 500 goes to the map generation process (step S1003) and terminates the map assignment number determination process (step S1002).
[0203] With the map assignment number determination process (step S1002), the specific basic word appearance map M1 can be generated for the number of basic words corresponding to the target appearance rate Pw. Therefore, since it is not necessary to assign all the basic words to the map and the assignment is determined according to the target appearance rate Pw, the map size can be optimized.
[0204] For the single characters, the specific single character appearance map M2 can be generated for the number of single characters corresponding to the target appearance rate Pc. Therefore, since it is not necessary to assign all the single characters to the map and the assignment is determined according to the target appearance rate Pc, the map size can be optimized.
[0205] FIG. 16 is a flowchart of a detailed process procedure of the map generation process (step S1003) depicted in FIG. 10. First, the information generating apparatus 500 sets the file number i to i=1 (step S1601) and reads the object file Fi (step S1602). The information generating apparatus 500 executes the map generation process for the object file Fi (step S1603). The information generating apparatus 500 then determines whether the file number i satisfies i>n (n is the total number of the object files F1 to Fn) (step S1604).
[0206] If i>n is not satisfied (step S1604: NO), the information generating apparatus 500 increments i (step S1605) and returns to step S1602. On the other hand, if i>n is satisfied (step S1604: YES), the map generation process (step S1003) is terminated. With this map generation process (step S1003), the map generation process of the object file Fi (step S1603) can be executed for each of the object files Fi.
[0207] FIG. 17 is a flowchart of a detailed process procedure of the map generation process for the object file Fi (step S1603) depicted in FIG. 16. First, the information generating apparatus 500 sets the starting character of the object file Fi as the object character (step S1701) and executes a specific basic word appearance map generation process (step S1702), a specific single character appearance map generation process (step S1703), and a multi-character string appearance map generation process (step S1704). The information generating apparatus 500 then determines whether the object character is the end character of the object file Fi (step S1705).
[0208] If the object character is not the end character of the object file Fi (step S1705: NO), the information generating apparatus 500 shifts the object character by one character toward the end (step S1706) and returns to step S1702. On the other hand, if the object character is the end character of the object file Fi (step S1705: YES), the information generating apparatus 500 goes to step S1604 and terminates the map generation process of the object file Fi (step S1603).
[0209] With this map generation process of the object file Fi (step S1603), the specific basic word appearance map M1, the specific single character appearance map M2, and the multi-character string appearance map M5 can simultaneously be generated in parallel while shifting the object character one-by-one.
[0210] FIG. 18 is a flowchart of a detailed process procedure of the specific basic word appearance map generation process (step S1702) depicted in FIG. 17. First, the information generating apparatus 500 executes a longest match search process for the object character (step S1801). A detailed process procedure of the longest match search process (step S1801) has the same process contents as the longest match search process (step S1301) depicted in FIG. 14.
[0211] The information generating apparatus 500 determines whether a longest matching basic word, i.e., a specific basic word exists (step S1802). If no longest matching basic word exists (step S1802: NO), the information generating apparatus 500 goes to the specific single character appearance map generation process (step S1703). On the other hand, if a longest matching basic word exists (step S1802: YES), the information generating apparatus 500 determines whether the specific basic word appearance map M1 has been set for the longest matching basic word (step S1803).
[0212] If the specific basic word appearance map M1 has been set (step S1803: YES), the information generating apparatus 500 goes to step S1805. On the other hand, if the specific basic word appearance map M1 has not been set (step S1803: NO), the information generating apparatus 500 sets the specific basic word appearance map M1 for the longest matching basic word (step S1804) and goes to step S1805.
[0213] For example, the information generating apparatus 500 registers the longest matching basic word as a specific basic word for a specific basic word item of the specific basic word appearance map M1 and sets zero in the bit string for all the file numbers. Subsequently, at step S1805, the information generating apparatus 500 turns on the bit of the object file Fi in the specific basic word appearance map M1 for the longest matching basic word (step S1805).
[0214] The information generating apparatus 500 terminates the specific basic word appearance map generation process (step S1702) and goes to the specific single character appearance map generation process (step S1703). With this specific basic word appearance map generation process (step S1702), the map can be generated with the longest matching basic word defined as a basic word for each object character.
[0215] FIG. 19 is a flowchart of a detailed process procedure of the specific single character appearance map generation process (step S1703) depicted in FIG. 17. First, the information generating apparatus 500 performs a binary search of the single character structure for the object character (step S1901) and determines whether a match is found (S1902). If no matching single character exists (step S1902: NO), the information generating apparatus 500 executes a divided character code appearance map generation process (step S1903) and goes to the multi-character string appearance map generation process (step S1704). Details of the divided character code appearance map generation process (step S1903) will be described later.
[0216] On the other hand, at step S1902, if a single character matching the object character exists based on the results of the binary search (step S1902: YES), the information generating apparatus 500 determines whether the specific single character appearance map M2 has been set for the binary-searched object character (step S1904). If the specific single character appearance map M2 has been set (step S1904: YES), the information generating apparatus 500 goes to step S1906. On the other hand, if the specific single character appearance map M2 has not been set (step S1904: NO), the information generating apparatus 500 sets the specific single character appearance map M2 for the retrieved single character (step S1905) and goes to step S1906.
[0217] For example, the information generating apparatus 500 registers the binary-searched single character as a specific single character for a specific single character item of the specific single character appearance map M2 and sets zero in the bit string for all the file numbers. Subsequently, at step S1906, the information generating apparatus 500 turns on the bit of the object file Fi in the specific single character appearance map M2 for the binary-searched single character (step S1906).
[0218] The information generating apparatus 500 then terminates the specific single character appearance map generation process (step S1703) and goes to the multi-character string appearance map generation process (step S1704). With this specific single character appearance map generation process (step S1703), the map can be generated with the binary-searched single character defined as a specific single character.
[0219] FIG. 20 is a flowchart of a detailed process procedure of the divided character code appearance map generation process (step S1903) depicted in FIG. 19. First, the information generating apparatus 500 divides the object character (step S2001) and determines whether the upper bit character code appearance map M3 has been set for an upper bit character code divided from the object character (step S2002). If the upper bit character code appearance map M3 has been set (step S2002: YES), the information generating apparatus 500 goes to step S2004. On the other hand, if the upper bit character code appearance map M3 has not been set (step S2002: NO), the information generating apparatus 500 sets the upper bit character code appearance map M3 for the upper bit character code divided from the object character (step S2003) and goes to step S2004.
[0220] For example, the information generating apparatus 500 registers the upper bit character code divided from the object character for an upper bit character code item of the upper bit character code appearance map M3 and sets zero in the bit string for all the file numbers. Subsequently, at step S2004, the information generating apparatus 500 turns on the bit of the object file Fi in the upper bit character code appearance map M3 for the upper bit character code divided from the object character (step S2004).
[0221] The information generating apparatus 500 determines whether the lower bit character code appearance map M4 has been set for a lower bit character code divided from the object character (step S2005). If the lower bit character code appearance map M4 has been set (step S2005: YES), the information generating apparatus 500 goes to step S2007. On the other hand, if the lower bit character code appearance map M4 has not been set (step S2005: NO), the information generating apparatus 500 sets the lower bit character code appearance map M4 for the lower bit character code divided from the object character (step S2006) and goes to step S2007.
[0222] For example, the information generating apparatus 500 registers the lower bit character code divided from the object character for a lower bit character code item of the lower bit character code appearance map M4 and sets zero in the bit string for all the file numbers. Subsequently, at step S2007, the information generating apparatus 500 turns on the bit of the object file Fi in the lower bit character code appearance map M4 for the lower bit character code divided from the object character (step S2007).
[0223] The information generating apparatus 500 then terminates the divided character code appearance map generation process (step S1903) and goes to the multi-character string appearance map generation process (step S1704). With regard to this divided character code appearance map generation process (step S1903), for single characters ranked lower than the rank corresponding to the target appearance rate Pc, a large number of OFF bits appears due to lower appearance frequency.
[0224] However, the exclusion from the generation of the specific single character appearance map M2 enables optimization of the map size of the specific single character appearance map M2. The single characters ranked lower than the rank corresponding to the target appearance rate Pc are divided and set in maps having fixed map sizes such as the upper bit character code appearance map M3 and the lower bit character code appearance map M4. Therefore, since no change is made in the upper bit character code appearance map M3 and the lower bit character code appearance map M4 regardless of an appearance rate set as the target appearance rate Pc, the map sizes can be prevented from increasing and a memory can be saved.
[0225] FIG. 21 is a flowchart of a detailed process procedure of the multi-character string appearance map generation process (step S1704) depicted in FIG. 17. First, the information generating apparatus 500 executes a multi-character string identification process for the object character (step S2101). Details of the multi-character string identification process (step S2101) will be described later. After the multi-character string identification process (step S2101), if no multi-character string related to the object character exists (step S2102: NO), the information generating apparatus 500 goes to step S1705.
[0226] On the other hand, if a multi-character string related to the object character exists (step S2102: YES), the information generating apparatus 500 determines whether the multi-character string appearance map M5 has been set for the multi-character string related to the object character (step S2103). If the multi-character string appearance map M5 has been set (step S2103: YES), the information generating apparatus 500 goes to step S2105. On the other hand, if the multi-character string appearance map M5 has not been set (step S2103: NO), the information generating apparatus 500 sets the multi-character string appearance map M5 for the multi-character string related to the object character (step S2104) and goes to step S2105.
[0227] For example, the information generating apparatus 500 registers the multi-character string related to the object character for a multi-character string item of the multi-character string appearance map M5 and sets zero in the bit string for all the file numbers. Subsequently, at step S2105, the information generating apparatus 500 turns on the bit of the object file Fi in the multi-character string appearance map M5 for the multi-character string related to the object character (step S2105). The information generating apparatus 500 then terminates the multi-character string appearance map generation process (step S1704) and goes to step S1705. With the multi-character string appearance map generation process (step S1704), the map can be generated for each multi-character string related to the object character.
[0228] FIG. 22 is a flowchart of a detailed process procedure of the multi-character string identification process (step S2101) depicted in FIG. 21. First, for the object character, the information generating apparatus 500 determines whether the object character has been divided (step S2201). In other words, the information generating apparatus 500 determines whether the object character is a divided character code. If the object character has not been divided (step S2201: NO), i.e., in the case of a single character, the information generating apparatus 500 determines whether the previous character exists (step S2202).
[0229] If the previous character exists (step S2202: YES), the information generating apparatus 500 determines whether the previous character has been divided (step S2203). In other words, the information generating apparatus 500 determines whether the previous character is a divided character code. If the previous character has not been divided (step S2203: NO), i.e., in the case of a single character, the information generating apparatus 500 determines a character string made up of the previous single character before the object character and the object character (single character) as a multi-character string (step S2204). The information generating apparatus 500 goes to step S2102.
[0230] On the other hand, at step S2203, if the previous character has been divided (step S2203: NO), i.e., in the case of a divided character code, the divided character code, i.e., the previous character, is a lower bit character code. Therefore, the information generating apparatus 500 determines a character string made up of the lower bit character code, which is the previous character, and the object character as a multi-character string (step S2205). The information generating apparatus 500 goes to step S2102.
[0231] At step S2202, if no previous character exists (step S2202: NO), only the object character exists and therefore, the information generating apparatus 500 goes to step S2102 without determining a multi-character string.
[0232] At step S2201, if the object character is divided (step S2201: YES), i.e., in the case of a divided character code, the information generating apparatus 500 determines whether the divided character code is an upper bit character code or a lower bit character code (step S2206).
[0233] In the case of the upper bit character code (step S2206: UPPER), the information generating apparatus 500 determines whether the previous character has been divided (step S2207). In other words, it is determined whether the previous character is a divided character code. If the previous character has not been divided (step S2207: NO), i.e., in the case of a single character, the information generating apparatus 500 determines a character string made up of the previous single character before the object character and the upper bit character code divided from the object character as a multi-character string (step S2208). The information generating apparatus 500 goes to step S2102.
[0234] On the other hand, at step S2207, if the previous character has been divided (step S2207: YES), i.e., in the case of a divided character code, the divided character code, i.e., the previous character, is a lower bit character code. Therefore, the information generating apparatus 500 determines a character string made up of the lower bit character code, which is the previous character, and the upper bit character code divided from the object character as a multi-character string (step S2209). The information generating apparatus 500 goes to step S2102.
[0235] At step S2206, in the case of the lower bit character code (step S2206: LOWER), the information generating apparatus 500 determines a character string bit consisting of the upper bit character code and the lower bit character code divided from the object character as a multi-character string (step S2210). The information generating apparatus 500 goes to step S2102.
[0236] With the multi-character string identification process (step S2101), a multi-character string can be identified even if the object character is divided. Since the multi-character strings are identified by shifting characters one-by-one, the map can simultaneously be generated in parallel with the specific basic word appearance map M1 and the specific single character appearance map M2.
[0237] With the information generation described above, since the numbers of basic words and single characters associated with the map generation are limited by the target appearance rates Pw and Pc, wasteful map generation is eliminated, and the acceleration of the map generation and the optimization of the map size can be realized at the same time. The generation of different types of maps can simultaneously be executed in parallel by shifting characters one-by-one, and the different types of maps used in highly accurate search can more efficiently be generated.
[0238] The information search program, the information search apparatus, and the information search method will be described. In the information search program, the information search apparatus, and the information search method, a search is performed by using various maps generated in the information generating program, the information generating apparatus, and the information generating method. An exemplary hardware configuration of the information search apparatus is the same as the exemplary hardware configuration depicted in FIG. 4. The information search apparatus may be a computer integrated with or separated from the information generating apparatus 500.
[0239] FIG. 23 is a block diagram of an example of a functional configuration of the information search apparatus. An information search apparatus 2300 includes an input unit 2301, a dividing unit 2302, a file identifying unit 2303, a narrowing-down unit 2304, a search unit 2305, and an output unit 2306. For example, the functions of the input unit 2301 to the output unit 2306 are implemented by the CPU 401 executing programs stored in a storage device such as the ROM 402, the RAM 403, the magnetic disk 405, and the optical disk 407 depicted in FIG. 4, or by the I/F 409.
[0240] The input unit 2301 receives input of a search character string. For example, the input of a search character string is received via operation of an input device such as the keyboard 410 and the mouse 411.
[0241] Among the single characters making up the search character string, the dividing unit 2302 divides the character code of a single character that does not correspond to a specific single character into divided character code, including upper bit character code and lower bit character code. For example, the dividing unit 2302 divides a character code of a single character that does not correspond to a specific single character registered as a specific single character item in the specific single character appearance map M2 described above into an upper bit character code and a lower bit character code.
[0242] The file identifying unit 2303 refers to index information indicating the presence/absence of specific designated words in each object file and identifies from among designated words present in the object file group F in which character strings are described and among the ranks in descending order up to the target appearance rate for the designated words, an object file that includes the search character string. For example, the file identifying unit 2303 identifies an object file that includes the search character string by referring to the specific basic word appearance map M1 described above.
[0243] The file identifying unit 2303 refers to index information indicating the presence/absence of specific single characters in each object file and identifies from among single characters present in the object file group F in which character strings are described and among the ranks in descending order up to the target appearance rate for the single characters, an object file that includes each single character making up the search character string. For example, the file identifying unit 2303 identifies an object file that includes the search character string by referring to the specific single character appearance map M2 described above.
[0244] The file identifying unit 2303 identifies an object file that includes an upper bit character code by referring to index information that indicates for each object file, the presence/absence of the upper bit character code obtained by the dividing unit 2302. For example, the file identifying unit 2303 refers to the upper bit character code appearance map M3 described above and identifies an object file that includes an upper bit character code obtained by the dividing unit 2302.
[0245] Similarly, the file identifying unit 2303 identifies an object file that includes lower bits by referring to index information indicating in each object file, the presence of lower bits obtained by the dividing unit 2302. For example, the file identifying unit 2303 refers to the lower bit character code appearance map M4 described above and identifies an object file that includes a lower bit character code obtained by the dividing unit 2302.
[0246] The file identifying unit 2303 refers to index information indicating the presence/absence of multi-character strings in each object file and identifies for each multi-character string that is a sequence of single characters among single characters present in the object file group F and among the ranks in descending order up to the target appearance rate for the single characters, an object file that includes each multi-character string making up the search character string. For example, the file identifying unit 2303 identifies an object file that includes each multi-character string making up the search character string by referring to the multi-character string appearance map M5 described above.
[0247] The file identifying unit 2303 refers to index information indicating the presence/absence of multi-character strings in each object file for each multi-character string that is a sequence of specific single characters and identifies from among single characters present in the object file group F and among the ranks in descending order up to the target appearance rate, an object file that includes a multi-character string that is a sequence of a specific single character and an upper bit character code making up the search character string. For example, the file identifying unit 2303 identifies an object file that includes each multi-character string making up the search character string by referring to the multi-character string appearance map M5 described above.
[0248] The file identifying unit 2303 identifies for each multi-character string that is a sequence of lower bits and a specific single character among single characters present in the object file group F and among the ranks in descending order up to the target appearance rate for the single characters, an object file that includes the multi-character string, by referring to index information indicating the presence/absence of multi-character strings in each object file. For example, the file identifying unit 2303 identifies an object file that includes each multi-character string making up the search character string by referring to the multi-character string appearance map M5 described above.
[0249] The file identifying unit 2303 refers to index information indicating the presence/absence of multi-character strings in each object file and identifies for each multi-character string that is a sequence of upper bits and lower bits, an object file that includes the multi-character string. For example, the file identifying unit 2303 identifies an object file that includes each multi-character string making up the search character string by referring to the multi-character string appearance map M5 described above.
[0250] The narrowing-down unit 2304 narrows down the object file group F identified by the file identifying unit 2303 to the object files that include all of the single characters making up the search character string. For example, the narrowing-down unit 2304 narrows down the object files identified by the file identifying unit 2303 to the object files having the bits turned on for all the single characters making up the search character string in the specific single character appearance map M2.
[0251] The narrowing-down unit 2304 narrows down the object file group F identified by the file identifying unit 2303 to the object files that include all of the single characters and the multi-character strings making up the search character string. For example, the narrowing-down unit 2304 narrows down the object files identified by the file identifying unit 2303 to the object files having the bits turned on for all the specific single characters making up the search character string in the specific single character appearance map M2 and having the bits turned on for all the multi-character strings making up the search character string in the multi-character string appearance map M5.
[0252] The narrowing-down unit 2304 narrows down the object file group F identified by the file identifying unit 2303 to the object files that include all of the single characters, the upper bit character codes, the lower bit character codes, and the multi-character strings making up the search character string.
[0253] For example, the narrowing-down unit 2304 narrows down the object files identified by the file identifying unit 2303 to the object files having the bits turned on for all the specific single characters making up the search character string in the specific single character appearance map M2, having the bits turned on for all the upper bit character codes making up the search character string in the upper bit character code appearance map M3, having the bits turned on for all the lower bit character codes making up the search character string in the lower bit character code appearance map M4, and having the bits turned on for all the multi-character strings making up the search character string in the multi-character string appearance map M5.
[0254] The search unit 2305 refers to the specific basic word appearance map M1 and searches for information related to the search character string in the object files identified by the file identifying unit 2303. For example, if the search character string corresponds to a specific basic word, the search unit 2305 refers to the specific basic word appearance map M1 and searches for a character string matching the search character string from the identified object files. If the search character string does not correspond to a specific basic word, the search unit 2305 searches the object files narrowed down by the narrowing-down unit 2304, for a character string matching the search character string.
[0255] The output unit 2306 outputs a search result obtained by the search unit 2305. For example, the output unit 2306 performs display output of the search result on a display, performs print output of the search result, verbally reads the search result, stores the search result into a storage device, and/or transmits the search result to an external device.
[0256] The search result is output as a character string matching the search character string or is output as information related to the character string matching the search character string. For the related information, for example, if the character string matching the search character string is an entry word of a dictionary, descriptive text is output. Conversely, if the character string matching the search character string is a character string in a descriptive text of a dictionary, the entry word of the descriptive text may be output.
[0257] An example of the information search process will be described.
[0258] FIG. 24 is an explanatory diagram of an example (part 1) of the information search process. In FIG. 24, it is assumed that a search character string is . The search character string includes specific basic words and . Therefore, an AND operation is performed for the specific basic word appearance map M2 of and depicted in FIG. 24. The object files are identified that have the file numbers turned to ON (1) in an AND result of this AND operation. In the case of FIG. 24, the object files F3 and Fn are likely to include the search character string .
[0259] FIG. 25 is an explanatory diagram of an example (part 2) of the information search process. In FIG. 25, it is assumed that a search character string is . The search character string includes specific single characters and . A two-character string also included. No specific basic word is included.
[0260] Therefore, an AND operation is performed for the specific single character appearance map M2 and the multi-character string appearance map M5 depicted in FIG. 25. The object file is identified that has the file number turned to ON (1) in an AND result of this AND operation. In the case of FIG. 25, the object file Fn includes the search character string . The object file Fn is likely to include a character string (e.g., ) including and therefore, the deterioration of search performance due to so-called parting can be prevented.
[0261] FIG. 26 is an explanatory diagram of an example (part 3) of the information search process. In FIG. 26, it is assumed that a search character string is . Since the single characters and in the search character string are not specific single characters, the search character string includes the upper bit character code "0x81" and the lower bit character code "0x31" of the single character and the upper bit character code "0xE9" and the lower bit character code "0x85" of the single character . The search character string includes two-character strings "0x81 0x31", "0x31 0xE9", and "0xE9 0x85". No specific basic word is included in the search character string .
[0262] Therefore, an AND operation is performed for the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5 depicted in FIG. 26. The object file is identified that has the file number turned to ON (1) in an AND result of this AND operation. In the case of FIG. 26, the object file Fn is likely to include the search character string .
[0263] FIG. 27 is an explanatory diagram of an example (part 4) of the information search process. In FIG. 27, it is assumed that a search character string is . Although the single character of the search character string is a specific single character, is not a specific single character. Therefore, the search character string includes the specific single character and the upper bit character code "0x81" and the lower bit character code "0x31" of the single character . The search character string includes two-character strings 0x81" and "0x81 0x31". No specific basic word is included in the search character string .
[0264] Therefore, an AND operation is performed for the specific single character appearance map M2, the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5 depicted in FIG. 27. The object file is identified that has the file number turned to ON (1) in an AND result of this AND operation. In the case of FIG. 27, the object file Fn is likely to include the search character string .
[0265] FIG. 28 is an explanatory diagram of an example (part 5) of the information search process. In FIG. 28, it is assumed that a search character string is . Although the single character 1B" of the search character string is a specific single character, is not a specific single character. Therefore, the search character string includes the specific single character and the upper bit character code "0x81" and the lower bit character code "0x31" of the single character . The search character string includes two-character strings "0x81 0x31" and "0x31. No specific basic word is included in the search character string .
[0266] Therefore, an AND operation is performed for the specific single character appearance map M2, the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5 depicted in FIG. 28. The object file is identified that has the file number turned to ON (1) in an AND result of this AND operation. In the case of FIG. 28, the object file Fn is likely to include the search character string .
[0267] FIG. 29 is an explanatory diagram of an example (part 6) of the information search process. In FIG. 29, it is assumed that search character strings are "is" and "a" and that a search condition is AND. The search character string "is" includes the specific basic word "is" (substantive verb) and the search character string "a" includes the specific basic word "a" (indefinite article). These search character strings enable a search for a sentence of the so-called is-a construction. Therefore, an AND operation is performed for the specific basic word appearance map M1 of "is" and "a" depicted in FIG. 29. The object files are identified that have the file numbers turned to ON (1) in an AND result of this AND operation. In the case of FIG. 29, the object files F3 and Fn includes the search character strings "is" and "a".
[0268] FIG. 30 is an explanatory diagram of an example (part 7) of the information search process. In FIG. 30, it is assumed that a search character string is "tern". The search character string "tern" includes two-character strings "te", "er", and "rn". Therefore, the object file is identified that has the file number turned to ON (1) in the two-character string appearance map M5 depicted in FIG. 30. In the case of FIG. 30, the object file Fn includes the search character string "tern".
[0269] FIG. 31 is a flowchart of an information search process procedure of the information search apparatus 2300. First, the information search apparatus 2300 waits for input of a search character string group (including one search character string) to the input unit 2301 (step S3101: NO) and, if the search character string group is input (step S3101: YES), the information search apparatus 2300 determines whether an unselected search character string exists (step S3102). If an unselected search character string exists (step S3102: YES), the information search apparatus 2300 selects one unselected search character string (step S3103), executes a file identification process (step S3104), and returns to step S3102.
[0270] On the other hand, if no unselected search character string exists (step S3102: NO), the information search apparatus 2300 determines a search condition (step S3105). If the search condition is AND (step S3105: AND), the information search apparatus 2300 uses an AND operation to narrow down and set the object files identified for each search character string as search object files (step S3106) and goes to step S3108. On the other hand, if the search result is OR (step S3105: OR), the information search apparatus 2300 uses an OR operation to narrow down and set the object files identified for each search character string as search object files (step S3107) and goes to step S3108.
[0271] At step S3108, a search is performed for each of the search object files according to the search condition (step S3108). An output process of outputting a search result is executed (step S3109) and the information search process is terminated.
[0272] FIG. 32A is a flowchart (part 1) of a detailed process procedure of the file identification process (step S3104) depicted in FIG. 31. First, the information search apparatus 2300 sets a starting character of a search character string as the object character (step S3201) and executes a longest match search process for the search character string (step S3202). Details of the longest match search process of the search character string (step S3202) will be described later.
[0273] The information search apparatus 2300 determines whether a longest matching basic word exists, based on a result of the longest match search process of the search character string (step S3202) (step S3203). If no longest matching basic word exists (step S3203: NO), the information search apparatus 2300 goes to step S3211 of FIG. 32B. On the other hand, if a longest matching basic word exists (step S3203: YES), the information search apparatus 2300 identifies an object file that includes the longest matching basic word from the specific basic word appearance map M1 (step S3204). For example, the information search apparatus 2300 identifies an object file having a bit turned on for the longest matching basic word, i.e., the specific basic word.
[0274] The information search apparatus 2300 then shifts the object character by an amount corresponding to the character string of the longest matching basic word (step S3205), and determines whether the object character exists (step S3206). If the object character exists (step S3206: YES), the information search apparatus 2300 returns to step S3202. On the other hand, no object character exists (step S3206: NO), the information search apparatus 2300 uses the narrowing-down unit 2304 to perform an AND operation to narrow down the object files identified up to step S3206 (step S3207). The information search apparatus 2300 returns to step S3102.
[0275] FIG. 32B is a flowchart (part 2) of a detailed process procedure of the file identification process (step S3104) depicted in FIG. 31. At step S3203 of FIG. 32A, if no longest matching basic word exists (step S3203: NO), in FIG. 32B, the information search apparatus 2300 determines whether the object character is a specific single character (step S3211). For example, the information search apparatus 2300 determines whether the object character is registered as a specific single character item in the specific single character appearance map M2.
[0276] If the object character is a specific single character (step S3211: YES), the information search apparatus 2300 identifies an object file that includes the object character from the specific single character appearance map M2 (step S3212). For example, the information search apparatus 2300 identifies an object file having a bit turned on for the object character and goes to step S3216.
[0277] On the other hand, if the object character is not a specific single character at step S3211 (step S3211: NO), the information search apparatus 2300 divides the object character into an upper bit character code and a lower bit character code (step S3213). The information search apparatus 2300 identifies an object file that includes the upper bit character code of the single character, from the upper bit character code appearance map M3 (step S3214). For example, the information search apparatus 2300 identifies an object file having a bit turned on for the upper bit character code. Similarly, the information search apparatus 2300 identifies an object file that includes the lower bit character code of the single character, from the lower bit character code appearance map M4 (step S3215). For example, the information search apparatus 2300 identifies an object file having a bit turned on for the lower bit character code. The information search apparatus 2300 goes to step S3216.
[0278] At step S3216, the information search apparatus 2300 executes a file identification process using the multi-character string appearance map M5 (step S3216). Details of the file identification process using the multi-character string appearance map M5 (step S3216) will be described later. The information search apparatus 2300 then shifts the object character by one character (step S3217) and goes to step S3206 of FIG. 32A.
[0279] With this file identification process (step S3104), if the search character string includes a specific basic word, the object files can be narrowed down by the specific basic word appearance map M1 and, if not including a specific basic word, the object files can be narrowed down and identified by the AND operation of the specific single character appearance map M2, the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5.
[0280] FIG. 33 is a flowchart of a detailed process procedure of the longest match search process (step S3202) depicted in FIG. 32B. First, the information search apparatus 2300 sets c=1 (step S3301). C is the number of characters from the object character (including the object character). C=1 means only the object character. The information search apparatus 2300 then performs a binary search for a basic word forward matching an object character string of c characters from the object character (step S3302). An object to be searched for in this case is a specific basic word group registered as the specific basic word items of the specific basic word appearance map M1.
[0281] The information search apparatus 2300 determines whether a specific basic word exists, based on a result of the binary search (step S3303). If no specific basic word is hit as a result of the binary search (step S3303: NO), the information search apparatus 2300 goes to step S3306.
[0282] On the other hand, if a specific basic word is hit as a result of the binary search (step S3303: YES), the information search apparatus 2300 determines whether the hit specific basic word completely matches the object character string (step S3304). If the designated basic word does not completely match (step S3304: NO), the information search apparatus 2300 goes to step S3306. On the other hand, if the designated basic word completely matches (step S3304: YES), the information search apparatus 2300 retains in a storage device, the specific basic word as a longest match candidate (step S3305) and goes to step S3306.
[0283] At step S3306, the information search apparatus 2300 determines whether the binary search has been completed for the object character string (step S3306). For example, the information search apparatus 2300 determines whether the binary search has been performed for the last specific basic word. If the binary search has not been completed (step S3606: NO), the information search apparatus 2300 goes to step S3302 and continues until the binary search is completed.
[0284] On the other hand, if the binary search has been completed for the object character string (step S3306: YES), the information search apparatus 2300 determines whether a c-th character is the end character of the search character string (step S3307). If the c-th character is the end character of the search character string (step S3307: YES), the information search apparatus 2300 goes to step S3310. On the other hand, if the c-th character is not the end character of the search character string (step S3307: NO), the information search apparatus 2300 determines whether c>cmax is satisfied (step S3308). Cmax is a value preliminarily set as the upper limit number of characters of the object character string.
[0285] If c>cmax is not satisfied (step S3308: NO), the information search apparatus 2300 increments c (step S3309) and returns to step S3302. On the other hand, if c>cmax is satisfied (step S3308: YES), the information search apparatus 2300 determines whether a longest matching candidate exists (step S3310). For example, the information search apparatus 2300 determines whether at least one longest matching candidate is retained in the storage device at step S3305.
[0286] If longest matching candidates exist (step S3310: YES), the information search apparatus 2300 determines the longest character string among the longest matching candidates as the longest matching basic word (step S3311). The information search apparatus 2300 then goes to step S3202. On the other hand, if no longest matching candidate exists at step S3310 (step S3310: NO), the information search apparatus 2300 goes to step S3203.
[0287] As a result, the longest match search process (step S3202) is terminated. With this longest match search process (step S3202), the longest character string of the completely matching character strings can be searched as a specific basic word from the specific basic word group registered in the specific basic word appearance map M1.
[0288] FIG. 34 is a flowchart of a detailed process procedure of the file identification process using the multi-character string appearance map M5 (step S3216) depicted in FIG. 32B. First, the information search apparatus 2300 defines a starting character of a search character string as the object character (step S3401). In this search character string, a divided character code is handled as one character if the character is divided into divided character codes.
[0289] The information search apparatus 2300 determines whether the object character is a divided character code (step S3402). If the object character is not a divided character code (step S3402: NO), the information search apparatus 2300 determines whether the previous character of the object character exists (step S3403). For example, if the object character is a lower bit character code, the previous character is an upper bit character code. If the object character is a specific single character or an upper bit character code, the previous character is a lower bit character code given that a character is divided immediately before the object character.
[0290] If the previous character exists (step S3403: YES), the information search apparatus 2300 determines whether the previous character is a divided character code (step S3404). If the previous character is not a divided character code (step S3404: NO), the information search apparatus 2300 identifies an object file from the multi-character string appearance map M5 of a bi-gram specific single character string (step S3405). For example, the information search apparatus 2300 identifies an object file having a bit turned on for a bi-gram specific single character string and goes to step S3217.
[0291] On the other hand, at step S3404, if the previous character is a divided character code (step S3404: YES), the information search apparatus 2300 identifies an object file from the multi-character string appearance map M5 of a multi-character string made up of a divided character code and a specific single character (step S3406). For example, the information search apparatus 2300 identifies an object file having a bit turned on for a multi-character string made up of a divided character code and a specific single character and goes to step S3217.
[0292] On the other hand, at step S3403, if no previous character of the object character exists (step S3403: NO), the information search apparatus 2300 goes to step S3217 without identifying an object file.
[0293] If the object character is a divided character code (step S3402: YES), the information search apparatus 2300 determines whether the previous character of the object character exists (step S3407).
[0294] If the previous character exists (step S3407: YES), the information search apparatus 2300 determines whether the previous character is a divided character code (step S3408). If the previous character is not a divided character code (step S3408: NO), the information search apparatus 2300 identifies an object file from the multi-character string appearance map M5 of a multi-character string made up of a specific single character and an upper bit character code (step S3409). For example, the information search apparatus 2300 identifies an object file having a bit turned on for a multi-character string made up of a specific single character and an upper bit character code and goes to step S3217.
[0295] On the other hand, at step S3408, if the previous character is a divided character code (step S3408: YES), the information search apparatus 2300 identifies an object file from the multi-character string appearance map M5 of a multi-character string made up of two divided character codes that are connected (step S3410). For example, the information search apparatus 2300 identifies an object file having a bit turned on for a multi-character string made up of two connected divided character codes and goes to step S3217.
[0296] At step S3407, if no previous character of the object character exists (step S3407: NO), the information search apparatus 2300 goes to step S3217 without identifying an object file.
[0297] With this file identification process of the multi-character string appearance map M5 (step S3216), an object file can be identified that has a multi-character string made up only of specific single characters, a multi-character string made up only of divided character codes, or a connection character code made up of a mixture of a specific single character and a divided character code present in the search character string.
[0298] As described above, according to the information search described above, if a specific basic word exists in a search character string, an object file can be identified from the specific basic word appearance map M1 and therefore, a high-speed search process can be realized. Even if no specific basic word exists in the search character string, object files can efficiently be narrowed down by using the specific single character appearance map M2, the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5. For example, a new clipped word such as is not registered as a specific basic word and, in such a case, object files can be narrowed down.
[0299] Map projection will be described. With regard to the map projection, an object file may newly be added to the object file group F. In such a case, the phases (A) to (D) are performed as depicted in FIGS. 1 to 3 for the added object file. The map projection refers to a process of generating bit lines for the added object file in the specific basic word appearance map M1, the specific single character appearance map M2, the upper bit character code appearance map M3, the lower bit character code appearance map M4, and the multi-character string appearance map M5.
[0300] FIG. 35 is an explanatory diagram of the map projection. In FIG. 35, the specific basic word appearance map M1 is taken as an example for the description. In (A), a segment S1 is a bitmap made up of the specific basic word group and the object files F1 to Fn corresponding to the initial object file group F.
[0301] If a predetermined number of added object files are accumulated, a new segment is set. In FIG. 35, for example, a segment S2 is set as a new segment if n object files are added when n is the same number as the segment S1. The number may not be the same as the segment S1.
[0302] (B) depicts a state after the segment S2 is set. (C) depicts a state when an object file is newly added with bit lines generated for the added object file. As depicted in (D), a bitmap can be generated with the specific basic word appearance map M1 made up of the specific basic word group and the segments S1 to SN.
[0303] FIG. 36 is a flowchart of an information search process procedure when using appearance maps segmented into multiple pieces due to addition of object files. First, the information search apparatus 2300 sets a segment number j as j=1 (step S3601) and executes an information search process using a segment Sj (step S3602). In this information search process (step S3602), step S3101 to step S3108 depicted in FIG. 31 are executed. Therefore, the file identification process (step S3104) depicted in FIGS. 32A and 32B and the longest match search process (step S3202) depicted in FIG. 33 are also executed. However, a partially different process is included in FIG. 32B and will therefore be descried with reference to FIG. 37.
[0304] The information search apparatus 2300 determines whether j>N is satisfied (step S3603). If j>N is not satisfied (step S3603: NO), the information search apparatus 2300 increments j to specify the next segment Sj (step S3604) and returns to step S3602. On the other hand, if j>N is satisfied at step S3603 (step S3603: YES), the information search apparatus 2300 executes an output process by the output unit 2306 (step S3605). At this step, search results using the segments S1 to SN are output.
[0305] FIG. 37 is a flowchart of a portion of the file identification process (step S3104) in the information search process (step S3602) depicted in FIG. 36. In FIG. 37, the steps identical to those in FIG. 32B are denoted by the same step numbers and will not be described. In FIG. 37, at step S3212, it is determined whether an object file in the segment Sj exists that can be identified as the file at step S3212 (step S3700).
[0306] If an object file in the segment Sj exists that can be identified as the file (step S3700: YES), the information search apparatus 2300 goes to step S3216. On the other hand, if no object file in the segment Sj exists that can be identified as the file (step S3700: NO), the information search apparatus 2300 goes to step S3603. In other words, when the segment Sj does not have an object file that includes a specific single character that is the object character, even if a file can be identified by setting the subsequent characters as the object file, no object file is acquired by narrowing down files at step S3207.
[0307] Therefore, if no object file can be identified for one character, the information search apparatus 2300 goes to step S3603 and specifies the next segment Sj, thereby skipping useless searches and accelerating the search speed.
[0308] As described above, according to the information generating program, the information generating apparatus, and the information generating method, the index information indicating the presence/absence of basic words and characters can be accelerated and the size of the index information can be optimized. According to the information search program, the information search apparatus, and the information search method, search noise can be reduced.
[0309] The methods described in the present embodiment may be implemented by executing a prepared program on a computer such as a personal computer and a workstation. The program is stored on a computer-readable recording medium such as a hard disk, a flexible disk, a CD-ROM, an MO, and a DVD, read out from the computer-readable medium, and executed by the computer. The program may be distributed through a network such as the Internet.
[0310] The information generating program, the information generating apparatus, and the information generating method enable faster generation of index information indicating the presence/absence of basic words and characters and optimization of the size of the index information. The information search program, the information search apparatus, and the information search method effect reductions in search noise.
[0311] All examples and conditional language provided herein are intended for pedagogical purposes of aiding the reader in understanding the invention and the concepts contributed by the inventor to further the art, and are not to be construed as limitations to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although one or more embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.
2013-11-14 Managing the product of temporary groups in a community
2013-10-10 Medical information search apparatus