宅男在线永久免费观看网直播,亚洲欧洲日产国码无码久久99,野花社区在线观看视频,亚洲人交乣女bbw,一本一本久久a久久精品综合不卡

全部
常見問題
產(chǎn)品動態(tài)
精選推薦

正則表達式回溯法原理

管理 管理 編輯 刪除

學(xué)習(xí)正則表達式,是需要懂點兒匹配原理的。

而研究匹配原理時,有兩個字出現(xiàn)的頻率比較高:“回溯”。

聽起來挺高大上,確實還有很多人對此不明不白的。

因此,本章就簡單扼要地說清楚回溯到底是什么東西。

內(nèi)容包括:

  1. 沒有回溯的匹配
  2. 有回溯的匹配
  3. 常見的回溯形式

#1. 沒有回溯的匹配

假設(shè)我們的正則是/ab{1,3}c/,其可視化形式是:

圖 0

而當目標字符串是"abbbc"時,就沒有所謂的“回溯”。其匹配過程是:

圖 1

其中子表達式b{1,3}表示“b”字符連續(xù)出現(xiàn)1到3次。

#2. 有回溯的匹配

如果目標字符串是"abbc",中間就有回溯。

圖 2

圖中第5步有紅顏色,表示匹配不成功。此時b{1,3}已經(jīng)匹配到了2個字符“b”,準備嘗試第三個時,結(jié)果發(fā)現(xiàn)接下來的字符是“c”。那么就認為b{1,3}就已經(jīng)匹配完畢。然后狀態(tài)又回到之前的狀態(tài)(即第6步,與第4步一樣),最后再用子表達式c,去匹配字符“c”。當然,此時整個表達式匹配成功了。

圖中的第6步,就是“回溯”。

你可能對此沒有感覺,這里我們再舉一個例子。正則是:

圖 3

目標字符串是"abbbc",匹配過程是:

圖 4

其中第7步和第10步是回溯。第7步與第4步一樣,此時b{1,3}匹配了兩個"b",而第10步與第3步一樣,此時b{1,3}只匹配了一個"b",這也是b{1,3}的最終匹配結(jié)果。

這里再看一個清晰的回溯,正則是:

圖 5

目標字符串是:"acd"ef,匹配過程是:

圖 6

圖中省略了嘗試匹配雙引號失敗的過程。可以看出.*是非常影響效率的。

為了減少一些不必要的回溯,可以把正則修改為/"[^"]*"/

#3. 常見的回溯形式

正則表達式匹配字符串的這種方式,有個學(xué)名,叫回溯法。

回溯法也稱試探法,它的基本思想是:從問題的某一種狀態(tài)(初始狀態(tài))出發(fā),搜索從這種狀態(tài)出發(fā)所能達到的所有“狀態(tài)”,當一條路走到“盡頭”的時候(不能再前進),再后退一步或若干步,從另一種可能“狀態(tài)”出發(fā),繼續(xù)搜索,直到所有的“路徑”(狀態(tài))都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法,就稱作“回溯法”。(copy于百度百科)。

本質(zhì)上就是深度優(yōu)先搜索算法。**其中退到之前的某一步這一過程,我們稱為“回溯”。**從上面的描述過程中,可以看出,路走不通時,就會發(fā)生“回溯”。即,嘗試匹配失敗時,接下來的一步通常就是回溯。

道理,我們是懂了。那么JS中正則表達式會產(chǎn)生回溯的地方都有哪些呢?

3.1 貪婪量詞

之前的例子都是貪婪量詞相關(guān)的。比如b{1,3},因為其是貪婪的,嘗試可能的順序是從多往少的方向去嘗試。首先會嘗試"bbb",然后再看整個正則是否能匹配。不能匹配時,吐出一個"b",即在"bb"的基礎(chǔ)上,再繼續(xù)嘗試。如果還不行,再吐出一個,再試。如果還不行呢?只能說明匹配失敗了。

雖然局部匹配是貪婪的,但也要滿足整體能正確匹配。否則,皮之不存,毛將焉附?

此時我們不禁會問,如果當多個貪婪量詞挨著存在,并相互有沖突時,此時會是怎樣?

答案是,先下手為強!因為深度優(yōu)先搜索。測試如下:


var string = "12345";
var regex = /(\d{1,3})(\d{1,3})/;
console.log( string.match(regex) );
// => ["12345", "123", "45", index: 0, input: "12345"]





