JP2012208917A - Document ranking method and apparatus - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a document ranking method and an apparatus.SOLUTION: A method comprises steps of: extracting query semantic information based on queries and an ontology of users; extracting document semantic information based on documents, the queries, and the ontology; determining a relational semantic relevance score between the document semantic information and the query semantic information; and ranking the documents based on the relational semantic relevance score. The method and an apparatus efficiently improve document ranking accuracy.

Description

  The present invention relates to the field of information retrieval, and more particularly to a document ranking method and apparatus.

  With the wide application and spread of electronic information, various and large amounts of information continue to be accumulated by various distributed systems. For this reason, interest in methods for finding useful information from a large amount of information is increasing.

  An information search is a search for information from a group of documents, such as a search for a specific part of information contained in a document, a search for the document itself, a search for metadata describing the document, a search in a database, etc. included. The search target information includes various texts, voices, data, and the like.

  Currently, methods for ranking documents are roughly classified into two types, a query-dependent type and a query-independent type. The query-dependent type is a method in which when a user executes a query, the documents are ranked based on the contents of the query input by the user, and target information can be obtained more accurately. In the conventional semantic-based document ranking method, the semantic relevance between a query and a document is mainly determined based on ontology, and the documents are ranked based on the relevance. In such a conventional method, only the semantic relevance between the concepts included in the query and the document is considered, and the semantic relevance existing in the relationship between these concepts is not considered. However, the semantic relevance (hereinafter referred to as “relation semantic relevance”) in this relationship is extremely useful for understanding the purpose of the user's query and accurately matching the target document.

  Therefore, various document ranking methods according to the prior art often cannot obtain a target query result quickly and accurately.

“Unsupervised information extraction from unstructured, unstructured data source on the World Wide web” (Unstructured, ungrammatical data source on the World Wide web) . 10, no. 3-4, pages 211-226 “Efficiently linked text documents with relevant structured information”, In Proceeding of VLDB2006 “Graph-Based Concept Identification and Dissemination for Enterprise Search (Graph-Based Concept Identification and Disambiguation for Enterprise Search)”, In Proceeding of WWW2010. “Improved Semantic Similarity Modeling and Application (improved semantic similarity calculation model and application)”, Jilin University Press, Vol. 39, no. 1,2009 “Using information content to evaluation similarity in a taxonomy (use of information content for taxonomic semantic similarity evaluation)”, In IJCAI '95 “Introduction to Modern Information Retrieval”, McGraw-Hill, 1983 “Categorizing and Ranking Search Engine ’s Results by Semantic Similarity”, In Proceeding of ICUIMC'08

  In view of the above problems, the present invention provides a document ranking method and apparatus.

  According to a first aspect of the present invention, a document ranking method is provided. The method includes the steps of extracting query semantic information based on a user query and ontology, extracting document semantic information based on the document, query and ontology, and relationship meaning between the document semantic information and the query semantic information. Determining a relevance score, and ranking the documents based on the relationship meaning relevance score.

  According to a second aspect of the present invention, a document ranking apparatus is provided. The apparatus is configured to extract query semantic information extraction means configured to extract query semantic information based on a user query and ontology, and to extract document semantic information based on the document, query, and ontology. Document semantic information extraction means, relation semantic relevance score determination means configured to determine a relation semantic relevance score between document semantic information and query semantic information, and ranking of documents based on the relation semantic relevance score Ranking means configured to:

  According to the method and apparatus of the present invention, ranking of documents is performed based not only on the semantic relevance score of concepts between queries and documents, but also on the related semantic relevance scores between queries and documents. Considering the semantic aspects of the relationships contained within the document and query effectively improves the query accuracy so that the user can obtain the desired query results more quickly and accurately.

  Other features and advantages of the present invention will become apparent from the following description of a preferred embodiment which elucidates the principles of the invention with reference to the accompanying drawings.

  Other objects and advantages of the present invention will become clearer and easier to understand if the present invention is more comprehensively understood by the following description with reference to the drawings.

5 is a flowchart of a document ranking method according to an embodiment of the present invention. 6 is a flowchart of a document ranking method according to another embodiment of the present invention. 4 is a flowchart of a method for determining a relationship semantic relevance score between document semantic information and query semantic information according to an embodiment of the present invention; 6 is a flowchart of a method for determining a relationship semantic relevance score between document semantic information and query semantic information according to another embodiment of the present invention. 6 is a flowchart of a method for determining a relationship semantic relevance score between document semantic information and query semantic information according to still another embodiment of the present invention; 1 is a block diagram of a document ranking apparatus according to an embodiment of the present invention.

  In all the above figures, the same reference numbers indicate the same, similar or corresponding features or functions.

  The flowcharts and block diagrams shown in the figures are systems, methods, architectures, functions, and operations executable by a computer program product according to an embodiment of the present invention. Each block in the flowchart or block diagram represents a module, program segment, or portion of code that includes one or more executable instructions for performing a particular logic function. Note that in some alternative embodiments, the functions shown in the blocks are performed in a different order than the order shown in the figures. For example, two consecutive blocks may actually be executed substantially in parallel or in reverse order in relation to the related function. It is also noted that the block diagrams, flowchart blocks, and combinations thereof may be implemented by a dedicated hardware-based system for performing a specific function / operation or by a combination of dedicated hardware and computer instructions. I want.

  Prior art document ranking methods are roughly classified into query-dependent and query-independent types. The query-dependent type is a method in which, when a user executes a query, documents are ranked based on the query content input by the user. Query-independent is a method that ranks documents without considering the degree of matching between the document and a specific query.For example, when ranking documents directly based on characteristics specific to the document. Applicable. The document ranking method according to the present invention is query dependent. According to the method of the present invention, when a query input by a user is received, a ranking of a plurality of documents is determined based on the query.

  In one embodiment of the present invention, a document ranking method and apparatus is disclosed. The document ranking method according to the present invention is executed based on a query input by a user. The method according to the invention can be adapted to rank a plurality of documents. According to an embodiment of the present invention, first, semantic information of a query is extracted based on a user's query and ontology, and semantic information of the document is extracted based on the document, the user's query and ontology, and the document meaning is extracted. A relationship semantic relevance score between the information and the query semantic information is determined, and the documents are ranked based on the determined relationship semantic relevance score. In the method of the present invention, when ranking documents, not only the concept included in the user query and the concept included in the document, but also the semantic relevance score based on the relationship between the user query and the document (in the present invention, (Also referred to as “relevance meaning relevance score”), the document ranking accuracy is effectively improved.

For clarity, the terminology used in the present invention is first explained.

1. Ontology

  Ontology, originally a philosophical term, is now considered "an explicit and formalized description of a shared conceptual model". An ontology collects knowledge in the relevant domain, provides a common understanding of the knowledge of the technology, determines the vocabulary (ie, concepts) that are commonly recognized in the technology, and further, between these concepts and these concepts. The explicit definition of existing relationships can be used as a means of providing in a formalized manner at various levels.

From a semantic point of view, the relationships between concepts are roughly classified into four types as shown in Table 1.

  In practical use, the relationship between the concepts is not limited to the above four types of basic relationships, and other relationships can be defined according to the situation specific to each field.

Currently, widely used ontology includes Wordnet, Framenet, SENSUS, Mikrommos, and the like. Wordnet is an English dictionary based on psychological language rules, and uses synets (a set of synonyms interchangeable in a specific context) as an information organization unit. Framenet is also an English dictionary, which employs a description frame called “frame semantics” to realize powerful semantic analysis capabilities. Currently, it is developing into Flamenet II. GUM is a concept organization mode that does not depend on the type of language, is oriented to natural language processing, supports multilingual processing, and is composed of basic concepts. SENSUS is also oriented towards natural language processing, providing a conceptual structure for machine translation and containing over 70,000 concepts. Mikrommos is also oriented towards natural language processing and supports multilingual processing. In addition, knowledge expression is performed using TMR, which is an intermediate language between languages.

2. Meaning path

A “semantic path” is a sequence made up of one or more relationships between concepts within an ontology. These concepts are extracted based on meaning and built on meaning. The m relation r in ontology _{'1, r' 2, ...} , are represented as r _'m, concepts _{d 1, d 2, ...,} d m, r 1, ..., if it is expressed as _{r m} Then, when r _i and d _{i + 1} (where i is 1 or more and less than m) have the same concept, the sequences r ′ ₁ (d ₁ , r ₁ ), r ′ ₂ (d ₂ , r ₂ ),. r ′ _m (d _m , r _m ) can be called a semantic path between the concept d ₁ and the concept r _m .

If the semantic path a = r ′ ₁ (d ₁ , r ₁ ), r ′ ₂ (d ₂ , r ₂ )..., R ′ _m (d _m , r _m ) is called a forward semantic path, the semantic path b = r ′ _q (r _m , d _q ), r ′ _q−1 (r _q−1 , d _q−1 )..., r ′ _p (r _p , d ₁ ) are referred to as reverse meaning paths. Can do.

For example, in the semantic path between the concept A and the concept B, the semantic path from the concept A to the concept B is referred to as a “forward” semantic path and expressed as P _AB . In this case, when there is a semantic path from the concept B to the concept A, for example, this is expressed as _PBA , and can be regarded as a “reverse” semantic path with respect to the “forward” semantic path.

Those skilled in the art will recognize that a “forward” meaning path and a “reverse” meaning path are relative and that a specific meaning path is defined as a “forward” or “reverse” meaning path in embodiments of the present invention. It will be understood that this is not essential.

3. Query semantic information

  The query semantic information includes a concept (or a concept set included in the query) included in the query, a semantic path between concepts included in the query, and the number of semantic paths between concepts included in the query.

Query semantic information can be expressed in various formats. For example, the query semantic information may be expressed in the form of a query graph represented by vertices and edges. The vertex of the query graph corresponds to each concept in the query concept set included in the query semantic information, and the edge of the query graph corresponds to one or more semantic paths between each concept pair included in the query semantic information. The weight of the edge of the query graph corresponds to the number of semantic paths between the two concepts respectively corresponding to the two vertices of the edge. As another example, the query semantic information may be expressed in the form of a text file. In this case, the concept included in the query and the semantic path between each concept pair are recorded in a text file. In addition to the above, the query semantic information may be expressed in any other suitable format.

4). Document semantic information

  In the present invention, a document is not an ordinary document in a narrow sense, but may include a part of document information, the document itself, metadata describing the document, and the like.

  The document semantic information is composed of concepts included in the document (this is called, for example, “document concept set”), semantic paths between concepts included in the document, and the number of semantic paths between concepts included in the document. be able to.

