Efficient globally optimal interpretation of documents

A system for parsing a document having a plurality of lines on which a series of actual items are listed, the listing of each actual item spanning one or more lines, said system comprising:

• a processor operative to:
• obtain a plurality of candidates representing hypothetical items within the document, each candidate spanning one or more lines of the document and having a local cost associate therewith, said local cost representing a confidence in a quality of the candidate with respect to an item model;
• determine one or more labeling costs for one or more intervals of the document defined between given pairs of lines of the document, each interval containing one or more candidates therein, each said labeling cost reflecting a different configuration of the candidates within the interval for which the labeling cost is determined;
• identify a best labeling for each interval based on the one or more labeling costs determined for that interval, said best labeling corresponding to one of the different configurations of the candidates within the interval for which the best labeling is being identified;
• define a global objective function;
• and
• select a subset of the candidates such that the global objective function is optimize, based on the identified best labelings.