返回顶部
首页 > 资讯 > 后端开发 > Python >Python “编辑距离”(Levens
  • 730
分享到

Python “编辑距离”(Levens

距离编辑Python 2023-01-31 07:01:34 730人浏览 安东尼

Python 官方文档:入门教程 => 点击学习

摘要

本文搜集了网上比较常用的几种计算Levenshtein distance的函数, 其中函数(1)为调用数学工具包Numpy, 函数(2)和(1)算法类似,都是采用DP, (3)来自wiki(4)是直接调用python的第三方库Levens

本文搜集了网上比较常用的几种计算Levenshtein distance的函数,

其中函数(1)为调用数学工具包Numpy, 函数(2)和(1)算法类似,都是采用DP, (3)来自wiki(4)是直接调用python的第三方库Levenshtein


源码和结果如下:

import time
from functools import wraps
import cProfile
import numpy
import Levenshtein


def fn_timer(function):
    @wraps(function)
    def function_timer(*args, **kwargs):
        t0 = time.time()
        result = function(*args, **kwargs)
        t1 = time.time()
        print ("Total time running %s: %s seconds" %
                (function.func_name, str(t1-t0))
                )
        return result
    return function_timer


def levenshtein1(source, target):
    if len(source) < len(target):
        return levenshtein1(target, source)
 
    # So now we have len(source) >= len(target).
    if len(target) == 0:
        return len(source)
 
    # We call tuple() to force strings to be used as sequences
    # ('c', 'a', 't', 's') - numpy uses them as values by default.
    source = numpy.array(tuple(source))
    target = numpy.array(tuple(target))
 
    # We use a dynamic programming alGorithm, but with the
    # added optimization that we only need the last two rows
    # of the matrix.
    previous_row = numpy.arange(target.size + 1)
    for s in source:
        # Insertion (target grows longer than source):
        current_row = previous_row + 1
 
        # Substitution or matching:
        # Target and source items are aligned, and either
        # are different (cost of 1), or are the same (cost of 0).
        current_row[1:] = numpy.minimum(
                current_row[1:],
                numpy.add(previous_row[:-1], target != s))
 
        # Deletion (target grows shorter than source):
        current_row[1:] = numpy.minimum(
                current_row[1:],
                current_row[0:-1] + 1)
 
        previous_row = current_row
 
    return previous_row[-1]


def levenshtein2(s1, s2):
    if len(s1) < len(s2):
        return levenshtein2(s2, s1)
 
    # len(s1) >= len(s2)
    if len(s2) == 0:
        return len(s1)
 
    previous_row = range(len(s2) + 1)
    for i, c1 in enumerate(s1):
        current_row = [i + 1]
        for j, c2 in enumerate(s2):
            insertions = previous_row[j + 1] + 1 # j+1 instead of j since previous_row and current_row are one character longer
            deletions = current_row[j] + 1       # than s2
            substitutions = previous_row[j] + (c1 != c2)
            current_row.append(min(insertions, deletions, substitutions))
        previous_row = current_row
 
    return previous_row[-1]


def levenshtein3(s, t):
        ''' From Wikipedia article; Iterative with two matrix rows. '''
        if s == t: return 0
        elif len(s) == 0: return len(t)
        elif len(t) == 0: return len(s)
        v0 = [None] * (len(t) + 1)
        v1 = [None] * (len(t) + 1)
        for i in range(len(v0)):
            v0[i] = i
        for i in range(len(s)):
            v1[0] = i + 1
            for j in range(len(t)):
                cost = 0 if s[i] == t[j] else 1
                v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
            for j in range(len(v0)):
                v0[j] = v1[j]
 
        return v1[len(t)]

@fn_timer
def calllevenshtein1(s,t,n):
    for i in range(n):
        levenshtein3(s,t)

@fn_timer
def calllevenshtein2(s,t,n):
    for i in range(n):
        levenshtein3(s,t)

@fn_timer
def calllevenshtein3(s,t,n):
    for i in range(n):
        levenshtein3(s,t)

@fn_timer
def calllevenshtein4(s,t,n):
    for i in range(n):
        Levenshtein.distance(s,t)
 
if __name__ == "__main__":
    n = 50000
    a = 'abddcdefdgbd22svb'
    b = 'bcdefg34rdyvdfsd'
    calllevenshtein1(a, b, n)
    calllevenshtein2(a, b, n)
    calllevenshtein3(a, b, n)
    calllevenshtein4(a, b, n)

结果:

Total time running calllevenshtein1: 16.0750000477 seconds
Total time running calllevenshtein2: 16.4990000725 seconds
Total time running calllevenshtein3: 16.2939999104 seconds
Total time running calllevenshtein4: 0.0629999637604 seconds


从结果来看,调用Python第三方包效率最高,原因是其内部调用c库,优化了算法结构


--结束END--

本文标题: Python “编辑距离”(Levens

本文链接: https://lsjlt.com/news/191625.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • Python “编辑距离”(Levens
    本文搜集了网上比较常用的几种计算Levenshtein distance的函数, 其中函数(1)为调用数学工具包Numpy, 函数(2)和(1)算法类似,都是采用DP, (3)来自wiki(4)是直接调用python的第三方库Levens...
    99+
    2023-01-31
    距离 编辑 Python
  • C++怎么编辑距离
    这篇文章主要介绍“C++怎么编辑距离”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C++怎么编辑距离”文章能帮助大家解决问题。编辑距离Example 1:Input: word1 = "h...
    99+
    2023-06-19
  • Python实现计算最小编辑距离
    最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数。允许的编辑操作有:删除,插入,替换。具体内容可参见:维基百科—莱文斯坦距离。一般代码实现的方式都是通过动态规划...
    99+
    2022-06-04
    最小 距离 编辑
  • C++实现LeetCode(72.编辑距离)
    [LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the ...
    99+
    2024-04-02
  • C++编辑距离(动态规划)
    题目描述: 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 我们可以对一个单词进行如下三种操作: 插入一个字符删除一个...
    99+
    2024-04-02
  • 怎么用C++实现编辑距离
    这篇文章主要讲解了“怎么用C++实现编辑距离”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“怎么用C++实现编辑距离”吧!Edit Distance 编辑距离Given two words&n...
    99+
    2023-06-20
  • C++实现LeetCode(161.一个编辑距离)
    [LeetCode] 161. One Edit Distance 一个编辑距离 Given two strings s and t, determin...
    99+
    2024-04-02
  • Python文本相似性计算之编辑距离详解
    编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符...
    99+
    2022-06-04
    相似性 详解 文本
  • C++怎么判断编辑距离是否为1
    这篇文章主要讲解了“C++怎么判断编辑距离是否为1”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++怎么判断编辑距离是否为1”吧!编辑距离这道题是之前那道 Edit Distan...
    99+
    2023-06-20
  • 算法leetcode|72. 编辑距离(rust重拳出击)
    文章目录 72. 编辑距离:样例 1:样例 2:提示: 分析:题解:rust:二维数组(易懂)滚动数组(更加优化的内存空间) go:c++:python:java: 72...
    99+
    2023-09-07
    rust golang 数据结构 算法 后端 leetcode
  • Java动态规划之如何编辑距离问题
    这篇文章给大家分享的是有关Java动态规划之如何编辑距离问题的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所...
    99+
    2023-05-30
    java
  • PHP如何计算两个字符串之间的编辑距离
    这篇文章将为大家详细讲解有关PHP如何计算两个字符串之间的编辑距离,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。PHP 计算字符串编辑距离 引言 字符串编辑距离是衡量两个字符串相似程度的指标。它计算将一个...
    99+
    2024-04-02
  • Python 马氏距离求取函数详解
    马氏距离区别于欧式距离,如百度知道中所言: 马氏距离(Mahalanobis distance)是由印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的,表示点与一个...
    99+
    2024-04-02
  • Python VTK映射三维模型表面距离
    数据准备: 需要准备两个stl文件、Python需要安装vtk库 步骤一:数据读取 首先通过vtk.vtkSTLReader() 定义stl文件读取接口...
    99+
    2024-04-02
  • python中scipy.spatial.distance距离计算函数怎么用
    这篇文章主要为大家展示了“python中scipy.spatial.distance距离计算函数怎么用”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“python中scipy.spatial.di...
    99+
    2023-06-29
  • python怎么求两个坐标点的距离
    可以使用Python中的math模块中的sqrt和pow函数来计算两个坐标点的距离。假设有两个坐标点A(x1, y1)和B(x2, ...
    99+
    2023-08-31
    python
  • python中怎么求两点之间的距离
    可以使用以下方法来求两点之间的距离: import math def distance(x1, y1, x2, y2): ...
    99+
    2024-03-15
    python
  • Python利用Redis计算经纬度距离案例
    目录1. 需要的库, Redis2. 连接Redis3. 计算4. 查看已添加位置的经纬度5. 计算两地之间的距离6. 搜索范围内的地址1. 需要的库, redispip install redis2....
    99+
    2024-04-02
  • Python——输入两个点,计算两点间距离
    题目: 分别输入两个点的坐标,计算两个点的距离 计算公式:((x1-x2)²+(y1-y2)²)½ 代码: import mathx1=eval(input('x1='))y1=eval(inp...
    99+
    2023-09-29
    python 学习
  • Python如何实现马氏距离求取函数
    这篇文章主要介绍了Python如何实现马氏距离求取函数,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。马氏距离区别于欧式距离,如百度知道中所言:马氏距离(Mahalanobis...
    99+
    2023-06-25
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作