تعقيد استبدال Regex

Question

لم أحصل على الجواب على هذا في أي مكان.ما مدى تعقيد وقت التشغيل لمطابقة Regex والاستبدال؟

يحرر:أنا أعمل في بايثون.ولكن أود أن أعرف بشكل عام عن اللغات/الأدوات الأكثر شيوعًا (Java، Perl، sed).

Answer 1

من موقف نظري بحت:

سيكون التنفيذ الذي أعرفه هو بناء جهاز آلي محدد محدد للتعرف على التعبير العادي.يتم ذلك في O(2^m)، m هو حجم التعبير العادي، باستخدام خوارزمية قياسية.بمجرد إنشاء هذا، فإن تشغيل سلسلة من خلاله يكون خطيًا في طول السلسلة - O(n)، n هو طول السلسلة.يجب أن يكون الاستبدال في التطابق الموجود في السلسلة وقتًا ثابتًا.

بشكل عام، أفترض أن O(2^m + n).

Answer 2

معلومات نظرية أخرى ذات أهمية محتملة.

من أجل الوضوح، افترض التعريف القياسي للتعبير العادي

http://en.wikipedia.org/wiki/Regular_language

من نظرية اللغة الرسمية.من الناحية العملية ، هذا يعني أن مواد البناء الوحيدة هي رموز أبجدية ، ومشغلي المسلسل ، والتناوب ، وإغلاق كليني ، إلى جانب الوحدة والثوابت الصفرية (التي تظهر لأسباب نظرية جماعية).عمومًا ، من الجيد عدم زيادة تحميل هذا المصطلح على الرغم من الممارسة اليومية في اللغات البرمزية التي تؤدي إلى الغموض.

هناك بناء NFA يحل مشكلة المطابقة للتعبير العادي R ونص إدخال T في O (| r | | t |) وقت و O (| r |) ، حيث |-| هي وظيفة الطول.تم تحسين هذه الخوارزمية بشكل أكبر بواسطة مايرز

http://doi.acm.org/10.1145/128749.128755

إلى تعقيد الزمان والمكان O(|r| |t| / log |t|) باستخدام قوائم العقدة الآلية ونموذج الروس الأربعة.يبدو أن هذا النموذج تم تسميته على اسم أربعة رجال روسيين كتبوا ورقة رائدة غير متصلة بالإنترنت.ومع ذلك ، يتم توضيح النموذج في ملاحظات محاضرة البيولوجيا الحسابية هذه

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

أجد أنه من المضحك تسمية نموذج برقم وجنسية المؤلفين بدلاً من أسمائهم الأخيرة.

مشكلة المطابقة للتعبيرات المنتظمة مع الإضافات المضافة هي NP-COMPLETE ، والتي أثبتت AHO من قبل AHO

http://portal.acm.org/citizen.cfm?id=114877

عن طريق التخفيض من مشكلة الغطاء الرأسي وهي مشكلة كلاسيكية كاملة NP.

لمطابقة التعبيرات المنتظمة مع Backreferences حتميًا ، يمكننا استخدام التراجع (لا يختلف عن محرك Perl Regex) لتتبع الكلمات الفرعية المحتملة لنص الإدخال T الذي يمكن تعيينه للمتغيرات في R.لا يوجد سوى o (| t |^2) الكلمات الفرعية التي يمكن تعيينها لأي متغير واحد في r.إذا كانت هناك متغيرات N في R ، فهناك O (| t |^2n) الواجبات المحتملة.بمجرد إصلاح التخصيص الفردي للمتغيرات ، تنخفض المشكلة إلى مطابقة التعبير العادي العادي.لذلك فإن أسوأ التعقيد لمطابقة التعبيرات العادية مع backreferences هو O (| t |^2n).

لاحظ ومع ذلك ، فإن التعبيرات العادية مع Backreferences لم يتم إعادة إيجادها بعد.

خذ ، على سبيل المثال ، رمز "لا تهتم" بصرف النظر عن أي عوامل أخرى.هناك العديد من الخوارزميات متعددة الحدود التي تقرر ما إذا كانت مجموعة من الأنماط تطابق نص الإدخال.على سبيل المثال، كوتشيروف وروسينوفيتش

http://dx.doi.org/10.1007/3-540-60044-2_46

