موضوع مقاله: خم مرتبه زد | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # خم مرتبه زد | مقدمه: این نام از گای مک دونالد مورتون گرفته شده‌است که برای اولین بار دستور ترتیب دهی فایل‌ها را در سال ۱۹۶۶ داد. | ## بخش 1: خم مرتبه زد | مقدار z یک نقطه در چند بعد به سادگی با در هم آمیختن مقادیر دودویی مختصات آن محاسبه می‌شود. پس از طبقه‌بندی داده‌ها به این ترتیب، می‌توان از هر داده ساختار یک بعدی مانند درخت جستجوی دودویی، درختان B، لیست پرشی یا جدول‌های درهمسازی استفاده کرد. مقادیر مختصات جدول زیر مقادیر Z را در دو بعد نشان می‌دهد که ۰ ≤ x ≤ ۷، ۰ ≤ y ≤ ۷ است (هم در مبنای ۱۰ و هم به صورت دودویی نشان داده می‌شود) در هم آمیختن مقادیر مختصات باینری مقادیر باینری z را بازمی‌گرداند. پس از مرتب‌سازی، نقاط هم می‌توانند در یک درخت دودویی جستجوی ذخیره شوند و به‌طور مستقیم استفاده شوند، که به آن چاردرخت خطی گفته می‌شود،. نقاط ورودی معمولاً در هر بعدی به صورت اعداد صحیح مثبت هستند، چه به عنوان یک نقطه ثابت در محدوده [۰ ، ۱] و چه متناسب با طول کلمه دستگاه. هر دو نمایش معادل هستند و اجازه می‌دهند بالاترین مرتبه بیت غیر صفر در زمان ثابت یافت شود. هر مربع در چاردرخت دارای طول ضلع است که توان آن دو است و مختصات گوشه که مضرب طول ضلع است. با توجه به هر دو نقطه، مربع بدست آمده برای دو نقطه، کوچکترین مربع است که هر دو نقطه را پوشش می‌دهد. نقاط را می‌توان با توجه به شافل آن‌ها طبقه‌بندی کرد بدون اینکه صریحاً بیت‌ها در هم آمیخته شود. برای انجام این کار، برای هر بعد، چپ‌ترین بیت از XOR مختصات دو نقطه، برای آن بعد مورد بررسی قرار می‌گیرد. بعدی که بیت سمت چپ آن از بقیه بزرگتر است برای مقایسه دو نقطه برای تعیین ترتیب شافل آن‌ها استفاده می‌شود. عملیات XOR بیت‌های مرتبه بالاتر که در آن‌ها دو مختصات یکسان هستند را تعیین می‌کند. از آنجا که شافل، بیت‌ها را از مرتبه بالاتر به مرتبه پایین‌تر به هم می‌ریزد، مختصات با بزرگترین بیت سمت چپ را اینگونه شناسایی می‌کند که ابتدا اولین بیت در ترتیب شافل که متفاوت است را شناسایی می‌کند و از این مختصات برای مقایسه دو نقطه استفاده می‌کند.. | ## بخش 2: خم مرتبه زد | هنگامی که امتیازها مرتب شدند، دو ویژگی باعث می‌شود که یک چاردرخت آسان ساخته شود: اولین نکته این است که نقاط موجود در یک مربع چاردرخت، به صورت مرتب شده و با فاصلهٔ متناوب باشند. دوم اینکه اگر بیش از یک بچهٔ مربع دارای یک نقطه ورودی باشد، مربع از دو نقطهٔ مرتب شدهٔ مجاور نشات گرفته شده‌است. برای هر دو نقطهٔ مجاور، مربع بدست آمده محاسبه می‌شود و طول آن مشخص می‌شود و برای هر مربع بدست آمده، فاصلهٔ شامل آن مربع توسط اولین مربع بزرگتر سمت راست و اولین مربع بزرگتر سمت چپ که به صورت مرتب شده هستند بدست می‌آید. نتیجه این کار یک چاردرخت فشرده شده‌است، که در آن فقط گره‌های حاوی نقاط ورودی یا دو یا چند بچه در آن حضور دارند. در صورت تمایل می‌توانید با قرار دادن گره‌های از دست رفته یک چاردرخت غیر فشرده بسازید. به جای ایجاد یک چاردرخت مبتنی بر پوینتر، نقاط را می‌توان به صورت مرتب شده در داده ساختاری مانند درخت جستجوی دودویی حفظ کرد. دو چاردرخت را می‌توان با ادغام دو مجموعهٔ مرتب شده از نقاط، و از بین بردن تکراری‌ها ادغام کرد. جای نقاط را می‌توان با جستجوی نقاط قبل و دنبال کردن نقطهٔ پرسیده شده به ترتیب مرتب شده انجام داد. اگر چاردرخت فشرده شده باشد، گره قبلی پیدا شده ممکن است یک برگ دلخواه در داخل گره فشرده شدهٔ مورد نظر باشد. در این حالت، لازم است که اولین جد مشترک نقطه پرسیده شده و برگ پیدا شده را پیدا کنیم. استفاده برای جستجوی دامنه با داده ساختارهای یک بعدی اگرچه این کار به خوبی مکان را حفظ می‌کند ولی برای جستجوی کارآمد دامنه، یک الگوریتم برای محاسبات از نقطه‌ای که در داده ساختار مشاهده می‌شود تا مقدار بعدی Z که در محدوده جستجو چند بعدی است لازم است: وسط|400x400پیکسل در این مثال، دامنه درخواست شده (x = ۲، … , 3, y = ۲، … , ۶) توسط خط چین مستطیل شکل نشان داده شده‌است. در این مثال مقدار F = ۱۹ در هنگام جستجوی یک داده ساختار در جهت افزایش مقدار Z با مشکل روبرو می‌شود، بنابراین باید در فاصلهٔ بین F و مقدار بیشینه جستجو کنیم. برای سرعت بخشیدن به جستجو، مقدار بعدی Z را که در محدوده جستجو قرار دارد محاسبه می‌کنیم که به آن مینیمم بزرگ می‌گوییم (نقطهٔ ۳۶ در مثال) و فقط در بازهٔ بین مینیمم بزرگ و نقطهٔ بیشینه جستجو می‌کنیم، بنابراین از بسیاری از قسمت‌ها می‌پریم. | ## بخش 3: خم مرتبه زد | جستجو در جهت کاهش مقدار، مشابه با LITMAX است که همان بیشترین مقدار Z در دامنهٔ پرسیده شدهٔ کوچک‌تر از F است. از آنجا که این رویکرد به داده ساختار یک بعدی انتخاب شده بستگی ندارد، انتخاب داده ساختار هنوز آزاد است، بنابراین می‌توان از روش‌های شناخته شده‌ای مانند درختان متوازن استفاده کرد (در مقابل برای داده ساختاری مانند درخت مستطیلی ملاحظات ویژه لازم است) به همین ترتیب، این استقلال باعث می‌شود که قرار دادن این روش در پایگاه داده‌های موجود آسان شود. استفاده از روش سلسله مراتب (با توجه به داده ساختار موجود)، به صورت اختیاری در هر دو جهت افزایش و کاهش، در بازه چندبعدی بازده بسیار کارآمدی دارد که در هر دو زمینهٔ تجاری و برنامه‌های فنی مهم است، به عنوان مثال روشی برای جستجوی نزدیک‌ترین همسایه. مرتبه Z یکی از معدود روشهای دسترسی چند بعدی است که راه خود را به سیستم‌های پایگاه دادهٔ تجاری پیدا کرده‌است (پایگاه داده اوراکل ۱۹۹۵،. در سال ۱۹۶۶، مورتن مرتبه Z را برای ترتیب دهی فایل‌های یک پایگاه داده جغرافیایی ایستا در دو بعد ارائه داد. ناحیهٔ واحدهای داده در یک یا چند فریم چهار درجه‌ای قرار داده شده‌اند که با اندازه‌های خود و گوشهٔ پایین سمت راست مقدار Z خود نشان داده شده‌اند، اندازه‌ها با سلسله مراتب مرتبه Z گوشه‌ها مطابقت دارد. ساختارهای مرتبط به عنوان یک گزینه جایگزین، منحنی هیلبرت پیشنهاد شده‌است زیرا مرتبه را بهتر حفظ می‌کند و در هندسه S2 نیز استفاده شده‌است. قبل از S2، از این روش استفاده نمی‌شد زیرا محاسبات آن پیچیده‌است و منجر به پردازنده‌ای خاص می‌شود. برای مطالعه راجع‌به پردازش داده‌های چند بعدی مانند جستجوی نزدیکترین همسایه، به کتاب هانان سامت مراجعه کنید.. مرتب کردن عناصر ماتریس در مرتبهٔ Z باعث بهبود مکان می‌شود و این مزیت را هم دارد که (در مقایسه با مرتب‌سازی ردیف یا ستون اصلی) که برای ضرب دو قسمت نیازی به دانستن اندازه کل ماتریس نداریم بلکه فقط اندازه قسمت‌ها و مکان آنها در حافظه برای ما کافی است. نگاشت بافت برخی از واحدهای پردازش گرافیکی نقشه‌های بافت را در مرتبهٔ Z ذخیره می‌کنند تا مکان مرجع را در حین نقشه‌برداری بافت افزایش دهد. این به حافظهٔ نهان سی‌پی‌یو اجازه می‌دهد کاشی‌های مربع را نمایان کند و احتمال این که دسترسی‌های مجاور در حافظه باشند را افزایش می‌دهد. این امری مهم است زیرا رندر کردن سه‌بعدی شامل تغییرات دلخواه (چرخش، مقیاس بندی، چشم‌انداز و تحریف توسط سطوح متحرک) می‌شوند. | ## جمع‌بندی | رمزگذاری تصویر/ویدئو یک تصویر یا یک ویدیو در واقع یک ماتریس است، ماتریس را به برداری از پیکسل‌ها در مرتبهٔ z تبدیل می‌کند، سپس بردار پیکسل را فشرده و رمزگذاری می‌کند.