Archive

Posts Tagged ‘BM’

fastsearch快速字符串查找算法

March 15th, 2011 No comments

原创文章,转载请注明: 转载自系统技术非业余研究

本文链接地址: fastsearch快速字符串查找算法

最近在做一个项目需要涉及到快速的字符串匹配,每秒几十万次的那种。之前我用过linux内核的的textsearch库的KMP,BM,FSM的算法觉得还不错,这几个算法用于Linux网络模块的关键词过滤系统,支持非线性的字符查找,但是对性能还是不够印象深刻。于是我想起了python的fastsearch. Python这样的脚本语言字符查找用的非常的密集,所以这个算法是非常的高效的,可以说这个算法很大程度影响着python的性能。我们来看下 作者的网站 怎么说的:
Read more…

Post Footer automatically generated by wp-posturl plugin for wordpress.

R14A实现了EEP31,添加了binary模块

May 21st, 2010 No comments

原创文章,转载请注明: 转载自系统技术非业余研究

本文链接地址: R14A实现了EEP31,添加了binary模块

Erlang的binary数据结构非常强大,而且偏向底层,在作网络程序的时候,很方便的能够和二进制协议对应起来。但是由于这个数据结构加入erlang语言的时间不是很长,相关的配套模块不是很多。 在binary的匹配,替换,修改就显的非常麻烦。 于是有了EEP31 。 R14A昨天已经实现了这个功能, 在stdlib下添加了个binary模块。 这个模块大部分功能是由BIF实现的, 同时充分考虑了CPU使用的公平性,源码大部分在erl_bif_binary.c下。 还添加了个gurad函数: binary_part进一步方便我们写匹配条件。

我们在源码里面发现了以下注释:
/*
* The native implementation functions for the module binary.
* Searching is implemented using aither Boyer-More or Aho-Corasick
* depending on number of searchstrings (BM if one, AC if more than one).
* Native implementation is mostly for efficiency, nothing
* (except binary:referenced_byte_size) really *needs* to be implemented
* in native code.
*/

这个模块兼顾了效率和方便性,使用起来就大大简化了代码的复杂度,有福气了。

Post Footer automatically generated by wp-posturl plugin for wordpress.

Categories: Erlang探索 Tags: , , , , ,