Document semantic information can be expressed in a variety of formats. For example, the document semantic information may be expressed in the form of a document graph represented by vertices and edges. The vertex of the document graph corresponds to each concept in the document concept set included in the document semantic information, and the edge of the document graph corresponds to one or more semantic paths between each concept pair included in the document semantic information. The weight of the edge of the document graph corresponds to the number of semantic paths between the two concepts respectively corresponding to the two vertices of the edge. In addition to the above, the document semantic information may be expressed in any other suitable format such as a text file format.

5. Concept meaning relevance score

In the present invention, the concept-meaning relevance score is a semantic relevance score based on a concept, and indicates a semantic relevance score between a query input by a user and a document from the viewpoint of the concept. The concept set extracted from the query reflects the user's information request to some extent, and the concept set extracted from the document reflects the content of the document to some extent. The calculation of the relevance score between the query concept set and the document concept set is adapted to determine the degree of matching between the user query and the document.

6). Relationship meaning relevance score

  In the present invention, the “relationship semantic relevance score” is a semantic relevance score based on a relationship, and indicates a semantic relevance score between a query input by a user and a document from the viewpoint of the relationship. Relationships are very important in understanding user query requests and what is described by the document. For example, when a user makes a query using two keywords “basketball” and “USA”, what the user actually needs is “the situation of basketball sales in the United States” and “the situation of basketball games in the United States”. Etc. At that time, there are two documents to be ranked, both of which contain the two concepts of “basketball” and “USA”, one of which describes the “production situation of basketball in the United States”. On the other hand, “Basketball game in the United States” is described. To solve the problem of determining which of the two documents is more relevant to the query, extract the potential semantic relationship between the user's query and the document, respectively, and the relationship between the two relation sets extracted A degree score needs to be calculated to determine if the user's query matches the document. According to the present invention, the probability that the semantic relation described in the document matches the semantic relation request of the user is calculated, and the relation semantic relevance score between the query and the document is obtained.

  FIG. 1 is a flowchart of a document ranking method according to an embodiment of the present invention.

  In step S101, query semantic information is extracted based on the user's query and ontology.

  In the present invention, the query semantic information can be composed of a concept extracted from a query input by a user and a semantic path between these concepts. In the embodiment of the present invention, the query semantic information extraction in step S101 extracts the query concept set included in the user's query based on the ontology, and the meaning between each concept pair in the query concept set based on the ontology. The procedure is carried out by obtaining a path and determining the number of semantic paths between the concept pairs based on the semantic paths between the concept pairs in the query concept set.

  Accordingly, in step S101, the concepts included in the user's query, the semantic paths existing between these concepts, and the number of semantic paths between each concept pair are determined.

  In an embodiment of the present invention, the number of semantic paths between each pair of concepts in a query concept set is determined, but there are many ways to optimize that number. In one embodiment, when acquiring the number of semantic paths between each concept pair, the number of forward semantic paths between each concept pair and the set of backward semantic paths are determined to be counted redundantly. The forward semantic path and the backward semantic path can be excluded. In another embodiment, the set of forward semantic paths and the set of backward semantic paths are optimized by excluding redundant paths from the set of forward semantic paths and the set of backward semantic paths, respectively. The number of semantic paths between each acquired concept pair is optimized. In yet another embodiment, the obtained number of semantic paths between each concept pair excludes the result of counting the mutual path pairs determined based on the set of forward semantic paths and the set of backward semantic paths. Optimized by.

  In step S102, document semantic information is extracted based on the document, query, and ontology.

  In the present invention, document semantic information can be composed of concepts extracted from documents to be ranked and semantic paths between these concepts. In one embodiment of the present invention, the procedure for extracting document semantic information in step S102 is performed in a number of ways.

  For example, based on ontology, a concept set included in a document and a concept set included in a query are extracted, and a document concept set is acquired based on a common part between the concept set included in the document and the concept set included in the query. The semantic path between each concept pair in the document concept set is acquired based on the document, and the number of semantic paths between the concept pairs is determined based on the semantic path between the concept pairs in the document concept set. .

  In another example, all the concepts contained in the document are pre-extracted and then the semantic path between all the concepts is obtained. When a query is received, a query concept set is obtained, matched with a concept in the document, and corresponding document semantic information is obtained. Therefore, in step S102, the concept included in each document among the plurality of documents to be ranked, the semantic path existing between these concepts, and the number of semantic paths between each concept pair are determined. Is done.

  In an embodiment of the present invention, the number of semantic paths between each concept pair in the document concept set is determined, but there are many ways to optimize that number. In one embodiment, when acquiring the number of semantic paths between each concept pair, the number of forward semantic paths between each concept pair and the set of backward semantic paths are determined to be counted redundantly. The forward semantic path and the backward semantic path can be excluded. In another embodiment, the set of forward semantic paths and the set of backward semantic paths are optimized by excluding redundant paths from the set of forward semantic paths and the set of backward semantic paths, respectively. The number of semantic paths between each acquired concept pair is optimized. In yet another embodiment, the number of semantic paths between each acquired concept pair is determined by excluding the count result of the mutual path pairs determined based on the set of forward semantic paths and the set of backward semantic paths. Optimized.

  It should be understood that step S101 and step S102 do not necessarily have to be executed in this order. In another embodiment of the present invention, step S102 is performed first, followed by step S101. Moreover, step S101 and step S102 may be performed simultaneously. The execution order of steps S101 and S102 shown in the embodiment of FIG. 1 is not intended to limit the present invention, but is merely an example.

  In step S103, a relationship semantic relevance score between document semantic information and query semantic information is determined.

  In one embodiment of the present invention, the number of semantic paths of document semantic information and the number of semantic paths of query semantic information are acquired, and based on the acquired number of semantic paths, the relationship semantic relation between document semantic information and query semantic information is acquired. A degree score is determined. 3-5 illustrate three examples for determining the relationship semantic relevance score between document semantic information and query semantic information according to the present invention. Hereinafter, these details will be described.

  In step S104, the documents are ranked based on the relationship meaning relevance score.

  Step S104 can be performed in a number of ways.

  In one embodiment, the ranking of documents is done by directly ranking the relationship semantic relevance scores obtained in association with each document in descending order or other suitable order.

  In another embodiment, a concept semantic relevance score for a document associated with the query is obtained, a document score is determined based on the relationship relevance score and the conceptual relevance score, and based on the document score. Documents are ranked.

  In yet another embodiment, a conceptual semantic relevance score between a document and a query is obtained, the documents are ranked based on the conceptual semantic relevance score, and the ranked documents are grouped. The documents in each group are ranked based on the relationship semantic relevance score.

  This is the end of the flow of FIG.

  It will be appreciated that the extraction of document semantic information based on documents, queries, and ontologies according to the present invention can be performed in a number of specific implementations.

  In one example of the present invention, the extraction of document semantic information is triggered by a user query, and a concept set included in the document and a concept set included in the query are extracted based on the ontology, and the concept set included in the document is extracted. And the concept set included in the query is obtained based on the common part of the query, the semantic path between each pair of concepts in the document concept set is obtained based on the document, and each concept in the document concept set is obtained. This is performed by a process in which the number of semantic paths between each concept pair is determined based on the semantic paths between the pairs.

  In other examples of the invention, document pre-processing is completed before a user query is received (e.g., in an offline state) or in the background while other queries are being processed. Is executed. Therefore, it is possible to extract the concepts contained in the document and the semantic paths between these concepts in advance based on the ontology, and store these extracted concepts and semantic paths in advance in a database or memory. it can. When the user executes a query, a common part between the concept set included in the document and the concept set included in the query is retrieved from the database or memory, and the document concept set is obtained based on the common part. Next, a semantic path between each concept pair in the document concept set is acquired according to the semantic path stored in the database or memory, and the number of semantic paths is determined. This example can be implemented as offline query processing.

  FIG. 2 is a flowchart of a document ranking method according to another embodiment of the present invention.

  In step S201, a query concept set included in the user's query is extracted based on the ontology.

  In this step, first, the query content input by the user is received. Here, it is assumed that the user inputs “American basketball” as a query in order to obtain and display the target document. In the present invention, “document” means any file that can be used by those skilled in the art, such as a Web page, a plain text file, a PDF file, a Word file, a PowerPoint file, and an Excel file.

  The concepts involved in the user's query can be determined in a number of ways based on the ontology. There are already many ways to extract concepts from text. For example, Non-Patent Document 1 ("Unstructured information extraction from unstructured unsourced data on the World Wide Web, unstructured data from unstructured unsourced data on the World Wide Web") Analysis and Recognition, 2007, vol. 10, No. 3-4, pages 211-226), Non-Patent Document 2 ("Efficiently linked text documents structured information"). Efficient Link Method between Text Document and Structured Related Information) ”, Concept Recognition Method described in In Proceeding of VLDB2006), and Non-Patent Document 3 (“ Graph-Based Concept Identification and Enterprise Search ”) Graph-based concept identification and disambiguation for enterprise search) ”, In Proceeding of WWW 2010).

  In the embodiment of the present invention, it is determined that the concepts included in the query “American basketball” inputted by the user are “America” and “basketball”, so that in step S201, the query concept set is {“America”. , “Basketball”}.

  In step S202, a semantic path between each concept pair in the query concept set is acquired based on the ontology.

  An ontology includes a number of known concepts and semantic paths between these concepts. By searching the concepts “USA” and “basketball” included in the query concept set in the ontology, the semantic path between the two concepts “USA” and “basketball” existing in the ontology is determined. For example, five meaning paths <produce (USA, basketball)>, <sell (USA, basketball)>, <hold (USA, basketball game)>, <use (basketball game, basketball)>, And <Production in (Basketball, USA)>.

  In step S203, the number of semantic paths between the concept pairs is determined based on the semantic paths between the concept pairs in the query concept set, and query semantic information is acquired.

  In one embodiment according to the present invention, based on the semantic path between each concept pair in the query concept set, a forward semantic path set and a reverse semantic path set between each concept pair are determined, and then Based on the number of elements in the set of forward semantic paths and the number of elements in the set of backward semantic paths, the number of semantic paths between each concept pair is acquired. For example, for a query concept set including two concepts “America” and “basketball”, from the concept “America” to the concept “basketball” based on the semantic path between the two concepts acquired in step S202. As a result, a set of forward semantic paths between the two concepts “America” and “Basketball” is obtained. Similarly, based on the semantic path between the two concepts acquired in step S202, a semantic path from the concept “basketball” to the concept “america” is detected. As a result, the two concepts “america” and “basketball” are detected. A set of backward semantic paths between “is obtained. Further, the number of elements in the forward semantic path set and the number of elements in the backward semantic path set are calculated, and the sum of the two elements is regarded as the number of semantic paths between the two concepts “America” and “Basketball”.

  In another embodiment according to the invention, a set of forward semantic paths and a set of backward semantic paths between each concept pair is determined based on the semantic paths between each concept pair in the query concept set. Thus, the redundant path is excluded from the set of forward semantic paths and the set of forward semantic paths is optimized, and the redundant path is excluded from the set of reverse semantic paths and the set of backward semantic paths is optimized. . Furthermore, the number of semantic paths between each pair of concepts is acquired based on the number of elements in the set of optimized forward semantic paths and the number of elements in the set of optimized backward semantic paths. For example, for a query concept set including two concepts “USA” and “basketball”, from the concept “USA” to the concept “basketball” based on the semantic path between the two concepts acquired in step S202. A set of forward semantic paths and a set of backward semantic paths are detected. Next, a redundant path is searched from a set of forward semantic paths, and a redundant path is searched from a set of backward semantic paths. By optimizing the set of forward semantic paths and the set of reverse semantic paths, redundant paths are excluded from the set of forward semantic paths and redundant paths are excluded from the set of reverse semantic paths. . Furthermore, the sum of the number of elements of the optimized forward semantic path set and the number of elements of the optimized backward semantic path set is calculated, and the sum of the two elements is the concept “America” and “basketball”. The number of semantic paths between

