JP2008146424A - Method for calculating conformity of XML document, program thereof, and information processing apparatus - Google Patents

Abstract

Processing is performed at high speed when a path and a search word are input to calculate the degree of fitness for an accumulated XML document.
In an information processing apparatus that accumulates a plurality of XML documents and ranks the XML documents based on a path and a search word, a storage unit stores path information, node information, and word information. ing. The path information stores path statistical information, which is statistical information related to a set of partial documents under each path, as information for each path.
The processing unit updates the path information including the path statistical information before the path and the search word are input, so there is no need to calculate the path statistical information when calculating the degree of matching, and the search can be performed at high speed. Can be processed.
[Selection] Figure 1

Description

  The present invention relates to a technique for calculating a fitness for a search query (query) having a path and a search word with respect to a plurality of stored XML (eXtensible Markup Language) documents.

In recent years, when a document is created by a computer device, XML, which is one of markup languages, is often used. This is because an XML document (hereinafter simply referred to as “document”) that is a document created by XML has many advantages.
For example, an XML document is easy to use because the contents of tags for expressing and managing the structure of the document can be defined by the user, and has a hierarchical structure and is suitable for data organization. Furthermore, since the XML document is text data instead of binary data, the user can easily confirm the contents of the data, and since it is certified as a global standard, it is compatible with many other applications.

  As the number of XML documents increases, the necessity of improving the accuracy and speed of searching for a plurality of stored XML documents is increasing. Hereinafter, the ranking performed based on the suitability of documents with respect to a search query is referred to as ranking. Further, at the time of search, a score is calculated using some statistic regarding the appearance of a search word in a document, and ranking is performed according to the magnitude relation of the score.

As a ranking technique for accumulated documents, a technique for statistically analyzing the description contents of the document is often used (see, for example, Non-Patent Document 1).
As statistics used for calculating the score, generally, “statistics for the entire document set (average of all document lengths (hereinafter referred to as“ average length ”)”), “statistics for each document” “Amount (length of each document, etc.)” and “Statistics for search word (frequency of appearance of search word in each document)” are used.

  Further, when an efficient search is to be performed on an XML document, it is necessary to be able to quickly extract description contents necessary for the search from the XML document that is structured data. Therefore, in general, an index (structure index) that records the structure and description contents of an XML document is constructed in advance. There are various methods for constructing the structure index. In many cases, all paths (strings indicating the location of data, such as “/ book / chapter / section”) and their paths are included in the XML document. A path index for associating description contents corresponding to is constructed (see, for example, Patent Document 1).

  Since the XML document has a meaning in its structure, it is desirable to perform ranking for the XML document by using the structure of the XML document. This is because highly accurate search results can be expected. That is, in ranking XML documents, it is preferable to calculate scores in units of partial documents (part of XML documents) instead of calculating scores in units of documents as was done during conventional ranking.

That is, as the statistic used for calculating the score related to the ranking of the XML document, “statistics for the entire partial document set” instead of “statistics for the entire document set”, and “statistics for each document” instead of “statistics for each document”. It is desirable to use “statistics for each subdocument”. As for “statistics for search words”, for example, it is better to identify the appearance position in more detail rather than in document units.
Kishida Kazuaki and two others, “Method and Practice of Search Experiment: Trial at NTCIR Workshop”, Pre-meeting Lecture at the NTCIR-3 Workshop, October 8, 2002, p.9-10 JP 2006-228155 A

However, the above-mentioned “statistics for the entire partial document set”, “statistics for each partial document”, and “statistics for the search word” vary depending on the contents of the search query. This is because the range of the corresponding partial document changes depending on the content of the path in the search query.
Therefore, in the related art including the above-described Non-Patent Document 1 and Patent Document 1, the statistics must be calculated for each search (ranking), and the calculation cost becomes enormous when the accumulated XML documents become large. As a result, there is a problem that the processing becomes slow (details are described at the beginning of “Best Mode for Carrying Out the Invention”).

  Therefore, the present invention has been made in view of the above-described problems, and performs processing at high speed when calculating the degree of matching by specifying a path and a search word for an accumulated XML document. With the goal.

In order to solve the above-mentioned problem, the invention according to claim 1 and claim 6 is characterized in that the information processing apparatus stores path information for storing information in units of paths related to a plurality of XML documents, and between nodes in each XML document for each XML document. Node information for storing the relationship information, and word information for storing the appearance position information of each word used in the plurality of XML documents, and pass information in units of paths for the plurality of XML documents. Used in one of a plurality of XML documents, a path index part for storing information, a node management part for analyzing a relation including a parent-child relation between nodes in each XML document, and storing the relation information in node information, and a plurality of XML documents Text index for storing a word in the word information in association with the appearance position information including the document ID of the XML document in which the word is used Comprises a section, when the path and the search word is entered, for a plurality of XML documents, a ranking unit for calculating a goodness of fit of the search word in the document partial document is a subordinate of the input paths, a.
The path information stores path statistical information, which is statistical information related to a set of partial documents under each path, as path unit information. The path index unit stores a path and a search word before input. The path information including path statistical information is updated with respect to a plurality of stored XML documents, and the ranking unit inputs path information including path statistical information, node information, and words after a path and a search word are input. With reference to the information, the degree of conformity for a plurality of XML documents is calculated based on the path and the search word.

  According to this invention, it is possible to calculate and store path statistical information, which is a statistic of the entire partial document set, before inputting a path and a search word, and use the path statistical information to conform to an XML document. The degree calculation process can be performed at high speed.

According to the second and seventh aspects of the present invention, the information processing apparatus stores path information for storing path unit information regarding a plurality of XML documents, and node information for storing relationship information between nodes in each XML document for each XML document. And a storage unit that stores word information for storing appearance position information of each word used in a plurality of XML documents, and a path index unit for storing path unit information in the path information for the plurality of XML documents, , A node management unit for analyzing a relationship including a parent-child relationship between nodes in each XML document and storing the relationship information in the node information, and a word used in one of the plurality of XML documents. A text index part to be stored in the word information in association with the appearance position information including the document ID of the XML document, and the path and the search word When it is, for a plurality of XML documents, comprising a ranking unit for calculating a goodness of fit of the search word in the document partial document is a subordinate of the input paths, a.
The node information stores, as information for each node, node statistical information that is statistical information regarding partial documents under each node, and the node management unit before the path and the search word are input The node information including the node statistical information is updated, and after the path and the search word are input, the ranking unit refers to the path information, the node information including the node statistical information, and the word information. Based on the above, the degree of fitness for a plurality of XML documents is calculated.

  According to this invention, it is possible to calculate and store node statistical information, which is a statistic for each partial document, before inputting a path and a search word. Can be performed at high speed.

