DE60005293T2 - Method and device for processing electronic documents - Google Patents

Description

relative Registrations

The present application refers to the European Patent application number 99 108 354.4, filed April 28, 1999 was submitted.

Territory of invention

The present invention relates to a method and an apparatus for processing electronic Documents, especially for extracting certain elements of electronic text documents.

description related technology

Electronic data processing (EDP) is becoming increasingly important these days to deal with the huge amount coping with documents from institutions like big companies, Administrative offices or the like must be processed. It is common today that the documents are in electronic form, for example the result of a scanning process and then an optical one Character recognition process (OCR) are about written documents convert to an electronic form.

If a large amount of such documents needs to be edited, for example, to get specific data are contained in an orderly manner such as in a database, then it is desirable that certain Parts of information (elements of the document), such as the date of birth, place of birth, or the like, of such electronic Documents can be extracted automatically. If for example, a company automatically processes a large volume of resumes would like to, then could it desirable be this data automatically from the electronic Extract documents. Also for other purposes such as Extracting accounting information for ERP systems can extract data from text documents desirable his. There are many applications imaginable for which it desirable that can be a certain text information or a text element or certain numbers or number information from a text document can be extracted. The text document can be any document, for example, that contains certain data of interest to be extracted, as it relates to a specific category of information that is extracted should be included.

Conventional extraction systems, the specific specific data of electronic text documents can extract work in such a way that they find a certain fixed position in a document, which is assumed to locate the desired data there are.

Such types of search algorithms don't work very well because they're heavily dependent on documents which have a certain predefined format, however the desired Data is not always in the same place.

US 5,191,525 describes a system for automatic processing of paper documents based on automatic extraction and processing of data are contained in these documents. For this purpose, the documents first converted to an electronic format. The system can edit different types of documents, and first the Type of document to be identified. There are several for this purpose Geographical identification areas provided that a specific Contain identification word or words based on which the identification of the document type is carried out. After the guy is identified was based on knowledge of the composition of this Type of document cutting out graphic data areas, extracted from the graphic image. These areas are sent to the recognition subsystem and according to the already well known Know about the type of document they contain a certain type of data, then for the further processing of this document can be used. The system hangs thus from a priori knowledge of the composition of the individual documents, especially via the Location where a certain type of data within a certain document type can be expected.

It is therefore an object of the present invention the conventional Process for extracting certain parts of data from text documents too improve.

Summary the invention

In one aspect, it creates The present invention a method and an apparatus for producing a layout document that represents an element of the text document and as input for one Classifying device can be used. Because of the special Type of layout document that is in accordance with this aspect of the present invention is generated, the classifying device is able to improved classification of a text element by the layout document represents will perform. This will improve extraction of certain text elements of text documents possible.

According to one aspect of the present invention, a layout document is based on elements of an electronic text document testifies, where the layout contains a representation of elements of the document together with representations of their corresponding position. By creating such a layout document that can be used as input to a classifier such as a neural network, it becomes possible to evaluate the elements of a document along with their geometric context elements (their neighborhood / environment) and not just the format or to take advantage of the content of an element itself, but also other information to evaluate whether the element belongs to a certain category or not. By taking into account not only an element or its format itself, but instead also its surrounding area or the elements contained in the surrounding area, a classification device receives further information as to whether or not a text element belongs to a certain category. These further indications, which are given by the surrounding area and the text elements contained therein, can be recognized or learned by a classification device, for example a neural network, and a trained neural network can thereby achieve an improved classification and thus an improved extraction of elements from text documents ,

According to another aspect of present invention, layouts for a variety of elements, that belong to a certain category, and those that are created Layouts are then used to train the classifier, to recognize elements of this category. The classification device is preferably a neural network through the layouts that are used for a variety created by elements, trained, and by input into the device during the Training phase, whether the elements for which the layouts were created belong to a certain category or not. So trained neural network or a classification device can further for classification are used by unknown text elements and to carry out a Extract elements from unknown texts.

According to another aspect of The present invention becomes a classifier that trains was used to evaluate whether an unknown item too belongs to a certain category or not, based on a layout document that is for this Element was generated to thereby create elements from a document extract that belong to a certain category.

According to another aspect of In the present invention, candidates are identified who according to a Search criteria possibly the category to which the extracted data should belong, belong. Preferably, a search criterion can be a format of an element, a word search criterion, a fault tolerant word search criterion or one Combination of such criteria. For each of these candidates can then create a layout document based on the candidate himself, his position in the electronic document and based on other elements of the electronic document and its position in the document. Those elements are preferred when the layout document is generated considered within one or more predefined ones Areas, preferably near or in the vicinity of the Candidates.

Based on such a layout document it is then judged whether the candidate actually did the job Category belongs or not.

According to another preferred embodiment The present invention makes the decision of whether a candidate to the desired category heard, by using a classifier is preferably a neural network. The neural network can be used by of layout documents have been trained by candidates and also by entering Information in the neural network whether these candidates to the desired Belong to category or Not.

According to another preferred embodiment will be the decision of whether a candidate should be the one you want Category belongs or not, using a method or device like in European Patent application with the application number 99 108 354.4 described that on April 28, 1999 and its priority for the present Application was claimed and which are hereby incorporated by reference in registration will begin.

