گرامر خط مستقیم (SLG) چیست؟
گرامر خط مستقیم (که گاهی با اختصار SLG شناخته میشود) نوعی گرامر رسمی است که دقیقاً یک رشته را تولید میکند. به همین دلیل، این گرامرها دارای دو ویژگی کلیدی هستند:
- عدم انشعاب: هر نماد غیرپایانی (non-terminal) تنها یک قانون تولید مرتبط دارد.
- عدم تکرار (حلقه): اگر نماد غیرپایانی A در مشتق (derivation) نماد B ظاهر شود، آنگاه B نمیتواند در مشتق A ظاهر شود.
کاربردها
گرامرهای خط مستقیم کاربرد فراوانی در توسعه الگوریتمهایی دارند که مستقیماً بر روی ساختارهای فشرده (بدون نیاز به بازگشایی اولیه) اجرا میشوند.
SLG ها در زمینههایی مانند:
- پیچیدگی کولموگوروف (Kolmogorov complexity)
- فشردهسازی داده بدون اتلاف (Lossless data compression)
- کشف ساختار (Structure discovery)
- ساختارهای داده فشرده (Compressed data structures)
مورد توجه هستند.
مسئله یافتن گرامری با کمترین اندازه که یک رشته معین را تولید کند، مسئله کوچکترین گرامر نامیده میشود (که معادل یافتن یک گرامر مستقل از متن یا SLG است).
گرامرهای خط مستقیم (به طور دقیقتر: گرامرهای مستقل از متن خط مستقیم) را میتوان به گرامرهای درختی مستقل از متن خط مستقیم تعمیم داد. نوع دوم به طور مؤثری برای فشردهسازی درختان قابل استفاده است.
تعریف رسمی
یک گرامر مستقل از متن G، یک SLG محسوب میشود اگر:
- برای هر نماد غیرپایانی N، حداکثر یک قانون تولید وجود داشته باشد که N در سمت چپ آن قرار گرفته باشد.
- گراف جهتدار G=<V,E> که در آن V مجموعه نمادهای غیرپایانی است و (A,B) ∈ E اگر B در سمت راست یکی از قوانین تولید A ظاهر شود، بدون دور (acyclic) باشد.
یک تعریف ریاضی از فرمالیسم کلیتر گرامرهای درختی مستقل از متن خط مستقیم را میتوان در کارهای Lohrey و همکاران یافت.
یک SLG در فرم نرمال چامسکی (Chomsky normal form) معادل یک برنامه خط مستقیم است.
الگوریتمهای مرتبط با SLG
- الگوریتم Sequitur: گرامر خط مستقیمی را برای یک رشته ورودی میسازد.
- الگوریتم Lempel-Ziv-Welch (LZW): گرامری مستقل از متن را به گونهای ایجاد میکند که تنها ذخیره قانون شروع گرامر تولید شده ضروری است.
- کدگذاری زوج بایت (Byte pair encoding - BPE): یکی از روشهای فشردهسازی مبتنی بر تکرار کاراکترها.
نکته جالب
آیا میدانستید؟ گرامر خط مستقیم در فرم نرمال چامسکی، معادل یک برنامه کامپیوتری خطی و بدون حلقه است.