پیچیدگی لمپل - زیو در ابتدا توسط دو دانشمند اسرائیلی، ابراهیم لمپل و یعقوب زیو، در مقاله ای به نام «پیچیدگی دنباله های محدود» ( 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 می باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاگر 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 می باشد.
wiki: پیچیدگی لمپل زیو