1.8 Որոնում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

Որոնումը կոմպյուտերային ծրագրավորման ամենից շատ հանդիպող գործողություններից է։ Այն նաև իդեալական խնդիր է զանազան տվյալների կառուցվածքները փորձարկելու համար։ ?? Գոյություն ունեն որոնման թեմայի մի քանի վարաիցիաներ, և մշակված են բազմաթիվ ալգորիթմներ։ Հետևյալ քննարկումներում ենթադրվում է, որ տվյալների հավաքածուն, որի մեջ որոնվելու է տրված տարրը, ֆիքսված է։ Կհամարենք, որ N տարրերի բազմությունը տրված է, օրինակ, զանգվածի տեսքով․

a : ARRAY N OF Item

Սովորաբար Item տիպը նկարագրված է որպես գրառում (record), որի դաշտերից մեկը բանալին (key) է։ Խնդիրը բերվում է այն տարրի գտնելուն, որի բանալին հավասար է x որոնման արգումենտին։ Արդյունքում ստացված i ինդեքսը, որ բավարարում է a[i].key = x պայմանին, հնարավորություն է տալիս դիմելու գտնված տարրի մյուս դաշտերին։ Քանի որ մեզ հետաքրքրում է միայն որոնման խնդիրը, և առայժմ չենք մտածում այն մյուս տվյալների մասին, որոնց համար որոնվում էր տարրը, կենթադրենք, որ Item տիպը պարունակում է միայն բանալին, այսինքն այն ինքը հենց բանալին է։

1.8.1 Գծային որոնում

Եթե որոնվող տվյալների մասին այլ լրացուցիչ տեղեկություններ տրված չեն, ապա ակնհայտ մոտեցումը զանգվածի տարրերի հաջորդական դիտարկումն է, քայլ առ քայլ մեծացնելուվ նրա այն հատվածի չափը, որտեղ որոնվող տարրը հայտնաբերված չէ։ Այս մոտեցումը կոչվում է գծային որոնում։ Որոնման ավարտի պայմանները երկուսն են․

1. Տարրը գտնված է, այնսինքն՝ a[i] = x։
2. Դիտարկված է ամբողջ զանգվածը և համընկնում չի հայտնաբերված։

Ստացվում է հետևյալ ալգորիթմը․

