Minimal so'rov oralig'i - Range minimum query

Minimal so'rovni hal qilish uchun tegishli dekartian daraxtini qurish.
Minimal so'rovlar diapazoniga qisqartirildi eng past umumiy ajdod muammo.

Informatika fanida, a minimal so'rov oralig'i (RMQ) taqqoslanadigan narsalar qatori kichik massivida minimal qiymatni topish masalasini hal qiladi. Minimal so'rovlar qatori kompyuter fanida bir nechta foydalanish holatlariga ega, masalan eng past umumiy ajdodlar muammosi va eng uzun tarqalgan prefiks muammosi (LCP).

Ta'rif

Bir qator berilgan A[1 … n] ning n dan olingan narsalar butunlay buyurtma qilingan to'plam, masalan, butun sonlar, minimal so'rov oralig'i RMQA(l,r) = arg min A[k] (bilan 1 ≤ l ≤ k ≤ r ≤ n) belgilangan kichik massivdagi minimal elementning holatini qaytaradi A[l … r].

Masalan, qachon A = [0,5,2,5,4,3,1,6,3], keyin pastki qator uchun minimal so'rovga javob A[3 … 8] = [2,5,4,3,1,6] bu 7, kabi A[7] = 1.

Algoritmlar

Sadolatli eritma

Odatda, sozlamada, qator A statikdir, ya'ni bir qator so'rovlar paytida elementlar qo'shilmaydi yoki o'chirilmaydi va on-layn javob beriladigan so'rovlar (ya'ni, algoritm uchun barcha so'rovlar to'plami oldindan ma'lum emas). Bunday holda, massivni ma'lumotlar tuzilmasiga mos ravishda qayta ishlash tezroq javob berishni ta'minlaydi. Achchiq echim - barcha mumkin bo'lgan so'rovlarni oldindan hisoblash, ya'ni barcha sub-qatorlarning minimal miqdori A, va ularni qatorda saqlang B shu kabi B[men, j] = min (A[men…j]); keyin qator oralig'idagi so'rov doimiy ravishda qatorni qidirish yo'li bilan hal qilinishi mumkin B. Lar bor Θ (n²) mumkin bo'lgan so'rovlar -n qatori va ularga javoblarni hisoblash mumkin Θ (n²) vaqt o'tishi bilan dinamik dasturlash.[1]

Doimiy vaqt va lineeritmik bo'shliqdan foydalangan holda echim

Yuqoridagi echimdagi kabi, doimiy ravishda so'rovlarga javob berish oldindan hisoblash natijalari yordamida amalga oshiriladi. Shu bilan birga, massiv barcha elementlar uchun oldindan hisoblangan min-so'rovlarni va faqat hajmi ikkitaga teng bo'lgan diapazonlarni saqlaydi. Lar bor Θ (log.) n) har bir boshlang'ich pozitsiyasi uchun bunday so'rovlar men, shuning uchun dinamik dasturlash jadvalining hajmi B bu Θ (n jurnal n). Har bir element B[men, j] diapazonning minimal indeksiga ega A[men…men+2j-1]. Jadval takrorlanish yordamida minima indekslari bilan to'ldiriladi[1]

Agar A[B[men, j-1]] ≤ A[B[men+2j-1, j-1]], keyin B[men, j] = B[men, j-1];
boshqa, B[men, j] = B[men+2j-1, j-1].

So'rov RMQA(l,r) endi uni ikkita alohida so'rovlarga bo'lish orqali javob berish mumkin: biri oldindan hisoblangan so'rov - dan intervalgacha l dan kichikroq eng yuqori chegaraga r. Ikkinchisi - bir xil uzunlikdagi intervalning so'rovi r uning o'ng chegarasi sifatida. Ushbu intervallar bir-biri bilan qoplanishi mumkin, ammo, masalan, yig'indidan ko'ra minimal hisoblanganligi sababli, bu muhim emas. Umumiy natijani doimiy vaqt ichida olish mumkin, chunki bu ikkita so'rovga doimiy vaqt ichida javob berish mumkin va faqat ikkita natijadan kichikroq qismini tanlash qoladi.

Natijalar jadvali A = [0,5,2,5,4,3,1,6,3]
 k
0123
l11111
22337
33337
44567
55677
66777
77777
88777
99777

Logaritmik vaqt va chiziqli bo'shliqdan foydalangan holda echim

