Instance-based sentence boundary determination by optimization

A computer readable medium having computer readable program code embodied therein for processing an optimization method for instance based sentence boundary determination, the computer readable program code comprising:

• process for setting the initial upper bound (UB) of the cost associated with the optimized solution to the lowest cost derived by several greedy algorithms;
• process for identifying all corpus instances stored in electronic database that contain one or more of a plurality of desired propositions;
• forming a search tree structure with branches for each of plurality of identified corpus instances that contain one or more of said plurality of desired propositions;
• process for deleting one or more of a plurality of undesired propositions from said identified corpus instances;
• process for updating the overall cost with one or more deletion cost;
• process for inserting one or more of said plurality of desired propositions that were not contained in said corpus instance into said corpus instance;
• process for updating the overall cost with one or more insertion cost;
• process for calculating the lower bound (LB) of the cost associated with the current solution (or partial solution);
• process for pruning the current search branch if the LB is greater than the established UB;
• process for recursively computing the best solution associated with generating one or more additional sentences to convey the rest of said plurality of desired propositions that were not contained in said corpus instance;
• updating the overall cost with a boundary cost plus the cost associated with the best solution found by the recursive procedure;
• process for updating UB if the current overall cost is lower than UB;
• process for outputting a solution that has the lowest overall cost using a set of said identified corpus instances with a set of said deletion, insertion and sentence break operations.

A computerized system for optimization of instance-based sentence boundary determination comprising:

• data entry and data output devices operationally connected to a computerized domain;
• a corpus stored in an electronic database and domain data accessible through a communications link and stored in a storage medium;
• said computerized domain performing the following
• setting the initial upper bound (UB) of the cost associated with the optimized solution to the lowest cost derived by several greedy algorithms;
• identifying all corpus instances stored in electronic database that contain one or more of a plurality of desired propositions;
• forming a search tree structure with branches for each of plurality of identified corpus instances that contain one or more of said plurality of desired propositions;
• deleting one or more of a plurality of undesired propositions from said identified corpus instances;
• updating the overall cost with one or more deletion cost;
• inserting one or more of said plurality of desired propositions that were not contained in said corpus instance into said corpus instance;
• updating the overall cost with one or more insertion cost;
• calculating the lower bound (LB) of the cost associated with the current solution (or partial solution);
• pruning the current search branch if the LB is greater than the established UB;
• recursively computing the best solution associated with generating one or more additional sentences to convey the rest of said plurality of desired propositions that were not contained in said corpus instance;
• updating the overall cost with a boundary cost plus the cost associated with the best solution found by the recursive procedure;
• updating UB if the current overall cost is lower than UB;
• outputting a solution that has the lowest overall cost using a set of said identified corpus instances with a set of said deletion, insertion and sentence break operations.