منحنى ترتيب Z

تم توسيع عملية تكرار منحنى الترتيب Z لتشمل ثلاثة أبعاد.

في التحليل الرياضي وعلوم الحاسوب ، تُستخدم الدوال ذات الترتيب Z ، ومنحنى ليبيغ ، ومنحنى مورتون لملء الفراغ ، ^{[ 1 ] أو} ترتيب مورتون أو رمز مورتون، لتحويل البيانات متعددة الأبعاد إلى بُعد واحد مع الحفاظ على موضع نقاط البيانات (أي أن نقطتين متقاربتين في فضاء متعدد الأبعاد باحتمالية عالية تقعان متقاربتين أيضًا في ترتيب مورتون). سُمّي هذا الترتيب في فرنسا نسبةً إلى هنري ليبيغ ، الذي درسه عام 1904، ^{[ 2 ]} وفي الولايات المتحدة نسبةً إلى غاي ماكدونالد مورتون ، الذي طبّقه لأول مرة على تسلسل الملفات عام 1966. ^{[ 3 ]} تُحسب قيمة Z لنقطة في فضاء متعدد الأبعاد ببساطة عن طريق تداخل البتات للتمثيلات الثنائية لقيم إحداثياتها. مع ذلك، عند الاستعلام عن نطاق بحث متعدد الأبعاد في هذه البيانات، لا يُعدّ استخدام البحث الثنائي فعالًا: إذ من الضروري حساب قيمة Z التالية الممكنة، انطلاقًا من نقطة مُصادفة في بنية البيانات ، والتي تقع ضمن نطاق البحث متعدد الأبعاد، ويُطلق عليها اسم BIGMIN. طُرحت مسألة BIGMIN لأول مرة وعُرض حلها بواسطة تروبف وهرتسوغ عام 1981. ^{[ 4 ]} بمجرد فرز البيانات باستخدام تداخل البتات، يمكن استخدام أي بنية بيانات أحادية البعد، مثل المصفوفات البسيطة أحادية البعد ، وأشجار البحث الثنائية ، وأشجار B ، وقوائم التخطي ، أو جداول التجزئة (مع اقتطاع البتات ذات الأهمية المنخفضة) . ويمكن وصف الترتيب الناتج بشكل مكافئ بأنه الترتيب الذي يمكن الحصول عليه من اجتياز شجرة رباعية أو ثمانية باستخدام البحث العمقي أولاً .

يوضح الشكل أدناه قيم Z للحالة ثنائية الأبعاد بإحداثيات صحيحة 0  ≤ x ≤ 7، 0 ≤ y ≤ 7 (موضحة بالنظامين العشري والثنائي). يؤدي تداخل قيم الإحداثيات الثنائية (بدءًا من اليمين بت x (باللون الأزرق) والتناوب إلى اليسار بت y (باللون الأحمر)) إلى الحصول على قيم z الثنائية (مائلة بزاوية 45 درجة كما هو موضح). يؤدي توصيل قيم z بترتيبها العددي إلى تكوين منحنى على شكل حرف Z بشكل متكرر. تُعرف قيم Z ثنائية الأبعاد أيضًا بقيم المفتاح الرباعي.       

يتم وصف قيم Z لإحداثيات x كأعداد ثنائية من متتالية Moser–de Bruijn ، والتي تحتوي على بتات غير صفرية فقط في مواضعها الزوجية:

x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}

يتم حساب مجموع وفرق قيمتين x باستخدام عمليات البت :

x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101 x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101 إذا كان i ≥ j

يمكن استخدام هذه الخاصية لتعويض قيمة Z، على سبيل المثال في بعدين، تكون الإحداثيات إلى الأعلى (انخفاض y)، والأسفل (زيادة y)، واليسار (انخفاض x)، واليمين (زيادة x) من قيمة Z الحالية z هي:

أعلى = (((ض & 0b10101010) − 1) & 0b10101010) | (ض & 0b01010101) bottom = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101) left = (((z & 0b01010101) − 1) & 0b01010101) | (z & 0b10101010) صحيح = (((ض | 0b10101010) + 1) & 0b01010101) | (ض & 0b10101010)

وبشكل عام، لجمع قيمتين ثنائيتي الأبعاد من نوع Z، وهما w و z :

المجموع = ((ض | 0b10101010) + (ث & 0b01010101) & 0b01010101) | ((ض | 0b01010101) + (ث & 0b10101010) & 0b10101010)