In the inventions according to claims 3 and 8, the information processing apparatus stores path information for storing path unit information regarding a plurality of XML documents, and node information for storing relation information between nodes in each XML document for each XML document. And a storage unit that stores word information for storing appearance position information of each word used in a plurality of XML documents, and a path index unit for storing path unit information in the path information for the plurality of XML documents, , A node management unit for analyzing a relationship including a parent-child relationship between nodes in each XML document and storing the relationship information in the node information, and a word used in one of the plurality of XML documents. A text index part to be stored in the word information in association with the appearance position information including the document ID of the XML document, and the path and the search word When it is, for a plurality of XML documents, comprising a ranking unit for calculating a goodness of fit of the search word in the document partial document is a subordinate of the input paths, a.
The word information stores, as the appearance position information, the node position information where the word appears together with the document ID of the XML document, and the text index portion stores the node position before the path and the search word are input. The word information including information is updated, and the ranking unit refers to the word information including the path information, the node information, and the node position information after the path and the search word are input, and based on the path and the search word. The degree of conformity for a plurality of XML documents is calculated.

  According to this invention, it is possible to calculate and store the appearance position information, which is a statistic for the search word, before inputting the path and the search word, and by using the appearance position information, the fitness level of the XML document can be calculated. The calculation process can be performed at high speed.

  The invention according to claim 4 and claim 9 is that in the information processing apparatus, the node management unit provides the start label value and the end label value for each node as the relationship information between the nodes, and the start label value of the parent node is a child. It is assigned to satisfy the relationship that it is smaller than the start label value of the node and the end label value of the parent node is larger than the end label value of the child node, and stored in the node information. As the node position information, the start label value and the end label value in the node information are given, and the ranking unit is based on the start label value and the end label value of each node in the node information when the path and the search word are input. The range of the partial document corresponding to the path is determined, and the matching degree of the search word with respect to the partial document is calculated.

  According to this invention, the range of the partial document can be determined based on the start label value and the end label value in the node information and the word information.

  In the invention according to claim 5, in the information processing apparatus, the storage unit further stores text information for storing the text data of the node having the text data in the XML document in association with the identification information of the text data. The node associates the identification information of the subordinate text data for each node in the node information, and the ranking unit determines the path based on the identification information of the text data in the node information when the path and the search word are input. The range of the partial document corresponding to is determined, and the degree of matching of the search word with respect to the partial document is calculated.

  According to this invention, the range of the partial document can be determined based on the identification information of the text data.

  The invention according to claim 10 is a program that causes a computer to execute the method for calculating the conformity of an XML document according to any one of claims 1 to 5.

  According to this invention, it is possible to cause a computer to execute a method for calculating the conformity of an XML document.

  According to the present invention, it is possible to perform processing at high speed when calculating a fitness level by specifying a path and a search word for an accumulated XML document.

Hereinafter, an information processing apparatus, a method for calculating the conformity of an XML document, and a best mode for carrying out the program (hereinafter referred to as an embodiment) will be described with reference to the drawings as appropriate. Note that drawings other than the reference diagram are also referred to as appropriate.
Before that, in order to facilitate understanding, comparative examples (prior art) and terms will be described with reference to FIGS.

FIG. 21 shows a ranking example using statistical information of a comparative example. (A) is a document example, (b) is a calculation example 1 of the fitness (ranking), and (c) is a calculation of the fitness. 10 is an explanatory diagram of Example 2. FIG.
As shown in FIG. 21A, here, a case will be described in which three documents (documents 01 to 03) are searched using the word “patent”. Note that the document here may or may not be an XML document. Further, the number of occurrences of the search word in the three documents and the text length of the document are as illustrated.

FIG. 21B shows a result of ranking by the number of appearances of the search word. FIG. 21C shows the result of ranking by the appearance frequency (number of appearances / text length) of the search word.
In the comparative example, generally, an index (text index) is recorded in which the above-described statistics (number of appearances and appearance frequency of search words) and word appearance position (appearance document identifier) are recorded. And at the time of a search, the appearance position of a search word can be pinpointed by using the constructed text index, and a high-speed score calculation can be performed.
When a plurality of words are included in the search character string, a score is calculated for each word, and those scores may be integrated by a predetermined calculation formula.

Next, the structure of an XML document that is structured data will be described with reference to FIG. 22A is a simplified diagram of an example of source code of an XML document, and FIG. 22B is a diagram illustrating a structure (tree structure) of the XML document.
As illustrated in FIG. 22A, in the source code of the XML document 001, a mark (such as “<book>”) used to identify a component of the XML document is referred to as a tag.

  Further, as shown in FIG. 22B, the XML document has a tree structure such as a directory structure, and each element (node) is a path (such as “/ book / chapter”). ). In each node, “n11” to “n13” are child nodes of the node “n1”, “n121” to “n124” are child nodes of the node “n12”, and so on. Reference numerals are attached (the same applies to other drawings).

In this way, since the XML document is given the meaning (attribute) of each description content by the tag separately from the description content, it is possible to search from a large XML document by specifying a path together with a word and performing a search. The necessary part can be taken out. As described above, a part of a document extracted from one XML document is referred to as a partial document.
In the example of FIG. 22, the XML document 001 represents book data. If only the title description content of this book is to be extracted, only the title description content is specified by specifying the path as “/ book / title”. Can be taken out.

  Also, as shown in FIG. 22B, in the XML document 001, the description content of the book is stored for each chapter under the “/ book”. If you want to take out a partial document in which the word “Earth” is written in detail from the XML document 001, for example, if you want to investigate every chapter, for “text” under “/ book / chapter” A search may be made with the word “Earth”. If you want to investigate every section that is more detailed than a chapter, you can search for the word “Earth” for “text” under “/ book / chapter / section”. In either case, the partial document with a high score becomes the partial document with the highest ranking.

Next, with reference to FIG. 23, differences in partial documents due to differences in path designation (path contents) will be described. (A) and (b) of FIG. 23 are diagrams showing ranges of partial documents by respective paths in the example of the structure of FIG. 22 (b).
As shown in FIG. 23A, if the path is designated as “/ book / chapter”, nodes under each “chapter” (n12, n13, etc.) become partial documents. On the other hand, as shown in FIG. 23B, if the path is designated as “/ book / chapter / section”, nodes under each “section” (such as n124) become partial documents. In this way, the range of partial documents differs depending on the contents of the path.

Next, another example of a difference in partial documents due to a difference in path designation will be described with reference to FIG. (A) and (b) of FIG. 24 are diagrams showing ranges of partial documents by respective paths in the example of FIG. 22 (b).
As shown in FIG. 24A, if the path is designated as “/ book / title”, only one location shown by a broken line becomes a corresponding partial document. On the other hand, as shown in FIG. 24B, if the path is designated as “arbitrary title”, three (or more) locations indicated by broken lines become corresponding partial documents.

  In this way, since the corresponding partial document changes depending on the content of the path in the search query, each time the content of the path changes, the “statistics for the entire partial document set”, “statistics for each partial document”, and “ The “statistics for search words” will also change. Therefore, in the comparative example, the statistics had to be calculated for each search. In particular, as the number of stored XML documents increases, the calculation cost of those statistics values increases.

