tre
TRE 0.9.0
هذا المشروع يبحث عن المشرفين. بالنسبة للمبتدئين ، هناك بعض طلبات السحب في انتظار المراجعة.
اسمحوا لي أن أعرف في [email protected] إذا كنت ترغب في تصعيد!
TRE هي مكتبة مطابقة لتوافق POSIX خفيفة الوزن وقوية وفعالة مع بعض الميزات المثيرة مثل مطابقة تقريبية (غامضة).
تستخدم خوارزمية المطابقة المستخدمة في 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 من جامعة أريزونا) ، يسمح TRE Agrep بإعادة التهيئة الكاملة من أي طول ، وأي عدد من الأخطاء ، والتكاليف غير الموحدة للإدراج والحذف والاستبدال.
يحدد POSIX سلوك وظائف regexp بدقة. TRE يحاول أن تتوافق مع هذه المواصفات بشكل صارم قدر الإمكان. TRE يعيد دائمًا المباريات الصحيحة للفرع ، على سبيل المثال. عدد قليل جدا من التطبيقات الأخرى تفعل ذلك بشكل صحيح. في الواقع ، فإن التطبيقات الأخرى الوحيدة الأخرى إلى جانب TRE على دراية بها (مجانية أم لا) التي تحصل عليها بشكل صحيح هي RX بواسطة Tom Lord و REGEX ++ بواسطة John Maddock و AT&T AST REGEX من Glenn Fowler و Doug McIlroy.
تحاول TRE القياسية أن تتوافق مع IEEE STD 1003.1-2001 ، أو مشكلة مواصفات قاعدة المجموعة المفتوحة ، والتي يشار إليها عادة باسم "posix". الأجزاء ذات الصلة هي المواصفات الأساسية حول التعبيرات العادية (والأساس المنطقي) ووصف API regcomp() .
للحصول على استطلاع ممتاز حول Posix Regexp Matchers ، راجع صفحات TestRegex من Glenn Fowler من AT&T Labs Research.
نظرًا لخوارزمية المطابقة المستخدمة في TRE ، فإن الحد الأقصى للوقت الذي يستهلكه أي مكالمة regexec() يتناسب بشكل مباشر مع طول السلسلة التي تم تفتيشها. هناك استثناء واحد: إذا تم استخدام المراجع الخلفية ، فقد يستغرق المطابقة وقتًا كبيرًا مع طول السلسلة. وذلك لأن مطابقة المراجع مرة أخرى هي مشكلة كاملة NP ، وبالتأكيد يتطلب وقتًا أسيًا للمطابقة في أسوأ الحالات.
مكالمة regexec() لا تخصص الذاكرة أبدًا من الكومة. يخصص TRE جميع الذاكرة التي يحتاجها أثناء مكالمة regcomp() ، وبعض مساحة العمل المؤقتة من إطار المكدس طوال مدة مكالمة regexec() . كمية المساحة المؤقتة المطلوبة ثابتة أثناء المطابقة ولا تعتمد على السلسلة التي تم تفتيشها. بالنسبة إلى regexps ذات الحجم المعقول ، يحتاج TRE إلى أقل من 50 ألفًا من الذاكرة المخصصة ديناميكيًا أثناء مكالمة regcomp() ، وأقل من 20 ألفًا لمخزن المؤسسة النمطية المترجمة ، وأقل من كيلوغرام من مساحة العمل المؤقتة من إطار المكدس أثناء مكالمة regexec() . لا يوجد وقت / مفاضلة الذاكرة. TRE صغير أيضا في حجم الرمز. يزيد الارتباط بشكل ثابت بـ TRE من الحجم القابل للتنفيذ أقل من 30K (GCC-3.2 ، x86 ، GNU/Linux).
TRE يدعم مجموعات الأحرف متعددة الفئران. هذا يجعل من الممكن استخدام regexps بسلاسة مع ، على سبيل المثال ، اللغات اليابانية. يوفر TRE أيضًا واجهة برمجة تطبيقات شخصية واسعة.
يوفر TRE واجهات برمجة التطبيقات التي تسمح بأحرف صفر ثنائية في كل من regexps والسلاسل التي تم تفتيشها. لا يمكن استخدام واجهة برمجة التطبيقات القياسية بسهولة ، على سبيل المثال ، البحث عن كلمات قابلة للطباعة من البيانات الثنائية (على الرغم من أنها ممكنة مع بعض القرصنة). البحث عن الأنماط التي تحتوي على أصفار ثنائية مضمنة غير ممكن على الإطلاق مع واجهة برمجة التطبيقات القياسية.
TRE هو موضوع آمن تماما. يتم إعادة إدخال جميع الوظائف التي تم تصديرها ، ويمكن استخدام كائن RegexP المترجم واحد في وقت واحد في سياقات متعددة ؛ على سبيل المثال في main() ومعالج الإشارة ، أو في العديد من مؤشرات الترابط من تطبيق متعدد مؤشرات الترابط.
TRE محمول عبر منصات متعددة. فيما يلي جدول من المنصات والمترجمين المستخدمة لتطوير واختبار TRE:
| منصة | المترجم |
|---|---|
| Freebsd 14.1 | Clang 18 |
| أوبونتو 22.04 | GCC 11 |
| ماكوس 14.6 | Clang 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
يجب أن يتم تجميع TRE دون تغييرات على معظم المنصات الحديثة التي تشبه POSIX ، وأن تكون محمولة بسهولة إلى أي منصة مع تطبيق C المستضافة.
اعتمادًا على النظام الأساسي ، قد تحتاج إلى تثبيت libutf8 للحصول على دعم مجموعة أحرف واسعة من شخصيات متعددة.
يتم إصدار TRE بموجب ترخيص هو نفس ترخيص "Clause" على غرار BSD المستخدم في NetBsD. راجع ترخيص الملف للحصول على التفاصيل.
يوجد حاليًا ميزتان ، سواء فيما يتعلق بالعناصر المتجمعية ، مفقودًا من الامتثال بنسبة 100 ٪ POSIX. هذه هي:
دعم عناصر التجميع <X> على سبيل المثال [[.<X>.]] لا يمكن دعم عناصر التجميع متعددة الأحرف بشكل كبير ، نظرًا لأن POSIX لا تحدد طريقة لتحديد ما إذا كان تسلسل الأحرف عنصر تجميع متعدد الحواس أم لا.
دعم فئات التكافؤ ، على سبيل المثال [[=<X>=]] ، حيث <X> هو عنصر تجميع. يطابق فئة التكافؤ أي حرف له نفس وزن الترتيب الأساسي مثل <X> . مرة أخرى ، لا توفر Posix أي آلية محمولة لتحديد وزن الترتيب الأساسي لعنصر التجميع.
لاحظ أن تطبيقات REGEXP الأخرى المحمولة لا تدعم العناصر المجمعة أيضًا. الاستثناء الفردي هو Regex ++ ، والذي يأتي مع قاعدة البيانات الخاصة به لجمع العناصر لمجموعة مختلفة. لم يتم طلب دعم عناصر التجميع ودروس التكافؤ على نطاق واسع وليس على مستوى أعلى في قائمة TODO في الوقت الحالي.
هذه ميزات أخرى أخطط لتنفيذها بشكل حقيقي قريبًا الآن:
تم تمكين جميع ملحقات GNU المفقودة في GNU Regex ، مثل [[:<:]] و [[:>:]] .
علامة REG_SHORTEST regexec() لإعادة أقصر مباراة بدلاً من أطول مباراة.
بناء الجملة المتوافق مع بيرل:
[:^class:] يطابق أي شيء سوى الشخصيات في الفصل. لاحظ أن [^[:class:]] يعمل بالفعل ، سيكون هذا مجرد اختصار للراحة.
A تطابق فقط في بداية السلسلة.
Z تطابق فقط في نهاية السلسلة ، أو قبل خط جديد في النهاية.
z تطابق فقط في نهاية السلسلة.
l sumrase char التالي (فكر VI).
u الكبير القادم char (فكر السادس).
L صغير حتى E (فكر vi).
U الكبير حتى E (فكر vi).
(?=pattern) صفر عرض إيجابي مؤثرات.
(?!pattern) Zero-Width نظرة سلبية النظر.
(?<=pattern) صفر عرض إيجابي يؤكد behind.
(?<!pattern) Zero-Width نظرة سلبية.
الوثائق خاصة بالنسبة للميزات غير القياسية لـ include/tre/tre.h ، مثل المطابقة التقريبية ، هي عمل مستمر (مع تعريف "التقدم" بشكل فضفاض ...) إذا كنت ترغب في العثور قد تقدم بعض التلميحات الإضافية إذا كنت مرتاحًا لرمز المصدر C.