يمكن استخدام ترتيب Z لبناء شجرة رباعية (ثنائية الأبعاد) أو شجرة ثمانية (ثلاثية الأبعاد) بكفاءة لمجموعة من النقاط. ^{[ 5 ] [ 6 ]} الفكرة الأساسية هي فرز مجموعة المدخلات وفقًا لترتيب Z. بمجرد فرزها، يمكن تخزين النقاط في شجرة بحث ثنائية واستخدامها مباشرةً، وهو ما يُسمى شجرة رباعية خطية، ^{[ 7 ]} أو يمكن استخدامها لبناء شجرة رباعية قائمة على المؤشرات.

تُقاس نقاط الإدخال عادةً في كل بُعد لتكون أعدادًا صحيحة موجبة، إما كتمثيل نقطة ثابتة على نطاق الوحدة [0، 1] أو بما يتوافق مع حجم كلمة الآلة. كلا التمثيلين متكافئان ويسمحان بإيجاد البت غير الصفري ذي الرتبة الأعلى في وقت ثابت. لكل مربع في الشجرة الرباعية طول ضلع يساوي قوة العدد 2 ، وإحداثيات زواياه هي مضاعفات طول الضلع. عند إعطاء أي نقطتين، يكون المربع الناتج عنهما هو أصغر مربع يغطيهما معًا. يُطلق على عملية تداخل البتات من مركبتي x و y لكل نقطة اسم " خلط x و y " ، ويمكن توسيعها لتشمل أبعادًا أعلى. ^{[ 5 ]}

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

تُخفي عملية XOR البتات ذات الرتبة الأعلى التي تتطابق فيها الإحداثيتان. وبما أن عملية التبديل تُبدّل البتات من الرتبة الأعلى إلى الرتبة الأدنى، فإن تحديد الإحداثي ذي البت الأكثر أهمية يُحدد أول بت مختلف في ترتيب التبديل، ويمكن استخدام هذا الإحداثي لمقارنة النقطتين. ^{[ 8 ]} يوضح ذلك كود بايثون التالي:

def cmp_zorder ( lhs , rhs ) -> bool : """مقارنة ترتيب Z.""" # نفترض أن lhs و rhs عبارة عن كائنات شبيهة بالمصفوفات تحتوي على مؤشرات. assert len ( lhs ) == len ( rhs ) # سيحتوي على البُعد الأكثر أهمية. msd = 0 # التكرار على الأبعاد الأخرى. for dim in range ( 1 , len ( lhs )): # التحقق مما إذا كان البُعد الحالي أكثر أهمية # من خلال مقارنة البتات الأكثر أهمية. if less_msb ( lhs [ msd ] ^ rhs [ msd ], lhs [ dim ] ^ rhs [ dim ]): msd = dim return lhs [ msd ] < rhs [ msd ]

إحدى طرق تحديد ما إذا كانت البتة الأكثر أهمية أصغر هي مقارنة الجزء الصحيح من اللوغاريتم ذي الأساس 2 لكل نقطة. اتضح أن العملية التالية مكافئة، ولا تتطلب سوى عمليات "أو" الحصرية: ^{[ 8 ]}

دالة less_msb ( x : int , y : int ) -> bool : تُرجع x < y و x < ( x ^ y )

من الممكن أيضاً مقارنة الأعداد العشرية باستخدام نفس الأسلوب. less_msbيتم تعديل الدالة لمقارنة الأسس أولاً. وعندما تتساوى، less_msbتُستخدم الدالة القياسية على الأجزاء الكسرية فقط. ^{[ 9 ]}

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

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

بدلاً من إنشاء شجرة رباعية تعتمد على المؤشرات، يمكن الاحتفاظ بالنقاط مرتبةً في بنية بيانات مثل شجرة البحث الثنائية. يتيح ذلك إضافة النقاط وحذفها في زمن قدره O (log n ) . يمكن دمج شجرتين رباعيتين بدمج مجموعتي النقاط المرتبتين، وإزالة النقاط المكررة. يمكن تحديد موقع النقطة بالبحث عن النقاط السابقة واللاحقة لنقطة الاستعلام بالترتيب المرتب. إذا كانت الشجرة الرباعية مضغوطة، فقد تكون العقدة السابقة التي تم العثور عليها ورقةً عشوائيةً داخل العقدة المضغوطة المطلوبة. في هذه الحالة، من الضروري إيجاد سلف أصغر سلف مشترك لنقطة الاستعلام والورقة التي تم العثور عليها. ^{[ 10 ]}

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