Next, the information processing apparatus, the XML document fitness calculation method, and the program thereof according to each embodiment of the present invention will be described with reference to FIGS.
First, BM25 (see “3.3.1 Okapi” in Non-Patent Document 1), which is a score calculation formula used in the ranking method of the present embodiment, will be described. When this BM25 is used, the calculation formula of the score S _qki of the word i in the document k is given by the following formula (1).

ここで、各記号の意味は次の通りである。
Ｌ：（部分）文書集合全体の平均長さ（部分文書集合全体の統計量。パス統計情報）
Ｎ：（部分）文書の総数（部分文書集合全体の統計量。パス統計情報）
ｌ_ｋ：（部分）文書ｋの長さ（部分文書の統計量。ノード統計情報）
ｔｆ_ｋｉ：（部分）文書ｋ中の単語ｉの出現回数（単語の統計量）
ｎ_ｉ：該当する単語ｉを含む（部分）文書数（単語の統計量）
ｌ_ｑ：検索文字列ｑの長さ
ｔｆ_ｑｉ：検索文字列ｑ中の検索単語ｉの出現回数

Here, the meaning of each symbol is as follows.
L: (Partial) Average length of the entire document set (Statistics of the entire partial document set. Path statistical information)
N: Total number of (partial) documents (statistics of the entire partial document set, path statistical information)
l _k : (partial) length of document k (statistics of partial document; node statistical information)
tf _ki : (partial) number of occurrences of word i in document k (word statistic)
n _i : Number of (partial) documents including the corresponding word i (word statistics)
l _q : Length of search character string q tf _qi : Number of appearances of search word i in search character string q

(First embodiment)
FIG. 1 is a configuration diagram of an information processing apparatus according to the first embodiment of the present invention. As illustrated in FIG. 1, the information processing apparatus 1 according to the first embodiment is a computer apparatus, and includes an input unit 2, an output unit 3, a memory 4, a storage unit 5, and a processing unit 6.

  The input unit 2 performs data input, and is, for example, a keyboard, a mouse, a communication interface, or the like. A user of the information processing apparatus 1 (hereinafter simply referred to as “user”) can input an XML document or a search query (path and search character string) using the input unit 2. In the present embodiment, it is assumed that the user understands the structure and description contents of the XML document to some extent, and specifies not only a character string but also a path as a search query.

The output unit 3 outputs data, and is, for example, a display or a speaker. The output unit 3 outputs a ranking result or the like by searching the XML document.
The memory 4 is a work area of the processing unit 6 and is, for example, a RAM (Random Access Memory).

The storage unit 5 stores data and is, for example, a hard disk. The storage unit 5 is, for example, a so-called relational database in which one piece of data is expressed as a set of a plurality of items (fields) and the set of data is expressed as a table. The storage unit 5 is an XML document group 51 for storing an XML document input from the input unit 2, a path table PT (Path Table. Path information; details will be described later with reference to FIG. 4B), and a node table NT (Node Table. Node information (details will be described later in FIG. 4A) and an inverted table IT (Inverted Table. Word information. Details are described later in FIG. 5) are stored.
Although not shown in the figure, the storage unit 5 stores a program describing a method for calculating the conformity of an XML document to be described later.

  The processing unit 6 performs various arithmetic processes, and is, for example, a CPU (Central Processing Unit). The processing unit 6 includes a data storage unit 61, a path index unit 62, a range label unit 63 (node management unit), a text index unit 64, and a ranking unit 65 as its functions. In the following, when the processing unit 6 fulfills functions other than these functions, the operation subject is described as the processing unit 6.

The data storage unit 61 stores the XML document input from the input unit 2 in the XML document group 51.
Based on the information of the XML document input from the input unit 2, the path index unit 62 uses the statistics of each path (the average length (L) of the entire partial document set) in the path table PT (see FIG. 4B). , The number of partial documents (N)) is updated.

  The range label unit 63 assigns a range label (binary ID (IDentification) of start label (value) “pre” and end label (value) “post”, relation information, appearance position information, node position information) to each node. Assigned and recorded in the node table NT (see FIG. 4A). By labeling each node so that the range label of the child node is a value between “pre” and “post” of the range label of the parent node, the upper and lower (parent-child) relationship between each node can be understood. (See Patent Document 1).

  Here, the range label will be described with reference to FIGS. 2 and 3. FIG. 2 is a diagram illustrating an example of source code of an XML document. (A) is a diagram related to an XML document 001 similar to FIG. 22, and (b) is a diagram related to an XML document 002 as another example. is there. As shown in FIGS. 2A and 2B, both XML documents are data relating to a book.

FIG. 3A is a diagram showing a state where a range label is assigned to the XML document 001, and FIG. 3B is a diagram showing a state where a range label is assigned to the XML document 002.
As shown in FIG. 3A, in the XML document 001, the node n1 (book) has a range label (1,99) (the start label “pre” is “1” and the end label “post” is “99”). In the same manner, it can be seen that it is the parent of the node n11 whose range label is (2, 5). Also, it can be seen that the node n11 has a range label of (2, 5) and does not have a vertical (parent-child) relationship with the node n12 whose range label is (6, 47). Similarly, for the XML document 002 shown in FIG. 3B, a range label is assigned to each node.

Returning to FIG. 1, the text index unit 64 records the appearance positions (document IDs and range labels) of all words appearing in the XML document input from the input unit 2 in the transposition table IT.
The ranking unit 65 extracts statistical information and the like from the path table PT, the node table NT, and the transposition table IT at the time of search, and calculates a score for each partial document.

Next, the node table and the path table will be described with reference to FIG. 4A is a diagram illustrating a node table, and FIG. 4B is a diagram illustrating a path table.
In FIG. 4A, (a1) is a node table 001NT related to the XML document 001, and (a2) is a node table 002NT related to the XML document 002. In any node table NT, in order from the left, a document ID (docid) representing an identifier of the XML document, a range label (“pre” and “post”), a tag (tag) given to each node, and a path identifier path ID representing the (pathid), lk that node representing the length of the partial document when it is the path specified (l _k), and, and a column of the text (text) is a text data of the node .

  As shown in FIG. 4B, the path table PT includes, in order from the left, path ID (pathid), path (pathexp), L (average length of the entire partial document set), and N (total number of partial documents). It consists of columns.

Next, the transposition table will be described with reference to FIG. FIG. 5 is a diagram showing an example of a transposition table.
As shown in FIG. 5, the transposition table IT is composed of columns of words (terms) and appearance positions (positions). The parentheses in the appearance position mean the document ID (docid), the start label (pre), and the end label (post) in order from the left. For example, if the appearance position corresponding to the word “universe” in the transposition table IT is (001, 3, 4), the start label (pre) in the XML document 001 whose document ID (docid) is “001” is “ It can be seen that the word “universe” is present at the node “3” whose end label (post) is “4”, that is, the node n111 in FIG.

