Trie-based normalization of field values for matching
A system tokenizes values stored in a field by multiple records. The system creates a trie from the tokenized values, each branch in the trie labeled with one of the tokenized values, each node storing a count indicating the number of the multiple records associated with a tokenized value sequence beginning from a root of the trie. The system tokenizes a value stored in the field by a prospective record. Beginning from the root of the trie, the system identifies each node corresponding to a token value sequence for the prospective record's tokenized value. Beginning from the most recently identified node for the prospective record's token value sequence, the system identifies each extending node which stores a count that satisfies a threshold, each identified extending node corresponding to another token value sequence. The system uses the other token value sequence to identify one of the multiple records that matches the prospective record.
1. A system comprising:
one or more processors; and
a non-transitory computer readable medium storing a plurality of instructions, which when executed, cause the one or more processors to:
tokenize, by a database system, values stored in a field, of a plurality of fields, by a plurality of records;
create, by the database system, a trie from the tokenized values, each branch in the trie for the field being labeled with one of the tokenized values, each node of the trie for the field storing a count indicating a number of the plurality of records associated with a tokenized value sequence beginning from a root of the trie;
tokenize, by the database system, a record field value stored in the field by a prospective record;
identify, by the database system, beginning from the root of the trie, each node corresponding to a token value sequence associated with the tokenized record field value;
identify, by the database system, beginning from a most recently identified node corresponding to the token value sequence, each extending node storing a record number count that when divided by another count, corresponding to the most recently identified node, generates a corresponding ratio which is determined to satisfy a threshold, each identified extending node corresponding to an extending token value sequence associated with the field; and
identify, by the database system, using the extending token value sequence associated with the field, an existing record of the plurality of records that matches the prospective record.
2. The system of claim 1 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises bypassing a token value in the token value sequence associated with the prospective record.
3. The system of claim 1 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises bypassing a node that lacks a correspondence to a token value in the token value sequence associated with the prospective record.
4. The system of claim 3 , wherein bypassing the node comprises identifying a subsequent node based on a transition probability associated with the subsequent node.
5. The system of claim 1 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises replacing a token value in the token value sequence with a substitute token value.
6. The system of claim 1 , wherein identifying the existing record that matches the prospective record comprises submitting the match identification for approval by a user.
7. A computer program product comprising a non-transitory computer readable medium with computer readable program code stored thereon, to be executed by one or more processors when retrieved from the non-transitory computer-readable medium, the program code including instructions to:
tokenize, by a database system, values stored in a field, of a plurality of fields, by a
plurality of records;
create, by the database system, a trie from the tokenized values, each branch in the trie for the field being labeled with one of the tokenized values, each node of the trie for the field storing a count indicating a number of the plurality of records associated with a tokenized value sequence beginning from a root of the trie;
tokenize, by the database system, a record field value stored in the field by a prospective record;
identify, by the database system, beginning from the root of the trie, each node corresponding to a token value sequence associated with the tokenized value;
identify, by the database system, beginning from a most recently identified node corresponding to the token value sequence, each extending node storing a record number count that when divided by another count, corresponding to the most recently identified node, generates a corresponding ratio which is determined to satisfy a threshold, each identified extending node corresponding to an extending token value sequence associated with the field; and
identify, by the database system, using the extending token value sequence, an existing record of the plurality of records that matches the prospective record associated with the field.
8. The computer program product of claim 7 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises bypassing a token value in the token value sequence associated with the prospective record.
9. The computer program product of claim 7 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises bypassing a node that lacks a correspondence to a token value in the token value sequence associated with the prospective record.
10. The computer program product of claim 9 , wherein bypassing the node comprises identifying a subsequent node based on a transition probability associated with the subsequent node.
11. The computer program product of claim 7 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises replacing a token value in the token value sequence with a substitute token value.
12. The computer program product of claim 7 , wherein identifying the existing record that matches the prospective record comprises submitting the match identification for approval by a user.
13. A method comprising:
tokenizing, by a database system, values stored in a field, of a plurality of fields, by a
plurality of records;
creating, by the database system, a trie from the tokenized values, each branch in the trie for the field being labeled with one of the tokenized values, each node of the trie for the field storing a count indicating a number of the plurality of records associated with a tokenized value sequence beginning from a root of the trie;
tokenizing, by the database system, a record field value stored in the field by a prospective record;
identifying, by the database system, beginning from the root of the trie, each node corresponding to a token value sequence associated with the tokenized record field value;
identifying, by the database system, beginning from a most recently identified node corresponding to the token value sequence, each extending node storing a record number count that when divided by another count, corresponding to the most recently identified node, generates a corresponding ratio which is determined to satisfy a threshold, each identified extending node corresponding to an extending token value sequence associated with the field; and
identifying, by the database system, using the extending token value sequence associated with the field, an existing record of the plurality of records that matches the prospective record.
14. The method of claim 13 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises bypassing a token value in the token value sequence associated with the prospective record.
15. The method of claim 13 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises bypassing a node that lacks a correspondence to a token value in the token value sequence associated with the prospective record.
16. The method of claim 15 , wherein bypassing the node comprises identifying a subsequent node based on a transition probability associated with the subsequent node.
17. The method of claim 13 , wherein identifying each node corresponding to the token value sequence associated with the tokenized record field value comprises replacing a token value in the token value sequence with a substitute token value.