Ushbu echim RMQ-larga javob beradi O(log n) vaqt. Uning ma'lumotlar tuzilmalaridan foydalaniladi O(n) bo'shliq va uning ma'lumotlar tuzilmalari doimiy ravishda so'rovlarga javob berish uchun ham ishlatilishi mumkin. Massiv avval kontseptual ravishda kattalik bloklariga bo'linadi s = jurnal n/4. Keyin har bir blok uchun minimal miqdorni hisoblash mumkin O(n) umumiy vaqt va minimalar yangi qatorda saqlanadi.

RMQ larga endi logaritmik vaqt ichida chap so'rov chegarasini, so'rovning o'ng chegarasini va ularning orasidagi barcha bloklarni o'z ichiga olgan bloklarga qarab javob berish mumkin:

  • Chegaralarni o'z ichiga olgan ikkita blokni sodda tarzda qidirish mumkin. Chegaradan tashqaridagi elementlarga hatto qarash kerak emas. Buni logaritmik vaqtda bajarish mumkin.
  • So'rovga to'liq javob berish uchun barcha bloklarning minimalarini va yuqorida aytib o'tilgan ikkita minimalarini taqqoslash kerak.
  • Massiv o'lcham bloklariga bo'linganligi sababli jurnal n/4, eng ko'pi bor 4n/jurnal n so'rovda to'liq mavjud bo'lgan bloklar.
  • Lineeritmik echimdan foydalanib, ushbu bloklar orasida umumiy minimumni topish mumkin. Ushbu ma'lumotlar tuzilishi hajmga ega O(n/jurnal n log (n/jurnal n)) = O(n).
  • Endi faqat uchta minimani taqqoslash kerak.

Masalan, massivdan foydalanish A = [0,5,2,5,4,3,1,6,3] va blok hajmi 3 (faqat tushuntirish maqsadida) minimal qatorni beradi A ' = [0,3,1].

Doimiy vaqt va chiziqli bo'shliqdan foydalangan holda echim

Yuqoridagi echimdan foydalanib, so'rovda to'liq bo'lmagan bloklar ichidagi pastki so'rovlarga doimiy ravishda javob berish kerak. Ushbu bloklarning ko'pi bilan ikkitasi mavjud: o'z ichiga olgan blok l va o'z ichiga olgan blok r. Doimiy vaqtga saqlash orqali erishiladi Dekart daraxtlari massivdagi barcha bloklar uchun. Bir nechta kuzatuvlar:

  • Bloklar izomorfik Kartezyen daraxtlari ushbu blokdagi barcha so'rovlar uchun bir xil natijani beradi
  • Ning turli xil dekartian daraxtlari soni s tugunlar Cs, s'th Kataloniya raqami
  • Shuning uchun bloklar uchun turli xil dekartian daraxtlari soni oralig'ida 4s

Har bir bunday daraxt uchun barcha so'rovlar uchun mumkin bo'lgan natijani saqlash kerak. Bu pastga tushadi s2 yoki O(log2 n) yozuvlar. Bu jadvalning umumiy hajmini anglatadi O(n).

Natijalarni samarali qidirish uchun ma'lum bir blokga mos keladigan dekartian daraxti (qatori) doimiy ravishda manzilga ega bo'lishi kerak. Yechim barcha daraxtlar uchun natijalarni massivda saqlash va yozuvlarga murojaat qilish uchun ikkilik daraxtlardan butun songacha noyob proektsiyani topishdir. Bunga erishish orqali erishish mumkin kenglik - birinchi qidiruv daraxt orqali va barg tugunlarini qo'shib, dekartiy daraxtidagi har bir tugunning to'liq ikkita bolasi bo'lishi uchun. Butun son har bir ichki tugunni 0-bit va har bir bargni bit-so'zda 1-bit sifatida ko'rsatish orqali hosil bo'ladi (daraxtni yana darajadagi tartibda bosib o'tish orqali). Bu o'lchamiga olib keladi jurnal n/4 har bir daraxt uchun. Har qanday daraxtga doimiy ravishda tasodifiy kirishni ta'minlash uchun asl qatorda bo'lmagan daraxtlarni ham qo'shish kerak. Ning ko'rsatkichlari bo'lgan qator jurnal n/4 bitlarning kattaligi bor 2jurnal n/4 = O(n).

Uchun dekartiy daraxtlari misoli A = [0,5,2,5,4,3,1,6,3]. E'tibor bering, birinchi va uchinchi daraxtlar bir xil sxemaga ega, shuning uchun chap tomonda jadvalda aniq hisoblangan ikkita so'rovlar to'plami mavjud.
Uch kartezyen bloklari uchun oldindan hisoblangan natijalar A = [0,5,2,5,4,3,1,6,3]
Indeks123
123123123
0—
23 (0010111 bitword)123—23——3
39 (bitword 0100111)111—23——3
127—

Ilovalar

RMQ'lar qatorlarni aniq va taxminiy moslashtirishda ko'plab vazifalar uchun vosita sifatida ishlatiladi. Fischer va Heun (2007) da bir nechta dasturlarni topish mumkin.[2]:3

Daraxtdagi eng past umumiy ajdodni hisoblash

RMQ-lardan eng past umumiy ajdodlar muammosini hal qilish uchun foydalanish mumkin[1][3] va aniq va taxminiy ko'plab vazifalar uchun vosita sifatida ishlatiladi mag'lubiyatni moslashtirish.LCA so'rovi LCAS(v, w) ildiz otgan daraxt S = (V, E) va ikkita tugun v, w ∈ V eng chuqur tugunni qaytaradi siz (bo'lishi mumkin v yoki w) ildizdan ikkalasiga o'tish yo'llarida w va v.Gabow, Bentley va Tarjan (1984) LCA muammosini chiziqli vaqt ichida RMQ muammosiga kamaytirish mumkinligini ko'rsatdi. Bundan kelib chiqadiki, RMQ muammosi singari, LCA masalasi ham doimiy vaqt va chiziqli fazoda echilishi mumkin.[2]

