- มีผู้เขียน
regex crate ของ Rust ซึ่งได้ปรับปรุงและเพิ่มประสิทธิภาพไลบรารี regex ของภาษา Rust
- ได้สร้าง crate ใหม่ชื่อ
regex-automata ที่เปิดเผยภายในของ regex crate ออกมาเป็น API แยกต่างหาก
- นี่เป็นไลบรารี regex ตัวแรกที่เปิดเผยภายในในระดับนี้ผ่านไลบรารีคนละเวอร์ชัน
- บทความนี้อธิบายกระบวนการเขียนใหม่เพื่อการปรับปรุง วิธีแก้ปัญหา และแนวทางการใช้ API ของ
regex-automata
- กลุ่มผู้อ่านเป้าหมายคือโปรแกรมเมอร์ Rust และทุกคนที่สนใจวิธีการทำงานของเอนจิน regex แบบฟินิตออโตมาตา
- บทความนี้เล่าประวัติย่อของ
regex crate และพัฒนาการของมัน
- ปัญหาที่
regex crate เผชิญมีทั้งเรื่องการตั้งค่า การทดสอบ คำขอ API บางประเภท และความจำเป็นของ DFA ที่คอมไพล์เสร็จสมบูรณ์
- การเขียนใหม่ช่วยแก้ปัญหาเหล่านี้ และมอบโซลูชันที่ยืดหยุ่นและปรับแต่งประสิทธิภาพได้ดีกว่าเดิม
- การเผยแพร่
regex-automata เป็น crate แยก ช่วยให้สามารถทดลองและพัฒนา API เพิ่มเติมได้ โดยไม่ทำให้ regex crate หลักซับซ้อนเกินไป
- บทความนี้เน้นข้อดีของการใช้
regex-automata และศักยภาพในการพัฒนาวงการเอนจิน regex ต่อไป
- บทความนี้อธิบายโปรแกรม
regex-cli ที่ให้การเข้าถึง API ของ regex crate ผ่านบรรทัดคำสั่ง
- โปรแกรมนี้มีเครื่องมืออย่างการซีเรียลไลซ์ DFA ที่คอมไพล์แล้วลงไฟล์ และการสร้างโค้ด Rust เป็นต้น
- บทความนี้แสดงตัวอย่างผลกระทบของ Unicode ต่อแพตเทิร์น regex
- โปรแกรม
regex-cli สามารถดีบักและแสดงผลชนิดข้อมูลต่าง ๆ ในระบบนิเวศของ regex crate ได้
- มีคำสั่ง
regex-cli find ที่สามารถค้นหาหลายแพตเทิร์นโดยใช้ capture group ได้
- บทความนี้อธิบายการไหลของข้อมูลภายในเอนจิน regex ตั้งแต่การพาร์สแพตเทิร์นไปจนถึงการสร้าง NFA
- การดึง literal ออกมาเป็นเทคนิคการปรับแต่งประสิทธิภาพสำคัญที่ใช้ใน
regex crate
- การดึง literal หมายถึงการดึงข้อความตรงตัวจากแพตเทิร์น regex เพื่อระบุผู้ต้องสงสัยว่าจะตรงกันใน haystack ได้อย่างรวดเร็ว
- การเลือกว่าจะค้นหา literal ใดสำคัญต่อการลด false positive และลด latency
- การดึง literal เป็นกระบวนการเชิงฮิวริสติกเพื่อจำกัดผลกระทบจาก false positive และ latency ให้ต่ำที่สุด
- แนวทางของการดึง literal คือให้ความสำคัญกับ literal ที่ยาวกว่า และหลีกเลี่ยง literal ที่สั้นมากหรือพบได้ทั่วไปเกินไป
- บทความนี้อธิบายการปรับแต่งลำดับ literal ของ regex
- ลำดับ literal คือชุดของสตริงที่ถูกปฏิบัติเป็นสตริงที่ต้องตรงกันแบบเป๊ะ
- ระหว่างการปรับแต่ง จะมีการระบุลำดับที่สามารถทำให้เป็นอนันต์ได้เพื่อเพิ่มประสิทธิภาพ
- บทความนี้อธิบายกระบวนการที่ regex ต่างกันอาจสร้างลำดับ literal ที่ต่างกัน
- บทความนี้ยังพูดถึงกระบวนการค้นหา literal ภายใน haystack ด้วย
- การค้นหา substring เดี่ยวและหลาย substring ใช้อัลกอริทึมต่างกัน
- บทความนี้แนะนำแนวคิดของ NFA (non-deterministic finite automata) และบทบาทของมันในเอนจิน regex
- NFA สามารถแปลงเป็นชนิดอื่นได้ และถูกใช้เพื่อสร้าง DFA (deterministic finite automata) เป็นต้น
- บทความนี้ให้ตัวอย่างอย่างละเอียดและคำอธิบายเกี่ยวกับองค์ประกอบของ NFA
- บทความนี้กล่าวถึงการปรับแต่งในคอมไพเลอร์ NFA ตัวใหม่เพื่อลดการใช้ epsilon transition
- คอมไพเลอร์ NFA ตัวใหม่ปรับปรุงการแทน NFA โดยใช้ sparse state ที่รองรับหลายช่วงไบต์
- การปรับแต่งนี้ลด overhead และตัดความจำเป็นของ epsilon transition ออกไป
- NFA แบบ byte-oriented ที่ใช้ในคอมไพเลอร์ก่อนหน้านี้ช้า และต้องคอมไพล์ NFA สำหรับ Unicode และแบบ byte-oriented แยกกัน
- คอมไพเลอร์ NFA ตัวใหม่ผสาน UTF-8 automata เข้าใน NFA แบบ byte-oriented เพื่อจัดการ Unicode class
- คอมไพเลอร์ตัวใหม่ใช้อัลกอริทึมของ Daciuk เพื่อคำนวณ DFA แบบต่ำสุดจากลำดับองค์ประกอบที่เรียงและไม่ซ้อนทับกัน
- การเปลี่ยนสถานะแบบย้อนกลับถูกจัดการด้วยโครงสร้างข้อมูลเฉพาะชื่อ
range trie
- คอมไพเลอร์ NFA ตัวใหม่สร้าง NFA ที่มีสถานะน้อยกว่าและไม่มี epsilon transition เมื่อเทียบกับคอมไพเลอร์เดิม
- สามารถใช้การปรับแต่ง reverse shrink เพื่อลดขนาดของ NFA ลงได้อีก แต่จะเพิ่มเวลาในการ build
- โดยรวมแล้ว คอมไพเลอร์ NFA ตัวใหม่ช่วยเพิ่มประสิทธิภาพและทำให้การจัดการ Unicode class ใน regex ง่ายขึ้น
- บทความนี้พูดถึงประเด็นทางเทคนิคที่เกี่ยวข้องกับ character encoding
- ประเด็นนี้เกี่ยวข้องกับอักขระที่พบไม่บ่อยและการแทนค่าในรูปแบบ encoding อื่น ๆ
- บทความนี้กล่าวถึงอักขระบางตัวและความถี่ของมันใน encoding ที่เกี่ยวข้อง
- บทความนี้เน้นให้เห็นความซับซ้อนและความท้าทายที่อาจเกิดขึ้นจาก character encoding
- บทความนี้อาจน่าสนใจสำหรับวิศวกรซอฟต์แวร์และนักพัฒนาที่ทำงานกับ character encoding
- บทความนี้อภิปรายเทคนิคการปรับแต่ง NFA ในเอนจิน regex
- Thompson NFA เป็นที่รู้กันว่าขยายตัวได้ไม่ดีนักเพราะ epsilon transition
- บทความนี้แนะนำการปรับแต่ง NFA ที่ลด epsilon transition โดยจำกัด alternation ของ literal
- คอมไพเลอร์ NFA ตัวใหม่สร้าง trie ของ literal และแปลงเป็น NFA ที่มี epsilon transition แบบย่อให้น้อยที่สุด
- การปรับแต่งนี้คงลำดับความสำคัญแบบซ้ายสุดก่อน และช่วยเพิ่มประสิทธิภาพการค้นหา
- บทความนี้ยังกล่าวถึงงานในอนาคต เช่น Glushkov NFA และการเก็บ NFA ไว้ในหน่วยความจำแบบ contiguous allocation เดียว
regex crate ของ Rust ใช้เอนจิน regex หลายแบบเพื่อรักษาสมดุลระหว่างความสามารถของฟีเจอร์กับประสิทธิภาพการค้นหา- PikeVM เป็นเอนจิน regex ที่ทรงพลังที่สุดใน crate นี้ และรองรับฟีเจอร์ regex ทั้งหมด
- PikeVM จำลอง NFA
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News