免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2054 | 回复: 6

[算法] grep 使用 NFA 为什么效率高 [复制链接]

论坛徽章:
22
丑牛
日期:2014-08-15 14:32:0015-16赛季CBA联赛之同曦
日期:2017-12-14 15:28:14黑曼巴
日期:2017-08-10 08:14:342017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:42
发表于 2016-11-01 08:58 |显示全部楼层
龙书中提到,grep为了效率,使用了 NFA 算法。
NFA 匹配正则的效率不是比 DFA 更慢吗?
这么说的原因是什么,我哪里没理解正确,请各位兄弟指教。

论坛徽章:
0
发表于 2016-11-01 18:21 |显示全部楼层
dfa只是正则的子集,能力太弱。

论坛徽章:
22
丑牛
日期:2014-08-15 14:32:0015-16赛季CBA联赛之同曦
日期:2017-12-14 15:28:14黑曼巴
日期:2017-08-10 08:14:342017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:42
发表于 2016-11-02 16:42 |显示全部楼层
回复 2# codechurch

正则直接转成NFA比较容易。我理解,每一个NFA都可以转换成DFA。在转换成DFA后,再做匹配,效率就会提高很多。
我这个思路错在哪里了?请赐教,谢谢

论坛徽章:
0
发表于 2016-11-02 18:44 |显示全部楼层
回复 3# amarant

并非所有nfa都可以转为dfa,正则的全集就不能转为dfa
dfa只能包括  *+| 的功能
像 “{,}” 与 后向引用等等功能,都不可能做到。


评分

参与人数 1可用积分 +2 信誉积分 +16 收起 理由
amarant + 2 + 16 赞一个!

查看全部评分

论坛徽章:
22
丑牛
日期:2014-08-15 14:32:0015-16赛季CBA联赛之同曦
日期:2017-12-14 15:28:14黑曼巴
日期:2017-08-10 08:14:342017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:42
发表于 2016-11-02 21:02 |显示全部楼层
回复 4# codechurch

多谢

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2016-11-07 18:09 |显示全部楼层
回复 4# codechurch

^_^,你这说的是 Unix 传统正则语言(或者说扩展正则)。按照编译书籍上严格的正则语言定义,正则语言(就是去掉 Unix 扩展正则的)和NFA DFA等价且可以相互转换的。
你说那个引用的问题,NFA 也是不能解决的,得用递归。
不过实际上的正则库实现来说,我认为没有必要死守编译理论,非把正则识别等同于构造 NFA DFA 来实现。

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2017-02-04 16:11 |显示全部楼层
codechurch 发表于 2016-11-02 18:44
回复 3# amarant

并非所有nfa都可以转为dfa,正则的全集就不能转为dfa

{,}可以转化为DFA
而后向引用当然不可以,因为它已经不是正则语言范畴
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

PostgreSQL中国大会,早鸟票抢购!

PostgreSQL中国大会,早鸟票抢购!
2019年11月29~11月30日,由 PostgreSQL中文社区与ITPUB联合主办的第九届《PostgreSQL 中国技术大会》将在北京隆重召开。PostgreSQL 作为功能最强的的开源关系型数据库之一,得到了越来越多企业的推广和运用,也越来越受到广大技术爱好者的欢迎和重视。这将是 PostgreSQL 的又一次交流盛会。




----------------------------------------

点击报名>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP