مكتبة تشبه regexp للبحث عن نمط المصفوفة

Question

هل هناك مكتبة (بأي لغة) يمكنها البحث عن أنماط في المصفوفات مثل التعبيرات العادية التي تعمل على الأوتار؟ شيء مثل الانتياجات العادية للمصفوفات ، أو أي طريقة البحث عن نمط المصفوفة؟

Answer 1

إذا لم تكن تعارض استخدام J ، فيمكنك معرفة ما إذا كانت المصفوفتان متساوية باستخدام -: (مطابقة) المشغل. فمثلا:

   X =: 4 3 $ i.12
   X
0  1  2
3  4  5
6  7  8
9 10 11
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X -: X
1
   X -: Y
0

تتمثل إحدى الميزات الرائعة في مشغل المطابقة في أنه يمكنك استخدامه لمقارنة صفائف البعد التعسفي ؛ إذا A هي صفيف 3x3x4 و B هي صفيف 2x1 ، ثم A-:B عائدات 0.

لمعرفة ما إذا كانت المصفوفة عبارة عن مجموعة فرعية من مصفوفة أخرى ، يمكنك استخدام E: (عضو في الفاصل الزمني) مشغل مثل ذلك:

 X =: 2 2 $ 1 2 4 5  
   X
1 2
4 5
   Y =: 4 3 $ (1+i.12)
   Y
 1  2  3
 4  5  6
 7  8  9
10 11 12
   X E. Y
1 0 0
0 0 0
0 0 0
0 0 0

يشير 1 في الجزء العلوي الأيسر من النتيجة إلى أن جزء y يساوي x يحتوي على بكسل معين كركن يديه العلوي. والسبب في ذلك هو أنه قد يكون هناك العديد من النسخ المتداخلة من X مضمنة في Y ، والعلامة فقط على البيكسل واحد يتيح لك رؤية موقع كل بلاط مطابق.

Answer 2

لقد وجدت شيئين: gawk و perl النصي.

إنها مشكلة مختلفة لأن تعبيرات السلسلة العادية تعمل (على سبيل المثال ، sed, grep) خط العمل على حدة على السلاسل أحادية البعد.

ما لم تكن المصفوفات الخاصة بك أحادية البعد (المتجهات أساسا) ، فإن هذه البرامج والخوارزميات التي يستخدمونها لن تعمل.

حظا طيبا وفقك الله!

Answer 3

ما عليك سوى البحث في صفوف النمط في كل صف من مصفوفة الإدخال باستخدام Aho-Corasick (Time O (حجم المصفوفة)). يجب أن تكون النتيجة صغيرة بما يكفي للانضمام إليها بسرعة في النتيجة النهائية.

Answer 4

لا أعتقد أن هناك أي شيء مثل التعبيرات العادية للأبعاد أعلى من 1 ، ولكن إذا كنت ترغب في مطابقة نمط دقيق بدلاً من فئة من الأنماط ، فقد أقترح عليك قراءة الالتفاف (أو بالأحرى الارتباط المتبادل )

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

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