实现不同字符串相似度和距离度量的库
strsim的Python项目详细描述
python字符串相似性
<强> Python 3.5实现的 实现不同字符串相似性和距离度量的库。目前已经实现了十几种算法（包括levenshtein编辑距离和兄弟、jaro winkler、最长公共子序列、余弦相似度等）。请查看下面的摘要表以获得完整的列表… 来自PYPI: 或者克隆此存储库： 每个实现算法的主要特点如下。"成本"列给出计算成本的估计，以分别计算长度m和n的两个字符串之间的相似性。 [1]在这个库中，levenshtein编辑距离、lcs距离及其同级值是使用动态规划方法计算的，其代价为o（m.n）。对于levenshtein距离，该算法有时被称为wagner-fischer算法（字符串到字符串的校正问题，1974）。原始算法使用大小为m x n的矩阵来存储字符串前缀之间的levenshtein距离。 如果字母表是有限的，可以使用四个俄罗斯人的方法（Arlazarov等人关于有向图传递闭包的经济构造（1970），以加速计算。这是由masek在1980年发表的（"一种计算字符串编辑距离的快速算法"）。这种方法将矩阵分割成t×t大小的块。每个可能的块都被预先计算以生成查找表。这个查找表可以用来计算字符串的相似性（或距离）o（nm/t）。通常，如果m>；n，则选择t作为log（m）。由此产生的计算成本为o（mn/log（m））。此方法尚未实现。 [2]在"最大公共子序列长度"一文中，K.S.Larsen提出了一种计算时间O（log（m）、log（n））中的LCS长度的算法。但该算法有一个内存需求o（m.n榍），因此没有在这里实现。 [3]Damerau-Levenshtein字符串距离有两种变体：具有相邻转置的Damerau-Levenshtein（有时也称为无限制Damerau-Levenshtein距离）和最佳字符串对齐（有时也称为受限编辑距离）。为了获得最佳的字符串对齐，任何子字符串都不能被多次编辑。 虽然主题看起来很简单，但是有很多不同的算法可以用来度量文本的相似性或距离。因此，库定义了一些接口来对它们进行分类。 通常，实现normalizedstringsimilarity的算法也会实现normalizedstringdistance，而similarity=1-distance。但也有一些例外，比如n-gram相似度和距离（kondrak）….. metricStringDistance接口：一些距离实际上是度量距离，这意味着验证三角形不等式d（x，y）<；=d（x，z）+d（z，y）。例如，levenshtein是公制距离，而normalizedLevenshtein不是。 许多最近邻搜索算法和索引结构都依赖于三角不等式。 一些算法通过将字符串转换成n个字符集（n个字符的序列，有时也称为k-shingles）来工作。字符串之间的相似性或距离就是集合之间的相似性或距离。 其中一些，比如jaccard，将字符串视为一组木瓦，而不考虑每个木瓦的出现次数。其他的，如余弦相似性，使用有时被称为弦的轮廓，它考虑到每个木瓦的出现次数。 对于这些算法，在处理大型数据集时，还可以使用另一个用例： 两个单词之间的levenshtein距离是将一个单词更改为另一个单词所需的单个字符编辑（插入、删除或替换）的最小数目。 这是一个公制串距离。这个实现使用动态编程（wagner-fischer算法），只有两行数据。因此，空间要求为o（m），算法在o（m.n）中运行。 此距离计算为Levenshtein距离除以最长字符串的长度。结果值始终在区间[0.0 1.0]内，但它不再是度量值！ 相似度计算为1-标准化距离。 levenshtein的一种实现，它允许为不同的字符替换定义不同的权重。 该算法通常用于光学字符识别（ocr）应用。例如，对于ocr，替换p和r的成本比替换p和m的成本低，因为from和ocr的观点p与r相似。 它也可以用于键盘键入自动更正。例如，在这里，替换e和r的成本更低，因为它们在azerty或qwerty键盘上彼此相邻。因此，用户错误键入字符的可能性更高。 与levenshtein类似，damerau levenshtein distance with transposition（有时也称为无限制的damerau levenshtein distance）是将一个字符串转换为另一个字符串所需的最小操作数，其中一个操作定义为插入、删除或替换单个字符，或两个相邻字符的换位 它确实尊重三角形不等式，因此是一个度量距离。 不要将此与最佳字符串对齐距离混淆，最佳字符串对齐距离是一个扩展，任何子字符串都不能编辑多次。 将产生： damerau–levenshtein（有时称为受限编辑距离）的最佳字符串对齐变量计算使字符串相等所需的编辑操作数，条件是不编辑多个子字符串，而真正的damerau–levenHtein没有这种限制。
与levenshtein距离算法的不同之处在于，换位运算增加了一个递归。 请注意，对于最佳字符串对齐距离，三角形不等式不成立，因此它不是真正的度量。 将产生： Jaro Winkler是一个字符串编辑dis在记录链接（重复检测）领域开发的实体（Winkler，1990）。Jaro–Winkler距离度量是专门设计的，最适合人名等短字符串，也最适合检测拼写错误。 jaro winkler计算两个字符串之间的相似性，返回值位于区间[0.0，1.0]。
它（大致上）是damerau levenshtein的一个变体，其中2个相邻字符的替换被认为比2个彼此相距较远的字符的替换更不重要。 距离计算为1-jaro winkler相似度。 将产生： 最长公共子序列（lcs）问题是寻找两个（或更多）序列的最长公共子序列。它不同于寻找公共子串的问题：与子串不同，子串不需要占据原始序列中的连续位置。 diff实用程序、git使用它来协调多个更改等。 字符串x（长度n）和y（长度m）之间的lcs距离为n+m-2 lcs（x，y）|
min＝0
最大值=n+m 当只允许插入和删除时（不允许替换），或者当替换成本是插入或删除成本的两倍时，LCS距离等于Levenshtein距离。 该类实现了动态规划方法，该方法具有空间需求o（m.n）和计算成本o（m.n）。 在"最大公共子序列长度"中，k.s.larsen提出了计算时间o（log m.log n）中lcs长度的算法。但该算法有一个内存需求o（m.n榍），因此没有在这里实现。 基于最长公共子序列的距离度量，摘自daniel bakkelund的注释"基于lcs的字符串度量"。
http://heim.ifi.uio.no/~danielry/stringmetric.pdf 距离计算为1-lcs（s1，s2）/max（s1，s2） 将产生： 由Kondrak定义的标准化n-gram距离，"n-gram相似性和距离"，字符串处理和信息检索，计算机科学课堂笔记37722005，p p 115-126。 http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf 该算法使用附加特殊字符'\n'来增加第一个字符的权重。标准化是通过将总相似度分数除以最长单词的原始长度来实现的。 在本文中，kondrak还定义了一个相似性度量，但还没有实现。
一些算法通过将字符串转换成n个字符集（n个字符的序列，有时也称为k-shingles）来工作。字符串之间的相似性或距离就是集合之间的相似性或距离。 计算这些相似性和距离的成本主要由k-shingling（将字符串转换为k个字符的序列）来确定。因此，这些算法通常有两个用例： 直接计算字符串之间的距离： 或者，对于大型数据集，预先计算所有字符串的配置文件。然后可以计算外形之间的相似性： 注意，这只在使用同一个kshinling对象解析所有输入字符串时有效！ q-gram距离，由ukkonen在"带q-grams和最大匹配的近似字符串匹配"中定义
http://www.sciencedirect.com/science/article/pii/0304397592901434 两个字符串之间的距离定义为它们剖面差异的l1范数（每n个克的出现次数）：和（v1_i-v2_i）。q-gram距离是levenshtein距离的下限，但可以在o（m+n）中计算，其中levenshtein需要o（m.n） 两个字符串之间的相似性是这两个向量表示之间角度的余弦，计算为v1。v2/（v1*v2） 距离计算为1余弦相似度。 与q-gram距离一样，输入字符串首先被转换成n-gram的集合（n个字符的序列，也称为k-shingles），但这次不考虑每个n-gram的基数。每个输入字符串只是一组n-grams。然后，jaccard索引计算为v1 inter v2/v1 union v2。 距离计算为1-相似性。
Jaccard索引是一个公制距离。 类似于Jaccard索引，但这次相似度计算为2*v1 inter v2/（v1+v2）。 距离计算为1-相似性。 sift4是一种通用的字符串距离算法，它受jarowinkler和最长公共子序列的启发。它是为了产生一种距离测量方法，使其尽可能接近人类对弦距离的感知。因此，它考虑了字符替换、字符距离、最长公共子序列等元素。它是在没有理论背景的情况下，通过实验测试开发出来的。 尚未实施 在项目中使用Java字符串相似性，并希望在这里提到它？别犹豫给我挂个电话！ 欢迎加入QQ群-->： 979659372
下载
pip install strsim
git clone https://github.com/luozhouyang/python-string-similarity
cd python-string-similarity
pip install -r requirements.txt
概述
< T/>< T/> < /广告><正文>正常化？ <度量？键入 成本
典型用法
levenshtein 距离 o（m*n）1 标准化levenshtein 距离
相似性o（m*n）1 加权levenshtein 距离 o（m*n）1 > OCR damerau levenshtein3 距离 o（m*n）1 最佳字符串对齐3 距离 o（m*n）1 jaro winkler 相似性
距离o（m*n） 打字错误更正 最长公共子序列
距离 O（M*N）1,2 diff实用程序，git调节 度量最长公共子序列 距离 o（m*n）1,2 n-gram 距离 o（m*n） q-gram 距离 剖面图 o（m+n） 余弦相似性
相似性
距离剖面图 o（m+n） 雅卡索引 相似性
距离o（m+n） Sorensen骰子系数 相似性
距离o（m+n） 标准化、度量、相似性和距离
（标准化）相似性和距离
公制距离
基于相似度和距离的带状疱疹（n-gram）
左旋血红素
fromsimilarity.levenshteinimportLevenshteinlevenshtein=Levenshtein()print(levenshtein.distance('My string','My $string'))print(levenshtein.distance('My string','My $string'))print(levenshtein.distance('My string','My $string'))
标准化Levenshtein
fromsimilarity.normalized_levenshteinimportNormalizedLevenshteinnormalized_levenshtein=NormalizedLevenshtein()print(normalized_levenshtein.distance('My string','My $string'))print(normalized_levenshtein.distance('My string','My $string'))print(normalized_levenshtein.distance('My string','My $string'))print(normalized_levenshtein.similarity('My string','My $string'))print(normalized_levenshtein.similarity('My string','My $string'))print(normalized_levenshtein.similarity('My string','My $string'))
加权levenshtein
fromsimilarity.weighted_levenshteinimportWeightedLevenshteinfromsimilarity.weighted_levenshteinimportCharacterSubstitutionInterfaceclassCharacterSubstitution(CharacterSubstitutionInterface):defcost(self,c0,c1):ifc0=='t'andc1=='r':return0.5return1.0weighted_levenshtein=WeightedLevenshtein(CharacterSubstitution())print(weighted_levenshtein.distance('String1','String2'))
达梅劳·莱文施泰因
fromsimilarity.damerauimportDameraudamerau=Damerau()print(damerau.distance('ABCDEF','ABDCEF'))print(damerau.distance('ABCDEF','BACDFE'))print(damerau.distance('ABCDEF','ABCDE'))print(damerau.distance('ABCDEF','BCDEF'))print(damerau.distance('ABCDEF','ABCGDEF'))print(damerau.distance('ABCDEF','POIU'))
1.0
2.0
1.0
1.0
1.0
6.0
最佳字符串对齐
fromsimilarity.optimal_string_alignmentimportOptimalStringAlignmentoptimal_string_alignment=OptimalStringAlignment()print(optimal_string_alignment.distance('CA','ABC'))
3.0
Jaro Winkler
pip install strsim
0
pip install strsim
1
最长公共子序列
pip install strsim
2
度量最长公共子序列
pip install strsim
3
pip install strsim
4
N克
pip install strsim
5
基于木瓦（n-gram）的算法
pip install strsim
6
pip install strsim
7
克
余弦相似性
雅卡索引
索伦森骰子系数
实验性
SIFT4
用户
推荐PyPI第三方库