Automatically extracting structure and data from business reports.
A considerable amount of clean semistructured data is internally available to companies in the form of business reports. However, business reports are untapped for data mining, data warehousing, and querying because they are not in relational form. Business reports have a regular structure that can be reconstructed. We present algorithms that automatically infer the regular structure underlying business reports and automatically generate wrappers to extract relational data.
Introduction
A considerable amount of clean semistructured data is available to companies through internal
business reports created during periodic data processing. Business reports provide data for
monitoring account balances, inventory levels, transaction status, current production status,
etc. Although the subject matter may di#er widely, many business reports share a similar
structure.
Businesses that employ state-of-the-art techniques capture reports in a Computer Output
to Laser Disk (COLD) 1 storage system that is accessible through an enterprise-wide
network. COLD systems support queries based on date, title, free-text scanning (as in
regular-expression matching), and precomputed indexes whose definitions have been constructed
manually at a significant cost in labor and systems-administration/maintenance
e#ort.
Because business reports are an integral part of the business process, when errors are
discovered, corrections must be made, and a new version of the report must be issued.
Compared to other sources of information, business reports are clean. 2 If this clean data
were available in relational form, it could feed a data warehouse.
For various reasons, in some cases important historical and operational data is only available
in a COLD system. In other cases, even when such data is available in legacy database
systems or file-processing systems, the variety of di#erent data sources and "middleware"
access layers can make it di#cult to assemble and integrate information from an organiza-
tion's databases. Since an organization's business reports provide a clean, comprehensive,
integrated view of the underlying data of interest, wrappers to extract this data could be less
expensive (and are sometimes the only option).
Giving a user finer granularity access to a business report allows more precise queries. If a
business report could be automatically decomposed into relational records, then it would not
be necessary for a company to have a mediator constructed for each and every one of its data
sources. Automatic decomposition would make possible the movement of information from
a COLD system into a relational database where data mining and other information tools
are available. Alternatively, automatic decomposition would support a direct SQL interface
to a COLD system, permitting data mining and queries directly on the COLD archive.
automatic decomposition, an end user must develop ad hoc techniques to extract
systems may use other storage technology besides optical disk, for example tape or RAID;
we use the term "COLD" to denote any kind of report archive system. Recently this has also been termed
"enterprise reporting," but for brevity we use "COLD."
As used in data warehousing, "clean" data is free of errors and redundancy, and is suitable for storing in
the warehouse.
information from a business report. For example, she may manually place data from a
business report into her spreadsheet. If she receives the business report electronically, she
may programmatically transfer the data to a database application such as Access [1] using
specialized tools such as awk [3], perl [25], Cambio [8], InfoXtract [6, 15], or Monarch [19]. The
di#culties she faces in an ad hoc approach are: the manual specification, the e#ort to set up a
process, the e#ort to maintain the process, and the acquisition of su#cient programming skills
to modify the process. Automatic decomposition eliminates the report-definition specification
inherent in manual or programmatic report-based information extraction.
Automated extraction is possible in narrow application domains [12, 13, 14]. However,
the techniques for narrow application domains are infeasible for large report bases because
ontologies would have to be manually constructed for each di#erent business report. Semi-automatic
techniques for wrappers have also been explored [2, 5, 11, 16, 22], but these
techniques do not take advantage of the special structural properties of business reports. The
project most closely related to ours is NoDoSE [2], which attacks the more general problem
of extracting structure from any kind of semistructured document. We apply techniques
specific to the business-report domain.
This paper presents a system that utilizes a lattice of field descriptions to automatically
identify fields. From field-level descriptions, this system then infers line types that describe
the kinds of lines found in a particular business report, and it infers and factors out page headers
and footers, yielding a line-type sequence whose regular structure can be inferred using
standard algorithms [17, 18]. Our system, implemented in Java, stores extracted information
in relational tables according to line type and line-group structure.
The remainder of this paper has four sections. Section 2 gives a high-level system overview.
Section 3 gives a detailed description of key algorithms and data structures. Section 4 gives
the results of a report survey. Section 5 gives our conclusions.
Business
Report
Field
Description
Lattice
Extract Fields
Report
Structure
Definition
Report
Decomposition
Populated
Database
Infer Line Types
Infer Page Headers
and Footers
Infer Recursive Groups

Figure

1: Business report structure and data extraction process.

Overview

Figure

