Patent Publication Number: US-6907562-B1

Title: Hypertext concordance

Description:
SUMMARY OF THE INVENTION 
     A system and method in accordance with an embodiment of the invention addresses the problems of unlinked or sparsely linked documents by linking them using a set of automatically extracted content words, the “index terms.” Upon receiving a list of documents for indexing, the system and method in accordance with an embodiment of the invention automatically selects the terms to be indexed and generates a hypertext concordance (an “HC”). A concordance is an index where each of the indexed terms is listed with surrounding text, i.e., in context. As well, each of the indexed terms in the HC is given a hyperlink, instead of a page number, back to the occurrence of the term in a version of the indexed document. In one embodiment of the invention, the original document that has been indexed is also revised to include hyperlinks from the index terms into the HC. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention will be described with respect to particular embodiments thereof, and reference will be made to the drawings, which are not necessarily drawn to scale, and in which: 
         FIG. 1  is a generalized block diagram illustration of the documents input into and output from a system in accordance with an embodiment of the invention; 
         FIG. 2  shows an example of a user prompt display screen in accordance with an embodiment of the invention; 
         FIG. 3  shows an example of a display indicating results to a user in an embodiment of the invention; 
         FIG. 4  is a generalized block diagram showing an HC in accordance with an embodiment of the invention; 
         FIG. 5  is an example display screen showing an index term list in accordance with the invention; 
         FIG. 6  is an example display screen showing a portion of a concordance listing in accordance with an embodiment of the invention; 
         FIG. 7  shows an example HCD in accordance with an embodiment of the invention; and 
         FIG. 8  shows a flow diagram illustrating the steps of a method in accordance with an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     A system and method that allows a user to more readily access the information in documents lacking hyperlinks is disclosed. More specifically, as illustrated in  FIG. 1 , a document  102  that has been specified by a user for indexing is input into an HC (a “Hypertext Concordance”) generator  104 . The HC generator is implemented in software in one embodiment, although embodiments done in firmware, software, hardware, or any combination thereof are also foreseeable. The HC generator outputs two documents: (1) the HC itself  106 , having the indexed terms listed in concordance format, and (2) a version  108  of the original document  102  revised to include links into the HC from the indexed terms. The revised document  108  is hereafter referred to as the “HC document” or the HCD.” 
     An example of a concordance listing  601  for an HC in accordance with the invention is shown in  FIG. 6  for the term “conversion agreement.”  FIG. 6  shows the term “conversion agreement” at  602  followed by several lines  608  of text. Each line of text contains the term “conversion agreement” in context, which in this example is four words to the left of the term and four words to the right (note that in this example, certain punctuation marks are deemed a single word). Each occurrence of the term “conversion agreement” is also hyperlinked into the HCD, so that a user who points to and clicks on a particular occurrence of the term in the concordance listing will instantly be brought to the selected occurrence of the term in the text of the indexed document. Hyperlinks are represented in  FIG. 6  by underlining the hyperlinked term, as is commonly done in the art. Of course other methods for designating a hyperlink will also be acceptable, e.g., denoting a hyperlinked term in a different color, etc. 
     Referring to  FIG. 2 , in accordance with an embodiment of the invention, a user is prompted at  202  (from a computer display) to enter one or more URLs (uniform resource locators) of websites that are to be indexed and/or to enter the file names of other electronically stored documents. Although the indexing of websites is often referred to herein, it is to be understood that the concepts described herein will apply equally to non-web page documents, provided that such documents are electronically stored, or if the documents are paper documents, that they are first scanned and undergo optical character recognition (OCR), thereby transferring them into electronic documents. At  204 , the user enters one or more file names or URLs, here designated Filename 1 , Filename 2 , and Filename 3 . 
     Once the files names or URLs have been specified, the HC Generator  104  automatically analyzes the documents and extracts the index terms. The index terms can be selected by any of a variety of methods. One method used in an embodiment of the invention is Damerau&#39;s method described in Damerau, “Generating and Evaluating Domain-Oriented Multi-Word Terms From Text,”  Information Processing and Management , Vol. 29, No. 4, pp. 433-447 (Pergamon Press Ltd. 1993), incorporated by reference herein. Using Damerau&#39;s method, the terms are automatically selected by comparing their in-document frequency with their frequency in general English, as derived from a reference corpus such as a newspaper text. In many embodiments, both words and two-word phrases are considered. Some embodiments may also consider phrases with more than two words and non-contiguous phrases. The system will compare the relative frequencies of words and phrases in the documents to be indexed (coll 1 ) and the relative frequencies of words and phrases in a reference collection (coll 2 ), such that 
         score   ⁡     (   wordj   )       =         f   ⁡     (     wordj   ,     coll   1       )         f   ⁡     (     coll   1     )         ÷       f   ⁡     (     wordj   ,     coll   2       )         f   ⁡     (     coll   2     )               
 
