README.md in lycopodium-0.0.2 vs README.md in lycopodium-0.0.3
- old
+ new
@@ -1,34 +1,74 @@
# Lycopodium Finds Fingerprints
-[](http://travis-ci.org/opennorth/lycopodium)
-[](https://gemnasium.com/opennorth/lycopodium)
-[](https://coveralls.io/r/opennorth/lycopodium)
-[](https://codeclimate.com/github/opennorth/lycopodium)
+[](https://badge.fury.io/rb/lycopodium)
+[](https://travis-ci.org/jpmckinney/lycopodium)
+[](https://gemnasium.com/jpmckinney/lycopodium)
+[](https://coveralls.io/r/jpmckinney/lycopodium)
+[](https://codeclimate.com/github/jpmckinney/lycopodium)
-Test what transformations you can make to a set of values without creating collisions.
+Lycopodium does two things:
-> Historically, Lycopodium powder, the spores of Lycopodium and related plants, was used as a fingerprint powder. – [Wikipedia](http://en.wikipedia.org/wiki/Fingerprint_powder#Composition)
+1. Test what transformations you can make to a set of values without creating collisions.
+1. Find [unique key](http://en.wikipedia.org/wiki/Unique_key) constraints in a data table.
+> Historically, Lycopodium powder, the spores of Lycopodium and related plants, was used as a fingerprint powder. – [Wikipedia](https://en.wikipedia.org/wiki/Fingerprint_powder#Composition)
+
+## 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](https://www.ic.gc.ca/app/scr/cc/CorporationsCanada/fdrlCrpSrch.html?locale=en_CA). 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](http://openrefine.org/) offers [two methods to solve this problem](https://github.com/OpenRefine/OpenRefine/wiki/Clustering-In-Depth):
+
+* 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](https://en.wikipedia.org/wiki/Levenshtein_distance) and [Prediction by Partial Matching](https://en.wikipedia.org/wiki/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](http://app.toronto.ca/tmmis/getAdminReport.do?function=prepareMemberVoteReport). 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](http://en.wikipedia.org/wiki/Unique_key). Lycopodium does this.
+
## Usage
```ruby
require 'lycopodium'
```
-First, write a method that transforms a value, for example:
+### Find a unique key in a data table
```ruby
+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:
+
+```ruby
meth1 = ->(string) do
string.gsub(/\p{Space}/, '')
end
```
-Then, initialize a `Lycopodium` instance with a set of values and the transformation method:
+Then, initialize a `Lycopodium` instance with a set of values and the method:
```ruby
-set = Lycopodium.new(["foo", "f o o"], meth1)
+set = Lycopodium.new(["foo", "f o o", " bar "], meth1)
```
Lastly, test whether the method creates collisions between the members of the set:
```ruby
@@ -45,26 +85,52 @@
meth2 = ->(string) do
string.upcase
end
```
-It will return the mapping from original to transformed string:
+It will return the mapping from original to transformed string (hence `value_to_fingerprint`):
- {"foo" => "FOO", "f o o" => "F O O"}
+```ruby
+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.
-To remove all members of the set that collide after transformation, run:
+If you can't find a suitable method, you can remove all values that collide after transformation:
```ruby
+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.
-## Method definition
+### Use the key collision method
+You can now apply the method to other values…
+
+```ruby
+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:
```ruby
meth = lambda do |string|
string.gsub(/\p{Space}/, '')
@@ -94,10 +160,12 @@
string.gsub(/\p{Space}/, '')
end
meth = Object.method(:func)
```
-## Bugs? Questions?
+## Related projects
-This project's main repository is on GitHub: [http://github.com/opennorth/lycopodium](http://github.com/opennorth/lycopodium), where your contributions, forks, bug reports, feature requests, and feedback are greatly welcomed.
+* [Nomenklatura](http://nomenklatura.okfnlabs.org/) 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](https://github.com/open-city/dedupe) is a Python library to determine when two records are about the same thing.
+* [name-cleaver](https://github.com/sunlightlabs/name-cleaver) is a Python library to parse and standardize the names of people and organizations.
-Copyright (c) 2013 Open North Inc., released under the MIT license
+Copyright (c) 2013 James McKinney, released under the MIT license