In the present invention, if r _m (C ₁ , C ₂ ) Λr _n (C ₂ , C ₃ ) → r _p (C ₁ , C ₃ ), the semantic path r ₁ between the concepts C ₁ and C ₃ . r _m r _n ... r _q is considered to be a redundant path with respect to another semantic path r ₁ ... r _p ... r _q (where C ₁ , C ₂ and C ₃ are three concepts, r _{1, ... r m, ... r} n, ... r p, ... r q , the relationship between the concept, the symbol "Λ" represents a relationship between "aND").

  In another embodiment according to the present invention, a set of forward semantic paths and a set of backward semantic paths between each concept pair is determined based on the semantic paths between each concept pair in the query concept set. In addition, a mutual path pair is determined based on a set of forward semantic paths and a set of reverse semantic paths. Next, the number of semantic paths between each concept pair is determined based on the number of elements in the forward semantic path set, the number of elements in the backward semantic path set, and the number of mutual path pairs. For example, for a query concept set including two concepts “USA” and “basketball”, based on the semantic path between the two concepts acquired in step S202, the concept “USA” to the concept “basketball”. A set of forward semantic paths and a set of reverse semantic paths are detected. Next, a mutual path pair is determined based on the set of forward semantic paths and the set of backward semantic paths. Furthermore, the number obtained by subtracting the number of mutual path pairs from the total number of elements in the forward semantic path set and the number of elements in the backward semantic path set is between the two concepts “America” and “Basketball”. Is considered as the number of paths.