其中,前面的\d{1,3}匹配的是"123",后面的\d{1,3}匹配的是"45"。

3.2 惰性量詞

惰性量詞就是在貪婪量詞后面加個問號。表示盡可能少的匹配,比如:


var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );
// => ["1234", "1", "234", index: 0, input: "12345"]





其中\d{1,3}?只匹配到一個字符"1",而后面的\d{1,3}匹配了"234"。

雖然惰性量詞不貪,但也會有回溯的現(xiàn)象。比如正則是:

圖 7

目標字符串是"12345",匹配過程是:

圖 8

知道你不貪、很知足,但是為了整體匹配成,沒辦法,也只能給你多塞點了。因此最后\d{1,3}?匹配的字符是"12",是兩個數(shù)字,而不是一個。

3.3 分支結(jié)構(gòu)

我們知道分支也是惰性的,比如/can|candy/,去匹配字符串"candy",得到的結(jié)果是"can",因為分支會一個一個嘗試,如果前面的滿足了,后面就不會再試驗了。

分支結(jié)構(gòu),可能前面的子模式會形成了局部匹配,如果接下來表達式整體不匹配時,仍會繼續(xù)嘗試剩下的分支。這種嘗試也可以看成一種回溯。

比如正則:

圖 9

目標字符串是"candy",匹配過程:

圖 10

上面第5步,雖然沒有回到之前的狀態(tài),但仍然回到了分支結(jié)構(gòu),嘗試下一種可能。所以,可以認為它是一種回溯的。


請登錄后查看

Desire- 最后編輯于2024-12-25 16:42:29

快捷回復(fù)
回復(fù)
回復(fù)
回復(fù)({{post_count}}) {{!is_user ? '我的回復(fù)' :'全部回復(fù)'}}
排序 默認正序 回復(fù)倒序 點贊倒序

{{item.user_info.nickname ? item.user_info.nickname : item.user_name}} LV.{{ item.user_info.bbs_level || item.bbs_level }}

作者 管理員 企業(yè)

{{item.floor}}# 同步到gitee 已同步到gitee {{item.is_suggest == 1? '取消推薦': '推薦'}}
{{item.is_suggest == 1? '取消推薦': '推薦'}}
沙發(fā) 板凳 地板 {{item.floor}}#
{{item.user_info.title || '暫無簡介'}}
附件

{{itemf.name}}

{{item.created_at}}  {{item.ip_address}}
打賞
已打賞¥{{item.reward_price}}
{{item.like_count}}
{{item.showReply ? '取消回復(fù)' : '回復(fù)'}}
刪除
回復(fù)
回復(fù)

{{itemc.user_info.nickname}}

{{itemc.user_name}}

回復(fù) {{itemc.comment_user_info.nickname}}

附件

{{itemf.name}}

{{itemc.created_at}}
打賞
已打賞¥{{itemc.reward_price}}
{{itemc.like_count}}
{{itemc.showReply ? '取消回復(fù)' : '回復(fù)'}}
刪除
回復(fù)
回復(fù)
查看更多
打賞
已打賞¥{{reward_price}}
532
{{like_count}}
{{collect_count}}
添加回復(fù) ({{post_count}})

相關(guān)推薦

快速安全登錄

使用微信掃碼登錄
{{item.label}} 加精
{{item.label}} {{item.label}} 板塊推薦 常見問題 產(chǎn)品動態(tài) 精選推薦 首頁頭條 首頁動態(tài) 首頁推薦
取 消 確 定
回復(fù)
回復(fù)
問題:
問題自動獲取的帖子內(nèi)容,不準確時需要手動修改. [獲取答案]
答案:
提交
bug 需求 取 消 確 定
打賞金額
當前余額:¥{{rewardUserInfo.reward_price}}
{{item.price}}元
請輸入 0.1-{{reward_max_price}} 范圍內(nèi)的數(shù)值
打賞成功
¥{{price}}
完成 確認打賞

微信登錄/注冊

切換手機號登錄

{{ bind_phone ? '綁定手機' : '手機登錄'}}

{{codeText}}
切換微信登錄/注冊
暫不綁定
CRMEB客服

CRMEB咨詢熱線 咨詢熱線

400-8888-794

微信掃碼咨詢

CRMEB開源商城下載 源碼下載 CRMEB幫助文檔 幫助文檔
返回頂部 返回頂部
CRMEB客服