حدد النمط ككلمة w_1@w_2@...@w_n حيث كل w_i عبارة عن كلمة (ليست تعبيرًا عاديًا) و"@" عبارة عن رمز متغير الطول "لا أهتم" غير موجود في أي من w_i.أنها تستمد O ((| t | + | p |) log | p |) خوارزمية لمطابقة مجموعة من الأنماط p ضد نص الإدخال t ، حيث | t | هو طول النص ، و | p | هو طول كل الكلمات في P.

سيكون من المثير للاهتمام معرفة كيفية دمج تدابير التعقيد هذه وما هو مقياس التعقيد لمشكلة المطابقة للتعبيرات المنتظمة مع REARFERENS ، "لا تهتم" وغيرها من الميزات المثيرة للاهتمام للتعبيرات العادية.

للأسف، لم أقل كلمة واحدة عن بايثون ...:)

Answer 3

يعتمد على ما تحدده بواسطة regex.إذا سمحت لمشغلي التسلسل والبديل وKleene-star، فقد يكون الوقت في الواقع O(m*n+m), ، أين m هو حجم regex و n هو طول السلسلة.يمكنك القيام بذلك عن طريق إنشاء NFA (وهو خطي في m)، ثم محاكاتها من خلال الحفاظ على مجموعة الحالات التي أنت فيها وتحديثها (in O(m)) لكل حرف من المدخلات.

الأشياء التي تجعل تحليل regex صعبًا:

• الأقواس والمراجع الخلفية:لا يزال الالتقاط مقبولًا مع الخوارزمية المذكورة أعلاه، على الرغم من أنه قد يزيد من التعقيد، لذلك قد يكون غير ممكن.تزيد المراجع الخلفية من قوة التعرف على التعبير العادي، كما أن صعوبته جيدة
• النظرة الإيجابية إلى الأمام:هو مجرد اسم آخر للتقاطع، مما يزيد من تعقيد الخوارزمية المذكورة أعلاه O(m^2+n)
• النظرة السلبية للمستقبل:كارثة لبناء الإنسان الآلي (O(2^m), ، ربما PSPACE كاملة).ولكن لا يزال من الممكن التعامل مع الخوارزمية الديناميكية بشيء من هذا القبيل O(n^2*m)

لاحظ أنه مع التنفيذ الملموس، قد تتحسن الأمور أو تسوء.كقاعدة عامة، يجب أن تكون الميزات البسيطة سريعة بما فيه الكفاية، ولا لبس فيها (على سبيل المثال.لا يشبه a*a*) التعابير المنطقية أفضل.

Answer 4

للتعمق في إجابة المؤسسة، بالنسبة لبناء الإنسان الآلي، O(2^m) هي الحالة الأسوأ، على الرغم من أنها تعتمد حقًا على شكل التعبير العادي (بالنسبة لتعبير بسيط جدًا يطابق كلمة، فهو موجود في O( م)، وذلك باستخدام على سبيل المثال خوارزمية نوث-موريس-برات).

Answer 5

يعتمد على التنفيذ.ما اللغة / المكتبة / الفصل؟قد تكون هناك حالة أفضل، ولكنها ستكون محددة جدًا لعدد الميزات الموجودة في التنفيذ.

Answer 6

يمكنك مقايضة المساحة بالسرعة من خلال بناء إنسان آلي محدود غير محدد بدلاً من DFA.يمكن اجتياز هذا في الوقت الخطي.بالطبع، في أسوأ الحالات قد يحتاج هذا إلى مساحة O(2^m).أتوقع أن تكون المقايضة تستحق العناء.

Answer 7

إذا كنت تريد المطابقة والاستبدال، فهذا يعني التجميع والمراجع الخلفية.

فيما يلي مثال لـ Perl حيث يمكن استخدام التجميع والمراجع الخلفية لحل مشكلة NP كاملة: http://perl.plover.com/NPC/NPC-3SAT.html

هذا (إلى جانب بعض الحكايات النظرية الأخرى) يعني أن استخدام التعبيرات العادية للمطابقة والاستبدال هو NP كامل.

لاحظ أن هذا يختلف عن التعريف الرسمي للتعبير العادي - الذي ليس لديه فكرة التجميع - ويتطابق في زمن كثير الحدود كما هو موضح في الإجابات الأخرى.