In the present invention, when the set of forward semantic paths between the concepts C _i and C _j is S _ij and the set of backward semantic paths is S _ji , the path l ₁ is an element of the forward semantic path set S _ij , That, _{l 1} ∈S _ij and _{l 1 = r 1 (C 1} , C 2), ..., a _{r m (C 2m-1,} C 2m), the path _{l 2} of the set _{S ji} reverse sense path Elements i.e. l ₂ ∈ S _ji and l ₂ = r _m ⁻¹ (C _2m , C _2m−1 ),..., R ₁ ⁻¹ (C ₂ , C ₁ ), where r ⁻¹ is r is the inverse relationship, and (l ₁ , l ₂ ) is a mutual path pair).

  The query semantic information is constructed based on a query concept set included in the user's query, a semantic path between each concept pair in the query concept set, and the number of semantic paths. As mentioned above, query semantic information can be expressed in a number of ways. For example, the query semantic information can be expressed in the form of a query graph based on graph theory. In this case, the vertex of the query graph corresponds to one concept in the query concept set included in the query semantic information, and the query graph Corresponds to the semantic path between the two concepts of the query semantic information. The edge weight of the query graph corresponds to the number of semantic paths between the two concepts of the query semantic information. The query semantic information can also be expressed in the form of a text file. It should be noted that the query graph and text file shown here are merely examples, and those skilled in the art will understand that the query semantic information is not limited to this and can be expressed in many appropriate formats.

  In step S204, based on the ontology, a concept set included in the document and a concept set included in the query are extracted.

  In the present invention, “document” means any file that can be used by those skilled in the art, such as a Web page, a plain text file, a PDF file, a Word file, a PowerPoint file, and an Excel file.

  As described above, the concepts included in the user's query are determined in a number of ways based on the ontology, thereby extracting a set of concepts included in the query. Similarly, the concepts contained in the document are determined in a number of ways based on the ontology, thereby extracting the set of concepts contained in the document.

  In step S204, an operation of extracting a concept set included in the document and an operation of extracting a concept set included in the query are performed. Both of these operations can be performed simultaneously or sequentially. It will be understood that is merely illustrative and not essential.

  In one example in accordance with the present invention, a concept set contained in a document is extracted (ie, the document is preprocessed) before a user query is received. At that time, the semantic paths between concepts acquired by the preprocessing of the document can be stored in a database or memory. Next, when a user query is received, a concept set included in the query is extracted based on the ontology. Further, a document concept set is acquired based on the semantic path between the concept acquired by the pre-processing of the document and the query concept.

  In step S205, a document concept set is acquired based on a common part between the concept set included in the document and the concept set included in the query.

  In the present invention, the method for obtaining a document concept set and the method for obtaining a query concept set are not necessarily the same. The query concept set acquired in step S201 is directly extracted from the user's query based on the ontology. The document concept set and the query concept set acquired in step S205 include the same concept, but these concepts can be classified into a virtual concept and a common concept.

  A concept acquired based on an ontology from a common part between a concept set extracted from a document and a query concept set (that is, a concept set included in a query) is a common concept. For example, in step S204, the concept set included in the document and extracted based on the ontology is {“basketball”, “store”, “game”}, and included in the query and extracted based on the ontology. If the set is {“USA”, “basketball”}, the common part between the concept set included in the document and the concept set included in the query is determined as {“basketball”}. This is the common concept described above.

  In step S204, the concept “USA” is not included in the concept extracted from the document based on the ontology. Therefore, in the present invention, when it is determined that the concepts “America” and “basketball” are included in the document concept set, “USA” in the document concept set {“USA”, “basketball”} is Is considered a virtual concept. When the semantic paths between the concepts in the document concept set are subsequently determined, the number of semantic paths between the virtual concept and the common concept is all set to zero.

  In step S206, a semantic path between each concept pair in the document concept set is acquired based on the document.

  Unlike step S202, in step S206, the basis for determining the semantic path between each concept pair in the document concept set is the document and ontology. As a result, more characteristics and characteristics of the document itself are reflected, so that it is easy to determine the degree of coincidence between the document and the query.

  In step S207, the number of semantic paths between the concept pairs is determined based on the semantic paths between the concept pairs in the document concept set, and document semantic information is acquired.

  In one embodiment according to the present invention, a set of forward semantic paths and a set of backward semantic paths between each concept pair are determined based on the semantic paths between each concept pair in the document concept set. Based on the number of elements in the direction semantic path set and the number of elements in the reverse direction semantic path set, the number of semantic paths between the concept pairs is acquired.

  In another embodiment according to the present invention, a set of forward semantic paths and a set of backward semantic paths between the concept pairs are determined based on the semantic paths between the concept pairs in the document concept set. In addition, the redundant path is excluded from the set of forward semantic paths and the set of forward semantic paths is optimized, and the redundant path is excluded from the set of reverse semantic paths and the set of backward semantic paths is optimized. The Furthermore, the number of semantic paths between each pair of concepts is acquired based on the number of elements in the set of optimized forward semantic paths and the number of elements in the set of optimized backward semantic paths.

  In another embodiment according to the present invention, a set of forward semantic paths and a set of backward semantic paths between the concept pairs are determined based on the semantic paths between the concept pairs in the document concept set. In addition, a mutual path pair is determined based on a set of forward semantic paths and a set of reverse semantic paths. Thereafter, the number of semantic paths between each concept pair is determined based on the number of elements in the forward semantic path set, the number of elements in the backward semantic path set, and the number of mutual path pairs. In this embodiment, the definition of “mutual path pair” is the same as that in step S203.

  In each of the above embodiments, in the process of determining the number of semantic paths in the forward semantic path set and the number of semantic paths in the backward semantic path set, the number of semantic paths between the virtual concept and the common concept is all zero. Note that they are gathered.

  The document semantic information is constructed based on a document concept set included in the document, a semantic path between each concept pair in the document concept set, and the number of semantic paths. As mentioned above, document semantic information can be constructed in a number of ways. For example, the document semantic information can be expressed in the form of a document graph based on graph theory. In this case, the vertex of the document graph corresponds to one concept in the document concept set included in the document semantic information, and the document graph Corresponds to a semantic path between two concepts of document semantic information. The weight of the edge of the document graph corresponds to the number of semantic paths between the two concepts of the document semantic information. The document semantic information can also be expressed in the form of a text file. Those skilled in the art will understand that the document graphs and text files shown here are merely examples, and the document semantic information is not limited to this and can be expressed in many appropriate formats.

  In step S208, the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information are acquired.

  In step S209, based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information, a relationship semantic relevance score between the document semantic information and the query semantic information is determined.

  Step S209 can be performed in a number of ways. FIGS. 3-5 are each according to one embodiment of the present invention, and based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information, between the document semantic information and the query semantic information. A method for determining a relationship semantic relevance score is shown.

  FIG. 3 is a flowchart of a method for determining a relationship semantic relevance score between document semantic information and query semantic information according to an embodiment of the present invention.

  In step S301, the total number of semantic paths of the document semantic information is calculated as a document numerical value. In this step, first, the number of semantic paths between each concept pair in the document semantic information is obtained, and then the number is summed. In another embodiment of the present invention, the summed numerical value is optimized, for example, by further subtracting the redundant path number and the mutual path pair number from the numerical value.

  In step S302, the total number of semantic paths of the query semantic information is calculated as a query numerical value. In this step, first, the number of semantic paths between each concept pair in the query semantic information is acquired, and then the number is summed. In another embodiment of the present invention, the summed numerical value is optimized, for example, by subtracting the redundant path number and the mutual path pair number from the numerical value.

  In step S303, the ratio of the document numerical value to the query numerical value is determined as the relationship semantic relevance score between the document semantic information and the query semantic information. The flow in FIG. 3 ends here.

  FIG. 4 is a flowchart of a relationship semantic relevance score determination method between document semantic information and query semantic information according to another embodiment of the present invention.

  In step S401, a concept set included in the query semantic information is acquired.

  In one embodiment according to the present invention, assuming that the concept set included in the query semantic information is {“USA”, “basketball”, “game”}, according to the present invention, the concept set included in the document semantic information. Is the same as the concept set included in the query semantic information, and the difference is that the concept set included in the document semantic information includes a virtual concept or a common concept (or both). For example, all concepts in a set may be common concepts, all concepts may be virtual concepts, or a set may include both common concepts and virtual concepts.

  In step S402, the number of document semantic paths between each concept pair in the concept set is determined based on the document semantic information.

  When determining the number of semantic paths between each pair of concepts in a concept set, it is necessary to consider the presence or absence of virtual concepts. When determining a semantic path between two concepts, if at least one of the two concepts is a virtual concept, the number of semantic paths between the two concepts is zero.

  Further, it should be noted that the number of document semantic paths between each concept pair in the concept set is determined based on document semantic information, not ontologies.

  In step S403, the number of query semantic paths between each concept pair in the concept set is determined based on the query semantic information.

  It should be noted that the number of query semantic paths between concept pairs in the concept set is determined based on query semantic information, not ontologies.

  In step S404, the ratio of the number of document semantic paths to the number of query semantic paths is calculated for each concept pair.

  In step S405, the product of the respective ratios is determined as a relationship semantic relevance score between the document semantic information and the query semantic information.

