Searching hypertext based multilingual web information

• US 7,711,682 B2
• Filed: 07/29/2005
• Issued: 05/04/2010
• Est. Priority Date: 07/30/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zhang, Ling
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Hotelling; Harold A
• Application Number:
  US11/192,477
• Publication Number:
  US 20060059132A1
• Time in Patent Office: 1,740 Days
• Field of Search: 707/710, 707/723, 707/739
• US Class Current: 707/771
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents

Abstract

The present invention provides methods, apparatus and systems for searching hypertext based multilingual Web information when searching on a network for keywords to be queried. A method includes: a receiving step for receiving keywords input by a user; a native language hypertext searching step for searching on the network, according to the keywords to be queried, for all hypertexts whose representing language is the same as a language representing the keywords and which matches the keywords to be queried; extracting hyperlinks related to an arbitrary language from all the searched hypertexts; a hyperlink ranking step for ranking the extracted hyperlinks according to the correlativity of the hyperlinks with the keywords to be queried; and returning to the user ranked search result. Thereby, an accurate cross language searching can be provided without extra machine translation effort, being more accurate and objective than machine translation, even than human translation.

Claims

1. A computer-implemented method comprising searching hypertext based multilingual Web information when searching on a network for keywords to be queried, the step of searching comprising steps of:

receiving keywords input by a user via a searching interface;

transferring the keywords to an analysis evaluation module for computing similarity between the keywords and hypertext information in a hypertext database;

using the analysis evaluation module for matching the keywords based on index data stored in a Web repository and performing an analysis of hyperlinks;

conducting a comprehensive evaluation based on the computing results of hypertext information retrieving and hyperlink analysis;

ranking hyperlinks according to the correlativity of the hyperlink text with the keywords; and

returning to the user a ranked search result;

wherein the hypertext similarity with respect to the keyword to be queried is determined as follows;

$S<br><br>\left(d_i,Q\right)=\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>d_{\mathrm{ij}}-q_j}{\sqrt{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>d_{\mathrm{ij}}^2-\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>q_j^2}}$

where d_i represents an i^th hypertext in a Web page d, d_ij represents a j'"'"'th dimension of the i'"'"'th hypertext, q_j represents the j'"'"'th dimension of a keyword Q, and S represents a hypertext similarity d_i with said keyword Q.

2. The computer-implemented method of claim 1, further comprising:

downloading Web pages in advance of the Internet and conducting data indexing, for quickly searching for the hypertext matched with the keyword to be queried; and

wherein the hyperlink ranking step further comprises performing ranking on the hyperlinks according to hypertext similarity with respect to the keyword to be queried and hyperlink ranks.

3. The method of claim 1 further comprising wherein preceding the step of receiving keywords the method comprises steps of:

using a web crawler to download from the Internet a plurality of Web pages, wherein the Web pages comprise hypertext information;

extracting from the Web pages all hyperlink texts and corresponding hyperlink addresses as well as Web page titles and multilingual Web information; and

processing the Web pages and storing the retrieved Web pages in a Web repository containing a URL database.

4. The method of claim 1 further comprising wherein preceding the step of conducting a comprehensive evaluation the method comprises the step of:

computing a similarity S of the hypertext with respect to the keyword to be queried, wherein each of hypertext d_j and keyword Q is represented by a vector, and a cosine value of the angle between the two vectors represents the similarity S.

5. The computer-implemented method of claim 2, wherein the hyperlink rank is determined through the following iterative computation:

$\mathrm{PR}<br><br>\left(v\right)=\mathrm{\varepsilon <br><br>}/n+\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>\underset{u,v\in <br><br>G}{\sum <br><br>}<br><br>\mathrm{PR}<br><br>\left(u\right)/\mathrm{outlink}<br><br>\left(u\right)$

where PR(v) refers to the rank of a Web page v, outlink(u) refers to the number of all the hyperlinks in a Web page u, n is the number of all Web pages, and ε

is an adjusting parameter.

6. The computer-implemented method of claim 3, wherein after conducting comprehensive evaluation according to the following computation, ranking is performed according to the comprehensive evaluation value:

