Source: http://www.google.com/patents/US5778400?dq=6,998,619
Timestamp: 2017-07-27 06:57:35
Document Index: 579230534

Matched Legal Cases: ['art.\n1', 'art; 2', 'art 2', 'art; 12', 'art; 13', 'art; 14', 'art; 15', 'art; 16', 'art; 17']

Patent US5778400 - Apparatus and method for storing, searching for and retrieving text of a ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsAn apparatus and a method for efficiently searching through a tagged document for the location of a desired word in text using tags as reference units for search and retrieval, whereby any of the referenced words in the text is searched for and retrieved quickly. The apparatus comprises: a document inputting...http://www.google.com/patents/US5778400?utm_source=gb-gplus-sharePatent US5778400 - Apparatus and method for storing, searching for and retrieving text of a structured document provided with tagsAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS5778400 APublication typeGrantApplication numberUS 08/605,795Publication dateJul 7, 1998Filing dateFeb 22, 1996Priority dateMar 2, 1995Fee statusLapsedPublication number08605795, 605795, US 5778400 A, US 5778400A, US-A-5778400, US5778400 A, US5778400AInventorsMasakazu TatenoOriginal AssigneeFuji Xerox Co., Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (7), Non-Patent Citations (4), Referenced by (68), Classifications (15), Legal Events (6) External Links: USPTO, USPTO Assignment, EspacenetApparatus and method for storing, searching for and retrieving text of a structured document provided with tags
US 5778400 AAbstract
An apparatus and a method for efficiently searching through a tagged document for the location of a desired word in text using tags as reference units for search and retrieval, whereby any of the referenced words in the text is searched for and retrieved quickly. The apparatus comprises: a document inputting part for inputting a structured document including reference units delimited by tags; a dividing part for dividing into reference units the structured document input by the document inputting part; a word extracting part for extracting words from the reference units divided by the dividing part; a tuple generating part for generating tuples comprising the locations of the reference units divided by the dividing part and the words extracted by the word extracting part from the reference units; a search index generating part which, given the tuples generated by the tuple generating part out of the locations of the reference units and the words from the reference units, generates a search index comprising the words and the locations of the reference units including the words; and a storing part for storing the search index, generated by the search index generating part, in conjunction with the structured document input by the document inputting part.
1. A structured document searching apparatus comprising:document inputting means for inputting a structured document including reference units delimited by tags; dividing means for dividing into reference units the structured document input by said document inputting means; word extracting means for extracting words from said reference units divided by said dividing means; tuple generating means for generating tuples comprising the locations of said reference units divided by said dividing means and the words extracted by said word extracting means from said reference units; search index generating means which, given the tuples generated by said tuple generating means out of the locations of said reference units and the words from said reference units, generates a search index comprising said words and said locations of said reference units including said words; and storing means for storing said search index, generated by said search index generating means, in conjunction with said structured document input by said document inputting means. 2. A structured document searching apparatus according to claim 1, further comprising:searching means which, when a target word is input, searches for said target word through the words within said search index generated by said search index generating means; and displaying means which, when said searching means detects said target word in a reference unit, displays the content of said reference unit including said target word within said structured document stored by said storing means in conjunction with said search index, the display being made by use of the location of said reference unit comprising said target word. 3. A structured document searching apparatus according to claim 1, wherein said reference units of any structured document input by said document inputting means include a reference unit type identification field each;wherein said word extracting means extracts as word-field pairs the words from and the fields of said reference units, said reference units having been separated by said dividing means; wherein said tuple generating means generates tuples each comprising the location of each reference unit separated by said dividing means and the word-field pairs extracted from that reference unit by said word extracting means; and wherein said search index generating means generates, out of the tuples each generated by said tuple generating means and comprising the location of each reference unit and the word-field pairs extracted from that reference unit, a search index including said word-field pairs and the locations of said reference units comprising the words within said word-field pairs. 4. A structured document searching apparatus according to claim 3, further comprising:searching means which, when a target word-field pair is input, searches for said target word-field pair through the word-field pairs in said search index generated by said search index generating means; and displaying means which, when said searching means detects said target word-field pair in a reference unit, displays the content of said reference unit including the detected word within said structured document stored by said storing means in conjunction with said search index, the display being made by use of the location of said reference unit comprising said target word-field pair. 5. A structured document searching apparatus according to claim 1, wherein the reference units of said structured document input by said document inputting means comprise pairs of reference unit attributes and the values corresponding thereto; andwherein said word extracting means extracts as words the pairs of reference unit attributes and the corresponding attribute values from the reference units separated by said dividing means. 6. A structured document searching apparatus according to claim 5, further comprising:searching means which, when a target attribute and the attribute value corresponding thereto are input, searches for said target attribute and for the corresponding attribute value through the pairs of attributes and attribute values in said search index generated by said search index generating means; and displaying means which, when said searching means detects said target attribute and the value thereof in a reference unit, displays the content of said reference unit including the detected pair of attribute and attribute value within said structured document stored by said storing means in conjunction with said search index, the display being made by use of the location of said reference unit comprising the detected pair of attribute and attribute value. 7. A structured document searching apparatus according to claim 3, wherein the reference units of said structured document input by said document inputting means comprise pairs of reference unit attributes and the values corresponding thereto; andwherein said word extracting means extracts as words the pairs of reference unit attributes and attribute values from the reference units separated by said dividing means. 8. A structured document searching apparatus according to claim 7, further comprising:searching means which, when a target attribute and the attribute value corresponding thereto are input, searches for said target attribute and for the corresponding attribute value through the pairs of attributes and attribute values in said search index generated by said search index generating means; and displaying means which, when said searching means detects said target attribute and the value thereof in a reference unit, displays the content of said reference unit including the detected pair of attribute and attribute value within said structured document stored by said storing means in conjunction with said search index, the display being made by use of the location of said reference unit comprising the detected pair of attribute and attribute value. 9. A structured document searching method for use with a structured document searching apparatus, the method comprising the steps of:(a) inputting a structured document including reference units delimited by tags; (b) dividing into reference units the structured document input in the step (a); (c) extracting words from said reference units divided in step (b); (d) generating tuples comprising the locations of said reference units divided in the step (b) and the words extracted in the step (c) from said reference units; (e) given the tuples generated in the step (d) out of the locations of said reference units and the words from said reference units, generating a search index comprising said words and said locations of said reference units including said words; and (f) storing said search index, generated in the step (e), in conjunction with said structured document input in the step (a). 10. A structured document searching method according to claim 9, further comprising the steps of:(g) when a target word is input, searching for said target word through the words within said search index generated in the step (e); and (h) when said target word is detected in a reference unit in the step (g), displaying the content of said reference unit including said target word within said structured document stored in the step (f) in conjunction with said search index, the display being made by use of the location of said reference unit comprising said target word. Description
In the above example, the tag <paragraph> stands for the beginning of the paragraph and is called a start tag. Another tag </paragraph> denotes the end of the paragraph and is called an end tag. That is, the example above shows a paragraph marked with the start tag <paragraph> and the end tag </paragraph>, distinguished partially as an element of the document text. The text portion flanked by the two tags represents a partial content of the tag-designated document structure.
The content of the DTD 100 in FIG. 10 is further described below in more detail. The DTD here is described according to the SGML notation and is thus interpreted according thereto. Specifically, the first symbols "<|" on each line of the DTD content constitute a markup declaration delimiter. The word "ELEMENT" following the markup declaration delimiter without blank is an element declaration keyword. The first delimiter and element "<|ELEMENT" designate how the content of the structure (i.e., subordinate structure) is to be determined by the subsequent description. The names given to the items that follow (document, chapter, title, paragraph, figure, etc.) represent the names of the tags for these items.
For example, if the subordinate structure of a tag is defined as "(chapter title, paragraph*, chapter*)," it means a subordinate structure wherein a paragraph is repeated zero or more times after the chapter title, followed by a chapter repeated zero or more times. Furthermore, if the subordinate structure of a tag is defined as "(title, (paragraph|figure)*, chapter*)," as on the second line of the DTD 100 in FIG. 10, it means a subordinate structure wherein a paragraph or figure is repeated zero or more times after the title, followed by a chapter repeated zero or more times.
In the document structure prototype defined by the DTD of FIG. 10, the document in question begins with the start tag "<document>" and comprises repeated chapters. Each of the chapters includes a title followed by a "paragraph" or "figure" repeated zero or more times, which in turn is followed by a "chapter" again repeated zero or more times. The titles and paragraphs are composed of character data.
A look at the SGML document 110 (a typical structured document) in FIG. 11 lets one understand that neither the start tag nor the end tag for the subordinate structure "title" of the "chapter" appears in this document. In fact, a start tag "<title>" is omitted between the tag "<chapter>" in the second line on the one hand, and its content "What is SGML?" on the other. Whether or not such a tag is omitted can only be known by referring to the DTD 100. That is, the exact structure of the target document can be read only in conjunction with the DTD furnished thereto.
Suppose that the SGML document of FIG. 11 is subjected to the process of restoring tags (i.e., structure). The process results in an SGML document 120 of FIG. 12. In the SGML document 120, the underlined parts indicate restored tags (structure). This target document is acquired by referring to the DTD 100 and thereby restoring the omitted tags. Specifically, under the rules defining the "chapter" structure, the tag <title> must exist after the tag <chapter> and thus the tag <title> is restored following the tag <chapter>. Similarly, the tag <title> must exist after the tag <figure> and thus the tag <title> is restored following the tag <figure>. Because each end tag is omitted, the respective end tags are restored after the contents (</title>, </paragraph>, etc., before the next corresponding tag). In this manner, the omitted tags (structure) are restored as shown underlined.
It is therefore an object of the present invention to overcome the above and other deficiencies and disadvantages of the prior art and to provide an apparatus and a method for efficiently searching through a tagged document for the location of a desired word in text using the tags as reference units for search and retrieval, whereby any of the referenced words in the text is searched for and retrieved with efficiency.
FIG. 1 is a block diagram outlining a structured document searching apparatus practiced as a first embodiment of the invention;
Preferred embodiments of the present invention will now be described with reference to the accompanying drawings. FIG. 1 is a block diagram showing major portions of a structured document searching apparatus practiced as the first embodiment. In FIG. 1, reference numeral 1 is a search word storing part; 2 is a stored word searching part 2; 3 is a text file of a tagged document; 4 is a search index attached to the text file; 11 is a reference unit dividing part; 12 is a word location extracting part; 13 is a sorting part; 14 is a search index generating part; 15 is a target word input part; 16 is a searching part; 17 is a text reference unit output part; and 18 is a search result output and display part.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4803643 *Aug 10, 1987Feb 7, 1989Oclc Online Computer Library Center IncorporatedSystem and method for creating memory-retained, formatted pages of text, tabulation, and graphic dataUS5557722 *Apr 7, 1995Sep 17, 1996Electronic Book Technologies, Inc.Data processing system and method for representing, generating a representation of and random access rendering of electronic documentsUS5587902 *May 26, 1993Dec 24, 1996Sharp Kabushiki KaishaTranslating system for processing text with markup signsJPH05135054A * Title not availableJPH06119331A * Title not availableJPH06131340A * Title not availableJPH06348756A * Title not available* Cited by examinerNon-Patent CitationsReference1"EBT's DynaText: building an SGML-based viewer," The Seybold Report on Publishing Systems, vol. 22 No. 1, Sep. 1992, pp. 6-7.2 *EBT s DynaText: building an SGML based viewer, The Seybold Report on Publishing Systems, vol. 22 No. 1, Sep. 1992, pp. 6 7.3Mark Walter et al., "Status Report on SGML: notes from SGML '93," The Seybold Report on Publishing Systems, vol. 23 No. 9, Jan. 1994, pp. 3-13.4 *Mark Walter et al., Status Report on SGML: notes from SGML 93, The Seybold Report on Publishing Systems, vol. 23 No. 9, Jan. 1994, pp. 3 13.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6014663 *Apr 10, 1998Jan 11, 2000Aurigin Systems, Inc.System, method, and computer program product for comparing text portions by reference to index informationUS6098071 *Jun 7, 1999Aug 1, 2000Hitachi, Ltd.Method and apparatus for structured document difference string extractionUS6263332 *Aug 14, 1998Jul 17, 2001Vignette CorporationSystem and method for query processing of structured documentsUS6438540Jun 19, 2001Aug 20, 2002Vignette CorporationAutomatic query and transformative processUS6526410Jun 27, 2000Feb 25, 2003Hitachi, Ltd.Method and apparatus for structured document difference string extractionUS6539118Aug 27, 1999Mar 25, 2003International Business Machines CorporationSystem and method for evaluating character sets of a message containing a plurality of character setsUS6718519Aug 27, 1999Apr 6, 2004International Business Machines CorporationSystem and method for outputting character sets in best available fontsUS6760887Aug 27, 1999Jul 6, 2004International Business Machines CorporationSystem and method for highlighting of multifont documentsUS6772141Dec 14, 1999Aug 3, 2004Novell, Inc.Method and apparatus for organizing and using indexes utilizing a search decision tableUS6778983Apr 28, 2000Aug 17, 2004International Business Machines CorporationApparatus and method for accessing HTML files using an SQL queryUS6778988 *May 1, 2001Aug 17, 2004R.R. Donnelley & Sons CompanyMethod and apparatus for delivering a web page to a client device based on printed publications and publisher controlled linksUS6813747Aug 27, 1999Nov 2, 2004International Business Machines CorporationSystem and method for output of multipart documentsUS6882995Jul 26, 2002Apr 19, 2005Vignette CorporationAutomatic query and transformative processUS6964013 *May 30, 2000Nov 8, 2005Kabushiki Kaisha ToshibaDocument editing system and method of preparing a tag information management tableUS7028024Jul 20, 2001Apr 11, 2006Vignette CorporationInformation retrieval from a collection of information objects tagged with hierarchical keywordsUS7031002Aug 27, 1999Apr 18, 2006International Business Machines CorporationSystem and method for using character set matching to enhance print qualityUS7039637 *Aug 27, 1999May 2, 2006International Business Machines CorporationSystem and method for evaluating characters in an inputted search string against a character table bank comprising a predetermined number of columns that correspond to a plurality of pre-determined candidate character sets in order to provide enhanced full text searchUS7103532Aug 27, 1999Sep 5, 2006International Business Machines Corp.System and method for evaluating character in a messageUS7111000Jan 6, 2003Sep 19, 2006Microsoft CorporationRetrieval of structured documentsUS7111011 *May 10, 2002Sep 19, 2006Sony CorporationDocument processing apparatus, document processing method, document processing program and recording mediumUS7191114Aug 27, 1999Mar 13, 2007International Business Machines CorporationSystem and method for evaluating character sets to determine a best match encoding a messageUS7237191 *Dec 18, 2001Jun 26, 2007Open Invention Network, LlcMethod and apparatus for generic search interface across document typesUS7315867Jul 20, 2005Jan 1, 2008Sony CorporationDocument processing apparatus, document processing method, document processing program, and recording mediumUS7415669 *Feb 27, 2001Aug 19, 2008Open Invention NetworkMethod and apparatus for viewing electronic commerce-related documentsUS7428538Mar 23, 2006Sep 23, 2008Microsoft CorporationRetrieval of structured documentsUS7603371Dec 17, 2003Oct 13, 2009Vignette CorporationObject based system and method for managing informationUS7613731 *May 28, 2004Nov 3, 2009Quantum Reader, Inc.Method of analysis, abstraction, and delivery of electronic informationUS7627558Sep 8, 2005Dec 1, 2009Vignette Software, LLCInformation retrieval from a collection of information objects tagged with hierarchical keywordsUS7685157 *Jun 18, 2003Mar 23, 2010Nippon Telegraph And Telephone CorporationExtraction of information from structured documentsUS7707139Sep 28, 2001Apr 27, 2010Hitachi, Ltd.Method and apparatus for searching and displaying structured documentUS7805424Apr 12, 2006Sep 28, 2010Microsoft CorporationQuerying nested documents embedded in compound XML documentsUS7949657Dec 11, 2007May 24, 2011Microsoft CorporationDetecting zero-result search queriesUS7984076Dec 28, 2007Jul 19, 2011Sony CorporationDocument processing apparatus, document processing method, document processing program and recording mediumUS8046370Sep 16, 2008Oct 25, 2011Microsoft CorporationRetrieval of structured documentsUS8271561Aug 21, 2009Sep 18, 2012Open Text S.A.Object structure-based system and method for managing informationUS8301642Nov 30, 2009Oct 30, 2012Open Text, S.A.Information retrieval from a collection of information objects tagged with hierarchical keywordsUS8561022Aug 12, 2008Oct 15, 2013Andrew Everett DavidsonMethod and apparatus for viewing electronic commerce-related documentsUS8862636Jun 5, 2008Oct 14, 2014International Business Machines CorporationScalable algorithms for mapping-based XML transformationUS9135226Apr 30, 2012Sep 15, 2015Open Invention Network, LlcMethod and apparatus for declarative updating of self-describing, structured documentsUS9262388Oct 15, 2013Feb 16, 2016Open Invention NetworkMethod and apparatus for viewing electronic commerce-related documentsUS9710457Jan 9, 2012Jul 18, 2017Gregory A. StobbsComputer-implemented patent portfolio analysis method and apparatusUS20020049781 *May 1, 2001Apr 25, 2002Bengtson Michael B.Methods and apparatus for serving a web page to a client device based on printed publications and publisher controlled linksUS20020065814 *Sep 28, 2001May 30, 2002Hitachi, Ltd.Method and apparatus for searching and displaying structured documentUS20020091671 *Nov 20, 2001Jul 11, 2002Andreas ProkophMethod and system for data retrieval in large collections of dataUS20030007397 *May 10, 2002Jan 9, 2003Kenichiro KobayashiDocument processing apparatus, document processing method, document processing program and recording mediumUS20040044963 *Jun 18, 2003Mar 4, 2004Nippon Telegraph And Telephone CorporationExtraction of information from structured documentsUS20040133557 *Jan 6, 2003Jul 8, 2004Ji-Rong WenRetrieval of structured documentsUS20040163041 *Feb 13, 2003Aug 19, 2004Paterra, Inc.Relational database structures for structured documentsUS20040205675 *Jan 11, 2002Oct 14, 2004Thangaraj VeerappanSystem and method for determining a document language and refining the character set encoding based on the document languageUS20060020591 *Sep 8, 2005Jan 26, 2006Kommers Jefferson MInformation retrieval from a collection of information objects tagged with hierarchical keywordsUS20060075331 *Nov 23, 2005Apr 6, 2006Fujitsu LimitedStructured document processing method and apparatus, and storage mediumUS20060095836 *Sep 23, 2005May 4, 2006Kabushiki Kaisha ToshibaDocument editing system and method of preparing a tag information management tableUS20060155690 *Mar 23, 2006Jul 13, 2006Microsoft CorporationRetrieval of structured documentsUS20060161532 *Mar 23, 2006Jul 20, 2006Microsoft CorporationRetrieval of structured documentsUS20060247393 *Jun 30, 2006Nov 2, 2006Nec CorporationFlame retardant epoxy resin composition and semiconductor device using the sameUS20060271634 *May 25, 2005Nov 30, 2006England Laurence EMethod, system, and program for processing a message with dispatchersUS20070244860 *Apr 12, 2006Oct 18, 2007Microsoft CorporationQuerying nested documents embedded in compound XML documentsUS20080235260 *Mar 23, 2007Sep 25, 2008International Business Machines CorporationScalable algorithms for mapping-based xml transformationUS20080256120 *Dec 28, 2007Oct 16, 2008Sony CorporationDocument processing apparatus, document processing method, document processing program and recording mediumUS20080275907 *Jun 5, 2008Nov 6, 2008International Business Machines CorporationScalable algorithms for mapping-based xml transformationUS20080301544 *Aug 12, 2008Dec 4, 2008Open Invention NetworksMethod and Apparatus for Viewing Electronic Commerce-Related DocumentsUS20090012956 *Sep 16, 2008Jan 8, 2009Microsoft CorporationRetrieval of Structured DocumentsUS20090043736 *Aug 8, 2007Feb 12, 2009Wook-Shin HanEfficient tuple extraction from streaming xml dataUS20090043806 *Jun 5, 2008Feb 12, 2009International Business Machines CorporationEfficient tuple extraction from streaming xml dataUS20090150375 *Dec 11, 2007Jun 11, 2009Microsoft CorporationDetecting zero-result search queriesUS20100004986 *Aug 12, 2008Jan 7, 2010Walker Jay SSystems and methods wherein a security deposit facilitates a transaction in which a benefit is applied in exchange for performance of a taskUS20100049774 *Aug 21, 2009Feb 25, 2010Vignette CorporationObject Structure-Based System and Method for Managing InformationUS20100077000 *Nov 30, 2009Mar 25, 2010Kommers Jefferson MInformation retrieval from a collection of information objects tagged with hierarchial keywords* Cited by examinerClassifications U.S. Classification715/202, 715/210, 715/256, 715/201, 707/E17.123, 707/999.002International ClassificationG06F17/22, G06F17/30Cooperative ClassificationG06F17/30911, G06F17/2247, G06F17/2205, Y10S707/99932European ClassificationG06F17/22C, G06F17/22M, G06F17/30X1Legal EventsDateCodeEventDescriptionFeb 22, 1996ASAssignmentOwner name: FUJI XEROX CO., LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:TATENO, MASAKAZU;REEL/FRAME:007886/0898Effective date: 19960216Sep 13, 2001FPAYFee paymentYear of fee payment: 4Dec 16, 2005FPAYFee paymentYear of fee payment: 8Feb 8, 2010REMIMaintenance fee reminder mailedJul 7, 2010LAPSLapse for failure to pay maintenance feesAug 24, 2010FPExpired due to failure to pay maintenance feeEffective date: 20100707RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services