where f(word j , coll i ) is the frequency of the word j in collection i, and f(coll i ) is the number of substantive words in collection i. In one embodiment, the reference collection is taken from all issues of The New York Times from 1990, which is a sufficiently broad corpus to model frequencies of words in general English well. The words and phrases in the submitted (input) documents are scored and ranked according to the ratio of the frequency of the words/phrases in the submitted (input) documents and the frequency of the words/phrases in the referenced text. The top n terms are selected as the index terms (e.g., n=200), which are generally those terms that occur significantly more often in the documents of interest than in the reference corpus. In many embodiments of the invention, words found in a stop list, which contains common words that are generally without much substance, such as articles, pronouns, etc., are excluded from the ranking.
 
     As will be understood by those of skill in the art many other methods of selecting index terms are available. The following is a list of other methodologies known:
         1. Selection according to raw frequency within a text, sometimes with part-of-speech prefilters or postfilters. Ross and Tukey, “Index to Statistics and Probability,” pps. iv-x, (R&amp;D Press 1975); Justeson and Katz, “Technical Terminology: Some Linguistic Properties and an Algorithm for Identification in Text.”  Natural Language Engineering , 1(1):9-27 (1995), Kupiec, Pedersen, and Chen, “A Trainable Document Summarizer,”  Proceedings of the  18 th    Annual International ACM SIGIR Conference , pps. 68-73 (1995).   2. Selection according to low variance in relative position (that is if two words occur at a fixed distance from each other whenever they co-occur, they are likely to be terminology). Smadja, “Retrieving Collocations from Text: Xtract,”  Computer Linguistics , 19(1):143-177 (1993).   3. Hypothesis testing and mutual information. Church and Hanks, “Word Association Norms, Mutual Information and Lexicography,”  Proceedings of the  27 th    Annual Meeting of the Association for Computational Linguistics , pps. 76-83, (1989).   4. Likelihood ratios within a text assuming a bi-nomial distribution. Dunning, “Accurate Methods for the Statistics of Surprise and Coincidence.”  Computer Linguistics , 19(1):61-74, (1993).   5. Residual idf Assuming a Poisson Distribution. Church, “One Term or Two?”,  Proceedings of the  18 th    Annual Int&#39;l ACM SIGIR Conference , pps. 310-318 (1995).   6. Finding index terms based on finite-state automaton parsing. Grefenstette,  Explorations in Automatic Thesaurus Discovery  (Kluwer Academic Press, 1994).   7. Finding index terms based on full parsing. Bourigault, “An Endogeneous Corpus-Based Method for Structural Noun Phrase Disambiguation,”  Proceedings of EACL , pps. 81-86 (1993); Jacquemin, “FASTR: A Unification-Based Front-End to Automatic Indexing,”  Proceedings of Recherche d&#39;Information assistèe par {dot over (O)}rdinateur  ( RIAO ), pps. 34-47 (1994); Strzalkowski, “Natural Language Information Retrieval,” IP&amp;M, 31(3):397-417(1995).   8. Terminology extraction based on deeper semantic analysis and theory. Pustejovsky et al., “Lexical Semantic Techniques for Corpus Analysis,  Computer Linguistics , 19(2):331-358 (1993).   9. Identifying boundaries of terminological phrases as points where the uncertainty of predicting the previous or next word is highest. Nakagawa and Mori, “Nested Collocation and Compound Noun for Term Extraction,”  Proceedings of First Workshop in Computational Terminology  (1998).       

     Nonetheless, Damerau&#39;s method is often preferable to those listed above because it uses an additional source of information instead of simply looking at the document of interest. Damerau&#39;s method can also be applied to very short documents while many of the above-mentioned methods require large collections to be effective. 
     Referring now to  FIG. 3 , once the index terms have been extracted and the HC and HCD built (as described more below), a system in accordance with the invention displays a results page to the user. Shown on the results page is a file name  302  for the HC  106 , and a list  304  of the resulting HCD files, which have been derived from the files that were originally submitted by the user. In many embodiments, even if more than one file was input by a user, only one HC will be output, although each of the submitted files will have its own HCD. 
       FIG. 4  shows an embodiment of the HC  106  as divided into two parts: the first part is an index term list  500 , and the second part is a concordance  600 . The index term list will be described with respect to  FIG. 5 , and the concordance will be described with respect to FIG.  6 . 
       FIG. 5  shows an example of an index term list  500  that forms the first part of the HC  106  in some embodiments of the invention. All of the terms extracted from the submitted documents are listed in alphabetical order. In many embodiments of the invention, the listed index terms are each hyperlinked to the beginning of the respective entry in concordance  600  (shown in FIG.  6 ). For instance, by clicking on the term “conversion agreement” in the listing of  FIG. 5 , the user will be brought to the concordance listing  601  for the entry for “conversion agreement.” Although an index term list  500  is desirable to aid the user in navigating to the most relevant terms, enabling the user to quickly jump to any term—even those not currently in the user&#39;s view—many embodiments of the invention do not need to include such an index term list. 
       FIG. 6  illustrates a concordance  600 , the second part of the HC  106 . Only the listing for a single term, “conversion agreement,” is shown, but it is to be understood that there will be many other terms, which will typically appear in alphabetical order. As shown, the concordance listing  601  in accordance with one embodiment of the invention has several parts. First, the index term  602  is listed. Links to other indexed terms  604  that share words with the index term are also listed. For instance as shown in  FIG. 6 , the terms “agreement dated” and “letter agreement” are listed, both sharing the word “agreement” with the two-word term “conversion agreement.” Then, each line  608  shows each occurrence of the index term in context. Although the number of words shown surrounding each index term is eight (four preceding and four succeed the term), other embodiments will have a different number of words supplied as context or will have phrases based as linguistic analysis (instead of a fixed number of words to the left and right). At the beginning of each context listing appears a document identifier  606 , indicating the document to which the occurrence of the term belongs. Each occurrence of the indexed term is also hyperlinked to the indexed document. By clicking on the index term in the concordance line, the user is immediately brought to the occurrence of the term in the indexed document. For instance, by clicking on “conversion agreement” in concordance line  608   6  the user will be displayed the portion of the document, shown in  FIG. 7 , containing the line &lt;description&gt; Xerox conversion agreement dated Mar. 2, 1994. 
     In a similar manner, in an embodiment of the invention, the indexed document is revised to include hyperlinks back into the concordance HC. For instance, clicking on the term “conversion agreement” on the first line of the document displayed in  FIG. 7 , will bring the user back to the concordance listing  601 , and particularly to line  608   6 . Nonetheless, some embodiments do not generate an HCD  108 , i.e., a document including hyperlinks back into the HC. In some embodiments, links from the HC simply bring the user into the original, unrevised document to the extent the original document has hyperlink anchors in the appropriate locations. 
     A summary of all the steps taken in accordance with an embodiment of the invention are described with respect to the flow chart of FIG.  8 . In step  802 , the system receives a listing of documents to be indexed from the user. In step  804 , the system and method in accordance with the invention extracts index terms, for instance, using Damerau&#39;s method. All words and word pairs (bi-grams) are considered except for those contained in a stop list. The top n terms are selected according to the likelihood ratio. 
     In step  806 , a system in accordance with the invention generates the HC  106 . To do so, the system retrieves the context surrounding each index term and generates concordance lines  608  with hypertext links into the original document or a revised version thereof. In many embodiments of the invention, in step  808 , an HCD is formed, a revised version of the original document that includes hyperlinks from each of the index terms back into the concordance. Of course, the order of the steps listed in  FIG. 8  may be varied as would be understood by those of skill in the art. 
     Hence, a system and method has been disclosed that allows a user to more readily access the information in non-hyperlinked documents, including web pages and other electronically stored documents. The HC is useful for look-up, similar to the traditional use of a book index, but page numbers (and the labor of finding them) are unnecessary since hyperlinks are used. Moreover, because entries of terms are given with context, the user can more easily identify the use of the word he or she is looking for. As well as look-up, the HC is also useful for browsing. The user can use a standard browser to browse the transformed document collection, either starting from the index or from the transformed document. 
     It should be understood that the particular embodiments described above are only illustrative of the principles of the present invention, and various modifications could be made by those skilled in the art without departing from the scope and spirit of the invention.