注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

yeye55的博客

编程就象品一杯清茶,清淡却又深厚。

 
 
 

日志

 
 
关于我

宅男一只,喜欢编程。没事的时候就喜欢抱着电脑看看电影、看看动漫、听听音乐、打打网游、逛逛论坛。清静的时候喜欢专研编程技术,但是发现自己至今仍然只是一只三脚猫。

网易考拉推荐

Delphi下实现包含通配符的文本查找  

2011-11-05 12:23:45|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  本文最早于2009年6月20日在编程论坛(programbbs.com)上发表,页面地址:http://programbbs.com/bbs/view12-21351-1.htm 。

1 前言

  通配符就是指“*”和“?”两个字符,“*”表示当前位置可以没有或者有多个任意字符;“?”表示当前位置有一个任意字符。通配符匹配在网上资料中都有讲到,但主要说的都是字符串匹配而不是文本查找。我结合通配符匹配的算法写了一个支持通配符的文本查找函数。这个函数的源代码可以在本楼末尾的压缩包中得到。现在先说一下通配符匹配的算法。

2 通配符匹配算法

  利用包含通配符的模式串(以下简称模式串)进行文本查找,通常会匹配到一个不定长度的文本。所以匹配完成后不但要得到匹配文本的结束位置也要得到匹配文本的开始位置。现在先来看一个简单的问题:假设有长度为PLen的模式串P,以及长度为TLen的文本T。如果P中不包含通配符,那么用下面这个简单算法就可以完成查找:

function FindText1(P,T : PAnsiChar;  PLen,TLen : Integer; var SelStart,SelEnd : Integer): Boolean;
var
    PCur,TCur : Integer;
begin
    result:=false;
    for TCur:=SelStart to  TLen-PLen do
    begin
         for PCur:=0 to PLen-1 do
             if P[PCur]<>T[TCur+PCur] then break;
         if PCur>=PLen then
        begin
             SelStart:=TCur;
             SelEnd:=TCur+PLen;
             result:=true;
             break;
         end;
    end;
end;

  以上函数从文本T的SelStart位置开始向下查找模式串P,返回是否找到,如果找到设置SelStart和SelEnd为匹配文本的开始位置和结束位置。这个算法是最简单的文本查找算法,它有两层循环,外层for循环用以确认查找位置并逐一后移,内层for循环进行文本比对。修改上述算法中的比较代码就可以使文本查找支持通配符“?”,将第8行的代码修改如下:

if (P[PCur]<>'?') and  (P[PCur]<>T[TCur+PCur]) then break;

  这样就可以支持通配符“?”,我们再来讲一下通配符“*”。对于文本查找“*”位于模式串的头部和尾部是没有意义的。例如模式串“*a*”,只要文本中包含字符“a”则可以匹配全部文本。所以我们在讨论时忽略“*”位于模式串头尾的情况。通配符“*”可以匹配任意文本,任意长度的任意字符这通常很难处理。由于“?”只能匹配一个字符,只包含“?”符的模式串可以匹配固定长度的文本。所以一个解决思路就是将模式串看成是多个由“*”分隔的子串,每个子串都匹配固定长度的文本。例如模式串“a1*b2*c?3”可以看成是“a1”、“b2”、“c?3”三个子串,前两个子串匹配2个字符,最后一个子串匹配3个字符。这样问题就转化为子串的查找,匹配算法的描述如下:

开始查找:
  模式串初始化,确认子串,
  从当前位置开始查找第一个子串,
  判断:是否找到?
    如果找到:记录匹配的开始位置和结束位置,
    如果没找到:匹配失败,转到结束查找,
  循环判断:还有其它子串?
    如果没有:匹配成功,转到结束查找,
    如果还有:从匹配的结束位置开始查找下一个子串,
    判断:是否找到?
      如果找到:记录匹配的结束位置,返回循环判断,
      如果没找到:匹配失败,转到结束查找,
结束查找。

  利用上面的算法描述结合前面给出的查找代码,自己设计一个支持通配符的文本查找算法应该不是问题。文本查找是可以设置方向的,上面的算法适合向下查找。当进行向上查找时可以将上面的算法反过来,先向前查找最后一个子串,然后向前查找倒数第二个子串,最后完成查找。

3 源代码

  项目文件下载(点这里

  上面的项目文件是一个示范程序,其中的WildcardFind.pas是核心文件。在该文件中只有一个函数,这个函数可以进行支持通配符的文本查找,同时支持多种功能如:区分大小、整字匹配等等。函数声明如下:

function FindText(Pattern,Text :  PAnsiChar; PLen,TLen : Integer; var SelStart,SelEnd : Integer; Options :  TFindTextOptions): Boolean;

  其中Pattern为要查找的文本(模式串),可以包含通配符和转义字符;Text为文本内容;PLen为模式串的长度;TLen为文本内容的长度;SelStart为文本选择开始的位置;SelEnd为文本选择结束的位置;Options为文本查找选项。模式串支持通配符和转义字符,如果模式串为空或者包含错误的字符格式,函数将返回false,通配符格式说明如下:

* 表示当前位置可以没有或者有多个任意字符;
? 表示当前位置有一个任意字符;

  由于可能需要查找“*”字符、“?”字符和非打印字符,所以模式串支持转义字符。转义字符的格式说明如下:

\xHH ASCII码为HH(十六进制)的字符,必需要有两个数值字符,
不区分大小写,例如:\x0D;
\\ 字符“\”;
\* 字符“*”;
\? 字符“?”;

  Options查找选项包含4个标志:当包含foMatchCase时区分大小写,不包含时不区分大小写;当包含foWholeWord时查找进行整字匹配,不包含时忽略整字匹配;当包含foDown时从SelEnd之后开始向下查找,不包含时从SelStart之前开始向上查找;当包含foLoop时,当向下查找失败时,从文本的头部重新开始向下查找;当向上查找失败时,从文本的尾部重新开始向上查找。

  该函数返回是否找到模式串指定的文本,如果找到则修改SelStart和SelEnd的值为匹配文本的开始位置和结束位置,并返回true。如果没找到则返回false。

  评论这张
 
阅读(709)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017