Segmentation of strings into structured records

A process for segmenting strings into component parts comprising:

• providing a reference table of string records that are segmented into multiple substrings corresponding to database attributes, wherein the reference table of string records does not comprise manually segmented training data;
• analyzing the substrings within database attribute values of string records for an attribute during a training phase to provide a state model that categorizes the substrings within database attribute values into positions based on a fixed beginning, middle, and trailing token topology for said attribute that:
• categorizes beginning and trailing substrings of a database attribute value that includes multiple substrings into corresponding beginning and trailing positions,
• categorizes each substring of the database attribute value that does not comprise a beginning or trailing substring into a middle position,
• accepts a null token for an empty attribute component,
• defines beginning, middle, and trailing state categories, wherein each state category includes states that accept tokens only if appearing in a corresponding one of said beginning, middle, and trailing positions, and
• adjusts said states and probabilities associated with said states within said state categories in order to relax sequential specificity and account for erroneous token placement when evaluating tokens in the input string appearing in particular positions, wherein the state category corresponding to a particular position in which the token appears is adjusted to include states from another state category that accept tokens appearing in a different position;
• breaking an input record into a sequence of tokens;
• determining a most probable segmentation of the input record by comparing the tokens of the input record with state models derived for attributes from the reference table;
• segmenting the input record into one or more component parts according to the most probable segmentation;
• and
• storing the one or more component parts in a database on a computer system.

A computer system for processing input strings to segment those records for inclusion into a database comprising:

• a) a database management system to store records organized into relations wherein data records within a relation are organized into a number of attributes;
• b) a model building component on the computer system that builds a number of attribute recognition models derived from training data from an existing relation of data records, wherein training data corresponding to database attributes in the existing relation of data records does not comprise manually segmented training data, wherein one or more of said attribute recognition models includes probabilities for segmenting input strings into component parts which categorizes tokens in database attribute values of the data records into positions based on a fixed beginning, middle, and trailing token topology that:
• categorizes each boundary token of a database attribute value that includes multiple tokens into corresponding beginning and trailing positions,
• categorizes each token that does not comprise a boundary token of a database attribute value into a middle position,
• defines beginning, middle, and trailing state categories, wherein each state category includes states that accept tokens only if appearing in a corresponding one of said beginning, middle, and trailing positions, and
• adjusts said states and probabilities associated with said states within said state categories in order to relax sequential specificity and account for erroneous entries when evaluating tokens within an input string appearing in particular positions, wherein the state category corresponding to a particular position in which the token appears is adjusted to include states from another state category that accept tokens appearing in a different position;
• and
• c) a segmenting component on the computer system that receives an input string and determines a most probable record segmentation by evaluating transition probabilities of states within the attribute recognition models built by the model building component.

A system for evaluating an input string to segment said input string into component parts comprising:

• means for providing a state transition model derived from training data from an existing collection of data records that includes probabilities to segment input strings into component parts, wherein the training data corresponding to database attributes in the existing collection of data records does not comprise manually segmented training data, and the state transition model categorizes tokens in database attribute values of the data records into positions based on a fixed beginning, middle, and trailing token topology that:
• categorizes each boundary token of a database attribute value that includes multiple tokens into corresponding beginning and trailing positions,
• categorizes each token that does not comprise a boundary token of a database attribute value into a middle position,
• defines beginning, middle, and trailing state categories, wherein each state category includes states for that accept tokens only if appearing in a corresponding one of said beginning, middle, and trailing positions, and
• adjusts said states and probabilities associated with said states within said state categories in order to relax sequential specificity and account for erroneous token placement when evaluating tokens in the input string appearing in particular positions, wherein the state category corresponding to a particular position in which the token appears is adjusted to include states from another state category that accept tokens appearing in a different position;
• means for determining a most probable segmentation of the input string by comparing an order of tokens that make up the input string with the state transition model derived from the existing collection of data records;
• means for segmenting the input string into one or more component parts according to the most probable segmentation;
• and
• means for storing the one or more component parts in a database on a computer system.