Next, the construction processing of the structure index (path table PT and node table NT) will be described with reference to FIG. FIG. 6 is a flowchart showing a structure index construction process.
First, a user inputs an XML document to be newly accumulated into the information processing apparatus 1 via the input unit 2. Then, the data storage unit 61 of the processing unit 6 stores the XML document in the XML document group 51 of the storage unit 5, and at that time, the path index unit 62 and the range label unit 63 obtain the structure index by the following processing. To construct.

  For the input XML document, the path index unit 62 takes out one path (step S601). The path index unit 62 refers to the path table PT and determines whether or not the path is already included (exists) in the path table PT (step S602).

  If the path is not included in the path table PT (No in step S602), the path index unit 62 issues a new path ID, newly adds the path to the path table PT (step S603), and further passes the path. L and N values (statistics of partial document set) are calculated, that is, the connected text length under the path is set to L value, and the value of N is set to “1”, respectively. Store in the location (step S604).

  If the path is already included in the path table PT (Yes in step S602), the path index unit 62 calculates L and N values (statistics of the partial document set) relating to the path, that is, the path of the path. The average of the subordinate connected text lengths is set as the value of L, the value of N is incremented (increased by one), and each is stored in the corresponding part of the path table PT (step S604).

  Thereafter, the path index unit 62 determines whether or not the processing for all the paths related to the XML document has been completed (step S605), and if not completed (No), the process returns to step S601 and repeats the processing. If yes (Yes), the process proceeds to step S606.

  In this way, the three statistics required for the search (“statistics for the entire partial document set”, “statistics for each partial document”, and “statistics for the search word”) are obtained by the processing in steps S601 to S605. Among them, “statistics of the entire partial document set” (“L” and “N” in the path table PT) can be calculated and stored immediately after the XML document is input (before the input of the search query). As a result, it is not necessary to calculate “statistics of the entire partial document set” at the time of search (calculation of fitness), and the search process can be speeded up.

Subsequently, regarding the input XML document, the range label unit 63 takes out one node (step S606).
Thereafter, the range label unit 63 refers to the path table PT, extracts a path ID corresponding to the node (step S607), assigns a range label according to the regularity described above (step S608), and sets each node table NT to each node table NT. The value (column information) is stored (step S609).

  That is, in step S609, the range label unit 63 determines not only the document ID (docid), range label ("pre" and "post"), tag (tag), and path ID (pathid), but also the partial documents under the node. Lk representing the length of the node and information regarding the text (text) which is the text data of the node are also stored in the node table NT.

  Thereafter, the range label unit 63 determines whether or not the processing for all the nodes related to the XML document has been completed (step S610), and if not completed (No), the processing returns to step S606 and repeats the processing. If yes (Yes), the process proceeds to step S611.

  In this way, three statistics required for the search (“statistics for the entire partial document set”, “statistics for each partial document”, and “statistics for the search word”) are obtained by the processing of steps S606 to S610. Among them, “statistics for each partial document” (“lk” in the node table NT) can be calculated and stored immediately after the XML document is input (before the search query is input). Thus, it is not necessary to calculate “statistics for each partial document” at the time of search (calculation of fitness), and the search process can be speeded up.

The processing unit 6 determines whether or not the processing for all the input XML documents has been completed (step S611), and if not completed (No), the processing returns to step S601 and repeats the processing. (Yes) The process is terminated.
In this manner, according to the processing of the flowchart of FIG. 6, for all the input XML documents, “statistics for the entire partial document set” and “statistics for each partial document” are calculated and stored immediately after the input. can do.

  In the flowchart of FIG. 6, for the sake of simplicity, the processing by the path index unit 62 and the processing by the range label unit 63 are separated. However, these processing may be performed in parallel.

Next, the text index (transposition table IT) construction process will be described with reference to FIG. FIG. 7 is a flowchart showing text index construction processing.
After the path table PT and the node table NT are updated for the input XML document by the processing of the flowchart shown in FIG. 6, the text index unit 64 of the processing unit 6 reads one record (one node worth) from the node table NT. Data) is extracted (step S701).

  Subsequently, the text index unit 64 performs morphological analysis (basic technology of natural language processing using a computer) on the description content (data in the column “text” of the node table NT in FIG. 4A) in the extracted record. The word is divided into words using one method (step S702).

Thereafter, the text index unit 64 determines whether or not one of the divided words is included in the transposition table IT (step S703).
If the word is not included in the transposition table IT (No in step S703), the text index unit 64 newly registers the word in the transposition table IT (step S704), and proceeds to step S705. If the word is included in the transposition table IT (Yes in step S703), the text index unit 64 proceeds to step S705 as it is.

  In step S705, the text index unit 64 stores the document ID (docid) and the range labels (“pre” and “post”) that are the appearance positions of the word in the transposition table IT. For example, if the word “universe” exists in the node n111 of the XML document 001 (see FIG. 3A), the document ID “001” of the XML document 001, the start label (pre) “3” of the node n111, and (001, 3, 4) representing the end label (post) “4” is stored in the “position” column corresponding to “universe” in the transposition table IT.

Thereafter, the text index unit 64 determines whether or not the processing for all the words related to the record has been completed (step S706), and if not completed (No), the process returns to step S703 to repeat the processing and finish. If yes (Yes), the process proceeds to step S707.
Further, the text index unit 64 determines whether or not the processing for all the records related to the XML document has been completed (step S707), and if not completed (No), the process returns to step S701 and repeats the processing to end. If so (Yes), the process is terminated.

  In this way, three statistics required for the search (“statistics for the entire partial document set”, “statistics for each partial document”, and “statistics for the search word” are obtained by the processing of the flowchart shown in FIG. ) Can be calculated and stored immediately after the input of the XML document (before the input of the search query). Thus, it is not necessary to calculate “statistics for the search word” at the time of search (calculation of fitness), and the search process can be speeded up.

Next, the ranking process will be described with reference to FIG. FIG. 8 is a flowchart showing the ranking process.
When ranking by search is performed on a plurality of XML documents stored in the XML document group 51 of the storage unit 5, first, the user inputs a search query (path and search character string) using the input unit 2.

Then, the ranking unit 65 of the processing unit 6 determines the path from the search query, the search word (extracted from the search character string), l _q (the length of the search character string q), and tf _qi (the search in the search character string q). The number of occurrences of the word i is extracted (calculated) (step S801).
Subsequently, the ranking unit 65 refers to the path table PT and extracts the values of “L”, “N” and the path ID (pathid) in the record corresponding to the path in the search query (step S802).

  The ranking unit 65 refers to the node table NT, and the position of the partial document (document ID (docid) and range label (“pre” and “post”)) in the record corresponding to the path ID (pathid) extracted in step S802. And the value of “lk” is extracted (step S803). A collection of the extracted partial documents is called a partial document group.

  The ranking unit 65 extracts the values of the search word appearance position (document ID (docid), range labels (“pre” and “post”)) from the transposition table IT (step S804). The collection of nodes at the appearance positions extracted here is called a word appearance document group.