For example, the number of document semantic paths between each concept pair is λ _i , and the number of query semantic paths between each concept pair is η _i (where i is an arbitrary number from 1 to K, and K is all in the concept set) The relationship semantic relevance score Score _R between the document semantic information and the query semantic information is expressed by the following equation.

  The flow in FIG. 4 ends here.

  FIG. 5 is a flowchart of a relationship semantic relevance score determination method between document semantic information and query semantic information according to another embodiment of the present invention.

  In step S501, a set of document spanning trees (panning trees) is determined based on the document semantic information.

  As described above, document semantic information can be expressed in the form of a document graph based on graph theory. In the field of graph theory, it is a well-known fact that document graphs can be decomposed into a plurality of spanning trees which are different from each other and all do not have a closed circuit. These spanning trees decomposed from the document graph constitute a document spanning tree set.

  In step S502, a query spanning tree set is determined based on the query semantic information.

  Similar to step S501, the query semantic information can be expressed in the form of a query graph based on graph theory, and the query graph can be decomposed into a plurality of spanning trees that are different from each other and do not have a closed circuit. These spanning trees decomposed from the query graph constitute a query spanning tree set.

  In step S503, based on the number of semantic paths in the document semantic information, the total number of combinations of semantic relations of documents described by each document spanning tree in the document spanning tree set is calculated.

  In step S504, based on the number of semantic paths in the query semantic information, the total number of combinations of query semantic relationships described by each query spanning tree in the query spanning tree set is calculated.

  In step S505, the semantic pair score of each spanning tree pair is determined based on the total number of combinations of document semantic relationships and the total number of combinations of query semantic relationships.

  A spanning tree pair is a pair of spanning trees composed of one of the query spanning trees in the set of query spanning trees and one corresponding spanning tree in the set of document spanning trees. One spanning tree of this pair has a one-to-one correspondence with the other spanning tree.

Edge weights between each two vertices (eg, corresponding concept) of each document spanning tree are λ ₁ , λ ₂ ,..., Λ _K, and each two vertices (eg, corresponding concept) of each query spanning tree. If the weights of the edges between them are η ₁ , η ₂ ,..., Η _K (where K is the total number of combinations in the case where each concept pair is created from all the concepts in the concept set), each spanning tree The pair semantic relevance score Score _tree is expressed by the following equation.

  In Equation (2), the numerator indicates the total number of combinations of the semantic relationships of the documents described by each document spanning tree in the document spanning tree set acquired in step S504, and the denominator is the query spanning acquired in step S505. Indicates the total number of semantic relationships of queries described by each query spanning tree in the tree set.

  In step S506, the average value of the semantic pair scores of the spanning tree pair is determined as the relationship semantic relevance score between the document semantic information and the query semantic information.

For example, the relationship semantic relevance score Score _R between document semantic information and query semantic information is calculated by the following equation.
Score _R = Mean (Score _tree ). (3)

Here, “Mean (x)” indicates an average value of x. In Equation (3), Mean (Score _tree ) indicates that the average value of the semantic relevance score Score _tree of each spanning tree pair is calculated. It will be appreciated that this average value may be an arithmetic average value, a weighted average value, or any other form of average value used by those skilled in the art.

  This is the end of the flow of FIG.

  In one embodiment according to the present invention, a set of document semantic information is pre-formed by obtaining document semantic information between all concepts in the document. Also, after receiving the query, the concepts in the query are obtained to form a query concept set. Thereafter, a sub-set of document semantic information is obtained by collating the query concept set with the document semantic information set. The document semantic information sub-set includes document semantic information for all concepts that are included in the document semantic information set and that match the concepts in the query concept set.

  Subsequently, the number of semantic paths in the document semantic information sub-set and the number of semantic paths in the query semantic information are acquired. Then, based on the number of semantic paths in the document semantic information sub-set and the number of semantic paths in the query semantic information, a relationship semantic relevance score between the document semantic information and the query semantic information is determined.

  In step S210, a concept-meaning relevance score between the document and the query is acquired.

  The concept semantic relevance score is a semantic relevance score between a document and a query from the viewpoint of a concept. The concept semantic relevance score can be calculated by a number of methods.

For example, a concept-meaning relevance score (referred to as Score _C ) may be calculated based on a vector space model. In this method, first, an n-dimensional query vector q = (q ₁ ,..., Q _n ) is constructed based on a query concept set (referred to as S _q ) and a semantic similarity calculation model (where, n is the total number of concepts in the ontology, each concept corresponding to one of the elements of the vector q). As an example of this semantic similarity calculation model, Non-Patent Document 4 (“Improved Semantic Simulating Modeling and Application”, Jilin University Press, Vol. 39, No. 1, 2009). ), Non-Patent Document 5 ("Using information content to evaluate semantic similarity in a taxonomy (use of information content for semantic similarity evaluation in taxonomy)"), In IJCAI '95). When setting the value of an element in the vector q, if the concept C _i (i = 1, 2,..., N) corresponding to the element appears in S _q , the value of the element is 1 Is gathered. If not, the value of the element is set to the semantic similarity between the target concepts in C _i and S _q .

の式で表され、
ここで、
ｆｒｅｑ_ｉ，ｄはドキュメント内に概念Ｃ_ｉが出現する頻度、

はドキュメント内の概念のうち最多の出現頻度を示す概念の頻度値、
ｎ_ｉはＣ_ｉによってマーキングされるドキュメントの総数、
Ｄは検索空間内のドキュメント集合である。 Next, when constructing an n-dimensional document vector d = (d ₁ ,..., D _n ), d _i (i = 1, 2,..., N) of each document, the concept C _i and the relevant document are The value is based on the appearance frequency of the concept C _i in the document, and the TF-IDF algorithm (Non-Patent Document 6 (“Introduction to Modern Information Retrieval”, McGraw-Hill) , 1983) This algorithm is

Represented by the formula
here,
freq _{i, d} is the frequency at which the concept C _i appears in the document,

Is the frequency value of the concept that shows the highest frequency of occurrence in the document,
n _i is the total number of documents marked by C _i ,
D is a set of documents in the search space.

Next, using the query vector q and the document vector d, a concept semantic relevance score Score _C is calculated according to the equation (4).

For example, Non-Patent Document 7 (“Categorizing and Ranking Search Engine's Results by Semantic Similarity (Classification and Ranking of Search Engine Results by Meaning of Similarity”, In Proceeding of ICUIMC'08). May be calculated by the described method, in which a query concept set S _q is obtained from a query, a document concept set S _d is obtained from a set of documents, and then each concept pair in S _q and S _d The semantic similarity between them is calculated, the average value of these similarities is calculated, and the concept semantic relevance score Score _C is obtained.

  It should be noted that a person skilled in the art can obtain the concept semantic relevance score by other known methods. The above-described method of obtaining the conceptual meaning relevance score is merely an example, and is not intended to limit the range.

  The concept semantic relevance score may be calculated in advance and stored in a storage device accessible by the document ranking device of the present invention. The storage device may be, for example, a local memory such as a semiconductor disk, a magnetic disk, an optical disk, or a floppy disk, a portable memory, or a memory that can be downloaded via a computer network such as the Internet.

  The conceptual meaning relevance score may be calculated in real time while the embodiment of the present invention is being executed (for example, step S210). Further, those skilled in the art are not limited to the specific examples disclosed herein, but use other suitable means based on current technical conditions and technical means to use the document's concept semantic relevance score and query. Would be able to get

  In step S211, the score of the document is determined based on each relationship relevance score and each concept relevance score.

In one embodiment according to the present invention, the relationship relevance score is Score _R , the concept relevance score is Score _C , the relationship relevance score and the concept relevance score are respectively a concept weight (λ _C ) and a relationship weight. Assume weighting using (λ _R ). Here, the values of the concept weight λ _C and the relationship weight λ _R are both in the range of 0 to 1, and the sum of the concept weight λ _C and the relationship weight λ _R is 1. The score of the document can be determined by summing the weighted relationship relevance score and the weighted concept relevance score. A method for determining the score (score _d ) of the document in this embodiment will be described below.
Score _d = λ _C · Score _C + λ _R · Score _R (5)

In equation (5), λ _R ∈ [0, 1], λ _C ∈ [0, 1], and λ _C + λ _R = 1.

