قمزح النص اعتمادا على بعض القواعد المحددة. خوارزمية في C ++

Question

أنا أكتب برنامجا الذي سيقوم بدعم نص الإدخال اعتمادا على بعض القواعد المحددة. أنا أستخدم C ++ لهذا الغرض.

قواعد

Letter 'a' should be converted to token 'V-A'
Letter 'p' should be converted to token 'C-PA'
Letter 'pp' should be converted to token 'C-PPA'
Letter 'u' should be converted to token 'V-U'

هذه مجرد عينة وفي الوقت الفعلي لدي حوالي 500 قواعد مثل هذا. إذا كنت أقدم الإدخال باسم "appu."، يجب أن يلغي مثل"VA + C-PPA + VU". لقد نفذت خوارزمية للقيام بذلك وأرادت التأكد من أنني أفعل الشيء الصحيح.

خوارزمية

سيتم الاحتفاظ بجميع القواعد في ملف XML مع التعيين المقابل إلى الرمز المميز. شيء مثل

<rules>
  <rule pattern="a" token="V-A" />
  <rule pattern="p" token="C-PA" />
  <rule pattern="pp" token="C-PPA" />
  <rule pattern="u" token="V-U" />
</rules>

1 - عند بدء تشغيل التطبيق، اقرأ ملف XML هذا والحفاظ على القيم في "STD :: MAP.". سيكون هذا متاحا حتى نهاية التطبيق (تنفيذ نمط Singleton).

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

3 - استبدل الحرف "أ" من نص الإدخال حيث حصلنا على رمزية لذلك.

4 - كرر الخطوة 2 و 3 مع الأحرف المتبقية في نص الإدخال.

فيما يلي شرح أكثر بساطة للخطوات

input-text = 'appu'
tokens-generated=''

// First iteration
character-to-match = 'a'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ap'
pattern-found = false

tokens-generated = 'V-A'

// since no match found for 'ap', taking the first success and replacing it from input text
input-text = 'ppu'

// second iteration
character-to-match = 'p'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'pp'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ppu'
pattern-found = false

tokens-generated = 'V-A + C-PPA'

// since no match found for 'ppu', taking the first success and replacing it from input text
input-text = 'u'

// third iteration
character-to-match = 'u'
pattern-found = true

tokens-generated = 'V-A + C-PPA + V-U'  // we'r done!

أسئلة

1 - هل هذه الخوارزمية تبدو جيدة لهذه المشكلة أم أنها هناك طريقة أفضل لمعالجة هذه المشكلة؟

2 - إذا كانت هذه هي الطريقة الصحيحة، STD :: MAP هو اختيار جيد هنا؟ أو هل أحتاج إلى إنشاء حاوية الرئيسية / القيمة الخاصة بي؟

3 - هل هناك مكتبة متوفرة والتي يمكنها تزيين السلسلة مثل ما سبق؟

سيكون موضع تقدير أي مساعدة

:)

Answer 1

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

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

---

تحرير: اسمحوا لي أن أشرح هذا قليلا.

أولا، يجب أن أشرح أنني لست على دراية بهؤلاء C ++ std::map, ، ما وراء الاسم، مما يجعل هذا مثالا مثاليا لماذا يتعلم المرء نظرية هذه الأشياء وكذلك تفاصيل مكتبات معينة لغات البرمجة المعينة: ما لم تكن هذه المكتبة إساءة استخدام بشكل سيئ اسم "خريطة" (وهو أمر غير مرجح تماما) ، أخبرني الاسم نفسه كثيرا عن خصائص هيكل البيانات. وأنا أعلم، على سبيل المثال، أن تكون هناك وظيفة، بالنظر إلى مفتاح واحد والخريطة، سيبحث بكفاءة للغاية وإرجاع القيمة المرتبطة بهذا المفتاح، وأن هناك أيضا وظيفة من شأنها أن تعطيك قائمة / صفيف / أيا كانت كل مفاتيح، والتي يمكنك البحث عنها باستخدام الرمز الخاص بك.

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

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

