[go: up one dir, main page]

WO2016001991A1 - 検索方法 - Google Patents

検索方法 Download PDF

Info

Publication number
WO2016001991A1
WO2016001991A1 PCT/JP2014/067438 JP2014067438W WO2016001991A1 WO 2016001991 A1 WO2016001991 A1 WO 2016001991A1 JP 2014067438 W JP2014067438 W JP 2014067438W WO 2016001991 A1 WO2016001991 A1 WO 2016001991A1
Authority
WO
WIPO (PCT)
Prior art keywords
gram
appearance
search
character
character string
Prior art date
Application number
PCT/JP2014/067438
Other languages
English (en)
French (fr)
Inventor
菅谷　奈津子
岐勇 飯島
敦 畠山
Original Assignee
株式会社日立製作所
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 株式会社日立製作所 filed Critical 株式会社日立製作所
Priority to US15/122,780 priority Critical patent/US10394870B2/en
Priority to JP2016530714A priority patent/JP6212639B2/ja
Priority to PCT/JP2014/067438 priority patent/WO2016001991A1/ja
Publication of WO2016001991A1 publication Critical patent/WO2016001991A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/35—Clustering; Classification
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/903—Querying
    • G06F16/90335—Query processing
    • G06F16/90344—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/93—Document management systems

