في RegEx، كيف يمكنك العثور على سطر لا يحتوي على أكثر من 3 أحرف فريدة؟

Question

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

هو موضع تقدير كل المساعدة.

(أنا أكتب البرنامج النصي بلغة PHP، إذا كان ذلك يساعد)

Answer 1

ربما سيعمل هذا:

preg_match("/^(.)\\1*(.)?(?:\\1*\\2*)*(.)?(?:\\1*\\2*\\3*)*$/", $string, $matches);
// aaaaa:Pass
// abababcaaabac:Pass
// aaadsdsdads:Pass
// aasasasassa:Pass
// aasdasdsadfasf:Fail

الشرح:

/
 ^                 #start of string
 (.)               #match any character in group 1
 \\1*              #match whatever group 1 was 0 or more times
 (.)?              #match any character in group 2 (optional)
 (?:\\1*\\2*)*     #match group 1 or 2, 0 or more times, 0 or more times 
                   #(non-capture group)
 (.)?              #match any character in group 3 (optional)
 (?:\\1*\\2*\\3*)* #match group 1, 2 or 3, 0 or more times, 0 or more times
                   #(non-capture group)
 $                 #end of string
/

فائدة إضافية، $matches[1], [2], [3] سوف تحتوي على الأحرف الثلاثة التي تريدها.يبحث التعبير العادي عن الحرف الأول، ثم يخزنه ويطابقه حتى يتم العثور على شيء آخر غير ذلك الحرف، ويلتقطه كحرف ثانٍ، ويطابق أيًا من هذين الحرفين أكبر عدد ممكن من المرات، ويلتقط الحرف الثالث، و يطابق الثلاثة حتى تفشل المباراة أو تنتهي السلسلة وينجح الاختبار.

يحرر

سيكون هذا التعبير العادي أسرع بكثير بسبب الطريقة التي يعمل بها محرك التحليل والتتبع العكسي، اقرأ إجابة بوبنس للحصول على الشرح:

/^(.)\\1*(?:(.)(?:\\1|\\2)*(?:(.)(?:\\1|\\2|\\3)*)?)?$/

Answer 2

والتعبيرات المنتظمة تحسين ممارسة وقت ممتع للأطفال! أخذ التعابير المنطقية gnarf باعتبارها نقطة الانطلاق:

^(.)\1*(.)?(?:\1*\2*)*(.)?(?:\1*\2*\3*)*$

ولقد لاحظت أن هناك ومتداخلة ومتتابعة الصورة * هنا، والذي يمكن أن يسبب الكثير من التراجع. على سبيل المثال في "abcaaax 'أنها سوف نحاول أن تتطابق هذه السلسلة الأخيرة من" وباعتبارها واحدة \ 1 * طول 3، \ 1 * طول اثنين تليها واحد \ 1، \ 1 تليها طول 2 \ 1 *، أو ثلاثة أيام مباراة واحدة \ 1S. أن المشكلة تزداد سوءا عندما يكون لديك سلاسل أطول، وخصوصا عندما بسبب التعبير المعتاد لا يوجد شيء وقف \ 1 من كونها نفس الحرف ك \ 2.

^(.)\1*(.)?(?:\1|\2)*(.)?(?:\1|\2|\3)*$

وكان هذا أكثر من ضعفي الأصلي، والاختبار على المنظر PCRE بايثون. (انها أسرع من إعداد عليه في PHP، آسف).

وهذا لا يزال لديه مشكلة في أن (.)? يمكن أن تتطابق شيء، ومن ثم الاستمرار في بقية المباراة. سوف \1|\2 لا يزال تطابق \ 1 حتى إذا لم يكن هناك \ 2 للمباراة، مما أدى إلى التراجع المحتمل في محاولة لتقديم \1|\2 و\1|\2|\3 بنود في وقت سابق عندما لا يمكن أن يؤدي إلى المباراة. هذا يمكن حلها عن طريق تحريك optionalness ? حول مجمل بنود زائدة:

^(.)\1*(?:(.)(?:\1|\2)*(?:(.)(?:\1|\2|\3)*)?)?$

وكان هذا أسرع مرتين مرة أخرى.

لا تزال هناك مشكلة محتملة في أن أيا من \ 1 \ 2 و \ 3 يمكن أن يكون نفس الطابع، مما يمكن أن يسبب المزيد من التراجع عندما لا يتطابق مع التعبير. وهذا من شأنه إيقافها باستخدام lookahead السلبي لعدم تطابق الحرف السابق:

^(.)\1*(?:(?!\1)(.)(?:\1|\2)*(?:(?!\1|\2)(.)(?:\1|\2|\3)*)?)?$

ولكن في بيثون مع بلدي بيانات اختبار عشوائي أنا لم يلاحظوا تسريع كبير من هذا. قد تختلف المسافة المقطوعة في PHP تعتمد على بيانات الاختبار، ولكن قد يكون جيدا بما فيه الكفاية بالفعل. غيور مطابقة (* +) قد ساعدت إذا كان هذا متاح هنا.

ولا التعابير المنطقية أداء أفضل من البديل أسهل للقراءة لبيثون:

len(set(s))<=3

وأسلوب مماثل في PHP ربما يكون مع count_chars :

strlen(count_chars($s, 3))<=3

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

وذلك أساسا أنا مجرد إهدار تماما وقتي تافه مع regexes. لا تضيعوا وقتكم، والبحث عن طرق سلسلة بسيطة أولا قبل اللجوء إلى REGEX!

Answer 3

وفي التعرض لخطر الإصابة downvoted، وسوف أقترح ليس المقصود التعابير العادية للتعامل مع هذا الوضع.

ويمكنك تطابق حرف أو مجموعة من الأحرف، ولكن لا يمكن أن يكون ذلك تذكر ما حرف من مجموعة تم العثور بالفعل على استبعاد تلك من مزيد من المباراة.

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

Answer 4

وبالنسبة لي - كمبرمج مع المعرض، ما يكفي من المعرفة التعبير العادية هذه الأصوات ليس مثل المشكلة التي يمكن أن تحل باستخدام التعبير العادي فقط

والأرجح أنك سوف تحتاج إلى بناء هيكل البيانات الرئيسية hashMap / مجموعة: قيمة حرف: العد وتكرار ملف نص كبير، وإعادة بناء الخريطة للحصول على كل سطر. في كل حرف جديد معرفة ما اذا كان عدد الأحرف اجه بالفعل هو 2، إذا كان الأمر كذلك، انتقل السطر الحالي.

ولكن ايم حريصة على أن يتفاجأ إذا كان أحد القراصنة REGEXP جنون سيأتي إلى حل.