تعقيد ليمبل-زيف

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 19 صور
الموسوعة الحرة

يُعدّ تعقيد ليمبل -زيف مقياسًا طُرح لأول مرة في مقالة بعنوان "حول تعقيد المتتاليات المنتهية" (IEEE Trans. On IT-22,1 1976)، من تأليف عالمي الحاسوب الإسرائيليين أبراهام ليمبل ويعقوب زيف . يرتبط هذا المقياس بتعقيد كولموغوروف ، لكن الدالة الوحيدة التي يستخدمها هي النسخ التكراري (أي النسخ السطحي).

تُشكّل الآلية الأساسية في مقياس التعقيد هذا نقطة انطلاق لبعض خوارزميات ضغط البيانات بدون فقدان ، مثل LZ77 وLZ78 و LZW . ورغم أنه يستند إلى مبدأ أساسي لنسخ الكلمات، إلا أن مقياس التعقيد هذا ليس مقيدًا للغاية، إذ يُلبي الخصائص الرئيسية المتوقعة لمثل هذا المقياس: فالمتواليات ذات الانتظام المُحدد لا تتمتع بتعقيد كبير، ويزداد التعقيد مع ازدياد طول المتوالية وعدم انتظامها.

يمكن استخدام مقياس تعقيد ليمبل-زيف لقياس تكرارية التسلسلات الثنائية والنصوص، مثل كلمات الأغاني أو النثر. كما ثبت أن تقديرات البعد الكسري لبيانات العالم الحقيقي ترتبط بتعقيد ليمبل-زيف. [ 1 ] [ 2 ]

مبدأ

لنفترض أن S هي متتالية ثنائية، طولها n، والتي يتعين علينا حساب تعقيد ليمبل-زيف لها، ويرمز لها بـ C(S). تُقرأ المتتالية من اليسار.

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

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

وبعبارة أخرى، فإن تعقيد ليمبل-زيف هو عدد السلاسل الفرعية المختلفة (أو الكلمات الفرعية) التي يتم مواجهتها عند النظر إلى التسلسل الثنائي على أنه تيار (من اليسار إلى اليمين).

التفسيرات الرسمية

تستخدم الطريقة التي اقترحها ليمبل وزيف ثلاثة مفاهيم: قابلية التكرار، وقابلية الإنتاج، والتاريخ الشامل للتسلسل، والتي قمنا بتعريفها هنا.

الرموز

ليكن S متتالية ثنائية طولها n (أي،ن{\displaystyle n}الرموز التي تأخذ القيمة 0 أو 1). ليكنS(أنا،ج){\displaystyle S(i,j)}، مع1≤أنا،ج≤ن{\displaystyle 1\leq i,j\leq n}، لتكون الكلمة الفرعية منS{\displaystyle S}من الفهرس i إلى الفهرس j (إذاج<أنا،S(أنا،ج){\displaystyle j<i,S(i,j)}السلسلة الفارغة ). يُرمز إلى طول السلسلة S بالرمز n.ل(S){\displaystyle l(S)}وتسلسلسؤال{\displaystyle Q}يقال إنها بادئة ثابتة لـS{\displaystyle S}لو:

∃ج<ل(S)، شارع S(1،ج)=سؤال.{\displaystyle \exists j<{l(S),{\text{ st }}S(1,j)=Q.}}

قابلية التكرار والإنتاج

مثال على إمكانية التكرار ، انقر هنا

من جهة، يُقال إن متتالية S ذات طول n قابلة للتكرار من بادئتها S(1,j) عندما تكون S(j+1,n) كلمة جزئية من S(1,j). ويُرمز إلى ذلك بـ S(1,j)→S.

وبعبارة أخرى، يمكن إعادة إنتاج S من بادئتها S(1,j) إذا كان باقي التسلسل، S(j+1,n)، ليس سوى نسخة من كلمة فرعية أخرى (تبدأ من فهرس i < j+1) من S(1,n−1).

لإثبات أن المتتالية S يمكن إعادة إنتاجها بواسطة أحد بادئاتها S(1,j)، عليك أن تُظهر ما يلي:

∃ص≤ج، شارع S(ج+1،ن)=S(ص،ل(S(ج+1،ن))+ص-1){\displaystyle \exists p\leq j,{\text{ st }}S(j+1,n)=S(p,l(S(j+1,n))+p-1)}

مثال على الإنتاجية (انقر هنا)

