LZMA

خوارزمية LZMA ( خوارزمية سلسلة ماركوف ليمبل-زيف ^{[ 1 ]} ) هي خوارزمية ضغط بيانات بدون فقدان للبيانات، طُوِّرت منذ عام 1998 على يد إيغور بافلوف، مطوّر برنامج 7-Zip . وقد استُخدمت في صيغة 7z لبرنامج الأرشفة 7-Zip منذ عام 2001. ^{[ 2 ]} تستخدم هذه الخوارزمية نظام ضغط قائم على القاموس، وهو مشابه إلى حد ما لخوارزمية LZ77 التي نشرها أبراهام ليمبل وجاكوب زيف عام 1977، وتتميز بنسبة ضغط عالية (أعلى عمومًا من bzip2 ) ^{[ 3 ]}^{[ 4 ]} وحجم قاموس ضغط متغير (يصل إلى 4 جيجابايت ) ^[⁵^] ، مع الحفاظ على سرعة فك ضغط مماثلة لخوارزميات الضغط الأخرى الشائعة الاستخدام. ^[⁶^]

LZMA2 هو تنسيق حاوية بسيط يسمح بالضغط وفك الضغط متعدد الخيوط باستخدام عدة تدفقات LZMA منفصلة. ويُستخدم في كل من تنسيق 7z و xz. ^{[ 7 ]}

ملخص

تستخدم خوارزمية LZMA خوارزمية ضغط القاموس (وهي نسخة معدلة من LZ77 ذات أحجام قواميس ضخمة ودعم خاص لمسافات التطابق المتكررة)، حيث يتم ترميز مخرجاتها باستخدام مُشفِّر نطاق ، وذلك باستخدام نموذج معقد للتنبؤ باحتمالية كل بت. يجد ضاغط القاموس التطابقات باستخدام هياكل بيانات قاموس متطورة، وينتج دفقًا من الرموز الحرفية ومراجع العبارات، والتي يتم ترميزها بتًا بتًا بواسطة مُشفِّر النطاق: تتوفر العديد من الترميزات، وتُستخدم خوارزمية البرمجة الديناميكية لاختيار الترميز الأمثل في ظل تقريبات معينة. ^{[ 8 ]}

قبل ظهور LZMA، كانت معظم نماذج التشفير تعتمد كليًا على البايت (أي أنها كانت تشفر كل بت باستخدام سلسلة من السياقات لتمثيل التبعيات على البتات السابقة من نفس البايت). يتمثل الابتكار الرئيسي في LZMA في أنه بدلًا من نموذج عام يعتمد على البايت، يستخدم نموذج LZMA سياقات خاصة بحقول البتات في كل تمثيل لحرف أو عبارة: وهذا يكاد يكون بنفس بساطة النموذج العام القائم على البايت، ولكنه يوفر ضغطًا أفضل بكثير لأنه يتجنب خلط البتات غير ذات الصلة معًا في نفس السياق. علاوة على ذلك، بالمقارنة مع ضغط القاموس التقليدي (مثل المستخدم في تنسيقات zip و gzip )، يمكن أن تكون أحجام القاموس، وعادةً ما تكون، أكبر بكثير، مستفيدةً من سعة الذاكرة الكبيرة المتاحة في الأنظمة الحديثة. ^{[ 8 ]}

نظرة عامة على التنسيق المضغوط

في ضغط LZMA، يكون التدفق المضغوط عبارة عن سلسلة من البتات، مُشفّرة باستخدام مُشفّر نطاق ثنائي تكيفي. يُقسّم التدفق إلى حزم، تصف كل حزمة إما بايتًا واحدًا، أو تسلسل LZ77 مع ترميز طوله ومسافته ضمنيًا أو صراحةً. يُنمذج كل جزء من كل حزمة بسياقات مستقلة، بحيث ترتبط تنبؤات الاحتمالية لكل بت بقيم ذلك البت (والبتات ذات الصلة من نفس الحقل) في الحزم السابقة من نفس النوع. يصف كل من lzip ^{[ 9 ]} ووثائق LZMA SDK تنسيق هذا التدفق. ^{[ 8 ]}

هناك 7 أنواع من الحزم: ^{[ 9 ]}

رمز مضغوط (تسلسل بتات)	اسم الحزمة	وصف العبوة
0 + رمز البايت	مضاء	بايت واحد مشفر باستخدام مشفر نطاق ثنائي تكيفي.
1+0 + الطول + المسافة	مباراة	تسلسل نموذجي من LZ77 يصف طول التسلسل والمسافة.
1+1+0+0	رحلة قصيرة	تسلسل LZ77 مكون من بايت واحد. المسافة تساوي آخر مسافة LZ77 مستخدمة.
1+1+0+1 + الطول	LONGREP[0]	تسلسل LZ77. المسافة تساوي آخر مسافة LZ77 مستخدمة.
1+1+1+0 + الطول	LONGREP[1]	تسلسل LZ77. المسافة تساوي المسافة المستخدمة قبل الأخيرة في تسلسل LZ77.
1+1+1+1+0 + الطول	LONGREP[2]	تسلسل LZ77. المسافة تساوي المسافة الثالثة الأخيرة المستخدمة في تسلسل LZ77.
1+1+1+1+1 + الطول	LONGREP[3]	تسلسل LZ77. المسافة تساوي المسافة الرابعة الأخيرة المستخدمة في تسلسل LZ77.