Since the sum of the concept weight λ _C and the relationship weight λ _R is 1, Equation (5) can be simplified as follows.
Score _d = λ _C · Score _C + (1−λ) · Score _R (6)

  In Equation (6), λε [0, 1].

  In step S212, the documents are ranked based on the document score.

  When step S211 is completed, the score for the document to be ranked can be acquired. For example, if there are 10 documents to be ranked, the scores of these 10 documents are acquired in step S211. Next, in step S212, the ten documents can be ranked in descending order, ascending order, or in an order determined by one skilled in the art. Each score of the 10 documents indicates the magnitude of the semantic relevance regarding the concept and relationship between the document and the query entered by the user. The higher the document score, the greater the semantic relevance between the document and the user query, and the lower the document score, the smaller the semantic relevance between the document and the user query.

In another embodiment according to the present invention, steps S211 and S212 are performed by ranking the documents based on the concept relevance score, grouping the ranked documents, and further relating the individual documents of each document group. It can be replaced with the step of ranking based on the degree score. As an example, assume that there are 10 documents to be ranked. The ten documents are ranked with coarse granularity based on each document's concept relevance score Score _C and divided into several groups. Here, for example, it is assumed that ten documents are divided into two groups of five documents, and the concept relevance score of the first document group is larger than the concept relevance score of the second document group. The five documents in the first group are then ranked with fine granularity based on their respective relationship relevance scores. Thereby, the rank of the five documents in the first group is further adjusted based on the original rank of the five documents. Similarly, the five documents in the second document group are also finely ranked based on their relational relevance scores. As a result, a ranking format of 10 documents is acquired. In this ranking, both the concept relevance score and the relationship relevance score between the query and the document are considered. It also shows the magnitude of the semantic relevance for concepts and relationships between the document and the query entered by the user.

  This is the end of the flow of FIG.

  FIG. 6 is a block diagram of a document ranking apparatus 600 according to an embodiment of the present invention. The apparatus 600 includes a query meaning information extraction unit 601, a document meaning information extraction unit 602, a relationship meaning relevance score determination unit 603, and a ranking unit 604. The query semantic information extraction unit 601 is configured to extract query semantic information based on the user's query and ontology. The document semantic information extraction unit 602 is configured to extract document semantic information based on the document, the query, and the ontology. The relationship meaning relevance score determination means 603 is configured to determine a relationship meaning relevance score between document semantic information and query semantic information. The ranking means 604 is configured to rank the documents based on the relationship meaning relevance score.

  In one embodiment according to the present invention, the query semantic information extracting means 601 includes means for extracting a set of query concepts included in the user's query based on the ontology, and each concept in the query concept set based on the ontology. Means for obtaining a semantic path between the pairs, and means for determining the number of semantic paths between the concept pairs based on the semantic paths between the concept pairs in the query concept set.

  In one embodiment according to the invention, the means for determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the query concept set is the semantic path between each concept pair in the query concept set. Each of the concept pairs based on the number of elements in the forward semantic path set and the number of elements in the forward semantic path set. Means for acquiring the number of semantic paths between them.

  In another embodiment according to the present invention, the means for obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the reverse semantic path set is the forward semantic path set. For optimizing the forward semantic path set by excluding redundant paths from the path, means for excluding redundant paths from the reverse semantic path set and optimizing the reverse semantic path set, and optimized forward semantics Means for obtaining the number of semantic paths between each concept pair based on the number of elements of the path and the number of elements of the optimized backward semantic path set.

  In another embodiment according to the present invention, the means for obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the reverse semantic path set is the forward semantic path set. And a semantic path between each concept pair based on the number of elements in the forward semantic path set, the number of elements in the reverse semantic path set, and the number of mutual path pairs. Means for obtaining a number.

  In one embodiment according to the present invention, the document semantic information extraction unit 602 extracts a concept set included in the document and a concept set included in the query based on the ontology, and a concept set and query included in the document. Means for obtaining a document concept set based on a common part with the contained concept set, means for obtaining a semantic path between each pair of concepts in the document concept set based on the document, and each concept pair in the document concept set Means for determining the number of semantic paths between each pair of concepts based on the semantic paths between them.

  In another embodiment according to the present invention, the means for determining the semantic path between each concept pair based on the semantic path between each concept pair in the query concept set is a semantic path between each concept pair in the document concept set. Each of the concept pairs based on the number of elements in the forward semantic path set and the number of elements in the forward semantic path set. Means for acquiring the number of semantic paths between them.

  In another embodiment according to the present invention, the means for obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the reverse semantic path set is the forward semantic path set. Means for optimizing the forward semantic path set by excluding redundant paths from the path, and means for optimizing the reverse semantic path set by excluding redundant paths from the reverse semantic path set. Means for obtaining the number of semantic paths between each pair of concepts based on the number of elements in the forward semantic path set and the number of elements in the optimized backward semantic path set.

  In another embodiment according to the present invention, the means for obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the reverse semantic path set is the forward semantic path set. Meaning between each pair of concepts based on the means for determining a mutual path pair based on the reverse semantic path set, the number of elements in the forward semantic path set, the number of elements in the reverse semantic path set, and the number of mutual path pairs Means for obtaining the number of passes.

  In one embodiment according to the present invention, the relationship meaning relevance score determination means 603 includes means for obtaining the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information, and the semantic path in the document semantic information. Means for determining a relationship semantic relevance score between document semantic information and query semantic information based on the number and the number of semantic paths in the query semantic information.

  In another embodiment according to the present invention, the means for determining the relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information is , A means for calculating the total number of semantic paths in the document semantic information to obtain a document number, a means for calculating the total number of semantic paths in the query semantic information to obtain a query number, and a ratio of the document number to the query number And a means for obtaining a relationship semantic relevance score between the document semantic information and the query semantic information.

  In another embodiment according to the present invention, the means for determining the relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information is Means for acquiring a set of concepts included in the query semantic information, means for determining the number of document semantic paths between each pair of concepts in the concept set based on the document semantic information, and in the concept set based on the query semantic information Means for determining the number of query semantic paths between each concept pair, means for calculating the ratio of the number of document semantic paths to the number of query semantic paths between each concept pair, and the product of each ratio as the document semantic information and the query Means for determining as a relationship semantic relevance score between semantic information.

  In another embodiment according to the present invention, the means for determining the relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information is Means for determining a document spanning tree set based on document semantic information, means for determining a query spanning tree set based on query semantic information, and each element of the query spanning tree set is paired with each element of the document spanning tree set. 1, a plurality of spanning tree pairs are generated), and the total number of combinations of document semantic relationships described by each document spanning tree in the document spanning tree set is calculated based on the number of semantic paths in the document semantic information. Means and query semantic information A means for calculating the total number of combinations of query semantics described by each query spanning tree in the set of query spanning trees based on the number of semantic paths, and the total number of combinations of document semantic relations and the total number of combinations of query semantic relations Means for determining a semantic pair score of each spanning tree pair, and means for determining an average value of the semantic pair scores of the spanning tree pair to obtain a relation meaning relevance score between the document semantic information and the query semantic information.

  In one embodiment according to the present invention, the ranking means 604 determines the score of the document based on the means for obtaining a concept semantic relevance score between the document and the query, and the relationship relevance score and the concept relevance score. Means, and means for ranking the documents based on the score of the documents.

  In another embodiment according to the present invention, the means for determining the document score based on the relationship relevance score and the concept relevance score uses the relationship weight and the concept weight, respectively. Means for weighting the relevance score (the relation weight and the concept weight are both 0 to 1 and the sum of the relation weight and the concept weight is 1), and the weighted relation relevance score And a weighted conceptual relationship degree score to obtain a document score.

  In one embodiment according to the present invention, the ranking means 400 is ranked by means for obtaining a concept semantic relevance score between a document and a query, and means for ranking the documents based on the concept relevance score. Means for grouping documents, and means for ranking each document in each document group based on a relevance score.

  The present invention further includes code for performing query semantic information extraction based on user query and ontology, code for performing document semantic information extraction based on document, query, and ontology, document semantic information, and query semantic information. The present invention relates to a computer program product comprising a code for performing a relationship semantic relevance score determination between and a code for ranking documents based on the relationship semantic relevance score. Before use, the code is stored in a memory in another computer system (for example, stored in a portable memory such as a hard disk, an optical disk or a floppy disk), or via a computer network such as the Internet. Can be downloaded.

  The methods disclosed by the embodiments of the present invention may be implemented as software, hardware, or a combination of software and hardware. The hardware portion can be implemented using dedicated logic circuitry, and the software portion can be stored in memory and executed by a suitable instruction execution system such as a microprocessor, personal computer, mainframe or the like. In a preferred embodiment, the present invention can be implemented as software such as firmware, resident software, microcode, etc. The present invention is further embodied as a computer program product, available from a computer or accessible by a computer readable medium, that provides program code for use by or in connection with an instruction execution system such as a computer. Also good. A computer-usable or computer-readable medium means any tangible means for storing, storing, communicating, propagating, or carrying a program used by or connected to an instruction execution system, apparatus, or device. To do.

  Such media are electronic, magnetic, optical, electromagnetic, infrared, semiconductor systems (apparatus or device), propagation media, and the like. Examples of computer readable media include semiconductor or solid state storage devices, magnetic tape, portable computer diskettes, random access memory (RAM), read only memory (ROM), hard disks, and optical disks. Examples of current optical discs include compact disc read only memory (CD-ROM), compact disc read / write memory (CR-ROM), and DVD.

  A data processing system adapted to store or execute program code according to an embodiment of the present invention includes one or more processors or the like coupled directly to a memory device or via a system bus. In addition to the local memory and the mass storage device that can be used during the execution of the program code, the memory element includes at least one part of the program code in order to reduce the number of times the code is read from the mass storage device at the time of execution. A cache provided for temporary storage is included.

  Input / output devices (keyboard, display, pointing device, etc.) can be connected to the system directly or through an intermediate I / O controller. The system may further be coupled with a network adapter for connecting the system to other processing systems, remote printers, remote storage devices, etc. via a private / public intermediate network. Currently available network adapters include modems, cable modems, and Ethernet cards, but these are merely examples. The communication networks mentioned in this specification include various networks including a local area network (LAN), a wide area network (WAN), an IP protocol-based network (such as the Internet), and an end-to-end network (such as an ad hoc peer-to-peer network). Can be configured.

  The present invention has been described above with reference to preferred embodiments. However, the present invention is not necessarily limited to the above embodiments, and various modifications can be made within the scope of the technical idea. it can.

  Further, a part or all of the above-described embodiment can be described as in the following supplementary notes, but is not limited thereto.

