亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

  免費(fèi)注冊(cè) 查看新帖 |

Chinaunix

  平臺(tái) 論壇 博客 文庫(kù)
最近訪問(wèn)板塊 發(fā)新帖
查看: 3863 | 回復(fù): 6
打印 上一主題 下一主題

[算法] grep 使用 NFA 為什么效率高 [復(fù)制鏈接]

論壇徽章:
22
丑牛 日期:2014-08-15 14:32:0015-16賽季CBA聯(lián)賽之同曦 日期:2017-12-14 15:28:14黑曼巴 日期:2017-08-10 08:14:342017金雞報(bào)曉 日期:2017-02-08 10:39:42黑曼巴 日期:2016-11-15 15:48:38CU十四周年紀(jì)念徽章 日期:2016-11-09 13:19:1015-16賽季CBA聯(lián)賽之同曦 日期:2016-04-08 18:00:03平安夜徽章 日期:2015-12-26 00:06:30程序設(shè)計(jì)版塊每日發(fā)帖之星 日期:2015-12-03 06:20:002015七夕節(jié)徽章 日期:2015-08-21 11:06:17IT運(yùn)維版塊每日發(fā)帖之星 日期:2015-08-09 06:20:002015亞冠之吉達(dá)阿赫利 日期:2015-07-03 08:39:42
跳轉(zhuǎn)到指定樓層
1樓 [收藏(0)] [報(bào)告]
發(fā)表于 2016-11-01 08:58 |只看該作者 |倒序?yàn)g覽
龍書中提到，grep為了效率，使用了 NFA 算法。
NFA 匹配正則的效率不是比 DFA 更慢嗎？
這么說(shuō)的原因是什么，我哪里沒(méi)理解正確，請(qǐng)各位兄弟指教。

論壇徽章:
0
2樓 [報(bào)告]
發(fā)表于 2016-11-01 18:21 |只看該作者
dfa只是正則的子集，能力太弱。

論壇徽章:
22
丑牛 日期:2014-08-15 14:32:0015-16賽季CBA聯(lián)賽之同曦 日期:2017-12-14 15:28:14黑曼巴 日期:2017-08-10 08:14:342017金雞報(bào)曉 日期:2017-02-08 10:39:42黑曼巴 日期:2016-11-15 15:48:38CU十四周年紀(jì)念徽章 日期:2016-11-09 13:19:1015-16賽季CBA聯(lián)賽之同曦 日期:2016-04-08 18:00:03平安夜徽章 日期:2015-12-26 00:06:30程序設(shè)計(jì)版塊每日發(fā)帖之星 日期:2015-12-03 06:20:002015七夕節(jié)徽章 日期:2015-08-21 11:06:17IT運(yùn)維版塊每日發(fā)帖之星 日期:2015-08-09 06:20:002015亞冠之吉達(dá)阿赫利 日期:2015-07-03 08:39:42
3樓 [報(bào)告]
發(fā)表于 2016-11-02 16:42 |只看該作者
回復(fù) 2# codechurch

正則直接轉(zhuǎn)成NFA比較容易。我理解，每一個(gè)NFA都可以轉(zhuǎn)換成DFA。在轉(zhuǎn)換成DFA后，再做匹配，效率就會(huì)提高很多。
我這個(gè)思路錯(cuò)在哪里了？請(qǐng)賜教，謝謝

論壇徽章:
0
4樓 [報(bào)告]
發(fā)表于 2016-11-02 18:44 |只看該作者
回復(fù) 3# amarant

并非所有nfa都可以轉(zhuǎn)為dfa，正則的全集就不能轉(zhuǎn)為dfa
dfa只能包括  *+| 的功能
像 “{，}” 與 后向引用等等功能，都不可能做到。


評(píng)分

參與人數(shù) 1可用積分 +2 信譽(yù)積分 +16 收起 理由
amarant + 2 + 16 贊一個(gè)!

查看全部評(píng)分