يشير LONGREP[*] إلى حزم LONGREP[0–3]، ويشير *REP إلى كل من LONGREP وSHORTREP، ويشير *MATCH إلى كل من MATCH و*REP.

تقوم حزم LONGREP[n] بإزالة المسافة المستخدمة من قائمة أحدث المسافات وإعادة إدخالها في المقدمة، لتجنب الإدخال المتكرر غير الضروري، بينما تقوم MATCH فقط بإضافة المسافة إلى المقدمة حتى لو كانت موجودة بالفعل في القائمة، ولا تقوم SHORTREP و LONGREP[0] بتغيير القائمة.

يتم ترميز الطول على النحو التالي:

رمز الطول (تسلسل البتات)	وصف
0+ 3 بتات	يتم ترميز الطول باستخدام 3 بتات، مما يعطي نطاق الأطوال من 2 إلى 9.
1+0+ 3 بتات	يتم ترميز الطول باستخدام 3 بتات، مما يعطي نطاق الأطوال من 10 إلى 17.
1+1+ 8 بت	يتم ترميز الطول باستخدام 8 بتات، مما يعطي نطاق الأطوال من 18 إلى 273.

كما هو الحال في LZ77، فإن الطول غير محدود بالمسافة، لأن النسخ من القاموس يتم تعريفه كما لو تم تنفيذ النسخ بايت بايت، مع الحفاظ على المسافة ثابتة.

المسافات منطقياً 32 بت، والمسافة 0 تشير إلى البايت الذي تمت إضافته مؤخراً في القاموس.

تبدأ عملية ترميز المسافة بـ "خانة مسافة" مكونة من 6 بتات، والتي تحدد عدد البتات الإضافية المطلوبة. يتم فك ترميز المسافات كسلسلة ثنائية، من الأكثر أهمية إلى الأقل أهمية، بتين حسب خانة المسافة، وبعض البتات المشفرة باحتمالية ثابتة قدرها 0.5، وبعض البتات المشفرة حسب السياق، وفقًا للجدول التالي (خانات المسافة من 0 إلى 3 تشفر المسافات من 0 إلى 3 مباشرة).

ترميز المسافة ^{[ 8 ]}
فتحة مسافة 6 بت	أعلى بتين	بتات احتمالية ثابتة 0.5	بتات مشفرة بالسياق
0	٠٠	0	0
1	01	0	0
2	10	0	0
3	11	0	0
4	10	0	1
5	11	0	1
6	10	0	2
7	11	0	2
8	10	0	3
9	11	0	3
10	10	0	4
11	11	0	4
12	10	0	5
13	11	0	5
14–62 (زوجي)	10	الفتحة / 2 - 5	4
15-63 (فردي)	11	(الفتحة - 1) / 2 - 5	4

تفاصيل خوارزمية فك الضغط

لا يبدو أن هناك مواصفات كاملة للغة الطبيعية للتنسيق المضغوط، بخلاف تلك التي تمت محاولتها في النص التالي.

يعتمد الوصف أدناه على وحدة فك التشفير المدمجة XZ Embedded من تأليف لاس كولين والمضمنة في مصدر نواة لينكس ^{[ 10 ]} والتي يمكن من خلالها استنتاج تفاصيل خوارزمية LZMA وLZMA2 بسهولة نسبية: وبالتالي، على الرغم من أن الاستشهاد بشفرة المصدر كمرجع ليس مثاليًا، إلا أنه ينبغي لأي مبرمج أن يكون قادرًا على التحقق من الادعاءات الواردة أدناه في غضون بضع ساعات من العمل.

ترميز نطاق البتات

يتم فك تشفير بيانات LZMA على أدنى مستوى بت واحد في كل مرة بواسطة وحدة فك التشفير النطاقي، في اتجاه وحدة فك تشفير LZMA.