i := 0;
WHILE (i < N) & (a[i] # x) DO INC(i) END

ՈՒշադրություն դարձրեք, որ բուլյան արտահայտության մեջ ենթաարտահայտությունների կարգը կարևոր է։

Ցիկլի ինվարիանտը, այսինքն այն պայմանը, որը ճշմարիտ է ցիկլի ամեն մի իտերացիայի սկզբում և վերջում, այսպիսինն է․

(0 ≤ i < N) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այն ցույց է տալիս, որ k֊ից փոքր բոլոր i֊երի համար համընկնումներ չեն եղել։ ՈՒշադրություն դարձնենք նաև, որ ցիկլի ամեն մի իտերացիայից առաջ և հետո i֊ի արժեքները տարբեր են։ Այնուամենայնիվ, ինվարիանտը պահպանվում է ցիկլի պայմանում։

Այս ասվածից և այն փաստից, որ որոնումն ավարտվում է միայն այն ժամանակ, երբ ցիկլի պայմանը տեղի չունի (կեղծ է), կարելի է դուրս բերել վերջնական պամանը․

((i = N) OR (a[i] = x)) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այս պայմանը ոչ միայն մեր ցանկալի արդյունքն է, այլ դրանից նաև հետևում է, որ եթե ալգորիթմը գտել է համընկնում, ապա այն գտել է ամենքփոքր ինդեքսովը, այսինքն՝ առաջինը որոնվող տարրերից։ i = N հավասարությունը ցույց է տալիս, որ համընկնումներ չեն հայտնաբերվել։

Ցիկլի կրկնությունների ավարտը ակնհայտորեն երաշխավորված է, որովհետև ամեն մի քայլում i֊ի արժեքն աճում է, հետևաբար այն, իհարկե, վերջավոր քայլերից հետո կհասնի N֊ին։ Իրականում, եթե համընկնումներ չեն եղել, ապա դա տեղի կունենա N քայլից հետո։

Պարզ է, որ յուրաքանչյուր քայլում պահանջվում է մեծացնել ինդեքսը և հաշվել բուլյան արտահայտությունը։ Կարելի՞ է արդյոք այս խնդիրը պարզեցնել, և դրանով պարզեցնել նաև որոնման գործողությունը։ Միակ հնարավորությունը երկու կտորից բաղկացած բուլյան արտահայտությունը պարզեցնելու մեջ է։ Հետևաբար, միակ տարբերակը այնպիսի ավելի պարզ պայմանի ձևակերպումն է, որը համարժեք է մեր ունեցած բարդ պայմանին։ Դա հնարավոր է, եթե երաշխավորենք, որ համընկնում միշտ տեղի է ունենալու, որին կարելի է հասնել զանգվածի վերջում x արժեքով լրացուցիչ տարր ավելացնելով։ Այս լրացուցիչ տարրը կանվանենք պատնեշ (sentinel), որովհետև այն ինդեքսին արգելում է դուրս ելնել զանգված սահմաններից։ Այժմ a զանգվածը սահմանված է որպես․

a: ARRAY N+1 OF INTEGER

իսկ գծային որոնման ալգորիթմը, պատնեշի օգտագործմամբ, կունենա հետևյալ տեսքը․

a[N] := x; i := 0;
WHILE a[i] # x DO INC(i) END

Նույն ինվարիանտից դուրս բերված վերջնական պայմանը կլինի․

(a[i] = x) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Պարզ է, որ i = N պայմանը ցույց է տալիս համընկնումներ չեն եղել՝ բացառությամբ պատնեշի հետ համընկնելը։

1.8.2 Որոնում կիսման եղանակով (բինար որոնում)

Լրիվ ակնհայտ է, որ այլևս հնարավորություն չկա արագացնելու որոնման գործողությունև, եթե միայն որոնվող տարրերի մասին տրված չեն լրացուցիչ տեղեկություններ։ Հայտնի է, որ որոնումը կարելի է ավելի արդյունավետ դարձնել, եթե տվյալները կարգավորված են։ Պատկերացրեք, օրինակ, մի հեռախոսագիրք, որում անունները այբբենական կարգով դասավորված չեն։ Դա լրիվ անպետք բան է։ Մենք կներկայացնենք ալգորիթմ՝ հիմնված a զանգվածում տարրերի կարգավորված լինելու փաստի վրա, այսինքն՝ հաշվի առնելով հետևյալ պայմանը․

Ak: 1 ≤ k < N: a[k-1] ≤ a[k]

Հիմնական գաղափարն է՝ վերցնել մի պատահական տարր, օրինակ, a[m] և այն համեմատել x որոնման արգումենտի հետ։ Եթե այն հավասար է x֊ին, ապա որոնումն ավարտվում է, եթե այն փոքր է x֊ից, ապա m֊ից փոքր կամ հավասար ինդեքս ունեցող բոլոր տարրերը կարելի է բացառել հետագա որոնումից, և եթե այն մեծ է x֊ից, ապա կարելի է բացառել m֊ից մեծ և հավասար ինդեքս ունեցող տարրերը։ Ասվածից հանգում ենք կիսման եղանակով որոնման ալգորիթմին։ Այն օգտագործում է L և R ինդեքսային փոփոխականները, որոնք ցույց են տալիս զանգվածի այն հատվածի ձախ և աջ սահմանները, որոնցում դեռ կարող է հայտնաբերվել որոնվող տարրը։

L := 0; R := N - 1;
m := L֊ի և R֊ի միջև ընկած որևէ տարր;
WHILE (L <= R) & (a[m] # x) DO
  IF a[m] < x THEN
    L := m + 1
  ELSE
    R := m - 1
  END;
  m := L֊ի և R֊ի միջև ընկած որևէ տարր
END

ՈՒշադրություն դարձրեք այս ալգորիթմի և նախորդ բաժնում նկարագրված գծային որոնման ալգորիթմի հիմնական կառուցվածքային նմանությանը․ այստեղ i ինդեքսի դերկ կատարում է L, m, R եռյակը։ Այդ նմանությունը բացատրելու, և, այնուհետև, ցիկլի կոռեկտության մեջ ավելի լավ համոզվելու համար, մենք ձեռնպահ մնացինք փոքրիկ օպտիմիզացիայից, որը կբացառեր m֊ի երկու նույնական վերագրումները։

Ցիկլի ինվարիանտը, այսինքն՝ ամեմ մի քայլից առաջ ու հետո տեղի ունեցող պայմանը, հետևյալն է․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից դուրս է բերված հետևյալ արդյունքը․

((L > R) OR (a[m] = x)) & (Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից էլ հետևում է․

((L > R) & (Ak: 0 ≤ k < N: a[k] ≠ x)) OR (a[m] = x)

m ինդեքսի ընտրությունը բոլորովին կամայական է այն իմաստով, որ ալգորիթմի կոռեկտությունը դրանից կախված չէ։ Բայց m֊ի ընտրությունն ազդում է ալգորիթմի արդյունավետության վրա։ Պարզ է, որ մեր նպատակն է ցիկլի ամեն մի քայլում հետագա որոնումից բացառել որքան հնարավոր է շատ տարրեր՝ անկախ համեմատման արդյունքից։ Լավագույն լուծումը կենտրոնական տարրի ընտրությունն է, որովհետև ամեն մի քայլում այն բացառում է զանգվածի տարրերի կեսը։ Արդյունքում քայլերի առավելագույն քանակը հավասար է log2 N, կլորացված վերև՝ մինչև ամենամոտիկ ամբողջ թիվը։ Այսպիսով, այս ալգորիթմը էականորեն շահեկան է գծային որոնման ալգորիթմից, որում համեմատությունների սպասվող քանակը N/2 է։

Արդյունավետությունը կարելի է մի քիչ լավացնել, տեղերով փոխելով ցիկլի մարմնի IF պայմանները։ Հավասարությունը պետք է ստուգել երկրորդ հերթին, որովհետև այն հանդիպում է միայն մեկ անգամ և բերում է ցիկլի ավարտին։ Բայց ավելի կարևոր է այն հարցը, թե արդյոք, ինչպես գծային որոնման դեպքում, հնարավո՞ր է գտնել ցիլի ավարտը որոշող ավելի պարզ պայման։ Իսկապես մենք գտնում ենք այդպիսի արագ ալգորիթմ, հենց որ հրաժարվում ենք որոնման ցիկլը տարրերի համընկնումով ավարտելու միամիտ ցանկությունից։ Առաջին հայացքից սա տարօրինակ է թվում, բայց ավելի ուշադիր ուսումնասիրությամբ բացահայտվում է, որ ամեն մի քայլում արդյունավետության շահն ավելին է, քան մի քանի լրացուցիչ տարրերի համեմատումից ստացված կորուստները։ Հիշենք, որ քայլերի առավելագույն քանակը log N է։

Արագ լուծումը հիմնված է հետևյալ ինվերիանտի վրա․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R ≤ k < N: a[k] ≥ x)

և որոնումը շարունակովում է այնքան ժամանակ, քանի դեռ երկու հատվածները չեն ծածկել ամբողջ զանգվածը։

L := 0; R := 0;
WHILE L < R DO
  m := (L + R) DIV 2;
  IF a[m] < x THEN L := m + 1 ELSE R := m END
END

Ավարտի պայմանն է L ≥ R։ Բայց հասանելի՞ է արդյոք այն։ Այս պնդումն ապացուցելու համար պետք է ցույց տանք, որ բոլոր դեպքերում R - L տարբերությունը նվազում է ամեն մի քայլից հետո։ L < R տեղի ունի յուրաքանչյուր քայլ սկզբում։ m թվաբանական միջինի կամար ճշմարիտ է L ≤ m < R։ Հետևաբար, տարբերությունն իրոք նվազում է L֊ին m+1 վերգրելով (Լ-ը մեծացնելով), կամ R֊ին m վերագրելով (R֊ը նվազեցնելով), և ցիկլի կրկնությունն ավարտվում է L = R պայմանով։

Այնուամենայնիվ, մեր ինվարիանտը և L = R պայմանը դեռևս համընկնում չեն նշանակում։ Իհարկե, եթե R = N, ապա համընկնում չկա։ Այլապես պետք է հաշվի առնենք, որ a[R] տարրը երբեք չի համեմատվել։ Հետևաբար, մի լրացուցիչ a[R] = x հավասարության ստուգումն անհրաժեշտ է։ Ի տարբերություն առաջին լուծման, այս ալգորիթմը, ինչպես և գծային որոնումը, գտնում է ամենափոքր ինդեքսով համընկնող տարրը։

1.8.3 Որոնում աղյուսակում

Զանգվածում որոնումը երբեմն անվանում են նաև որոնում աղյուսակում, հատկապես եթե բանալիները բաղադրյալ օբյեկտներ են, ինչպես օրինակ թվերի կամ նիշերի զանգվածը։ Վերջինս հոնդիպում է ավելի հաճախ․ նիշերի զնգվածներն անվանում են տողեր կամ բառեր։ Սահմանենք String տիպը հետևյալ կերպ․

String = ARRAY M OF CHAR

իսկ x և y տողերի միջև կարգը սահանենք հետևյալ կերպ․

(x = y) ≡ (Aj: 0 ≤ j < M : x[j] = y[j])

(x < y) ≡ Ei: 0 ≤ i < N : ((Aj: 0 ≤ j < i : x[j] = y[j]) & (x[i] < y[i]))

Ակնհայտ է, որ համընկնումը հաստատելու համար, պետք է համոզվենք, որ համեմատվող տողերի բոլոր նիշերը համընկնում են։ Բաղադրյալ օպերանդների այսպիսի համեմատումը բերվում է օպերանդներում չհամընկնող մասերի հայտնաբերմանը, այսինքն՝ անհավասարության որոնման։ Եթե գոյություն չունի չհամընկնող մասեր, ապա հավասարությունը հաստատված է։ Ենթադրենք բառերի երկարությունը բավականաչափ փոքր է, ասենք 30֊ից փոքր, այդ դեպքում կօգտագործենք գծային որոնումը։

Շատ գործնական կիրառություններում ցանկալի է ընդունել, որ տողն ունի փոփոխական երկարություն։ Սա ենթադրում է, որ յուրաքանչյուր տողի հետ պահվում է նաև իր երկարությունը։ Օգտագործելով վերը սահմանված String տիպը, այդ երկարությունը չպետք է գերազանցի M առավելագույն արժեքը։ Այս սխեման բավականաչափ ճկուն է և ընդունելի է շատ դեպքերում, ինչպես նաև ազատում է դինամիկ հիշողության հետ աշխատելու դժվարություններից։ Լայնորեն օգտագործվում են տողի երկարությունը ներկայացնելու երկու ներկայացումներ․

1. Երկարությունը բացահայտ նշվում է տողի վերջում մի հատուկ նիշ կցելով, որը այլ տեղերում չի հանդիպում։ Սովորաբար դա 0X չարտածվող արժեքն է։ (Հետագա կիրառություններում կարևոր է, որ այդ հատուկ նիշը նիշերի բազմության ամենափոքր տարրն է։)
2. Երկարությունը բացահայտ նշվում է զանգվածի առաջին տարրում, այսինքն տողն ունի հետևյալ տեսքը․

s = s[0], s[1], s[2], ..., s[N-1]

որտեղ s[1]...s[N-1] տողի նիշերն ենմ և s[0] = CHR(N)։ Այս եղանակի առավելությունն այն է, որ երկարությունն ուղղակի մատչելի է, իսկ թերությունն այն է, որ տողի երկարությունը սահմանափակված է նիշերի բազմության հզորությամբ, այն է՝ 256 նիշ՝ ASCII կոդավորման դեպքում։

Ստորև բերված որոնման ալգորիթմում նախապատվությունը կտանք առաջին սխեմային։ Այդ դեպքում տողերի համեմատումն ընդունում է հետևյալ տեսքը․

i := 0;
WHILE (x[i] # 0X) & (x[i] = y[i]) DO i := i + 1 END

Այստեղ եզրափակող նիշը կատարում է պատնեշի դերը։ Ցիկլի ինվարիանտն է․

Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X

Իսկ վերջնական պայմանն ունի հետևյալ տեսքը․

((x[i] = 0X) OR (x[i] ≠ y[i])) & (Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X)

Այս պայմանը հաստատում է x և y տողերի հավասարությունը, երբ x[i] = y[i], և հաստատում է x < y պայմանը, եթե x[i] < y[i]։

Հիմա արդեն պատրաստ ենք վերադառնալու աղյուսակում որոնման խնդրին։ Այն պահանջվում է ներդրված որոնումներ, ավելի ճիշտ՝ որոնում աղյուսակի տարրերով, իսկ ամեն մի տարրի համար՝ կոմպոնենտների համեմատումների հաջորդականություն։ Օրինակ, թող որ T աղյուսակը և x որոնման արգումենտը սահմանված են այսպես․

T: ARRAY N OF String;
x: String

Ենթադրելով որ N֊ը բավականաչափ մեծ է և աղյուսակի տարրերը կարգավորված են այբբենական կարգով, կօգտագործենք որոնման կիսման մեթոդը։ Օգտագործելով բինար որոնման և տողերի համեմատման վերը մշակված ալգորիթմները, ստանում ենք ծրագրի հետևյալ հատվածը։

i := -1;
L := 0; R := N;
WHILE L < R DO
  m := (L + R) DIV 2;
  i := 0;
  WHILE (x[i] # 0X) & (T[m,i] = x[i]) DO i := i + 1 END;
  IF T[m,i] < x[i] THEN L := m + 1 ELSE R := m END
END;
IF R < N THEN
  i := 0;
  WHILE (x[i] # 0X) & (T[R,i] = x[i]) DO i := i + 1 END
END
(* (R < N) & (T[R,i] = x[i]) պայմանը որոշում է համընկնումը *)