正则表达式搜索的原理:
首先是解析正则表达式,把它表示成容易实现的等价树形形式。
然后是由模式串建立一个非确定的有限自动机(NFA)。NFA本质上是一个状态机,当读入文本字符时,活动状态被改变。状态机的当前状态为一个终止状态时,表示识别出一个字符串。
NFA构建完成之后即可直接进行搜索(即NFA-Thompson算法),速度很慢,原因是可能同时存在多个活动状态。
所以一般把NFA转换为DFA(确定有限自动机),它在任何时刻都只有一个活动状态,所以特别适合文本搜索。
但因为转换后的DFA的大小可能是原来的NFA的指数级,所以只有在模式串较短的时候才适用。
所以对于较大的模式串,通常用多个较小的DFA构造一个大的NFA,这种DFA和NFA结合的方法有较好的效率,就是DFA modules算法。
 
除此之外,正则表达式搜索还有其它算法,各有适用范围,有些位并行之类的较新的算法会有效率上的大提高。
 
了解了这些原理,实现你所说的那些图示就不是很难的事啦~~
::...
免责声明:
当前网页内容, 由 大妈 ZoomQuiet 使用工具: ScrapBook :: Firefox Extension 人工从互联网中收集并分享;
内容版权归原作者所有;
本人对内容的有效性/合法性不承担任何强制性责任.
若有不妥, 欢迎评注提醒:

大妈的多重宇宙 - YouTube

全新自媒体:科幻/读书/说故事...欢迎订阅;

或是邮件反馈可也:
askdama[AT]googlegroups.com


订阅 substack 体验古早写作:
Zoom.Quiet’s Chaos42 | Substack


点击注册~> 获得 100$ 体验券: DigitalOcean Referral Badge

关注公众号, 持续获得相关各种嗯哼:
zoomquiet



粤ICP备18025058号-1
公安备案号: 44049002000656 ...::