Lycopodium Finds Fingerprints

Lycopodium does two things:

1. Test what transformations you can make to a set of values without creating collisions.
2. Find unique key constraints in a data table.

Historically, Lycopodium powder, the spores of Lycopodium and related plants, was used as a fingerprint powder. – Wikipedia

What it tries to solve

Find a key collision method

Let's say you have an authoritative list of names: for example, a list of organization names from a company register. You want to match a messy list of names – for example, a list of government contractors published by a city – against this authoritative list.

For context, Open Refine offers two methods to solve this problem:

• Key collision methods group names that transform into the same fingerprint; transformations include lowercasing letters, removing whitespace and punctuation, sorting words, etc.

• Nearest neighbor methods group names that are close to each other, using distance functions like Levenshtein distance and Prediction by Partial Matching.

Key collision methods tend to be fast and strict, whereas nearest neighbor methods are more likely to produce false positives, especially when dealing with short strings.

If you want fast and strict reconciliation, Lycopodium lets you figure out what transformations can be applied to an authoritative list of names without creating collisions between names. Those transformations can then be safely applied to the names on the messy list to match against the authoritative list.

Find a unique key in a data table

Let's say you have a data table: for example, the City of Toronto publishes voting records grouped by city councillor. You want to instead group the voting records by motion being voted on. However, the data table doesn't contain one, single column identifing the motion. You instead need to identify the combination of columns that identify the motion. In other words, you are looking for the data table's unique key. Lycopodium does this.

Usage

require 'lycopodium'

Find a unique key in a data table

table = [
  ['foo', 'bar', 'baz'],
  ['foo', 'bar', 'bzz'],
  ['foo', 'zzz', 'bzz'],
]
Lycopodium.unique_key(table)
# => [1, 2]

The values of the second and third columns – taken together - are unique for each row in the table. In other words, you can uniquely identify a row by taking the values of its second and third columns.

Find a key collision method

Write a method that transforms a value, for example:

meth1 = ->(string) do
  string.gsub(/\p{Space}/, '')
end

Then, initialize a Lycopodium instance with a set of values and the method:

set = Lycopodium.new(["foo", "f o o", " bar "], meth1)

Lastly, test whether the method creates collisions between the members of the set:

set.value_to_fingerprint

In this example, an exception will be raised, because the method creates collisions:

Lycopodium::Collision: "foo", "f o o" => "foo"

With another method that, for example, uppercases a string and creates no collisions:

meth2 = ->(string) do
  string.upcase
end

It will return the mapping from original to transformed string (hence value_to_fingerprint):

set.function = meth2
set.value_to_fingerprint
# => {"foo"=>"FOO", "f o o"=>"F O O", "bar"=>" BAR "}

We thus learn that whitespace disambiguates between members of the set, but letter case does not.

If you can't find a suitable method, you can remove all values that collide after transformation:

set.function = meth1
set_without_collisions = set.reject_collisions
# => [" bar "]
set_without_collisions.value_to_fingerprint
# => {" bar "=>"bar"}

A Lycopodium instance otherwise behaves as an array.

Use the key collision method

You can now apply the method to other values…

messy = "\tbar\n"
fingerprint = meth1.call(messy)
# => "bar"

… and match against your original values:

fingerprint_to_value = set_without_collisions.value_to_fingerprint.invert
fingerprint_to_value.fetch(fingerprint)
# => " bar "

Method definition

Besides the -> syntax above, you can define the same method as:

meth = lambda do |string|
  string.gsub(/\p{Space}/, '')
end

Or:

meth = proc do |string|
  string.gsub(/\p{Space}/, '')
end

Or:

meth = Proc.new do |string|
  string.gsub(/\p{Space}/, '')
end

Or even:

def func(string)
  string.gsub(/\p{Space}/, '')
end
meth = Object.method(:func)

Related projects

• Nomenklatura is a web service to maintain a canonical list of entities and to match messy input against it, either via the user interface or via Open Refine reconciliation.
• dedupe is a Python library to determine when two records are about the same thing.
• name-cleaver is a Python library to parse and standardize the names of people and organizations.

Copyright (c) 2013 James McKinney, released under the MIT license