من جهة أخرى، تُعرَّف قابلية الإنتاج من قابلية التكرار: يكون التسلسل S قابلاً للإنتاج من بادئته S(1,j) إذا كان S(1,n−1) قابلاً للتكرار من S(1,j). ويُرمز لذلك بـ S(1,j)⇒S. بعبارة أخرى، يجب أن يكون S(j+1,n−1) نسخةً من كلمة فرعية أخرى من S(1,n-2). يمكن أن يكون الرمز الأخير من S رمزًا جديدًا (ولكن لا يمكن أن يكون كذلك)، مما قد يؤدي إلى إنتاج كلمة فرعية جديدة (ومن هنا جاء مصطلح قابلية الإنتاج).

مقارنة بين قابلية التكرار وقابلية الإنتاج. انقر هنا

تاريخ شامل وتعقيد

انطلاقًا من تعريف قابلية الإنتاج، فإن السلسلة الفارغة Λ = S(1,0) ⇒ S(1,1). لذا، من خلال عملية إنتاج تكرارية، في الخطوة i، لدينا S(1,hi) ⇒ S(1,hi+1)، وبالتالي يمكننا بناء S من بادئاتها. وبما أن S(1,i) ⇒ S(1,i+1) (حيث hi+1 = hi + 1) صحيحة دائمًا، فإن عملية إنتاج S هذه تستغرق على الأكثر n = l(S) خطوة. ليكن m،1≤م≤ل(S){\displaystyle 1\leq {\text{m}}\leq l(S)}، ليكن عدد الخطوات اللازمة لعملية إنتاج S هذه. يمكن كتابة S في شكل مُجزأ، يُسمى تاريخ S، ويُرمز له بـ H(S)، ويُعرف على النحو التالي:

ح(S)=S(1،ح1)S(ح1+1،ح2)⋯S(حم-1+1،حم){\displaystyle H(S)=S(1,h_{1})S(h_{1}+1,h_{2})\dotsm S(h_{m-1}+1,h_{m})}حأنا(S)=S(حأنا-1+1،حأنا)،أنا=1،2⋯م،أينح0=0،ح1=1،حم=ل(S)، يُطلق عليه اسم مكون من ح(S).{\displaystyle H_{i}(S)=S(h_{i-1}+1,h_{i}),i=1,2\dotsm m,{\text{حيث}}\;h_{0}=0,h_{1}=1,h_{m}=l(S),{{\text{يُسمى مُكَوِّن }}H(S)}.}

مقارنة بين قابلية التكرار وقابلية الإنتاج. انقر هنا

يقال أن أحد مكونات S، Hi(S)، شامل إذا كان S(1,hi) هو أطول تسلسل ينتجه S(1,hi−1) (أي S(1,hi−1) ⇒ S(1,hi)) ولكن بحيث لا ينتج S(1,hi−1) S(1,hi) (يرمز له بـ).S(1،حأنا-1)↛S(1،حأنا){\displaystyle S(1,h_{i}-1)\nrightarrow S(1,h_{i})}يُطلق على الفهرس p الذي يسمح بالحصول على أطول إنتاج اسم المؤشر.

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

الخوارزمية

لحسن الحظ، توجد طريقة فعالة للغاية لحساب هذا التعقيد، وذلك في عدد خطي من العمليات (يا(ن){\displaystyle {\mathcal {O}}(n)}لن=ل(S){\displaystyle n=l(S)}طول التسلسل S).

يُقدّم الوصف الرسمي لهذه الطريقة من خلال الخوارزمية التالية :

  • i = p − 1، حيث p هو المؤشر (انظر أعلاه)
  • u هو طول البادئة الحالية
  • يمثل v طول المكون الحالي للمؤشر الحالي p
  • يمثل vmax الطول النهائي المستخدم للمكون الحالي (الأكبر على جميع المؤشرات الممكنة p).
  • و C هي تعقيد ليمبل-زيف، يتم زيادتها بشكل متكرر.
// S عبارة عن سلسلة ثنائية بحجم n i := 0 C := 1 u := 1 v := 1 vmax := v while u + v <= n do if S [ i + v ] = S [ u + v ] then v := v + 1 else vmax := max ( v , vmax ) i := i + 1 if i = u then // تم التعامل مع جميع المؤشرات C := C + 1 u := u + vmax v := 1 i := 0 vmax := v else v := 1 end if end if end while if v ! = 1 then C := C + 1 end if

انظر أيضاً

  • LZ77 و LZ78 – خوارزميات ضغط تستخدم فكرة مماثلة لإيجاد السلاسل الفرعية المتطابقة.

ملاحظات ومراجع

مراجع

فهرس

  • أبراهام ليمبل وجاكوب زيف، «  حول تعقيد المتتاليات المنتهية  »، مجلة IEEE للمعاملات في نظرية المعلومات، يناير 1976، ص  75-81، المجلد 22، العدد 1

طلب