A tool for quickly locating the most likely match for a name (or other short natural language string) in another (very large) set of names.
Entries for the tool are in the form (Name, UID) where the unique identifier is
of any arbitrary data type that satisfies both Hashable and Eq,
so there's no extra matching to be done afterwards to recover results; the
results are returned with both the matching name and the matching name's UID.
Use case for which it was developed: You need to match records across two data sets using only names, but have too many records to reasonably perform string distance calculations between every pair in the cartesian set. QuickSearch only performs distance calculations between strings that share an entire token, making it well suited to quickly remove the low-hanging fruit. This in turn drastically reduces the sizes of the sets requiring a costly full scan, allowing for more iteration and experimentation on the edge cases.
Able to process thousands of names against a population of a hundred thousand names in under a second (once the QuickSearch is actually built... first search always takes several seconds to build the filters).
Uses Data.Text internally, but there is an identical String interface
to be found at QuickSearch.String if that suits the pipeline better (but you
should probably be using Data.Text, String is much slower).
Usage:
> import QuickSearch
> names = map T.pack ["Rep. Meg Mueller","Twana Jacobs","Sammie Paucek"]
> targets = zip names [1..] --Stand-in for your UIDs
> qs = buildQuickSearch targets
-- Exposes jaro, jaroWinkler, and damerauLevenshteinNorm from Data.Text.Metrics
-- but scorer can be any func of type (T.Text -> T.Text -> Ratio Int)
> entry = T.pack "Rep. Meg Muller"
> topNMatches qs 1 jaroWinkler entry
[Match (100,Entry ("rep. meg mueller", 1))]
> entry = T.pack "Towana Jacobs"
> matchesWithThreshold qs 90 damerauLevenshteinNorm entry
[Match (92,Entry ("twana jacobs", 2))]Both topNMatches and matchesWithThreshold have an associated batch function
for processing entire lists at once, named batchTopNMatches and
batchMatchesWithThreshold. These take lists of pairs of names and UIDs
instead of a target string, and return for each entry the results of running
the associated single function.
Both are built using a helper function batch, so the definition of
batchTopNMatches is batchTopNMatches = batch topNMatches. If you define
your own retrieval functions on a single entry, you can in turn define your
own batch version in the same way.
If you have your list of names to be matched and list of target names both
in the form [(T.Text, uid)] (or [(String, uid)]) and you don't plan
on re-using the QuickSearch filters, you can run it as a one-shot batch with
import QuickSearch.OneShot
-- or, import QuickSearch.String.OneShot
names, targets :: (Hashable uid, Eq uid) => [(T.Text, uid)]
scorer :: (T.Text -> T.Text -> Ratio Int)
> oneShotTopNMatches 5 names targets scorerwhich will return a list of (Entry uid1, Match (Entry uid2))
topNMatches and matchesWithThreshold have one-shot batch versions, named
oneShotTopNMatches and oneShotMatchesWithThreshold respectively. Like the
batch versions, they are built with a helper, oneShot, so you're free to
make your own One-Shot retrieval functions by defining it for a single item
and decorating it.
Shout out to Charles Sommers, who wrote the Python tool I'm reimplementing the idea of.
unstableNub used in QuickSearch.Filter borrowed from Universum.Nub
and modified slightly under the MIT license.