Here i am basically looking for performance improvement.
I need to match names in a SWIFT message (Let's say MT 103) against sanctions lists (sanctions lists by UN, by OFAC, some custom lists) and below is what i have developed
- Since there are various lists and total number of names are more than 50 thousand so i load all the names in a list instead of fetching them again and again from database
- Then i loop through the list and use Levenshtein distance, because there could be spelling mistakes, to find the difference between two names(one name from database and name in the SWIFT message) and store their differences
- Then i pick the top 10,50 or 100 names with least differences.
Since name fields in SWIFT messages are free-formatted four lines with 35 characters each and there is no rule to have a delimiter so you will find name, address and contact numbers mixed up together. For example the Remitter name would be like
ABCXYZ INTERNATIONAL PLASTIC INDUST RIES PVT LTD 49-A, S.I.E A JOHANNES BURG SOUTH AFRICA
Charles Philip Arthur George Mountb atten-Windsor Buckingham Palace Wes tminster London
Since there is no way to separate name with the address so i decided to create names from parts of these lines. For example
ABCXYZ ABCXYZ INTERNATIONAL ABCXYZ INTERNATIONAL PLASTIC ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT LTD ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT LTD 49-A, ABCXYZ INTERNATIONAL PLASTIC INDUSTRIES PVT LTD 49-A, S.I.E ... INTERNATIONAL INTERNATIONAL PLASTIC INTERNATIONAL PLASTIC INDUSTRIES ... PLASTIC PLASTIC INDUSTRIES PLASTIC INDUSTRIES PVT PLASTIC INDUSTRIES PVT LTD ...
Charles Charles Philip Charles Philip Arthur ... George George Mountbatten-Windsor George Mountbatten-Windsor Buckingham ... Buckingham Buckingham Palace Buckingham Palace Westminster Buckingham Palace Westminster London ... Westminster Westminster London London
The case would be similar with Beneficiary name. Sometimes the number of these combinations exceeds 200 and so comparing these 200 names with 50 thousand names of sanctions lists is quite expensive.
Here i need to improve the performance by identifying the name from these 4 lines somehow or extract candidate names from these combinations to shorten the list of names to be matched or extract candidate names from sanctions lists, etc
I am already using
Parallel.ForEach which consumes 100% CPU which is not a feasible solution.
I need suggestions to improve the performance of this solution or a better solution.
Edit # 1
I used Fast approximate string matching with large edit distances in Big Data (2015) by Wolf Garbe and below is the result
Sanctioned names: 48, 290 Names screened: 360 Total time by Existing* Levenshtein: 468,575 ms (7.809 min) Total time by Wolf Garbe Levenshtein: 177,862 ms (2.964 min)
Both these algos calculated the same distances for 57,961 varying name matchings. * Don't remember the source of this implementation.