dedupeio / affinegap Goto Github PK

View Code? Open in Web Editor NEW

58.0 5.0 9.0 73 KB

:triangular_ruler: A Cython implementation of the affine gap string distance

License: MIT License

Python 43.05% Cython 56.95%

string-distance levenshtein-distance python cython

affinegap's Introduction

affinegap

A Cython implementation of the affine gap penalty string distance also known as the Smith–Waterman algorithm

Part of the Dedupe.io cloud service and open source toolset for de-duplicating and finding fuzzy matches in your data.

To install

pip install affinegap

To use

import affinegap
d1 = affinegap.affineGapDistance('foo', 'bar')
d2 = affinegap.affineGapDistance('foo', 'bar',
                                 matchWeight = 1,
                                 mismatchWeight = 11,
                                 gapWeight = 10,
                                 spaceWeight = 7,
                                 abbreviation_scale = .125)
d3 = affinegap.normalizedAffineGapDistance('foo', 'bar')

To get set up for development

git clone https://github.com/dedupeio/affinegap.git
cd affinegap
pip install -r requirements.txt
cython affinegap/*.pyx
python setup.py develop
pytest

Team

Forest Gregg, Dedupeio

Errors and Bugs

If something is not behaving intuitively, it is a bug and should be reported. Report it here by creating an issue: https://github.com/dedupeio/affinegap/issues

Help us fix the problem as quickly as possible by following Mozilla's guidelines for reporting bugs.

Patches and Pull Requests

Your patches are welcome. Here's our suggested workflow:

Fork the project.
Make your feature addition or bug fix.
Send us a pull request with a description of your work. Bonus points for topic branches!

Copyright and Attribution

affinegap's People

Contributors

Stargazers

Watchers

Forkers

krishnasamudrala-tal kball afcarl 1306dish odidev stjordanis net-mist arpitjain799

affinegap's Issues

setup.py install fails, searches for affinegap.c instead of affinegap.pyx

Line 15 in setup.py:
ext_modules=[Extension('affinegap.affinegap', ['affinegap/affinegap.c'])],

There is no affinegap.c file in the affinegap folder.

Can't build with easy_install on windows

https://ci.appveyor.com/project/fgregg/dedupe/build/1.0.185

Always getting this same error:

Downloading https://pypi.python.org/packages/source/a/affinegap/affinegap-1.5.tar.gz#md5=f674711461037be8b6c868ba5132354b
Processing affinegap-1.5.tar.gz
Writing c:\users\appveyor\appdata\local\temp\1\easy_install-80tzbj\affinegap-1.5\setup.cfg
Running affinegap-1.5\setup.py -q bdist_egg --dist-dir c:\users\appveyor\appdata\local\temp\1\easy_install-80tzbj\affinegap-1.5\egg-dist-tmp-xosury
Traceback (most recent call last):
  File "setup.py", line 66, in <module>
    """
  File "C:\Python27_32\lib\distutils\core.py", line 152, in setup
    dist.run_commands()
  File "C:\Python27_32\lib\distutils\dist.py", line 953, in run_commands
    self.run_command(cmd)
  File "C:\Python27_32\lib\distutils\dist.py", line 972, in run_command
    cmd_obj.run()
  File "C:\Python27_32\lib\site-packages\setuptools\command\develop.py", line 32, in run
    self.install_for_development()
  File "C:\Python27_32\lib\site-packages\setuptools\command\develop.py", line 132, in install_for_development
    self.process_distribution(None, self.dist, not self.no_deps)
  File "C:\Python27_32\lib\site-packages\setuptools\command\easy_install.py", line 718, in process_distribution
    [requirement], self.local_index, self.easy_install
  File "C:\Python27_32\lib\site-packages\pkg_resources\__init__.py", line 836, in resolve
    dist = best[req.key] = env.best_match(req, ws, installer)
  File "C:\Python27_32\lib\site-packages\pkg_resources\__init__.py", line 1081, in best_match
    return self.obtain(req, installer)
  File "C:\Python27_32\lib\site-packages\pkg_resources\__init__.py", line 1093, in obtain
    return installer(requirement)
  File "C:\Python27_32\lib\site-packages\setuptools\command\easy_install.py", line 638, in easy_install
    return self.install_item(spec, dist.location, tmpdir, deps)
  File "C:\Python27_32\lib\site-packages\setuptools\command\easy_install.py", line 668, in install_item
    dists = self.install_eggs(spec, download, tmpdir)
  File "C:\Python27_32\lib\site-packages\setuptools\command\easy_install.py", line 851, in install_eggs
    return self.build_and_install(setup_script, setup_base)
  File "C:\Python27_32\lib\site-packages\setuptools\command\easy_install.py", line 1079, in build_and_install
    self.run_setup(setup_script, setup_base, args)
  File "C:\Python27_32\lib\site-packages\setuptools\command\easy_install.py", line 1065, in run_setup
    run_setup(setup_script, args)
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 240, in run_setup
    raise
  File "C:\Python27_32\lib\contextlib.py", line 35, in __exit__
    self.gen.throw(type, value, traceback)
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 193, in setup_context
    yield
  File "C:\Python27_32\lib\contextlib.py", line 35, in __exit__
    self.gen.throw(type, value, traceback)
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 152, in save_modules
    yield saved
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 126, in __exit__
    self._saved = UnpickleableException.dump(type, exc)
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
  File "C:\Python27_32\lib\site-packages\setuptools\sandbox.py", line 110, in dump
    return cls.dump(cls, cls(repr(exc)))
MemoryError
Command exited with code 1

Divide by Zero

The normalized function does not check that both string lengths are greater than zero. For some reason this issue is arising in my dataset despite using has missing.

Is 0.0 appropriate here given that lower values are more similar in normalizedAffineGapDistance?

Add documentation to readtehdocs

Non-zero distance for matching strings using default parameters

Using default parameters, affineGapDistance returns len(string_a) for matching strings, which produces normalizedAffineGapDistance of 0.5.

Is this intended behavior? I scanned through the referenced paper, but didn't see any discussion of this.

Weird Behavior Caused by abbreviation_scale

Hi,

I don't know if this is an issue/bug or is intentional, but here is an example of a weird behavior:

>>> affinegap.affineGapDistance("TED A", "TD A", 
+       matchWeight = 0, spaceWeight = 2, gapWeight = 10, 
+       abbreviation_scale = 0.125)
12.0 # Correct. Open a gap and insert a space for "E".

>>> affinegap.affineGapDistance("TESD A", "TD A", 
+       matchWeight = 0, spaceWeight = 2, gapWeight = 10, 
+       abbreviation_scale = 0.125)
14.0 # Correct. Continue the gap and insert a space for "S".

>>> affinegap.affineGapDistance("TESTD A", "TD A", 
+       matchWeight = 0, spaceWeight = 2, gapWeight = 10, 
+       abbreviation_scale = 0.125)
16.0 # Correct. Continue the gap and insert a space for "T".

>>> affinegap.affineGapDistance("TESTED A", "TD A", 
+       matchWeight = 0, spaceWeight = 2, gapWeight = 10, 
+       abbreviation_scale = 0.125)
16.25 # Weird. 
      # This is because the second "E" is at position 5, which is greater 
      # than the length of the second string. 
      # So the score for the additional space for "E" is scaled.

I believe it is triggered by

affinegap/affinegap/affinegap.pyx

Line 79 in 853f3d3

if j <= length2 :

by accident.

It would be great if you could take a look. Thanks.

Add support to release aarch64 wheels

Problem

On aarch64, pip install affinegap builds the wheels from source code and then install it. It requires user to have development environment installed on his system. also, it take some time to build the wheels than downloading and extracting the wheels from pypi.

Resolution

On aarch64, pip install affinegap should download the wheels from pypi

@fgregg, Please let me know your interest on releasing aarch64 wheels. I can help in this.

normalizedAffineGapDistance returns wrong value when parameters are Japanese(UTF-8 string)

I try to normalized affine gap for japanese strings such a "日本"

I make a script to test.
Then affinegap.normalizedAffineGapDistance("日本", "日本") returns 0.166666671634 which is wrong, should be 0.5.

import affinegap
import sys

args = sys.argv
word1 = args[1]
word2 = args[2]

#print word1
#print word2

normalizer = len(word1.decode("utf8")) + len(word2.decode("utf8"))

print "normalizer by utf8 decode"
print normalizer

print "normalizer of byte length"
print len(word1) + len(word2)


d = affinegap.affineGapDistance(word1, word2)
print "affine gap"
print d


print "expected normalized value"
print d/normalizer

nd = affinegap.normalizedAffineGapDistance(word1, word2)
print "normalized value"
print nd

# python affine_gap_test.py "日本" "日本"
normalizer by utf8 decode
4
affine gap
2.0
expected normalized value
0.5
normalized value
0.166666671634

I think, it causes a definition of normalizer.

https://github.com/dedupeio/affinegap/blob/master/affinegap/affinegap.pyx#L122 and L123 shoud be change to

cdef int length1 = len(_ustring(string1))
 cdef int length2 = len(_ustring(string2))

Or, affineGapDistance use byte length of input parameter instead of unicode length.

Matching strings return non-zero distances

Using the default value for the matchWeight parameter, the affineGapDistance function returns len(string_a) as the distance between two strings that match exactly, and normalizedAffineGapDistance returns 0.5.

Is this intended behavior? I looked through the referenced paper, but did not see any discussion of this.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.