ضغط الإحداثيات: مراتب تحفظ الترتيب ولا تمثل المسافة

ما الذي نضغطه فعلًا؟

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

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

مرجع ضغط الإحداثيات، موضع الإدراج والعضوية في Python.

ست قيم وقاموس من أربع خانات

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

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

خطوات البناء وحدود الذاكرة

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

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

لماذا تتشارك المتساويات مرتبة واحدة؟

إزالة التكرار من قاموس المفاتيح لا تعني إزالة التكرار من البيانات. إذا وردت القيمة نفسها خمس مرات، فستبقى خمسة عناصر في متجه النتائج، تحمل كلها المرتبة نفسها. هذا ما يجعل المساواة قابلة للفحص بعد الضغط. في الأصل لدينا المليار في موضعين، وفي الناتج لدينا المرتبة ثلاثة في الموضعين نفسيهما. ولدينا اثنان وأربعون في موضعين يقابلهما ظهور المرتبة اثنين. أما إعطاء كل ظهور مرتبة مختلفة فيحول سؤال المساواة إلى سؤال آخر ويجعل القيمة المتكررة تبدو مختلفة عن نفسها؛ ليس ذلك العقد الذي نستخدمه في هذا المقال.

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

حفظ الترتيب يحتاج تفسيرًا دقيقًا

إذا كانت قيمة أولى أصغر من قيمة ثانية في القاموس، فإن موضع الأولى يسبق موضع الثانية؛ لذلك تكون مرتبتها أصغر. وإذا تساوت القيمتان كانتا المفتاح نفسه، فتتساوى مرتبتهما. والعكس صحيح في قاموس مختلف مرتب تصاعديًا: تساوي المرتبتين يعني العودة إلى الخانة نفسها، وصغر المرتبة يعني العودة إلى قيمة أصغر. يمكن إذن استبدال مقارنة مفتاحين معلومين بمقارنة مرتبتيهما، ضمن القاموس الواحد الذي بني منه الترميز. مثلًا سالب سبعة أصغر من اثنين وأربعين، وتقابلهما المرتبتان صفر واثنان بالاتجاه نفسه.

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

الفروق والمسافات تضيع من المراتب وحدها

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

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

عرض الرسم بالحجم الكامل

الجمع والمنتصف ليسا عمليتين محفوظتين

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

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

استعادة الأصل وفحص حدود المرتبة

الاستعادة بسيطة عندما نحفظ القاموس المرتب: لكل مرتبة في متجه النتائج نقرأ القيمة الموجودة في خانتها. نقرأ الثالثة فنحصل على المليار، ثم الصفرية فنحصل على سالب سبعة، ونتابع حتى نعيد التسلسل الأصلي كاملًا. تكرار المرتبة يعيد القيمة نفسها أكثر من مرة، ولذلك لا نفقد ظهورات المدخل رغم أن القاموس يضم المختلف فقط. هذا التحقق يقدم اختبارًا قويًا للتنفيذ: اضغط المدخل ثم فك النتائج باستعمال القاموس نفسه، وقارن التسلسل المستعاد بالأصل موضعًا بموضع. تساوي مجموعة القيم فقط ليس كافيًا لأن ترتيب العناصر وعددها مطلوبان أيضًا.

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

القيمة المجهولة وموضع الإدراج

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

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

القاموس الجديد يغير معنى المراتب القديمة

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

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

الفراغ والأنواع والتحويل الذي لا يغير المراتب

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

اخترنا في التنفيذ المرافق أعدادًا صحيحة عادية فقط، ورفضنا القيم المنطقية والكسور العددية حتى يكون العقد واضحًا. ليست هذه قاعدة تمنع كل تطبيق ممكن للضغط على أنواع أخرى؛ إنها حدود هذه الأمثلة واختباراتها. كذلك أضفنا مئة إلى كل قيمة في المثال فبقي متجه المراتب نفسه، لأن ترتيب المفاتيح ومساواتها لم يتغيرا. تغيّر القاموس، ولذلك تتغير القيم المستعادة رغم ثبات الرموز. يبين هذا الاختبار أن المراتب تصف علاقات ترتيب داخل المجموعة، بينما يظل القاموس مسؤولًا عن القيم الفعلية. افصل التحويلات على البيانات الأصلية عن التفسير العددي لرموزها.

كيف نتحقق من تنفيذ صغير؟

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

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

اختيار الضغط حسب السؤال اللاحق

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

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