Short description of the drawings

1 shows a computer system that can be used to implement an embodiment according to the present invention;

2 illustrates an example of a text document from which elements are to be extracted;

3 shows an example of a working document created from a text document;

4 shows an example of a user interface for the definition of the layout area;

5a shows an example of a layout area;

5b shows an example of a layout document;

6 shows an example of a coding scheme for coding a candidate box;

7 shows an example of the coding of element positions of the layout document;

8th shows an example of a learning phase of a classifying device;

9 shows an example of an extraction phase of a classifying device.

detailed Description of the preferred embodiments

The present invention can be accomplished by a computer system as in 1 shown to be implemented.

1 shows schematically the structure of a computer system that can be used in connection with the preferred embodiment of the invention. The computer 100 contains a CPU 110 , a memory 120 ; and an I / O unit 130 , The computer 100 is able to run programs by computer commands through the CPU 110 run the CPU from memory 120 fetched and in a storage facility 150 such as a CD-ROM or a floppy disk. The I / O unit 120 is with a keyboard 160 and a mouse 170 connected to enable a user to input data into the computer, and it is also connected to a printer 180 connected to output documents as printouts. The computer 100 is also with a display unit 140 connected like a monitor. It is further understood that the computer configuration described in 1 is only an exemplary configuration and other computer configurations, such as parallel processing computers, neural network computers with separate hardware, or any other computer systems capable of performing the method explained below, can be used in connection with the present invention.

The present invention will hereinafter be used in connection with extracting a date of birth from a curriculum vitae as in 2 shown described. It will be immediately understood by those skilled in the art that the description of the present invention in connection with the extraction of a date of birth of a resume is for illustrative purposes only, and the same method and apparatus as described below for any other text documents, some of which are pieces of information are to be extracted, such as an account number of an account sheet, the prices of invoices, for extracting values that can be used in a factory of corresponding sheets, and the like.

The resume is in the computer on a disk Stored in electronic form, it can be the result of an editing process using a word processor, or that Electronic document can be the result of a scanning process and a subsequent one optical character recognition. Instead of a resume any other document of which an element has a specific meaning or should be extracted falling into a certain category, be used.

First, the electronic Document parses to the individual documents that make it up exists to get. "Element" means any here Sequence of characters separated from other elements by a delimiter such as a space, a tab, an underscore, or any other data element that interprets as a delimiter can be separated. The easiest way to split Text in individual elements is by identifying those parts of the text as elements separated by a space, dependent can from the purpose of analysis however, other criteria may also be considered, such as the underscore, a hyphen, a new paragraph, or other elements of the electronic document viewed like this can be that they separate one element from the other. Another criterion that can be considered if individual items could be identified the geometric distance between the individual text characters his. For example a threshold must be defined beyond which there is a distance between two characters is interpreted so that the two characters are different Elements are. In the present example we assume that a Element of any single character or a sequence of characters can be that of other "elements" by a space are separated.

In the present example of a text document as in 2 the first two elements "curriculum" and "vitae" would be shown, other elements would be "Tel:", "Fax:", etc. as is immediately understood by the person skilled in the art. These elements are identified, for example, by a parser that simply looks for spaces.

Aside from getting the items themselves will also get their corresponding position in the document, for example, by calculating the X and Y coordinates at which the element is arranged in the document. The position later becomes Generation of the layout document used.

After the individual elements of the electronic text document have been identified, these elements are stored in a so-called "working document". In the working document, each item that has been identified is stored along with information about its location in the electronic document. For example, the element "curriculum" can be stored along with its X and Y coordinates that identify its position in the electronic document. The working document is a convenient tool for storing all elements that have been identified, together with their corresponding position, so that reference can be made to the working document for the generation of the layout document, which will be explained in detail later. An example of a working document that consists of a Text document generated is in 3 shown. The tags Tagt, Tagt, etc. contain the position information of the corresponding elements. This information can be represented in any form, for example by directly storing the X and Y coordinates of the elements in the tags. The elements in 3 can be, for example, the individual words identified in a text document or any other character sequences recognized as elements by the previously explained method, and the tags then contain information about the position of these elements, such as where they are with respect to their X - and Y coordinates are localized. The tags may also contain indications of the font style of the elements, the fonts, whether they are underlined or not, or any similar information. For example, for a bold element in the corresponding tag, the character sequence "bf 'may be included, which represents that the element is printed in bold faced characters, another character sequence may represent that the element is underlined, or the like.

The position of an element can for example, the center of gravity of an element that was calculated based on its individual pixel values, or it can represent any other geometric information, that represent the location of the element. For example a frame (box) is constructed surrounding the element, and the average between the maximum and minimum X coordinates the box can be made from X coordinate for the positions are used and the average of the maximum and the minimum of the Y position of the box can be used as the Y coordinate of the Elements are used when its position in the text is indicated by a corresponding day is represented in the working document.

The working document contains one List of identified elements along with their tags current position and possibly also include other information as previously mentioned, such as information about the fonts of the elements, their style, whether they are underlined or not, etc.