$\begin{array}{c}\mathrm{PR}<br><br>\left(v\right)=\mathrm{\varepsilon <br><br>}/n+\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>\underset{u,v\in <br><br>G}{\sum <br><br>}<br><br>\mathrm{PR}<br><br>\left(u\right)/\mathrm{outlink}<br><br>\left(u\right)\\ R<br><br>\left(d\right)=\mathrm{PR}<br><br>\left(d\right)<br><br>\left\{1+\mathrm{\delta <br><br>}·<br><br>S<br><br>\left(d,Q\right)\right\}\end{array}$

where PR(v) refers to the rank of a Web page v, outlink(u) refers to the number of all the hyperlinks in a Web page u, n is the number of all Web pages, and δ

is an adjusting parameter;

R(d) is the comprehensive evaluation value, S represents the similarity of the hypertext d_j included in the Web page d with the keyword Q, and parameter δ

is used to adjust the weights of PR(d) and S in the computation of R(d).

7. A computer system comprising:

a web crawler configured for downloading information from the Web, wherein the information comprises hypertext-based multilingual Web information;

a storage device storing an index of the hypertext-based multilingual Web information;

an analysis evaluation module configured to search for keywords in the index of the hypertext based multilingual Web information for keywords and for computing similarity of hypertext corresponding to the URL with respect to the keywords;

an interface device for receiving the keywords input by a user;

a processor configured for;

searching for the keywords, for all hypertexts whose representing language is the same as a language representing the keywords and which matches the keywords to be queried;

extracting hyperlinks related to an arbitrary language from all the searched hypertexts;

conducting a comprehensive evaluation based on the computing results of hypertext information retrieving and the hyperlink analysis;

ranking the extracted hyperlinks according to the correlativity of the hyperlinks with the keywords to be queried; and

wherein the interface device is also for returning to the user ranked search results and the similarity of the hypertext with respect to the keyword to be queried is determined as follows;

$S<br><br>\left(d_i,Q\right)=\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>d_{\mathrm{ij}}-q_j}{\sqrt{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>d_{\mathrm{ij}}^2-\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>q_j^2}}$

where d_j represents an i^th hypertext in a Web page d, d_ij represents a j^th dimension of the i^th hypertext, q_i represents the j^th dimension of a keyword Q, and S represents a hypertext similarity d_i with said keyword Q.

8. The system of claim 7, wherein after the ranking, the hyperlink which is pointed to most includes the information matched most with the keyword.

9. The system of claim 7, wherein:

the web crawler conducts data indexing, for quickly searching for the hypertext matched with the keyword to be queried; and

ranking the extracted hyperlinks performs ranking on the hyperlinks according to hypertext similarity with respect to the keyword to be queried and hyperlink ranks.

10. The system of claim 9, wherein the hyperlink rank is determined through the following iterative computation:

$\mathrm{PR}<br><br>\left(v\right)=\mathrm{\varepsilon <br><br>}/n+\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>\underset{u,v\in <br><br>G}{\sum <br><br>}<br><br>\mathrm{PR}<br><br>\left(u\right)/\mathrm{outlink}<br><br>\left(u\right)$

where PR(v) refers to the rank of a Web page v, outlink(u) refers to the number of all the hyperlinks in a Web page u, n is the number of all Web pages, and ε

is an adjusting parameter.

11. The system of claim 9, wherein after conducting comprehensive evaluation according to the following computation, ranking is performed according to the comprehensive evaluation value:

$\begin{array}{c}\mathrm{PR}<br><br>\left(v\right)=\mathrm{\varepsilon <br><br>}/n+\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>\underset{u,v\in <br><br>G}{\sum <br><br>}<br><br>\mathrm{PR}<br><br>\left(u\right)/\mathrm{outlink}<br><br>\left(u\right)\\ R<br><br>\left(d\right)=\mathrm{PR}<br><br>\left(d\right)<br><br>\left\{1+\mathrm{\delta <br><br>}·<br><br>S<br><br>\left(d,Q\right)\right\}\end{array}$

