Retrieval of Structured Documents

• US 20090012956A1
• Filed: 09/16/2008
• Published: 01/08/2009
• Est. Priority Date: 01/06/2003
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Cui, Hang, Wen, Ji-Rong
• Granted Patent: US 8,046,370 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3341 using boolean model
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

This disclosure relates to performing a query for a search term of a database containing a plurality of structured documents. Those structured documents that do not include the search term are ferreted or filtered out during an initial search. Matched structured documents which are those structured documents that do contain the search term are evaluated by ranking the individual elements based on how well each individual element matches the search term, and indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

Claims

1. A method, comprising:

ranking structured elements within a structured document, the structured document includes a document element or root element, at least one section element, and at least one paragraph elements, the ranking including;

for each paragraph element, in which Weight(t_j,P_j) stands for the weight of the term t_i in the paragraph P_j, “

t_f(t_i,P_j)”

is the term frequency of t_i in this paragraph, N denotes the number of documents in the corpus, and n_i represents the number of documents containing the term t_i calculating the terms'"'"' weight according to the calculation;

$\mathrm{Weight}<br><br>\left(t_i,P_j\right)=\ln <br><br>\left(1+\mathrm{tf}<br><br>\left(t_i,P_j\right)\right)\times <br><br>\ln <br><br>\frac{N}{n_i};<br><br>$

for any section element E_j at the upper levels following a bottom-up fashion, in which “

I(t_i,E_j)”

is the entropy measure of the term t_i in element E_j, wherein if Weight(t_i,E_j)≧

average(E_j)+std_dev(E_j), the term t_i is selected as an index term of the element E_j and all sub-elements of E_j would eliminate t_i from their index term list, where “

average (E_j)”

denotes the arithmetic average of all terms'"'"' weights in the element E_j, and std_dev(E_j) denotes the standard deviation of these weights, calculating term weights using the calculation Weight(t_i,E_j)=ln(1+tf(t_i,E_j))×

I(t_i,E_j);

repeating the calculating the term weights using the calculation Weight(t_i,E_j)=ln(1+tf(t_i,E_j))×

I(t_i,E_j) until the root element (i.e., the document element) is reached;

obtaining paths for all evaluated candidate elements, and assign query terms'"'"' weight for elements to paths respectively;

ranking paths in which

$\ln <br><br>\frac{N}{n_i}$

is the inverse document frequency (IDF) value of query term t_i, which represents the query term'"'"'s weight and Q is the number of query terms in a query, using the calculation;

$\mathrm{Rank}<br><br><br><br>\left({\mathrm{Path}}_p\right)=\underset{i=1}{\overset{Q}{\sum <br><br>}}<br><br><br><br>\mathrm{Weight}<br><br>\left(t_i,E_j\right)\times <br><br>\ln <br><br>\frac{N}{n_i};<br><br><br><br>\mathrm{and}$

returning elements corresponding to the ranked paths in a descending order.

2. The method of claim 1, further comprising indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

3. The method of claim 2, wherein the indicating to the user includes displaying a hierarchical structure of the matched document to the user the structure.

4. The method of claim 3, wherein the displaying the hierarchical structure includes providing a hierarchical tree that displays the structure of the structured document.

5. The method of claim 1, wherein the ranking of the individual elements is indicated numerically.

6. The method of claim 1, wherein the ranking of the individual number is indicated by providing a number of graphic indicators.

7. The method of claim 6, wherein the number of graphic indicator includes a number of asterisks.

8. The method of claim 1, further comprising weighting individual elements, wherein the weighting individual elements includes an entropy measure.

9. A method, comprising

displaying ranked elements of a structured document containing a search term by:

ranking individual elements of the document based on a number of appearances of the search term in each of the individual elements;

displaying a hierarchical structure of the structured document by providing a hierarchical tree that displays a structure of the individual elements of the structured document; and

indicating to the user the ranking of the individual elements wherein the individual elements can be accessed by the user.

10. The method of claim 9, wherein indicating to the user the ranking of the individual elements includes presenting graphic indicators associated with each of the individual elements wherein a number of graphic indicators presented for each of the individual elements is proportional to the ranking the individual elements.