يتم استدعاء فك تشفير النطاق القائم على السياق بواسطة خوارزمية LZMA عن طريق تمرير مرجع إلى "السياق"، والذي يتكون من متغير prob غير مُوقّع ذي 11 بت (يتم تنفيذه عادةً باستخدام نوع بيانات 16 بت) والذي يمثل الاحتمالية المتوقعة لكون البت 0، والذي تتم قراءته وتحديثه بواسطة مُفكِّك النطاق (ويجب تهيئته إلى ⁠ $2^{10}$ ( يمثل احتمال 0.5).

يفترض فك التشفير ذو النطاق الاحتمالي الثابت احتمالًا قدره 0.5، ولكنه يعمل بشكل مختلف قليلاً عن فك التشفير القائم على السياق.

تتكون حالة فك تشفير النطاق من متغيرين غير موقعين 32 بت، النطاق (يمثل حجم النطاق)، والرمز (يمثل النقطة المشفرة داخل النطاق).

تتكون عملية تهيئة وحدة فك التشفير النطاقية من ضبط النطاق على $232 - 1$ ، والرمز على قيمة 32 بت بدءًا من البايت الثاني في التدفق الذي يتم تفسيره على أنه big-endian؛ يتم تجاهل البايت الأول في التدفق تمامًا.

تتم عملية التطبيع على النحو التالي:

قم بإزاحة كل من النطاق والرمز إلى اليسار بمقدار 8 بتات
اقرأ بايتًا واحدًا من الدفق المضغوط
قم بتعيين أقل 8 بتات أهمية من التعليمات البرمجية إلى قيمة البايت المقروءة

تتم عملية فك تشفير النطاق القائم على السياق للبت باستخدام متغير الاحتمالية على النحو التالي:

إذا كان المدى أقل من $2^{24}$ قم بإجراء عملية التطبيع
تم ربطه بـ $\lfloor range/2^{11}\rfloor \times prob$ ⁠
إذا كان الكود أقل من الحد المسموح به :
1. حدد النطاق إلى الحد
2. اضبط قيمة prob على prob + $\lfloor 2^{11}-prob\rfloor /2^{5}$ ⁠
3. بت الإرجاع 0
وإلا (إذا كان الرمز أكبر من أو يساوي الحد ):
1. اضبط النطاق على النطاق - الحد
2. اضبط الكود على الكود المرتبط
3. اضبط الاحتمال على $prob-\lfloor prob/2^{5}\rfloor$ ⁠
4. بت الإرجاع 1

تتم عملية فك تشفير البتات ذات النطاق ذي الاحتمالية الثابتة على النحو التالي:

إذا كان المدى أقل من $2^{24}$ قم بإجراء عملية التطبيع
اضبط النطاق على $\lfloor range/2\rfloor$ ⁠
إذا كان الرمز أقل من النطاق :
1. بت الإرجاع 0
وإلا (إذا كان الرمز أكبر من أو يساوي النطاق ):
1. اضبط الرمز على نطاق الرمز
2. بت الإرجاع 1

rc_direct()لأسباب تتعلق بالأداء، لا يتضمن تطبيق نواة لينكس لفك التشفير ذي الاحتمالية الثابتة في `required` فرعًا شرطيًا، بل يطرح النطاق `range` من الكود بشكل غير مشروط. تُستخدم بتة الإشارة الناتجة لتحديد البتة المراد إرجاعها ولتوليد قناع يُدمج مع الكود ويُضاف إلى النطاق `range` .

لاحظ أن:

القسمة على $2^{11}$ عند حساب الحد الأدنى ، تتم عملية التقريب إلى أقرب عدد صحيح قبل عملية الضرب، وليس بعدها (على ما يبدو لتجنب الحاجة إلى دعم سريع للأجهزة لعملية الضرب 32 بت مع نتيجة 64 بت).
لا يُعد فك التشفير باحتمالية ثابتة مكافئًا تمامًا لفك التشفير النطاقي القائم على السياق مع أي قيمة احتمالية ، وذلك لأن فك التشفير النطاقي القائم على السياق يتجاهل البتات الـ 11 الأدنى من النطاق قبل الضرب في الاحتمالية كما هو موضح للتو، بينما يتجاهل فك التشفير باحتمالية ثابتة البت الأخير فقط.

ترميز نطاق الأعداد الصحيحة

يُوفر مُفكِّك النطاق أيضًا إمكانيات فك تشفير الأعداد الصحيحة باستخدام شجرة البت، وشجرة البت العكسية، واحتمالية ثابتة، والتي تُستخدم لفك تشفير الأعداد الصحيحة، وتُعمِّم عملية فك تشفير البت الواحد الموصوفة أعلاه. لفك تشفير الأعداد الصحيحة غير المُوقَّعة الأقل من الحدّ ، يتم توفير مصفوفة من $(الحد - 1)$ متغير احتمالية مكونة من 11 بت، والتي تُرتَّب من الناحية المفاهيمية على أنها عُقد داخلية لشجرة ثنائية كاملة ذات عدد محدود من الأوراق.

تعتمد خوارزمية فك تشفير شجرة البتات غير العكسية على الاحتفاظ بمؤشر إلى شجرة المتغيرات، التي تبدأ من الجذر. طالما أن المؤشر لا يشير إلى ورقة، يتم فك تشفير البت باستخدام المتغير المشار إليه بواسطة المؤشر، ويتم تحريك المؤشر إلى الفرع الأيسر أو الأيمن بناءً على ما إذا كان البت 0 أو 1؛ وعندما يشير المؤشر إلى ورقة، يتم إرجاع الرقم المرتبط بتلك الورقة.

وبالتالي يحدث فك تشفير شجرة البت غير العكسي من البت الأكثر أهمية إلى البت الأقل أهمية، ويتوقف عندما تكون هناك قيمة واحدة فقط ممكنة في النطاق الصالح (يسمح هذا من الناحية النظرية بأحجام نطاق ليست قوى العدد اثنين، على الرغم من أن LZMA لا تستخدم هذا).

يقوم فك تشفير شجرة البت العكسي بفك التشفير من البت الأقل أهمية إلى البتات الأكثر أهمية، وبالتالي يدعم فقط النطاقات التي هي قوى العدد اثنين، ويفك تشفير نفس عدد البتات دائمًا. وهو مكافئ لإجراء فك تشفير شجرة البت غير العكسي بحد أقصى لقوى العدد اثنين ، وعكس آخر بتات $log 2 (الحد الأقصى)$ من النتيجة.

في دالة rc_bittree في نواة لينكس، تُعاد الأعداد الصحيحة فعليًا في النطاق $[limit, 2 \times limit)$ (مع إضافة limit إلى القيمة المفاهيمية)، والمتغير الموجود في الفهرس 0 في المصفوفة غير مستخدم، بينما المتغير الموجود في الفهرس 1 هو الجذر، ويتم حساب فهرسي الأبناء الأيسر والأيمن على أنهما 2i و 2 i + 1. أما دالة rc_bittree_reverse فتضيف الأعداد الصحيحة في النطاق $[0,$ $limit$ $)$ إلى متغير يوفره المستدعي، حيث يتم تمثيل limit ضمنيًا بواسطة لوغاريتمه، ولها تنفيذ مستقل خاص بها لأسباب تتعلق بالكفاءة.

يقوم فك تشفير الأعداد الصحيحة باحتمالية ثابتة ببساطة بفك تشفير البتات باحتمالية ثابتة بشكل متكرر، حيث يقرأ البتات من الأكثر أهمية إلى الأقل أهمية.

تكوين LZMA

يتم تكوين مُفكِّك LZMA بواسطة بايت "الخصائص" lclppb وحجم القاموس. قيمة بايت lclppb هي ، حيث:lc + lp * 9 + pb * 9 * 5

يمثل lc عدد البتات العالية من البايت السابق لاستخدامها كسياق للترميز الحرفي (القيمة الافتراضية المستخدمة بواسطة LZMA SDK هي 3).
lp هو عدد البتات المنخفضة لموضع القاموس المراد تضمينها في literal_pos_state (القيمة الافتراضية المستخدمة بواسطة LZMA SDK هي 0).
يمثل pb عدد البتات المنخفضة لموضع القاموس المراد تضمينها في pos_state (القيمة الافتراضية المستخدمة بواسطة LZMA SDK هي 2).

في التدفقات غير LZMA2، يجب ألا تتجاوز قيمة lc 8، ويجب ألا تتجاوز قيمتا lp و pb 4؛ مما ينتج عنه نطاق من 0 إلى 224. أما في التدفقات LZMA2، فيجب ألا تتجاوز قيمة pb 4؛ مما يوفر مجموعة أكبر بكثير من القيم غير الممكنة.lc + lp

في تنسيق ملف LZMA الخاص ببرنامج 7-zip، تتم عملية التهيئة عبر ترويسة تحتوي على بايت "properties" متبوعًا بحجم القاموس ذي 32 بت بنظام little-endian بالبايتات. أما في LZMA2، فيمكن تغيير بايت "properties" اختياريًا في بداية حزم LZMA2، بينما يُحدد حجم القاموس في ترويسة LZMA2 كما هو موضح لاحقًا.

سياقات ترميز LZMA

تم وصف تنسيق حزمة LZMA بالفعل، ويحدد هذا القسم كيفية قيام LZMA بنمذجة التدفقات المشفرة LZ إحصائيًا، أو بعبارة أخرى، ما هي متغيرات الاحتمالية التي يتم تمريرها إلى وحدة فك التشفير النطاقي لفك تشفير كل بت.

يتم تنفيذ متغيرات الاحتمالية هذه كمصفوفات متعددة الأبعاد؛ قبل إدخالها، يتم تعريف بعض القيم التي تستخدم كمؤشرات في هذه المصفوفات متعددة الأبعاد.

تعتمد قيمة الحالة من الناحية المفاهيمية على أي من الأنماط في الجدول التالي يتطابق مع آخر 2-4 أنواع من الحزم التي تمت رؤيتها، ويتم تنفيذها كحالة آلة حالة يتم تحديثها وفقًا لجدول الانتقال المدرج في الجدول في كل مرة يتم فيها إخراج حزمة.

الحالة الأولية هي 0، وبالتالي يُفترض أن الحزم قبل البداية هي حزم LIT.

ولاية	الحزم السابقة				الحالة التالية عند وصول الحزمة التالية
	الرابع السابق	الثالث السابق	السابق الثاني	سابق	مضاء	مباراة	LONGREP[*]	رحلة قصيرة
0		مضاء	مضاء	مضاء	0	7	8	9
1		مباراة	مضاء	مضاء	0	7	8	9
2		LONGREP[*]	مضاء	مضاء	0	7	8	9
2	*مباراة	رحلة قصيرة	مضاء	مضاء	0	7	8	9
3	مضاء	رحلة قصيرة	مضاء	مضاء	0	7	8	9
4			مباراة	مضاء	1	7	8	9
5			LONGREP[*]	مضاء	2	7	8	9
5		*مباراة	رحلة قصيرة	مضاء	2	7	8	9
6		مضاء	رحلة قصيرة	مضاء	3	7	8	9
7			مضاء	مباراة	4	10	11	11
8			مضاء	LONGREP[*]	5	10	11	11
9			مضاء	رحلة قصيرة	6	10	11	11
10			*مباراة	مباراة	4	10	11	11
11			*مباراة	*مندوب	5	10	11	11

تتكون قيمتا pos_state و literal_pos_state من أقل بتات أهمية في موضع القاموس (عدد البايتات المشفرة منذ آخر إعادة ضبط للقاموس، بتردد يساوي حجم القاموس) على التوالي، وذلك بالنسبة لـ pb و lp ( حتى 4 بتات ، من رأس LZMA أو حزمة خصائص LZMA2). لاحظ أن حجم القاموس عادةً ما يكون من مضاعفات قوة كبيرة للعدد 2، لذا يمكن وصف هاتين القيمتين بشكل مكافئ بأنهما أقل بتات أهمية في عدد البايتات غير المضغوطة التي تمت رؤيتها منذ آخر إعادة ضبط للقاموس.

يتم تعيين قيمة prev_byte_lc_msbs إلى البتات الأكثر أهمية (حتى 4، من رأس LZMA أو حزمة خصائص LZMA2) للبايت غير المضغوط السابق.

تشير قيمة is_REP إلى ما إذا كانت الحزمة التي تتضمن طولًا هي LONGREP بدلاً من MATCH.

قيمة match_byte هي البايت الذي كان سيتم فك تشفيره إذا تم استخدام حزمة SHORTREP (بمعنى آخر، البايت الموجود في القاموس عند آخر مسافة مستخدمة)؛ يتم استخدامه فقط بعد حزمة *MATCH .

literal_bit_mode عبارة عن مصفوفة من 8 قيم في النطاق 0-2، قيمة واحدة لكل موضع بت في البايت، وهي 1 أو 2 إذا كانت الحزمة السابقة *MATCH وكان إما موضع البت الأكثر أهمية أو جميع البتات الأكثر أهمية في الحرف المراد ترميزه/فك ترميزه تساوي البتات في المواضع المقابلة في match_byte ، وإلا فإنها تكون 0؛ يعتمد الاختيار بين القيمتين 1 أو 2 على قيمة البت في نفس الموضع في match_byte .

يمكن اعتبار مجموعة المتغيرات الحرفية / الحرفية بمثابة "شجرة بت زائفة" تشبه شجرة البت ولكن مع 3 متغيرات بدلاً من 1 في كل عقدة، يتم اختيارها بناءً على قيمة literal_bit_mode في موضع البت التالي المراد فك تشفيره بعد سياق شجرة البت المشار إليه بواسطة العقدة.

إن الادعاء الموجود في بعض المصادر بأن القيم الحرفية بعد *MATCH يتم ترميزها كعملية XOR لقيمة البايت مع match_byte غير صحيح؛ بدلاً من ذلك يتم ترميزها ببساطة كقيمة البايت الخاصة بها، ولكن باستخدام شجرة البت الزائفة الموصوفة للتو والسياق الإضافي المدرج في الجدول أدناه.

مجموعات متغيرات الاحتمالية المستخدمة في LZMA هي تلك التالية:

اسم XZ	اسم حزمة تطوير البرامج LZMA	مُعَلَّم بواسطة	يستخدم عندما	وضع الترميز	إذا كانت البتة 0،	إذا كانت البتة 1،
is_match	تطابق	الحالة ، حالة_الموقع	بدء تشغيل الحزمة	قليل	مضاء	*مباراة
is_rep	جمهورية إسرائيل	ولاية	بعد تسلسل البتات 1	قليل	مباراة	*مندوب
is_rep0	IsRepG0	ولاية	بعد تسلسل البتات 11	قليل	تقرير قصير/ تقرير طويل[0]	LONGREP[1–3]
is_rep0_long	IsRep0Long	الحالة ، حالة_الموقع	بعد تسلسل البتات 110	قليل	رحلة قصيرة	LONGREP[0]
is_rep1	IsRepG1	ولاية	بعد تسلسل البتات 111	قليل	LONGREP[1]	LONGREP[2/3]
is_rep2	IsRepG2	ولاية	بعد تسلسل البتات 1111	قليل	LONGREP[2]	LONGREP[3]
حرفيًا	حرفي	prev_byte_lc_msbs ، حالة الموضع الحرفي ،سياق شجرة البت`literal_bit_mode[bit position]`	بعد تسلسل البتات 0	شجرة بت زائفة ذات 256 قيمة	قيمة البايت الحرفية
فتحة_المسافة	PosSlot	`min(match_length, 5)`سياق شجرة البت	المسافة: البداية	شجرة بتية مكونة من 64 قيمة	فتحة المسافة
منطقة خاصة	SpecPos	distance_slot ، سياق شجرة البت العكسية	المسافة: 4-13 خانة مسافة	`((distance_slot >> 1) − 1)`شجرة بت عكسية - بت	أجزاء منخفضة من المسافة
محاذاة المسافة	محاذاة	سياق شجرة البت العكسي	المسافة: 14+ خانة مسافة، بعد بتات الاحتمالية الثابتة	شجرة بت عكسية 4 بت	أجزاء منخفضة من المسافة
len_dec.choice	لين تشويس	is_REP	طول المباراة: البداية	قليل	الطول من 2 إلى 9	طول 10+
len_dec.choice2	لين تشويس 2	is_REP	طول التطابق: بعد تسلسل البتات 1	قليل	طول 10-17	طول 18+
len_dec.low	لينلو	is_REP ، pos_state ، سياق شجرة البت	طول التطابق: بعد تسلسل البتات 0	شجرة بتية ذات 8 قيم	أجزاء قصيرة من الطول
len_dec.mid	لينميد	is_REP ، pos_state ، سياق شجرة البت	طول التطابق: بعد تسلسل البتات 10	شجرة بتية ذات 8 قيم	الأجزاء الوسطى من الطول
len_dec.high	لينهاي	is_REP ، سياق شجرة البت	طول التطابق: بعد تسلسل البتات 11	شجرة بتية مكونة من 256 قيمة	أجزاء طويلة

تنسيق LZMA2

يدعم حاوية LZMA2 عمليات متعددة لضغط بيانات LZMA وفك ضغطها. يمكن لكل عملية ضغط LZMA أن تحتوي على إعدادات وقاموس LZMA مختلفين. يُحسّن هذا من ضغط الملفات غير القابلة للضغط جزئيًا أو كليًا، ويتيح الضغط وفك الضغط متعدد الخيوط عن طريق تقسيم الملف إلى أجزاء يمكن ضغطها أو فك ضغطها بشكل مستقل ومتوازٍ.

يتكون رأس LZMA2 من بايت يشير إلى حجم القاموس:

يشير الرقم 40 إلى حجم قاموس يبلغ 4 جيجابايت - 1
حتى القيم الأقل من 40 تشير إلى حجم قاموس يبلغ ^{2v /2 + 12} بايت
تشير القيم الفردية الأقل من 40 إلى حجم قاموس يبلغ 3×2 ^{( v − 1)/2 + 11} بايت
القيم التي تزيد عن 40 غير صالحة

تتكون بيانات LZMA2 من حزم تبدأ ببايت تحكم، بالقيم التالية:

يشير الرقم 0 إلى نهاية الملف
يشير الرقم 1 إلى إعادة ضبط القاموس متبوعًا بجزء غير مضغوط
يشير الرقم 2 إلى جزء غير مضغوط بدون إعادة ضبط القاموس
القيم من 3 إلى 0x7f غير صالحة
تشير القيم من 0x80 إلى 0xff إلى جزء LZMA، حيث تُستخدم البتات الخمس الأدنى كبتات من 16 إلى 20 من الحجم غير المضغوط ناقص واحد، وتشير البتات من 5 إلى 6 إلى ما يجب إعادة ضبطه

يمكن أن تكون البتات 5-6 لأجزاء LZMA كالتالي:

0: لم تتم إعادة ضبط أي شيء
1: إعادة ضبط الحالة
2: إعادة ضبط الحالة، إعادة ضبط الخصائص باستخدام بايت الخصائص
3: إعادة ضبط الحالة، إعادة ضبط الخصائص باستخدام بايت الخصائص، إعادة ضبط القاموس

تؤدي عمليات إعادة ضبط حالة LZMA إلى إعادة ضبط جميع حالات LZMA باستثناء القاموس، وتحديدًا:

مشفر النطاق
قيمة الحالة
المسافات الأخيرة للمباريات المتكررة
جميع احتمالات LZMA

تتكون الأجزاء غير المضغوطة مما يلي:

قيمة كبيرة النهاية مكونة من 16 بت تشفر حجم البيانات ناقص واحد
البيانات المراد نسخها حرفيًا إلى القاموس والناتج

تتكون أجزاء LZMA من:

قيمة كبيرة النهاية مكونة من 16 بت تشفر أقل 16 بت من الحجم غير المضغوط ناقص واحد
قيمة كبيرة النهاية مكونة من 16 بت تشفر الحجم المضغوط ناقص واحد
بايت properties/lclppb إذا تم ضبط البت 6 في بايت التحكم
البيانات المضغوطة بتقنية LZMA، بدءًا من 5 بايتات (يتم تجاهل البايت الأول منها) المستخدمة لتهيئة مُشفِّر النطاق (والتي يتم تضمينها في الحجم المضغوط).

تنسيقات xz و 7z

تم توثيق تنسيق .xz، الذي يمكن أن يحتوي على بيانات LZMA2، على موقع tukaani.org ، ^[¹¹^] بينما تم توثيق تنسيق ملف .7z، الذي يمكن أن يحتوي على بيانات LZMA أو LZMA2، في ملف 7zformat.txt الموجود في LZMA SDK. ^[¹²^]

تطبيق 7-Zip المرجعي

تتوفر نسخة LZMA المستخرجة من برنامج 7-Zip كحزمة تطوير برمجية (SDK) خاصة بها. كانت في الأصل مرخصة بترخيص مزدوج بموجب كل من رخصة جنو العمومية الصغرى (GNU LGPL) ورخصة Common Public License ، ^{[ 13 ]} مع استثناء خاص إضافي للملفات الثنائية المرتبطة، ولكن قام إيغور بافلوف بنشرها في الملكية العامة في 2 ديسمبر 2008، مع إصدار النسخة 4.62. ^{[ 12 ]}

أصبح ضغط LZMA2، وهو نسخة محسنة من LZMA، ^{[ 14 ]} الآن هو طريقة الضغط الافتراضية لتنسيق .7z، بدءًا من الإصدار 9.30 في 26 أكتوبر 2012. ^{[ 15 ]}

كُتبت مكتبة ضغط LZMA المرجعية مفتوحة المصدر في الأصل بلغة C++، ولكن تم نقلها إلى لغات ANSI C و C# و Java . ^{[ 12 ]} كما توجد روابط Python خارجية لمكتبة C++، ^{[ 16 ]} بالإضافة إلى نسخ من LZMA إلى لغات Pascal ، ^{[ 17 ]} وGo، ^{[ 18 ]} و Ada . ^{[ 19 ]}

يستخدم تطبيق 7-Zip عدة أنواع من سلاسل التجزئة والأشجار الثنائية وأشجار باتريشيا كأساس لخوارزمية البحث في القاموس الخاصة به.

بالإضافة إلى خوارزمية LZMA، تتضمن حزمة تطوير البرامج (SDK) وبرنامج 7-Zip العديد من مرشحات المعالجة المسبقة المصممة لتحسين الضغط، بدءًا من ترميز دلتا البسيط (للصور) وBCJ للبرامج التنفيذية. كما توفر بعض خوارزميات الضغط الأخرى المستخدمة في 7z.

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

تطبيقات أخرى

بالإضافة إلى تطبيق 7-Zip المرجعي، تدعم البرامج التالية تنسيق LZMA.

xz : تطبيق لضغط البيانات المتدفقة، يحتوي على أداة سطر أوامر شبيهة بـ gzip ، تدعم خوارزمية LZMA2 في صيغة ملفات xz. وقد شقّ طريقه إلى العديد من برامج أنظمة يونكس بفضل أدائه العالي (مقارنةً بـ bzip2 ) وحجمه الصغير (مقارنةً بـ gzip ). ^{[ 3 ]} تحتوي نواة لينكس ، وأنظمة dpkg و RPM على شيفرة xz، ويستخدم العديد من موزعي البرامج، مثل kernel.org ، وديبيان ^{[ 20 ]} ، وفيدورا ، xz لضغط إصداراتهم.
lzip : تطبيق آخر لـ LZMA مخصص في الغالب لأنظمة شبيهة بنظام Unix، وهو بديل لـ xz. ^{[ 21 ]} يتميز بتنسيق ملف أبسط مع سهولة استعادة الأخطاء.
ZIPX : امتداد لتنسيق ضغط ZIP تم إنشاؤه بواسطة WinZip بدءًا من الإصدار 12.1. كما يمكنه استخدام طرق ضغط أخرى متنوعة مثل BZip و PPMd . ^{[ 22 ]}

مراجع

↑ سالومون، ديفيد (20 مارس 2007). ضغط البيانات: المرجع الكامل . سبرينغر لندن. ص 242. ISBN 9781846286032.
↑ إيغور بافلوف (5 ديسمبر 2001). "صيغة 7z" . مؤرشف من الأصل في 5 ديسمبر 2001.
1 2 لاس كولين (31 مايو 2005). "مقارنة سريعة: Gzip مقابل Bzip2 مقابل LZMA" . تم الاطلاع عليه بتاريخ 21 أكتوبر 2015 .- تم استبدال منفذ LZMA Unix أخيرًا بـ xz الذي يتميز بضغط أفضل وأسرع؛ ومن هنا نعلم أن منفذ LZMA Unix كان أفضل بكثير من gzip و bzip2.
↑ كلاوسمان، توبياس (8 مايو 2008). "مقارنة بين Gzip وBzip2 وLzma" . مدونة حيوان ألفا . مؤرشف من الأصل في 6 يناير 2013. تم الاطلاع عليه في 16 يونيو 2013 .
↑ غير معروف (2013). "تنسيق 7z" . تم الاسترجاع في 16-06-2013 .
↑ ماهوني، مات. "شرح ضغط البيانات" . تم الاسترجاع في 13-11-2013 .
↑ "ضغط البيانات XZ في لينكس - وثائق نواة لينكس" . www.kernel.org . تاريخ الاسترجاع: 22-12-2025 .
1 2 3 4 "مواصفات LZMA.7z في LZMA SDK" . 7-zip.org .
1 2 "تنسيق Lzip Stream" . دليل Lzip . تم الاطلاع عليه بتاريخ 14 نوفمبر 2019 .
↑ كولين، لاس؛ بافلوف، إيغور. "lib/xz/xz_dec_lzma2.c" . تم الاسترجاع في 16-06-2013 .
↑ "تنسيق ملف .xz" . 27-08-2009 . تم الاطلاع عليه بتاريخ 16-06-2013 .
1 2 3 إيغور بافلوف (2013). "مجموعة أدوات تطوير البرمجيات LZMA" . تم الاسترجاع في 16-06-2013 .
↑ "تصفح /LZMA SDK/4.23" . سورس فورج . تم الاسترجاع في 12 فبراير 2014 .
↑ "مساعدة إعداد Inno" . jrsoftware.org . تم الاطلاع عليه بتاريخ 16-06-2013 . LZMA2 هو إصدار مُعدّل من LZMA يوفر نسبة ضغط أفضل للبيانات غير القابلة للضغط (تتوسع البيانات العشوائية بنسبة 0.005% تقريبًا، مقارنةً بنسبة 1.35% مع LZMA الأصلي)، ويمكنه اختياريًا ضغط أجزاء متعددة من الملفات الكبيرة بالتوازي، مما يزيد من سرعة الضغط بشكل كبير ولكن مع احتمال انخفاض نسبة الضغط.
↑ "تاريخ 7-Zip" . 2012-10-26 . تم الاطلاع عليه بتاريخ 2013-06-16 .
↑ باوخ، يواكيم (2010-04-07). "PyLZMA - روابط بايثون مستقلة عن النظام الأساسي لمكتبة ضغط LZMA" . تم الاسترجاع في 2013-06-16 .
↑ بيرتلز، آلان (13-06-2006). "مساعدة في البرمجة: حزمة تطوير البرمجيات باسكال LZMA" . تم الاطلاع عليه بتاريخ 16-06-2013 .
↑ فييرو، أندريه (28-06-2012). "حزمة compress/lzma للغة Go 1" . مؤرشفة من الأصل بتاريخ 21-09-2016 . تم الاطلاع عليها بتاريخ 16-06-2013 .
↑ "زيب-آدا" .
↑ غيليم جوفر. "تم قبول dpkg 1.17.0 (المصدر amd64 all)" . ضمان جودة حزم دبيان . تم الاسترجاع في 21-10-2015 .
↑ دياز، دياز. "معايير أداء LZIP" . LZIP (نونغنو).
↑ "ما هو ملف Zipx؟" . WinZip.com . تم الاطلاع عليه بتاريخ 14-03-2016 .

روابط خارجية

[1] سالومون، ديفيد (20 مارس 2007). ضغط البيانات: المرجع الكامل . سبرينغر لندن. ص 242. ISBN 9781846286032.

[7z_format-2] إيغور بافلوف (5 ديسمبر 2001). "صيغة 7z" . مؤرشف من الأصل في 5 ديسمبر 2001.

[gzip_bzip_lzma_bench-3] 1 2 لاس كولين (31 مايو 2005). "مقارنة سريعة: Gzip مقابل Bzip2 مقابل LZMA" . تم الاطلاع عليه بتاريخ 21 أكتوبر 2015 .- تم استبدال منفذ LZMA Unix أخيرًا بـ xz الذي يتميز بضغط أفضل وأسرع؛ ومن هنا نعلم أن منفذ LZMA Unix كان أفضل بكثير من gzip و bzip2.

[4] كلاوسمان، توبياس (8 مايو 2008). "مقارنة بين Gzip وBzip2 وLzma" . مدونة حيوان ألفا . مؤرشف من الأصل في 6 يناير 2013. تم الاطلاع عليه في 16 يونيو 2013 .

[LZMA_Format-5] غير معروف (2013). "تنسيق 7z" . تم الاسترجاع في 16-06-2013 .

[6] ماهوني، مات. "شرح ضغط البيانات" . تم الاسترجاع في 13-11-2013 .

[7] "ضغط البيانات XZ في لينكس - وثائق نواة لينكس" . www.kernel.org . تاريخ الاسترجاع: 22-12-2025 .

[lzma-sdk-format-8] 1 2 3 4 "مواصفات LZMA.7z في LZMA SDK" . 7-zip.org .

[lzip-format-9] 1 2 "تنسيق Lzip Stream" . دليل Lzip . تم الاطلاع عليه بتاريخ 14 نوفمبر 2019 .

[10] كولين، لاس؛ بافلوف، إيغور. "lib/xz/xz_dec_lzma2.c" . تم الاسترجاع في 16-06-2013 .

[11] "تنسيق ملف .xz" . 27-08-2009 . تم الاطلاع عليه بتاريخ 16-06-2013 .

[LZMA_SDK-12] 1 2 3 إيغور بافلوف (2013). "مجموعة أدوات تطوير البرمجيات LZMA" . تم الاسترجاع في 16-06-2013 .

[13] "تصفح /LZMA SDK/4.23" . سورس فورج . تم الاسترجاع في 12 فبراير 2014 .

[14] "مساعدة إعداد Inno" . jrsoftware.org . تم الاطلاع عليه بتاريخ 16-06-2013 . LZMA2 هو إصدار مُعدّل من LZMA يوفر نسبة ضغط أفضل للبيانات غير القابلة للضغط (تتوسع البيانات العشوائية بنسبة 0.005% تقريبًا، مقارنةً بنسبة 1.35% مع LZMA الأصلي)، ويمكنه اختياريًا ضغط أجزاء متعددة من الملفات الكبيرة بالتوازي، مما يزيد من سرعة الضغط بشكل كبير ولكن مع احتمال انخفاض نسبة الضغط.

[15] "تاريخ 7-Zip" . 2012-10-26 . تم الاطلاع عليه بتاريخ 2013-06-16 .

[16] باوخ، يواكيم (2010-04-07). "PyLZMA - روابط بايثون مستقلة عن النظام الأساسي لمكتبة ضغط LZMA" . تم الاسترجاع في 2013-06-16 .

[17] بيرتلز، آلان (13-06-2006). "مساعدة في البرمجة: حزمة تطوير البرمجيات باسكال LZMA" . تم الاطلاع عليه بتاريخ 16-06-2013 .

[18] فييرو، أندريه (28-06-2012). "حزمة compress/lzma للغة Go 1" . مؤرشفة من الأصل بتاريخ 21-09-2016 . تم الاطلاع عليها بتاريخ 16-06-2013 .

[19] "زيب-آدا" .

[dpkg_use_xz-20] غيليم جوفر. "تم قبول dpkg 1.17.0 (المصدر amd64 all)" . ضمان جودة حزم دبيان . تم الاسترجاع في 21-10-2015 .

[lzip_bench-21] دياز، دياز. "معايير أداء LZIP" . LZIP (نونغنو).

[zipx-22] "ما هو ملف Zipx؟" . WinZip.com . تم الاطلاع عليه بتاريخ 14-03-2016 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[

[

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