Definitions

  • the present invention relates to a search method.
  • Acceleration of database search is important in order to acquire necessary data in a database in a short time. Further, for example, analysis using big data existing on the Internet is required to be able to search a very large amount of data at high speed.
  • Patent Document 1 creates an index (descriptor table) of appearance character positions for all three characters such as “abc” and “bcd” from the search target text.
  • index descriptor table
  • a technique for searching for an adjacent character position of the index “abc” and the character position of the index “bcd” is disclosed (paragraphs 0002 to 0009). 2 and 4).
  • Such a technique is known as an n-gram method (a 3-gram method in the case of three characters).
  • Patent Document 1 If the technology disclosed in Patent Document 1 is used, the entire text can be searched faster than searching from the beginning one character at a time. However, no technology related to speeding up search across a plurality of indexes is disclosed.
  • an object of the present invention is to speed up a search in a search across a plurality of indexes, that is, a search using a plurality of decomposed search keys.
  • a representative search method is a computer character string search method for searching a document using a specified character string, wherein the specified character string is a first character or character string and a second character or character.
  • the present invention it is possible to speed up the search in a search across a plurality of indexes, that is, a search using a plurality of decomposed search keys.
  • a computer is a general computer having a CPU (processor) and a memory, and the CPU executes processing using data stored in the memory in accordance with a program stored in the memory. For this reason, in the description below that uses the computer as the subject, the subject may be replaced with a CPU.
  • the configuration of the computer is not limited to the above, but an example of a specific configuration will be described later with reference to FIG.
  • the computer can also be regarded as a search device for executing the search.
  • FIG. 1 is a diagram showing an example of n-gram text search using an n-gram appearance list.
  • the computer creates an n-gram node 11, an n-gram appearance list 12, 13 and n-gram indexes 14 to 17 in advance before starting the search.
  • the n-gram node 11 is a table that associates n characters with a pointer (pt).
  • n characters are 2 characters, and all 2 characters included in the search target text are listed.
  • N-gram indexes 14 and 16 are tables for enumerating character positions where “FO” appears in the search target text.
  • the position of the character used as a reference in “FO” may be, for example, the position “F” or the position “O”.
  • the reference character position in “OT” is “O”.
  • N-gram indexes 14, 16 include ID.
  • IDs may be assigned to such items and paragraphs, and the text An ID may be given to a group of multiple lines.
  • the character position is a relative position from the beginning of the text specified by the ID.
  • n-gram indexes 15 and 17 are tables for enumerating character positions where “OT” appears in the search target text, and the configuration of the tables is the same as that of the n-gram indexes 14 and 16.
  • the n-gram appearance list 12 is a table indicating whether “FO” exists in the ID range.
  • Each pointer (pt) becomes a pointer to the n-gram index 14, 16 when “FO” exists in the corresponding ID range, and when “FO” does not exist in the corresponding ID range, Become.
  • the predetermined value in the case where “FO” does not exist is a value that does not become a pointer to any n-gram index, and may be null or zero, for example, and is represented by diagonal lines in FIG.
  • pointers corresponding to ID ranges 1 to 100 and 201 to 300 in the n-gram appearance list 12 are n.
  • Pointer to -gram index 14 and n-gram index 16. “FO” does not exist in the ID range 101-200.
  • the n-gram appearance list 13 is a table indicating whether or not “OT” exists in the ID range, and the configuration of the table is the same as the n-gram appearance list 13.
  • each value of the ID range of the n-gram appearance list 12 and each value of the ID range of the n-gram appearance list 13 are all the same.
  • 100 is a unit, which is 1 to 100, 101 to 200, 201 to 300, and the like. Since each value of the ID range is the same in different n-gram appearance lists, either “FO” or “OT” does not exist in both the ID ranges 101 to 200 and 201 to 300, and “FOOT” Can be determined not to exist.
  • the computer sets each value of the ID range of all the n-gram appearance lists including the n-gram appearance lists such as “AB” (not shown) and the n-gram appearance lists 12 and 13 to be the same.
  • the n-gram index is configured so that the pointer from the n-gram appearance list to the n-gram index corresponds to the ID value of the n-gram index.
  • the n-gram index so that the pointer corresponding to the ID range 1 to 100 in the n-gram appearance list 12 includes 52, 73, and 89 whose ID values are 1 to 100. Make 14 a group.
  • the table is described as a table.
  • the data structure is not limited to the table, and any data structure other than the table may be used as long as it can be managed in the same way.
  • the structure that appears to be corresponding or grouped in FIG. 1 is not limited to a structure in which memory addresses are adjacent to each other.
  • the computer searches the n-gram, here, 2-gram, and decomposes it into “FO” and “OT” as the search key 19. Then, the computer searches each of “FO” and “OT” with n characters of the n-gram node 11. When each of “FO” and “OT” is found, the computer follows the pointers corresponding to “FO” and “OT”, and acquires the n-gram appearance list 12 and the n-gram appearance list 13.
  • the calculator follows these pointers in both the n-gram appearance list 12 and the n-gram appearance list 13 to indicate that the pointers corresponding to ID ranges 1 to 100 are “FO” and “OT”.
  • the computer collates IDs whose values match in both the n-gram index 14 and the n-gram index 15, and collates the adjacent character positions of the IDs found in the collation.
  • the calculator finds that the ID value is 52 and matches, and the character position value is 37 and 39 and finds the adjacent character position.
  • the character position of “F” is 37
  • the character position of “O” of “FO” is 38
  • the character position of “O” of “OT” is 39. Since the ID position value 52 and the matching character position values 122 and 125 are not adjacent to the character position, the computer advances the collation target next.
  • the calculator finds that the ID value matches 73. Since the character position values 1 and 26 are not adjacent to the character position, the computer advances the object of collation to the next character position value of the n-gram index 14 having the smaller character position value, and the character position value is 24. And 26 find the adjacent character position. Since the remaining value of the character position whose ID value is 73 is not adjacent to the character position, the computer advances the collation target next. Since the ID values 89 and 95 do not match and there is no “OT” in the ID value 89, the computer continues until the ID value becomes 95 or higher in the n-gram index 14 where the ID value is small. Proceed with the ID to be matched.
  • next ID value of the n-gram index 14 (not shown) is found to match at 95, the process proceeds to the collation of the character position value. If the next ID value is greater than 95, the ID value The collation target is advanced to the next ID in the n-gram index 15 until the above is reached. In this way, the computer sets all the IDs of both the n-gram index 14 and the n-gram index 15 as collation targets.
  • the processing using two n-gram appearance lists has been described, when the search word 18 is 5 characters or more and the search key 19 is 3 or more, the same number n as the number of the search keys 19 Only when the pointers corresponding to the same ID range are present in all of the -gram appearance lists, the n-gram index may be set as a collation target.
  • the calculator can find the adjacent character positions of “FO” and “OT” and perform text search for “FOOT”, and n-gram indexes 16, 17 based on the n-gram appearance lists 12 and 13 Can be reduced and the search processing including matching can be reduced, so that text search can be speeded up.
  • FIG. 2 is a diagram showing an example of hierarchizing the n-gram appearance list based on the ID range.
  • the search word 18, the search key 19, the n-gram node 11, and the n-gram appearance lists 12 and 13 are the same as those described with reference to FIG.
  • the pointer of the n-gram appearance list is not an n-gram index but an n-gram subgroup appearance list.
  • the data structure of the n-gram subgroup appearance list 21 is the same as that described using the n-gram appearance list 12, and is a table indicating whether “FO” exists in the ID range. -The value of ID range is different from the gram appearance list 12.
  • the data structure of the n-gram subgroup appearance list 22 is the same as that described using the n-gram appearance list 13, and is a table indicating whether “OT” exists in the ID range. -The value of ID range is different from the gram appearance list 13.
  • Each value in the ID range of the n-gram subgroup appearance list 21 and each value in the ID range of the n-gram subgroup appearance list 22 are all the same. In the example shown in FIG. 2, the ID range is 10 units, 1 to 10, 11 to 20, 21 to 30. . . 91-100.
  • the n-gram index not shown in FIG. 2 includes the same information as described with reference to FIG. Since both the n-gram index 14 and the n-gram index 15 include the ID value 52, both the n-gram subgroup appearance list 21 and the n-gram subgroup appearance list 22 have ID range values 51 to 51 Pointers corresponding to 60 indicate the presence of “FO” and “OT”. On the other hand, “OT” does not exist when the ID range is 81 to 90, and the pointer corresponding to the ID range 81 to 90 in the n-gram subgroup appearance list 22 is a predetermined value when “OT” does not exist. It is.
  • the computer indicates that the pointers corresponding to ID ranges 1 to 100 in both the n-gram appearance list 12 and the n-gram appearance list 13 indicate “FO” and “OT”.
  • the pointer follows the pointer.
  • an n-gram subgroup appearance list 21 and an n-gram subgroup appearance list 22 are acquired.
  • the pointer corresponding to the ID range 1 to 10 indicates that neither “FO” nor “OT” exists.
  • the verification target is advanced.
  • the pointer corresponding to the ID range 51 to 60 indicates the presence of both “FO” and “OT”, so the computer follows the pointer and the n-gram index 14 Check n-gram index 15.
  • the calculator sets the ID ranges of both the n-gram subgroup appearance list 21 and the n-gram subgroup appearance list 22 Advances the collation target to 61-70.
  • the pointer corresponding to the ID range 81 to 90 in the n-gram subgroup appearance list 21 indicates the presence of “FO”, but the n-gram subgroup appearance list 22 Since the pointer corresponding to the ID range 81 to 90 indicates that “OT” does not exist, the computer advances the collation target to the next without following the pointer.
  • the pointers corresponding to the ID ranges 101 to 200 and 201 to 300 in the n-gram appearance list 12 and the n-gram appearance list 13 indicate that either “FO” or “OT” does not exist.
  • the calculator does not follow these pointers. For this reason, the computer does not acquire both the n-gram subgroup appearance list 23 and the n-gram subgroup appearance list 24, and does not process it.
  • the n-gram appearance list and the n-gram subgroup appearance list have two hierarchies.
  • the ID range may be grouped into more hierarchies.
  • the computer does not target 81 to 90 including the 89 ID value of the n-gram index 14 based on the n-gram subgroup appearance lists 21 and 22 and can further reduce the search processing. This makes it possible to speed up text search.
  • FIG. 3 is a diagram showing an example of scanning text instead of the n-gram index.
  • reading such as search target text is managed in units of pages, and the CPU reads a specific page by specifying a page number.
  • the capacity of one page is, for example, a capacity that can be read by one read, and is, for example, 8 KB (kilobytes).
  • a computer OS operating system
  • a file system collectively manages a predetermined capacity called a cluster size as a read unit
  • the page capacity may be a cluster size.
  • an application program such as a database manages a predetermined capacity collectively as a read unit
  • the page capacity may be a capacity managed by the application program.
  • the search word 18, the search key 19, and the n-gram node 11 shown in FIG. 3 are the same as those described with reference to FIG.
  • the n-gram appearance list 31 includes page numbers and information on the presence / absence of “FO” on each page.
  • the n-gram appearance list 32 includes page numbers and information on the presence / absence of “OT” on each page.
  • the page numbers in the n-gram appearance list 31 correspond to the page numbers in the n-gram appearance list 32, and the capacity of the same page number is the same.
  • the ID range is illustrated to explain the correspondence between the page numbers, and is not necessary as the contents of the n-gram appearance lists 31 and 32.
  • Page 33 is a scan target that is read by designating page number 1, and includes scan targets with IDs of 01 to 15.
  • the questionnaire answer is the text to be searched, and page 33 includes the ID, gender, age and questionnaire answer. Since the answer to the questionnaire with ID 03 includes both “FO” and “OT”, whether or not the n-gram appearance list 31 appears and the n-gram appearance list 32 appears on page number 1 including ID 03 Both are available.
  • the page 34 is a scan target that is read by designating the page number 2 and has the same structure as the page 33. The answer to the questionnaire on page 34 does not include “OT”, and the answer to the questionnaire whose ID is 16 includes “FO”. The presence / absence of Listing 32 is none.
  • Page 35 and page 36 are also scan targets to be read by designating page number 3 and page number 40, respectively, and have the same structure as page 33. Since the answer to the questionnaire on page 35 does not include “FO” and the answer to the questionnaire with ID 33 includes “OT”, the n-gram appearance list 31 does not appear on page 3 and the n-gram appears. The presence or absence of the appearance of the list 32 becomes yes. Since the answer to the questionnaire with ID 79 includes both “OT” and “FO”, whether or not the n-gram appearance list 31 appears and whether or not the n-gram appearance list 32 appears in the page number 40 including the ID 79 Both are available.
  • the computer acquires the n-gram appearance list 31 and the n-gram appearance list 32 by the same process as described with reference to FIG. Since page number 1 has both occurrences of n-gram appearance list 31 and n-gram appearance list 32, the computer designates page number 1 and leads page 33 to answer the questionnaire. to scan. In order to scan, the computer obtains the ID, gender, and age of the ID of page 33 that has been read, and scans with the search term 18 “FOOT” in the questionnaire response text. This scanning process may be a process of determining whether or not each character matches.
  • the computer finishes scanning the questionnaire response with ID 01, it advances the scan target to ID 02.
  • the scan target further advances to ID 03, the computer finds “FOOT” in “FOOTBALL”.
  • the computer determines whether page number 2 appears in both the n-gram appearance list 31 and the n-gram appearance list 32. In this example, since there is no appearance of the n-gram appearance list 32, the computer proceeds to the determination of the appearance of the page number 3 without setting the page 34 as a scan target. Since there is no appearance of the n-gram appearance list 31 at the page number 3, the computer proceeds to the determination of the appearance of the page number 4 without setting the page 35 as a scan target.
  • the calculator does not scan pages 34 and 35 based on the n-gram appearance lists 31 and 32, and can reduce the search process, so it scans text instead of n-gram index. Can also speed up text search. Further, since the presence / absence of the occurrence of a character string that matches the search key is managed on the page that is the unit of read, the computer does not perform a read that does not include the character string that matches the individual search key.
  • FIG. 4 is a diagram showing an example in which questionnaire responses are separated.
  • the search word 18, the search key 19, and the n-gram node 11 are the same as those described with reference to FIG.
  • the n-gram appearance list 41 has the same structure as the n-gram appearance list 31 described with reference to FIG. 3 and includes a page number and information on the presence / absence of “FO” on each page, but corresponds to one page. The ID range is different.
  • the n-gram appearance list 42 also has the same structure as the n-gram appearance list 32, and includes the page number and information about the presence / absence of “OT” on each page, but the ID range corresponding to one page is different. .
  • Page 43 is information that is read by designating page number 1 and includes information with IDs 01-20.
  • Page 43 includes an ID, gender, age, and a pointer (pt) to the questionnaire response.
  • This pointer may include the page number in which the questionnaire response is included and the character position in the page of the first character of each questionnaire response text.
  • the correspondence between IDs and questionnaire responses is the same as that of pages 33 and 34 shown in FIG.
  • each page can include the same amount of ID range information.
  • the ID range of page number 1 is 15 IDs of 1 to 15, and the ID range of page number 2 is 6 IDs of 16 to 21.
  • the ID range of page number 1 and the ID range of page number 2 are 20 IDs.
  • Page 44 is a scan target that is read by designating page number 5, and includes the text of the questionnaire response. Since the page 44 does not include anything other than questionnaire responses, the page 44 can include more questionnaire responses than the page 33 even if the page 44 has the same capacity. Pages 45 to 48 have the same structure as pages 43 and 44. In the example shown in FIG. 4, the questionnaire response corresponding to the ID of page 43 is present on page 44, but the answer is not limited to such a state. Depending on the page capacity and text capacity, page 43 In some cases, part of the questionnaire response corresponding to the ID is divided into page 44 and page 46. In addition, a questionnaire response corresponding to a part of the IDs of the page 45 and a questionnaire response corresponding to a part of the IDs of the page 47 may be collected on one page 46.
  • the computer reads the page 43, follows the pointer in the page 43, reads the page 44, and sets the questionnaire response as the scan target.
  • FIG. 5 is a diagram showing an example in which an n-gram node has a tree structure.
  • the search word 18, the search key 19, and the n-gram appearance lists 12 and 13 are the same as those described with reference to FIG.
  • the example of the n-gram node shown in FIG. 5 is a tree structure, and the first layer n-gram node 51 serving as the root (root), the second layer n-gram node 52, and the third layer serving as the leaf (leaf). It consists of n-gram nodes 53 in the layer.
  • the n-gram node 53 has the same contents as the n-gram node 11 and includes n characters (2 characters) and a pointer to an n-gram index corresponding to the n characters.
  • the n-gram node 52 includes a pointer to the n-gram node 53.
  • the pointer in which the n characters of the n-gram node 52 correspond to “AE” is the pointer to which the n characters of the n-gram node 53 are “AB”, “AC”, and “AE”.
  • the pointers shown in FIG. 5 are represented by arrows to “AB” on behalf of “AB”, “AC”, and “AE”.
  • a pointer whose n-gram node 52 has n characters corresponding to “BR” is a pointer to n-gram node 53 whose n characters are “BE”, “BI”, and “BR”.
  • the pointer whose n character corresponds to “OT” is a pointer where the n character of the n-gram node 53 is “FO”, “GO”, or “OT”.
  • the pointer in which the n character of the n-gram node 51 corresponds to “BR” is a pointer to the n character including “AE” and “BR” of the n-gram node 52, and the n character of the n-gram node 51 is “
  • the pointer corresponding to “SV” is a pointer to n characters including “OT” and “SV” of the n-gram node 52.
  • the n character positioned between “BR” and “SV” exists ahead of the pointer corresponding to “SV”, and the n character positioned between “AE” and “BR” is “BR”.
  • each of the “FO” and “OT” is searched from the n-gram node 51.
  • the calculator compares the search key 19 “FO” with the n-letter “BR” and compares it with the n-letter “SV” to determine that “FO” is located between “BR” and “SV”. .
  • the computer follows the pointer corresponding to “SV” and obtains n characters including “OT” and “SV” of the n-gram node 52.
  • the calculator compares “FO” of the search key 19 with “OT” of n characters of the n-gram node 52, and “FO” exists in the direction of “BR” rather than “OT”, that is, “FO” is “ Judged to be located between “OT” and “BR”.
  • the computer follows the pointer corresponding to “OT”, finds “FO” of the n-gram node 53, follows the pointer corresponding to “FO”, and obtains the n-gram appearance list 12.
  • the subsequent processing is the same as the processing already described with reference to FIG. Similarly, for the search key 19 “OT”, the pointer corresponding to “SV” of the n-gram node 51 is traced, the pointer corresponding to “OT” of the n-gram node 52 is traced, and the n-gram node 53 Find “OT” and follow the pointer corresponding to “OT” to obtain the n-gram appearance list 13.
  • the computer uses the n-gram node 11 shown in FIG. 1 to search for the search keys 19 one by one in the order of “AB”, “AC”, “AE”, “BE”, etc.
  • the number of comparisons is less when the tree-structured n-gram node shown in FIG. 5 is used than when compared and searched, and n characters matching the search key 19 can be found in a short time. Since the number of comparisons increases when the number of levels in the tree structure is large, the number of comparisons decreases when the number of levels is uniform and small. For this reason, a so-called balanced tree structure is preferred.
  • the computer can acquire the n-gram appearance list in a short time from the start of the search by the tree-structured n-gram node.
  • the n-gram appearance list can be used even if the n-gram node has a tree structure, the speed-up effect described with reference to FIG. 1 and the like can be obtained.
  • the tree structure of n-gram nodes in which the same n characters are arranged in each layer that is, the n-gram nodes 51, 52, and 53 are described as a tree structure including “BR”.
  • FIG. 6 is a diagram showing an example of search using B-tree.
  • the appearance list described above can be used not only for text search but also for search using B-tree.
  • the search target table 61 includes values for the four items of ID, C1, C2, and C3, and is a table in which ID values that match the values of the respective items of C1, C2, and C3 are searched.
  • the computer expands the C1 B-tree node, the C2 B-tree node, and the C3 B-tree node (not shown) from the search target table 61 before starting the search.
  • the B-tree node has a general B-tree structure, description of the structure itself is omitted.
  • Each value of the B-tree node shown in Fig. 6 corresponds to the value of C1 or C3.
  • the pointer from the B-tree node to the B-tree appearance lists 62 and 63 is information for specifying the ID value, but a plurality of ID values correspond to one value of C1 in the search target table 61. .
  • C1 corresponds to a value of 12.
  • the B-tree appearance lists 62 and 63 include an ID range and a pointer (pt). That is, the B-tree appearance lists 62 and 63 have pointers to the existing B-tree indexes 64 to 67 when IDs within the ID range exist. Further, the B-tree appearance lists 62 and 63 have, as pointer values, predetermined values indicating that they do not exist when there is no ID within the ID range.
  • each value of the ID range of the B-tree appearance list 62 and each value of the ID range of the B-tree appearance list 63 are the same.
  • the B-tree indexes 64 and 66 list the ID values of the search target table 61 when the value of C1 is 12, and the B-tree index 64 has an ID value in the range of 1 to 10.
  • the B-tree index 66 includes IDs in the range of 21-30. Here, there is no ID in the range of 11-20.
  • the B-tree indexes 65 and 67 list the ID values of the search target table 61 when the value of C3 is 32.
  • the B-tree index 65 has an ID value in the range of 1 to 10.
  • the B-tree index 67 includes ID values in the range of 11-20.
  • the computer expands the search target table 61 to B-tree nodes, creates B-tree indexes 64 to 67, creates B-tree appearance lists 62 and 63, and connects them with pointers.
  • the computer converts the search condition 68 into a search key 69.
  • the search condition 68 is an AND condition that the value of C1 is 12 and that the value of C3 is 32. Therefore, the search key 69 is converted into 12 which is the value of C1 and 32 which is the value of C3. Then, an ID whose C1 value matches the value 12 of the search key 69 is searched, and an ID whose C3 value matches the value 32 of the search key 69 is searched.
  • the computer Since the value 12 of the search key 69 is 50 or less in the B-tree node of C1 and matches the value 12, the computer acquires the B-tree appearance list 62. Further, since the value 32 of the search key 69 is the value 52 or less in the B-tree node of C3 and is the value 35 or less and matches the value 32, the computer acquires the B-tree appearance list 63. As described above, each value in the ID range of the B-tree appearance list 62 and each value in the ID range of the B-tree appearance list 63 are the same. The computer determines that the ID exists in both the B-tree appearance list 62 and the B-tree appearance list 63 in the ID range 1 to 10, and follows the pointers to obtain the B-tree index 64 and the B-tree index 65, respectively. .
  • the computer first compares the first ID 1 of the B-tree index 64 with the first ID 3 of the B-tree index 65, and these ID values do not match and the ID value of the B-tree index 64 is small. Then, the collation target of the B-tree index 64, that is, the comparison target is advanced. The computer compares the ID 3 of the B-tree index 64 with the ID 3 of the B-tree index 65, and since these ID values match, it finds 3 as the ID value satisfying the search condition 68.
  • the computer advances the collation target and compares ID 8 of B-tree index 64 with ID 5 of B-tree index 65, and these ID values do not match, and B-tree index 64 and B-tree Since it is the end of the index 65, the collation target in the B-tree appearance list 62 and the B-tree appearance list 63 is advanced to the ID range 11-20.
  • the computer determines from the pointers corresponding to the ID ranges 11 to 20 in the B-tree appearance list 62 that there is no ID in the ID ranges 11 to 20, and the pointers corresponding to the ID ranges 11 to 20 in the B-tree appearance list 63 It is determined that the search condition 68 is not satisfied without using the previous B-tree index 67 as a comparison target. Further, the computer advances the collation target in the B-tree appearance list 62 and the B-tree appearance list 63 to the ID ranges 21 to 30.
  • the computer determines from the pointers corresponding to the ID ranges 21 to 30 in the B-tree appearance list 63 that there is no ID in the ID ranges 21 to 30, and the pointers corresponding to the ID ranges 21 to 30 in the B-tree appearance list 62 It is determined that the search condition 68 is not satisfied without using the previous B-tree index 66 as a comparison target.
  • the computer does not target B-tree indexes 66 and 67 based on the B-tree appearance list, and the search processing can be reduced. Speed can be increased.
  • FIG. 7 is a diagram showing an example of a file system.
  • Some computer OSs or file systems manage directories and files using i-nodes.
  • the directory is also a file and is managed as a data block in the data area.
  • a plurality of i-nodes are listed to form an i-node list.
  • the i-node 76 includes a pointer to the root directory 710, and each directory and each file in the root directory 710 includes a pointer to the i-node.
  • the directory name home of the root directory 710 has a pointer to the i node 77, and the i node 77 has a pointer to the / home directory 711.
  • the directory name src of the / home directory 711 has a pointer to the i node 78, and the i node 78 has a pointer to the / home / src directory 712.
  • the file name test.c in the / home / src directory 712 has a pointer to the i-node 79, and the i-node 79 has a pointer to the test.c file 713. In this way, the test.c file 713 can be reached from the root directory 710 and the test.c file 713 can be accessed.
  • the i-node list is grouped, and each grouped i-node list is managed by a list number. Similar to the explanation using FIG. 3, the unit of the group in the i-node list is preferably a unit of one read. Then, the presence / absence of a search key is managed for each list number in the appearance list. Since a plurality of appearance lists have the same list number, the same grouped i-node list is managed.
  • the search key “main” exists in the data block ahead of the pointer included in the two i-node lists, i-node list 73 managed by list number 1 and i-node list 74 managed by list number 2. Therefore, the column of presence / absence of the list numbers 1 and 2 in the appearance list 71 becomes null.
  • the appearance of the list number 3 in the appearance list 71 The presence / absence column is “Yes”. The same applies to the appearance list 72 of “src”.
  • the computer When searching for a data block such as a directory or a file including both “main” and “src” search keys, the computer first displays the presence / absence column of the list number 1 in the appearance list 71 and the list number 1 in the appearance list 72. It is determined that both the presence / absence column is absent. That is, since the computer can determine that there are neither “main” nor “src” ahead of the pointer included in the i-node list 73 of list number 1, the i-node list 73 is not targeted for search, and list number 2 Proceed to The computer determines that the presence / absence column of list number 2 in the appearance list 72 is present, but the presence / absence column of list number 2 in the appearance list 71 is absent. For this reason, the computer does not set the i-node list 74 as a search target and proceeds to the list 3.
  • a data block such as a directory or a file including both “main” and “src” search keys
  • the computer determines that the appearance presence / absence column of list number 3 in both the appearance list 71 and the appearance list 72 is present. At this time, it is unclear which i-node pointer of the i-node list 75 managed by the list number 3 has “main” and “src”. Therefore, the computer scans which i-node pointer in the i-node list 75 contains “main” and “src”. The computer obtains the / home / src directory 712 that is the pointer of the i-node 78 and scans “main” and “src”. Further, the computer obtains the test.c file 713 ahead of the pointer of the i-node 79 and scans “main” and “src”. In this example, the computer finds “main” and “open” in the test.c file 713.
  • the i-node lists 73 and 74, the root directory 710, and the / home directory 711 are not scanned based on the appearance lists 71 and 72, and the search processing can be reduced. Can search for files faster.
  • FIG. 8 is a diagram showing an example of the configuration of a computer.
  • the computer has two CPUs, CPU-A81 and CPU-B82, and the two CPUs can execute processing independently.
  • a dedicated cache A83 is connected to CPU-A81
  • a dedicated cache B84 is connected to CPU-B82.
  • the computer has a cache C85 shared by CPU-A81 and CPU-B82, and has a memory 86 and a storage device 87 such as an HDD (hard disk drive) or an SSD (solid state drive). These have different access performance and storage capacity, and the access performance of cache A83 and cache B84 is the highest and the storage capacity is the lowest.
  • Cache C85 has the second highest access performance and the second smallest storage capacity.
  • the access performance of the memory 86 is the third highest and the storage capacity is the third lowest.
  • the access performance of the storage device 87 is the fourth highest and the storage capacity is the fourth lowest.
  • Appearance list that is, n-gram appearance lists 12, 13, 21-24, 31, 32, 41, 42, B-tree appearance lists 62, 63, and appearance lists 71, 72 have search keys within a predetermined range
  • information other than the appearance list may not be processed, but all information in the appearance list is processed. Therefore, storing the appearance list in the cache has the effect of speeding up the search process. Get higher.
  • the text occupies a large storage capacity, so the page is stored in the storage device 87, and the page that is read based on the appearance list is reduced.
  • the number of accesses to the device 87 is reduced, and the effect of speeding up the search process is enhanced.
  • a plurality of appearance lists in the hierarchy may be processed in parallel by different CPUs.
  • the n-gram subgroup appearance lists 21 and 22 shown in FIG. 2 are stored in the cache A83 and processed by the CPU-A81.
  • the n-gram subgroup appearance list in which the pointer exists in the same ID range of both the n-gram appearance lists 12 and 13 (not shown) is stored in the cache B84 and processed by the CPU-B82.
  • the two n-gram subgroup appearance lists can be processed in parallel by the two CPU-A81 and CPU-B82.
  • different ID ranges in the appearance list are independent, different ID ranges may be processed in parallel by different CPUs.
  • the ID ranges 1 to 100 of both the n-gram appearance lists 12 and 13 are stored in the cache A83 and processed by the CPU-A81.
  • the ID ranges 101 to 200 of both the n-gram appearance lists 12 and 13 are stored in the cache B84 and processed by the CPU-B82.
  • the different ID ranges of the n-gram subgroup appearance lists may be processed by different CPUs, and the different page numbers of the n-gram appearance lists 31 and 32 may be processed by different CPUs.
  • the appearance list is stored in the cache C85 or the memory 86 and is shared by the CPU-A81 and CPU-B82 so that they can be processed in parallel by different CPUs. May be.
  • the questionnaire response text on different pages may be scanned in parallel by different CPUs.
  • CPU-A 81 may scan page 33 with page number 1 shown in FIG. 3, and CPU-A 82 may scan page 36 with page number 40.
  • FIG. 8 shows an example in which the computer has two CPUs and three caches. However, the present invention is not limited to this, and the computer may have three or more CPUs. You may have.
  • the computer has an input / output IF (interface) 88 that connects a display, a keyboard, and a mouse (not shown), and a network IF 89 that connects to a network (not shown).
  • the computer may receive setting information for processing the search via the input / output IF 88, and the search result may be output from the input / output IF 88 and displayed on the display. Further, the computer may receive the setting information via the network IF 89 and output the search result. Further, search target data such as text and ID and a program to be executed for the search may be received by the network IF 89.
  • FIG. 9 is a diagram showing an example of a processing flow for creating an appearance list.
  • the appearance list may be created when creating an n-gram node, B-tree node, or i-node before starting the search, or an n-gram node and n-gram index or a B-tree node and B-tree index are created in advance.
  • the search may be started and may be created at the time of the first search.
  • an appearance list is created together with a node before the search is started will be described.
  • the computer determines the group creation unit in step 91.
  • 100 ID ranges are one group
  • in FIG. 3 one page is one group
  • 10 ID ranges are one group.
  • a user input value may be used, or a read unit such as a page may be obtained from parameters of the OS or the file system.
  • the computer proceeds to step 93 by setting the steps from step 92 to step 911 as the loop range and the number of groups as the number of loops.
  • the computer acquires data of one group in step 93.
  • one group is a group of units determined in step 91, and is changed to another group each time a loop is executed.
  • the data is ID of the page 33, etc. in the text search of FIGS. 3 and 4, gender, age, questionnaire response (text), the search target table 61 in the ID search of FIG. 6, and the data in the file system search of FIG. It is a block.
  • step 94 the computer acquires all IDs from the data acquired in step 93. 1 are all IDs included in, for example, 1 to 100 in FIG. 1 and are 52, 73, 89, 95, etc., for example, are 1 to 15 in FIG. 3, and are included in, for example, 1 to 10 in FIG. 1 to 3, 5, 8, etc.
  • the computer sets the steps from step 95 to step 910 as the loop range, and proceeds to step 96 with the number of IDs acquired in step 94 as the number of loops.
  • step 96 the computer obtains all n characters in the text corresponding to one ID or a value corresponding to one ID.
  • one ID is sequentially changed to another ID every time the loop is executed.
  • all n characters in the text corresponding to the ID 01 are all two characters such as “OU”, “UT”, and “TD” from the answer text of the questionnaire.
  • the values corresponding to ID 1 are 12 of C1, aaa of C2, and 78 of C3.
  • step 97 the computer registers all the n characters or values acquired in step 96 in the n-gram node or B-tree node, and creates the n-gram node or B-tree node.
  • step 98 the computer registers the ID and all character positions as necessary in the index. That is, when the ID value is 52 in step 96, the computer registers the ID value 52 in the n-gram indexes 14 and 15 in FIG. 1, and the character positions 37 and 122 and the character position 39 are associated with this ID value. And 125 are registered. If the ID value is 1 in step 96, the computer registers the ID value 1 in the B-tree index 64 in FIG. 6, and C2 is the B-tree index corresponding to aaa and C3 is 78. ID value 1 is registered in the B-tree index corresponding to.
  • step 99 when the computer registers a new n character or new value in step 98, the computer creates an appearance list for the registered new n character or new value, and creates the appearance list or the already generated appearance list. Register pointer to index or information about presence or absence.
  • the computer calculates the number of groups including the ID range from 1 to 100 as well as 101 or later for the new n character “FO” whose ID value is 52 in FIG. Create an n-gram appearance list 12 with numbers.
  • the computer registers the n-gram appearance list 12 to the pointer corresponding to the n character “FO” of the n-gram node 11, and the n-gram appearance list 12 has an ID range of 1 to 100 to the pointer corresponding to the n-gram appearance list 12.
  • Register gram index 14 The computer sets a predetermined value when “FO” does not exist in the pointer whose ID range in the n-gram appearance list is 101 or later.
  • the computer registers the n-gram index 16 to the pointer corresponding to the ID range 201 to 300 of the existing n-gram appearance list 12 for the non-new n character “FO” whose ID value is 203. . Since “FO” does not exist in the ID range 101 to 200, the ID range 101 to 200 in the n-gram appearance list 12 maintains a predetermined value when “FO” set at the time of creation does not exist.
  • an n-gram node or B-tree node and an n-gram index or B-tree index can be created, and an n-gram appearance list or B-tree appearance list can be created. Since the text scan shown in FIGS. 3 and 4 and the file system shown in FIG. 7 do not have an index or the like, the computer need not execute unnecessary steps.
  • FIG. 10 is a diagram showing an example of a search processing flow using the appearance list.
  • the computer converts the search term 18 as a search condition into the search key 19, or converts the search condition 68 into the search key 69.
  • the computer searches for an n-gram node or a B-tree node with a search key, acquires a pointer corresponding to the n character string or value found with the search key, and acquires an appearance list with the acquired pointer. That is, in FIG. 1, the computer finds the n character “FO” of the n-gram node 11 with respect to “FO” of the search key 19 and uses the pointer corresponding to the n character “FO” to display the n-gram appearance list 12. To get. In FIG. 6, the computer finds the value 12 of the B-tree node of C1 with respect to the value 12 of the search key 69, and acquires the B-tree appearance list 62 using the pointer corresponding to the value 12.
  • the computer proceeds from step 103 to step 107 with the range of the loop as the loop range, and the number of groups in the appearance list acquired at step 102 as the number of loops to step 104.
  • the number of groups is the number of items in the ID range of 1 to 100, 101 to 200, and 201 to 300 in the n-gram appearance list 12 of FIG. 1, and the n-gram appearance list of FIG.
  • the number of items of 31 page numbers is 40.
  • step 104 the computer obtains all occurrence / non-occurrence information of one group or a pointer indicating the occurrence / absence from the occurrence list.
  • one group is changed to another group each time a loop is executed.
  • All the appearance information of one group is, for example, appearance information corresponding to page number 1 in the n-gram appearance list 31 in FIG. 3 and appearance information corresponding to page number 1 in the n-gram appearance list 32 in FIG. That is, it is the presence / absence information of all the plurality of n-gram appearance lists of one group of page number 1.
  • the pointers indicating the presence / absence of all occurrences of one group correspond to, for example, the pointer corresponding to the ID range 1 to 100 in the n-gram appearance list 12 and the ID range 1 to 100 in the n-gram appearance list 13 in FIG. Pointer. That is, it is a pointer for all the n-gram appearance lists in one group whose ID range is 1 to 100.
  • step 105 the computer determines whether all the presence / absence information acquired in step 104 indicates presence, or whether the acquired pointers indicate all presence. If the computer determines that all are present, the process proceeds to step 106, and a detailed search is performed for one group corresponding to presence / absence information. For example, in FIG. 3, there is one group corresponding to the presence of page number 1, and the computer acquires page 33 with page number 1 and scans “FOOT” from the questionnaire response text included in page 33. .
  • the computer acquires the n-gram index 14 from the pointer corresponding to the ID range 1 to 100 in the n-gram appearance list 12, and n-gram
  • the n-gram index 15 is acquired from the pointer corresponding to the ID range 1 to 100 of the gram appearance list 13, and the ID match and the character position adjacency are collated as already described with reference to FIG.
  • the computer collectively outputs the detailed search results in step 108.
  • step 106 is executed after checking the presence / absence information of all the groups, and when there are many groups having all occurrence / non-occurrence information, that is, when the detailed search takes time. May prompt the user to review the search conditions.
  • FIG. 11 is a diagram showing an example of inputting an appearance list creation parameter.
  • the computer may output the display data of the window 111 from the input / output IF 88 to the display, and accept input of parameters by the keyboard and mouse by the input / output IF 88.
  • another computer connected to the network IF 89 may perform output and input, and the computer may transmit and receive the display data to be output and the input parameters via the network IF 89.
  • the appearance list creation input field 112 is a field for entering settings including a setting for not creating an appearance list, a setting for creating an appearance list before starting a search, and a setting for creating an appearance list at the first search. If a setting for not creating an appearance list is input in this field, the computer does not execute step 99 shown in FIG. 9 and registers the corresponding index in the node. If the setting for creating the appearance list at the first search is input, the computer does not execute step 99, registers the corresponding index to the node, and creates and registers the appearance list at the first search. . When the setting for creating the appearance list before starting the search is input, the computer processes as described with reference to FIG.
  • the search target input column 113 is a column for specifying a search target data file, that is, a target file for generating an appearance list.
  • the name of the text file that is the target of the text search may be specified, or the name of the database that is the target of the search may be specified.
  • the computer obtains data from the file specified in the input field 113 to be searched.
  • the ID unit input column 114 is a column in which the ID described with reference to FIGS.
  • an ID is explicitly included in the file specified in the search target input field 113, for example, there is an ID item in the search target table 61 described with reference to FIG.
  • the unit input field 114 is designated.
  • the item or paragraph input field 114 may be specified as described with reference to FIG.
  • a line of text may be specified as an ID unit.
  • the ID unit input field 114 may be set so that no ID is specified.
  • the group unit input column 115 is a column for specifying a group based on the ID specified in the ID unit input column 114, or specifying that a parameter is acquired from the OS or file system to be a group.
  • a unit 100 is input in the group unit input field 115, and the B-tree appearance lists 62 and 63 described with reference to FIG.
  • the unit 10 is entered in the group unit input field 115.
  • a unit of one read is input from the OS or file system.
  • the designation input in the group unit input field 115 is common to all the appearance lists. This makes it possible to determine whether or not an item found with the search keys 19 and 69 appears for each group.
  • the number-of-hierarchies input field 116 is a field for designating the number of levels in the appearance list.
  • “1” is input in the input column 116 for the number of layers.
  • the computer may determine that the appearance list is one layer if nothing is input.
  • the appearance list has two layers of the n-gram appearance lists 12 and 13 and the n-gram subgroup appearance lists 21 to 24, 2 is input in the input column 116 for the number of layers.
  • an input field for the group unit Increase 115 to 2.
  • 100 for the n-gram appearance list 12 and 10 for the n-gram subgroup appearance lists 21 and 23 are input.
  • a character string may be input, selectable candidates may be listed and displayed, and may be selected by a so-called radio button, or may be selectable by a so-called pull-down menu.
  • the search target data is divided into a plurality of groups, and the same group is managed by a plurality of appearance lists, so that the computer can determine a group that does not need to be searched based on the appearance list. Reduce group processing and speed up searches.
  • n-gram node 12 n-gram appearance list 14-17: n-gram index 18: search word 19, 69: search key 21-24: n-gram subgroup appearance list 62, 63: B- Tree appearance list 64 to 67: B-tree index 68: Search condition

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Linguistics (AREA)
  • Business, Economics & Management (AREA)
  • General Business, Economics & Management (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

　指定された文字列で文献を検索する計算機の文字列検索方法において、前記指定された文字列を第１の文字または文字列と第２の文字または文字列を含む複数の文字または文字列に分解する第１のステップと、前記計算機の１回のリード処理で読み込める単位で複数の文献をグルーピングして複数の集合を作成する第２のステップと、前記複数の集合それぞれにおいて前記第１の文字または文字列が出現するか否かを判定し、出現する集合それぞれに前記第１の文字または文字列の第１の出現情報を付与する第３のステップと、前記複数の集合それぞれにおいて前記第２の文字または文字列が出現するか否かを判定し、出現する集合それぞれに前記第２の文字または文字列の第２の出現情報を付与する第４のステップと、前記複数の集合の中の第１の集合において前記第１の出現情報と前記第２の出現情報が付与されている場合、前記第１の集合を詳細検索対象とする第６のステップと、を有する。

Description

検索方法
本発明は検索方法に関するものである。
　データベースにおいて必要なデータを短時間で取得するために、データベースの検索の高速化が重要である。また、例えばインターネット上などに存在するビッグデータを使用した分析では非常に多量なデータを高速に検索できることが要求されている。
　このような検索の中でテキスト検索の高速化に関し、特許文献１には検索対象テキストから“ａｂｃ”や“ｂｃｄ”など全ての３文字それぞれに対して出現文字位置のインデックス（ディスクリプタテーブル）を作成し、“ａｂｃｄ”を検索語とした場合に“ａｂｃ”のインデックスの出現文字位置と“ｂｃｄ”のインデックスの出現文字位置とが隣接するものを検索する技術が開示されている（段落０００２～０００９、図２、４）。なお、このような技術はn-gram法（３文字の場合は3-gram法）として知られている。
特開平０８－１９４７１８号公報
　特許文献１に開示された技術を使用すれば、テキスト全体を先頭から１文字ずつ検索するより高速に検索できる。しかしながら、複数のインデックスにまたがる検索の高速化に関する技術までは開示されていない。
　そこで、本発明の目的は、複数のインデックスにまたがるような検索すなわち分解された複数の検索キーによる検索において検索を高速化することにある。
　本発明に係る代表的な検索方法は、指定された文字列で文献を検索する計算機の文字列検索方法において、前記指定された文字列を第１の文字または文字列と第２の文字または文字列を含む複数の文字または文字列に分解する第１のステップと、前記計算機の１回のリード処理で読み込める単位で複数の文献をグルーピングして複数の集合を作成する第２のステップと、前記複数の集合それぞれにおいて前記第１の文字または文字列が出現するか否かを判定し、出現する集合それぞれに前記第１の文字または文字列の第１の出現情報を付与する第３のステップと、前記複数の集合それぞれにおいて前記第２の文字または文字列が出現するか否かを判定し、出現する集合それぞれに前記第２の文字または文字列の第２の出現情報を付与する第４のステップと、前記複数の集合の中の第１の集合において前記第１の出現情報と前記第２の出現情報が付与されている場合、前記第１の集合を詳細検索対象とする第６のステップと、を有することを特徴とする。
　本発明によれば、複数のインデックスにまたがるような検索すなわち分解された複数の検索キーによる検索において検索の高速化が可能となる。
n-gram出現リストとインデックスを用いた検索の例を示す図である。 n-gram出現リストを階層化した例を示す図である。 n-gram出現リストとテキストスキャンを用いた検索の例を示す図である。 分離したテキストのスキャンを用いた検索の例を示す図である。 n-gramノードを木構造にした例を示す図である。 B-tree出現リストとインデックスを用いた検索の例を示す図である。 ファイルシステムを用いた検索の例を示す図である。 計算機のハードウェア構成の例を示す図である。 出現リストなどの作成の処理フローの例を示す図である。 出現リストなどを用いた検索の処理フローの例を示す図である。 出現リスト作成パラメタの設定画面の例を示す図である。
　以下に図面を参照しながら好ましい実施例を説明する。以下では計算機の処理として説明する。計算機はCPU（プロセッサ）とメモリを有する一般的なものであり、メモリに格納されたプログラムにしたがってCPUがメモリに格納されたデータを使用して処理を実行する。このため、以下の説明における計算機を主語とする説明は主語をCPUに置き換えてもよい。なお、計算機の構成は上記のものに限定されないが、図８を用いて特定の構成の例を後で説明する。また、計算機は検索を実行するため検索装置と見なすこともできる。
　図１はn-gram出現リストを用いたn-gramテキスト検索の例を示す図である。計算機は検索を開始する前に予めn-gramノード11とn-gram出現リスト12、13とn-gramインデックス14～17を作成しておく。n-gramノード11はｎ文字とポインタ（pt）とを対応付けるテーブルである。ここではｎ文字を２文字とし、検索対象テキストに含まれる全ての２文字が列挙される。また、n-gramノード11に列挙される全てのn文字、例えば「AB」～「BR」などに対応するポインタとn-gram出現リストとn-gramインデックスは存在するが、ここでは図示を省略し、n文字が「FO」と「OT」に対応するものの一部のみを図示する。
　n-gramインデックス14、16は検索対象テキストにおける「FO」の出現する文字位置を列挙するテーブルである。ここで、文字位置がｎ文字の中のどの文字の位置を基準とするかは一定の位置を基準とすればよい。「FO」において基準とする文字の位置は、例えば「F」の位置でもよいし、「O」の位置でもよい。ただし、「F」の位置とした場合、「OT」において基準とする文字の位置は「O」となる。
　n-gramインデックス14、16はIDを含む。例えば特許文献１の図４にも記載されているように、検索対象テキストが項目やパラグラフを含むことは一般的であり、そのような項目やパラグラフなどにIDが付与されてもよいし、テキストの複数行をまとめたものにIDが付与されてもよい。このため、文字位置はIDで特定されるテキストの先頭から相対的な位置である。また、複数のｎ文字が１つのIDにおいて存在する場合、図１に示すように複数の文字位置が１つのIDに対応付けられる。n-gramインデックス15、17は検索対象テキストにおける「OT」の出現する文字位置を列挙するテーブルであり、そのテーブルの構成はn-gramインデックス14、16と同じである。
　n-gram出現リスト12は「FO」がID範囲に存在するか否かを示すテーブルである。各ポインタ（pt）はそれぞれ対応するID範囲に「FO」が存在する場合、n-gramインデックス14、16へのポインタとなり、それぞれ対応するID範囲に「FO」が存在しない場合、所定の値となる。「FO」が存在しない場合の所定の値はいかなるn-gramインデックスへのポインタにもならない値であり、例えばnullやゼロでもよく、図１において斜線で表している。図１に示した例において「FO」はIDが５２、７３、８９、２０３に存在するため、n-gram出現リスト12のID範囲が１～１００と２０１～３００に対応するポインタは、それぞれn-gramインデックス14とn-gramインデックス16へのポインタである。「FO」はID範囲が１０１～２００において存在しない。
　n-gram出現リスト13は「OT」がID範囲に存在するか否かを示すテーブルであり、そのテーブルの構成はn-gram出現リスト13と同じである。ここで、n-gram出現リスト12のID範囲の各値とn-gram出現リスト13のID範囲の各値とは全て同一である。図１に示した例では１００を単位とし、１～１００、１０１～２００、２０１～３００などである。異なるn-gram出現リストにおいてID範囲の各値が同一であるため、ID範囲が１０１～２００と２０１～３００の両方において「FO」と「OT」のどちらか一方は存在せず、「FOOT」は存在しないと判断できる。
　このため、計算機は図示を省略した「AB」などのn-gram出現リストとn-gram出現リスト12、13を含めて全てのn-gram出現リストのID範囲の各値を同一に設定する。また、n-gram出現リストからn-gramインデックスへのポインタがn-gramインデックスのIDの値に対応するように、n-gramインデックスを構成する。図１に示した例では、n-gram出現リスト12のID範囲が１～１００に対応するポインタの先はＩＤの値が１～１００である５２、７３、８９を含むようにn-gramインデックス14を１つのグループにする。
　なお、以上の説明ではテーブルとして説明したが、テーブルにデータ構造を限定するものではなく、テーブル以外のデータ構造であっても、同じ管理の可能なデータ構造であればよい。また、図１において対応したりまとまったりして見える構造もメモリのアドレスが隣接するなどの構造に限定するものではなく、同じ管理の可能な構造であればよい。
　以下では、検索条件である検索語18が「FOOT」の場合の処理の例を説明する。計算機は検索語18として「FOOT」が入力されると、n-gramここでは2-gramにより検索するため、検索キー19として「FO」と「OT」へ分解する。そして、計算機はn-gramノード11のn文字で「FO」と「OT」のそれぞれを検索する。「FO」と「OT」のそれぞれが見つかると、計算機は「FO」と「OT」それぞれに対応したポインタをたどり、n-gram出現リスト12とn-gram出現リスト13を取得する。
　計算機は、n-gram出現リスト12とn-gram出現リスト13の両方においてID範囲の１～１００に対応するポインタが「FO」と「OT」の存在することを示すため、これらのポインタをたどりn-gramインデックス14とn-gramインデックス15を取得する。ID範囲が１０１～２００と２０１～３００に対応するポインタは「FO」と「OT」のどちらか一方の存在しないことを示すため、計算機はこれらのポインタはたどらない。このため、計算機はn-gramインデックス16とn-gramインデックス17の両方を取得せず、処理の対象ともしない。
　計算機は、n-gramインデックス14とn-gramインデックス15の両方で値の一致するIDを照合し、照合で見つかったIDの文字位置が隣接するものを照合する。図１に示した例において、計算機はIDの値が５２で一致することを見つけ、文字位置の値が３７と３９で文字位置の隣接を見つける。「F」の文字位置が３７、「FO」の「O」の文字位置が３８、「OT」の「O」の文字位置が３９である。IDの値が５２で一致する文字位置の値が１２２と１２５は文字位置の隣接ではないので、計算機は次に照合対象を進める。
　計算機はIDの値が７３で一致することを見つける。文字位置の値が１と２６は文字位置の隣接ではないため、計算機は文字位置の値の小さいn-gramインデックス14の次の文字位置の値へ照合対象を進めて、文字位置の値が２４と２６で文字位置の隣接を見つける。IDの値が７３の文字位置の残りの値は文字位置の隣接ではないので、計算機は次に照合対象を進める。IDの値が８９と９５は不一致であり、IDの値が８９には「OT」が存在しないため、計算機はIDの値が小さいn-gramインデックス14においてIDの値が９５以上になるまで次のIDへ照合対象を進める。そして、図示を省略したn-gramインデックス14の次のIDの値が９５で一致することを見つければ文字位置の値の照合へ進み、次のIDの値が９５より大きければ、そのIDの値以上になるまでn-gramインデックス15において次のIDへ照合対象を進める。このようにして、計算機はn-gramインデックス14とn-gramインデックス15の両方の全てのIDを照合対象とする。
　なお、２個のn-gram出現リストを使用した処理を説明したが、検索語18が５文字以上であり、検索キー19が３個以上の場合は、検索キー19の数と同じ個数のn-gram出現リスト全てにおいて同一のID範囲に対応するポインタが存在を示す場合だけ、n-gramインデックスを照合対象にすればよい。
　以上で説明したように、計算機は「FO」と「OT」の文字位置の隣接を見つけて「FOOT」をテキスト検索できるとともに、n-gram出現リスト12、13に基づきn-gramインデックス16、17を照合対象とせず、照合を含む検索処理を減らすことができるため、テキスト検索を高速化できる。
　図２はn-gram出現リストをID範囲に基づき階層化した例を示す図である。検索語18と検索キー19とn-gramノード11とn-gram出現リスト12、13は図１を用いて説明したものと同じである。ただし、n-gram出現リストのポインタの先はn-gramインデックスではなく、n-gramサブグループ出現リストである。n-gramサブグループ出現リスト21のデータ構造はn-gram出現リスト12を用いて説明したものと同じであって、「FO」がID範囲に存在するか否かを示すテーブルであるが、n-gram出現リスト12とはID範囲の値が異なる。
　n-gramサブグループ出現リスト22のデータ構造もn-gram出現リスト13を用いて説明したものと同じであって、「OT」がID範囲に存在するか否かを示すテーブルであるが、n-gram出現リスト13とはID範囲の値が異なる。そして、n-gramサブグループ出現リスト21のID範囲の各値とn-gramサブグループ出現リスト22のID範囲の各値とは全て同一である。図２に示した例でID範囲は１０を単位とし、１～１０、１１～２０、２１～３０．．．９１～１００である。
　図２において図示を省略したn-gramインデックスは図１を用いて説明したものと同じ情報を含む。n-gramインデックス14とn-gramインデックス15の両方はIDの値が５２を含むので、n-gramサブグループ出現リスト21とn-gramサブグループ出現リスト22の両方でID範囲の値が５１～６０に対応するポインタは「FO」と「OT」それぞれの存在を示す。これに対し、ID範囲が８１～９０において「OT」は存在せず、n-gramサブグループ出現リスト22のID範囲が８１～９０に対応するポインタは「OT」が存在しない場合の所定の値である。
　既に説明したとおり、計算機はn-gram出現リスト12とn-gram出現リスト13の両方においてID範囲の１～１００に対応するポインタが「FO」と「OT」の存在することを示すため、これらのポインタをたどる。そして、n-gramサブグループ出現リスト21とn-gramサブグループ出現リスト22をそれぞれ取得する。n-gramサブグループ出現リスト21とn-gramサブグループ出現リスト22の両方においてID範囲が１～１０に対応するポインタは「FO」と「OT」のいずれも存在しないことを示すため、計算機は次に照合対象を進める。
　ID範囲が５１～６０まで照合対象が進むと、ID範囲が５１～６０に対応するポインタは「FO」と「OT」の両方の存在を示すため、計算機はポインタをたどりn-gramインデックス14とn-gramインデックス15を照合する。n-gramインデックス14とn-gramインデックス15の両方においてIDの値が６０までの照合を終了すると、計算機はn-gramサブグループ出現リスト21とn-gramサブグループ出現リスト22の両方のID範囲が６１～７０へ照合対象を進める。
　ID範囲の８１～９０まで照合対象が進むと、n-gramサブグループ出現リスト21のID範囲が８１～９０に対応するポインタは「FO」の存在を示すが、n-gramサブグループ出現リスト22のID範囲が８１～９０に対応するポインタは「OT」の存在しないことを示すため、計算機はポインタをたどらずに次へ照合対象を進める。ここで、n-gram出現リスト12とn-gram出現リスト13のID範囲が１０１～２００と２０１～３００に対応するポインタは「FO」と「OT」のどちらか一方の存在しないことを示すため、計算機はこれらのポインタはたどらない。このため、計算機はn-gramサブグループ出現リスト23とn-gramサブグループ出現リスト24の両方を取得せず、処理の対象ともしない。
　なお、図２に示した例ではn-gram出現リストとn-gramサブグループ出現リストの２階層としたが、ID範囲をグループ分けしてさらに多くの階層としてもよい。
　以上で説明したように計算機はn-gramサブグループ出現リスト21、22に基づきn-gramインデックス14のIDの値が８９を含めて８１～９０を照合対象とせず、さらに検索処理を減らすことができるため、テキスト検索を高速化できる。
　図３はn-gramインデックスの代わりにテキストをスキャンする例を示す図である。この例では検索対象テキストなどのリードがページという単位により管理され、CPUはページ番号を指定することにより特定のページをリードする。１つのページの容量は例えば１回のリードで読める容量であって、例えば8KB（キロバイト）である。一般に計算機のOS（オペレーティングシステム）あるいはファイルシステムは、クラスタサイズなどと呼ばれる所定の容量をまとめて管理してリードの単位としており、ページの容量はクラスタサイズとしてもよい。また、データベースなどのアプリケーションプログラムが所定の容量をまとめて管理してリードの単位とする場合、ページの容量はアプリケーションプログラムの管理する容量としてもよい。
　図３に示した検索語18と検索キー19とn-gramノード11は図１を用いて説明したものと同じである。n-gram出現リスト31はページ番号と各ページにおける「FO」の出現有無の情報を含む。n-gram出現リスト32はページ番号と各ページにおける「OT」の出現有無の情報を含む。ここで、n-gram出現リスト31のページ番号とn-gram出現リスト32のページ番号は対応しており、同じページ番号の容量は同じである。なお、ID範囲はこのページ番号の対応関係を説明するために図示したものであり、n-gram出現リスト31、32の内容としては必要がない。
　ページ33はページ番号１を指定されることによりリードされるスキャン対象であり、IDが０１～１５のスキャン対象を含む。この例ではアンケートの回答がテキスト検索の対象となるテキストであり、ページ33はIDと性別と年齢とアンケートの回答を含む。IDが０３のアンケートの回答は「FO」と「OT」の両方を含むため、IDが０３を含むページ番号１においてn-gram出現リスト31の出現有無とn-gram出現リスト32の出現有無の両方が有となる。ページ34はページ番号２を指定されることによりリードされるスキャン対象であり、ページ33と同じ構造である。ページ34のアンケートの回答は「OT」を含まず、IDが１６のアンケートの回答は「FO」を含むため、ページ番号２においてn-gram出現リスト31の出現有無は有となり、n-gram出現リスト32の出現有無は無となる。
　ページ35とページ36もそれぞれページ番号３とページ番号４０を指定されることによりリードされるスキャン対象であり、ページ33と同じ構造である。ページ35のアンケートの回答は「FO」を含まず、IDが３３のアンケートの回答は「OT」を含むため、ページ番号３においてn-gram出現リスト31の出現有無は無となり、n-gram出現リスト32の出現有無は有となる。IDが７９のアンケートの回答は「OT」と「FO」の両方を含むため、IDが７９を含むページ番号４０においてn-gram出現リスト31の出現有無とn-gram出現リスト32の出現有無の両方が有となる。
　テキスト検索の処理を開始すると、図１を用いて説明した処理を同じ処理により、計算機はn-gram出現リスト31とn-gram出現リスト32を取得する。ページ番号１においてn-gram出現リスト31の出現有無とn-gram出現リスト32の出現有無の両方が有であるため、計算機はページ番号１を指定してページ33をリードし、アンケートの回答をスキャンする。スキャンするために計算機はリードしたページ33のIDが０１のIDと性別と年齢を取得し、アンケートの回答のテキストで検索語18の「FOOT」でスキャンする。このスキャンの処理は１文字ずつ一致するか否かを判定するなどの処理でもよい。
　計算機はIDが０１のアンケートの回答をスキャンし終えると、IDが０２へスキャン対象を進める。さらにIDが０３へスキャン対象を進めると、計算機は「FOOTBALL」の「FOOT」を見つける。計算機はIDが１５すなわちページ33の全てをスキャンし終えると、n-gram出現リスト31とn-gram出現リスト32の両方においてページ番号２の出現有無を判定する。この例ではn-gram出現リスト32の出現有無が無であるため、計算機はページ34をスキャン対象とすることなく、ページ番号３の出現有無の判定に進む。ページ番号３ではn-gram出現リスト31の出現有無が無であるので、計算機はページ35をスキャン対象とすることなく、ページ番号４の出現有無の判定へ進む。
　このようにしてページ番号４０まで出現有無の判定を進めると、n-gram出現リスト31の出現有無とn-gram出現リスト32の出現有無の両方が有であるため、計算機はページ番号４０を指定してページ36をリードする。計算機はIDが７８のアンケートの回答をスキャン対象とし、次にIDが７９のアンケートの回答をスキャン対象とする。このアンケートの回答は「OT」と「FO」を含むが「FOOT」を含まないため、計算機は検索語18の「FOOT」でスキャンしても「FOOT」を見つけない。
　以上で説明したように、計算機はn-gram出現リスト31、32に基づきページ34、35をスキャン対象とせず、検索処理を減らすことができるため、n-gramインデックスの代わりにテキストをスキャンしてもテキスト検索を高速化できる。また、リードの単位であるページで検索キーと一致する文字列の出現有無を管理するため、計算機は個別の検索キーと一致する文字列を含まないリードを行うことがない。
　図４はアンケートの回答を分離した例を示す図である。検索語18と検索キー19とn-gramノード11は図１を用いて説明したものと同じである。n-gram出現リスト41は図３を用いて説明したn-gram出現リスト31と同じ構造であり、ページ番号と各ページにおける「FO」の出現有無の情報を含むが、１つのページに対応するIDの範囲が異なる。また、n-gram出現リスト42もn-gram出現リスト32と同じ構造であり、ページ番号と各ページにおける「OT」の出現有無の情報を含むが、１つのページに対応するIDの範囲が異なる。
　ページ43はページ番号１を指定されることによりリードされる情報であり、IDが０１～２０の情報を含む。ページ43はIDと性別と年齢とアンケートの回答へのポインタ（pt）を含む。このポインタはアンケートの回答の含まれるページ番号と、アンケートの回答のテキストそれぞれの先頭文字のページ内における文字位置を含んでもよい。IDとアンケートの回答との対応関係は図３に示したページ33、34と同じである。アンケートの回答をページ44へ分離することにより、ページ33と同じ容量であっても、ページ43はページ33と比較して多くのIDに関する情報を含むことができる。
　また、ページ43は可変長のアンケートの回答を含まないため、各ページは同じ量のID範囲の情報を含むことができる。図３に示したn-gram出現リスト31ではページ番号１のID範囲が１～１５の１５個のIDであり、ページ番号２のID範囲が１６～２１の６個のIDであるのに対し、図４に示したn-gram出現リスト41ではページ番号１のID範囲もページ番号２のID範囲も２０個のIDである。
　ページ44はページ番号５を指定されることによりリードされるスキャン対象であり、アンケートの回答のテキストを含む。ページ44はアンケートの回答以外を含まないため、ページ33と同じ容量であっても、ページ44はページ33と比較して多くのアンケートの回答を含むことができる。ページ45～48もページ43、44と同じ構造である。なお、図４に示した例ではページ43のIDに対応するアンケートの回答がページ44に存在するが、このような状態に限定されるものではなく、ページの容量とテキストの容量によってはページ43のIDに対応するアンケートの回答の一部がページ44とページ46とに分かれる場合もある。また、ページ45の一部のIDに対応するアンケートの回答とページ47の一部のIDに対応するアンケートの回答とが１つのページ46にまとまる場合もある。
　図３を用いて既に説明したページ33をリードする代わりに、計算機はページ43をリードし、ページ43内のポインタをたどってページ44をリードして、アンケートの回答をスキャン対象にする。
　以上で説明したように、１回のリードにより多くのIDに関する情報を取得することが可能になる。また、可変長のテキストをポインタで管理するデータ構造は一般に広く採用されており、そのようなデータ構造であっても、計算機はn-gram出現リスト41、42に基づきページ45、46をスキャン対象とせず、検索処理を減らすことができるため、テキスト検索を高速化できる。
　図５はn-gramノードを木構造にした例を示す図である。検索語18と検索キー19とn-gram出現リスト12、13は図１を用いて説明したものと同じである。図５に示すn-gramノードの例は木構造であり、根（ルート）となる第１層のn-gramノード51と第２層のn-gramノード52と葉（リーフ）となる第３層のn-gramノード53とから構成される。n-gramノード53はn-gramノード11と同じ内容であり、ｎ文字（２文字）とそのｎ文字に対応するn-gramインデックスへのポインタを含む。
　n-gramノード52はn-gramノード53へのポインタを含む。n-gramノード52のｎ文字が「AE」に対応するポインタは、n-gramノード53のｎ文字が「AB」「AC」「AE」へのポインタである。図５に示したポインタは「AB」「AC」「AE」の３つを代表して「AB」への矢印で表す。同様にn-gramノード52のｎ文字が「BR」に対応するポインタは、n-gramノード53のｎ文字が「BE」「BI」「BR」へのポインタであり、n-gramノード52のｎ文字が「OT」に対応するポインタは、n-gramノード53のｎ文字が「FO」「GO」「OT」へのポインタである。
　n-gramノード51のｎ文字が「BR」に対応するポインタは、n-gramノード52の「AE」「BR」を含むｎ文字へのポインタであり、n-gramノード51のｎ文字が「SV」に対応するポインタは、n-gramノード52の「OT」「SV」を含むｎ文字へのポインタである。このため、「BR」と「SV」との間に位置するｎ文字は「SV」に対応するポインタの先に存在し、「AE」と「BR」との間に位置するｎ文字は「BR」に対応するポインタの先に存在する。
　計算機は検索条件である検索語18の「FOOT」を検索キー19の「FO」と「OT」へ分解すると、「FO」と「OT」のそれぞれをn-gramノード51から検索する。計算機は検索キー19の「FO」とｎ文字の「BR」と比較し、ｎ文字の「SV」と比較して、「FO」が「BR」と「SV」との間に位置すると判断する。そして、計算機は「SV」に対応するポインタをたどり、n-gramノード52の「OT」と「SV」を含むｎ文字を取得する。計算機は検索キー19の「FO」とn-gramノード52のｎ文字の「OT」と比較して、「FO」が「OT」より「BR」の方に存在する、すなわち「FO」が「OT」と「BR」との間に位置すると判断する。
　このため、計算機は「OT」に対応するポインタをたどり、n-gramノード53の「FO」を見つけて「FO」に対応するポインタをたどり、n-gram出現リスト12を取得する。この後の処理は図１を用いて既に説明した処理と同じである。また、検索キー19の「OT」に関しても同じくn-gramノード51の「SV」に対応するポインタをたどり、n-gramノード52の「OT」に対応するポインタをたどり、n-gramノード53の「OT」を見つけて「OT」に対応するポインタをたどり、n-gram出現リスト13を取得する。
　以上の説明でも明らかなように、計算機が図１に示したn-gramノード11を用いてｎ文字の「AB」「AC」「AE」「BE」などと順番に１つずつ検索キー19と比較して検索するよりも図５に示した木構造のn-gramノードを用いた方が比較の回数が少なく、短い時間で検索キー19と一致するｎ文字を見つけることができる。なお、木構造の階層の数は多いと比較の回数が増加するため、階層の数が均一であって少ない方が比較の回数が少なくなる。このため、いわゆるバランスした木構造の方が好ましい。
　以上で説明したように、計算機は木構造のn-gramノードにより検索開始から短時間でn-gram出現リストを取得できる。また、n-gramノードを木構造にしてもn-gram出現リストは使用できるため、図１などを用いて説明した高速化の効果を得ることができる。なお、各階層は同じｎ文字を配置するn-gramノードの木構造すなわちn-gramノード51、52、53は「BR」を含む木構造を説明したが、例えばn-gramノード51のｎ文字が１文字であり、n-gramノード52のｎ文字が２文字であり、n-gramノード53のｎ文字が３文字であるような木構造であってもよい。すなわち、「ABC」を「A」「AB」「ABC」と階層化した木構造であってもよい。
　図６はB-treeを用いた検索の例を示す図である。以上で説明した出現リストはテキスト検索のみならず、B-treeを用いた検索でも利用できる。検索対象テーブル61はID、C1、C2、C3の４つの項目に対して値を含むものであり、C1、C2、C3の各項目の値に一致するIDの値を検索されるテーブルである。計算機は検索開始前に検索対象テーブル61からC1のB-treeノードと図示を省略したC2のB-treeノードとC3のB-treeノードを展開する。ここで、B-treeノードは一般的なB-treeの構造であるので、構造そのものの説明は省略する。
　図６に示したB-treeノードの各値はC1あるいはC3の値に対応する。そして、B-treeノードからB-tree出現リスト62、63へのポインタはIDの値を特定する情報であるが、C1の１つの値に対し複数のIDの値が検索対象テーブル61では対応する。図６に示した検索対象テーブル61のC1が１２という値に対応するIDの値として１と３があり、検索対象テーブル61では図示を省略したIDの値として８、２２、２９もB-treeインデックス64、66に示すようにC1が１２という値に対応する。
　図１を用いて説明したIDと同じ処理をするため、B-tree出現リスト62、63はID範囲とポインタ（pt）を含む。すなわち、B-tree出現リスト62、63はそのID範囲内のIDが存在する場合、その存在するB-treeインデックス64～67へのポインタを有する。また、B-tree出現リスト62、63はそのID範囲内のIDが存在しない場合、存在しないことを示す所定の値をポインタの値として有する。ここで、B-tree出現リスト62のID範囲の各値とB-tree出現リスト63のID範囲の各値とは同一である。
　B-treeインデックス64、66はC1の値が１２である場合の検索対象テーブル61のIDの値を列挙したものであり、B-treeインデックス64はIDの値が１～１０の範囲のものを含み、B-treeインデックス66はIDの値が２１～３０の範囲のものを含む。ここで、IDの値が１１～２０の範囲のものは存在しない。また、B-treeインデックス65、67はC3の値が３２である場合の検索対象テーブル61のIDの値を列挙したものであり、B-treeインデックス65はIDの値が１～１０の範囲のものを含み、B-treeインデックス67はIDの値が１１～２０の範囲のものを含む。
　計算機は検索対象テーブル61をB-treeノードへ展開した後、B-treeインデックス64～67を作成し、B-tree出現リスト62、63を作成してポインタで接続する。計算機は検索を開始すると検索条件68を検索キー69へ変換する。この例では検索条件68がC1の値が１２であることとC3の値が32であることのAND条件である。このため、検索キー69はC1の値である１２とC3の値である３２と変換される。そして、C1の値が検索キー69の値１２に一致するIDが検索され、C3の値が検索キー69の値３２に一致するIDが検索される。
　検索キー69の値１２がC1のB-treeノードにおいて値５０以下であり、値１２と一致するため、計算機はB-tree出現リスト62を取得する。また、検索キー69の値３２がC3のB-treeノードにおいて値５２以下であり、値３５以下であり、値３２と一致するため、計算機はB-tree出現リスト63を取得する。既に説明したようにB-tree出現リスト62のID範囲の各値とB-tree出現リスト63のID範囲の各値とは同一である。計算機はID範囲１～１０においてB-tree出現リスト62とB-tree出現リスト63の両方にIDが存在すると判断し、ポインタをたどってB-treeインデックス64とB-treeインデックス65をそれぞれ取得する。
　計算機は先ずB-treeインデックス64の先頭のID 1とB-treeインデックス65の先頭のID 3を比較し、これらのIDの値は一致せず、B-treeインデックス64のIDの値が小さいため、B-treeインデックス64の照合対象すなわち比較対象を進める。計算機はB-treeインデックス64のID 3とB-treeインデックス65のID 3を比較し、これらのIDの値は一致するので、検索条件68を満たすIDの値として３を見つける。さらに、計算機は照合対象を進めて、B-treeインデックス64のID 8とB-treeインデックス65のID 5を比較し、これらのIDの値は一致せず、B-treeインデックス64とB-treeインデックス65の末尾であるため、B-tree出現リスト62とB-tree出現リスト63における照合対象をID範囲１１～２０へ進める。
　計算機はB-tree出現リスト62のID範囲１１～２０に対応するポインタからID範囲１１～２０にはIDが存在しないと判断し、B-tree出現リスト63のID範囲１１～２０に対応するポインタの先のB-treeインデックス67を照合対象とすることなく、検索条件68を満たさないと判断する。さらに、計算機はB-tree出現リスト62とB-tree出現リスト63における照合対象をID範囲２１～３０へ進める。計算機はB-tree出現リスト63のID範囲２１～３０に対応するポインタからID範囲２１～３０にはIDが存在しないと判断し、B-tree出現リスト62のID範囲２１～３０に対応するポインタの先のB-treeインデックス66を照合対象とすることなく、検索条件68を満たさないと判断する。
　以上で説明したように、B-treeを用いた検索においても計算機はB-tree出現リストに基づきB-treeインデックス66、67を照合対象とせず、検索処理を減らすことができるため、ID検索を高速化できる。
　図７はファイルシステムの例を示す図である。計算機のＯＳあるいはファイルシステムにはiノードを用いてディレクトリとファイルを管理するものがある。このような管理においてディレクトリもファイルであり、データ領域にデータブロックとして管理される。iノードは複数個列挙されてiノードリストを構成する。図７に示すようにiノード76はルートディレクトリ710へのポインタを含み、ルートディレクトリ710の各ディレクトリと各ファイルはiノードへのポインタを含む。ルートディレクトリ710のディレクトリ名homeはiノード77へのポインタを有し、iノード77は/homeディレクトリ711へのポインタを有する。
　/homeディレクトリ711のディレクトリ名srcはiノード78へのポインタを有し、iノード78は/home/srcディレクトリ712へのポインタを有する。/home/srcディレクトリ712のファイル名test.cはiノード79へのポインタを有し、iノード79はtest.cファイル713へのポインタを有する。このようにしてルートディレクトリ710からtest.cファイル713へ到達してtest.cファイル713へアクセス可能となる。
　iノードリストはグループ分けされ、グループ分けされたそれぞれのiノードリストはリスト番号で管理される。図３を用いた説明と同じように、iノードリストのグループの単位は１回のリードの単位が好ましい。そして、出現リストにおいてリスト番号ごとに検索キーの出現有無を管理する。複数の出現リストは同一のリスト番号を有するため、同一のグループ分けされたiノードリストを管理する。
　例えば「main」という検索キーはリスト番号１で管理されるiノードリスト73とリスト番号２で管理されるiノードリスト74との２つのiノードリストに含まれるポインタの先のデータブロックには存在しないため、出現リスト71のリスト番号１と２の出現有無の欄は無となる。これに対し、リスト番号３で管理されるiノードリスト75に含まれるiノード79のポインタの先のtest.cファイル713には「main」が存在するため、出現リスト71のリスト番号３の出現有無の欄は有となる。「src」の出現リスト72も同様である。
　「main」と「src」の両方の検索キーを含むディレクトリやファイルなどのデータブロックを検索する場合、計算機は先ず出現リスト71のリスト番号１の出現有無の欄と出現リスト72のリスト番号１の出現有無の欄との両方が無であると判定する。すなわち、計算機はリスト番号１のiノードリスト73に含まれるポインタの先には「main」と「src」の両方が無いことを判定できるため、iノードリスト73を検索対象とせず、リスト番号２へ進む。計算機は出現リスト72のリスト番号２の出現有無の欄は有であるが、出現リスト71のリスト番号２の出現有無の欄は無であると判定する。このため、計算機はiノードリスト74を検索対象とせず、リスト３へ進む。
　計算機は出現リスト71と出現リスト72の両方のリスト番号３の出現有無の欄が有であると判定する。この時点では、リスト番号３で管理するiノードリスト75のどのiノードのポインタの先に「main」と「src」が存在するかは不明である。そこで、計算機はiノードリスト75のどのiノードのポインタの先に「main」と「src」が含まれるか否かをスキャンする。計算機はiノード78のポインタの先の/home/srcディレクトリ712を取得して、「main」と「src」をスキャンする。さらに、計算機はiノード79のポインタの先のtest.cファイル713を取得して、「main」と「src」をスキャンする。この例では計算機がtest.cファイル713において「main」と「open」を見つける。
　以上で説明したように、iノードを使用するファイルシステムにおいて、出現リスト71、72に基づきiノードリスト73、74およびルートディレクトリ710と/homeディレクトリ711をスキャン対象とせず、検索処理を減らすことができるため、ファイルの検索を高速化できる。
　図８は計算機の構成の例を示す図である。計算機はCPU-A81とCPU-B82の２個のCPUを有し、２個のCPUは独立して処理を実行できる。CPU-A81は専用のキャッシュA83が接続され、CPU-B82は専用のキャッシュB84が接続される。さらに、計算機はCPU-A81とCPU-B82が共用するキャッシュC85を有し、メモリ86とHDD（ハードディスクドライブ）やSSD（ソリッドステートドライブ）などのストレージデバイス87を有する。これらはアクセス性能と記憶容量が異なり、キャッシュA83とキャッシュB84のアクセス性能が１番に高く記憶容量が１番に少ない。キャッシュC85のアクセス性能が２番目に高く記憶容量が２番目に少ない。メモリ86のアクセス性能が３番目に高く記憶容量が３番目に少ない。ストレージデバイス87のアクセス性能が４番目に高く記憶容量が４番目に少ない。
　出現リストすなわちn-gram出現リスト12、13、21～24、31、32、41、42と、B-tree出現リスト62、63と、出現リスト71、72は、所定の範囲に検索キーが存在するか否かを示す簡単な情報であり、格納に必要な記憶容量が少ないため、キャッシュA83およびキャッシュB84あるいはキャッシュC85に格納されることにより、検索処理を高速化できる。特に、出現リスト以外の情報は処理対象とならない場合があるのに対し、出現リストの情報は全てが処理対象となるため、出現リストがキャッシュに格納されることにより検索処理の高速化の効果は高くなる。
　図３に示すようにページがアンケートの回答のテキストを含む場合、テキストは大きな記憶容量を占めるため、ページはストレージデバイス87に格納され、出現リストに基づきリードされるページが少なくなることにより、ストレージデバイス87へのアクセス回数が減少して検索処理の高速化の効果は高くなる。
　図２に示すように出現リストが階層化された場合、階層内の複数の出現リストは異なるCPUで並列に処理されてもよい。例えば、図２に示すn-gramサブグループ出現リスト21、22はキャッシュA83に格納されて、CPU-A81により処理される。これに対して、図示を省略したn-gram出現リスト12、13の両方の同じID範囲にポインタの存在するn-gramサブグループ出現リストはキャッシュB84に格納されて、CPU-B82により処理される。これにより、２つのn-gramサブグループ出現リストは２つのCPU-A81とCPU-B82により並列に処理可能となる。
　また、出現リストの異なるID範囲は独立であるため、異なるID範囲は異なるCPUで並列に処理されてもよい。例えば、n-gram出現リスト12、13の両方のID範囲１～１００はキャッシュA83に格納されて、CPU-A81により処理される。これに対して、n-gram出現リスト12、13の両方のID範囲１０１～２００はキャッシュB84に格納されて、CPU-B82により処理される。そして、n-gramサブグループ出現リストも異なるID範囲は異なるCPUで処理されてもよく、n-gram出現リスト31、32の異なるページ番号は異なるCPUで処理されてもよい。
　なお、計算機がキャッシュA83とキャッシュB84を含まない場合であっても、異なるCPUで並列に処理するために、出現リストがキャッシュC85あるいはメモリ86に格納されて、CPU-A81とCPU-B82に共用されてもよい。
　図３、４に示すようにアンケートの回答のテキストがスキャンされる場合、異なるページのアンケートの回答のテキストは異なるCPUで並列にスキャンされてもよい。例えば、図３に示すページ番号１のページ33をCPU-A81がスキャンし、ページ番号４０のページ36をCPU-A82がスキャンしてもよい。図８には計算機が２個のCPUと３個のキャッシュを有する例を示したが、これに限定されるものではなく、３個以上のCPUを有してもよく、４個以上のキャッシュを有してもよい。
　計算機は、図示を省略したディスプレイとキーボードとマウスを接続する入出力IF（インターフェイス）88と図示を省略したネットワークに接続するネットワークIF89を有する。計算機が検索を処理するための設定情報を入出力IF88経由で受け取り、検索結果を入出力IF88から出力してディスプレイに表示してもよい。また、計算機はネットワークIF89経由で設定情報を受け取り、検索結果を出力してもよい。さらに、テキストやIDなどの検索対象データおよび検索のために実行するプログラムをネットワークIF89で受け取ってもよい。
　図９は出現リストを作成する処理フローの例を示す図である。出現リストは検索開始前のn-gramノード、B-treeノード、iノード作成時に作成されてもよいし、n-gramノードとn-gramインデックスあるいはB-treeノードとB-treeインデックスが予め作成されていて検索を開始し、１回目の検索の時点で作成されてもよい。ここでは検索開始前にノードとともに出現リストを作成する例を説明する。
　計算機はステップ91によりグループ作成単位を決定する。図１において１００のID範囲が１つのグループであり、図３において１つのページが１つのグループであり、図６において１０のID範囲が１つのグループである。これらのグループを作成する単位はユーザの入力値を使用してもよいし、ページなどのリードの単位であればＯＳやファイルシステムのパラメタから取得してもよい。次に、計算機はステップ92からステップ911までのステップをループの範囲とし、グループの個数をループの回数としてステップ93へ進む。
　計算機はステップ93により１つのグループのデータを取得する。ここで、１つのグループはステップ91で決定した単位のグループであり、ループが実行されるごとに次々と他のグループへ変更される。データは図３、４のテキスト検索においてページ33などのID、性別、年齢、アンケートの回答（テキスト）であり、図６のID検索において検索対象テーブル61であり、図７のファイルシステム検索においてデータブロックである。
　ステップ94により計算機はステップ93で取得したデータから全てのIDを取得する。全てのIDは図１において例えば１～１００に含まれる全てのIDであって５２、７３、８９、９５などであり、図３において例えば１～１５であり、図６では例えば１～１０に含まれる全てのIDであって１～３、５、８などである。次に、計算機はステップ95からステップ910までのステップをループの範囲とし、ステップ94で取得したIDの個数をループの回数としてステップ96へ進む。
　計算機はステップ96により１つのIDに対応するテキスト内の全てｎ文字、あるいは１つのIDに対応する値を取得する。ここで、１つのIDはループが実行されるごとに次々と他のIDへ変更される。そして、図３においてIDが０１に対応するテキスト内の全てのｎ文字は、アンケートの回答のテキストから「OU」「UT」「TD」などの全ての２文字である。また、図６においてIDが１に対応する値は、C1の１２とC2のaaaとC3の７８である。
　ステップ97により計算機はステップ96で取得した全てのｎ文字あるいは値をn-gramノードあるいはB-treeノードへ登録し、n-gramノードあるいはB-treeノードを作成して行く。ステップ98により計算機はインデックスへIDおよび必要に応じて全ての文字位置を登録する。すなわち、ステップ96でIDの値が５２の場合に図１で計算機はn-gramインデックス14、15にIDの値５２を登録し、このIDの値に対して文字位置３７と１２２および文字位置３９と１２５を登録する。また、ステップ96でIDの値が１の場合に図６で計算機はB-treeインデックス64にIDの値１を登録し、図示を省略したC2がaaaに対応するB-treeインデックスとC3が７８に対応するB-treeインデックスにIDの値１を登録する。
　ステップ99により計算機はステップ98で新たなｎ文字あるいは新たな値を登録した場合、登録した新たなｎ文字あるいは新たな値に関する出現リストを作成し、作成した出現リストあるいは既に作成済みの出現リストへインデックスへのポインタあるいは出現有無の情報を登録する。ここで、出現リストを作成するために計算機は図１でIDの値が５２の新たなｎ文字「FO」に対し、ID範囲が１～１００のみならず１０１以降も含めてグループの数を行数とするn-gram出現リスト12を作成する。そして、計算機はn-gramノード11のｎ文字「FO」に対応するポインタへn-gram出現リスト12を登録し、n-gram出現リスト12のID範囲が１～１００に対応するポインタへn-gramインデックス14を登録する。計算機はn-gram出現リストのID範囲が１０１以降のポインタへ「FO」が存在しない場合の所定の値を設定する。
　その後、計算機はIDの値が２０３の新たではないｎ文字「FO」に対し、既に存在するn-gram出現リスト12のID範囲が２０１～３００に対応するポインタへn-gramインデックス16を登録する。ID範囲が１０１～２００において「FO」は存在しないため、n-gram出現リスト12のID範囲が１０１～２００は作成時に設定された「FO」が存在しない場合の所定の値を維持する。
　以上で説明したように、n-gramノードあるいはB-treeノードと、n-gramインデックスあるいはB-treeインデックスを作成するとともに、n-gram出現リストあるいはB-tree出現リストを作成できる。なお、図３、４に示したテキストスキャンと図７に示したファイルシステムではインデックスなどがないため、計算機は必要のないステップを実行しなければよい。
　図１０は出現リストを使用した検索の処理フローの例を示す図である。ステップ101により計算機は検索条件である検索語18を検索キー19に変換する、あるいは検索条件68を検索キー69に変換する。ステップ102により計算機はn-gramノードあるいはB-treeノードを検索キーで検索し、検索キーにより見つかったｎ文字列あるいは値に対応するポインタを取得し、取得したポインタにより出現リストを取得する。すなわち、図１において計算機は検索キー19の「FO」に対してn-gramノード11のｎ文字「FO」を見つけ、ｎ文字「FO」に対応するポインタを使用してn-gram出現リスト12を取得する。また、図６において計算機は検索キー69の値１２に対してC1のB-treeノードの値１２を見つけ、値１２に対応するポインタを使用してB-tree出現リスト62を取得する。
　計算機はステップ103からステップ107までのステップをループの範囲とし、ステップ102で取得した出現リスト内のグループ数をループの回数としてステップ104へ進む。ここで、グループ数は図１のn-gram出現リスト12の１～１００と１０１～２００と２０１～３００を３個と数えてのID範囲の項目数であり、図３のn-gram出現リスト31のページ番号の項目数の４０である。
　ステップ104により計算機は出現リストから１つのグループの全ての出現有無情報あるいは出現有無を示すポインタを取得する。ここで、１つのグループはループが実行されるごとに次々と他のグループへ変更される。１つのグループの全ての出現有無情報は例えば図３のn-gram出現リスト31のページ番号１に対応する出現有無情報とn-gram出現リスト32のページ番号１に対応する出現有無情報である。すなわち、ページ番号１という１つのグループの複数のn-gram出現リスト全ての出現有無情報である。１つのグループの全ての出現有無を示すポインタは例えば図１のn-gram出現リスト12のID範囲が１～１００に対応するポインタとn-gram出現リスト13のID範囲が１～１００に対応するポインタである。すなわち、ID範囲が１～１００という１つのグループの複数のn-gram出現リスト全てのポインタである。
　ステップ105により計算機はステップ104で取得した出現有無情報が全て有を示すか否か、あるいは取得したポインタが全て有を示すか否かを判定する。計算機は全て有を示すと判定するとステップ106へ進み、出現有無情報が有に対応する１つのグループについて詳細な検索を行う。例えば図３ではページ番号１という有に対応する１つのグループがあり、計算機はページ番号１であるページ33を取得し、ページ33に含まれるアンケートの回答のテキストの中から「FOOT」をスキャンする。
　例えば図１ではID範囲が１～１００という有に対する１つのグループがあり、計算機はn-gram出現リスト12のID範囲が１～１００に対応するポインタからn-gramインデックス14を取得し、n-gram出現リスト13のID範囲が１～１００に対応するポインタからn-gramインデックス15を取得し、図１を用いて既に説明したようにIDの一致と文字位置の隣接を照合する。ステップ103からステップ107までのループにより全てのグループを照合すると、計算機はステップ108により詳細検索の結果をまとめて出力する。
　以上で説明したように、計算機は出現リストに基づき１つのグループの全ての出現有無情報が有の場合のみに詳細検索を実行するため、詳細検索の実行対象を絞ることができ、検索を高速化できる。また、図１０においてステップ106を全てのグループの出現有無情報のチェックが終わった後に実行することとし、全出現有無情報が有であるグループの数が多い場合、すなわち詳細検索に時間が掛かる場合には、ユーザに検索条件の見直しを促すようにしてもよい。
　図１１は出現リスト作成パラメタの入力の例を示す図である。図９に示したステップ91において計算機は入出力IF88からディスプレイへウインドウ111の表示データを出力し、キーボードとマウスによるパラメタの入力を入出力IF88で受け付けてもよい。また、ネットワークIF89で接続されたネットワークの他の計算機が出力と入力を行い、出力する表示データと入力するパラメタを計算機はネットワークIF89で送受信してもよい。
　出現リスト作成の入力欄112は、出現リストを作成しない設定、出現リストを検索開始前に作成する設定、出現リストを１回目の検索時に作成する設定を含む設定を入力する欄である。この欄で出現リストを作成しない設定が入力されると、計算機は図９に示したステップ99を実行せず、対応するインデックスをノードへ登録する。また、出現リストを１回目の検索時に作成する設定が入力されると、計算機はステップ99を実行せず、対応するインデックスをノードへ登録し、１回目の検索時に出現リストを作成して登録する。また、出現リストを検索開始前に作成する設定が入力されると、計算機は図９を用いて説明したとおり処理する。
　検索対象の入力欄113は検索対象データのファイルなど、すなわち出現リストを作成する対象のファイルなどを指定する欄である。テキスト検索の対象となるテキストファイルの名称を指定してもよいし、検索の対象となるデータベースなどの名称を指定してもよい。計算機はステップ93により検索対象の入力欄113で指定されたファイルなどからデータを取得する。
　ID単位の入力欄114は図１、６を用いて説明したIDを指定される欄である。検索対象の入力欄113で指定されたファイルなどにIDが明示的に含まれる場合、例えば図６を用いて説明した検索対象テーブル61にはIDの項目が存在するため、このIDの項目をID単位の入力欄114は指定される。検索対象の入力欄113で指定されたファイルなどにIDが明示的に含まれていない場合、図１を用いて説明したように項目やパラグラフをID単位の入力欄114は指定されてもよい。また、テキストの行をID単位として指定されてもよい。なお、図３、４を用いて説明した例ではIDを使用しないため、ID単位の入力欄114はIDを指定されないという設定が可能であってもよい。
　グループ単位の入力欄115はID単位の入力欄114で指定されたIDを基準にグループを指定したり、OSやファイルシステムからパラメタを取得してグループとすることを指定したりする欄である。図１を用いて説明したn-gram出現リスト12、13とするために、グループ単位の入力欄115は１００という単位が入力され、図６を用いて説明したB-tree出現リスト62、63とするために、グループ単位の入力欄115は１０という単位が入力される。図３、４を用いて説明した例では、OSやファイルシステムから１回のリードという単位が入力される。このグループ単位の入力欄115で入力された指定は複数の出現リスト全てで共通である。これによりグループごとに検索キー19、69で見つかるものの出現有無の判定が可能となる。
　階層数の入力欄116は出現リストの階層数を指定される欄である。図１、６の例では出現リストが１層であるため、階層数の入力欄116は１が入力される。あるいは、デフォルトの階層数を１として、計算機は何も入力されないと出現リストが１層であると判断してもよい。図２の例では出現リストがn-gram出現リスト12、13とn-gramサブグループ出現リスト21～24の２層であるため、階層数の入力欄116は２が入力される。ここで、n-gramサブグループ出現リスト21、23はn-gram出現リスト12の１つのグループをさらにグループ分けするものであるから、そのグループ分けの単位を入力するために、グループ単位の入力欄115を２つに増やす。そして、グループ単位の入力欄115はn-gram出現リスト12のための１００とn-gramサブグループ出現リスト21、23のための１０が入力される。
　入力欄112～116のそれぞれは文字列を入力可能としてもよいし、選択可能な候補が列挙して表示されていわゆるラジオボタンで選択可能としてもよいし、いわゆるプルダウンメニューで選択可能としてもよい。
　以上で説明したように、検索対象データを複数のグループに分け、複数の出現リストで同じグループを管理することにより、計算機は出現リストに基づき検索が不要のグループを判断できるため、検索が不要なグループの処理を削減し、検索を高速化できる。
１１　　　：n-gramノード
１２、１３：n-gram出現リスト
１４～１７：n-gramインデックス
１８　　　：検索語
１９、６９：検索キー
２１～２４：n-gramサブグループ出現リスト
６２、６３：B-tree出現リスト
６４～６７：B-treeインデックス
６８　　　：検索条件

Claims (12)

  1. 　指定された文字列で文献を検索する計算機の文字列検索方法において、
    　前記指定された文字列を第１の文字または文字列と第２の文字または文字列を含む複数の文字または文字列に分解する第１のステップと、
    　前記計算機の１回のリード処理で読み込める単位で複数の文献をグルーピングして複数の集合を作成する第２のステップと、
    　前記複数の集合それぞれにおいて前記第１の文字または文字列が出現するか否かを判定し、出現する集合それぞれに前記第１の文字または文字列の第１の出現情報を付与する第３のステップと、
    　前記複数の集合それぞれにおいて前記第２の文字または文字列が出現するか否かを判定し、出現する集合それぞれに前記第２の文字または文字列の第２の出現情報を付与する第４のステップと、
    　前記複数の集合の中の第１の集合において前記第１の出現情報と前記第２の出現情報が付与されている場合、前記第１の集合を詳細検索対象とする第６のステップと、
    を有することを特徴とする文字列検索方法。
  2. 　前記複数の集合の中の第２の集合において前記第１の出現情報あるいは前記第２の出現情報が付与されていない場合、前記第２の集合を詳細検索対象としない第７のステップをさらに有することを特徴とする請求項１に記載の文字列検索方法。
  3. 　前記詳細検索対象を前記指定された文字列で検索する第８のステップをさらに有することを特徴とする請求項２に記載の文字列検索方法。
  4. 　前記複数の集合それぞれにおいて、前記第１の文字または文字列および前記第２の文字または文字列以外の前記分解された文字または文字列それぞれが出現するか否かを判定し、出現する集合それぞれに出現情報を付与する第５のステップをさらに有し、
    　前記第６のステップであって、前記複数の集合の中の第３の集合において前記第１の出現情報と前記第２の出現情報を含むすべての出現情報が付与されている場合、前記第３の集合を詳細検索対象とする第６のステップを有することを特徴とする請求項１に記載の文字列検索方法。
  5. 　前記複数の集合の中の第４の集合において前記第３のステップと前記第４のステップと前記第５のステップの少なくとも１つのステップにおいて出現情報が付与されていない場合、前記第４の集合を詳細検索対象としない第７のステップをさらに有することを特徴とする請求項４に記載の文字列検索方法。
  6. 　前記詳細検索対象を前記指定された文字列で検索する第８のステップをさらに有することを特徴とする請求項５に記載の文字列検索方法。
  7. 　指定された文字列で文献を検索する計算機の文字列検索方法において、
    　前記計算機の１回のリード処理で読み込める単位で複数の文献をグルーピングして複数の集合を作成する第１のステップと、
    　前記複数の集合それぞれにｎ個（ｎは自然数）の任意の文字が出現するか否かを判定し、出現する集合それぞれにｎ個の文字の出現情報を付与する第２のステップと、
    　前記指定された文字列を第１のｎ個の文字と第２のｎ個の文字を含む複数のｎ個の文字に分解する第３のステップと、
    　前記複数の集合の中の第１の集合において前記第１のｎ個の文字の出現情報が付与されるとともに前記第２のｎ個の文字の出現情報が付与されている場合、前記第１の集合を詳細検索対象とする第４のステップと、
    を有することを特徴とする文字列検索方法。
  8. 　前記複数の集合の中の第２の集合において前記第１のｎ個の文字の出現情報あるいは前記第２のｎ個の文字の出現情報のいずれかがが付与されていない場合、前記第２の集合を詳細検索対象としない第５ステップをさらに有することを特徴とする請求項７に記載の文字列検索方法。
  9. 　前記詳細検索対象を前記指定された文字列で検索する第６ステップをさらに有することを特徴とする請求項８記載の文字列検索方法。
  10. 　前記第４のステップであって、前記複数の集合の中の第３の集合において前記第１のｎ個の文字の出現情報と前記第２のｎ個の文字の出現情報を含む前記分解されたすべてのｎ個の文字の出現情報が付与されている場合、前記第３の集合を詳細検索対象とする第４のステップを有することを特徴とする請求項７に記載の文字列検索方法。
  11. 　前記複数の集合の中の第４の集合において前記第１のｎ個の文字の出現情報と前記第２のｎ個の文字の出現情報を含む前記分解されたｎ個の文字の出現情報の中の少なくとも１つの出現情報が付与されていない場合、前記第４の集合を詳細検索対象としない第５のステップをさらに有することを特徴とする請求項１０に記載の文字列検索方法。
  12. 　前記詳細検索対象を前記指定された文字列で検索する第６のステップをさらに有することを特徴とする請求項１１に記載の文字列検索方法。
PCT/JP2014/067438 2014-06-30 2014-06-30 検索方法 WO2016001991A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US15/122,780 US10394870B2 (en) 2014-06-30 2014-06-30 Search method
JP2016530714A JP6212639B2 (ja) 2014-06-30 2014-06-30 検索方法
PCT/JP2014/067438 WO2016001991A1 (ja) 2014-06-30 2014-06-30 検索方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2014/067438 WO2016001991A1 (ja) 2014-06-30 2014-06-30 検索方法

Publications (1)

Publication Number Publication Date
WO2016001991A1 true WO2016001991A1 (ja) 2016-01-07

Family

ID=55018593

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2014/067438 WO2016001991A1 (ja) 2014-06-30 2014-06-30 検索方法

Country Status (3)

Country Link
US (1) US10394870B2 (ja)
JP (1) JP6212639B2 (ja)
WO (1) WO2016001991A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2018084907A (ja) * 2016-11-22 2018-05-31 富士通株式会社 ジョブ消費電力推定プログラム、並列処理装置およびジョブ消費電力推定方法

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11868335B2 (en) * 2019-05-22 2024-01-09 Druva Inc. Space-efficient change journal for a storage system
US20230161774A1 (en) * 2021-11-24 2023-05-25 International Business Machines Corporation Semantic annotation for tabular data

Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH05135102A (ja) * 1991-11-11 1993-06-01 Ricoh Co Ltd 文書検索方式
JPH07282073A (ja) * 1994-04-04 1995-10-27 Toyota Motor Corp データ検索装置及びその方法
JPH0869476A (ja) * 1994-08-30 1996-03-12 Hokkaido Nippon Denki Software Kk 検索システム
JPH08161357A (ja) * 1994-06-02 1996-06-21 Ricoh Co Ltd 文書管理装置
JPH09223160A (ja) * 1996-02-19 1997-08-26 Hitachi Ltd 文書検索方法
JP2009037359A (ja) * 2007-07-31 2009-02-19 Hitachi Ltd データ登録検索方法、データ登録検索プログラムおよびデータベースシステム
JP2009134627A (ja) * 2007-11-30 2009-06-18 Mitsubishi Electric Corp Ｎ文字索引生成装置、文書検索装置、ｎ文字索引生成方法、文書検索方法、ｎ文字索引生成プログラムおよび文書検索プログラム
WO2013179348A1 (ja) * 2012-05-31 2013-12-05 富士通株式会社 インデックス生成プログラム及び検索プログラム

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP3459053B2 (ja) 1995-01-12 2003-10-20 株式会社日立製作所 文書検索方法および装置
JP3620968B2 (ja) 1998-08-05 2005-02-16 株式会社日立製作所 文書検索方法及びその実施装置並びにその処理プログラムを記録した媒体
JP4115048B2 (ja) * 1999-08-17 2008-07-09 株式会社リコー 文書検索システム
US7054855B2 (en) * 2001-07-03 2006-05-30 International Business Machines Corporation Method and system for performing a pattern match search for text strings
JP2006185408A (ja) * 2004-11-30 2006-07-13 Matsushita Electric Ind Co Ltd データベース構築装置及びデータベース検索装置及びデータベース装置
US8521751B2 (en) * 2008-08-22 2013-08-27 Nec Corporation Search device, a search method and a program
US20160292234A1 (en) * 2014-12-12 2016-10-06 Infosys Limited Method and system for searching in a distributed database

Patent Citations (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH05135102A (ja) * 1991-11-11 1993-06-01 Ricoh Co Ltd 文書検索方式
JPH07282073A (ja) * 1994-04-04 1995-10-27 Toyota Motor Corp データ検索装置及びその方法
JPH08161357A (ja) * 1994-06-02 1996-06-21 Ricoh Co Ltd 文書管理装置
JPH0869476A (ja) * 1994-08-30 1996-03-12 Hokkaido Nippon Denki Software Kk 検索システム
JPH09223160A (ja) * 1996-02-19 1997-08-26 Hitachi Ltd 文書検索方法
JP2009037359A (ja) * 2007-07-31 2009-02-19 Hitachi Ltd データ登録検索方法、データ登録検索プログラムおよびデータベースシステム
JP2009134627A (ja) * 2007-11-30 2009-06-18 Mitsubishi Electric Corp Ｎ文字索引生成装置、文書検索装置、ｎ文字索引生成方法、文書検索方法、ｎ文字索引生成プログラムおよび文書検索プログラム
WO2013179348A1 (ja) * 2012-05-31 2013-12-05 富士通株式会社 インデックス生成プログラム及び検索プログラム

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2018084907A (ja) * 2016-11-22 2018-05-31 富士通株式会社 ジョブ消費電力推定プログラム、並列処理装置およびジョブ消費電力推定方法

Also Published As

Publication number Publication date
US20170075989A1 (en) 2017-03-16
US10394870B2 (en) 2019-08-27
JPWO2016001991A1 (ja) 2017-04-27
JP6212639B2 (ja) 2017-10-11

Similar Documents

Publication Publication Date Title
US11720633B2 (en) Aggregating personalized suggestions from multiple sources
US9104979B2 (en) Entity recognition using probabilities for out-of-collection data
US10579661B2 (en) System and method for machine learning and classifying data
US8745061B2 (en) Suffix array candidate selection and index data structure
JP5616444B2 (ja) 文書インデックス化およびデータクエリングのための方法およびシステム
WO2017151194A1 (en) Atomic updating of graph database index structures
US10613785B1 (en) Scalable binning for big data deduplication
US10372718B2 (en) Systems and methods for enterprise data search and analysis
KR101823463B1 (ko) 연구자 검색 서비스 제공 장치 및 그 방법
Welch et al. Fast and accurate incremental entity resolution relative to an entity knowledge base
Krishnan et al. A taxonomy of query auto completion modes
JP4237813B2 (ja) 構造化文書管理システム
JP6212639B2 (ja) 検索方法
Qin et al. Asymmetric signature schemes for efficient exact edit similarity query processing
Bedathur et al. Interesting-phrase mining for ad-hoc text analytics
Ilic et al. Inverted index search in data mining
Mostafa A case study on B-Tree database indexing technique
Lu et al. Boosting the quality of approximate string matching by synonyms
Lee et al. Integrating code search into the development session
JP2795317B2 (ja) 多段表処理方式
JP6081609B2 (ja) データ分析システム及びその方法
WO2013069149A1 (ja) データ検索装置、データの検索方法及びプログラム
JP2000163439A (ja) 電子ファイル検索装置および電子ファイル検索方法
JP2005301855A (ja) 文書検索方法、文書検索プログラムおよびこれを実行する文書検索装置
JP7639730B2 (ja) 検索方法

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 14896622

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2016530714

Country of ref document: JP

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 15122780

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 14896622

Country of ref document: EP

Kind code of ref document: A1