إذن ما تحتاجه حقا ليس خريطة واحدة، ولكن خرائط خرائط الخرائط، كل منها حرف واحد. يجب أن يمنحك بحث عن "P" على المستوى الأعلى خريطة جديدة، مع مفتاحين: p, ، إنتاج C-PPA رمز، و "أي شيء آخر"، وإنتاج C-PA رمزية. هذا هو بنية بنية البيانات الثلاثية.

هل لهذا معنى؟

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

Answer 2

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

2. كنت أستخدم خريطة STD :: معيار بدلا من نظامك الخاص.

3. هناك أدوات مثل lex (أو flex) يمكن أن تستخدم لهذا. ستكون المشكلة ما إذا كان يمكنك تجديد المحلل المعجمي الذي سينشئه عند تغيير مواصفات XML. إذا لم تتغير مواصفات XML في كثير من الأحيان، فقد تتمكن من استخدام الأدوات مثل lex للقيام المسح والمسح أو رسم الخرائط بسهولة أكبر. إذا كانت مواصفات XML يمكن أن تتغير في نزوة تلك التي تستخدم البرنامج، إذن lex ربما أقل ملاءمة.

هناك بعض التحذير - لا سيما lex و flex إنشاء رمز C، بدلا من C ++.

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

Answer 3

الأفضل من ذلك، إذا كنت ستستخدم مكتبة Boost، فهناك دائما مكتبة Tokenizer Boost -> http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html.

Answer 4

يمكنك استخدام Regex (ربما دفعة :: مكتبة Regex). إذا كانت جميع الأنماط هي فقط سلاسل من الحروف، مثل Regex مثل "(A | P | PP | U)" ستجد مباراة جشعة. وبالتالي:

1. قم بتشغيل Regex_Search باستخدام النمط أعلاه لتحديد موقع المباراة التالية
2. قم بتوصيل نص المباراة في MAP الخاص بك STD: للحصول على نص استبدال.
3. اطبع المدخلات المستهلكة غير المتطابقة واستبدال النص إلى إخراجك، ثم كرر 1 على الإدخال المتبقي.

وفعلت.

Answer 5

قد يبدو معقدا بعض الشيء، ولكن الطريقة الأكثر كفاءة للقيام بذلك هي استخدام الرسم البياني لتمثيل الرسم البياني للحالة. في البداية، اعتقدت boost.statechart. سوف يساعد، لكنني أحسب أنه لم يكن مناسبا حقا. يمكن أن تكون هذه الطريقة أكثر كفاءة تستخدم خريطة STD STD STD :: إذا كانت هناك العديد من القواعد، فإن عدد الأحرف المحتملة محدودة وطول النص للقراءة مرتفع للغاية.

على أي حال، باستخدام رسم بياني بسيط:

0) إنشاء الرسم البياني مع قمة "ابدأ"

1) قراءة ملف تكوين XML وإنشاء رؤوس عند الحاجة (الانتقال من "مجموعة من الأحرف" (مثل "PP") إلى واحد إضافي (مثل "PPA")). داخل كل قمة، تخزن جدول انتقالي إلى القمم التالية. إذا اكتمال "نص المفتاح"، مارك قمة كخير وتخزين النص الناتج

2) قراءة النص الآن وتفسرها باستخدام الرسم البياني. ابدأ في قمة "البداية". (*) استخدام الجدول لتفسير حرف واحد والقفز إلى قمة جديدة. إذا لم يتم تحديد قمة جديدة، فيمكن إصدار خطأ. خلاف ذلك، إذا كانت قمة رأسية جديدة نهائية، فقم بطباعة النص الناتج والقفز مرة أخرى لبدء VertEx. العودة إلى (*) حتى لا يوجد نص آخر للتفسير.

يمكنك استخدام boost.graph. لتمثيل الرسم البياني، لكنني أعتقد أنه مجمع للغاية لما تحتاجه. اصنع التمثيل المخصص الخاص بك.