In this way the working document is created and contains a list of the individual elements of the electronic text document along with their corresponding position and possibly other information. Even non-textual elements can be included in the working document, such as horizontal or vertical lines or grids in the electronic document are contained, which are then also in the working document in a Shape, its position and appearance (horizontal, vertical, line, grid, or similar) according to one Represent coding scheme. For example, a horizontal line in a working document are represented by the character sequence AAAA, a vertical Line can be represented by the character sequence BBBB, each then is followed by a day indicating the position of the line. The The working document generated in this way can then be used to identify candidate elements that may be can be the element to be extracted. For this purpose the working document (or possibly also the "source document" based on which the Working document was created) parsed to those elements too identify a specific search criteria such as meet a format criterion. In this step of extracting a candidate, everyone will be Elements analyzed for possible Candidates for the ones you want to find extracting elements. Preferably not only individual elements searched, but also combinations of elements, so the procedure with spaces between the individual Elements. If, for example, after a bank account number what is believed to have eight digits, so a search can be performed for a number that has eight digits has that are either represented as "99999999" or as "999 999 99" or as "9 9 9 9 9 9 9 9", or in any one other combination. The search for such a bank account number can therefore be carried out, for example, by following a Number with eight digits is searched. Depending on the information content that the element to be extracted can have a different format can be used as search criteria. Possible search criteria are searches according to regular Express (such as a format search where a specific Format such as a string, a sequence of numbers that possibly also contains a certain total number of digits, is searched), or the like. Another search criteria could be be that a search for a simple predefined element carried out is done by performing a string comparison. For example a search for the word "birth" is carried out, and any element that met this search criteria would then appear as a candidate.

Another possible search criterion could be to carry out a so-called determination search, which means that an element is sought which is arranged at a specific position (left / right / up / down) with respect to a candidate who was found by another search criterion. For example, if a search criterion was a search for the word "birth", then a search could be performed for an element located to the right of the "birth" element, and in this case the resulting candidate would be the element to the right of the element "birth" is arranged. In the example of 2 the element "May 5, 1960" would appear as a candidate with such a search for a destination.

Another search criterion could be be to perform a search for all items, including those in a database available.

The search for candidates is preferably fault tolerant in such a way that prefixes / suffixes can be ignored in order to ignore typical errors in optical character recognition, or for elements such as "," and "." to ignore. For example, in the case of 2 a word search for the word "birth" can be carried out using such a fault-tolerant search, for example using a wildcard. A search would then be performed for the "birth *" element so that the "birth:" element would appear as a candidate. With the determination search, the actual date, which is arranged to the right of the "birth" element, could then be determined as a candidate.

Depending on the way in which Candidate search performed more or fewer candidates for the elements to be extracted are identified.

Other search methods could, for example include a trigram search, which means combinations of three characters are searched. This is also a method of performing fault tolerant Search. For example, if a typo appears in a candidate, then would nevertheless get a trigram search such a candidate because several character sequences contained in the candidate would be recognized as correct trigrams. Another fault-tolerant search method would be the Levenshtein distance to use, which is a representation of the Is key presses that are needed on a keyboard to complete a character sequence to convert to another. Based on the Levenshtein distance could also a fault-tolerant search can be carried out.

The candidate search is preferably carried out by Search the working document for elements that match the search criteria fulfill, carried out. The analysis of the document in elements that have already been carried out can be used. In principle, however, can also search for candidates be carried out directly on the text document.

The search is used to find candidate elements get that possibly contain the information that is being searched for. It is instant recognizable that dependent of the information that is searched for according to the search criteria need to be adjusted. If a bank account number is searched, then preferably one Format criterion used, which is a possibly known number format the account number used. On the other hand, if a place of birth is sought then the search for strings is more promising than that Search for numbers. The adaptation of the search criteria (format search, Word search, database search, destination search, or a combination of that) to the particular piece Information that is sought can depend on the person skilled in the art the circumstances chosen accordingly become.

If the candidates found later in a Training procedure for a classifier should be used, as in Detail later it is preferred if they somehow do that Users are displayed or initiated and if the user is able to confirm whether the candidates found match the search criteria or not. This enables the classifying device to be explained later be trained. The display of the candidates can, for example searched by "highlighting" them in the Text document happen to then give the user a confirmation or Allow candidates to be rejected by clicking the mouse. The format search or fault-tolerant element search provide candidates for too extracting elements. The result of the candidate search is already complete good in terms of correctness because it is based on inherent properties of the elements, that are searched for, such as their format or their actual Information content. However, the candidates can then continue to be evaluated be regarding of whether they belong to a particular category by adding other items than the candidates considered themselves as described below.

For each of the candidates is then created a so-called layout document, not just a representation of the candidate and his position in the electronic document contains but also of other elements that surround the candidate element, as well as their respective position. The layout document is therefore an electronic representation of the candidate and his position in the electronic document itself, as well as other elements in the electronic document and their corresponding position. A layout document, that for a particular candidate is generated for a particular area that surrounds this candidate. This area (or equivalent Majority of areas) can either be predefined or from User defined.