where PR(v) refers to the rank of a Web page v, outlink(u) refers to the number of all the hyperlinks in a Web page u, n is the number of all Web pages, and ε

is an adjusting parameter;

R(d) is the comprehensive evaluation value, S represents the similarity of the hypertext d_i contained in the Web page d with the keyword Q, and parameter δ

is used to adjust the weights of PR(d) and S in the computation of R(d).

12. An article of manufacture comprising a physical computer usable storage medium having computer readable program code means embodied therein for causing a processor to search for hypertext based multilingual Web information for searching on a network for keywords to be queried, the computer readable program code means in said article of manufacture for causing a computer to perform the steps of:

receiving keywords input by a user via a searching interface;

searching for the keywords, for all hypertexts having a representing language the same as a language representing the keywords and which matches the keywords;

extracting hyperlinks related to an arbitrary language from all the searched hypertexts;

transferring the keywords to an analysis evaluation module for computing similarity between the keywords and hypertext information in a hypertext database;

using the analysis evaluation module for matching the keywords based on index data stored in a Web repository and performing an analysis of hyperlinks;

conducting a comprehensive evaluation based on the computing results of hypertext information retrieving and the hyperlink analysis;

ranking the extracted hyperlinks according to the correlativity of the hyperlinks with the keywords to be queried; and

returning to the user ranked search results

wherein;

in the hyperlink ranking step, the hyperlink which is pointed to most includes the information comprising the most matches with the keyword in the native language hypertext searching step,

Web pages are downloaded in advance from the Internet;

data indexing is conducted for quickly searching for the hypertext matched with the keyword; and

the hyperlink ranking step performs ranking on the hyperlinks according to hypertext similarity with respect to the keyword to be queried and hyperlink ranks;

wherein the hypertext similarity with respect to the keyword is determined as follows;

$S<br><br>\left(d_i,Q\right)=\frac{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>d_{\mathrm{ij}}-q_j}{\sqrt{\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>d_{\mathrm{ij}}^2-\underset{j=1}{\overset{n}{\sum <br><br>}}<br><br>q_j^2}}$

where d_i represents an i^th hypertext in a Web page d, d_ij represents a j^th dimension of the i^th hypertext, q_i represents the j^th dimension of a keyword Q, and S represents a hypertext similarity d_i with the keyword Q;

wherein the hyperlink ranking is determined through the following iterative computation;

$\mathrm{PR}<br><br>\left(v\right)=\mathrm{\varepsilon <br><br>}/n+\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br><br><br>\underset{u,v\in <br><br>G}{\sum <br><br>}<br><br>\mathrm{PR}<br><br>\left(u\right)/\mathrm{outlink}<br><br>\left(u\right)$

where PR(v) refers to the rank of a Web page v, outlink(u) refers to the number of all the hyperlinks in a Web page u, n is the number of all Web pages, and ε

is an adjusting parameter;

wherein after conducting comprehensive evaluation according to the following computation, the hyperlink ranking is performed according to the comprehensive evaluation value;

$\mathrm{PR}<br><br>\left(v\right)=\mathrm{\varepsilon <br><br>}/n+\left(1-\mathrm{\varepsilon <br><br>}\right)<br><br>\underset{u,v\in <br><br>G}{\sum <br><br>}<br><br><br><br>\mathrm{PR}<br><br>\left(u\right)/\mathrm{outlink}<br><br>\left(u\right)$ $R<br><br>\left(d\right)=\mathrm{PR}<br><br>\left(d\right)<br><br>\left\{1+S-S<br><br>\left(d,Q\right)\right\}$

wherein PR(v) refers to the rank of a Web page v, outlink(u) refers to the number of all the hyperlinks in a Web page u, n is the number of all Web pages, and ε

is an adjusting parameter;

wherein R(d) is the comprehensive evaluation value, S represents the similarity of the hypertext d_j included in the Web page d with the keyword Q, and parameter δ

is used to adjust the weights of PR(d) and S in the computation of R(d).