في هذا المثال، يُشار إلى النطاق المطلوب البحث فيه ( x  =  2،  ...،  3، y  =  2،  ...،  6) بالمستطيل المنقط. أعلى قيمة Z فيه (MAX) هي 45. في هذا المثال، تُصادف القيمة F  =  19 عند البحث في بنية البيانات باتجاه تزايد قيمة Z، لذا يجب البحث في الفترة بين F وMAX (المنطقة المظللة). لتسريع البحث، يتم حساب قيمة Z التالية ضمن نطاق البحث، والتي تُسمى BIGMIN (36 في المثال)، والبحث فقط في الفترة بين BIGMIN وMAX (القيم المكتوبة بخط غامق)، وبالتالي تخطي معظم المنطقة المظللة. البحث في اتجاه تناقصي يُشابه LITMAX، وهي أعلى قيمة Z في نطاق البحث أقل من F. طُرحت مشكلة BIGMIN لأول مرة وعُرض حلها في بحث تروبف وهيرتسوغ. ^{[ 4 ]} للاطلاع على تاريخها بعد النشر، انظر ^{[ 11 ] .}

يقدم تروبف في عام 2021 شرحًا وافيًا لخوارزمية حساب LITMAX/BIGMIN، بالإضافة إلى شفرة مصدرية بلغة باسكال (ثلاثية الأبعاد، سهلة التعديل لتناسب n-أبعاد) وتلميحات حول كيفية التعامل مع بيانات الفاصلة العائمة، وربما البيانات السالبة. لا يتم هنا إجراء تداخل البتات بشكل صريح؛ إذ تحتوي بنية البيانات على مؤشرات فقط إلى سجلات قاعدة البيانات الأصلية (غير المصنفة). وبفضل دالة مقارنة السجلات العامة (أكبر من أو يساوي، بمعنى قيمة z)، يتم تجنب التعقيدات المتعلقة بطول تسلسلات البتات الذي يتجاوز طول كلمة الحاسوب، ويمكن تعديل الشفرة بسهولة لتناسب أي عدد من الأبعاد وأي طول لكلمة مفتاح السجل.

بما أن هذا النهج لا يعتمد على بنية البيانات أحادية البعد المختارة، فإنه يتيح حرية اختيار هيكلة البيانات، وبالتالي يمكن استخدام طرق معروفة مثل الأشجار المتوازنة للتعامل مع البيانات الديناميكية، ويستغرق الحفاظ على توازن الشجرة عند الإضافة أو الحذف وقتًا قدره O(log n). تُستخدم هذه الطريقة أيضًا في أشجار UB (المتوازنة). ^{[ 12 ]}

يُسهّل الخيار الحر دمج هذه الطريقة في قواعد البيانات الموجودة. وهذا على عكس أشجار R، على سبيل المثال ، حيث يلزم مراعاة اعتبارات خاصة.

يُتيح تطبيق هذه الطريقة بشكل هرمي (وفقًا لبنية البيانات المتاحة)، مع إمكانية تطبيقها في اتجاه تصاعدي أو تنازلي، بحثًا فعالًا للغاية في نطاق متعدد الأبعاد، وهو أمر بالغ الأهمية في التطبيقات التجارية والتقنية على حد سواء، كإجراء أساسي في عمليات البحث عن أقرب جار. يُعدّ ترتيب Z أحد أساليب الوصول متعددة الأبعاد القليلة التي شقت طريقها إلى أنظمة قواعد البيانات التجارية. ^{[ 13 ]} تُستخدم هذه الطريقة في تطبيقات تقنية متنوعة في مجالات مختلفة. ^{[ 14 ]} وفي أنظمة قواعد البيانات التجارية. ^{[ 15 ]}

في عام 1966، اقترح جي إم مورتون ترتيب Z لتسلسل ملفات قاعدة بيانات جغرافية ثنائية الأبعاد ثابتة. تُخزَّن وحدات البيانات المساحية في إطار تربيعي واحد أو بضعة إطارات، يُمثَّل كل منها بحجمه وقيم Z في الزاوية السفلية اليمنى، وتتوافق الأحجام مع التسلسل الهرمي لترتيب Z عند موضع الزاوية. وباحتمالية عالية، يتم الانتقال إلى إطار مجاور بخطوة مسح واحدة أو بضع خطوات صغيرة نسبيًا. ^{[ 3 ]}

كبديل، تم اقتراح منحنى هيلبرت لأنه يتمتع بسلوك أفضل في الحفاظ على الترتيب، ^{[ 6 ]} وقد تم استخدامه بالفعل في مؤشر مُحسَّن، وهو هندسة S2. ^{[ 16 ]}

• جيوهاش
• شجرة هيلبرت آر
• الجبر الخطي
• التجزئة التي تحافظ على الموقع
• تمثيل المصفوفة
• نظرية نيتو
• شجرة PH
• المؤشر المكاني

• STANN: مكتبة للبحث التقريبي عن أقرب جار، باستخدام منحنى الترتيب Z
• طرق برمجة التداخل البتّي ، شون إيرون أندرسون، جامعة ستانفورد