پیچیدگی لمپل-زیو

پیچیدگی لمپل-زیو در ابتدا توسط دو دانشمند اسرائیلی، ابراهیم لمپل و یعقوب زیو، در مقاله ای به نام «پیچیدگی دنباله‌های محدود» (IEEE Trans. در IT-22،۱ ۱۹۷۶) ارائه شد. این اندازه‌گیری پیچیدگی تنها تابعی که از آن استفاده می‌کند، نسخه بازگشتی است. پیچیدگی Lempel-Ziv را می‌توان برای اندازه‌گیری مقدار تکرار دنباله‌های باینری و متن مانند متن ترانه استفاده کرد.

توضیح عملکرد

اگر S دنبالهٔ باینری با طول n باشد و پیچیدگی Lempel_Ziv را با C(S) نشان دهیم. دنباله از چپ خوانده می‌شود. تصور کنید که شما یک خط دارید که می‌توانید برای انجام محاسبات در طول آن حرکت کنید. این خط بعد از اولین نماد در ابتدای دنباله تنظیم می‌شود. این موقعیت اولیه موقعیت ۱ نامیده می‌شود، که ما باید آن را به موقعیت ۲ که موقعیت اولیه برای مرحله بعدی در نظر گرفته می‌شود منتقل کنیم (و غیره). ما باید جداکننده را از ابتدا (در موقعیت ۱) حرکت دهیم (ممکن است حرکت به سمت راست باشد)، به این ترتیب کلمهٔ بین موقعیت ۱ و موقعیت جداکننده، یک کلمه از دنباله است که قبل از موقعیت ۱ جداکننده شروع می‌شود و به محض این که جداکننده در موقعیتی قرار گرفت که این شرایط ایجاد نشد ما متوقف می‌شویم و جداکننده را به این موقعیت حرکت می‌دهیم و دوباره با علامت گذاری این موقعیت به عنوان موقعیت اولیه جدید (به عنوان مثال، موقعیت ۱) دوباره شروع می‌کنیم. تا انتهای دنباله، تکرار کنید. پیچیدگی Lempel-Ziv مربوط به تعداد تکرارهای مورد نیاز برای پایان دادن به این روش است. به بیان دیگر پیچیدگی Lempel-Ziv تعداد زیر رشته‌ها (یا واژگان) است که در طول یک دنباله باینری (از چپ به راست) موجود می‌باشد.

تکرار پذیری

یک دنباله S با طول n را به صورت زیر تعریف می‌کنیم:

(S(i,j)(1 ≤ i , j ≤ n و اگر j<i بود S(i,j) تهی باشد.

طول دنبالهٔ S را با L(S) نشان می‌دهیم. دنبالهٔ s با توجه به مقدار S(1,j) زمانی تکرارپذیر می‌باشد که بقیهٔ دنباله یعنی S(j + 1، n) تکرار کلمهٔ دیگر (که از i < j+1 شروع شده‌است) از S(1,n-1) باشد. برای اثبات تکرار پذیری دنبالهٔ S باید نشان دهید که:

Ǝp≤j ,s.t.S(j+1,n)=S(p,L(S(j+1,n))+p-1

الگوریتم

• S دنبالهٔ باینری با طول n می‌باشد.
• u طول S(1,j) می‌باشد.
• i=p-1 و p نشانگر می‌باشند.
• v طول مولفهٔ موردنظر برای نشانگر موردنظر p می‌باشد.
• vmax طول نهایی استفاده شده برای مولفهٔ موردنظر می‌باشد.
• c پیچیدگی lempel-ziv می‌باشد.

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  // all the pointers have been treated
 C := C + 1
 u := u + vmax
 v := ۱
 i := ۰
 vmax := v
else
 v := ۱
 end  if
 end   if
 end   while
if v != 1 then
 C := C+1 
end si

توضیح تصویری برای تکرار پذیری در لینک زیر موجود می‌باشد