كود قائم على القواعد النحوية

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 4 صور
الموسوعة الحرة
قواعد نحوية خطية (مع رمز البداية ß) للجملة الثانية من إعلان استقلال الولايات المتحدة . كل حرف أزرق يمثل رمزًا غير طرفي ؛ وقد تم الحصول عليها من ضغط الجملة باستخدام gzip .

تُعدّ الشفرات القائمة على القواعد النحوية، أو الضغط القائم على القواعد النحوية، خوارزميات ضغط تعتمد على فكرة بناء قواعد نحوية خالية من السياق (CFG) للسلسلة المراد ضغطها. ومن الأمثلة على ذلك خوارزميات ضغط البيانات الشاملة غير المفقودة . [ 1 ] لضغط سلسلة بياناتx=x1⋯xن{\displaystyle x=x_{1}\cdots x_{n}}، وهو تحويل قائم على القواعد النحويةx{\displaystyle x}إلى قواعد نحوية خالية من السياقجي{\displaystyle G}تُعرف مشكلة إيجاد أصغر قواعد نحوية لتسلسل إدخال ( مشكلة أصغر قواعد نحوية ) بأنها مشكلة صعبة من نوع NP، [ 2 ] لذا تم اقتراح العديد من خوارزميات تحويل القواعد النحوية من وجهتي نظر نظرية وعملية. بشكل عام، القواعد النحوية الناتجةجي{\displaystyle G}يتم ضغطها بشكل أكبر بواسطة مشفرات إحصائية مثل الترميز الحسابي .

أمثلة وخصائص

تُعدّ فئة الشفرات القائمة على القواعد النحوية واسعة النطاق، وتشمل شفرات الكتل ، وخوارزمية مطابقة الأنماط متعددة المستويات (MPM)، [ 3 ] ومتغيرات شفرة ليمبل-زيف للتحليل التزايدي ، [ 4 ] والعديد من خوارزميات الضغط الشاملة الجديدة غير الفاقد للبيانات. وتتميز الشفرات القائمة على القواعد النحوية بشموليتها، إذ يمكنها تحقيق معدل إنتروبيا تقاربياً لأي مصدر ثابت ومستقر ذي أبجدية محدودة.

الخوارزميات العملية

تتوفر برامج الضغط التالية من خلال روابط خارجية.

  • Sequitur [ 5 ] هي خوارزمية ضغط قواعد كلاسيكية تقوم بترجمة نص الإدخال بشكل متسلسل إلى CFG، ثم يتم ترميز CFG الناتج بواسطة مشفر حسابي.
  • خوارزمية Re-Pair [ 6 ] هي خوارزمية جشعة تستخدم استراتيجية الاستبدال الأكثر تكرارًا أولًا. تتميز بأداء ضغط قوي، على الرغم من أن متطلبات مساحة الذاكرة الرئيسية كبيرة جدًا.
  • GLZA ، [ 7 ] الذي يُنشئ قواعد نحوية قابلة للاختزال، أي تحتوي على تكرارات، حيث تكون تكلفة ترميز الإنتروبيا لـ"كتابة" التكرارات أقل من تكلفة إنشاء قاعدة وترميزها بالإنتروبيا لالتقاطها. (بشكل عام، فإن SLG الأمثل للضغط ليس غير قابل للاختزال، وتختلف مشكلة أصغر قواعد نحوية عن مشكلة ضغط SLG الفعلية).

انظر أيضاً

مراجع

  1. ↑ كيفر، جيه سي؛ يانغ، إي-إتش (2000)، "الرموز القائمة على القواعد النحوية: فئة جديدة من رموز المصدر الشاملة غير المفقودة"، معاملات IEEE لنظرية المعلومات ، 46 (3): 737-754 ، Bibcode : 2000ITIT...46..737K ، doi : 10.1109/18.841160
  2. ↑ شاريكار، م.؛ ليمان، إ.؛ ليو، د.؛ بانيغراهي، ر.؛ برابهاراكان، م.؛ ساهي، أ.؛ شيلات، أ. (2005)، "مشكلة أصغر قواعد نحوية"، معاملات IEEE لنظرية المعلومات ، 51 (7): 2554-2576 ، رمز Bibcode : 2005ITIT...51.2554C ، doi : 10.1109/tit.2005.850116 ، S2CID 6900082 
  3. ↑ كيفر، جيه سي؛ يانغ، إي إتش؛ نيلسون، جي؛ كوسمان، بي (2000)، "ضغط شامل بدون فقدان البيانات عبر مطابقة الأنماط متعددة المستويات" ، معاملات IEEE لنظرية المعلومات ، 46 (4): 1227-1245 ، رمز Bibcode : 2000ITIT...46.1227K ، doi : 10.1109/18.850665 ، S2CID 8191526 
  4. ↑ زيف، ج.؛ ليمبل، أ. (1978)، "ضغط التسلسلات الفردية عبر ترميز المعدل المتغير"، معاملات IEEE لنظرية المعلومات ، 24 (5): 530-536 ، Bibcode : 1978ITIT...24..530Z ، doi : 10.1109/TIT.1978.1055934 ، hdl : 10338.dmlcz/142945
  5. ↑ نيفيل-مانينغ، سي جي؛ ويتن، آي إتش (1997)، "تحديد البنية الهرمية في المتتاليات: خوارزمية خطية الوقت"، مجلة أبحاث الذكاء الاصطناعي ، 7 (4): 67-82 ، arXiv : cs/9709102 ، doi : 10.1613/jair.374 ، hdl : 10289/1186 ، S2CID 2957960 
  6. ↑ لارسون، ن. ج.؛ موفات، أ. (2000)، "الضغط غير المتصل بالإنترنت القائم على القاموس" (ملف PDF) ، وقائع معهد مهندسي الكهرباء والإلكترونيات ، 88 (11): 1722-1732 ، رمز Bibcode : 2000IEEEP..88.1722L ، doi : 10.1109/5.892708
  7. ↑ كونراد، كينون جيه؛ ويلسون، بول آر. (2016). "ضغط زيف-ليمبل النحوي: تحقيق نسب ضغط نصية من فئة PPM بسرعة فك ضغط من فئة LZ". مؤتمر ضغط البيانات 2016 (DCC) . ص 586. doi : 10.1109/DCC.2016.119 . ISBN  978-1-5090-1853-6. S2CID 3116024 .