論壇徽章:
22
丑牛 日期:2014-08-15 14:32:0015-16賽季CBA聯(lián)賽之同曦 日期:2017-12-14 15:28:14黑曼巴 日期:2017-08-10 08:14:342017金雞報(bào)曉 日期:2017-02-08 10:39:42黑曼巴 日期:2016-11-15 15:48:38CU十四周年紀(jì)念徽章 日期:2016-11-09 13:19:1015-16賽季CBA聯(lián)賽之同曦 日期:2016-04-08 18:00:03平安夜徽章 日期:2015-12-26 00:06:30程序設(shè)計(jì)版塊每日發(fā)帖之星 日期:2015-12-03 06:20:002015七夕節(jié)徽章 日期:2015-08-21 11:06:17IT運(yùn)維版塊每日發(fā)帖之星 日期:2015-08-09 06:20:002015亞冠之吉達(dá)阿赫利 日期:2015-07-03 08:39:42
5樓 [報(bào)告]
發(fā)表于 2016-11-02 21:02 |只看該作者
回復(fù) 4# codechurch

多謝

論壇徽章:
3
15-16賽季CBA聯(lián)賽之山東 日期:2016-10-30 08:47:3015-16賽季CBA聯(lián)賽之佛山 日期:2016-12-17 00:06:31CU十四周年紀(jì)念徽章 日期:2017-12-03 01:04:02
6樓 [報(bào)告]
發(fā)表于 2016-11-07 18:09 |只看該作者
回復(fù) 4# codechurch

^_^，你這說(shuō)的是 Unix 傳統(tǒng)正則語(yǔ)言(或者說(shuō)擴(kuò)展正則)。按照編譯書籍上嚴(yán)格的正則語(yǔ)言定義，正則語(yǔ)言(就是去掉 Unix 擴(kuò)展正則的)和NFA DFA等價(jià)且可以相互轉(zhuǎn)換的。
你說(shuō)那個(gè)引用的問(wèn)題，NFA 也是不能解決的，得用遞歸。
不過(guò)實(shí)際上的正則庫(kù)實(shí)現(xiàn)來(lái)說(shuō)，我認(rèn)為沒(méi)有必要死守編譯理論，非把正則識(shí)別等同于構(gòu)造 NFA DFA 來(lái)實(shí)現(xiàn)。

論壇徽章:
3
2015年迎新春徽章 日期:2015-03-04 09:56:11數(shù)據(jù)庫(kù)技術(shù)版塊每日發(fā)帖之星 日期:2016-08-03 06:20:00數(shù)據(jù)庫(kù)技術(shù)版塊每日發(fā)帖之星 日期:2016-08-04 06:20:00
7樓 [報(bào)告]
發(fā)表于 2017-02-04 16:11 |只看該作者
codechurch 發(fā)表于 2016-11-02 18:44
回復(fù) 3# amarant

并非所有nfa都可以轉(zhuǎn)為dfa，正則的全集就不能轉(zhuǎn)為dfa

{,}可以轉(zhuǎn)化為DFA
而后向引用當(dāng)然不可以,因?yàn)樗呀?jīng)不是正則語(yǔ)言范疇
您需要登錄后才可以回帖 登錄 | 注冊(cè)

本版積分規(guī)則 發(fā)表回復(fù)

  

北京盛拓優(yōu)訊信息技術(shù)有限公司. 版權(quán)所有 京ICP備16024965號(hào)-6 北京市公安局海淀分局網(wǎng)監(jiān)中心備案編號(hào)：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年舉報(bào)專區(qū)
中國(guó)互聯(lián)網(wǎng)協(xié)會(huì)會(huì)員  聯(lián)系我們：huangweiwei@itpub.net
感謝所有關(guān)心和支持過(guò)ChinaUnix的朋友們 轉(zhuǎn)載本站內(nèi)容請(qǐng)注明原作者名及出處

清除 Cookies - ChinaUnix - Archiver - WAP - TOP