editdistance

编辑距离（Levenshtein距离）的快速实现。

这个库使用C++和Cython简单地实现了Levenshtein距离。

本库使用的算法源自Heikki Hyyrö的"Explaining and extending the bit-parallel approximate string matching algorithm of Myers"（2001）

二进制轮子

感谢pypa/cibuildwheel 在Linux、Mac OS和Windows上提供了二进制轮子。

安装

你可以通过pip安装：

pip install editdistance

使用

使用非常简单：

import editdistance
editdistance.eval('banana', 'bahama')
# 2L

简单性能测试

使用IPython，我尝试了几个库：

在Python 2.7.5上：

a = 'fsffvfdsbbdfvvdavavavavavava'
b = 'fvdaabavvvvvadvdvavavadfsfsdafvvav'
import pylev
timeit pylev.levenshtein(a, b)
# 100次循环，3次中最佳：每循环7.48毫秒

from pyxdameraulevenshtein import damerau_levenshtein_distance
timeit damerau_levenshtein_distance(a, b)
# 100000次循环，3次中最佳：每循环11.4微秒

timeit editdistance.eval(a, b)  # 我的库
# 100000次循环，3次中最佳：每循环3.5微秒

import Levenshtein

timeit Levenshtein.distance(a, b)
# 100000次循环，3次中最佳：每循环3.21微秒

任意对象的距离计算

上述库只支持字符串。但有时我们需要处理其他类型的对象，比如字符串列表（单词）。我支持任何可迭代对象，只要其中的元素是可哈希的：

Levenshtein.distance(['spam', 'egg'], ['spam', 'ham'])
# ---------------------------------------------------------------------------
# TypeError                                 Traceback (most recent call last)
# <ipython-input-22-3e0b30d145ac> in <module>()
# ----> 1 Levenshtein.distance(['spam', 'egg'], ['spam', 'ham'])
#
# TypeError: distance expected two Strings or two Unicodes

editdistance.eval(['spam', 'egg'], ['spam', 'ham'])
# 1L

所以，如果对象的哈希值相同，则被视为相同。你可以为你的对象实例提供__hash__方法。

尽情使用吧！

许可证

本项目采用MIT许可证发布。

Copyright (c) 2013 Hiroyuki Tanaka

特此免费授予任何获得本软件及相关文档文件（"软件"）副本的人不受限制地处置该软件的权利，包括不受限制地使用、复制、修改、合并、发布、分发、再许可和/或出售该软件副本，以及再授权被配发了本软件的人如上的权利，须在下列条件下：

上述版权声明和本许可声明应包含在该软件的所有副本或实质成分中。

本软件是"按原样"提供的，没有任何形式的明示或暗示的保证，包括但不限于对适销性、特定用途的适用性和非侵权性的保证。在任何情况下，作者或版权持有人都不对任何索赔、损害或其他责任负责，无论这些追责来自合同、侵权或其它行为中，还是产生于、源于或有关于本软件以及本软件的使用或其它处置。