Subsequently, the ranking unit 65 narrows down the partial documents in which the search word appears using the value of the appearance position extracted from the transposition table IT, and tf _ki (number of occurrences of the word i in the partial document k) and _ni (corresponding) The number of partial documents including the word i to be calculated) is calculated (step S805). That is, the ranking unit 65 uses the position information of the partial document group and the word appearance document group to select partial documents including the search word from the partial document group, and tf _ki that is the statistic of the word in each partial document. to calculate the n _i. Here, a specific example of step S805 will be described with reference to FIG.

FIG. 9 is a diagram showing a specific example of step S805, that is, an example of selection of partial documents and calculation of word statistics. The example in FIG. 9 is an independent example that is not related to the specific examples in FIGS.
Based on the partial document group shown in FIG. 9A and the word appearance document group shown in FIG. 9B, for example, first, the partial documents (001, 10, 20) in the partial document group (the four shown in the figure). The word appearance document included in the word appearance document group is searched for. That is, in the word appearance document group, a word appearance document having a document ID “001” and a range label “10” to “20” may be searched. Here, (001, 12, 13) and (001, 15, 16) correspond to the word appearance documents.

Similarly, as shown in FIG. 9C, the partial documents are narrowed down to three (the document with the document ID “003” is not included because it does not include any search word), and the statistics Tf _ki (number of occurrences of the word i in the partial document k) is “2”, “1” and “1” from the top, and n _i (the number of partial documents including the corresponding word i) is “3”. Can be calculated.

Returning to FIG. 8, the ranking unit 65 calculates the score of the corresponding partial document by using each statistic and the above-described equation (1) (step S806).
Then, the ranking unit 65 performs ranking by sorting the partial documents in descending order of the score calculated in step S806 (step S807).

  In this way, the information processing apparatus 1 uses the three statistics ("statistics for the entire partial document set", "statistics for each partial document", and "statistics for the search word") calculated and stored in advance. By performing a search (calculation of suitability, ranking) using the search, the search can be processed at high speed.

(Search example)
Next, an example in which a search (ranking) according to the flowchart of FIG. 8 is performed on the specific examples of FIGS. Here, it is assumed that in the search query, the path is “/ book / chapter / text / text ()” and the search character string is “Earth”.
First, l _q (the length of the search character string q) is “2”, and tf _qi (the number of appearances of the word i (earth) in the search character string q) is “1” (FIG. 8). Step S801 of FIG. 8. Hereinafter, “FIG. 8” is omitted).

Further, from the record in which the path in the path table PT (see FIG. 4) is “/ book / chapter / text / text ()” (the record whose “pathid” is “09”), “L” is “2379”, It can be seen that “N” is “13” (step S802).
Furthermore, from the record whose “pathid” is “09” in the node table 001NT (see FIG. 4 (a1)), the appearance position of the partial document is (001, 14, 15), and lk (length of the partial document k) ) Is “319” (step S803).

Also, from the record in which “term” is “Earth” in the transposition table IT (see FIG. 5), all the positions where the word “Earth” appears are (001, 14, 15) and (001, 19, 20). It can be seen that there is (step S804).
However, since the partial documents (001, 19, 20) are not included in the partial documents (001, 14, 15) extracted in step S803, only the partial documents (001, 14, 15) are narrowed down as corresponding partial documents. (Step S805). That is, the partial document (001, 19, 20) is not included in the search because it is not included in the partial document corresponding to the path specified by the search query by the user.

Further, regarding this partial document (001, 14, 15), tf _ki (number of occurrences of word i in partial document k) is “1”, and n _i (number of partial documents including the corresponding word i) is also “ 1 ”can be calculated (step S805).

このようにして、検索クエリに該当した部分文書に関するスコアを算出することができる。 The following formula (2) shows a score calculated by substituting the above seven values into the above formula (1).

In this way, the score regarding the partial document corresponding to the search query can be calculated.

  In step S802, there may be a plurality of “L” and “N” values depending on the contents of the path of the search query. The handling of the values “L” and “N” in that case will be described with reference to FIG. FIG. 10 is an explanatory diagram for calculating the values of “L” and “N” when there are a plurality of values of “L” and “N”. FIG. 10A is a path table similar to FIG. (B) represents the calculation formulas for the values of “L” and “N”, such as PT.

For example, when the path of the search query is “title (// title) at an arbitrary position”, as shown in FIG. 10A, a plurality of paths are applicable (path ID (pathid) is “02”). And "07" path). In this case, for example, as shown in the calculation formula of FIG. 10B, the value of “N” is a value obtained by adding a plurality of values of “N (N ₁ , N ₂ ,...)”, “L”. May be calculated as a weighted average of the corresponding values of “N” for each of a plurality of “L (L ₁ , L ₂ ,...)”. A specific calculation example is as shown in the lower half of FIG.
In this way, even when there are a plurality of values of “L” and “N”, it is possible to calculate the fitness level and perform ranking without any trouble.

(Second Embodiment)
Next, a second embodiment of the present invention will be described with reference to FIGS. 11A to 20. FIG. 11A is a configuration diagram of an information processing apparatus according to the second embodiment. In addition, the same code | symbol is attached | subjected about the structure similar to the information processing apparatus 1 of FIG. 1, and description is abbreviate | omitted suitably. In the information processing apparatus 1a in FIG. 11A, the configurations of the storage unit 5a and the processing unit 6a are changed compared to the information processing apparatus 1 in FIG.

As illustrated in FIG. 11A, the processing unit 6a of the information processing device 1a includes a tag index unit 66 (node management unit) instead of the range label unit 63 of FIG. The tag index unit 66 manages information regarding each node using the node ID in the node table NTa.
Further, in the storage unit 5a, the node table NTa and the transposition table ITa are partially changed in constituent elements as compared with the corresponding configurations in the information processing apparatus 1 in FIG. 1 (details are shown in FIGS. 12 and 14). And later). Further, the storage unit 5a newly has a text table TT (text information) as compared with the storage unit 5 of FIG. 1 (details will be described later in FIG. 13).

Here, a state in which a node ID is assigned to an XML document will be described with reference to FIG. 11B. FIG. 11B is a diagram showing a state in which (a) assigns a node ID to the XML document 001 in FIG. 2 (a), and (b) shows a node ID for the XML document 002 in FIG. 2 (b). It is a figure which shows the state which provided.
As shown in FIG. 11B (a), in the XML document 001, the node n1 (book) is the parent of the node n11 whose node ID is “001” and whose node ID is “002”. Similarly, different node IDs are assigned as identifiers to all nodes. The same applies to FIG. 11B (b).

Next, the node table NTa will be described with reference to FIG. FIG. 12A shows the node table 001NTa related to the XML document 001, and FIG. 12A shows the node table 002NTa related to the XML document 002. In any node table NTa, in order from the left, a node ID (nodeid), a parent node ID (parent) representing the node ID of the latest parent node, a tag (tag) given to each node, and a path identifier are represented. A path ID (pathid), lk indicating the length of the partial document when the node is designated as a path, and a text ID (textid) that is an identifier of text data included in the partial document when the node is designated as a path ) (Related information, node position information) column.
The path table PT in FIG. 12B is the same as that in FIG.

