Skip to content

Latest commit

 

History

History
109 lines (73 loc) · 17.7 KB

莱文斯坦距离 - 维基百科，自由的百科全书.md

File metadata and controls

109 lines (73 loc) · 17.7 KB

本文由 简悦 SimpRead 转码， 原文地址 zh.wikipedia.org

中文维基百科

Facebook 粉丝专页

正式上线，邀请大家一同关注。

此条目没有列出任何参考或来源。 (2014 年 8 月 19 日)
维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。

莱文斯坦距离，又称 Levenshtein 距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

允许的编辑操作包括：

  1. 将一个字符替换成另一个字符
  2. 插入一个字符
  3. 删除一个字符

俄罗斯科学家弗拉基米尔 · 莱文斯坦（英语：Vladimir Levenshtein）在 1965 年提出这个概念。

目录

定义 [编辑]

如果分别用 和 表示 两个字符串的长度，那么它们的列文斯坦距离为 ，它符合：

是一个指示函数（indicator function），当 时，其值为 0，其他时候它等于 1 。

表示 的前 个字符与 的前 个字符之间的列文斯坦距离。（ 和 都是从 1 开始的下标）

注意：min 运算中的第一个公式代表（ 从 中）删除字符（以到达 ）；第二个公式代表插入字符；第三个代表替换（取决于当前字符是否相同）

例如 [编辑]

将 “kitten” 一字转成 “sitting” 的莱文斯坦距离为 3：

  1. kitten → sitten （k→s）
  2. sitten → sittin （e→i）
  3. sittin → sitting （插入 g）

应用 [编辑]

算法 [编辑]

动态规划经常被用来作为这个问题的解决手段之一。

int LevenshteinDistcance(string str1[1..lenStr1], string str2[1..lenStr2])
    int d[0..lenStr1, 0..lenStr2]
    int i, j, cost
 
    for i = 0 to lenStr2
       d[i, 0] := i
    for j = 0 to lenStr1
       d[0, j] := j
 
    for i = 1 to lenStr2
        for j = 1 to lenStr1
            if str2[i] = str1[j] 
                cost := 0
            else 
                cost := 1
            d[i, j] := min(
                                d[i-1, j  ] + 1,     // 删除
                                d[i  , j-1] + 1,     // 插入
                                d[i-1, j-1] + cost   // 替換
                            )
 
   return d[lenStr1, lenStr2]

参见 [编辑]

[隐藏]字符串
String metric（英语：String metric）
字符串搜索算法
多字符串搜索
正则表达式
序列比对
数据结构
其它

NewPP limit report Parsed by mw2369 Cached time: 20230128223319 Cache expiry: 1814400 Reduced expiry: false Complications: [show‐toc] CPU time usage: 0.133 seconds Real time usage: 0.225 seconds Preprocessor visited node count: 953/1000000 Post‐expand include size: 41685/2097152 bytes Template argument size: 1080/2097152 bytes Highest expansion depth: 25/100 Expensive parser function count: 12/500 Unstrip recursion depth: 0/20 Unstrip post‐expand size: 576/5000000 bytes Lua time usage: 0.031/10.000 seconds Lua memory usage: 2358116/52428800 bytes Number of Wikibase entities loaded: 0/400

Transclusion expansion time report (%,ms,calls,template) 100.00% 115.583 1 -total 37.28% 43.086 1 Template:Unreferenced 32.68% 37.768 1 Template:Ambox 27.95% 32.304 1 Template: 字符串 26.05% 30.110 1 Template:Navbox 23.39% 27.037 1 Template:Lang 21.55% 24.911 1 Template:Category_handler 17.49% 20.218 10 Template:Tsl 13.13% 15.174 1 Template:Category_handler/numbered 11.91% 13.761 1 Template:Namespace_detect

Saved in parser cache with key zhwiki:pcache:idhash:210725-0!userlang=zh-cn!zh-cn and timestamp 20230128223319 and revision id 71758497.