An example of the definition of such a surrounding area by a user interface is in 4 shown. 4 shows how a total of four boxes surrounding the candidate can be defined by a user. A first box surrounds the candidate in all directions, a second box represents the neighborhood to the left of the candidate, a third box represents the neighborhood to the right of the candidate, and a fourth box represents the neighborhood above the candidate. Optionally, a fifth box, which represents the neighborhood among the candidate, be used. The user can enter the dimension of the size of the boxes, for example, by entering values that represent their size in dots per inch or in another unit, such as pixels, millimeters, or the like. In the example of 4 The size of the boxes can be dimensioned by the user, but they can also be predefined. The area for generating the layout document can be defined by the user depending on the specific category of an element that a user wishes to extract.

To create the layout document are all elements related to their position in the electronic document in the boxes that the area of the layout document define, taken into account for the generation of the layout document. For this Purpose can be referred to the working document in which all elements are saved together with their corresponding positions.

In the following it is assumed that the process of obtaining a candidate element is element May 5, 1960 of the document 2 as a candidate. For example, this can be the result of a format search that searches for a combination of three individual elements in series, where the three elements should contain two integers (representing day and year) and another number or word that represents the month. The search result would then be the series of the three elements. Other search criteria could also be presented that lead to the result May 5, 1960 as a candidate, such as a destination search that searches for three elements next to the element "birth", which would also result in May 5, 1960 as a candidate. Any other regular expression searches could also result in a candidate such as May 5, 1960, such as searching for a regular expression that contains three elements, two of the three elements being numbers and the third being a word or number, one being the numbers range from 1 to 31. It is immediately apparent to those skilled in the art that many definitions of search criteria are possible that lead to candidates for a piece of information that is supposed to be a "date".

After one or more candidates go through the above search procedure obtained as described is then for each the candidate a layout document that creates a representation of the candidate and his surrounding area. For generation of the layout document first the elements that lie within the area that is to be created of the layout document is used, identified and then based on these elements created the layout document. It contains a representation the candidate and the elements that are within this area, along with the corresponding positions of these elements.

5a shows an example of a layout area in the case of the text document 2 , The candidate here is "May 5, 1960", and the dashed line in 5a defines the layout area surrounding the candidate. All elements of the document 2 , or off 5a that fall within this area are used to create the layout document. This in 5a The area shown can be the result of a user definition using an interface like that 4 or it can also be predefined.

An example of the layout document created for the candidate "May 5, 1960" and the corresponding layout area as in the example from the 5a is shown in 5b shown. The first line of the layout document corresponds to the element "May 5, 1960" itself. It is represented in the layout document by the character sequence "DDMMYY", since according to the particular implementation of the present exemplary embodiment it is recognized that its format is a "date" equivalent. However, it is not necessary, but only a preferred option when generating the layout document, that a recognizable element, of which the format is recognizable, is replaced in the layout document by a corresponding representation of this format, as here by DDMMYY as representation of the format "date". The character sequence to the right of the "DDMMYY" sequence represents the position of this element in the electronic document, as will be explained in more detail later.

The first line of the layout document in 5b therefore corresponds to the candidate element "May 5, 1960". The position of the candidate in the electronic document 2 and its size is also represented by the character sequence "MXMYWLHM", as will become clearer from the explanation below.

To explain how the position of the candidate element in the electronic document in the layout document is represented by the character sequence "MXMYWLHM", is given on 6 Referred. 6 shows a so-called candidate box, ie the bounding rectangle of the candidate element. Depending on the size of the candidate element (eg depending on the font) the size of the candidate box can also vary and can be in the layout document using the coding scheme for the box size as illustrated schematically in the right part of 6 be represented. Based on this coding scheme, the box size is encoded as "WLHM", which means that the candidate box has a large width "long width" (WL), and a medium height "medium height" (HM), as from 6 is recognizable. This coding sequence then executes the last four characters WLHM in the first line of the layout document 5b , It is immediately understood that which actual values are represented by which coding sequence, in other words which values as "small" and which are encoded as "large" depends on the particular implementation and is only a matter of choice for the person skilled in the art.