(Appendix 1)
Extracting semantic information of the query based on the user's query and ontology;
Extracting document semantic information based on documents, queries and ontologies;
Determining a relationship semantic relevance score between the document semantic information and query semantic information;
Ranking the documents based on the relationship semantic relevance score, and a document ranking method.

(Appendix 2)
Extracting the query semantic information based on the user's query and ontology;
Extracting a set of query concepts contained in the user's query based on the ontology;
Obtaining a semantic path between each concept pair in the query concept set based on the ontology;
The document ranking method according to claim 1, further comprising: determining the number of semantic paths between the concept pairs based on the semantic paths between the concept pairs in the query concept set.

(Appendix 3)
Said step of determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the query concept set;
Determining a forward semantic path set and a reverse semantic path set between each concept pair based on a semantic path between each concept pair in the query concept set;
The document ranking method according to claim 2, further comprising the step of obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set. .

(Appendix 4)
Said step of extracting document semantic information based on documents, queries and ontologies,
Extracting a concept set included in the document and a concept set included in the query based on the ontology; and
Obtaining a document concept set based on a common part between a concept set included in the document and a concept set included in the query;
Obtaining a semantic path between each pair of concepts in the document concept set based on the document;
The document ranking method according to claim 1, further comprising: determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the document concept set.

(Appendix 5)
Determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the document concept set;
Determining a forward semantic path set and a reverse semantic path set between each concept pair based on a semantic path between each concept pair in the document concept set;
The document ranking method according to claim 4, further comprising the step of obtaining the number of semantic paths between concept pairs based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set. .

(Appendix 6)
Obtaining the number of semantic paths between each pair of concepts based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set;
Steps for optimizing the forward semantic path set by excluding redundant paths from the forward semantic path set;
Steps for optimizing the reverse semantic path set by excluding redundant paths from the reverse semantic path set;
The step of obtaining the number of semantic paths between each pair of concepts based on the number of elements of the optimized forward semantic path set and the number of elements of the optimized backward semantic path set. The document ranking method according to 3 or appendix 5.

(Appendix 7)
Obtaining the number of semantic paths between each pair of concepts based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set;
Determining a mutual path pair based on a forward semantic path set and a reverse semantic path set;
(C) obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set, the number of elements in the reverse semantic path set, and the number of mutual path pairs. 5. The document ranking method according to 5.

(Appendix 8)
Determining the relationship semantic relevance score between the document semantic information and query semantic information;
Obtaining the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information;
The method of claim 1, further comprising: determining a relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information. The document ranking method described.

(Appendix 9)
Determining the relationship semantic relevance score between document semantic information and query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in query semantic information;
Calculating the total number of semantic paths in the document semantic information as a document number;
Calculating the total number of semantic paths in the query semantic information as a query number;
The document ranking method according to appendix 8, further comprising: determining a ratio of the document numerical value to the query numerical value to obtain a relationship semantic relevance score between the document semantic information and the query semantic information.

(Appendix 10)
Determining the relationship semantic relevance score between document semantic information and query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in query semantic information;
Obtaining a set of concepts contained in the query semantic information;
Determining the number of document semantic paths between each pair of concepts in the concept set based on the document semantic information;
Determining the number of query semantic paths between each concept pair in the concept set based on the query semantic information;
Calculating the ratio of the number of document semantic paths to the number of query semantic paths between each concept pair;
The document ranking method according to claim 8, further comprising: determining a product of each ratio as a relationship semantic relevance score between the document semantic information and the query semantic information.

(Appendix 11)
Determining a relationship semantic relevance score between document semantic information and query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in query semantic information;
Determining a document spanning tree set based on document semantic information;
Determining a query spanning tree set based on query semantic information;
Calculating the total number of combinations of document semantic relationships described by each document spanning tree in the document spanning tree set based on the number of semantic paths in the document semantic information;
Calculating the total number of combinations of query semantic relationships described by each query spanning tree in the query spanning tree set based on the number of semantic paths in the query semantic information;
Determining a semantic pair score for each spanning tree pair based on the total number of document semantic relationship combinations and the total number of query semantic relationship combinations;
Determining an average value of the semantic pair score of the spanning tree pair to obtain a relationship semantic relevance score between the document semantic information and the query semantic information,
9. The document ranking method according to appendix 8, wherein each element of the query spanning tree set has a one-to-one correspondence with each element of the document spanning tree set, and a plurality of spanning tree pairs are generated.

(Appendix 12)
Ranking the documents based on the relationship semantic relevance score,
Obtaining a conceptual semantic relevance score between the document and the query;
Determining a score for the document based on the relationship relevance score and the concept relevance score;
The document ranking method according to claim 1, further comprising the step of ranking the document based on the score of the document.

(Appendix 13)
Determining the document score based on the relationship relevance score and the concept relevance score;
Weighting the relationship relevance score and the concept relevance score using the relationship weight and the concept weight, respectively,
Summing the weighted relationship relevance score and the weighted concept relevance score to obtain a document score,
13. The document ranking method according to appendix 12, wherein the relationship weight and the concept weight are both 0 to 1, and the sum of the relationship weight and the concept weight is 1.

(Appendix 14)
Ranking the documents based on the relationship semantic relevance score,
Obtaining a conceptual semantic relevance score between the document and the query;
Ranking the documents based on the concept relevance score;
Grouping the ranked documents;
The document ranking method according to claim 1, further comprising: ranking each document in each document group based on the relevance score.

(Appendix 15)
Query semantic information extraction means configured to extract query semantic information based on a user query and ontology;
Document semantic information extraction means configured to extract document semantic information based on documents, queries and ontologies;
A relationship semantic relevance score determining means configured to determine a relationship semantic relevance score between document semantic information and query semantic information;
A document ranking apparatus comprising: ranking means configured to rank documents based on a relation meaning relevance score.

(Appendix 16)
The query semantic information extraction means includes:
A means for extracting a set of query concepts contained in a user's query based on an ontology;
A means for obtaining a semantic path between each concept pair in the query concept set based on ontology;
The document ranking apparatus according to claim 15, further comprising: means for determining the number of semantic paths between the concept pairs based on the semantic paths between the concept pairs in the query concept set.