Next, the text table will be described with reference to FIG. 13A is a node table NTa similar to FIG. 12A, and FIG. 13B is a configuration diagram of a text table TT.
As shown in FIG. 13B, text data (text) of each text node is stored in the text table TT in association with the text ID (textid).

Next, the transposition table ITa will be described with reference to FIG. FIG. 14 is a configuration diagram of the transposition table ITa.
As shown in FIG. 14, the transposition table ITa is composed of columns of a word (term) and a text ID (textid). The text ID (textid) corresponds to the text ID (textid) in the text table TT in FIG.

Next, the construction process of the structure index (path table PT and node table NTa) will be described with reference to FIG. FIG. 15 is a flowchart showing an overview of the structure index construction process.
First, a user inputs an XML document to be newly accumulated into the information processing apparatus 1 via the input unit 2. Then, the data storage unit 61 of the processing unit 6 stores the XML document in the XML document group 51 of the storage unit 5. At that time, with respect to all the input XML documents (until Yes is selected in step S1503), the path index unit 62 constructs a path index (updates the path table PT) (step S1501, details are shown in FIG. 16). The tag index unit 66 constructs a tag index (updates the node table NTa and the text table TT) (step S1502, details are shown in FIG. 17), thereby constructing a structure index.

  FIG. 16 is a flowchart of the path index construction process performed by the path index unit 62. The processes in steps S1601 to S1605 are the same as the processes in steps S601 to S605 in FIG.

FIG. 17 is a flowchart of the process of building the tag index (node table NTa and text table TT), which is performed after the process of the flowchart of FIG.
First, the tag index unit 66 extracts one node from the input XML document (step S1701).
Next, the tag index unit 66 refers to the path table PT and extracts a path ID corresponding to the node (step S1702).
If the node is a text node (a node having text data), the tag index unit 66 stores the text data in the text table TT (step S1703), and the value of the corresponding text ID (textid) from the text table TT. Is taken out (step S1704). If the node is not a text node, the tag index unit 66 passes through without performing the processes of steps S1703 and S1704.

Subsequently, the tag index unit 66 determines whether or not the node is a root node (highest node) (step S1705). If the node is a root node (Yes), the tag index unit 66 sets “parent” of the node in the node table NTa. “0” is stored (step S1710), and the process proceeds to step S1711.
If the node is not the root node (No in step S1705), the tag index unit 66 stores the node ID of the nearest parent node in “parent” of the node in the node table NTa (the node ID of the parent node is the parent value). (Step S1706).

  After step S1706, the tag index unit 66 traces the parent value and moves up to the parent node that is one level higher until the tag index unit 66 moves to the root node (until the parent value of the record becomes 0. That is, until it becomes Yes in step S1709). Is moved to the row (record) of the node table NTa (step S1707), and the value of the text ID extracted in step S1704 is added to the text ID (textid) of the record (step S1708).

That is, by the processing in steps S1707 to S1709, all the text IDs (textid) of the text data under the node are collected in each node in the node table NTa. For example, in FIG. 12A1, text IDs (textid) of all text data of the XML document 001 are collected at the root node (node having a node ID (nodeid) of “001”).
If the node extracted in step S1701 is not a text node, the tag index unit 66 passes through without performing the processing in steps S1706 to S1709.

Next, the tag index unit 66 adds the record of the node itself to the end of the node table NTa (step S1711). At this time, the tag index unit 66 stores each value (column information) including “lk” in the node table NT.
The tag index unit 66 determines whether or not the processing for all the nodes has been completed (step S1712). If not completed (No), the process returns to step S1701 to repeat the process, and if completed (Yes) ) End the process.

  As described above, when the node table NTa is updated by the processing of the flowchart of FIG. 17 as in the case of steps S606 to S610 of FIG. 6, “statistics for each partial document” (“lk” of the node table NTa). ) Can be calculated and stored. Thus, it is not necessary to calculate “statistics for each partial document” at the time of search (calculation of fitness), and the search process can be speeded up.

Next, the text index (transposition table ITa) construction process will be described with reference to FIG. FIG. 18 is a flowchart showing text index construction processing.
After the path table PT and the node table NTa are updated for the input XML document by the processing of the flowcharts shown in FIGS. 15 to 17, the text index unit 64 takes out one record from the node table NTa (step S1801). ).

  Subsequently, the text index unit 64 describes the description contents in the extracted record (data in the column “text” in the text table TT in FIG. 13B corresponding to “textid” in the node table NTa in FIG. 13A). Is divided into words using a morphological analysis technique (step S1802).

Thereafter, the text index unit 64 determines whether or not one of the divided words is included in the transposition table ITa (step S1803).
If the word is not included in the transposition table ITa (No in step S1803), the text index unit 64 newly registers the word in the transposition table ITa (step S1804).

  In the case of Yes in step S1803 and following step S1804, in step S1805, the text index unit 64 stores “textid” of the word in the transposition table ITa. For example, if the word “universe” exists in the node n111 of the XML document 001 (see FIG. 11B (a)), “01” (“id”) corresponding to the text data of the node n111 (FIG. 13 (b)). Is stored in the column “textid” corresponding to “space” in the transposition table ITa (see FIG. 14).

Thereafter, the text index unit 64 determines whether or not the processing for all the words related to the record has been completed (step S1806), and if not completed (No), the process returns to step S1803 to repeat the processing and finish. If yes (Yes), the process proceeds to step S1807.
In addition, the text index unit 64 determines whether or not the processing for all the records related to the XML document has been completed (step S1807), and if not completed (No), the process returns to step S1801 to repeat the processing and end. If so (Yes), the process is terminated.

  In this way, three statistics required for the search (“statistics for the entire partial document set”, “statistics for each partial document”, and “statistics for the search word” are obtained by the processing of the flowchart shown in FIG. ) Can be calculated and stored immediately after the input of the XML document (before the input of the search query), and therefore, when searching (calculation of fitness) It is not necessary to calculate the “statistics for the search word”, and the search process can be speeded up.

Next, the ranking process will be described with reference to FIG. FIG. 19 is a flowchart showing the ranking process.
When ranking by search is performed on a plurality of XML documents stored in the XML document group 51 of the storage unit 5a, first, the user uses the input unit 2 to input a search query (path and search character string).

Then, the ranking unit 65 of the processing unit 6 determines the path from the search query, the search word (extracted from the search character string), l _q (the length of the search character string q), and tf _qi (the search in the search character string q). The number of occurrences of word i is extracted (calculated) (step S1901).
Subsequently, the ranking unit 65 refers to the path table PT and extracts the values of “L”, “N” and the path ID (pathid) in the record corresponding to the path in the search query (step S1902).

The ranking unit 65 refers to the node table NTa and extracts the text ID (textid) and the value of “lk” in the record corresponding to the path ID (pathid) extracted in step S1902 (step S1903).
The ranking unit 65 extracts the value of the appearance position (textid) of the search word from the transposition table ITa (step S1904).

