Source: https://patents.google.com/patent/US6853992B2/en
Timestamp: 2018-08-21 20:12:12
Document Index: 523844012

Matched Legal Cases: ['art2', 'art2', 'art2', 'art1', 'art2', 'art3', 'art3', 'art3', 'art1', 'art1', 'art3', 'art3', 'art1', 'art2', 'art1', 'art1', 'art2', 'art1', 'art2']

US6853992B2 - Structured-document search apparatus and method, recording medium storing structured-document searching program, and method of creating indexes for searching structured documents - Google Patents
US6853992B2
US6853992B2 US09725680 US72568000A US6853992B2 US 6853992 B2 US6853992 B2 US 6853992B2 US 09725680 US09725680 US 09725680 US 72568000 A US72568000 A US 72568000A US 6853992 B2 US6853992 B2 US 6853992B2
US20010007987A1 (en )
(1) referring to the hierarchical index and converting the query tree to a Boolean expression in which a set having a character string and a part-ID is used as a single search key; and
(2) referring to the text index and obtaining a document-ID of a document corresponding to the query tree, by use of the Boolean expression.
Further, nodes representing meta parts are characterized in that the nodes satisfy requirements in relation to meta parts such that the nodes share a common upper node meta part, the nodes have the same element name and the same occurrence position (we call it “offset”) in a row of sibling parts in the document, and each node has an offset in a row of sibling parts in the document, a link extending from a child node to a parent node, and a link extending to another node having the same element name. This feature enables high-speed searching even when documents have a complicated structure.
1) Analyzing the structure of a document (step S13);
2) Judging whether each document part is a meta part (step S15);
3) When the document part is a meta part, registering the node in the hierarchical index 13 as the meta part (step S18); and
4) Registering in the text index 15 the identifier of the meta part and text data contained therein (step S19).
At the time of registration of structured documents, a root node of the hierarchical index 13 is first created (step S11), and the steps described below are repeated until the processing has been performed for all the documents (step S12).
1) Sharing a common upper meta part (step S22);
2) Having the same element name (step S23); and
3) Having the same offset in the row of sibling parts in a corresponding document (step S24).
When the selected document part has not yet been registered in the hierarchical index 13 (step S21), the selected document part is regarded to be a new meta part (step S25) and is registered in the hierarchical index 13 (steps S17 and S18 of FIG. 3). When the selected document part has already been registered in the hierarchical index 13, it is judged that the same meta part has already been registered (step S26), and, without registration in the hierarchical index 13, the registration of text data in the text index 15 is performed (step S19 of FIG. 3).
1) Following the tree structure up to a node corresponding to the upper meta part (step S31);
2) When the upper meta part has no child (step S32), extending a child link of the upper meta part to the new node (step S33), and when the upper meta part has a child, adding the new node (sibling link) to the end of the child node of the upper meta part (step S34);
3) Extending a link (parent link) from the new node to the upper meta part (step S35); and
4) Extending an element link to a node having the same element name.
The processing of extending an element link described in the above stage 4) is performed by means of the following steps.
(a) Preparing a work buffer in which element names are registered and from which links are extended to corresponding nodes;
(b) When the work buffer is empty (no element name is registered) (step S36), registering a new node in the work buffer (step S37); and
(c) When a node has been registered in the work buffer (step S36), extending an element link from the registered node to the new node, and registering the new node in the work buffer (step S38).
1) Registering into the text index 15 a special search key; i.e., a set including a part-ID and a special character string representing the presence of a structure (step S41);
2) When a presently-selected document part contains text data (step S42), creating pseudo text data from the text data through addition of special character strings at the start and end positions of the text data (step S43);
3) Dividing the pseudo text data into characteristic elements (step S44); and
4) Registering in the text index 15 search keys; i.e., sets each including the characteristic element and the part-ID (step S45).
Each of the special character string for representing the presence of a structure and the special character strings which are inserted at the start and end positions of text data may be a character string (a row of codes other than character codes) which does not appear in text data.
1) Creating a query tree from a user's query (step S51);
2) Converting the query tree to a Boolean expression with reference to the hierarchical index 13 (step S52); and
3) Referring to the text index 15 by use of the Boolean expression (step S53).
The user's query may be created by use of an object-oriented query language, a query language for XML documents, which is currently standardized by W3C (World Wide Web Consortium), or any other suitable language.
1) Searching from the hierarchical index 13 portions that match the structure of the query tree, and attaching temporary nodes to the matched portions (step S61).
2) Assembling the temporary nodes to create a Boolean logic tree (step S62); and
3) Creating a Boolean expression (character string) from the Boolean logic tree (step S63).
Within the full-text search engine, a Boolean expression, which is a character string, is analyzed in order to create a Boolean logic tree. Therefore, when the form of the Boolean logic tree created in step S62 shown in FIG. 9 is rendered the same as that used in the full-text search engine, the processing in step S63 may be omitted.
1) Going around the nodes of the query tree while giving priority in the hierarchical depth (steps S71 and S72);
2) Obtaining from the hierarchical index 13 a set of nodes corresponding to each node (step S73);
3) For the set obtained in 2) above, judging whether a parent-child relationship (including ancestors) which is the same as that of the nodes of the query tree is present (steps S75 and S76);
4) When a presently-selected node of the query tree has a plurality of child nodes, pushing the node of the hierarchical index 13 into a stack (steps S77 and S78);
5) When the presently-selected node of the query tree has a text-data matching condition (including a query which inquires only the presence of a document part), adding a temporary node to a node of the hierarchical index 13 (step S711); and
6) Extending a query link of the node of the hierarchical index 13 to the corresponding node of the query tree (steps S79 and S712).
Each temporary node serves as a node of a Boolean logic tree. Such a temporary node is created to have a node type (AND, OR, the type of a search key), a text-data matching condition, and a part-ID. A node whose type is AND or OR is used as an intermediate node, and ultimately, a single logic tree is assembled in step S62 of FIG. 9.
1) Removing, one at a time, the nodes of the hierarchical index 13 from the stack created in step S78 of FIG. 10 (step S82) until the stack becomes empty (step S81);
2) Performing the processing in steps S83 to S89, which will be described below, for temporary nodes provided at a level lower than the removed node;
3) When the stack becomes empty, preparing an OR temporary node, and rendering all the temporary nodes provided at a level lower than the root node of the hierarchical index 13 children of the OR node; and
4) When any AND or OR node of the assembled logical tree has a single child node, linking the child node directly to the parent node, and removing the AND or OR node from the logic tree (step S811).
The processing performed for the temporary nodes described in the above stage 2) includes the following steps.
(a) Preparing at least one OR temporary node, and rendering nodes having the same query link children of the OR node (step S83);
(b) When a plurality of OR nodes are created in step S83, preparing an AND temporary node, and rendering OR nodes which are connected to nodes having the same parent node children of the AND node (step S84);
(c) Attaching temporary nodes which are not subjected to the processing in (a) and (b) above to a node removed from the stack (step S85);
(d) When the query tree includes designation of an order (step S86), re-forming the logic tree assembled in step S84 into a disjunctive normal form (a logic expression having a form of, for example, “A1 OR A2 OR A3 OR . . . ,” and each term having a form “Ai=B1 AND B2 AND B3 AND . . . ”), by use of a logic expression distribution rule “A AND (B OR C)=(A AND B) OR (A AND C),” discarding an AND node when the order of child nodes of the query tree does not match the order of offsets stored in nodes to which the temporary nodes have been attached (step 87) (however, the disjunctive normal form used here is such that nodes up to the nodes to which the temporary nodes have been attached are treated as being literal; and the logic tree is not re-formed to a formal disjunctive normal form); and
(e) When the type of a child of the parent node of the query tree does not match the type of a child of an AND node, discarding the AND node (step S88), and attaching to the node obtained through the processing in step S82 an AND node which was not discarded in step S88 (step S89).
Through the above-described processing, a Boolean logic tree is assembled. The thus-assembled logic tree is converted into a character string by means of the processing in step S63 shown in FIG. 9. In this conversion processing, the Boolean logic tree is gone around recursively while priority is given in the hierarchical direction; and child nodes of an AND node are output in the form of an AND expression, and child nodes of an OR node are output in the form of an OR expression. Further, the output of child nodes of each node is enclosed in parentheses. An example of a recursive pseudo program for performing the above conversion is shown below.
Conversion function for conversion of a logic tree to a character string
1) The root node of the hierarchical index is created through the processing in step S11 shown in FIG. 3. The root node is created to have dummy values as an offset in sibling parts and a part-ID (see FIG. 12A).
2) During registration of Document 1, all the document parts are registered as new meta parts, because nothing has been registered in the hierarchical index. Further, through the processing in step S37 shown in FIG. 5, the respective names of document parts and links extending to the nodes are stored in a work buffer 41 (see FIG. 12B).
3) During registration of Document 2, no special processing is performed for a document part “Document,” which serves as the root of Document 2, because there has already been registered a node which is identical with the document part “Document” in terms of upper meta part, element name, and offset in a row of sibling parts in the document.
Subsequently, “Part2,” which is the first child of “Document,” is judged to be a different meta part and is registered newly, because although a node which is identical in terms of upper meta part and element name has been registered, “Part2” differs from the registered node in terms of offset in a row of sibling parts. Further, in step S38 shown in FIG. 5, the element link of the node linked from the work buffer 41 is extended to the new node, and the new node is registered in the work buffer 41 (see FIG. 12C). This is because “Part2” has already been registered in the work buffer 41.
4) “Part1” of Document 2 is newly registered as in the case of “Part2.” Re-formation of element links in the work buffer 41 is performed in a similar manner (see FIG. 13A).
5) No special processing is performed for “Part3” of Document 2, because there has already been registered a node which is identical with “Part3” in terms of upper meta part, element name, and offset in a row of sibling parts in the document. Further, since “Part3” is the last document part to be registered, the work buffer 41 is released, and the hierarchical index is completed ultimately (see FIG. 13B).
The processing for registering the above-described two documents in the text index 15 will be described with reference to FIG. 14. The example registration of documents in the text index shown in FIG. 14 is for the case in which:
An inverted file format is used;
Each characteristic element is extracted in the form of bigram, i.e. two continuous characters (since the above documents 1 and 2 are Japanese documents);
“??” is used as a special character string for expressing the presence of a structure
“^” is used as a special character string to be added at the start position of text data; and
“$” is used as a special character string to be added at the end position of the text data.
The inverted file form includes search keys 51 and document identifier lists 52, each of which is a list of the document-IDs of documents including the corresponding search key. A characteristic element and a part-ID of a document part in which the characteristic element is present are registered in the search key 51. In the document identifier list 52, the document-IDs of documents including each search key are registered in a row. If necessary, offsets and the number of times of appearance in each document are registered. FIG. 14 shows an example in which registration is performed in the form “document-ID: offset, . . . ” For example, a search key in which “” is set as a characteristic element, and “3” is set as a part-ID corresponds to the document identifier list 52 including “1:8, 2:8.” This means that the characteristic element “RE” appears at the 8th position of Document 1 and at the 8th position of Document 2.
1) The query tree is formed of a single node; and, in the node of the query tree, “Part1” is stored as an element name, and “??” is stored as a text-data matching condition (see FIG. 15A).
2) Through the processing shown in FIG. 10, temporary nodes are attached to the nodes of “Part1” in the hierarchical index. Further, the query links of the nodes to which temporary nodes have been attached are linked to the node of the query tree (see FIG. 15B).
3) Since the query tree for Search Request 1 fail to satisfy the conditions of the processing in step S77 shown in FIG. 10, there is created a state in which nothing is present in the stack. Here, the conditions of the processing in step S81 shown in FIG. 11 are satisfied, and through processing in step S810, the temporary nodes provided in 2) above are rendered child nodes of an OR node in a Boolean logic tree (see FIG. 16).
4) The Boolean logic tree assembled in 3) above is converted to a character string by means of the processing in step S63 shown in FIG. 9, so that an ultimate Boolean expression is obtained. When one search key is described in the form of “search character string@part-ID”, an OR operator in the form of “OR”, an AND operator in the form of “AND”, and parentheses symbols in the form of “(“and”)”, the ultimate Boolean expression assumes the form of a character string as follows.
1) The query tree is formed of a single node; and, in the node of the query tree, “Part3” is stored as an element name, and “” is stored as a text-data matching condition.
2) Through the processing shown in FIG. 10, a temporary node is attached to the node of “Part3” in the hierarchical index. Further, the query link of the nodes to which a temporary node has been attached is linked to the node of the query tree (see FIG. 17A).
3) Since the query tree for Search Request 2 also fails to satisfy the conditions of the processing in step S77 shown in FIG. 10, there is created a state in which nothing is present in the stack. Here, the conditions of the processing in step S81 shown in FIG. 11 are satisfied, and through processing in step S810, the temporary nodes provided in 2) above are rendered child nodes of an OR node (see FIG. 17B).
4) The form of the Boolean logic tree assembled in 3) above is regulated by means of the processing in step S811 shown in FIG. 11, and is converted to a character string by means of the processing in step S63 shown in FIG. 9, so that the following Boolean expression is obtained ultimately.
“^” appears at the 7th position of Document 1, and at the 7th position of Document 2;
“” appears at the 8th position of Document 1, and at the 8th position of Document 2;
“$” appears at the 9th position of Document 1, and at the 9th position of Document 2; and
1) As shown in FIG. 18A, the query tree is formed of three nodes; and the respective nodes store the following data:
Element name: “Document”, text-data matching condition: none (no text-data matching condition is required to be set for the parent node of the query tree);
Element name: “Part1”, text-data matching condition: “” and
Element name: “Part2”, text-data matching condition: “?!”;
For these nodes, the processing shown in FIG. 10 is performed, while the priority is given in their depth.
2) First, the node having the element name “Document” is first processed. Since the conditions of the processing in step S77 shown in FIG. 10 are satisfied, through processing in step S78, through processing in step S78, the corresponding node of the hierarchical index is stored in the stack 42. Further, through processing in step S79, the query link of the node stored in the stack 42 is extended to the corresponding node of the query tree (see FIG. 18A).
3) Subsequently, the node having the element name “Part1” is processed, and temporary nodes are attached to the nodes of “Part1” through processing in step S711. The nodes having an element name “Part2” are processed in a similar manner (see FIG. 18A).
4) Since one node is stored in the stack 42, this node is removed from the stack 42 through processing in step S82 shown in FIG. 11.
5) The processing in step S83 is performed for temporary nodes lower in level than the removed node, in order to render temporary nodes having the same query link child nodes of an OR node (see FIG. 19).
6) Subsequently, through the processing in step S84, among the above-described OR nodes, OR nodes which are linked, via query links, to nodes which share the same parent node are rendered child nodes of an AND node (see FIG. 20).
7) Since search conditions do not contain the “sibling order relationship,” the processing in step S87 is not performed, and through the processing in step S89, the above-described AND node is attached to the node removed from the stack 42 (see FIG. 21A).
8) Since the stack 42 becomes empty at this point in time, through processing in step S810, the AND node described in 7) above is rendered a child node of an OR node (see FIG. 21B).
9) The form of the Boolean logic tree assembled in 8) above is regulated by means of the processing in step S811 shown in FIG. 11. Subsequently (see FIG. 21C), the Boolean logic tree is converted to a character string by means of the processing in step S63 shown in FIG. 9, so that the following Boolean expression is obtained ultimately.
1) As in the case of Search Request 4, temporary nodes are attached to the nodes of “Part1” and “Part2,” and the node corresponding to the parent node of the query tree is stored in the stack 42. Further, through processing in steps S83 and 84, a logic expression including OR nodes and an AND node is assembled (see FIG. 22).
2) Through processing in step S87 shown in FIG. 11, the links among the OR and AND nodes are re-formed in accordance with a logic expression distribution rule, so that the logic expression is converted into the disjunctive normal form (see FIG. 23).
3) With reference to information regarding the offsets of the nodes of the hierarchical index, to which nodes are attached the children nodes of each of the AND nodes, an AND node or nodes which is in FIG. 23 and fail to satisfy the sibling relationship with order are discarded. In the example shown in FIG. 23, only the leftmost AND node satisfies the sibling relationship with order, and therefore, the remaining AND nodes are discarded (See FIG. 24A).
4) The processing in step S87 and subsequent steps is the same as the case of Search Request 4. That is, upon completion of the processing in step S811 shown in FIG. 11, the logic tree shown in FIG. 24B is obtained. The logic tree is converted to a character string by means of the processing in step S63 shown in FIG. 9, so that the following Boolean expression is obtained ultimately.
1) As shown in FIG. 27, the query tree is formed of five nodes and includes a two-level sibling relationship such that the “Author” node is a parent of the “Name” node and the “Section” node, and the “Document” node is a parent of the “Author” node and the “Title” node. First, the “Document” node is processed. Since the “Document” node satisfies the conditions of the processing in step S77 shown in FIG. 10, the corresponding node of the hierarchical index is pushed into the stack 42 (see FIG. 27).
2) Next, the “Author” node is processed, so that the corresponding nodes of the hierarchical index are pushed into the stack 42 as in the case of the “Document” node. The order in which corresponding nodes are pushed into the stack 42 is the reverse of the order in which the element links are followed (see FIG. 28).
3) Subsequently, the “Name” node, the “Section” node, and the “Title” node are processed, in this sequence, and temporary nodes are attached to the corresponding nodes of the hierarchical index (see FIG. 29). In the example shown in FIG. 29, links which will not be described are omitted in order to simplify the description.
4) The nodes stored in the stack 42 are removed successively, and temporary nodes under the node just removed are rendered child nodes of OR and AND nodes. At this time, since the nodes under node (element name: “Author”/offset: 0/part-ID: 8) fail to satisfy the conditions of AND nodes defined in the processing in step S88 shown in FIG. 11, the nodes under the node (element name: “Author”/offset: 0/part-ID: 8) are discarded (see FIG. 30).
5) Subsequently, through the processing in steps S83 and 84 shown in FIG. 11, temporary nodes lower in level than the node of the hierarchical index corresponding to the “Document” node are rendered child nodes of OR and AND nodes (see FIG. 31).
6) Upon completion of the processing in step S811 shown in FIG. 11, the logic tree shown in FIG. 32 is obtained. The logic tree is converted to a character string by means of the processing in step S63 shown in FIG. 9, so that the following Boolean expression is obtained ultimately.
(((“YAMADA TARO”@3 AND “SHIBUYA RESEARCH CENTER”@4) OR (“YAMADA TARO”@6 AND “SHIBUYA RESEARCH CENTER”@7))
AND (“STRUCTURED DOCUMENT”@1 OR “STRUCTURED DOCUMENT”@10))
1) The sibling order relationship among document parts is included in the search request, and then the processing in step S87 shown in FIG. 11 is performed. That is, since all the documents satisfy the condition of “Name” preceding “Section,” the processing up to the processing in 4) above for Search Request 6 (the example shown in FIG. 30) is performed in the same manner.
2) Subsequently, when the processing in steps S83 and S84 is performed for temporary nodes lower in level than the node of the hierarchical index corresponding to the “Document” node, the logic tree shown in FIG. 33 is assembled.
3) When the logic tree shown in FIG. 33 is converted to the disjunctive normal form, the state shown in FIG. 34 is obtained. Since AND nodes other than the second AND node as counted from the right fail to satisfy the order relationship, the AND nodes other than the second AND node are discarded.
4) Ultimately, the logic tree shown in FIG. 35 is assembled, and the logic tree is converted to a character string by means of the processing in step S63 shown in FIG. 9, so that the following Boolean expression is obtained.
((“YAMADA TARO”@3 AND “SHIBUYA RESEARCH CENTER”@4) AND “STRUCTURED DOCUMENT”@10)
The text index shown in FIG. 26 is referred to by use of the thus-obtained Boolean expression, so that a message “no document found” is obtained as a search result.
first store means for storing a hierarchical index that represents a hierarchical relationship among document parts and is expressed in a tree structure in which each of a plurality of meta parts forms a single node, the document parts being elements of each of the structured documents, and the document parts that are common in structure among the structured documents being regarded as the meta parts;
second store means for storing a text index in which information representing a relationship between a set and a document-ID is registered, the set having a character string in text data and a part-ID identifying a meta part, and the document-ID being an ID of a document in which the character string and the meta part appear; and
search means for searching a structure from the hierarchical index on the basis of a query tree that represents a query in the tree structure, and for searching a document corresponding to the query tree by referring to the text index on the basis of a search result on the structure, the query designating search conditions that express relationships among the document parts, including a sibling relationship in the tree structure, the search means comprising
first refer means for referring to the hierarchical index and for converting the query tree to a Boolean expression in which a set having a character string and a part-ID is used as a single search key, and
second refer means for referring to the text index and for obtaining a document-ID of a document corresponding to the query tree by use of the Boolean expression, hierarchical index creating means for judging, for corresponding document parts of respective structured documents to be subjected to search, whether the document parts are meta parts that satisfy conditions in which each of the nodes shares a common upper meta part and has a same element name and a same offset in a row of sibling parts in the document, the hierarchical index creating means setting, for the node information regarding the offset in the row of sibling parts in the document, a link extending from a child node to a parent node, and a link extending to another node having the same element name by assigning a part-ID to the document parts and registering as a node of the hierarchical index, when the document parts are meta parts.
2. A structured-document search apparatus according to claim 1,
wherein, in the query, either a sibling relationship with order or a sibling relationship without order among the document parts is selectively designated, and
wherein the search means performs matching between the query tree and the hierarchical index on the basis of a designated one of the sibling relationship with order and the sibling relationship without order.
3. A structured-document search apparatus according to claim 1, wherein the search means converts to a Boolean expression the search conditions that are expressed in the form of a query tree and that contain a sibling relationship among the document parts.
wherein nodes of the same meta parts in the hierarchical index are generated with each of the nodes sharing a common upper meta part and having a same element name and a same offset in a row of sibling parts in the document, and
5. A structured-document search apparatus according to claim 1, wherein the search means inputs as a search request the query in which relationships among document parts, including a sibling relationship, are expressed in the tree structure and which designates the search conditions, and searches on the basis of the query tree that represents the query in the tree structure.
text index creating means for creating a special key composed of a special character string and a part-ID, and for registering in the text index, for each document part, when a set composed of a character string in text data and a part-ID is created.
7. A structured-document search apparatus according to claim 1, further comprising:
text index creating means for creating pseudo text data, which are obtained through addition of special character strings at a start and an end position of the text data, and for creating a search key to be registered in the text index created from the pseudo text data, for each text data, when a set composed of a character string in text data and a part-ID is created.
8. A structured-document search apparatus according to claim 1, further comprising:
9. A structured-document search method for searching structures and text data of structured documents, the method comprising:
matching a structure of a query tree and a structure of a hierarchical index in which a hierarchical relationship among document parts of each of the structured documents to be searched is expressed in a tree structure in which a meta part is treated as a single node, and generating a search key with a character string and a part-ID identifying the meta part on the basis of a matched portion, the query tree representing a query in the tree structure, the query being expressed in the tree structure and designating relationships among the document parts, which are elements of the structured document, as a search condition;
on the basis of the search key, referring to a text index in which is registered information representing a relationship between sets having a part-ID of a meta part and a character string in text data of a structured document to be searched and a document-ID of a document in which the character string appears; and
searching a document corresponding to the query tree, said searching comprising
referring to the hierarchical index and converting the query tree to a Boolean expression in which a set having a character string and a part-ID is used as a single search key, and
referring to the text index and obtaining a document-ID of a document corresponding to the query tree by use of the Boolean expression, hierarchical index creating for judging, for corresponding document parts of respective structured documents to be subjected to search, whether the document parts are meta parts that satisfy conditions in which each of the nodes shares a common upper meta part and has a same element name and a same offset in a row of sibling parts in the document, the hierarchical index creating for setting, for the node information regarding the offset in the row of sibling parts in the document, a link extending from a child node to a parent node, and a link extending to another node having the same element name by assigning a part-ID to the document parts and registering as a node of the hierarchical index, when the document parts are meta parts.
10. A structured-document search method according to claim 9, the method further comprising:
inputting as a search request the query that is expressed in the tree structure and in which a sibling relationship among the document parts, which are elements of the structured document, are designated as the search condition, and creating the query tree that represents the query in the tree structure.
11. A computer-readable storage controlling a computer to search structures and text data of structured documents, and comprising a process of:
matching a structure of a query tree and a structure of a hierarchical index in which a hierarchical relationship among document parts of each of the structured documents to be searched is expressed in a tree structure in which a meta part is treated as a single node, and generating a search key having a character string and a part-ID identifying the meta part on the basis of a matched portion, the query tree representing a query in the tree structure, the query being expressed in the tree structure and designating relationships among the document parts, which are elements of the structured documents, as a search condition;
referring, on the basis of the search key, to a text index in which is registered information representing a relationship between sets having a part-ID of a meta part and a character string in text data of a structured document to be searched and a document-ID of a document in which the character string appears; and
12. A computer-readable storage according to claim 11, further comprising:
inputting as a search request the query which is expressed in the tree structure and in which a sibling relationship among document parts, which are elements of the structured documents, are designated as the search condition, and creating the query tree the represents the query in the tree structure.
13. A method for creating an index used in a structured-document search apparatus for searching structures and text data of structured documents,
wherein the structured-document search apparatus receives as a search request a query in which document parts, which are elements of the structured documents, are expressed in a tree structure with a query tree representing a query in the tree structure, refers to a hierarchical index in which a hierarchical relationship among document parts of each of the structured documents to be searched is expressed in the tree structure in which a meta part is treated as a single node, and refers to a text index that stores a search key having a character string in text data and a part-ID identifying a meta part and stores a document-ID of a document in which the search key appears, to search structures and text data of structured documents,
judgment is made for corresponding document parts of respective structured documents to be subjected to searching whether the document parts are meta parts that satisfy conditions in which each of one or more nodes shares a common upper meta part and has a same element name and a same offset in a row of sibling parts in the structured document, and
when the document parts are meta parts, a part-ID is assigned to the document parts, which are registered as a node of the hierarchical index, and set for the node information regarding the offset in a row of sibling parts in the document, a link extending from a child node to a parent node, and a link extending to another node having the same element name and
wherein searching a document comprises
14. A method for creating an index used in a structured-document search apparatus for searching structures and text data of structured documents,
wherein the apparatus inputs as a search request a query in which document parts, which are elements of the structured documents, are expressed in a tree structure with a query tree representing a query in the tree structure, the apparatus referring to a hierarchical index in which a hierarchical relationship among the document parts of each of the structured documents to be searched is expressed in the tree structure in which a meta part is treated as a single node and referring to a text index that stores a search key composed of a character string in text data and a part-ID identifying a meta part and stores a document-ID of a document in which the search key appears, to search structures and text data of the structured documents,
wherein, when a set comprising a character string in text data and a part-ID is created during creation of the text index, for each document part, a special key comprising a special character string and a part-ID is created and registered in the text index, and
15. A method for creating an index used in a structured-document search apparatus for searching structures and text data of structured documents,
wherein the apparatus inputs as a search request a query in which document parts, which are elements of the structured documents, are expressed in a tree structure with a query tree representing a query in the tree structure, the apparatus referring to a hierarchical index in which a hierarchical relationship among the document parts of each of the structured documents to be searched is expressed in a tree structure in which a meta part is treated as a single node and referring to a text index that stores a search key comprising a character string in text data and a part-ID identifying a meta part and stores a document-ID of a document in which the search key appears, to search structures and text data of the structured documents,
wherein, when a set comprising a character string in text data and a part-ID is created during creation of the text index, for each text data, pseudo text data that are obtained through addition of special character strings at a start and an end position of the text data are created and the search key to be registered in the text index is created from the pseudo text data, and
16. A structured-document search apparatus for searching structures and text data of structured documents, the apparatus comprising:
a first store unit storing a hierarchical index that represents a hierarchical relationship among document parts and is expressed in a tree structure in which each of a plurality of meta parts forms a single node, the document parts being elements of each of the structured documents, and the document parts that are common in structure among the structured documents being regarded as the meta parts;
a second store unit storing a text index in which information representing a relationship between a set and a document-ID is registered, the set having a character string in text data and a part-ID identifying a meta part, and the document-ID being an ID of a document in which the character string and the meta part appear; and
a search unit searching a structure from the hierarchical index on the basis of a query tree that represents a query in the tree structure, and for searching a document corresponding to the query tree by referring to the text index on the basis of a search result on the structure, the query designating search conditions that express relationships among the document parts, including a sibling relationship in the tree structure, the search unit comprising
a first refer unit referring to the hierarchical index and converting the query tree to a Boolean expression in which a set having a character string and a part-ID is used as a single search key, and
a second refer unit referring to the text index and obtaining a document-ID of a document corresponding to the query tree by use of the Boolean expression, hierarchical index creating for judging, for corresponding document parts of respective structured documents to be subjected to search, whether the document parts are meta parts that satisfy conditions in which each of the nodes shares a common upper meta part and has a same element name and a same offset in a row of sibling parts in the document, the hierarchical index creating for setting, for the node information regarding the offset in the row of sibling parts in the document, a link extending from a child node to a parent node, and a link extending to another node having the same element name by assigning a part-ID to the document parts and registering as a node of the hierarchical index, when the document parts are meta parts.
17. A method for creating an index used in a structured-document search apparatus for searching structures and text data of structured documents, comprising:
receiving as a search request, by the structured-document search apparatus, a query in which document parts, which are elements of the structured documents, are expressed in a tree structure with a query tree representing a query in the tree structure, referring to a hierarchical index in which a hierarchical relationship among document parts of each the structured documents to be searched is expressed in the tree structure in which a meta part is treated as a single node, and referring to a text index that stores a search key having a character string in text data and a part-ID identifying a meta part and stores a document-ID of a document in which the search key appears;
determining, when the hierarchical index is created, for corresponding document parts of respective structured documents to be subjected to searching, whether the document parts are meta parts that satisfy conditions in which each of one or more nodes shares a common upper meta part and has a same element name and a same offset in a row of sibling parts in the structured document; and
assigning, when the document parts are meta parts, a part-ID to the document parts, which are registered as a node of the hierarchical index, and setting a link extending from a child node to a parent node and a link extending to another node having the same element name as node information regarding the offset in a row of sibling parts in the document,
18. A method for creating an index used in a structured-document search apparatus for searching structures and text data of structured documents, comprising:
inputting as a search request, by the apparatus, a query in which document parts, which are elements of the structured documents, are expressed in a tree structure with a query tree representing a query in the tree structure, referring to a hierarchical index in which a hierarchical relationship among the document parts of each of the structured documents to be searched is expressed in the tree structure in which a meta part is treated as a single node, and referring to a text index that stores a search key composed of a character string in text data and a part-ID identifying a meta part and stores a document-ID of a document in which the search key appears; and
creating, when a set comprising a character string in text data and a part-ID is created during creation of the text index, for each document part, a special key comprising a special character string and a part-ID and registering the special key in the text index,
19. A method for creating an index used in a structured-document search apparatus for searching structures and text data of structured documents,
inputting as a search request, by the apparatus, a query in which document parts, which are elements of the structured documents, are expressed in a tree structure with a query tree representing a query in the tree structure, the apparatus referring to a hierarchical index in which a hierarchical relationship among the document parts of each of the structured documents to be searched is expressed in a tree structure in which a meta part is treated as a single node and referring to a text index that stores a search key comprising a character string in text data and a part-ID identifying a meta part and stores a document-ID of a document in which the search key appears; and
creating, when a set comprising a character string in text data and a part-ID is created during creation of the text index, for each text data, pseudo text data that are obtained through addition of special character strings at a start and an end position of the text data, the search key to be registered in the text index being created from the pseudo text data,
US20010007987A1 true US20010007987A1 (en) 2001-07-12
US6853992B2 true US6853992B2 (en) 2005-02-08
US20070073662A1 (en) * 2005-09-28 2007-03-29 Brother Kogyo Kabushiki Kaisha Data transmission system, device, and method
JP4374014B2 (en) * 2006-11-21 2009-12-02 株式会社日立製作所 Index generation apparatus and the program
JP5594120B2 (en) * 2010-12-17 2014-09-24 富士通株式会社 Data conversion program, the data conversion apparatus and data conversion method
JP6102594B2 (en) 2013-07-16 2017-03-29 富士通株式会社 Data output method, and a data output program
JP6136685B2 (en) 2013-07-16 2017-05-31 富士通株式会社 Data extraction methods and data extraction program
JPH0746908A (en) 1994-06-08 1995-02-21 Yanmar Agricult Equip Co Ltd Fertilizer applicator and seeder
JPH1153400A (en) 1997-07-31 1999-02-26 Nec Corp Structured document retrieval device and machine readable recording medium for recording program
JPH11242676A (en) 1998-02-25 1999-09-07 Hitachi Ltd Method for registering structured document, method for retrieving structured document, and portable medium used in these methods
US8468468B2 (en) * 2005-09-28 2013-06-18 Brother Kogyo Kabushiki Kaisha Data transmission system, device, and method
US20010007987A1 (en) 2001-07-12 application