(Appendix 17)
Means for determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the query concept set,
Means for determining a forward semantic path set and a reverse semantic path set between each concept pair based on a semantic path between each concept pair in the query concept set;
The document ranking apparatus according to appendix 16, further comprising means for obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set. .

(Appendix 18)
The document semantic information extraction means includes
A means for extracting a concept set included in a document and a concept set included in a query based on an ontology;
Means for obtaining a document concept set based on a common part between a concept set included in a document and a concept set included in a query;
Means for obtaining a semantic path between each pair of concepts in a document concept set based on a document;
The document ranking apparatus according to appendix 15, further comprising means for determining the number of semantic paths between the concept pairs based on the semantic paths between the concept pairs in the document concept set.

(Appendix 19)
Means for determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the document concept set;
Means for determining a forward semantic path set and a reverse semantic path set between each concept pair based on a semantic path between each concept pair in the document concept set;
The document ranking apparatus according to appendix 18, further comprising means for acquiring the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set. .

(Appendix 20)
Means for obtaining the number of semantic paths between each pair of concepts based on the number of elements of the forward semantic path set and the number of elements of the backward semantic path set,
Means for excluding redundant paths from the forward semantic path set and optimizing the forward semantic path set;
Means for excluding redundant paths from the reverse semantic path set and optimizing the reverse semantic path set;
And means for obtaining the number of semantic paths between each pair of concepts based on the number of elements in the optimized forward semantic path set and the number of elements in the optimized backward semantic path set. The document ranking apparatus according to 17 or appendix 19.

(Appendix 21)
Means for obtaining the number of semantic paths between each pair of concepts based on the number of elements of the forward semantic path set and the number of elements of the backward semantic path set,
Means for determining a mutual path pair based on a forward semantic path set and a reverse semantic path set;
Supplementary note 17 or Supplementary note, comprising means for obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set, the number of elements in the backward semantic path set, and the number of mutual path pairs 19. The document ranking apparatus according to 19.

(Appendix 22)
The relation meaning relevance score determination means includes
Means for obtaining the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information;
(Supplementary note 15) comprising means for determining a relationship semantic relevance score between document semantic information and query semantic information based on the number of semantic paths in document semantic information and the number of semantic paths in query semantic information. The document ranking device described.

(Appendix 23)
The means for determining the relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information,
A means for calculating the total number of semantic paths in the document semantic information to obtain a document number;
A means for calculating the total number of semantic paths in the query semantic information and making it a query number;
The document ranking apparatus according to appendix 22, further comprising means for determining a ratio of the document numerical value with respect to the query numerical value to obtain a relationship meaning relevance score between the document semantic information and the query semantic information.

(Appendix 24)
The means for determining the relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information,
Means for acquiring a set of concepts included in the query semantic information;
Means for determining the number of document semantic paths between each pair of concepts in a concept set based on document semantic information;
Means for determining the number of query semantic paths between each pair of concepts in a concept set based on query semantic information;
Means for calculating the ratio of the number of document semantic paths to the number of query semantic paths between each concept pair;
The document ranking apparatus according to appendix 22, further comprising: means for determining a product of each ratio as a relationship semantic relevance score between the document semantic information and the query semantic information.

(Appendix 25)
The means for determining the relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information,
Means for determining a document spanning tree set based on document semantic information;
Means for determining a query spanning tree set based on query semantic information;
Means for calculating the total number of combinations of document semantic relationships described by each document spanning tree in the document spanning tree set based on the number of semantic paths in the document semantic information;
Means for calculating the total number of combinations of query semantic relationships described by each query spanning tree in the query spanning tree set based on the number of semantic paths in the query semantic information;
Means for determining a semantic pair score for each spanning tree pair based on the total number of document semantic relationship combinations and the total number of query semantic relationship combinations;
Means for determining an average value of the semantic pair score of the spanning tree pair to obtain a relationship semantic relevance score between the document semantic information and the query semantic information,
23. The document ranking apparatus according to appendix 22, wherein each element of the query spanning tree set corresponds to each element of the document spanning tree set on a one-to-one basis, and a plurality of spanning tree pairs are generated.

(Appendix 26)
The ranking means is
A means for obtaining a conceptual semantic relevance score between a document and a query;
Means for determining a score for a document based on a relationship relevance score and a concept relevance score;
The document ranking apparatus according to claim 15, further comprising means for ranking the document based on the score of the document.

(Appendix 27)
The means for determining the score of the document based on the relationship relevance score and the concept relevance score,
Means for weighting the relationship relevance score and the concept relevance score using the relationship weight and the concept weight, respectively;
Means for summing the weighted relationship relevance score and the weighted concept relevance score to obtain a score for the document,
27. The document ranking apparatus according to appendix 26, wherein the relation weight and the concept weight both have a value of 0 to 1, and the sum of the relation weight and the concept weight is 1.

(Appendix 28)
The ranking means is
A means for obtaining a conceptual semantic relevance score between a document and a query;
A means of ranking documents based on conceptual relevance scores;
A means of grouping ranked documents;
The document ranking apparatus according to appendix 15, further comprising means for ranking each document in each document group based on the relevance score.

601: Query semantic information extracting means 602: Document semantic information extracting means 603: Relation meaning relevance score determining means 604: Ranking means

Claims (10)

Extracting semantic information of the query based on the user's query and ontology;
Extracting document semantic information based on documents, queries and ontologies;
Determining a relationship semantic relevance score between the document semantic information and query semantic information;
Ranking the documents based on the relationship semantic relevance score, and a document ranking method. Extracting the query semantic information based on the user's query and ontology;
Extracting a set of query concepts contained in the user's query based on the ontology;
Obtaining a semantic path between each concept pair in the query concept set based on the ontology;
The document ranking method according to claim 1, further comprising: determining the number of semantic paths between the concept pairs based on the semantic paths between the concept pairs in the query concept set. Said step of determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the query concept set;
Determining a forward semantic path set and a reverse semantic path set between each concept pair based on a semantic path between each concept pair in the query concept set;
Obtaining the number of semantic paths between each pair of concepts based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set. Method. Said step of extracting document semantic information based on documents, queries and ontologies,
Extracting a concept set included in the document and a concept set included in the query based on the ontology; and
Obtaining a document concept set based on a common part between a concept set included in the document and a concept set included in the query;
Obtaining a semantic path between each pair of concepts in the document concept set based on the document;
2. The document ranking method according to claim 1, further comprising: determining the number of semantic paths between each concept pair based on a semantic path between each concept pair in the document concept set. Determining the number of semantic paths between each concept pair based on the semantic paths between each concept pair in the document concept set;
Determining a forward semantic path set and a reverse semantic path set between each concept pair based on a semantic path between each concept pair in the document concept set;
5. The document ranking according to claim 4, further comprising: obtaining the number of semantic paths between each concept pair based on the number of elements in the forward semantic path set and the number of elements in the backward semantic path set. Method. Determining the relationship semantic relevance score between the document semantic information and query semantic information;
Obtaining the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information;
And determining a relationship semantic relevance score between the document semantic information and the query semantic information based on the number of semantic paths in the document semantic information and the number of semantic paths in the query semantic information. Document ranking method described in. Ranking the documents based on the relationship semantic relevance score,
Obtaining a conceptual semantic relevance score between the document and the query;
Determining a score for the document based on the relationship relevance score and the concept relevance score;
The document ranking method according to claim 1, further comprising: ranking documents based on document scores. Determining the document score based on the relationship relevance score and the concept relevance score;
Weighting the relationship relevance score and the concept relevance score using the relationship weight and the concept weight, respectively,
Summing the weighted relationship relevance score and the weighted concept relevance score to obtain a document score,
8. The document ranking method according to claim 7, wherein the relation weight and the concept weight both have a value of 0 to 1, and the sum of the relation weight and the concept weight is 1. 9. Ranking the documents based on the relationship semantic relevance score,
Obtaining a conceptual semantic relevance score between the document and the query;
Ranking the documents based on the concept relevance score;
Grouping the ranked documents;
The document ranking method according to claim 1, further comprising: ranking each document in each document group based on the relevance score. Query semantic information extraction means configured to extract query semantic information based on a user query and ontology;
Document semantic information extraction means configured to extract document semantic information based on documents, queries and ontologies;
A relationship semantic relevance score determining means configured to determine a relationship semantic relevance score between document semantic information and query semantic information;
A document ranking apparatus comprising: ranking means configured to rank documents based on a relation meaning relevance score.

Images