Subsequently, the ranking unit 65 narrows down the partial documents in which the search word appears using the value of the text ID (textid) extracted from the transposition table ITa, and tf _ki (number of occurrences of the word i in the partial document k) and n _i (the number of partial documents including the corresponding word i) is calculated (step S1905). Here, a specific example of step S1905 will be described with reference to FIG.

FIG. 20 is a diagram showing a specific example of step S1905, that is, an example of selection of partial documents and calculation of word statistics. The example in FIG. 20 is an independent example that is not related to the specific examples of FIGS.
Based on the partial document group shown in FIG. 20A and the word appearance document group shown in FIG. 20B, for example, first, the partial document (node ID “ 004 ”, text ID“ 02, 03, 04, 05, 06, 07 ”) is searched for whether the text ID exists in the word appearance document group (b). Here, in the word appearance document group of (b), the text IDs “03” and “07” correspond.

Similarly, as shown in FIG. 20C, the partial documents are narrowed down to three, and the statistic tf _ki (number of occurrences of the word i in the partial document k) is “2”, “ It can be calculated that “1” and “1”, and n _i (number of partial documents including the corresponding word i) is “3”.

Returning to FIG. 19, the ranking unit 65 calculates the score of the corresponding partial document using each statistic and the above-described equation (1) (step S1906).
Then, the ranking unit 65 performs ranking by sorting the partial documents in descending order of the score calculated in step S1906 (step S1907).
Note that the processing in step S1906 and step S1907 is the same as the processing in step S806 and step S807 in FIG.

  As described above, the information processing apparatus 1a uses the three statistics ("statistics for the entire partial document set", "statistics for each partial document", and "statistics for the search word") that are calculated and stored in advance. By using this to perform a search (calculation of suitability, ranking), the search can be processed at high speed.

  In addition, the calculation method of the conformity of the XML document of each embodiment can be realized in a computer (apparatus) by creating a program for executing each flowchart described above. Furthermore, these programs can be stored in a recording medium such as a hard disk, a flash memory, a CD-ROM (Compact Disk Read Only Memory), or a DVD (Digital Versatile Disk).

This is the end of the description of the embodiments, but the aspects of the present invention are not limited to these.
For example, in this embodiment, morphological analysis is used as a method for extracting a word from a character string, but another method such as N-gram may be used.
In addition, the specific configuration can be changed as appropriate without departing from the spirit of the present invention.

It is a block diagram of the information processing apparatus of 1st Embodiment. It is the figure which showed the example of the source code of an XML document, (a) is a figure regarding the XML document 001 similar to FIG. 22, (b) is a figure regarding the XML document 002 as another example. (A) is a figure which shows the state which provided the range label with respect to the XML document 001, (b) is a figure which shows the state which provided the range label with respect to the XML document 002. FIG. 6A is a diagram illustrating a node table, and FIG. 5B is a diagram illustrating a path table. It is the figure which showed the example of the transposition table. It is a flowchart which shows the construction process of a structure index. It is a flowchart which shows the construction process of a text index. It is a flowchart which shows a ranking process. It is the figure which showed the example of the selection of a partial document, and the calculation of the statistic of a word. FIG. 4 is an explanatory diagram of calculation of “L” and “N” values when there are a plurality of “L” and “N” values, and (a) shows a path table PT similar to FIG. b) represents formulas for calculating the values of “L” and “N”, respectively. It is a block diagram of the information processing apparatus of 2nd Embodiment. (A) is a figure which shows the state which provided node ID with respect to the XML document 001 of Fig.2 (a), (b) is the state which provided node ID with respect to the XML document 002 of FIG.2 (b). FIG. FIG. 6A is a diagram illustrating a node table, and FIG. 5B is a diagram illustrating a path table. (A) is the same node table NT as FIG. 12 (a), (b) is a block diagram of the text table TT. It is the figure which showed the example of transposition table ITa. It is a flowchart which shows the outline | summary of the construction process of a structure index. 10 is a flowchart of a path index construction process by a path index unit 62. It is a flowchart of a tag index construction process. It is a flowchart which shows the construction process of a text index. It is a flowchart which shows a ranking process. It is the figure which showed the example of the selection of a partial document, and the calculation of the statistic of a word. The ranking example using the statistical information of a comparative example is shown, (a) is a document example, (b) is a calculation example 1 of the fitness (ranking), and (c) is a calculation example 2 of the fitness. FIG. (A) is a simplified diagram of an example of source code of an XML document, and (b) is a diagram showing a tree structure of the XML document. (A) And (b) is the figure which showed the range of the partial document by each path | pass about the example of FIG.2 (b). (A) And (b) is the figure which showed the range of the partial document by each path | pass about the example of FIG.2 (b).

Explanation of symbols

DESCRIPTION OF SYMBOLS 1,1a Information processing apparatus 2 Input part 3 Output part 4 Memory 5, 5a Storage part 6, 6a Processing part 51 XML document group 61 Data storage part 62 Path index part 63 Range label part 64 Text index part 65 Ranking part 66 Tag index Department IT, ITa Transposition table NT, NTa Node table PT, PTa Path table TT Text table

Claims (10)

