tre
TRE 0.9.0
โครงการนี้กำลังมองหาผู้ดูแล สำหรับผู้เริ่มต้นมีคำขอดึงสองสามข้อรอการตรวจสอบ
แจ้งให้เราทราบที่ [email protected] ถ้าคุณต้องการก้าวขึ้น!
Tre เป็นไลบรารีการจับคู่ Regexp ที่มีน้ำหนักเบามีน้ำหนักเบาและมีประสิทธิภาพพร้อมคุณสมบัติที่น่าตื่นเต้นเช่นการจับคู่โดยประมาณ (ฟัซซี่)
อัลกอริทึมการจับคู่ที่ใช้ใน TRE ใช้เวลากรณีที่เลวร้ายที่สุดเชิงเส้นในระยะเวลาของข้อความที่กำลังค้นหาและเวลาที่เลวร้ายที่สุดกำลังสองในระยะเวลาของการแสดงออกปกติที่ใช้
กล่าวอีกนัยหนึ่งความซับซ้อนของเวลาของอัลกอริทึมคือ O (M^2N) โดยที่ m คือความยาวของการแสดงออกปกติและ n คือความยาวของข้อความ พื้นที่ที่ใช้แล้วยังเป็นกำลังสองตามความยาวของ Regex แต่ไม่ได้ขึ้นอยู่กับสตริงที่ค้นหา พฤติกรรมกำลังสองนี้เกิดขึ้นเฉพาะในกรณีทางพยาธิวิทยาซึ่งอาจหายากมากในทางปฏิบัติ
นี่คือวิธีการทำงานกับรหัสนี้
คุณจะต้องติดตั้งเครื่องมือต่อไปนี้ในระบบของคุณ:
ขั้นแรกเตรียมต้นไม้ เปลี่ยนเป็นรูทของไดเรกทอรีต้นฉบับและเรียกใช้
./utils/autogen.sh
สิ่งนี้จะสร้างสิ่งต่าง ๆ โดยใช้เครื่องมือที่จำเป็นต้องมีเพื่อให้คุณจบลงด้วยต้นไม้ที่สร้างได้
หลังจากนี้คุณสามารถเรียกใช้การกำหนดค่าสคริปต์และสร้าง Tre ได้ตามปกติ:
./configure
make
make check
make install
ในต้นไม้ที่เตรียมไว้คำสั่งนี้จะสร้างซอร์สโค้ด tarball:
./configure && make dist
หรือคุณสามารถวิ่งได้
./utils/build-sources.sh
ซึ่งสร้างแพ็คเกจซอร์สโค้ดและวางไว้ในไดเรกทอรี dist สคริปต์นี้ต้องการคำสั่ง zip ที่ใช้งานได้
TRE ไม่ได้เป็นเพียงการจับคู่ regexp อื่น TRE มีคุณสมบัติบางอย่างที่ไม่ได้อยู่ในการใช้งานที่เข้ากันได้กับ POSIX ฟรีส่วนใหญ่ คุณสมบัติเหล่านี้ส่วนใหญ่ไม่ได้อยู่ในการใช้งานที่ไม่ฟรีเช่นกันสำหรับเรื่องนั้น
การจับคู่รูปแบบโดยประมาณช่วยให้การจับคู่นั้นโดยประมาณนั่นคือช่วยให้การจับคู่ใกล้เคียงกับรูปแบบการค้นหาภายใต้การวัดความใกล้ชิด Tre ใช้การวัดการแก้ไขระยะไกล (หรือที่เรียกว่าระยะทาง Levenshtein) ซึ่งสามารถแทรกตัวอักษรลบหรือแทนที่ในข้อความค้นหาเพื่อให้ได้การจับคู่ที่แน่นอน
การแทรกการลบหรือการทดแทนแต่ละครั้งจะเพิ่มระยะทางหรือค่าใช้จ่ายของการแข่งขัน Tre สามารถรายงานการแข่งขันที่มีค่าใช้จ่ายต่ำกว่าค่าเกณฑ์ที่กำหนด TRE ยังสามารถใช้เพื่อค้นหาการจับคู่ด้วยค่าใช้จ่ายต่ำสุด
TRE รวมถึงรุ่นของเครื่องมือบรรทัดคำสั่ง AgREP (โดยประมาณ GREP) สำหรับการจับคู่ regexp โดยประมาณในรูปแบบของ GREP ซึ่งแตกต่างจากการใช้งาน agrep อื่น ๆ (เช่นเดียวกับ Sun Wu และ Udi Manber จาก University of Arizona) Tre AgREP ช่วยให้ regexps เต็มความยาวใด ๆ ข้อผิดพลาดจำนวนมากและค่าใช้จ่ายที่ไม่สม่ำเสมอสำหรับการแทรกการลบและการทดแทน
Posix กำหนดพฤติกรรมของฟังก์ชั่น regexp อย่างแม่นยำ Tre พยายามที่จะปฏิบัติตามข้อกำหนดเหล่านี้อย่างเคร่งครัดที่สุด TRE จะส่งคืนการจับคู่ที่ถูกต้องเสมอสำหรับ Subpatterns เช่น การใช้งานอื่น ๆ น้อยมากทำสิ่งนี้ได้อย่างถูกต้อง ในความเป็นจริงการใช้งานอื่น ๆ เท่านั้นนอกเหนือจาก Tre ที่ฉันตระหนักถึง (ฟรีหรือไม่) ที่ทำให้ถูกต้องคือ Rx โดย Tom Lord, Regex ++ โดย John Maddock และ AT&T AST Regex โดย Glenn Fowler และ Doug McIlroy
Tre มาตรฐานพยายามที่จะปฏิบัติตามคือ IEEE STD 1003.1-2001 หรือข้อมูลจำเพาะฐานกลุ่มเปิดฉบับที่ 6 โดยทั่วไปเรียกว่า "posix" ชิ้นส่วนที่เกี่ยวข้องเป็นข้อกำหนดพื้นฐานในการแสดงออกปกติ (และเหตุผล) และคำอธิบายของ regcomp() API
สำหรับการสำรวจที่ยอดเยี่ยมเกี่ยวกับการจับคู่ Posix regexp ดูหน้า Testregex โดย Glenn Fowler จาก AT&T Labs Research
เนื่องจากอัลกอริทึมการจับคู่ที่ใช้ใน TRE เวลาสูงสุดที่ใช้โดยการโทร regexec() ใด ๆ จึงเป็นสัดส่วนโดยตรงกับความยาวของสตริงค้นหา มีข้อยกเว้นหนึ่งข้อ: หากใช้การอ้างอิงย้อนกลับการจับคู่อาจใช้เวลาที่เพิ่มขึ้นอย่างทวีคูณด้วยความยาวของสตริง นี่เป็นเพราะการจับคู่การอ้างอิงกลับเป็นปัญหาที่สมบูรณ์ของ NP และเกือบจะต้องใช้เวลาชี้แจงในการจับคู่ในกรณีที่เลวร้ายที่สุด
การโทร regexec() ไม่เคยจัดสรรหน่วยความจำจากกอง TRE จัดสรรหน่วยความจำทั้งหมดที่ต้องการในระหว่างการโทร regcomp() และพื้นที่ทำงานชั่วคราวบางส่วนจากเฟรมสแต็กตลอดระยะเวลาของการโทร regexec() ปริมาณของพื้นที่ชั่วคราวที่จำเป็นคือคงที่ในระหว่างการจับคู่และไม่ได้ขึ้นอยู่กับสตริงที่ค้นหา สำหรับ Regexps ที่มีขนาดที่สมเหตุสมผลต้องการหน่วยความจำที่จัดสรรแบบไดนามิกน้อยกว่า 50k ในระหว่างการโทร regcomp() น้อยกว่า 20k สำหรับบัฟเฟอร์รูปแบบที่รวบรวมและน้อยกว่าสองกิโลไบต์ของพื้นที่ทำงานชั่วคราวจากเฟรมสแต็กในระหว่างการโทร regexec() ไม่มีการแลกเปลี่ยนเวลา / หน่วยความจำ Tre ยังมีขนาดเล็กในรหัส การเชื่อมโยงกับ TRE แบบคงที่จะเพิ่มขนาดที่ใช้งานได้น้อยกว่า 30K (GCC-3.2, X86, GNU/Linux)
TRE รองรับชุดอักขระ multibyte สิ่งนี้ทำให้สามารถใช้ Regexps ได้อย่างราบรื่นเช่นสถานที่ตั้งของญี่ปุ่น Tre ยังให้ API ตัวละครที่กว้าง
TRE ให้ APIs ซึ่งอนุญาตให้มีอักขระบอรี่ศูนย์ทั้งใน Regexps และ Strings ค้นหา API มาตรฐานไม่สามารถใช้ได้อย่างง่ายดายเช่นค้นหาคำที่พิมพ์ได้จากข้อมูลไบนารี (แม้ว่าจะเป็นไปได้ด้วยการแฮ็คบางอย่าง) การค้นหารูปแบบที่มีเลขฐานสองที่ฝังอยู่เป็นไปไม่ได้เลยด้วย API มาตรฐาน
Tre ปลอดภัยอย่างสมบูรณ์ ฟังก์ชั่นที่ส่งออกทั้งหมดจะกลับเข้ามาอีกครั้งและวัตถุ RegeXP ที่รวบรวมได้เดียวสามารถใช้พร้อมกันในหลายบริบท เช่นใน main() และตัวจัดการสัญญาณหรือในหลายเธรดของแอปพลิเคชันมัลติเธรด
Tre สามารถพกพาได้ในหลายแพลตฟอร์ม ด้านล่างนี้เป็นตารางของแพลตฟอร์มและคอมไพเลอร์ที่ใช้ในการพัฒนาและทดสอบ TRE:
| แพลตฟอร์ม | ผู้ประกอบการ |
|---|---|
| FreeBSD 14.1 | เสียงดัง 18 |
| Ubuntu 22.04 | GCC 11 |
| macos 14.6 | เสียงดัง 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
TRE ควรรวบรวมโดยไม่มีการเปลี่ยนแปลงบนแพลตฟอร์มที่มีลักษณะคล้าย Posix ที่ทันสมัยส่วนใหญ่และสามารถพกพาไปยังแพลตฟอร์มใด ๆ ได้อย่างง่ายดายด้วยการใช้งาน C โฮสต์
ขึ้นอยู่กับแพลตฟอร์มคุณอาจต้องติดตั้ง libutf8 เพื่อรับการรองรับชุดอักขระที่กว้างและชุดอักขระ multibyte
TRE ได้รับการปล่อยตัวภายใต้ใบอนุญาตซึ่งเป็นหลักเช่นเดียวกับใบอนุญาต“ 2 ประโยค” BSD ที่ใช้ใน NetBSD ดูใบอนุญาตไฟล์สำหรับรายละเอียด
ขณะนี้มีคุณสมบัติสองประการทั้งสองเกี่ยวข้องกับองค์ประกอบการรวบรวมซึ่งขาดหายไปจากการปฏิบัติตาม POSIX 100% นี่คือ:
สนับสนุนองค์ประกอบการรวบรวม (เช่น [[.<X>.]] โดยที่ <X> เป็นองค์ประกอบการรวบรวม) มันเป็นไปไม่ได้ที่จะสนับสนุนองค์ประกอบการรวบรวมหลายตัวละครอย่างต่อเนื่องเนื่องจาก POSIX ไม่ได้กำหนดวิธีในการตรวจสอบว่าลำดับตัวละครเป็นองค์ประกอบการรวบรวมหลายตัวละครหรือไม่
รองรับคลาสที่เท่าเทียมกันเช่น [[=<X>=]] โดยที่ <X> เป็นองค์ประกอบการรวบรวม คลาสที่เท่าเทียมกันตรงกับอักขระใด ๆ ที่มีน้ำหนักการเปรียบเทียบหลักเช่น <X> อีกครั้ง POSIX ไม่มีกลไกแบบพกพาสำหรับการกำหนดน้ำหนักการเปรียบเทียบหลักขององค์ประกอบการรวบรวม
โปรดทราบว่าการใช้งาน regexp แบบพกพาอื่น ๆ ไม่สนับสนุนองค์ประกอบที่รวบรวมได้เช่นกัน ข้อยกเว้นเดียวคือ Regex ++ ซึ่งมาพร้อมกับฐานข้อมูลของตัวเองสำหรับการรวบรวมองค์ประกอบสำหรับสถานที่ต่าง ๆ การสนับสนุนสำหรับองค์ประกอบการรวบรวมและคลาสที่เท่าเทียมกันยังไม่ได้รับการร้องขออย่างกว้างขวางและไม่สูงมากในรายการสิ่งที่ต้องทำในขณะนี้
นี่คือคุณสมบัติอื่น ๆ ที่ฉันวางแผนจะนำไปใช้จริงในไม่ช้าตอนนี้:
ส่วนขยาย GNU ที่หายไปทั้งหมดเปิดใช้งานใน GNU regex เช่น [[:<:]] และ [[:>:]]
ธง REG_SHORTEST regexec() สำหรับการคืนการแข่งขันที่สั้นที่สุดแทนการจับคู่ที่ยาวที่สุด
ไวยากรณ์ที่เข้ากันได้กับ Perl:
[:^class:] ตรงกับอะไรนอกจากตัวละครในชั้นเรียน โปรดทราบว่า [^[:class:]] ทำงานแล้วนี่จะเป็นเพียงชวเลขที่สะดวก
A จับคู่เฉพาะที่เริ่มต้นของสตริง
Z จับคู่เฉพาะตอนท้ายของสตริงหรือก่อนหน้าใหม่ในตอนท้าย
z จับคู่เฉพาะตอนท้ายของสตริง
l ตัวพิมพ์เล็กถัดไปถ่าน (คิด VI)
u uppercase ถัดไปถ่าน (คิด vi)
L ตัวพิมพ์เล็กจนถึง E (คิด vi)
U uppercase จนถึง E (คิด vi)
(?=pattern) การยืนยันล่วงหน้าเป็นศูนย์ความกว้าง
(?!pattern) การยืนยันการมองเห็นล่วงหน้าเชิงลบแบบไม่มีความกว้าง
(?<=pattern) การยืนยันรูปลักษณ์ที่เป็นบวกเป็นศูนย์
(?<!pattern) การยืนยันรูปลักษณ์เชิงลบที่มีความกว้างเป็นศูนย์
เอกสารโดยเฉพาะอย่างยิ่ง include/tre/tre.h คุณสมบัติที่ไม่เป็นมาตรฐานของ TRE เช่นการจับคู่โดยประมาณเป็นงานที่กำลังดำเนินการอยู่ อาจให้คำแนะนำเพิ่มเติมบางอย่างหากคุณพอใจกับซอร์สโค้ด C
