企业网站建设问题,软件公司怎么找客户,关于幼儿建设网站ppt模板下载,WordPress移动端加搜索目录 一、算法介绍1、算法1#xff09;基于编辑距离2#xff09;基于标记3#xff09;基于序列4#xff09;基于压缩5#xff09;基于发音6#xff09;简单算法 2、安装 二、代码demo1、Hamming 距离2、Levenshtein 距离3、Damerau-Levenshtein距离4、Jaro 相似度5、Jaro… 目录 一、算法介绍1、算法1基于编辑距离2基于标记3基于序列4基于压缩5基于发音6简单算法 2、安装 二、代码demo1、Hamming 距离2、Levenshtein 距离3、Damerau-Levenshtein距离4、Jaro 相似度5、Jaro-Winkler相似度6、Smith–Waterman相似度7、Jaccard 相似度8、Sørensen-Dice 相似度9、Tversky 相似度10、Overlap coefficient相似度11、Cosine similarity相似度12、N-gram相似度13、最长公共子字符串/子序列相似度14、Ratcliff-Obershelp相似度 三、效果分析1、中文文本字符串1效果最好排序2速度最快排序3综合排序 2、其他1基于压缩的应用场景2基于发音的应用场景3简单算法的应用场景 一、算法介绍
1、算法
1基于编辑距离
算法类函数HammingHamminghammingMLIPNSMlipnsmlipnsLevenshteinLevenshteinlevenshteinDamerau-LevenshteinDamerauLevenshteindamerau_levenshteinJaro-WinklerJaroWinklerjaro_winkler, jaroStrcmp95StrCmp95strcmp95Needleman-WunschNeedlemanWunschneedleman_wunschGotohGotohgotohSmith-WatermanSmithWatermansmith_waterman
2基于标记
算法类函数Jaccard indexJaccardjaccardSørensen–Dice coefficientSorensensorensen, sorensen_dice, diceTversky indexTverskytverskyOverlap coefficientOverlapoverlapTanimoto distanceTanimototanimotoCosine similarityCosinecosineMonge-ElkanMongeElkanmonge_elkanBag distanceBagbag
3基于序列
算法类函数最长公共子序列相似度LCSSeqlcsseq最长公共子串相似度LCSStrlcsstrRatcliff-Obershelp 相似度RatcliffObershelpratcliff_obershelp
4基于压缩
使用不同压缩算法的归一化压缩距离。
经典压缩算法
算法类函数算术编码ArithNCDarith_ncdRLERLENCDrle_ncdBWT RLEBWTRLENCDbwtrle_ncd
常见压缩算法
算法类函数平方根SqrtNCDsqrt_ncd熵EntropyNCDentropy_ncd
正在开发的算法将两个字符串比较为比特数组
算法类函数BZ2BZ2NCDbz2_ncdLZMALZMANCDlzma_ncdZLibZLIBNCDzlib_ncd
5基于发音
算法类函数MRAMRAmraEditexEditexeditex
6简单算法
算法类函数前缀相似度Prefixprefix后缀相似度Postfixpostfix长度距离Lengthlength身份相似度Identityidentity矩阵相似度Matrixmatrix
2、安装
仅纯Python实现
pip install textdistance带有额外库以实现最大速度
pip install textdistance[extras]包含所有库用于基准测试和测试
pip install textdistance[benchmark]带有特定算法的额外库
pip install textdistance[Hamming]提供额外库的算法有DamerauLevenshtein、Hamming、Jaro、JaroWinkler、Levenshtein。
二、代码demo
1、Hamming 距离 import textdistance as tdtd.hamming(book, look)
1td.hamming.normalized_similarity(book, look)
0.75td.hamming(bellow, below)
3td.hamming.normalized_similarity(Below, Bellow)
0.5在第一个示例中有一个不同的字符。这使得距离等于1归一化相似度等于4-1/4 75%。在第二个示例中比较“bellow”和“below”前三个字母相同但接下来的三个字母不同。因此距离是3归一化相似度是6-3/6 50%。
2、Levenshtein 距离 td.levenshtein(book, look)
1td.levenshtein.normalized_similarity(book, look)
0.75td.levenshtein(bellow, below)
1td.levenshtein.normalized_similarity(Below, Bellow)
0.84在第一个示例中可以通过替换一个字母来得到另一个单词因此归一化相似度是4-1/4 75%。在第二个示例中有一个插入操作因此距离是1归一化相似度是6-1/6 84%。
3、Damerau-Levenshtein距离 td.levenshtein(act, cat)
2td.levenshtein.normalized_similarity(act, cat)
0.34td.damerau_levenshtein(act, cat)
1td.damerau_levenshtein.normalized_similarity(act, cat)
0.67Damerau-Levenshtein距离是Levenshtein 距离的一个变种应用广泛如拼写检查和序列分析
4、Jaro 相似度 td.jaro(bellow, below)
0.94td.jaro(simple, plesim)
0td.jaro(jaro, ajro)
0.92在第一个示例中有5个匹配字符和一个插入这不是置换操作因此Jaro 相似度为1/3*(5/65/56/6)。在第二个示例中有0个匹配字符因为共同字符不在max(|s1|, |s2|)/2-1的范围内。这就是为什么相似度为0的原因。在最后一个示例中有4个匹配字符和第一和第二字母之间的1个置换操作因此相似度为1/3 * (4/44/43/4) 0.91。
5、Jaro-Winkler相似度 td.jaro(simple, since)
0.7t.jaro_winkler(simple, since)
0.76由于两个字符串有两个共同的前缀字母。Jaro-Winkler相似度大于Jaro相似度0.7 0.12(1–0.7) 0.7 0.06 0.76。
6、Smith–Waterman相似度 td.smith_waterman(GATTACA, GCATGCU)
3td.smith_waterman(GATTACA, GCATGCU)
0.43Smith–Waterman算法在生物信息学中特别有用用于识别生物序列中的相似区域或基序
7、Jaccard 相似度 td.jaccard(jaccard similarity.split(), similarity jaccard.split())
1td.jaccard(jaccard similarity.split(), similarity jaccard jaccard.split())
0.66类似交并比Intersection of UnionIoU对比时并不考虑字符串单词的顺序
8、Sørensen-Dice 相似度 td.sorencen(jaccard similarity.split(), similarity jaccard.split())
1td.sorencen(jaccard similarity.split(), similarity jaccard jaccard.split())
0.8与前者相比不考虑重复元素
9、Tversky 相似度 td.sorencen(tversky similarity.split(), similarity tversky tversky.split())
0.8tversky td.Tversky(ks(0.5, 0.5))tversky(tversky similarity.split(), similarity tversky tversky.split())
0.8td.jaccard(tversky similarity.split(), similarity tversky tversky.split())
0.67tversky td.Tversky(ks(1, 1))tversky(tversky similarity.split(), similarity tversky tversky.split())
0.67tversky td.Tversky(ks(0.2, 0.8))tversky(tversky similarity.split(), similarity tversky tversky.split())
0.7410、Overlap coefficient相似度 td.overlap(overlap similarity.split(), similarity overlap overlap.split())
1.0计算集合交集大小与较小集合大小的比例
11、Cosine similarity相似度 td.cosine(cosine.split(), similarity.split())
0td.cosine(cosine sim.split(), cosine sim sim.split())
0.8112、N-gram相似度
N-gram 相似度是一种基于字符串中连续N个字符的相似度度量方法。它通过将字符串拆分为N-gramN个连续字符的子串然后比较这些N-gram的集合来计算两个字符串之间的相似度。下面是用 Python 实现 N-gram 相似度的代码示例
def ngrams(string, n):将字符串拆分为N-gramreturn [string[i:in] for i in range(len(string)-n1)]def ngram_similarity(str1, str2, n):计算两个字符串的N-gram相似度ngrams1 set(ngrams(str1, n))ngrams2 set(ngrams(str2, n))intersection ngrams1.intersection(ngrams2)union ngrams1.union(ngrams2)return len(intersection) / len(union) if union else 0.0# 示例
str1 hello
str2 hallo
n 2similarity ngram_similarity(str1, str2, n)
print(f{n}-gram 相似度: {similarity:.2f})
# 2-gram 相似度: 0.3313、最长公共子字符串/子序列相似度 s1, s2 RO PATTERN MATCHING, RO PRACTICEtd.lcsstr(s1, s2), td.lcsseq(s2, s1), td.lcsseq(s2, s1)(RO P, RO PRATC, RO PRACI)td.lcsstr.normalized_similarity(s1, s2), td.lcsseq.normalized_similarity(s1, s2)(0.21, 0.42)最长公共子字符串专注于找出两个字符串之间的最长公共子字符串它通过识别两个字符串共享的最长连续字符序列来衡量字符串之间的相似度 子序列不要求在原始序列中占据连续位置。因此最长公共子序列总是大于最长公共子字符串
14、Ratcliff-Obershelp相似度 s1, s2 RO PATTERN MATCHING, RO PRACTICEtd.ratcliff_obershelp(s1, s2), td.ratcliff_obershelp(s2, s1), len(s1), len(s2)
(0.46, 0.53, 19, 11)三、效果分析
1、中文文本字符串
在对中文文本字符串进行相似度比较时效果和速度各有不同的算法可供选择。以下是根据效果最好和速度最快分别排序的算法
1效果最好排序
Levenshtein计算编辑距离考虑到中文字符的插入、删除和替换效果较好。Damerau-Levenshtein比Levenshtein更进一步考虑到字符的交换能更准确地反映一些错别字的相似性。Jaro-Winkler考虑字符的匹配和位移对拼音和形近字有较好的识别效果。Needleman-Wunsch常用于序列比对适合处理长文本但速度较慢。Smith-Waterman和Needleman-Wunsch类似但更精细适合局部相似性比对。Cosine similarity基于向量空间模型适合处理词语或短句相似度但需要预处理成向量表示。Jaccard index基于集合的相似度计算适合分词后的文本比较。
2速度最快排序
Hamming适合固定长度的字符串比较速度极快但只能比较长度相同的字符串。Jaccard index基于集合操作速度较快尤其是在分词后的文本上。Cosine similarity向量化处理后计算余弦相似度速度较快但依赖预处理。Jaro-Winkler速度相对较快适合短文本比较。Levenshtein虽然是动态规划算法但优化后速度也较快适合中短文本比较。Damerau-Levenshtein考虑交换操作稍慢于Levenshtein但仍然较快。Smith-Waterman局部比对速度较慢适合较短文本。Needleman-Wunsch全局比对速度慢适合处理长文本。
3综合排序
结合效果和速度以下是综合排序
Levenshtein综合效果和速度适合大多数情况。Damerau-Levenshtein效果好于Levenshtein速度稍慢但仍然适用。Jaro-Winkler适合拼音和形近字速度较快。Cosine similarity需要预处理但在向量化后速度较快效果也不错。Jaccard index适合分词后的文本比较速度快。Needleman-Wunsch适合长文本效果好但速度慢。Smith-Waterman适合局部相似性比较效果好但速度最慢。
选择具体算法时可以根据文本的长度、预处理的复杂度以及对效果的要求来综合考虑。 英文文本也适用
2、其他
1基于压缩的应用场景
基于压缩的算法主要用于处理和比较大规模或复杂的数据集因为它们能够有效地压缩和分析数据。这些算法常用于以下场景
大数据分析在需要处理和比较大量文本数据的场景中如日志文件、网络爬虫数据等。数据压缩和传输在需要高效压缩和传输数据的应用中这些算法可以用于优化数据存储和传输效率。文本和字符串匹配用于需要在大文本库中查找相似文本或字符串的场景。
2基于发音的应用场景
基于发音的算法主要用于处理语音和文本的相似性计算这在以下场景中尤为有用
语音识别和处理在语音识别系统中用于比较和识别发音相似的词汇。拼写纠正在文本输入系统中根据发音相似性来纠正拼写错误。名称匹配用于比较和匹配发音相似的人名、地名等如客户关系管理系统中匹配相似的客户名字。
3简单算法的应用场景
简单算法通常用于需要快速、直接比较的场景这些场景不需要复杂的计算或大量数据处理
前缀和后缀匹配用于文件名或路径的匹配和分类如查找特定前缀或后缀的文件。长度比较用于需要比较字符串长度的场景如数据验证和清理。身份相似度用于简单的字符串相等性比较如用户输入的验证码验证。矩阵相似度用于矩阵数据的比较如图像处理中的像素矩阵比较。