1 outlines the two phases of the business report decomposition process: (1) the four
steps of report-structure inference, and (2) report decomposition. The input is a business
report R, about which we make five assumptions:
1. R is composed of fields that are aggregated into lines, which are in turn aggregated
into larger structures.
2. R is in printable ASCII and represents meaningful human-readable information. 3
3. R uses the ASCII form-feed character (FF) as the page delimiter, and the ASCII linefeed
character (LF) as the line delimiter. 4
4. Each page has the same number of lines R L
, and the width of each line is W characters,
padded with blanks if necessary.
5. Blank lines and blanks between fields are for human readability only.
3 We use ASCII, but EBCDIC or another character set could be used in similar fashion. In the case of
EBCDIC, it is easy to translate from EBCDIC to ASCII format. In the case of non-English character sets
or non-U.S. business reports, di#erent regular expressions would be required.
4 There is no di#culty in using CR-LF as a line delimiter as on PC systems.
006 9994 10355 JASON MASON CONSTRUCTION INC 100,000.00 .06005 03/07/99
MS
MS
* TOTAL LARGE CD * 1,605,529.79

Figure

2: A typical type I report page.

Figure

3: A portion of a typical type II report page.
We have observed two major categories of business report structure, distinguished by the
relationship between line and record structures. Both kinds of business reports have possible
page headers, possible page footers, and a report body that consists of repeating detail lines.
A type I detail line has columns (fields), belongs to a distinct line-type category, and contains
information about a single record. In contrast, a type II detail line contains fields pertaining
to several records. A type I business report contains only type I detail lines. A type II
business report contains type II detail lines (and may also contain type I detail lines).

Figure