Path information for storing information in units of paths for a plurality of XML documents, node information for storing relation information between nodes in each XML document for each XML document, and each word used in the plurality of XML documents A storage unit for storing word information for storing appearance position information;
A path index unit for storing path unit information in the path information for the plurality of XML documents;
A node management unit that analyzes a relationship including a parent-child relationship between nodes in each XML document and stores the relationship information in the node information;
A text index part for storing a word used in any of the plurality of XML documents in the word information in association with appearance position information including a document ID (IDentification) of the XML document in which the word is used;
When a path and a search word are input, with respect to the plurality of XML documents, a ranking unit that calculates a degree of matching of the search word in a partial document that is a document under the input path;
An information processing apparatus that stores a plurality of XML documents that are structured data, and calculates, for each of the plurality of XML documents, a matching degree of the search word in a partial document under the input path. A method of calculating the fitness,
The path information stores path statistical information that is statistical information on a set of partial documents under each path as information on a path basis.
The path index unit updates path information including the path statistical information with respect to the plurality of stored XML documents before the path and a search word are input.
The ranking unit refers to the path information including the path statistical information, the node information, and the word information after the path and the search word are input, and based on the path and the search word, A method for calculating the degree of conformity of an XML document, comprising: calculating the degree of conformity relating to an XML document. Path information for storing information in units of paths for a plurality of XML documents, node information for storing relation information between nodes in each XML document for each XML document, and each word used in the plurality of XML documents A storage unit for storing word information for storing appearance position information;
A path index unit for storing path unit information in the path information for the plurality of XML documents;
A node management unit that analyzes a relationship including a parent-child relationship between nodes in each XML document and stores the relationship information in the node information;
A text index part for storing a word used in any of the plurality of XML documents in the word information in association with appearance position information including a document ID (IDentification) of the XML document in which the word is used;
When a path and a search word are input, with respect to the plurality of XML documents, a ranking unit that calculates a degree of matching of the search word in a partial document that is a document under the input path;
An information processing apparatus that stores a plurality of XML documents that are structured data, and calculates, for each of the plurality of XML documents, a matching degree of the search word in a partial document under the input path. A method of calculating the fitness,
The node information stores, as information for each node, node statistical information that is statistical information regarding partial documents under each node,
The node management unit updates the node information including the node statistical information before the path and the search word are input,
The ranking unit refers to the path information, node information including the node statistical information, and the word information after the path and the search word are input, and based on the path and the search word, A method for calculating the degree of conformity of an XML document, comprising: calculating the degree of conformity relating to an XML document. Path information for storing information in units of paths for a plurality of XML documents, node information for storing relation information between nodes in each XML document for each XML document, and each word used in the plurality of XML documents A storage unit for storing word information for storing appearance position information;
A path index unit for storing path unit information in the path information for the plurality of XML documents;
A node management unit that analyzes a relationship including a parent-child relationship between nodes in each XML document and stores the relationship information in the node information;
A text index part for storing a word used in any of the plurality of XML documents in the word information in association with appearance position information including a document ID (IDentification) of the XML document in which the word is used;
When a path and a search word are input, with respect to the plurality of XML documents, a ranking unit that calculates a degree of matching of the search word in a partial document that is a document under the input path;
An information processing apparatus that stores a plurality of XML documents that are structured data, and calculates, for each of the plurality of XML documents, a matching degree of the search word in a partial document under the input path. A method of calculating the fitness,
The word information stores, as the appearance position information, node position information where the word appears together with the document ID of the XML document,
The text index unit updates the word information including the node position information before the path and search word are input,
The ranking unit refers to word information including the path information, the node information, and the node position information after the path and the search word are input, and based on the path and the search word, A method for calculating the conformity of an XML document, comprising: calculating the conformity of an XML document. As the relationship information between the nodes, the node management unit sets a start label value and an end label value for each node, a start label value of the parent node is smaller than a start label value of the child node, and an end label value of the parent node is It is given to satisfy the relationship that it is larger than the end label value of the child node, and stored in the node information,
The text index unit assigns a start label value and an end label value in the node information as node position information of each word information,
The ranking unit determines a range of partial documents corresponding to the path based on a start label value and an end label value of each node in the node information when the path and a search word are input, and the partial document The method of calculating the fitness of an XML document according to claim 3, wherein the fitness of the search word is calculated with respect to. The storage unit further stores text information for storing text data of a node having text data in the XML document in association with identification information of the text data,
The node management unit associates identification information of text data under each node in the node information,
When the path and the search word are input, the ranking unit determines a range of the partial document corresponding to the path based on the identification information of the text data in the node information, and the search word of the search word is related to the partial document. The method for calculating the conformity of an XML document according to claim 3, wherein the conformance is calculated. Path information for storing information in units of paths for a plurality of XML documents, node information for storing relation information between nodes in each XML document for each XML document, and each word used in the plurality of XML documents A storage unit for storing word information for storing appearance position information;
A path index unit for storing path unit information in the path information for the plurality of XML documents;
A node management unit that analyzes a relationship including a parent-child relationship between nodes in each XML document and stores the relationship information in the node information;
A text index part for storing a word used in any of the plurality of XML documents in the word information in association with appearance position information including a document ID (IDentification) of the XML document in which the word is used;
When a path and a search word are input, with respect to the plurality of XML documents, a ranking unit that calculates a degree of matching of the search word in a partial document that is a document under the input path;
A plurality of XML documents that are structured data, and for the plurality of XML documents, an information processing apparatus that calculates a degree of matching of the search word in a partial document under the input path,
The path information stores path statistical information that is statistical information on a set of partial documents under each path as information on a path basis.
The path index unit updates path information including the path statistical information with respect to the plurality of stored XML documents before the path and a search word are input.
The ranking unit refers to the path information including the path statistical information, the node information, and the word information after the path and the search word are input, and based on the path and the search word, An information processing apparatus that calculates a degree of conformity with respect to an XML document. Path information for storing information in units of paths for a plurality of XML documents, node information for storing relation information between nodes in each XML document for each XML document, and each word used in the plurality of XML documents A storage unit for storing word information for storing appearance position information;
A path index unit for storing path unit information in the path information for the plurality of XML documents;
A node management unit that analyzes a relationship including a parent-child relationship between nodes in each XML document and stores the relationship information in the node information;
A text index part for storing a word used in any of the plurality of XML documents in the word information in association with appearance position information including a document ID (IDentification) of the XML document in which the word is used;
When a path and a search word are input, with respect to the plurality of XML documents, a ranking unit that calculates a degree of matching of the search word in a partial document that is a document under the input path;
A plurality of XML documents that are structured data, and for the plurality of XML documents, an information processing apparatus that calculates a degree of matching of the search word in a partial document under the input path,
The node information stores, as information for each node, node statistical information that is statistical information regarding partial documents under each node,
The node management unit updates the node information including the node statistical information before the path and the search word are input,
The ranking unit refers to the path information, node information including the node statistical information, and the word information after the path and the search word are input, and based on the path and the search word, An information processing apparatus that calculates a degree of conformity with respect to an XML document. Path information for storing information in units of paths for a plurality of XML documents, node information for storing relation information between nodes in each XML document for each XML document, and each word used in the plurality of XML documents A storage unit for storing word information for storing appearance position information;
A path index unit for storing path unit information in the path information for the plurality of XML documents;
A node management unit that analyzes a relationship including a parent-child relationship between nodes in each XML document and stores the relationship information in the node information;
A text index part for storing a word used in any of the plurality of XML documents in the word information in association with appearance position information including a document ID (IDentification) of the XML document in which the word is used;
When a path and a search word are input, with respect to the plurality of XML documents, a ranking unit that calculates a degree of matching of the search word in a partial document that is a document under the input path;
A plurality of XML documents that are structured data, and for the plurality of XML documents, an information processing apparatus that calculates a degree of matching of the search word in a partial document under the input path,
The word information stores, as the appearance position information, node position information where the word appears together with the document ID of the XML document,
The text index unit updates the word information including the node position information before the path and search word are input,
The ranking unit refers to word information including the path information, the node information, and the node position information after the path and the search word are input, and based on the path and the search word, An information processing apparatus that calculates a degree of conformity with respect to an XML document. As the relationship information between the nodes, the node management unit sets a start label value and an end label value for each node, a start label value of the parent node is smaller than a start label value of the child node, and an end label value of the parent node is It is given to satisfy the relationship that it is larger than the end label value of the child node, and stored in the node information,
The text index unit assigns a start label value and an end label value in the node information as node position information of each word information,
The ranking unit determines a range of partial documents corresponding to the path based on a start label value and an end label value of each node in the node information when the path and a search word are input, and the partial document The information processing apparatus according to claim 8, wherein the matching degree of the search word is calculated with respect to.   A program for causing a computer to execute the method for calculating the conformity of an XML document according to any one of claims 1 to 5.

Images