Therefore, as from the first line of the layout document 5b recognizable, not only the position of the candidate box (which represents the positions of the candidate himself) in the document, as will be explained later, but also the size of the candidate box (representing the size of the candidate). The representation of the size of the candidate box by a corresponding coding sequence is shown schematically in the lower part on the right side of the 6 illustrated. A candidate box that has a small candidate width in the X direction is encoded as "WS" (for "width small", a medium-sized candidate box is encoded as "WM" (for "width medium", medium width) , a candidate box with a large dimension in the X direction is coded as "WL" (for "width long", large width), and an extra large candidate box with an extra large size in the X direction is coded as "WX" (for " width extra long ", extra large width). Similarly, the question of which values are assigned to which coding sequences is a matter of choice for the person skilled in the art.

Similar to the width, the height of the candidate box is encoded by one of the sequences "NS", "HM", "HL", or by "HX". In the event of 5b with the candidate May 5, 1960, the candidate box is encoded as "WLHM", which means that it has a large dimension in the X direction and a medium dimension in the Y direction.

The position of the candidate box in the X and Y directions is encoded as illustrated schematically in the left part of the 6 , For this purpose, certain areas of the document are used 2 assigned to certain coding sequences, as in 6 shown in the left part. Depending on the area in which the candidate box is located, the X and Y position of the candidate box is encoded either as "LL", "MX", "RR" (for the X position) and as "TT", " MY ", or" BB "(for the Y position).

In the present case of 5a for the May 5, 1960 candidate box, the candidate box is medium in location in the X direction, which means that it is not very far to the right in the document and not very far to the left in the document, but rather in the middle of the document in terms of its X position. Such localization is encoded by the character sequence "MX", as from the left part of 6 is recognizable. The Y position of the candidate box is encoded by the sequence "MY", since it is comparatively in the middle of the document with respect to its Y position. From this, the position coding "MXMY" as shown in the first line of the layout document can be obtained for the candidate box. Combining the representation of the candidate's format representation, the position of the candidate box, and the size of the candidate box results in the character sequence in the first line of 5b is shown.

It is understood that the coding is made 6 is only exemplary for the candidate box and other codes, other assignments between position and code and other splits of the document into corresponding areas can be used just as well. The granularity of the size and position of the candidate box can be finer or coarser than in 6 be, depending on the particular implementation, as easily understood by the skilled person.

The coding sequences are very similar, that were used here completely arbitrary, here "LL" simply means "far left", "MX" means "pretty much in the middle in X direction", and "RR" means "far right in the document in the X direction ". Similar ones Wise means "TT" at the very top, "MY" means "pretty much in the middle", and "BB" means "at the very bottom of the document in terms of Y direction ". Others Coding sequences can however, are used as well as recognized by those skilled in the art. Also can instead of capital letters DDMMYY other character sequences are used to identify the recognized To represent the format of a "date".

After the candidate box has been encoded as explained above, the other elements appearing in the area of the layout document as referenced to 5a explained, then also encoded and integrated into the layout document.

This in 5b The layout document shown was generated based on an area that is in 5a is shown by the dashed line. As previously explained, the surrounding area can also be set to a smaller area differently, depending on the preferences of the user and the computing load that can be processed by the computer used, and of course it can also be set larger. Therefore, the layout used here is meant to be an example, and other area definitions can be used as well. Of course, the larger the area used, the more information is contained in the layout document generated from that area, and therefore it is possible that with an enlarged area, the accuracy of further evaluation of the layout document is increased. However, this may depend on the particular implementation and purpose, and good results can also be achieved with small layout areas.

The second line of the layout document 5b is a representation of fax number 07029 8125, which is in 5a is shown and falls within the layout area. Since, according to the particular implementation of the present exemplary embodiment, it is recognized that the two elements 07029 and 8125, which fall within the layout area, consist of integers, they are represented in the layout document by a coding sequence, that of the representation tation of integers, namely capital letters IIQQ.

The second and third lines of the layout document in 5d each represent the area code 07029 and the number 8125. The coding sequence IIQQ, which represents an integer, is then each followed by a coding sequence, which specifies the relative position of the integer in the text document 2 regarding the candidate element.

Any coding scheme can be used to encode the relative position, the particular one used herein is shown schematically in FIG 7 explained. For the purpose of coding discrete areas of distances that correspond to relative positions in the X and Y directions, corresponding coding sequences are assigned, such as “NR” for near, “FF” for far (far), “HEE” for at the same position in the horizontal direction, "VFF" for arranged at the same position in the vertical direction, etc. The special coding scheme is in 7 illustrated, but it is to be understood that this is only an example and can be easily modified. For example, the coding sequences can be different, the division into certain areas can be different, the number ranges can be different, etc.

Out 7 combined with 5b it is understood that the second line of the layout document 5b is based on the fact that area code 07029 is left near (LNR) and above near (ANR) the candidate box, resulting in a position coding sequence LNRANR as in the second line of 5b shown and appended to the integer code IIQQ.

Since the number 8125 is horizontally the same but close to the candidate, this leads to the third line in 5b , which is IIQQHEEANR.

The remaining three elements "date", "of 'and" birth: "that fall within the layout area are made in the last three lines of the layout document 5b together with their corresponding position coding sequences, which are immediately associated with 7 be understood. All elements are vertically the same as the candidate (VEE) but at different horizontal distances from the candidate.

It is immediately understood that instead the relative position coding also absolute positions of the elements within the layout area for the generation of the layout document can be used.

It is also possible that when the layout document is created, other such elements for which the Format is recognizable, not just for example as if the item has the format of a "date" in the layout document be encoded by an appropriate coding sequence. During this here only for the date on the first line and the integers on the second and third line of the layout document was shown, such Replacement also for other recognizable elements such as postcodes (ZIP codes) (could can be recognized by a database query) and by a specific one Character sequence like ZZZ or similar be represented carried out become. The corresponding recognition can either be based on format recognition or a database query (in which, for example, all postcodes are saved).

As explained above, a layout document that generates information about the candidate himself, his position in the document and further information about others Contains elements of the document and their position in the document. The Position information is represented in the present example by replacing coordinate values with character sequences that a position according to a represent certain coding scheme that is used to identify places or areas in which the electronic element for coding purposes has been divided and assigned corresponding character codes were to define. Similar can number codes equally good for coding the position of the elements of the electronic Document can be used. Any coding scheme that the position and / or the format of the elements represents can be used for generation of the layout document. The layout document can also more information about non-textual elements of the document to be analyzed such as lines or grids in the document. The information can also be easily obtained through a geometric analysis of the document, and then the lines or grids, that exist in a document in the layout document Corresponding coding sequences are encoded, preferably also through representation their corresponding position, possibly also their style and other information.

Preferably, the coding scheme contains that for Creation of the layout document is used, a position coding that is based on that corresponding to discrete areas of location information Position codes as previously explained are assigned. Further, style information or Format information that can be recognized, such as the format or the Style of elements, also in the layout document by appropriate Coding sequences represented. However, it is possible just some of these elements of a coding scheme for generation of a layout document.

The position specified in the layout document can be a representation of the geometric position based on coordinate values, such as the X and Y coordinate values that were previously explained. However, it is also possible that the position information for an element in the lay out document represents the relative position between the candidate and this element, such as the number of elements that appear between this element and the candidate. This also makes it possible to encode the relative position between the candidate and other elements in the layout area, by the distance between them, by the number of words that appear between them. Such an encoding scheme could be useful, for example, when the text document to be processed does not actually have much of a layout, such as an email message. Alternatively, however, a virtual layout can be calculated for an email and used for further processing instead of the relative position of the elements as previously explained.

The more information in the layout document about the Candidates and their surrounding elements are included, the more accurate can the layout document and the subsequent processing result his. However, the more detailed the layout document, the more processing power is necessary, around the layout document generate and process it to make a decision get. Therefore can be dependent of the desired Accuracy of the decision-making procedure of the user or a programmer the area for creating the layout document and the area for creating it of the information used in the layout document.

The process of obtaining candidates and subsequently creating a layout document for the candidate was explained above. If, for example, it is now desired that a certain piece of information, namely the date of birth, be taken from the document 2 extracted, then a candidate search is performed on the document to obtain candidates for a date. In case of 2 a search for a regular expression or a format search is carried out as previously explained and would deliver two candidates, which could be the date of birth according to the search criterion used, namely May 5, 1960 and May 17, 1979. A layout document is then created for both candidates as previously explained, and this layout document is input to a classifier that has been trained to recognize the layout documents from actual birth dates as opposed to layout documents that are dates but not birth dates. Such recognition is possible because the layout document created from a date of birth contains further information that makes it possible to recognize it as layout documents that originate from birth dates instead of other dates. For example, it is common for the word "birth" to appear in the vicinity of the date of birth, and if there is a layout document that contains this term, this is a further indication that this layout document generates from a date of birth has been. Similarly, other elements that appear in the vicinity of the date of birth can also be interpreted as a reference, such as the term "place" or the term "of" as in the example 5b , However, if, for example, several birth dates are arranged in the column of a table, the head of the column containing the term "birth", then by coding the position of the term "birth" as previously explained, this can be used by a classifier as an indication that the dates in this column are actually dates of birth. In general, the surrounding area of the vicinity of a candidate for which a layout document has been created can be used as an indication of the actual information content of such a candidate by a classifier. By taking into account the indications given by such a surrounding area or neighborhood, a set of candidates that has been extracted from a document according to a search criterion can be further evaluated as to whether these candidates actually contain the information sought.

Of course, the layout document also directly for all elements of a text document can be generated, and then each element is evaluated based on the layout document generated in this way, whether it is to a certain desired Category belongs or not. The use of a candidate search was previously reduced however, the computing cost that would arise if a layout document for each Element of the text document would have to be generated.

The extraction process and the training process using a classifier described in detail.

After the layout document has been created, it can be used to train a neural network or any other other computerized device that can decide whether a certain document belongs to a certain category or a class or not. For This is the purpose of the candidate's layout documents in the neural Network or other decision device (classifying device) entered, together with the information whether the layout document corresponds to a correct candidate or not, which means whether the candidate the desired Has information content or not.

Training of such a neural network is shown schematically in 8th shown.

An electronic document is analyzed as explained above to obtain elements of a text document and their corresponding positions. A text-based document, a working document, is then preferably generated. Filtering is then carried out in order to obtain a set of candidates who may have a be agreed category could match. The set obtained is preferably corrected, either based on manual input by the user or automatically, for example by checking whether the candidate received has a probability of being correct beyond a certain threshold value. For manual correction in the training phase, the candidates can be highlighted in the document and the user can then confirm for some or all of them whether they are correct candidates or not. The aforementioned manual or automatic selection of correct results then leads to a set of correct results and a set of incorrect results. Layout documents are then generated for each of the elements of the set of correct results and for each of the elements of the set of incorrect results. Thereafter, the layout documents created for the set of incorrect results and the layout documents generated for the set of correct results are used to train the neural network. If no candidate is recognized, the user can also select a candidate himself, highlight him (for example with the mouse) and then use it as a training input.

An extraction process, it uses a network that is as in 8th shown is trained in 9 shown. A set of candidates is similar to that in 8th received, a layout document is created for each of them as previously explained. The layouts are then used as inputs for the trained neural network, which then decides whether the candidates belong to the desired category or not.

An output of the network can be found in the correctly extracted candidate or, for example also in a weighting that indicates the likelihood of correctness for each Candidate weighted. The extracted candidates can also be used directly imports or exports to another electronic document like a database, an MS Excel file, a table, a word document or any other document that is for another electronic Processing or similar suitable is.

The extraction process that identifies the Includes candidates and the creation of the layout document as described in detail above. For everyone found The corresponding generated layout document then becomes a candidate into a classifying device or a decision device entered, which is not necessarily, although preferably, a neural network, and then a decision is made for each candidate hit whether it belongs to the correct category or not.

A particularly suitable device to classify the generated layout document according to whether it belongs to the desired Category belongs or not, is in the European Patent application 99 108 354.4, the entire content of which is hereby described is incorporated by reference into the present application. The device described therein is able to read text documents through its representation classified by means of vectors, the values of the vector components each correspond to the frequency with which a particular word or a term appears in the document. Such a vector, which is a document represents, spans an n-dimensional vector space, and several documents together also span a certain vector space. The classification is carried out by calculating a hyperplane that contains the vector space in at least splits two sub-levels, making one classification into so many Classes, like subspaces are available can be. A learning or training process consists of training of the vector space and the corresponding separating hyperplane for one Set of training documents. An unknown document can then can be classified by calculating whether the corresponding Vector falls into one or the other subspace. As with the previously described Procedure it possible is to represent the elements of a text document by a layout document, that hints about their surrounding areas there, and since the layout document itself in turn is a text document, can in the aforementioned European patent application described classification apparatus can be used for classification purposes. A preferred implementation of the classification device, which is described in the patent application consists of a neural Mesh, such as in a perceptron. More details like the decision device can be implemented are taken from this application and will therefore not continue described here in detail.

However, it should be understood that any other neural network or computer method or a device capable of documents to evaluate (classify) whether they belong to a certain category or not, for training layout documents and then for meeting the Decide whether a candidate (or their corresponding layout document) is correct extracted or not, can be used. It should further understood that any other layout document representation cannot be used in connection with the present invention only the layout documents in which the positions are represented by sign sequences become. For example, it is also possible that the positions are encoded by absolute numbers that represent the positions (coordinates) represent, or by angles and distances (polar coordinates).

It is understood by those skilled in the art that the foregoing detailed description is merely a describes exemplary embodiment of the present invention, other embodiments are also within the ability of the general knowledge of those skilled in the art. It will also be immediately apparent to those skilled in the art that the method of the present invention can be implemented by any computer system, general purpose computer, or by any special hardware that implements a method described above. An apparatus according to the present invention may therefore be in any computer system that carries out the method of the present invention, the method being, for example, in a computer system as in FIG 1 shown can exist. As far as certain device elements or device components are mentioned here or in the appended claims, they can be implemented by a computer or a part of a computer that carries or executes computer programs or parts of computer programs. As far as the present invention relates to a computer program or a computer program product, it is obvious to a person skilled in the art that a data carrier or any computer element such as a memory or a transmission line or the like, which can receive computer program instructions, can form an embodiment of the present invention as far as it is Receives computer program instructions that enable a computer to perform a method according to the present invention. Those skilled in the art will also recognize that many computer programs can be written that operate in accordance with the principles of the present invention as described above, so that any computer programs that operate in accordance with the method of the invention as described above are considered to be within the scope of the present invention are. In addition, a data structure representing the structure of a layout document as described can also be an embodiment of the invention, regardless of whether it is on a storage medium, a data carrier, a transmission line, a memory such as a ROM, a RAM, or the like , is trained. Furthermore, the present invention can be used in a small server architecture, which means that parts of a computer program implementing the present invention are executed on the server and other parts on the client.

As far as device components in the present description or the appended claims, they can be realized by a computer that is a computer program or executes certain program instructions, or they can by any special hardware will be implemented that will function this component executes like an electronic circuit, a special purpose computer, or similar.

Further modifications and applications of the present invention are for recognizable to those skilled in the art, and it is understood that the present Invention was only explained by exemplary embodiments, which are not as limiting for the scope of the present invention should be understood. In particular, it should be understood that the example of extracting a Date of birth is just an example and that explained above Method for extracting any information elements from a Text document can be used that belongs to a certain category belong, as is immediately recognized by the specialist.

Claims (24)

Computer-implemented method for generation an input to be used by a classifier on an electronic document that contains a variety of elements comprises the process being characterized by: Analyze the electronic document to put one or more of the elements together with information about maintain their respective positions in the document; Produce of an electronic layout document that is used as the input of the classifier to be used, the electronic layout document comprising: a representation a variety of elements obtained in the analyzing step along with information that is absolute and / or relative Represent position in the electronic document. The method of claim 1, wherein the layout document having: a representation a first element from a plurality of elements of the text document along with information that is absolute and / or relative Represent position in the electronic document; and a representation composed of others from the multitude of elements of the text document with information indicating their absolute and / or relative position represent in the electronic document, with the others Elements within a predefined or custom Area that is adjacent to and / or surrounds the first element. The method of claim 1 or 2, further comprising: searching for items that match a particular search criteria to obtain candidates for items that fall within a particular category in terms of information content; and Generate a layout document for one or more of the candidate elements. The method of claim 3, wherein the step of Searching candidates further one or more of the following steps having: Search for items in the document that have a specific Meet format criteria; Search for words in the document that meet a specific string comparison criterion fulfill; Performing one fault-tolerant word search; Do a search for a Element which has a predetermined relative position with respect to a has found candidate; Perform a database query to search for elements that are stored in a database Words match. A method according to any one of claims 1 to 4, which is distant does one or more of the following: Represent the position of an element in the layout document by a corresponding one Character sequence based on a predefined position coding scheme; Represent of elements that have a recognizable predefined format, by a character sequence based on a predefined format coding scheme; Represent of elements that have a recognizable meaning by a character sequence based on a predefined meaning coding scheme. The method of claim 5, wherein the recognized format one or more of the following: Vertical and / or horizontal lines in the document; Floating point numbers; Dates; whole Numbers; ZIP codes. Method according to one of the preceding claims, wherein the area, which is taken into account for the generation of the layout document, one or more geometric surfaces whose dimensions can be predefined or set by the user can be. A method according to any one of claims 1 to 7, which further comprises: using the electronic layout document as one Input for a classifier for training the classifier or for evaluating the input by the classifying device. Method of extracting one or more Elements from an electronic document that relate to a specific one include predefined category the method being characterized in that it comprises: Search for candidate elements in the document based on one or several predefined search criteria; Generate a layout document according to one of the previous claims for each Candidate element obtained by the search step; and Judge, whether the candidate belongs to the category based on the information content of the layout document. Method for training a classification device, to train the device to recognize if an element of a document belongs to a certain category or not, the method being characterized in that it comprises: Search for candidate elements in the document based on one or several predefined search criteria; Generate a layout document according to one of the previous claims for each Candidate element obtained by the search step; and Enter of the layout document into the classifier to the classifier to train, along with information that determines whether the candidate belongs to the particular category or not. The method of claim 9 or 10, wherein the classifying device is a neural network. Device for generating an input from a Classifier to be used based on a electronic document comprising a plurality of elements, the Device is characterized by: an analyzer for Analyze the electronic document to one or more of the Items along with information about their location to get in the document; a generator for generating a electronic layout document that as the input of the classifier to be used, the electronic layout document comprising: a representation a variety of elements obtained in the analyzing step along with information that is absolute and / or relative Represent position in the electronic document. The apparatus of claim 12, wherein the layout document comprises: a representation of a first element from a plurality of elements of the text document together with information reflecting its absolute and / or relative position in the electronic document present; and a representation of others of the plurality of elements of the text document along with information representing their absolute and / or relative position in the electronic document, the other elements being within a predefined or user-defined area that is adjacent to the first element and / or this surrounds. The apparatus of claim 12 or 13, which further having: a viewfinder to search for items that a meet certain search criteria to find candidates for items to get which ones their information content falls into a certain category; and the Generator for generating a layout document for one or more of the candidate elements. The apparatus of claim 14, wherein the viewfinder is for Searching for candidates also one or more of the following characteristics having: an item finder to search for items in the document that meets a certain format criterion; one Word searcher to search for words in the document that match a particular Meet string comparison criterion; one Word finder to perform a fault-tolerant word search; an element finder to perform a Search for an item that has a predetermined relative position with respect to a found candidate; one Database querier to perform a database query to search for elements that are included in a Database stored words match. Apparatus according to any one of claims 12 to 15, wherein the layout document is further on one or more of the following characteristics is adapted: Represent the position of an element in the layout document by a corresponding one Character sequence based on a predefined position coding scheme; Represent of elements that have a recognizable predefined format, by a character sequence based on a predefined format coding scheme; Represent of elements that have a recognizable meaning by a character sequence based on a predefined meaning coding scheme. The apparatus of claim 16, wherein the recognized Format of one or more of the following includes: Vertical and / or horizontal lines in the document; Floating point numbers; Dates; whole Numbers; ZIP codes. Device according to one of claims 12 to 17, wherein the area which is considered to generate the layout document, one or several geometric surfaces whose dimensions can be predefined or set by the user can be. The apparatus of any one of claims 12 to 18, which further having: the classifier, which is the electronic layout document as an input to train the classifier or used to evaluate the input by the classifier. Device for extracting one or more Items that belong to a certain predefined category an electronic document, the device being characterized is through: a finder to find candidate elements in the document based on one or more predefined ones Search criteria; a generator for generating a layout document according to one of the preceding claims for each Candidate element obtained in the search step; and one Judge to judge whether the candidate element belongs to the category heard, based on the information content of the layout document. Classifying device which can be trained to to recognize whether an element of a document is related to a particular Category belongs or not, the device being characterized by one Finder based on finding candidate elements in the document on one or more pre-defined search criteria; one Generator for generating a layout document according to a of the preceding claims for each Candidate element obtained from the seeker; and a Setup for entering the layout document along with information whether the candidate belongs to the particular category or not into the classifier to the classifier to train. Apparatus according to claim 20 or 21, wherein the Classifier is a neural network. Computer program, which program code executable by a computer program , characterized in that it is adapted to cause the computer to carry out a method according to any one of claims 1 to 11. Data structure for use as input in a Classifying device, wherein the data structure is characterized is, that you was obtained in that a Procedure according to a of claims 1 to 11 executed has been.