📄 编辑距离、拼写检查与度量空间：一个有趣的数据结构.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0047)http://www.matrix67.com/blog/article.asp?id=382 -->
<HTML lang=UTF-8 xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>编辑距离、拼写检查与度量空间：一个有趣的数据结构 - Matrix67: My Blog</TITLE>
<META http-equiv=Content-Type content="text/html; charset=UTF-8">
<META http-equiv=Content-Language content=UTF-8>
<META content=all name=robots>
<META content=matrix67@tom.com,Matrix67 name=author>
<META content="PJBlog2 CopyRight 2005" name=Copyright>
<META
content=matrix67,PJBlog,blog,博客,OI,OIer,NOI,NOIp,Pascal,信息学,算法,数据结构,数学,趣题,美剧,电影
name=keywords>
<META
content="Matrix67: My Blog - 50% Informatics, 50% Mathematics, and 50% Imagination"
name=description><LINK
title="订阅 Matrix67: My Blog - Program Impossible 所有文章(rss2)"
href="http://www.matrix67.com/blog/feed.asp?cateID=6" type=application/rss+xml
rel=alternate><LINK title="订阅 Matrix67: My Blog - Program Impossible 所有文章(atom)"
href="http://www.matrix67.com/blog/atom.asp?cateID=6" type=application/atom+xml
rel=alternate><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/global.css" type=text/css rel=stylesheet><!--全局样式表--><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/layout.css" type=text/css rel=stylesheet><!--层次样式表--><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/typography.css" type=text/css
rel=stylesheet><!--局部样式表--><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/link.css" type=text/css rel=stylesheet><!--超链接样式表--><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/editor.css" type=text/css rel=stylesheet><!--UBB编辑器代码--><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/highlight.css" type=text/css
rel=stylesheet><LINK rev=stylesheet media=all
href="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/bt.css" type=text/css rel=stylesheet><LINK
href="favicon.ico" type=image/x-icon rel=icon><LINK href="favicon.ico"
type=image/x-icon rel="shortcut icon">
<SCRIPT src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/common.js"
type=text/javascript></SCRIPT>
<SCRIPT src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/BubbleTooltips.js"
type=text/javascript></SCRIPT>
<META content="MSHTML 6.00.2900.3268" name=GENERATOR></HEAD>
<BODY onkeydown=PressKey() onload=initJS()><A accessKey=i
href="http://www.matrix67.com/blog/default.asp"></A><A accessKey=z
href="javascript:history.go(-1)"></A>
<DIV id=container><!--顶部-->
<DIV id=header>
<DIV id=blogname>Matrix67: My Blog
<DIV id=blogTitle>50% Informatics, 50% Mathematics, and 50%
Imagination</DIV></DIV>
<DIV id=menu>
<DIV id=Left></DIV>
<DIV id=Right></DIV>
<UL>
<LI class=menuL></LI>
<LI><A class=menuA title=日志首页
href="http://www.matrix67.com/blog/default.asp">Index</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=标签云集
href="http://www.matrix67.com/blog/tag.asp">TagsCloud</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=个人档案
href="http://www.matrix67.com/blog/LoadMod.asp?plugins=AboutMeForPJBlog">Profile</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=留言板
href="http://www.matrix67.com/blog/LoadMod.asp?plugins=GuestBookForPJBlog">GuestBook</A></LI>
<LI class=menuDiv></LI>
<LI><A class=menuA title=讨论区
href="http://www.matrix67.com/blog/discuss.asp?action=index">Discuss(beta)</A></LI>
<LI class=menuR></LI></UL></DIV></DIV><!--内容-->
<DIV id=Tbody>
<DIV id=mainContent>
<DIV id=innermainContent>
<DIV id=mainContent-topimg></DIV>
<DIV class=content-width id=Content_ContentList><A accessKey=B
href="http://www.matrix67.com/blog/article.asp?id=382#body" name=body></A>
<DIV class=pageContent>
<DIV style="FLOAT: right; WIDTH: auto"><A title=订阅所有日志 accessKey=F
href="http://www.matrix67.com/blog/feed.asp?cateID=6" target=_blank><IMG
style="MARGIN-BOTTOM: -3px" alt=订阅所有日志
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/rss.png" border=0> 订阅</A> | <A
title="上一篇日志: 趣图：分形图形之海岸线 无限放大的图片" accessKey=,
href="http://www.matrix67.com/blog/article.asp?id=381"><IMG alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/Cprevious.gif" border=0>上一篇</A> | <A
title="下一篇日志: 号外：2,3图灵机通用性得证 英国大学生获得2.5万美元奖金" accessKey=.
href="http://www.matrix67.com/blog/article.asp?id=383"><IMG alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/Cnext.gif" border=0>下一篇</A> </DIV><IMG
style="MARGIN: 0px 2px -4px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/24.gif"> <STRONG><A
title="查看所有Program Impossible的日志"
href="http://www.matrix67.com/blog/default.asp?cateID=6">Program
Impossible</A></STRONG> </DIV>
<DIV class=Content>
<DIV class=Content-top>
<DIV class=ContentLeft></DIV>
<DIV class=ContentRight></DIV>
<H1 class=ContentTitle><STRONG>编辑距离、拼写检查与度量空间：一个有趣的数据结构</STRONG></H1>
<H2 class=ContentAuthor>作者:matrix67 日期:2007-10-22</H2></DIV>
<DIV class=Content-Info>
<DIV class=InfoOther>字体大小: <A accessKey=1
href="javascript:SetFont('12px')">小</A> <A accessKey=2
href="javascript:SetFont('14px')">中</A> <A accessKey=3
href="javascript:SetFont('16px')">大</A></DIV>
<DIV class=InfoAuthor><IMG style="MARGIN: 0px 2px -6px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/hn2_sunny.gif"><IMG alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/hn2_t_sunny.gif"> <IMG
style="MARGIN: 0px 2px -1px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/level5.gif"> | 本文内容遵从<A
href="http://creativecommons.org/licenses/by-nc-sa/3.0/deed.zh"
target=_blank>CC版权协议</A> 转载请注明出自matrix67.com </DIV></DIV>
<DIV class=Content-body
id=logPanel> 除了字符串匹配、查找回文串、查找重复子串等经典问题以外，日常生活中我们还会遇到其它一些怪异的字符串问题。比如，有时我们需要知道给定的两个字符串“有多像”，换句话说两个字符串的相似度是多少。1965年，俄国科学家Vladimir
Levenshtein给字符串相似度做出了一个明确的定义叫做Levenshtein距离，我们通常叫它“编辑距离”。字符串A到B的编辑距离是指，只用插入、删除和替换三种操作，最少需要多少步可以把A变成B。例如，从FAME到GATE需要两步（两次替换），从GAME到ACM则需要三步（删除G和E再添加C）。Levenshtein给出了编辑距离的一般求法，就是大家都非常熟悉的经典动态规划问题。<BR> 在自然语言处理中，这个概念非常重要，例如我们可以根据这个定义开发出一套半自动的校对系统：查找出一篇文章里所有不在字典里的单词，然后对于每个单词，列出字典里与它的Levenshtein距离小于某个数n的单词，让用户选择正确的那一个。n通常取到2或者3，或者更好地，取该单词长度的1/4等等。这个想法倒不错，但算法的效率成了新的难题：查字典好办，建一个Trie树即可；但怎样才能快速在字典里找出最相近的单词呢？这个问题难就难在，Levenshtein的定义可以是单词任意位置上的操作，似乎不遍历字典是不可能完成的。现在很多软件都有拼写检查的功能，提出更正建议的速度是很快的。它们到底是怎么做的呢？1973年，Burkhard和Keller提出的BK树有效地解决了这个问题。这个数据结构强就强在，它初步解决了一个看似不可能的问题，而其原理非常简单。<BR><BR> 首先，我们观察Levenshtein距离的性质。令d(x,y)表示字符串x到y的Levenshtein距离，那么显然：<BR><BR>1.
d(x,y) = 0 当且仅当 x=y （Levenshtein距离为0 <==> 字符串相等）<BR>2. d(x,y) =
d(y,x) （从x变到y的最少步数就是从y变到x的最少步数）<BR>3. d(x,y) + d(y,z)
>=
d(x,z) （从x变到z所需的步数不会超过x先变成y再变成z的步数）<BR><BR> 最后这一个性质叫做三角形不等式。就好像一个三角形一样，两边之和必然大于第三边。给某个集合内的元素定义一个二元的“距离函数”，如果这个距离函数同时满足上面说的三个性质，我们就称它为“度量空间”。我们的三维空间就是一个典型的度量空间，它的距离函数就是点对的直线距离。度量空间还有很多，比如Manhattan距离，图论中的最短路，当然还有这里提到的Levenshtein距离。就好像并查集对所有等价关系都适用一样，BK树可以用于任何一个度量空间。<BR><BR> 建树的过程有些类似于Trie。首先我们随便找一个单词作为根（比如GAME）。以后插入一个单词时首先计算单词与根的Levenshtein距离：如果这个距离值是该节点处头一次出现，建立一个新的儿子节点；否则沿着对应的边递归下去。例如，我们插入单词FAME，它与GAME的距离为1，于是新建一个儿子，连一条标号为1的边；下一次插入GAIN，算得它与GAME的距离为2，于是放在编号为2的边下。再下次我们插入GATE，它与GAME距离为1，于是沿着那条编号为1的边下去，递归地插入到FAME所在子树；GATE与FAME的距离为2，于是把GATE放在FAME节点下，边的编号为2。<BR> <IMG
alt="" src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/200710223.gif"
border=0><BR> 查询操作异常方便。如果我们需要返回与错误单词距离不超过n的单词，这个错误单词与树根所对应的单词距离为d，那么接下来我们只需要递归地考虑编号在d-n到d+n范围内的边所连接的子树。由于n通常很小，因此每次与某个节点进行比较时都可以排除很多子树。<BR> 举个例子，假如我们输入一个GAIE，程序发现它不在字典中。现在，我们想返回字典中所有与GAIE距离为1的单词。我们首先将GAIE与树根进行比较，得到的距离d=1。由于Levenshtein距离满足三角形不等式，因此现在所有离GAME距离超过2的单词全部可以排除了。比如，以AIM为根的子树到GAME的距离都是3，而GAME和GAIE之间的距离是1，那么AIM及其子树到GAIE的距离至少都是2。于是，现在程序只需要沿着标号范围在1-1到1+1里的边继续走下去。我们继续计算GAIE和FAME的距离，发现它为2，于是继续沿标号在1和3之间的边前进。遍历结束后回到GAME的第二个节点，发现GAIE和GAIN距离为1，输出GAIN并继续沿编号为1或2的边递归下去（那条编号为4的边连接的子树又被排除掉了）……<BR> 实践表明，一次查询所遍历的节点不会超过所有节点的5%到8%，两次查询则一般不会17-25%，效率远远超过暴力枚举。适当进行缓存，减小Levenshtein距离常数n可以使算法效率更高。<BR><BR>Matrix67原创<BR>做人要厚道
转贴请注明出处 <BR><BR><BR></DIV>
<SCRIPT type=text/javascript><!--google_ad_client = "pub-8918918108662869";google_ad_width = 728;google_ad_height = 90;google_ad_format = "728x90_as";google_ad_type = "text_image";google_ad_channel = "";google_color_border = "CCCCCC";google_color_bg = "F3F3F3";google_color_link = "6060FF";google_color_text = "292929";google_color_url = "000000";//--></SCRIPT>
<SCRIPT src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/show_ads.js"
type=text/javascript></SCRIPT>
<DIV class=Content-body><IMG style="MARGIN: 0px 2px -4px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/icon_trackback.gif"><STRONG>引用通告地址:</STRONG>
http://www.matrix67.com/blog/trackback.asp?tbID=JOHSCNF0&key=JOKOJQDPMMDQM8<BR><IMG
style="MARGIN: 4px 2px -4px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/tag.gif"><STRONG>Tags:</STRONG> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E8%B6%A3%E9%A2%98">趣题</A><A
style="DISPLAY: none" href="http://technorati.com/tag/趣题" rel=tag>趣题</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84">数据结构</A><A
style="DISPLAY: none" href="http://technorati.com/tag/数据结构" rel=tag>数据结构</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E9%80%92%E5%BD%92">递归</A><A
style="DISPLAY: none" href="http://technorati.com/tag/递归" rel=tag>递归</A> <BR><!--Add By WBC --><IMG style="MARGIN: 4px 2px -4px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/tag.gif"><STRONG>我猜你可能喜欢:</STRONG><BR>
<DIV class=Content-body id=wbc_tag></DIV><BR><!--End By WBC --></DIV>
<DIV class=Content-bottom>
<DIV class=ContentBLeft></DIV>
<DIV class=ContentBRight></DIV>评论: 6</A> | <A
href="http://www.matrix67.com/blog/trackback.asp?tbID=JOHSCNF0&key=JOKOJQDPMMDQM8"
target=_blank>引用: 0</A> | 查看次数: 1423 </DIV></DIV></DIV><A accessKey=C
href="http://www.matrix67.com/blog/article.asp?id=382#comm_top"
name=comm_top></A>
<DIV class=pageContent>
<DIV class=page style="FLOAT: right">
<UL>
<LI class=pageNumber><STRONG>1</STRONG></LI></UL></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('javau','commcontent_2653')"
name=comm_2653><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/icon_quote.gif" border=0></A> javau <SPAN
class=commentinfo>[楼层: 地基 发表时间: 2008-01-13 04:33 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_2653>真是张见识了...</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('ardcnis','commcontent_2420')" name=comm_2420><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="编辑距离、拼写检查与度量空间：一个有趣的数据结构.files/icon_quote.gif" border=0></A> ardcnis <SPAN
class=commentinfo>[楼层: 地下室 发表时间: 2007-12-25 06:41 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_2420>请看文章《告别Edit距离》<A
href="http://www.ardcn.com/NewsChinese.aspx?id=31"
target=_blank>http://www.ardcn.com/NewsChinese.aspx?id=31</A></DIV></DIV>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -