Patent Publication Number: US-5629846-A

Title: Method and system for document translation and extraction

Description:
BACKGROUND OF THE INVENTION 
     The present invention relates generally to electronic textual documents, and more particularly to translating an electronic textual document having a first format into an electronic target document having a second format. 
     Electronic textual documents exist in many different formats ranging from plain ASCII text to proprietary editor viewer formats. In recent years there has been greater interest and importance attached to storing documents in formats which are public or which may be translated into public formats. One particular class of public formats is known as Standard Generalized Markup Language (SGML), which is a standard-based tagging methodology that provides a platform and application independent document while allowing information such as formatting, indexing, and linked information to remain within the document. SGML is accomplished by embedding SGML-compliant codes known as tags to build the document into its final formatted form. These standard-based tagging methodologies are gaining in use, especially in the publishing industry. However, there exists a vast amount of electronic material and paper documents available for scanning and use of optical character recognition which are in non-standard formats that cannot be readily translated into SGML compliant formats. 
     Since the value of a document is dependent upon its accessibility, there is further value added when the document can be displayed in a different environment using different viewers which sometimes require different formats. Thus, there is a need to be able to translate documents from one format or tagging scheme to another. Currently, there are several types of document viewing/editing software available that provide internal or external translators that can go from their own format to an industry standard and formats of others. Essentially, these translators are written in low-level languages such as C or C++, or by using LEX and YACC to construct parsers. LEX is a tool for building lexical analyzers which identify the next token in the character stream being processed. YACC is a tool for creating rule-based parsers which receive the stream of tokens from the lexical analyzer and identify the pattern and ensure legal syntax. Once such a parser has been written to understand a particular format, code may then be written to output the information in the target format. Coding these translators is labor intensive and requires a great deal of time. Therefore, there is a need for an easy to use approach that translates documents without requiring a lot of time and specialized skill to write the translation code. 
     In addition to the translation problem described above, there often exists a need to restructure a document. If the document is in an SGML-compatible format, restructuring may be done by simply editing the DTD (document type definition). However, if the document is not in a standard format, it may be very difficult to restructure the document. Thus, if there was an easy to use translator, then this problem would be able to be overcome by approaching the restructuring as a translation problem. 
     SUMMARY OF THE INVENTION 
     Therefore, it is a primary objective of the present invention to provide a method and system for translating documents from one format into another format which does not require a lot of time and skill to use. 
     Another object of the present invention is to provide a method and system that can quickly restructure an original source document into a target document by using selected examples. 
     In the present invention, a user selects a few portions from a source document which is to be translated. The selected portions contain various constructs and formats. The selected portions are then transformed manually by an editor into the format of a target document. In the present invention, the text does not change, only the tagging or control information is modified. Translation rules are then deduced from the transformed selected portions and their corresponding originals. The translation rules are used for mapping the entire source document to the target document. If the translator is confronted with constructs or formats that are not covered by the translation rules, then the user can supply additional examples to extend the amount of translation rules. The present invention is simple and does not require the time or skill necessary to write code as in the above-mentioned translators. 
     Thus, in accordance with the present invention, there is provided a method for translating an electronic source document having a first format into an electronic target document having a second format. The method comprises selecting portions of constructs and formats from the source document. Then the selected portions are extracted from the source document. The format of the extracted portions are transformed into the second format of the electronic target document. From the original and transformed portions, a set of translation rules are deduced. The translation rule set is applied to the electronic source document and used to translate the source document into the target document. As the translation rule set is applied to the electronic source document, a first draft is produced. 
     Also, in accordance with the present invention, there is provided a system for translating an electronic source document having a first format into an electronic target document having a second format. The system comprises a selecting means for selecting portions from the source document having various constructs and formats. An extraction means extracts selected portions from the source document. A transforming means transforms the format of the extracted portions into the second format of the electronic target document. The transformation can be greatly facilitated by importing the text into a WYSIWYG (What you see is what you get) editor for the target format, but the present invention does not assume any particular process for preparing the selected portions of the document. A deducing means deduces a translation rule set from the original and transformed portions. A first applying means applies the translation rule set to the electronic source document. A first producing means produces a first draft of the electronic target document as the translation rule set is applied to the electronic source document. 
     While the present invention will hereinafter be described in connection with a preferred embodiment and method of use, it will be understood that it is not intended to limit the invention to this embodiment. Instead, it is intended to cover all alternatives, modifications and equivalents as may be included within the spirit and scope of the present invention as defined by the appended claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a system according to the present invention; 
     FIG. 2 is a schematic illustrating the translation of a source document into the format of the target document; 
     FIG. 3 is an example of a translation rule set; and 
     FIG. 4 is a flow chart describing the operation of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PRESENT INVENTION 
     FIG. 1 shows a block diagram of a system 10 according to the present invention. The system includes a CPU/controller 12 which may, for example, be a general purpose computer such as a personal computer, a workstation, or a micro- or minicomputer. The computer receives an electronic source document 14 which may be a computer file or other type of electronically stored document with all of the original tagging/formatting information still in tact. The input document may also be the result of scanning a source document from hard copy (i.e., paper) and using optical character recognition and other techniques to capture, with the text, as much formatting information as possible. The electronic source document 14 may be generated from a commercially available word processing package such as Microsoft Word™, Framemaker™, WordPerfect™, or the like. 
     An interactive knowledge extractor 16 such as a mouse and keyboard, selects various portions from the source document and extracts the selected portions therefrom. The extracted portions are then transformed into the format of a target document 24 by a transformer 20 such as an editor. The various constructs and formats (tags) from the selected portions are then identified by a construct tagger 18. In order to deduce a translation rule set, the CPU/Controller needs the tags from the extracted portions and the new tags from the target portions. The text then serves as a basis or reference to allow deduction of what are tags in both the old and new representations. Once both types of tags are identified by the construct tagger, translation rules may be postulated. The CPU/Controller 12 then deduces the translation rule set that is used to translate the source document into the target document. The translation rule set is stored in a translation rule base 22. After the translation rule set has been deduced, it is then applied by the CPU/Controller to the electronic source document 14. As the translation rule set is applied, the text and format in the source document are translated into the format of the target document (i.e., another, commercially available word processing package) resulting in a first draft. An error/warning log generator 25 identifies portions of text in the source document that were unable to be translated by the translation rule set. The translation rule set is then modified into a new translation rule set by selecting additional examples or portions from the source document and applying the technique described above. Then the new translation rule set is applied to the electronic source document. These steps continue until the source document has been completely translated into the target document or until the user is satisfied with the translation. 
     FIG. 2 is a schematic illustrating the translation of the source document 14 into the format and constructs of the target document 24. Within the source document 14 are portions of text 26 labeled A, B, C, D, etc., having various constructs and formats. Note that the portions could be pages of text or classes of documents and is not limited to paragraphs as shown in FIG. 2. The interactive knowledge extractor 16 selects various portions (e.g., A, B, C, D) from the source document and extracts the selected portions therefrom. The text and the original tagging in the selected portions are extracted. The extracted portions are then transformed into the format of the target document 24 by the transformer 20. The construct tagger 18 identifies the tags extracted from the source document and the new tags formed from the transformation. In FIG. 2, portion A is extracted and transformed into the format of the target document and shown as portion A&#39;. Similar extractions and transformations are made on the portions B, C, and D, resulting in corresponding portions B&#39;, C&#39;, and D&#39;, respectively. 
     After transforming several portions 26, the translation rule set is then deduced from these portions and the transformed portions 28. The translation rule set is deduced by using the principles of case-base reasoning. In particular, the translation rule set is deduced by examining the portions of text (i.e., A, B, C, D, etc.) and the corresponding transformed portions (i.e., A&#39;, B&#39;, C&#39;, D&#39;, etc.). By examining enough cases (i.e., original selected portions and corresponding transformed portions), rules can be correlated on how to translate the source document 14 into the format of the target document 24. An example of a translation rule set 30 for portions A, B, C, and D is shown in FIG. 3. In FIG. 3, a portion containing the following information \SubHA\Text\end, translates into !HDR1!Text&lt;n1&gt;. Thus, rules can be deduced to indicate that the format \SubHA\ in the source document will translate into the format !HDR1! in the target document and the format \end\ will translate into the format &lt;n1&gt;. Other rules can be derived from other portions and placed in the translation rule set. After the translation rule set has been deduced, it is applied to the electronic source document 14. The example in FIG. 3 is an illustration of how the translation rules are deduced. Although the example is relatively simple in scope, it is within the realm of the present invention to cover much more complicated cases. As the translation rule set 30 is applied, the text and format in the source document are translated into the format of the target document, resulting in a draft. 
     An added feature of the present invention, is the error/warning log generator 25 which identifies portions of the source document that were unable to be translated by the translation rule set. This feature depends upon the translator having a model of the source tagging scheme allowing it to identify characters which are likely to be tags in the source document, but for which it has no translation rules. However, this model need not be difficult. In the example provided in FIG. 3, the model might be that characters between two back slashes are tags. In the present invention, the error/warning log generator 25 has the capacity to provide assumptions of problems in the translation rule set that are preventing the translation of a certain portion of the source document. Alternatively, the error/warning log generator can notify the user of missing portions or rules from the translation rule set 30 or of conflicting examples which require additional information to allow discrimination and avoid conflicting rules. Upon receiving the error/warning log, the user interactively enters portions of text and format from the source document using the editor to transform the portions of the source document into the corresponding format of the target document. After enough portions of the source document have been selected, extracted, and transformed, the CPU/Controller 12 modifies the translation rule set into a new translation rule set. After the new translation rule set has been formulated, it is then applied to the electronic source document. As the new translation rule set is applied, the text and format in the source document are again translated into the format of the target document, resulting in a second draft. 
     If the second draft is not a complete translation of the source document, then the error/warning log generator notifies the user of other portions of text that were identified as being untranslatable. The user then selects more examples from the source document and the editor transforms them into the format of the target document. After enough portions of the source document have been selected, extracted, and transformed, the translation rule set is modified into another translation rule set. After the newest translation rule set has been formulated, it is then applied to the electronic source document. As the new translation rule set is applied, the text and format in the source document are again translated into the format of the target document, resulting in a third draft. The above steps continue until the source document has been completely translated into the target document or until the user is satisfied with the translation. 
     FIG. 4 is a flow chart describing the operation of the present invention. At 32, the computer receives the electronic source document 14. The interactive knowledge extractor selects various portions from the source document and extracts the selected portions at 34. The extracted portions are then transformed into the format of the target document at 36. The various constructs and formats from the source document and the transformed portions from the target document are identified at 38. In addition, the translation rule set is then deduced at 38. The translation rule set is then stored at 40. The translation rule set is then applied to the electronic source document at 42. If the translation is not complete at 44, then portions of the source document that were unable to be translated by the translation rule set are identified at 46. The translation rule set is then modified into a new translation rule set at 48. After the new translation rule set has been formulated, it is then applied again to the electronic source document at 42. The above steps continue until the source document has been completely translated into the target document or until the user is satisfied with the translation. 
     It is therefore apparent that there has been provided in accordance with the present invention, a method and system for translating a source document into the format of a target document that fully satisfy the aims, advantages and objectives hereinbefore set forth. The invention has been described with reference to several embodiments, however, it will be appreciated that variations and modifications can be effected by a person of ordinary skill in the art without departing from the scope of the invention.