加载中…

加载中...

正文 字体大小:

grep分析和文件检索的思考[原创]

(2009-11-25 10:00:28)
标签:

linux

grep

模糊

搜索

源代码

分析

it

分类: 应用技术
由于工作需要,想要弄一个关于快速搜索、模糊查询之类的功能,当然,速度是最重要的事情之一。最先想到的可以完成这件事情的东西就是Linux下的著名程序Grep,很好用,也不算慢。于是对他进行了一些分析,顺便对全文检索方面做了一些基本测试工作。
捎带提一句,由于分析工作需要在Linux下进行,所以安装了一个比较流行的ubuntu,总体来说还不错,自动化方面进行了很多改进,对于终端用户确实是一个不错的办法。但是,有一些功能或者一些商用方面的软件仍旧没有办法实现对用户的傻瓜操作,最终还是会落到linux终端操作的复杂情况上。看来,他仍旧还是玩物一样的Linux。
好了,说回正题。首先,先说说关于文件到内存的装载。对于全文搜索这样的功能,最终是要在内存中进行匹配和查询的,这就不得不涉及到文件系统到内存的装载。首先,在Linux系统下有两套班子负责者个事情,标C的fopen和系统的open。没有做特别严正的考正,貌似open比较底层,也提供一些关于权限等方面的更多功能,fopen最终是否需要借助open实现不得而知,但是应该也是貌似那样的一种底层调用。在网上查了一下,有说法说open会略快,但是fopen有缓冲机制,对于多次操作有更多的优化作用。大概就是这样。关于方法就这么多。然后我选择了fopen进行了一下速度方面的测试。
首先,我选择了一个4.5G左右的iso文件作为目的文件,然后使用不同的方式进行遍历装载到内存,参看下表 :
每次读取10M ,消耗时间510秒
每次读取1M   ,消耗时间337秒
每次读取100K,消耗时间154秒
每次读取10K  ,消耗时间138秒
每次读取1K    ,消耗时间137秒
每次读取100B,消耗时间137秒
从上数数据可以看出,fopen确实有缓冲机制,大小大概是10K左右,可能因不同系统而异。所以,并不是我们想象的读取的次数越少总体开销就越小,因为缓冲机制的原因,稍小一点反而快一些。

再下来,我们看看grep怎么执行的。
我们仅以最简单的无正则搜索为例。首先在main里面,当然是必备的一些检测情况,然后有一个比较关键的步骤,装载处理函数install_matcher,这个过程会根据你的参数情况使用不同的search过程来处理你的不同搜索原则,其可用原则如下:
struct matcher const matchers[] = {
  { "default", Gcompile, EGexecute },
  { "grep", Gcompile, EGexecute },
  { "egrep", Ecompile, EGexecute },
  { "awk", Ecompile, EGexecute },
  { "fgrep", Fcompile, Fexecute },
  { "perl", Pcompile, Pexecute },
  { "", 0, 0 },
};
其中每一个原则都对应两个不同的处理函数,不同处理函数按照原则要求再调用详细的算法进行搜索运算。

装载备用,下面就准备进行分析了,grep会依据文件情况,判定是否文件夹,进而判定是否使用grepdir函数进行递归遍历。最终对于文件,使用grepfile进行进度检索入口。
grepfile打开文件,这里是用的是open,估计可能是为了追求绝对速度。从这里引导到grep函数。grep函数将文件通过reset并不断fillbuf装载到内存,然后进入grepbuf进行内存搜索。
grepbuf使用了我们刚才提到的装载的搜索函数,然后对成功搜索的结果就进行输出。
以我们讨论的 最简单的搜索为例,grepbuf将引导到EGexecute函数进行处理,然后执行算法路由过程kwsexec,这个过程会根据情况引导到不同的算法,比如我们 进入的Fast boyer-moore search算法,bmexec函数就是负责这个算法的执行函数。我查了以下这是比较著名的串搜索算法之一。网上有一些对于这样的算法的详细介绍,感兴趣的朋友自行搜索吧,我这里仅做最简单的介绍。
bm函数回维护 一个d1数组来装载关键字相关用于匹配,里面的信息什么样子,我们稍候还会介绍。
d1 = kwset->delta;
然后用tp和ep判定是否在top和end,由此来负责截止搜索。
while (tp <= ep)
然后使用 下列原则,进行匹配:
        d = d1[U(tp[-1])], tp += d;
        d = d1[U(tp[-1])], tp += d;
        if (d == 0)
          goto found;
        d = d1[U(tp[-1])], tp += d;
        d = d1[U(tp[-1])], tp += d;
        d = d1[U(tp[-1])], tp += d;
        if (d == 0)
          goto found;
        d = d1[U(tp[-1])], tp += d;
        d = d1[U(tp[-1])], tp += d;
        d = d1[U(tp[-1])], tp += d;
        if (d == 0)
          goto found;
        d = d1[U(tp[-1])], tp += d;
        d = d1[U(tp[-1])], tp += d;
这个有点常,有点重复,我们解释一下。
其实,搜索的原则很简单,但事也很有意思。bm选用最末字符进行反向比对。比如,我们搜索include,一个7字符的字串。
那么他会让d的初始为7位,然后看看我们的原串第一个7位 的最末字符是不是e,如果不是,我们就理解为前面这七个字符组成的字串不可能是用e作结尾的include,那么我们就在找下去。
当然我们不可能仅仅使用e作为比较原则,我们此时需要使用刚刚准备好的d1。我们把d1准备成这样
c=4
d=1
e=0
i=6
l=3
n=5
u=2
然后,其他的所有可能字符都安排成7。看没看出一点规律。
好了,实际上他是这样用的,如果我们在任意时刻通过d的位移,找到了任何 上表中的字符,比如n,我们就假装我们已经找到了,然后按照上表d1中的原则,让d等于d1所指定的数字。也就是说,我们假装找到include的n然后推5位去找e,或者。当然,有可能找得到,有可能找不到。如果找不到,我们通过检索d1表,自然会找到一个新的d,而这个数值实际上决定了我们累加tp的偏移,从而忽略刚才找到的n。反之,如果我们找到了e,由于e在d1中对应的数值是0,所以我们会停在这里,等待下面步骤。等待什么呢。对了,就是等待上面程序中的goto found,假装我们真的找到了。
在无条件转子后,我们反着找回7个字符,看看对不对。如果对了,成功命中,退出去让刚才的断点输出然后进行下次循环。否则,对不起,我们猜错了。我们回去再找。直到tp和ep相同,那就不找了。
事实上,我们就是在利用关键字中的每个字符相对于关键字的位置来假装命中,只要我们找到e就等待处理found验证我们的假装。就这么简单,但是挺精妙的。
其实,这个是符合我们的hash原则的一种搜索,就是可能进入的关键字是无穷的。通过hash函数转换成数值,然后进行位移命中。将无限空间映射到有限的索引中。
大概就是这样了。收工,自己想琢磨去了。:)

0

阅读 评论 收藏 转载 喜欢 打印举报
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有