spike: string matching algorithms

[adamdecaf]

OFAC searches are inherently messy and complicated because they interact with people's real names and/or aliases. This means there isn't a "one-size" algorithm we could apply and instead need to offer our customers with lots of options.

In short, our search endpoint(s) should be able to reflect multiple string comparison algorithms:

POST /v1/ofac/search/name?algos=levenstein,exact
[
 {
   // ...
 }
]

We should also support no algos parameter (or a value of all) to run all string comparison algorithms. All searches run across aliases and real names from the OFAC list.

The initial list of algorithms could include:

• case-insensitive and trimmed exact match
• Levenstein
• Jaro
• Jaro-Winkler
• Hamming Distance
• Soundex
• Ukkonen
• Wagner-Fischer

With many other possible algorithms,

• https://www.rosette.com/blog/overview-fuzzy-name-matching-techniques/

I think the result body for an algorithm should be:

{
  "algorithm": "hamming",
  "score": 0.95
}

• algorithm: lowercase enumeration of all algorithms.
• score: Is a normalized 0-1 percent of string match. (i.e. 0.95 -> 95% match)

[adamdecaf]

FYI, we should look at how ES does Soundex and if we're normalizing the result similar to them.

https://www.elastic.co/guide/en/elasticsearch/guide/current/phonetic-matching.html (Should also check 6.x)

[adamdecaf]

Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English.

(From: https://en.wikipedia.org/wiki/Soundex)

We will likely need to find non-english alternatives to use alongside.

Edit: From the paper directly below:

The Soundex and Metaphone algorithms are highly susceptible to missing matches where a name pair starts with a different letter (e.g. KAVANAGH, CAVANAGH and HAVANAH). This is especially true with names beginning with vowels - where typically many equivalents exist (e.g. EWELL, ULE, YOUL, WHEWELL, HEWEL), which should result in matches being reported.

[adamdecaf]

From https://waset.org/publications/8664/a-comparison-and-analysis-of-name-matching-algorithms-

Looks like the order of most accurate in that graph:

1. NYSIIS
2. Phonex
3. LIG2

I've also found some sample implementations:

• https://github.com/tdebatty/java-string-similarity/tree/master/src/main/java/info/debatty/java/stringsimilarity
• https://github.com/rockymadden/stringmetric/tree/master/core/src/main/scala/com/rockymadden/stringmetric/phonetic

[adamdecaf]

FYI, if we need to come back to this I think we should write custom ES scorers with specific string compare algorithms.