A `set` subclass providing fuzzy search based on N-grams.
Project description
The NGram class extends the Python ‘set’ class with efficient fuzzy search for members by means of an N-gram similarity measure. It also has static methods to compare a pair of strings.
The N-grams are character based not word-based, and the class does not implement a language model, merely searching for members by string similarity.
The documentation and tutorial are on the PyPI package documentation site.
Installation
Install python-ngram from PyPI using pip installer:
pip install ngram
It should run on Python 2.6, Python 2.7 and Python 3.2
How does it work?
The set stores arbitrary items, but for non-string items a key function (such as str) must be specified to provide a string represenation. The key function can also be used to normalise string items (e.g. lower-casing) prior to N-gram indexing.
To index a string it pads the string with a specified dummy character, then splits it into overlapping substrings of N (default N=3) characters in length and associates each N-gram to the items that use it.
To find items similar to a query string, it splits the query into N-grams, collects all items sharing at least one N-gram with the query, and ranks the items by score based on the ratio of shared to unshared N-grams between strings.
History
In 2007, Michel Albert (exhuma) wrote the python-ngram module based on Perl’s String::Trigram module by Tarek Ahmed, and committed the code for 2.0.0b2 to a now-disused Sourceforge subversion repo.
Since late 2008, Graham Poulter has maintained python-ngram, initially refactoring it to build on the set class, and also adding features, documentation, tests, performance improvements and Python 3 support.
Primary development takes place on GitHub, but changes are also pushed to the earlier repo on Google Code.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.