2 gives an example of a simple type I report. 5 Each detail line in Figure 2 describes
a particular certificate of deposit. Figure 3 shows a portion of a type II checking-account
statement. Each detail line in Figure 3 lists two or three cleared-check items, each of which
has a check number, amount, and date cleared.
When we correctly identify the basic line types that exist within a type I report, then
we can extract the report structure. In contrast, extracting the structure of a type II report
requires information beyond line classification. In this paper we discuss type I reports. Type
II reports are the subject of a separate paper.
Our process starts with a type I business report R, and a field-description lattice F
5 None of the data in this paper is actual customer data, but the patterns are based on actual business
report structures not designed by us.
(described in Section 3.1), infers the structure of R, stores its definition in a relational
database, decomposes R, and stores its decomposition in the database. The contents of R
can now be queried. This paper focuses on the four steps of the report-structure inference
phase, which consists of the following four steps (corresponding to Algorithms 1 through 4
respectively).
1. For each line t of R, decompose t into its sequence of fields.
2. Infer B, the set of basic line types of R. For each line t of R, assign t its basic line type
from B.
3. Infer page headers and footers for R. Factor out the page structure from R's line type
description.
4. Infer R's recursive line groups.
This system is implemented in Java 2, using the OROMatcher 1.1 regular-expression
library [21] for matching and extracting substrings from lines. We used mySQL [20] for the
database management system and twz1jdbcForMysql [23] for the JDBC interface to mySQL.
Source code is available on our Web site [10].
2.1 Notation
Before proceeding, we introduce notation and terminology. In general, let
#R[1], ., R[R P
]# 6 be a business report with R P
pages, each with R L
lines, R[i] denoting
the i'th page. Each page is a sequence of lines, so
]#. Each line is
a sequence of W characters; after executing Algorithm 1 we can also represent a line as a
sequence of fields:
Given a line t, we denote a substring of t from position j to k, 1
t[j, k]. A field f in t is a 4-tuple (j, k, i, s), where is the substring of t to which f
6 We always denote an ordered sequence with angle brackets #. Also, all indexes are 1-based.
corresponds, j is the starting position of f , k is the ending position, and i is a pattern index
to be defined in Section 3.1.
fields in lines t 1 and t 2 respectively. We
say that f 1 and f 2 overlap if there is a q such that
overlap, the overlap has one of five alignment values:
(share left and right endpoints),
ALIGN they do not AGREE, but both fields are numeric and aligned at
the decimal-point position,
LR they do not AGREE nor ALIGN, but
CENTER they do not AGREE, ALIGN, nor are LR, but
(center aligned),
OTHER none of the above apply.
A field type f for fields f
is index of the least upper bound of
the elements in the field-description lattice F that are indexed by i 1 , ., i n . F is defined in
Section 3.1. For each q, 1 # q # n, let s # q be s q padded with j q - j blanks on the left and
blanks on the right; then
A line type t for lines t 1 , ., t m is a sequence of field types f
(j with two properties: (1) none of the field types may overlap, and (2) s 1 , ., s n
are each ordered sequences containing m strings that correspond respectively to all the fields
in lines t 1 , ., t m . By these two properties we guarantee that we can reconstruct the original
lines from a line type.
A group type d for R is a triple (a, b, c) where a is either a line type or an ordered sequence
of group types, and b and c are respectively the minimum and maximum number
of consecutive occurrences of d observed in R.
3 Structure Extraction Algorithms
As outlined in Section 2, four algorithms extract a business report's structure. Sections 3.1
through 3.4 describe Algorithms 1 through 4 respectively.
3.1 Field Detection
Consider the type I report of Figure 2. The first task is to decompose each line into fields.
This is done by applying Algorithm 1 to each line of R.
Let F be the field-description lattice of Figure 4. Indentation in Figure 4 represents
precedence, and the universal lower bound is the empty expression (not shown explicitly).
Each element of F is a class that describes a set of ASCII strings typically found in business
reports. Julian is the only class with two immediate successors (Date and Number). The
parenthesized numbers in Figure 4 are used in Section 3.2.1.
E[e]# be a sequence of regular expressions corresponding to the field-
description lattice of Figure 4 (except for the universal upper bound Any and the universal
lower bound #). E[e], the last element of the sequence E, has the property that it recognizes
any sequence of contiguous non-blank characters (E[e] corresponds to the class String in this
case).

Table

1 in Appendix A shows the regular expressions of E. Notice that no expression
E[i] in E matches a string of only blank characters. Algorithm 1 extracts the fields in line t
according to E.
Algorithm 1. Extract fields from line.
Input: Regular-expression sequence E and line t.
Output: The sequence of disjoint fields that comprise t relative to E.
to e do
while E[i] matches t do
Set j to the start of the first match.
Let k be the largest k # W such that E[i] recognizes t[j, k].
Record the field as the 4-tuple (j, k, i, t[j, k]).
Replace the characters of t[j, k] with a special non-ASCII symbol.
while
end for
Sort the fields by j, the beginning field position.
Any (1)
String
Time (.3)
Hour Minute Second (0)
Hour Minute (0)
Date
Julian (0)
Day Month Year (0)
Month Day Year (0)
Year Month Day (0)
Month Year (0)
Month Day (0)
Day Month (0)
Phone Number (.3)
Phone with Area Code (0)
Phone without Area Code (0)
ID Code (.3)
ID Begins with Letters (0)
ID Ends with Letters (0)
ID with Digits, Dashes (0)
Number
Julian (0)
Percent (0)
Negative (0)
General Number (0)
Fraction (0)
Currency (0)
Currency with Dollar Sign (0)
Page Number (0)
Field Label (0)
Dividing Line (0)

Figure

4: Field-classification lattice.
Regular-expression matching can be linear in the length of the text to be matched (if we
accept exponential space in pathological cases) [4], so the inner loop runs in O(W ) time.
Since there are e expressions, the outer loop executes e times. Thus, Algorithm 1 executes in
O(eW ) time. Since E[e], the last regular expression, always recognizes contiguous non-blank
characters, Algorithm 1 terminates and extracts all fields from t. The step that replaces the
characters of t[j, k] with a special symbol forces the fields to be disjoint since t[j, k] can no
longer be matched by any expression.
3.2 Basic Line-Type Inference
Algorithm 2 is the heart of our technique. It infers basic line types that describe categories
of lines in a business report. Before presenting the algorithm we define three field- and
line-distance measures.
We first introduce two di#erent distances between fields: a first-order distance, and a
second-order distance. first-order distance measures field distance using a character-level
string comparison. Second-order distance yields a similarity metric based on the field-
classification lattice. A traditional method for characterizing string similarity is edit distance
[24], which describes the cost of transforming one string into the other. But the computation
of edit distance is O(mn) where m and n are the lengths of the strings being compared. Our
simple but adequate first-order distance can be computed in O(max(m,n)) time.
We measure field distances using the minimum of first- and second-order distances together
with alignment information (e.g. are the two fields left justified or decimal-aligned).
Based on this field distance metric we define a line distance, used in Algorithm 2 to decide
when two line types belong to the same cluster.
3.2.1 Field Distance
Let s 1 and s 2 be non-empty ASCII strings. Without loss of generality, we assume that
|. The first-order distance between s 1 and s 2 , is:
string
(1)
where # K
(a, b) is the Kronecker delta function, namely 1 if a #= b and 0 if a = b.
field types. Recall that s 1 and s 2 are
ordered sequences of strings. The first-order field distance between f 1 and f 2 is:
string
Our first-order distance uses a (trivial) lattice on characters and ignores the higher-order
structure associated with fields. Our second-order distance uses the regular-expression sequence
field-description lattice F described in Section 3.1. E and F have three
important properties: 7
1. Lattice. Each pair of elements in F has a unique least upper bound.
2. Covering. Every ASCII string is a member of at least one class in F .
3. Consistency. Let F [i] and F [j] be classes in F , and let E[i] and E[j] be the regular
expressions in E that correspond to F [i] and F [j], respectively. If F [i] precedes F [j]
then the language recognized by E[i] is a subset of the language recognized by E[j].
We define a function # that assigns each element of F a value; more specific classes have
lower values than more general classes. Values for #, in the interval [0, 1], are shown in
parentheses in Figure 4, and were determined empirically.
Given these properties, we define the second-order field distance. Let f
be two field types. be the class in F corresponding
to the regular expression E[i 1 lub be the least upper
bound of F [i 1 ] and F [i 2 ]. Without loss of generality, we assume that #(F [i
The second-order field distance between f 1 and f 2 is:
The di#erence component of Equation 3 returns a low value for fields whose classes are
relatively close. The P term is an empirical constant to penalize fields whose least upper
bound is relatively general; we assigned P a value of 1.1 in our experiments. Finally, to
ensure that a distance stays in the interval [0, 1], Equation 3 uses the min(1, .) expression.
7 These properties require careful construction of the field-description lattice and regular-expression se-
quence, and we do not formally prove that they hold. For our purposes it is su#cient simply to assume
that these properties hold. For the lattice F in Figure 4 the class Any is defined to be the set of all ASCII
strings. The consistency property can be guaranteed if we replace each superior regular expression s by the
disjunction of s with each regular expression i that is inferior to s.
Given the first- and second-order field distances of Equations 1 and 3, we define
# field (f 1 , t 2 ), the field distance between field type f
the sequence of field types of line type t 2 , as follows. If f 1 either overlaps no field types
of t 2 or overlaps more than one field type of t 2 , we define # field (f 1 , t 2 ) to be 1. Oth-
erwise, let f be the single field type in t 2 that overlaps f 1 , and let
Equation 4 gives the definition of # field (f 1 , t 2
where A is the alignment value of the overlap of f 1 and f 2 , defined in Section 2.1. We
determined alignment values empirically, choosing 0, 0, .1, .2, and .4 for AGREE, ALIGN,
LR, CENTER, and OTHER, respectively.
3.2.2 Line Distance
be the number of field types in line type t 1 , and let n 2 be the number of field types
in line type t 2 . Based on # field , we define # line (t 1 , t 2 ), the line distance between t 1 and t 2 . If
both n 1 and n 2 are 0, then the value of # line is defined to be 0. If either n 1 or n 2 is 0 but
not both, then the value of # line is defined to be 1. Otherwise, # line is defined according to
Equation 5:
line
3.2.3 Line-Type Inference
Algorithm 2. Infer B, the set of basic line types for report R.
Input: R, after Algorithm 1.
Output: B, the set of basic line types for R, and
L, a mapping from the lines of R to line types in B.
Make a copy Q of R:
for each R[i][j], 1
do
Create a new line type t 1 for R[i][j].
duplicates a line type t 2 in Q then
Generalize t 2 to cover t 1 .
else
Add t 1 to Q.
end for
Reduce line types in Q to B:
for each line type Q[i], 1 # i # |Q| do
Let m be the smallest # line (Q[i], t) from Q[i] to any line type t in B.
Add Q[i] to B.
else
Generalize t to cover Q[i].
end for
Construct array L so that L[i][j] is the line type in B that covers line R[i][j].
Algorithm 2 terminates in O(G - R P - R L
time, where G is the cost of the "generalize"
operation, described below. .3 is a threshold chosen empirically. Line types t 1 and t 2
are duplicates if and only if their associated field-type sequences are identical up to the field
text, i.e. (a) they have the same number of field types, (b) the corresponding field types have
the same left and right positions, and (c) the corresponding field types are both recognized
by the same regular expression.
We now define what it means to generalize a line type t 2 to cover line type t 1 . For each
field type f be the number of field types in t 1 that overlap f 2 .
We denote these m field types as f
There are three possibilities for m:
do nothing with f 2 .
2. to the least upper bound of
padded with blanks as needed.
3. m > to e; pad the
strings in s 2 with blanks as needed, and add to s 2 the strings from s 1,1 , ., s 1,m , joined
and filled/padded with blanks as needed.
If any field type f 1 in t 1 was not overlapped by some field type in t 2 , add f 1 to t 2 . After
modifying t 2 , if any field types in t 2 now overlap each other, combine them as described above
in step 3.
3.3 Page Header/Footer Inference
A type I business report may have page header and/or a page footer. A page header for
report R is a sequence of line types that appears at the beginning of each page in R. If
line-type sequence A = #a 1 , ., a h # is a page header for R, then (#i,
. Similarly, a page footer is a sequence of line types that appears
at the end of each page in R (we assume that a page footer always starts at the same o#set
from the top of page). To distinguish between report detail and page headers or footers, we
require that each non-blank line type t # A # Z have the following properties for each page
R[i]:
. t does not repeat in R[i] two or more times in immediate succession, and
. t appears only once or twice on any single page R[i].
Algorithm 3. Infer page headers and footers from line types.
Input: Array L from Algorithm 2.
Output: Page-header sequence A, page-footer sequence Z, and
line-type sequence -
L with A and Z factored out.
Mark non-blank line types that cannot be page header/footer candidates:
If and L[i][j] is non-blank, then mark both L[i][j] and L[i][j
If (#j, k, l)j #= k #= l and
Infer page header:
Find the largest h, 0 # h # R L
such that (#i,
Set A to the first h line types of page R[1] may be empty).
Infer page footer:
Find the smallest f, h # f # R L
such that (#i, j)L[i][f
If such an f exists, set Z to line types f through R L
of page R[1];
otherwise let Z be the empty sequence and set f to R L
1.
Reduce L to -
L by removing page structure and blank lines:
L be the sequence of line types
Remove all blank line types that appear in -
L.
Note that whereas L is a two-dimensional array, -
L has only one dimension. Algorithm 3
terminates in O(R L -R P
time.
3.4 Recursive Group Inference
After the page-specific structure of a business report R has been factored out, we can focus
on inferring the structure of R's detail section. Miclet's technique [17, 18] is a reasonable and
general way to infer regular structure from a set of example strings. Because of the nature of
business reports and the simplifying assumptions this allows, it is possible to infer structure
from a single example. Our Algorithm 4 is a variant of Miclet's technique, using di#erent
decision heuristics governing when we should reduce a recursive group, and restricted to a
single example string (the array -
L of line types).
Business reports created with a report-writer 8 are built up from groups of the form uv k w,
where u is a (possibly empty) group header section, v is a detail section that repeats one
or more times, and w is a (possibly empty) group footer section. Each of the u, v, and w
sections may themselves be composed of other uv k w structures. We make three assumptions
about the uv k w structure of line-group types for a business report R reduced by Algorithms
1 to 3 to -
L:
1. k # 2; that is, v appears consecutively somewhere in -
L.
2. If group v appears k # 2 times consecutively in -
L, it forms the v k component of a uv k w
structure (and there is no predetermined upper bound for k). Also, uvw (where
may appear in -
L as long as uv k appears elsewhere in -
L.
3. Groups u, v, and w may not appear in -
individually (outside of a uv k w sequence).
There are no optional lines in a group. If the real report structure is uv k w, u and w
always appear together with v k . 9
We give three examples, representing a line types with lowercase letters. Example 1.
The sequence abccc is a line group with a group header
and an empty group footer, #. The reason for this particular uv k w solution is that c
Most business reports created by custom programming also follow these conventions.
9 This assumption does not hold for all type I business reports, but we leave such reports for future
investigation.
is the only repeating line type in our example. Example 2. The sequence abccabcccc is
(abc+)(abc+). Thus, an expression to describe the structure of
such a report is (abc+)+. Example 3. The sequence abccbccdabcd is formed by repeating
and nesting. We first create the inner group section c.
By substitution, the sequence is now aeedaed. Let d, with header a, detail section
e k , and footer d. By substitution, the sequence is now ff , which is a group with an empty
header and footer, and a detail section f k . The expression describing this report structure is
Essentially, Algorithm 4 reduces the regular expression defined by the line-type sequence
L to a more compact regular expression G that describes the recursive structure of -
L.
Algorithm 4. Infer recursive line-type groups.
Input: Basic line-type sequence B from Algorithm 2
and line-type sequence -
L from Algorithm 3.
Output: Recursive line-group structure.
Let g be a set of group types that contains one entry for each line type in B.
L to G by substituting each line type with its corresponding group type from g.
while |G| > 1 and changed = true do
to |G| do
Find the smallest j > i such that conditions 1, 2, and 3 hold.
Condition 1. Every group type in v is unique.
Condition 2. The sequence vv occurs in G.
Condition 3. After substituting a new group type for each occurrence of
in G, there is no group type in v that still occurs in G.
exists then
Create a new group type x whose definition is the sequence v.
Add x to g.
Substitute x in G everywhere v appears.
Replace all consecutive occurrences of x.x in G by a single x, and mark x
with the minimum and maximum consecutive-occurrence counts.
end for
while
Algorithm 4 is a least-fixed point algorithm, where the fixed point upon which we converge
is a regular expression to describe -
L. Because |G| is initially | -
L|, the while loop can execute
at most | -
L| times (since we only loop as long as a change has been made, and a change must
always reduce the size of G by at least 1). The for loop also executes at most | -
L| times.
Verifying Conditions 1, 2, and 3 and substituting x for v can both be done in -
time. Thus,
Algorithm 4 executes in O(|B|
In practice, Algorithm 4 usually took between
one and three passes to converge, running orders of magnitude faster than the worst case
just described. (This is because v k sequences tend to be long.)
There are five areas where we used empirically determined values to control the business-
report structure and data extraction process: (1) the regular expressions used to recognize
fields, (2) the values (#) associated with each class in the field-description lattice F , (3) the
value of alignment constants (AGREE, ALIGN, LR, CENTER, OTHER), (4) the threshold
for line-type generalization, and (5) the penalty for least-upper-bound generality in Equation
3. We used hundreds of reports from four di#erent organizations as the basis for our
choices.
To test our process, we used 76 business reports from a separate organization that had
not been used in the training phase. Of these 76 reports, 7 were not type I. An additional 7
reports were too short to be meaningful (i.e. they comprised a single page containing only
page headers or a single detail line). Of the 62 remaining reports, our process correctly
extracted the structure and data for 40 reports, but failed with 22. The 22 failures point out
directions for future enhancement. We discuss four.
1. E, our sequence of regular expressions for matching fields, was sometimes insu#cient.
We give four examples. (i) In one case, two fields that were usually separated by a single
blank space had a number sign (#) instead of a space on one line. This caused the two fields
to be recognized as a single string, which in turn caused the creation of an extra line type that
interfered with the recursive line-type group inference (Algorithm 4). (ii) In another case, we
discovered decimal-aligned numeric fields that were left-filled with underscores. Furthermore,
these underscores abutted the string field on the left (e.g. "One 5.52" and "Two 934.22").
Our system recognized the string portion together with the padding underscores as a single
field, and the numbers as a second field. Because of the overlapping of these fields, our system
generated too many line types for this report. (iii) In another case, we discovered currency
amounts specified with 4 digits after the decimal point, rather than the more common 2
digits. Due to the order of our expressions, our system broke such fields in two, which caused
too many line types to be generated. (iv) Finally, we found a string field that had two
internal spaces (e.g. "XXXX XX"), but our String pattern only expects one internal space.
This caused the field to be split and an extra line type to be generated. All of these problems
can be corrected by tuning E. For our test set, the amount of tuning required would have
been small. Adjustments to E are also required for non-U.S. business reports.
2. By far the most common reason for our process to fail was the problem of optional
fields in a line type. With more fields present on a line, our distance formulas are more
tolerant to optional fields. However it is often the case that lines with few fields also have
optional fields, and for lines with many fields, it is also often the case that several fields are
optional. Optional fields may lead to our system generating too many line types. Tuning the
threshold T of Algorithm 2 for a particular report can sometimes fix this problem, but it is
not a general solution.
3. There were several cases where we did not generalize two line types because of the
simplistic structure of Algorithm 2, which decides when to generalize based on a threshold.
In a future study we will apply clustering techniques such as recursive partitioning or nearest
neighbor (as in [9]) to find a better decision function to control when we generalize line types.
Such techniques are more likely to be general across business reports with very di#erent line
types, and will not be as sensitive to the order of processing line types.
4. Sometimes our uniformity assumption for line-type groups did not hold. That is,
Algorithm 4 assumes that if uv k w is a line-type group, then u, v k , and w always appear
together. In some cases lines in a uv k w structure are optional, and in other cases (especially
for short lines) a single line type may be reused in two distinct uv k w structures. Algorithm 4
needs to be revised to accommodate optional lines in a line-type group.
Conclusions
It is possible to automatically extract structure and data from business reports. Our process
correctly extracted the structure and data in 40 out of 62 type I business reports in a test
set we had not seen before.
While these initial numbers are encouraging, much work remains to be done. In Section 4
we mentioned four areas needing improvement: (1) field recognition, (2) detecting optional
fields, (3) improved line-type clustering techniques, and (4) handling optional lines within a
line-type group. We also plan to study structure and data extraction for type II reports. Here
it may be possible to use segmentation techniques like those applied in document imaging
and optical character recognition (OCR) algorithms (e.g. [7]). This may also enable more
accurate extraction of fields from lines, and may shed light on improved techniques for type I
line-type clustering. In the current investigation we have assumed fixed-width fields (padded
with blanks as needed); since some reports have variable-width fields, our process needs to
be extended to accommodate such reports. Also, our assumption that fields are separated by
white space does not always hold (some reports are designed to be printed on forms, which
may have lines between characters to divide fields). Future work should examine ways to
determine field boundaries in the absence of white space.
One weakness of our approach is the number of fixed, empirically determined constants
associated with our algorithms. We can surely achieve better results by using adaptive
techniques to dynamically compute and adjust these constants whenever possible.
After we have more fully mapped out structure and data extraction for type II reports,
we will construct a compressed data structure that contains a full inverted index of the
information in a business report R, together with su#cient information to reconstruct the
original pages of R from the inverted index. Often it is not enough to merely return the
data associated with a particular page; regulatory constraints (at a financial institution,
for example) may require that original pages be returned (e.g. records may be subject to
subpoena in legal proceedings, in which case the original report pages must be printed). Thus,
after fully inverting the data in a report, we must still be able to retrieve the original report
pages, including white space. The extensive structural information our system generates
constitutes an excellent domain-specific model for compressing reports.
Our business-report structure and data extraction system is implemented in Java. We also
implemented a graphical pattern editor tool to assist in the creation and debugging of regular
expressions for field extraction. This tool, available from our Web site as PatternEditor 1.0
[10], has general applicability for regular-expression debugging beyond our current project.



--R

Microsoft Corporation access page.

The AWK Programming Language.

Wrapper generation for semi-structured internet sources
Mining mainframe reports: Intelligent data extraction from print streams
Background structure in document images.
Data Junction Corporation home page.
An iterative clustering algorithm for interpretation of imperfect line drawings.
Data Extraction Group home page.
A scalable comparison-shopping agent for the World-Wide Web

A conceptual-modeling approach to extracting data from the web

IA Corporation home page.
Wrapper induction for information ex- traction
Regular inference with a tail clustering method.
Structural Methods in Pattern Recognition.
DataWatch Corporation home page.
URL: http://www.

Learning to extract text-based information from the World-Wide Web
URL: http://www.
The string to string correction problem.
Programming Perl.
--TR
Compilers: principles, techniques, and tools
The AWK programming language
Programming perl
A scalable comparison-shopping agent for the World-Wide Web
Wrapper generation for semi-structured Internet sources
NoDoSEMYAMPERSANDmdash;a tool for semi-automatically extracting structured and semistructured data from text documents
Ontology-based extraction and structuring of information from data-rich unstructured documents
The String-to-String Correction Problem
Conceptual-model-based data extraction from multiple-record Web pages
A Conceptual-Modeling Approach to Extracting Data from the Web
automatic wrapper generation;regular expressions;report structure;data and information extraction;business reports