Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
正規表現改善報告する回 / Regexp memoization progress report
Search
TSUYUSATO Kitsune
August 19, 2023
Programming
2
590
正規表現改善報告する回 / Regexp memoization progress report
RubyKaigi 2023 follow up(
https://rhc.connpass.com/event/288535/
) での発表資料です。
TSUYUSATO Kitsune
August 19, 2023
Tweet
Share
More Decks by TSUYUSATO Kitsune
See All by TSUYUSATO Kitsune
YAPC::Japan::Online 2022で発表して WEB+DB PRESSに記事を寄稿した話
makenowjust
0
27
Regular Expressions, REXML, Automata Learning
makenowjust
0
320
オートマトン学習しろ / Do automata learning
makenowjust
3
240
#kaigieffect LT 2024 - rexml-css_selector: A REXML extension for supporting CSS selector
makenowjust
1
360
RubyKaigi 2024 - Make Your Own Regex Engine!
makenowjust
1
1.6k
Make Regexp#match much faster
makenowjust
1
2.7k
ReDoS 検出の最先端 recheck の紹介 / State of the Art of ReDoS Detection
makenowjust
9
3.6k
ReDoS 検出プログラム recheck の開発 / recheck: ReDoS check program
makenowjust
0
160
Integrated Shrinking による 高階関数の自動生成 / PRO-2020-4 Generating Higher-Order Functions by Integrated Shrinking
makenowjust
0
150
Other Decks in Programming
See All in Programming
Fluent UI Blazor 5 (alpha)の紹介
tomokusaba
0
140
フロントエンドテストの育て方
quramy
9
2.5k
自分のために作ったアプリが、グローバルに使われるまで / Indie App Development Lunch LT
pixyzehn
1
120
신입 안드로이드 개발자의 AI 스타트업 생존기 (+ Native C++ Code를 Android에서 사용해보기)
dygames
0
500
研究開発と実装OSSと プロダクトの好循環 / A virtuous cycle of research and development implementation OSS and products
linyows
1
190
新卒から4年間、20年もののWebサービスと 向き合って学んだソフトウェア考古学
oguri
7
6.7k
Develop Faster With FrankenPHP
dunglas
2
2.5k
CTFのWebにおける⾼難易度問題について
hamayanhamayan
1
980
보일러플레이트 코드가 진짜 나쁜 건가요?
gaeun5744
0
370
私の愛したLaravel 〜レールを超えたその先へ〜
kentaroutakeda
12
3.5k
The Evolution of Enterprise Java with Jakarta EE 11 and Beyond
ivargrimstad
0
920
AI Agentを利用したAndroid開発について
yuchan2215
0
210
Featured
See All Featured
Designing Experiences People Love
moore
141
23k
Building Adaptive Systems
keathley
41
2.5k
GraphQLの誤解/rethinking-graphql
sonatard
70
10k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
Code Review Best Practice
trishagee
67
18k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
16
1.1k
Writing Fast Ruby
sferik
628
61k
4 Signs Your Business is Dying
shpigford
183
22k
Faster Mobile Websites
deanohume
306
31k
Measuring & Analyzing Core Web Vitals
bluesmoon
6
320
Visualization
eitanlees
146
16k
The World Runs on Bad Software
bkeepers
PRO
67
11k
Transcript
౻࿘େ !NBLF@OPX@KVTU !3VCZ,BJHJGPMMPXVQ ਖ਼نදݱվળใࠂ͢Δճ
લճͷ͋Β͢͡ IUUQTSVCZLBJHJPSHQSFTFOUBUJPOTNBLFOPXKVTUIUNMEBZ
લճͷ͋Β͢͡ ਖ਼نදݱϚονϯάΛΊͬͪΌͨ͘͠
લճͷ͋Β͢͡ ͔͠͠ɺਖ਼نදݱ͕͘ͳΔͨΊʹ੍͍͔͕ͭ͘
લճͷ͋Β͢͡ ੍ϑϦʔͳੈքΛΊͯ͟͠ ό Ϧ Ξ
੍#FGPSF w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1
ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x> w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS ඍົʁ
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS ཧతʹແཧ ͋·ΓΘΕͯͳ͍
w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮઌಡΈɾޙಡΈʯ(?=foo) (?<=bar)ʮΞτϛοΫάϧʔϓʯ(?>foo) ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x>
w ͦͷଞɺಾͷ੍ͨͪ ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ۭจࣈྻʹϚον͢Δ͔͠Εͳ͍܁Γฦ͕͠ωετͰ͖ͳ͍ ੍"GUFS ཧతʹແཧ ͋·ΓΘΕͯͳ͍ ͦΜͳʹ ѱ͘ͳ͍ʁ
͜Ε·ͰͷϝϞԽ w ී௨ͷਖ਼نදݱͷ߹ɺ ʮ͋Δঢ়ଶʹ͋ΔҐஔ͔ΒͷϚονͰࣦഊͨ͠ʯͱ͍͏ใΛه͢Ε0, w ϝϞԽςʔϒϧͷܕ memo: (State,
Int) -> (NoMemo | Failure) w ઌಡΈɾޙಡΈ͕͋Δ߹ɺΞτϛοΫάϧʔϓ͕͋Δ߹ʁ
ઌಡΈɾޙಡΈͷϝϞԽ w ઌಡΈɾޙಡΈ෦Ϛονϯάࣦഊ͍ͯ͠ͳͯ͘ɺ ʮ͋Δঢ়ଶɾ͋ΔҐஔʯʹ͏Ұ౸ୡ͢ΔՄೳੑ͕͋Δ ྫ/a*?(?=a*)z/ w ʮઌಡΈɾޙಡΈ෦ͷϚονϯάʹޭͨ͠ʯͱ͍͏ใΛ
ϝϞԽςʔϒϧʹه͢Δඞཁ͕͋Δ w ϝϞԽςʔϒϧͷܕ memo: (State, Int) -> (NoMemo | Success | Failure)
ΞτϛοΫά ϧʔϓͷϝϞԽ w ΞτϛοΫά ϧʔϓͷ߹ɺ ΞτϛοΫά ϧʔϓͷதͰͷࣦഊͱɺ֎ଆͰͷࣦഊΛ۠ผ͠ͳ͚Ε͍͚ͳ͍ ֎ଆͰࣦഊͨ͠߹ɺΞτϛοΫά ϧʔϓͷதͷόοΫτϥοΫ
লུ͠ͳ͚Ε͍͚ͳ͍ w ϝϞԽςʔϒϧͷܕ memo: (State, Int) -> (NoMemo | Success | AtomicFailure | Failure)
࣮ͷमਖ਼ w ࣮ࡍͷϝϞԽςʔϒϧCJUྻͳͷͰɺ ઌಡΈɾޙಡΈɾΞτϛοΫά ϧʔϓͷঢ়ଶʹରͯ͠ CJUͬͯϝϞԽ͢ΔΑ͏ʹͨ͠ w ͜Ε·Ͱʮ͋Δঢ়ଶʹ͋ΔҐஔͰ౸ୡͨ͠ʯͱ͍͏ใΛه͍͕ͯͨ͠ɺ
ʮ͋Δঢ়ଶʹ͋ΔҐஔ͔ΒͷϚονʹࣦഊͨ͠ʯͱ͍͏ใʹ͢ΔͨΊɺ όοΫτϥοΫதʹϝϞԽςʔϒϧΛߋ৽͢ΔΑ͏ʹͨ͠ IUUQTHJUIVCDPNSVCZSVCZQVMM
ݱࡏͷ੍ w ͜ΕΒͷػೳΛ͏ͱɺਖ਼نදݱϚονϯά͕࠷దԽ͞Εͳ͍ ʮ݅ذʯ(?(<x>)yes|no)ʮඇแؚԋࢉࢠʯ(?~foo) ʮޙํࢀরʯ(foo)\1 ʮ෦ࣜͷݺͼग़͠ʯ(?<x>foo)\g<x> w ͦͷଞɺಾͷ੍ͨͪ
ճࢦఆͷ܁Γฦ͕͠ωετͰ͖ͳ͍(fo{1,23}){42} ઌಡΈɾޙಡΈͱΞτϛοΫά ϧʔϓ͕ωετͰ͖ͳ͍ ઌಡΈɾޙಡΈɾΞτϛοΫά ϧʔϓͷதͰΩϟϓνϟ͑ͳ͍
ΏΔ΅ w ੍ʹ͔͔Βͳ͍͔Ͳ͏͔ΛRegexp.linear_time?ͰνΣοΫͰ͖·͢ w ͜ΕΛͬͯɺϓϩάϥϜதͷਖ਼نදݱ੍͕ʹ͔͔Βͳ͍͔νΣοΫ͢Δ 3VCPDPQϓϥάΠϯΛ࡞ͬͯɺϝϯςφϯεͯ͘͠ΕΔਓΛืू͍ͯ͠·͢ SVCZKQ4MBDLͷSFHFYQνϟϯωϧʹͯ