Implementation of edit distance calculation.
Project description
Fast calculation of Edit Distance (ED)
A implementation of edit distance with improved runtime. Implemented using C and cython.
Highlight:
This edit distance calculation is significantly faster than most of existing python package. It enables a max edit distance search, specifically, if you have a query sequence and wanted to find the most similar item in a long list, you could set a maximum edit distance and enable a fast search.
Installation:
Install using pip:
pip install fast-edit-distance
or build from source
git clone https://github.com/youyupei/fast_edit_distance.git
cd fast_edit_distance
python3 setup.py build
python3 setup.py install --user
Usage:
from fast_edit_distance import edit_distance
# example
edit_distance(string1, string2, max_ed=5)
Compare with Levenshtein.distance
The fast_edit_distance.edit_distance
has the same function as Levenshtein.distance with significantly improved runtime. Especially when people need to identied pair of strings whose ED are smaller than a number (set max_ed
in fast_edit_distance.edit_distance). Here is the runtime test with some random sequence (Run the test/test.py to reproduce this comparison):
Runtime test no max ed cutoff(1_000_000 iteration):
Levenshtein.distance: 46.49s
fast_edit_distance.edit_distance: 12.75s
Runtime test with max ed cutoff 1 (1_000_000 iteration):
Levenshtein.distance: 46.45s
fast_edit_distance.edit_distance: 0.50s
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.
Source Distributions
Built Distributions
Hashes for fast_edit_distance-1.2.1-pp310-pypy310_pp73-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9889310e056dd9ef2e7b1bad93ba4027fff6b932c6690b6c39b0cdfeace901f1 |
|
MD5 | 29917494e162b34a989740b1a4b7e41e |
|
BLAKE2b-256 | 8fa785d6eaa29fddd141214ef4e7b41f55cc96411e3b0b07047e2075dd656511 |
Hashes for fast_edit_distance-1.2.1-pp310-pypy310_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0c28d4473436853f67129f3bdcae97b3cf7419bb4b5cb32b4677a5a47b340334 |
|
MD5 | e6b6f6e6a69321a847a2ea9deb44cba3 |
|
BLAKE2b-256 | a206646c73be7eec2f4e5093fc10ecb90fb63fe3e7e0b12fca46724361bf2956 |
Hashes for fast_edit_distance-1.2.1-pp39-pypy39_pp73-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 79c7f6330b0892e2c152fa840be9e6ed8ce4d9a5d271a8db4da396eb5db03206 |
|
MD5 | 7b4a96348836794cec6b77a138756a1e |
|
BLAKE2b-256 | 4fb8364ee0abd4b05624f8640fa0950e38ef193025db439bdf1b658f6fbdefa4 |
Hashes for fast_edit_distance-1.2.1-pp39-pypy39_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1e5bdf1165a6703edad6194a863ec832b7e99b9e575a4abb9e0244f1bf9bec05 |
|
MD5 | 0dff5dba867a28008022f7caf97db078 |
|
BLAKE2b-256 | 6e102946c0377b0e5aaf4735e2e2924c2daa1adb12f0c239ceb95630acee6887 |
Hashes for fast_edit_distance-1.2.1-pp38-pypy38_pp73-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ff5f431090e0b0dbfd7b0b55572785f637ae8fbd7ef7ec3731fc79ac639bf15 |
|
MD5 | fea6cf5de96f2ad66e88b6d8df786579 |
|
BLAKE2b-256 | 58c85c02c8cad88ef7a7958e9194b7ba83fe5103407c44e7eca2b8eaff68e662 |
Hashes for fast_edit_distance-1.2.1-pp38-pypy38_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3eac42b561be94173bf91da20f1d44de717fb3be95e0c13c7d70fb59090e4a28 |
|
MD5 | 64ecc1e1df5c1b5f346fa34788fb4356 |
|
BLAKE2b-256 | a28b3fb0b2a17d56821c5421b047a6404f9d6e25afaa8a47468083147af246b9 |
Hashes for fast_edit_distance-1.2.1-pp37-pypy37_pp73-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | df15701fc963df4e73ccfce85205ef1166a07aade0f4afc0744ca7d5455e173a |
|
MD5 | 5a06d3e3ef0c11cfb782dba3a6af84ce |
|
BLAKE2b-256 | dd9acff6a968d33cfe59963e6c05c9f4f381d44d06309e8923a6112e7442f17a |
Hashes for fast_edit_distance-1.2.1-pp37-pypy37_pp73-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fb339736f05e095ca876c8f2579250aeca312a295d7c7438d34eaf3279693083 |
|
MD5 | 5e3a9dc32ddfc6a54ab206810346470f |
|
BLAKE2b-256 | 1ba145c450a81d2e9190158783bc4c25f69d6746a3d27b9f32dbc844a0c0d8de |
Hashes for fast_edit_distance-1.2.1-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7966af65ab12bf939c4a4e2c0259c9a20572de99973bc6d18f336cc26ae2f39d |
|
MD5 | 1fc7fc34a4a2034a951d4055dfb1098b |
|
BLAKE2b-256 | ed320ce6ea61e1d1286b5d6c06c00a44de12df10f82de3b3aa1e6f96ed7274f6 |
Hashes for fast_edit_distance-1.2.1-cp312-cp312-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | decb8a55732ff5e60d3eb55fa39e763ae494695ad956a510341ea2b41f3e1c8a |
|
MD5 | 17666c7f75cfbb34965fdea7747cca38 |
|
BLAKE2b-256 | 9a10c4d8da6de26da0c4b61f4aad081b6887c2c617328c2a1b7e7ee45a081c9d |
Hashes for fast_edit_distance-1.2.1-cp312-cp312-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7118c598637f4989ffb33dcb693824ae71079ae82cd59bd5a43a9926b734a350 |
|
MD5 | 0deb418d2b974b3e773c8890120c530a |
|
BLAKE2b-256 | 6de48d1dd53cad92d426e378e26acc392e4f3426e383890ece073c347da52bd0 |
Hashes for fast_edit_distance-1.2.1-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0bb00ef9ffa03650f387acd541919eec9bb73238d2d46facc57d1b00014ce898 |
|
MD5 | d70f2b43632203db27142b8a761266eb |
|
BLAKE2b-256 | 8460a41dcecf2ca5b615262765a649371dc1875f996f0897acf877cd6ac20f9d |
Hashes for fast_edit_distance-1.2.1-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 10754fe372f96180f88cdb13493ea70e2efad8adb4b41517b57fc9529633a671 |
|
MD5 | 6dbf3bcea98d019f7bdb33d0454801d5 |
|
BLAKE2b-256 | 2dafe815fbfb3292b14d8a457cdb6f859630f652879726b2c4b9258368733ff9 |
Hashes for fast_edit_distance-1.2.1-cp311-cp311-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 86c5d1c697deeaed16590eff5680f6878c427715e0ee021464ae11f6ac37a2e7 |
|
MD5 | b8a0102f029d704675f08d1e8103206b |
|
BLAKE2b-256 | 83f67c93d201a44172fe940a3ef86e53eb84af7ac70828883be5e966aee64f5b |
Hashes for fast_edit_distance-1.2.1-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7640278fc00386bb97495cdf5dd1fb2a82f6c153730af0d3fd65aef4682c9304 |
|
MD5 | 9d48449a80bfa2ad50a8f08230c41e23 |
|
BLAKE2b-256 | 291b3eb2dfbb319706d8b112de53167a10cc28b3012817eb8affd39bd29d51eb |
Hashes for fast_edit_distance-1.2.1-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 35ec59b86b6af015be77ab9e27c9e1c6047ef09dd61bfd38d0bfb0b0922e5fb1 |
|
MD5 | 0a1f0c6bfed46689d88383474fb87794 |
|
BLAKE2b-256 | e5f25fdeb0fc24c4acf3abeed1accf34974d7f5964b9136643124c90a56adfcc |
Hashes for fast_edit_distance-1.2.1-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 226ee940e1a127b9a3ff73e9b7daaa087ec7e3c493d80de7568021f1cda17c59 |
|
MD5 | 2e51f3058824deb60389c019a794232b |
|
BLAKE2b-256 | 9f3e0b32007220f3c26bc955750d1943057e402513d5b3c87c230706aceeb2f4 |
Hashes for fast_edit_distance-1.2.1-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 910d72583e0d76c728bdb6fc81a370ac36c52075faaa55d627de75ccb19e2a9e |
|
MD5 | 87c576eba701e19d3ce547548b6b4f26 |
|
BLAKE2b-256 | 73b151dc9e70723c51007ffcce0de2a676dee1d277cafa10adc6053815463b7d |
Hashes for fast_edit_distance-1.2.1-cp310-cp310-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3379a70ae1a8ece470f38a4a28f4293f517d224a04a1610fdb0c208f2bcb38db |
|
MD5 | f1f61de8a00859a090ec4b68573c6d96 |
|
BLAKE2b-256 | 270e08471ffa3b543da2b224d456f4a65d9188274263b508eda1817877fc971f |
Hashes for fast_edit_distance-1.2.1-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6147ad4447f1322873566580059b8455b1d02de84124ec94891a40f84a03193d |
|
MD5 | c5023159b330cb28042dcaae3c6b79ed |
|
BLAKE2b-256 | dca7175b962f9f57b1316b133f49276a6b73b0c8250e730501630561d5a4b116 |
Hashes for fast_edit_distance-1.2.1-cp310-cp310-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8ab1921aecd2776c6c54b5bb155647a07925a71a0f828cb7a5c7c695f03e393 |
|
MD5 | 90001b9cc0a1ebc494fdb8abf797c4d5 |
|
BLAKE2b-256 | add571fec3953765a46f610c36178f564d3867b2ce9f54feec34d61e89af159f |
Hashes for fast_edit_distance-1.2.1-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 720707c6ec3afd8cf82263f90a53e492b7f794b57540a1e5946d98f2a6e7ab0a |
|
MD5 | 6690b8da94826277a1cb22594e0d76ce |
|
BLAKE2b-256 | 445c56a19b9e4a74af80ab97ff93987c8346c4e741569f44727f1f6497292f9c |
Hashes for fast_edit_distance-1.2.1-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4a381915fcc3cb7b2e649f04881f3d66a0b2e222f1cc60997ca1e8b0f711e25e |
|
MD5 | e52c415a3a5724857d577174a2c2d6fd |
|
BLAKE2b-256 | cb2ca38e476866a29c9e847204af43a935b93a1c65efa1f28af39cb2e1fbd2ad |
Hashes for fast_edit_distance-1.2.1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a6331927738b13a19083f87b01044c17035a768528800041ce6ac6e5a32c4272 |
|
MD5 | b00d5544948f90ca22cab3b8818b146c |
|
BLAKE2b-256 | 08e07d718f1e813a4b257dc555978a080cc9e69e1bb14475ee6fc1650651ac10 |
Hashes for fast_edit_distance-1.2.1-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4b763c41d341513560b850223715e4452ade081d572e8a588abd92ba65d45ca6 |
|
MD5 | 33879689aa76b7ac81f9cac148d4633c |
|
BLAKE2b-256 | faa8d91ca78c86bb86630736c7d0ef3d496af777fe52227f1fb2280d36af7337 |
Hashes for fast_edit_distance-1.2.1-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce48f373c9a05c12651e8d84a7b1697dbb6de4af93a0dd7ae12a2016c7e3877d |
|
MD5 | 0effb15e15b14f6215f9f672e82dbebe |
|
BLAKE2b-256 | fd972b190303c56f444a3703456aff8951bfd5a425335e9034fd87b24bc2cc9d |
Hashes for fast_edit_distance-1.2.1-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5a7be667ff0b6038e03a6d736ff0c2d369a904d47b1f2589d581a6f24fef90f |
|
MD5 | 722c5f4018ce4d434fda00f7d52d15c3 |
|
BLAKE2b-256 | f3e654b7b4db39e506bb33ab7f4058ff4c983e98856f36ba16ccca3257ad5fab |
Hashes for fast_edit_distance-1.2.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1d8f9f5d85a4d19237610fc10da348841bd0de44b670203d0ff6468eda41c5b6 |
|
MD5 | a990a1058d014ed759b1036171464279 |
|
BLAKE2b-256 | 15fda49d30ebe3e7ac65ae1776516cda72cfb7ea28f7a4604fe3d241fe9d6b9c |
Hashes for fast_edit_distance-1.2.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c5600cb1030dea3b85d99d648fac1dd37f1c5774f89c1828ac2816bb5cc7b76d |
|
MD5 | c1b7658603aa7d332b85844a9c1d3e34 |
|
BLAKE2b-256 | 6253562323e96485910fc20b5663e2cfd8f88b5c9f505eb27a012116c87ce7a3 |
Hashes for fast_edit_distance-1.2.1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b1054505aeacc20d726ae5edfc6c458d877e330d2394cf13c732e6661490d604 |
|
MD5 | aac7330628941bbf570a9b0c7da658ff |
|
BLAKE2b-256 | 34894ac8b113f6b5fe2e11ec6ddaf55e4275174f53cbdead3d2727768a4d60c3 |
Hashes for fast_edit_distance-1.2.1-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f7eb6e50f010da6e1ae2ed1d245bc93e6b2b85583321ab030d2bf0c0d2582640 |
|
MD5 | 87542e4d52f47ae14965ab4eaf82588f |
|
BLAKE2b-256 | e2c67f0a78e856b782e6c427c51c4fa87c473a291ff758356c02635918b1ba2c |
Hashes for fast_edit_distance-1.2.1-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1de147412cd6de422081683a41059e3d3bd3b26fed6fb58b53624fa742b5cbd5 |
|
MD5 | 179264d285e866e203d17bd8e8f1ace3 |
|
BLAKE2b-256 | 5c65e38b3c1fd2e1fc15cb186733651a075e56a3e80093ae18664606ea74e03f |
Hashes for fast_edit_distance-1.2.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f80f18da24165be1f31f42a58609f63871009f1002867dbcc7ecc5d8ef8eec42 |
|
MD5 | a5d160a7849632c3463ba10ec8d16408 |
|
BLAKE2b-256 | b81c491fdfa516311f1057b37b20bf86ddbc616848aa08c73ea8ac88008b789c |
Hashes for fast_edit_distance-1.2.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bf8e47fe91e839fac1c31a13a9cdd333980f4580f33cc338273e12dbdaf87c77 |
|
MD5 | cc79e5badf1ca6686fbd0d9f40599b6d |
|
BLAKE2b-256 | 82bc7dd65eac95e41f778865108e0a95e5c3dea74f64dd054c725cf62b0a3215 |
Hashes for fast_edit_distance-1.2.1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c88aa52b9f30cc9a5069102e8db7c571074495b08bc466d5f7327f395ebcdfd2 |
|
MD5 | 37d1ce1b1a447ac9880b8e6e7f37f149 |
|
BLAKE2b-256 | 1ea51e0dde7751fa30e199d190715884036c3faa3dd0de73f2008c2577437555 |
Hashes for fast_edit_distance-1.2.1-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 337e51bfd0ec2f796101c5aa5922bd593069944ed30099a5e0ef6e2d293f32d5 |
|
MD5 | 687d4bbfaf06cb0d4d85386f10b469bd |
|
BLAKE2b-256 | 1f1c17d65d25495d1f5fb9dcb3f6cc44e165116637d9b672397bff16f7749f8f |
Hashes for fast_edit_distance-1.2.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 63484aedfc3bfe727e01dc46c3f56bdf20fae2df41bcfb38381d894cf67bbc80 |
|
MD5 | b654116e62e2d86b6c46725dc849d30a |
|
BLAKE2b-256 | a17b9aa77bfb705d7dad19946e53a2f03f95b7e2f72f571c78e4f6a2dfa89c68 |
Hashes for fast_edit_distance-1.2.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eb57910fdf448576d47c8daa480aa70196c4d54f02876a3e9a32abc65f0d3a5e |
|
MD5 | ec56f31dab2b326abb256db4fc0e76ef |
|
BLAKE2b-256 | b874df7c09247b5bce0a32c2472bcfad9e89d8a92f4f37e6c1e02458969bd2dd |
Hashes for fast_edit_distance-1.2.1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a7cb80d29a5bd1551f58a5b6f01ca387f6b0c51df7c5b6755db5c7ab30c46ec5 |
|
MD5 | 4f33659fe8880cafa540fb99314b7e4d |
|
BLAKE2b-256 | 97d5e684ba6fafc329cdb3cbdfe19d97bb8ac333dd097dd546a19d780ea92e4f |
Hashes for fast_edit_distance-1.2.1-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 91c275d5ea07f3e3ef9e274b90f4709c38a8bb2f68e934d8b8f344a5909ddcba |
|
MD5 | 6e87a554c730724bf351a534358193e5 |
|
BLAKE2b-256 | 97e62df6e645cbaafe52969114c3f21a73c19c357b99d192ae35d8d38cc7ce47 |
Hashes for fast_edit_distance-1.2.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83883826f4e3677fe5cf2eeda1390b59ecc68370987be71a303904fb6d429b3b |
|
MD5 | 84de5978d0be85c361fe07615cb7d275 |
|
BLAKE2b-256 | 7e079cfcc94250a0aeb543dca87303efa2c02d4d0a30ba9a2fcf8609d4580298 |