Ipdagi eng uzun tarqalgan prefiksni hisoblash

Matnni indekslash kontekstida RMQ yordamida LCP (eng uzun tarqalgan prefiks) topiladi, bu erda LCPT(men, j) indekslardan boshlanadigan qo'shimchalarning LCP-ni hisoblab chiqadi men va j yilda T.Buni amalga oshirish uchun biz avval qo'shimchalar qatorini hisoblaymiz Ava teskari qo'shimchali qator A−1. Keyin biz LCP qatorini hisoblaymiz H qo'shni qo'shimchalarning LCP-ni berish A. Ushbu ma'lumotlar tuzilmalari hisoblanganda va RMQni qayta ishlash tugallangandan so'ng, umumiy LCP uzunligini doimiy ravishda quyidagi formula bo'yicha hisoblash mumkin: LCP (men, j) = RMQH(A-1[men] + 1, A-1[j]), bu erda biz buni soddaligi uchun taxmin qilamiz A-1[men] + 1 <= A-1[j] (aks holda almashtirish).[4]

Shuningdek qarang

Adabiyotlar

  • Berkman, Omer; Vishkin, Uzi (1993). "Rekursiv yulduzlar daraxti bilan parallel ma'lumotlar tuzilishi". Hisoblash bo'yicha SIAM jurnali. 22 (2): 221–242. doi:10.1137/0222017.
  • Yoxannes Fischer (2009 yil dekabr). Minimal so'rovlar uchun maqbul aniqlik (Texnik hisobot). Universität Tübingen, Bioinformatika markazi. arXiv:0812.2775. Bibcode:2008arXiv0812.2775F.
  1. ^ a b v Bender, Maykl A.; Farax-Kolton, Martin; Pemmasani, Giridxar; Skiena, Stiven; Sumazin, Pavel (2005). "Daraxtlarda eng kam tarqalgan ajdodlar va yo'naltirilgan asiklik grafikalar" (PDF). Algoritmlar jurnali. 57 (2): 75–94. doi:10.1016 / j.jalgor.2005.08.001.
  2. ^ a b Fischer, Yoxannes; Heun, Volker (2007). RMQ-ma'lumotlarning yangi aniq vakili va yaxshilangan qo'shimchalar qatoridagi yaxshilanishlar. Kombinatorika, algoritmlar, probabilistik va eksperimental metodologiyalar bo'yicha xalqaro simpozium materiallari. LNCS. 4614. Springer. 459-470 betlar. doi:10.1007/978-3-540-74450-4_41.
  3. ^ Bender, Maykl; Farax-Kolton, Martin (2000). LCA muammosi qayta ko'rib chiqildi. LATIN 2000: Nazariy informatika. LNCS. 1776. Springer. 88-94 betlar. doi:10.1007/10719839_9.
  4. ^ Fischer, J. va V. Xen (2006). RMQ-muammosi bo'yicha nazariy va amaliy takomillashtirish, LCA va LCE dasturlari bilan. Kombinatorial naqshlarni moslashtirish. Kompyuter fanidan ma'ruza matnlari. 4009. 36-48 betlar. CiteSeerX  10.1.1.64.5439. doi:10.1007/11780441_5. ISBN  978-3-540-35455-0.

Tashqi havolalar