Two step algorithm for non-exact matching of large datasets
A two-step algorithm for conducting near real-time fuzzy searches of a target on one or more large data sets is described. This algorithm includes the simplification of the data by removing grammatical constructs to bring the target search term (and the stored database) to their base elements and then perform a Levenstein comparison to create a subset of the data set that may be a match. Then performing a scoring algorithm while comparing the target to the subset of the data set to identify any matches.
1. A non-transitory machine-readable media programmed to:
search for a subset of records in a list that most closely matches a target, wherein the search comprises software programmed to:
read a record from the list;
perform a search Levenstein distance calculation on the target and the record; and
store the record in a subset list if the search Levenstein distance calculation is greater than a search threshold;
score the records in the subset list, wherein the score comprises software programmed to:
loop through fields of the records in the subset list;
calculate a score Levenstein distance between the field in the record in the subset list and the field in the target;
check that the score Levenstein distance is greater than a field-level threshold, and to go to a next record in the loop if the score Levenstein distance is greater than the field-level threshold;
sum a product of the score Levenstein distance multiplied by a weight factor for the field; and
divide the product by a sum of the weight factor for the fields to derive a weighted mean score for the record;
indicate that the target is located in the list if at least one weighted mean score is calculated.
2. The non-transitory machine-readable media of claim 1 further programmed to:
create the list from one or more source lists with software programmed to:
read an entry from the one or more source lists;
simplify the entry in the one or more source lists;
split the entry into the one or more source lists; and
store the entry in the list as a new record.
3. The non-transitory machine-readable media of claim 2 wherein the software to simplify is programmed to convert all capital letters to lower case.
4. The non-transitory machine-readable media of claim 2 wherein the software to simplify is programmed to remove repeated letters.
5. The non-transitory machine-readable media of claim 2 is further programmed to transform one or more portions of the record to enhance the performance of searches using Levenstein distance calculations, during the creating of the list.
6. The non-transitory machine-readable media of claim 1 is further programmed to simplify the target.
7. The non-transitory machine-readable media of claim 6 wherein the software to simplify the target is programmed to remove punctuation.
8. The non-transitory machine-readable media of claim 6 wherein the software to simplify the target is programmed to consolidate all geographic terms into a selected geographic term.
9. The non-transitory machine-readable media of claim 1 is further programmed to sort the weighted mean score for the records.
10. The non-transitory machine-readable media of claim 1 wherein the software to score is programmed to select the fields configured to boost the weighted mean score for the record, and to incorporate the field score in the weighted mean score for the field configured to boost if the field score increases the weighted mean score.
11. A method comprising:
searching for a subset of records in a list that most closely matches a target, wherein the searching comprises:
performing a search Levenstein distance calculation on the target and a record from the list; and
storing the record in a subset list if the search Levenstein distance calculation is greater than a search threshold;
scoring the records in the subset list, wherein the scoring comprises:
looping through fields of the records in the subset list;
calculating a score Levenstein distance between the field in the record in the subset list and the field in the target;
checking that the score Levenstein distance is greater than a field-level threshold, and going to a next record in the loop if the score Levenstein distance is greater than the field-level threshold;
summing a product of the score Levenstein distance multiplied by a weight factor for the field; and
dividing the product by a sum of the weight factor for the fields to derive a weighted mean score for the record;
indicating that the target is located in the list if at least one weighted mean score is calculated.
12. The method of claim 11 further comprising:
creating the list from one or more source lists, wherein the creating comprises:
reading an entry from the one or more source lists;
simplifying the entry in the one or more source lists;
splitting the entry into the one or more source lists; and
storing the entry in the list as a new record.
13. The method of claim 12 wherein the simplifying includes converting all capital letters to lower case.
14. The method of claim 12 wherein the simplifying includes removing repeated letters.
15. The method of claim 12 further comprising transforming one or more portions of the record to enhance the performance of searches using Levenstein distance calculations, during the creating of the list.
16. The method of claim 11 further comprising simplifying the target.
17. The method of claim 16 wherein the simplifying includes removing punctuation.
18. The method of claim 16 wherein the simplifying includes consolidating all geographic terms into a selected geographic term.
19. The method of claim 11 further comprising sorting the weighted mean score for the records.
20. The method of claim 11 wherein the scoring further comprises selecting fields configured for boosting the weighted mean score for the record, and incorporating the field score in the weighted mean score for the field configured for boosting if the field score increases the weighted mean score.