อธิบายอนุพันธ์ของนิพจน์ทั่วไปโดยใช้ Pac-Man
![](https://post.nghiatu.com/assets/images/m/max/724/1*gvfrjSzIvn4qtiUm3m0UeA.png)
การกินเชอร์รี่สีแดงทำให้คุณสามารถกินผีสีน้ำเงินได้ แนวคิดที่ว่าสามารถใช้อนุพันธ์เพื่อสร้างอัลกอริทึมการจับคู่นิพจน์ทั่วไปนั้นเกือบจะไร้สาระ ให้ฉันอธิบายว่าอัลกอริทึมนี้ทำงานอย่างไรและเกี่ยวข้องกับ Pac-Man อย่างไร
ในปี 1964 Brzozowski ได้ตีพิมพ์บทความเกี่ยวกับ Derivatives of Regular expressions นี่เป็นหนึ่งในอัลกอริธึมที่ฉันโปรดปราน การใช้อนุพันธ์ของนิพจน์ทั่วไป เราสามารถใช้อัลกอริทึมในการจับคู่นิพจน์ทั่วไปได้ อัลกอริทึมนี้ดีมาก:
- เรียบง่าย
- การทำงาน
- ขยายได้อย่างง่ายดายด้วยตัวดำเนินการของคุณเอง
ในบทความนี้ ฉันจะแสดงให้คุณเห็นว่าเราสามารถจับคู่สตริงกับนิพจน์ทั่วไปได้อย่างไรโดยใช้ฟังก์ชันบริสุทธิ์เพียงสองฟังก์ชันและการเปรียบเทียบบางอย่างของ Pac-Man หากต้องการ คุณสามารถดูวิดีโอต่อไปนี้แทนการอ่านบทความได้ เนื่องจากเนื้อหาครอบคลุมเนื้อหาเดียวกัน:
สรุปนิพจน์ทั่วไป
ขั้นแรก เรามาตรวจทาน Regular Expression อย่างรวดเร็วเพื่อให้แน่ใจว่าเราอยู่ในหน้าเดียวกัน นิพจน์a(a|b)*
จะจับคู่สตริงที่ขึ้นต้นด้วย an a
ซึ่งตามด้วยa
's และb
's จำนวนเท่าใดก็ได้
- สตริง
ab
จะจับa(a|b)*
คู่ เราจะระบุสิ่งนี้ด้วยผีสีน้ำเงินที่กินได้ - สตริง
aabbba
ยังตรงกันa(a|b)*
เนื่องจากขึ้นต้นด้วย ana
และตามด้วยa
' และb
' หลายตัว - ถัดไป สตริง
ac
ไม่ตรงกันa(a|b)*
เนื่องจาก regex ไม่ตรงกับc
' ใดๆ และ regex ของเราไม่จับคู่สตริงย่อยใดๆ เราจะระบุสิ่งนี้โดยใช้ผีสีแดงที่ไล่ล่า Pac-Man - สุดท้าย สตริง
ba
ยังไม่ตรงกันa(a|b)*
เนื่องจากไม่ได้ขึ้นต้นด้วยa
.
![](https://post.nghiatu.com/assets/images/m/max/724/1*8KciDeiFnWPHBI9fmnJcnA.png)
ภาพรวมของอัลกอริทึม
ก่อนจะลงลึกในรายละเอียด เรามาดูภาพรวมว่าอัลกอริทึมนี้ทำงานอย่างไร ฉันได้คิดค้นเกม Pac-Man แปลก ๆ ที่คุณจะได้กินผีก็ต่อเมื่อคุณกินผลไม้ตามลำดับที่ตรงกับ regex Pac-Man ของเราเป็นตัวแทนของaba*
regex มีผลไม้ให้กินดังนี้ แอปเปิ้ล กล้วย แล้วก็แอปเปิ้ลaba
:
- เมื่อเราเริ่ม ผีจะไล่ตามเรา และนิพจน์ทั่วไปที่เราเหลือไว้ให้จับคู่
aba*
คือ - เรากินแอปเปิ้ลลูกแรก และนิพจน์ทั่วไปที่เราเหลือให้จับคู่ตอนนี้
ba*
คือ ผียังคงไล่ล่าเราตั้งแต่ผลไม้ที่เรากินจนถึงตอนนี้, แอปเปิ้ล, ไม่ตรงกับ regex - ต่อไปเรากินกล้วย regex ที่เราเหลือไว้ให้ตรงกัน
a*
คือ ตอนนี้ผีเริ่มหนีแล้ว เพราะตามเทคนิคab
แล้วaba*
- เราสามารถลองกินผีหรือกินแอปเปิ้ลลูกอื่น ซึ่งในกรณีนี้ นิพจน์ทั่วไปที่เราเหลือไว้ให้จับคู่ยังคง
a*
อยู่ ผียังคงวิ่งหนีเพราะaba
ยังตรงกับการแสดงออกaba*
ปกติ
![](https://post.nghiatu.com/assets/images/m/max/724/1*QSSBeM2FyvxO4AgPT4o6Nw.gif)
![](https://post.nghiatu.com/assets/images/m/max/724/1*blLxr_eBkdD5JWR9-YsEwA.png)
มีอีกหนึ่งหน้าที่ในการทำงานที่นี่ ฟังก์ชั่นตรวจสอบว่าผีกำลังไล่ล่า Pac-Man หรือไม่หรือว่า Pac-Man จับคู่กับ regex แล้วและกำลังไล่ล่าผีหรือไม่ ฟังก์ชันนี้เรียกว่าฟังก์ชัน nullable; จะตรวจสอบว่า regex ที่เหลือให้ตรงกันตรงกับสตริงว่างหรือไม่ ที่ทำเช่นนี้ได้เพราะหาก regex ที่เหลือให้จับคู่ตรงกับสตริงว่าง ผลไม้ที่กินเข้าไปจะต้องเพียงพอสำหรับ regex แล้ว
![](https://post.nghiatu.com/assets/images/m/max/724/1*uUpDbR_QN2YqRo-kym7ahQ.png)
![](https://post.nghiatu.com/assets/images/m/max/724/1*kyVrEdryAkFX5BybNaTgyg.png)
อัลกอริทึมการจับคู่อนุพันธ์
นั่นหมายความว่าเราต้องการเพียงสองฟังก์ชันในการเขียนอัลกอริทึมการจับคู่อนุพันธ์:
- ฟังก์ชันอนุพันธ์
- ฟังก์ชันที่เป็นโมฆะ
หนึ่งใน Golang สำหรับโปรแกรมเมอร์ที่จำเป็น:
และอีกอันใน Haskell สำหรับโปรแกรมเมอร์ที่ใช้งานได้:
ฟังก์ชั่นทั้งสองนี้เทียบเท่ากันและเขียนในรูปแบบการเขียนโปรแกรมที่แตกต่างกัน ในรหัส Haskell หรือที่foldl
เรียกว่าพับซ้ายหรือลดในภาษาอื่น การทำงานของ for วนซ้ำสำหรับคุณ นอกจากนี้ ใน Haskell เราไม่ต้องการเครื่องหมายจุลภาคเพื่อส่งพารามิเตอร์ไปยังฟังก์ชัน เนื่องจากฟังก์ชันแอ็พพลิเคชันเป็นการดำเนินการทั่วไปในภาษาการเขียนโปรแกรมเชิงฟังก์ชัน เราจึงใช้ช่องว่างเพื่อคั่นพารามิเตอร์
ตอนนี้ เรามาเจาะลึกเกี่ยวกับวิธีการใช้ฟังก์ชัน nullable และอนุพันธ์
การพูดนอกเรื่องที่มาของ Pac-Man
แต่ก่อนที่เราจะทำเช่นนั้น ฉันไม่รู้ว่าคุณเคยสงสัยเกี่ยวกับเรื่องราวต้นกำเนิดของ Pac-Man หรือไม่ ฉันยืนยันว่าไม่มีถังขยะนิวเคลียร์ที่ Pac-Man ตกลงไป ส่งผลให้ Pac-Man ได้รับพลังในการกินผี ตรรกะนั้นง่ายกว่ามาก
Pac-Man เป็นผลไม้! เมื่อ Pac-Man กินผลไม้อื่น Pac-Man กำลังเป็นมนุษย์กินคน ดังนั้นหากคุณเคยถูกผีไล่ตาม คุณต้องกินเนื้อมนุษย์ และอย่างน้อยผีก็ควรเริ่มวิ่งหนีคุณชั่วคราว ตอนนี้ฉันไม่ได้ลองด้วยตัวเอง แต่ตรรกะดูเหมือนจะฟังดูดี
สิ่งนี้อธิบายได้ว่าทำไมซอมบี้ถึงไล่ล่ามนุษย์อยู่เสมอ ดังที่ David Attenborough เคยกล่าวไว้ว่า:
“ซอมบี้ที่ไล่ตามเรา คือตัวมันเองถูกผีที่เรามองไม่เห็นไล่ตาม หลังจากที่ซอมบี้กินเนื้อมนุษย์ของเราไปบางส่วนแล้ว คุณจะเห็นพวกมันแสดงพฤติกรรมแปลกๆ คือ ร้องเสียงแหลมๆ นี่คือซอมบี้ที่กินผีที่ไล่ล่ามันก่อนหน้านี้”
ตัวดำเนินการพื้นฐาน
การใช้งานฟังก์ชัน nullable และ derivative จำเป็นต้องกำหนดตัวดำเนินการพื้นฐานที่มีอยู่ในนิพจน์ทั่วไปของเราก่อน
![](https://post.nghiatu.com/assets/images/m/max/724/1*vH1VHNT1ilPmAAqdn4tWzQ.png)
เราสามารถนึกถึงนิพจน์ทั่วไปเพื่ออธิบายชุดของสตริง
- ซึ่งหมายความว่าเซตว่างแทนโอเปอเรเตอร์ที่ไม่ตรงกับสตริง
- สตริงว่างแสดงถึงชุดซิงเกิลตันของสตริงเดียวที่ตรงกับสตริงว่างเท่านั้น
- อักขระยังแสดงถึงชุดซิงเกิลตันที่ตรงกับอักขระเดียว
a
เท่านั้น - จากนั้น เราสามารถรวมนิพจน์ทั่วไปพื้นฐานเหล่านี้โดยใช้ตัวดำเนินการ เช่น
or
,concatenation
และKleene star
, โดยที่r
และs
แสดงถึงนิพจน์ทั่วไปสองรายการที่เรากำลังรวมเข้าด้วยกัน
ฟังก์ชัน Nullable
เราสามารถเริ่มต้นด้วยฟังก์ชัน nullable มาดูตัวอย่างและหาว่า Regular Expression ใดที่ตรงกับสตริงว่าง เพื่อให้เข้าใจถึงวิธีการนำฟังก์ชันนี้ไปใช้
a*
จับคู่สตริงว่างตั้งแต่ศูนย์ขึ้นไปรวมศูนย์(a*|b)
จับคู่สตริงว่างตั้งแต่ด้านซ้ายของ or จับคู่สตริงว่างab
ไม่ตรงกับสตริงว่าง เนื่องจากตรงกับสตริงเท่านั้นab
ab*
ยังไม่ตรงกับสตริงว่าง เนื่องจากab*
ต้องใช้สตริงที่ขึ้นต้นด้วยa
(a|b)
ไม่ตรงกับสตริงว่าง เนื่องจากทั้งด้านซ้ายและขวาของทั้งด้านซ้ายและขวาไม่or
ตรงกับสตริงว่าง
![](https://post.nghiatu.com/assets/images/m/max/724/1*OB1dd3cBtsouF4ggHpG7_A.png)
นี่คือการใช้งานฟังก์ชัน nullable ด้านซ้ายแสดงค่าที่ส่งผ่านไปยังฟังก์ชัน และด้านขวาแสดงถึงการนำฟังก์ชันไปใช้ในกรณีนั้น ผีสีแดงเป็นตัวแทนของเท็จและผีสีน้ำเงินเป็นตัวแทนของจริง:
![](https://post.nghiatu.com/assets/images/m/max/724/1*E-8ql0fflVpEfi-dFL1VNg.png)
- ชุดว่างไม่ตรงกับสตริงว่างเนื่องจากไม่ตรงกับสตริงใดๆ
- สตริงว่างตรงกับสตริงว่างเพราะตรงกับสตริงว่างเท่านั้น
- อักขระ
a
ไม่ตรงกับสตริงว่าง เนื่องจากตรงกับอักขระa
เท่านั้น - ถ้าเรามีตรรกะ
or
เราต้องตรวจสอบทั้งสองด้าน หากตรงกับสตริงว่าง ตรรกะจะor
ตรงกับสตริงว่าง - เพื่อให้
concatenation
นิพจน์ทั่วไปของนิพจน์ทั้งสองตรงกับสตริงว่าง ทั้งสองต้องจับคู่สตริงว่าง - และสุดท้าย ถ้าเรามี
zero or more
ของบางอย่าง ก็จะรวมศูนย์ด้วย ซึ่งหมายความว่ามันจะจับคู่กับสตริงว่างเสมอ
- ตัวดำเนินการอันดับต้น ๆ ของเราคือสิ่ง
or
นี้หมายความว่าเราต้องตรวจสอบค่าว่างของด้านซ้ายและด้านขวา:b
และa*
- เราตรวจสอบและดูว่าอักขระ
b
ทางด้านซ้ายไม่เป็นโมฆะ:false
. - จากนั้นเราตรวจสอบและดูว่า
a*
ด้านขวาเป็นโมฆะ:true
. - ตอนนี้เรากลับมา
false
แล้วtrue
และเราสามารถor
เอามันไปให้true
ได้
แบบฝึกหัดที่เป็นโมฆะ
ลองแนะนำการใช้งานและตรวจสอบว่านิพจน์ทั่วไปต่อไปนี้เป็นโมฆะหรือไม่ คุณสามารถคลิกเพื่อตรวจสอบคำตอบของคุณ:
- ก
- ก*(ข*|∅)
- ε
- ∅*
- (∅|b)*(abc|ε)
ก่อนที่เราจะดูการใช้งานฟังก์ชัน เรามาดูตัวอย่างอนุพันธ์กันก่อน ต่อไปนี้เราจะพิจารณาอนุพันธ์ของนิพจน์ทั่วไปสองสามรายการ ทั้งหมดเกี่ยวกับอักขระa
:
- นิพจน์ทั่วไปที่เหลือให้ตรงกันหลังจาก
a*
ได้กินแอ ปa
เปิ้ลยังคงa*
อยู่ - อนุพันธ์ของ
ab*
เทียบกับa
isb*
เนื่องจากเราได้จับคู่คำนำหน้าa
แล้ว - อนุพันธ์ของเทียบ
(a|b)b
กับa
คือb
- อนุพันธ์ของเทียบ
b|(a*b)
กับa
คือa*b
ทางซ้ายb
ไม่ตรงกัน เราจึงโยนทิ้งได้ และทางขวาก็a
กินหมดzero or more
a
- ต่อไปเรามี
ab*
อันนี้ค่อนข้างยุ่งยากเล็กน้อย หลังจากที่มันกินแอปเปิ้ล นิพจน์ปกติที่เหลือให้จับคู่b(ab)*
คือ เนื่องจากเราจับคู่ได้เท่านั้นa
เราจึงคาดว่าจะเห็นอีกอย่างน้อยหนึ่งb
รายการ
![](https://post.nghiatu.com/assets/images/m/max/724/1*diyoj9GJOSiSgskTtAidog.png)
- อนุพันธ์ของเซตว่างจะเป็นเซตว่างเสมอ ไม่มีทางที่จะกู้คืนได้เนื่องจากเซตว่างไม่ตรงกับอะไรเลย
- อนุพันธ์ของสตริงว่างที่เกี่ยวข้องกับอักขระใดๆ คือเซตว่าง มันไม่ได้คาดหวังให้ตรงกับตัวละคร มันจะจับคู่สตริงว่างเท่านั้น
- อนุพันธ์ของอักขระตัวเดียวกับอักขระที่คล้ายกัน (ในกรณีนี้คือ
a
pple) คือสตริงว่าง เนื่องจากหลังจากที่จับคู่ตัวเองแล้ว สิ่งที่เหลือให้จับคู่คือสตริงว่าง - อนุพันธ์ของอักขระที่เกี่ยวกับอักขระอื่นที่ไม่เท่ากัน ในกรณีนี้
b
anana เป็นเซตว่างเนื่องจากเราไม่ได้จับคู่อักขระเฉพาะ - อนุพันธ์ของ
or
นิพจน์คือor
อนุพันธ์ มันก็ผลักปัญหาลงมาที่ลูกหลานของมัน - อนุพันธ์ของ
concat
นิพจน์ต้องพิจารณาว่าสามารถข้ามนิพจน์แรกได้หรือไม่ สามารถข้ามนิพจน์แรกได้ก็ต่อเมื่อนิพจน์แรกตรงกับสตริงว่างและเป็นโมฆะ สิ่งแรกที่เราทำคือตรวจสอบสิ่งนี้ ลองนึกถึงกรณีที่ไม่สามารถข้ามนิพจน์แรกได้เมื่อนิพจน์r
นั้นไม่เป็นโมฆะ จากนั้นอนุพันธ์คืออนุพันธ์ของนิพจน์แรกกับนิพจน์ที่concatenated
สองs
หากเราสามารถข้าม regex แรกได้ เราต้องพิจารณาทางเลือกอื่นที่เป็นอนุพันธ์ของนิพจน์ที่สองเท่านั้น จากนั้นเราสามารถor
มีทางเลือกสองทางคือข้ามr
และไม่ข้ามr
แล้วย้อนกลับมา - ในที่สุดเราก็มีตัว
star
ดำเนินการ ตรงกับนิพจน์ตั้งแต่ศูนย์ครั้งขึ้นไป เนื่องจากเราถูกส่งผ่านอักขระ นี่ไม่ใช่กรณีศูนย์ ดังนั้นเราต้องพิจารณาเป็นone or more
กรณีไป ซึ่งหมายความว่าเราต้องหาอนุพันธ์ของนิพจน์ใน thestar
และconcatenate
it อีกครั้งด้วยzero or more
นิพจน์
ตัวอย่างอนุพันธ์1
ลองหาอนุพันธ์ของเทียบ(ab)*
กับa
![](https://post.nghiatu.com/assets/images/m/max/724/1*nv0GwVV-SWSUUrzmefP4Jw.png)
(ab)*
เป็นการzero or more
แสดงออกดังนั้นเราจึงมองไปที่zero or more
กฎ เราเห็นว่าสิ่งนี้ต้องใช้อนุพันธ์ของนิพจน์ภายในstar
.
นี่คือconcatenation
ของa
และ b
ดังนั้นเราจึงตรวจสอบว่าด้านซ้ายเป็นโมฆะหรือไม่ และอักขระa
นั้นไม่เป็นโมฆะ ซึ่งหมายความว่าเราไม่สามารถข้ามไปได้ เราต้องหาอนุพันธ์ของเทียบa
กับ a
แต่นั่นคือสตริงว่าง ดังนั้นถ้าเราconcatenate
สตริงว่างที่มีด้านขวา ซึ่งก็คือb
เราจะb
ได้
ทีนี้ เราวนกลับมาที่zero or more
จำไว้ว่า เราหาอนุพันธ์ของab
ด้วยความเคารพa
แล้วได้ a กลับb
มา ตอนนี้เราสามารถเชื่อมต่อมัน(ab)*
อีกครั้งและเราb(ab)*
ได้
ตัวอย่างอนุพันธ์2
ลองหาอนุพันธ์ของเทียบ(a*ba)
กับb
![](https://post.nghiatu.com/assets/images/m/max/724/1*mteM5uFycQn2JuN6V2iTzg.png)
a*
ถูกเชื่อมเข้าด้วยกันba
ดังนั้น เรามาดูกฎการต่อข้อมูลกัน- เราตรวจสอบว่าด้านซ้าย
a*
เป็นโมฆะหรือไม่ ซึ่งก็คือ ซึ่งหมายความว่าเราสามารถข้ามมันไปได้ ซึ่งหมายความว่าเราต้องสร้างor
อนุพันธ์จากสองอนุพันธ์ด้วย - ด้านซ้ายลงเอยด้วยการไม่ตรงกัน เนื่องจาก
a*
ไม่b
ตรงกัน - โชคดีที่เรามีทางเลือกอื่นคือ
ba
. อนุพันธ์ของba
ที่เกี่ยวกับb
isa
และ
ฉันได้ข้ามรายละเอียดบางอย่างที่นี่ ถือว่าเป็นแบบฝึกหัดในการตรวจสอบงานของฉันด้วยการเดินผ่านฟังก์ชันด้วยตัวเอง
แบบฝึกหัดอนุพันธ์
ลองดำเนินการตามขั้นตอนและตรวจสอบว่าอนุพันธ์ของนิพจน์ทั่วไปต่อไปนี้เกี่ยวข้องกับb
อะไร คุณสามารถคลิกเพื่อตรวจสอบคำตอบของคุณ:
- εb
- ข*(ข|ค)
- ก*(ข|ค)
- เบ๊บ
- ∅*ข
ฉันหวังว่าตอนนี้คุณคงเข้าใจแล้วว่าทำไมการกินเชอร์รี่สีแดงจึงทำให้คุณสามารถกินผีสีน้ำเงินได้ และวิธีปรับใช้ตัวจับคู่นิพจน์ปกติโดยใช้อัลกอริทึมอนุพันธ์
เราได้กล่าวถึงอัลกอริทึมการทำงานพื้นฐานไว้ที่นี่แล้ว แต่มีหลายวิธีที่จะทำให้อัลกอริทึมนี้ดียิ่งขึ้นด้วยการปรับแต่งเล็กน้อย เราโกงและกลบเกลื่อนกฎการทำให้เข้าใจง่ายในโพสต์นี้ โดยใช้กฎเหล่านี้โดยไม่อธิบาย ซึ่งจะชัดเจนเป็นพิเศษหากคุณทำแบบฝึกหัด เรายังไม่ได้พูดถึงวิธีที่คุณสามารถใช้การท่องจำเพื่อสร้างหุ่นยนต์ที่มีประสิทธิภาพอย่างเกียจคร้าน
นอกจากนี้ เรายังสามารถขยายอัลกอริทึมได้อย่างง่ายดายเพื่อรวมโอเปอเรเตอร์ใหม่ๆ เช่นnot
และinterleave
แม้แต่สนับสนุนไวยากรณ์ที่ไม่มีบริบท ฉันจะพูดถึงบางหัวข้อเหล่านี้ในบทความถัดไป
ในระหว่างนี้ ฉันอยากเห็นคุณใช้อัลกอริทึมนี้ในภาษาโปรแกรมที่คุณคุ้นเคยที่สุด กรุณาส่งลิงค์ในความคิดเห็น
ขอขอบคุณ
- Brink van der Merweที่สละเวลาอธิบายอัลกอริทึมนี้ให้ฉันฟัง
- Brzozowski, Janusz A. “อนุพันธ์ของนิพจน์ทั่วไป” วารสาร ACM (JACM) 11.4 (1964): 481–494.
- Owens, Scott, John Reppy และ Aaron Turon “ตรวจสอบอนุพันธ์นิพจน์ปกติอีกครั้ง” วารสาร Functional Programming 19.2 (2009): 173–190.