Բինար բուրգի կիրառության օրինակ

«Common Lisp։ 12 օրինակ» գրքիս խնդիրներից մեկում պահանջվում է տրված անգլերեն տեքստի հիման վրա անգլերեն այբուբենի համար կառուցել Մորզեի կոդավորման սխեմա։ Մորզեի կոդում ամեն մի տառի համապատասխանեցվում է կետ և գիծ նիշերից բաղկացած հաջորդականություն։ Կառուցվելիք սխեմայի համար հիմնական պահանջն այն է, որ տեքստում ավելի հաճախակի հանդիպող տառերին պետք է համապատասխանացնել ավելի կարճ կոդեր։

ՈՒրեմն, նախ պետք է վերլուծել տրված տեքստը և հաշվել անգլերեն այբուբենի 26 տառերից ամեն մեկի հանդիպելու հաճախությունը (ինչքան ավելի մեծ է վերլուծվող տեքստը, այնքան ավելի լավ արդյունքներ կարող ենք ստանալ)։ Այնուհետև պետք է և՛ տառերը դասավորել ըստ հաճախությունների նվազման, և՛ կոդերը դասավորել ըստ երկարությունների աճման։ Վերջում՝ համադրել այս երկու ցուցակները։

Ենթադրենք ունեմ մի histogram ֆունկցիա, որն արգումենտում ստանում է վերլուծվող տեքստը պարունակող ֆայլի անունը և վերադարձնում է անգլերեն այբուբենի տառերի ցուցակը՝ կարգավորված ըստ տեքստում դրանց հանդիպելու հաճախությունների նվազման։ Առայժմ սա դնեմ մի կողմ։
Մորզեի կոդերը կառուցում եմ հետևյալ կերպ։ Քանի որ այբուբենի տառերը 26 հատ են, ապա բավական է կառուցել 1, 2, 2 և 4 երկարությամբ կոդերը, որոնց ընդհանուր քանակը 30 հատ է։ 1. կառուցում եմ մի լրիվ բինար ծառ՝ արմատից բացի ևս չորս մակարդակներով։ 2. ծառի հանգույցները ըստ մակարդակների լրացնում եմ histogram ֆունկցիայի օգնությամբ ստացված ցուցակի տառերով։ 3. վերջում ծառի բոլոր ձախ գնացող ճյուղերը նշում եմ «.» (կետ) նիշով, իսկ դեպի աջ գնացողները՝ «-» (գիծ) նիշով։

Ստանում եմ մոտավորապես այսպիսի պատկեր.

Այս ծառի որևէ հանգույցում գրված տառի Մորզեի կոդը արմատից դեպի տվյալ հանգույցը հասնող կողերի նիշերի հաջորդականությունն է։ Օրինակ E = ., N = -., K = .--.։ Ավելի կոնկրետ. եթե տառը գտնվում է իր ծնողի ձախ կողմում, ապա տվյալ տառի կոդը ստացվում է ծնողի կոդին կցելով «.» նիշը, եթե տառը ծնողի աջ կողմում է, ապա նրա կոդը ստանալու համար ծնողի կոդին պետք է կցել «-» նիշը։

Քանի որ կառուցված ծառը բինար բուրգ է, այն կարող եմ մոդելավորել սովորական միաչափ զանգվածով (մանրամասները «Նախապատվություններով հերթի իրականացումը» գրառման մեջ)։ Զանգվածի 1 և 2 ինդեքսներով դիրքերում գրում եմ «.» և «-» նիշերը, իսկ 3-ից 26 միջակայքի k դիրքերի համար Մորզեի կոդը հաշվում եմ հետևյալ արտահայտությամբ.

c[k] = (c[(k-1)//2] + '.') if k % 2 == 1 else (c[(k-2)//2] + '-')

Սա ասում է, որ եթե \(k\)-ն կենտ է, ապա նրա ծնողի ինդեքսը հաշվել \(\frac{k-1}{2}\) բանաձևով և ծնողի կոդին կցել «.» նիշը, իսկ եթե \(k\)-ն զույգ է, ապա ծնողի ինդեքսը հաշվել \(\frac{k-2}{2}\) բանաձևով և ծնողի կոդին կցել «-» նիշը։ Ահա morsecodes ֆունկցիան, որը տրված n թվի համար կառուցում է 1-ից n երկարությամբ բոլոր Մորզեի կոդերը։

def morsecodes(n):
  c = list(range(n+1))
  c[1] = '.'
  c[2] = '-'
  for k in range(3,n+1):
    c[k] = (c[(k-1)//2] + '.') if k % 2 == 1 else (c[(k-2)//2] + '-')
  return c[1:]

Հիմա արդեն կարող եմ histogram ֆունկցիայով ստանալ ըստ հաճախությունների նվազման դասավորված տառերի ցուցակը, morsecodes ֆունկցիայով ստանալ կոդերի ցուցակը և Python լեզվի zip դրանք միավորել իրար հետ։

result = list(zip(histogram('thevalleyofthemoon.txt'),morsecodes(26)))

* ^* * Որպես վերլուծվող տեքստ ես վերցրել եմ Ջեկ Լոնդոնի «Լուսնի հովիտը» վեպի անգլերեն տարբերակը։ Իսկ վերլուծությունը կատարել եմ ահա այս Python ֆունկցիայով.

def histogram(source):
  alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  his = {c: 0 for c in alphabet}
  with open(source) as inp:
    while True:
      chars = inp.read(4096).upper()
      if chars == '': break
      for ch in filter(lambda c: c in alphabet, chars):
        his[ch] = his[ch] + 1
  return sorted(his, key=his.get, reverse=True)

Նախապատվություններով հերթի իրականացումը

Հերթի այն տեսակը, որտեղ տարրերը կարող են ավելացվել կամայականորեն, բայց կարող են հեռացվել միայն ըստ նրանց մեջ սահմանված կարգի, կոչվում է նախապատվություններով հերթ։ Օրինակ, եթե որպես հերթի մեջ ավելացվող տարրեր դիտարկվում են թվերը, իսկ թվերի մեջ սահմանված կարգ է հանդիսանում "\(<\)" (փոքր է) գործողությունը, ապա ամեն անգամ հերթից որևէ տարր պահանջելով կստանանք այնտեղ եղած տարրերից ամենափոքրը (նույնը կարելի է ասել, իհարկե, "\(>\)" (մեծ է) գործողության նկատմամբ)։ Մեկ այլ օրինակում, եթե հերթի որպես տարրեր դիտարկվում են բառեր (տեքստ), իսկ որպես կարգի հարաբերությունը սահմանված է բառի երկարության նկատմամբ՝ \(|w_1| < |w_2|\), ապա ամեն անգամ հերթից տարր պահանջելով կստանանք այդ պահին հերթում մնացած ամենակարճ բառը։

Նախապատվություններով հերթն իրականացվում է մի տվյալների կառուցվածքի հիման վրա, որին գրականության մեջ տրված է heap (ռուս. куча) անունը։ Սա մի ծառ է (տվյալ դեպքում՝ բինար ծառ), որի ամեն մի հանգույցի արժեքն ավելի փոքր է (մեծ է) իր ժառանգների արժեքներից։ Բնականաբար ծառի արմատում գտնվում է ամենափոքր (կամ ամենամեծ) տարրը։ Այս ծառը նաև լրիվ (բինար) ծառ է։

Դասախոսությունների կամ այլ խոսակցությունների ժամանակ (քանի որ հայերեն գրականություն գործնականում չկա) ես հանդիպել եմ նաև heap տերմինի կույտ բառացի և, իմ կարծիքով, անհաջող թարգմանությանը։ Հանդիպել եմ նաև բուրգ տերմինը, և այս գրառման մեջ կօգտագործեմ հենց այս տարբերակը։

Ենթադրենք արդեն իրականացրել ենք Heap<T> շաբլոնային դասը որն ունի Add(T value) մեթոդը՝ հերթում տարրեր ավելացնելու համար, և T TakeMinimal() մեթոդը՝ հերթից ամենաբարձր նախապատվություն (տվյալ դեպքում՝ ամենափոքր արժեք) ունեցող տարրը հեռացնելու համար։ Ինչպես նաև նախատեսված է արժեքավորող ցուցակով կոնստրուկտոր։ Ստեղծենք int տիպի արժեքների հերթ և նրանում ավելացնենք {32, 9, 23, 14, 17, 2, 20, 17, 6} թվերը։

  Heap h {32, 9, 23, 14, 17, 2, 20, 17, 6};

Այս թվերով կառուցված ծառը կունենա ստորև բերված նկարի տեսքը, որում երևում է, որ ամեն մի հանգույցի արժեք ավելի փոքր է, քան իր ժառանգների արժեքները։ * * * Հիմա ներկայացնեմ իրականացումը։ Սովորաբար բուրգն իրականացվում է ոչ թե ցուցիչների վրա հիմնված դինամիկ կառուցվածքների միջոցով, այլ սովորական ինդեքսավորված վեկտորներով։ Բուրգի արմատի արժեքը գրվում է վեկտորի զրո ինդեքսով բջջում։ Իսկ ամեն մի k ինդեքսով հանգույցի աջ (R) ու ձախ (L) ժառանգների ինդեքսները հաշվվում են L=2k+1 և R=2k+2 բանաձևերով։ Օրինակ, նկարում բերված ծառը վեկտորի տեսքով կներկայանա հետևյալ կերպ.

 Value | 2 | 6 | 9 | 14| 17| 23| 20| 32| 17
-------+---+---+---+---+---+---+---+---+---
 Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

Այս ներկայացումն արդյունավետ է շնորհիվ այն բանի, որ բուրգը լրիվ ծառ է և ամենաներքևի մակարդակը լրացված է ձախից աջ։
Եվ այսպես, C++11 լեզվով սահմանում եմ Heap դասը։ Այս դասի size ստատիկ հաստատունը ցույց է տալիս տարրերի վեկտորի նախնական չափը։ capacity դաշտը ցույց է տալիս բուրգի տարողությունը, իսկ count դաշտը ցույց է տալիս տվյալ պահին առկա տարրերի քանակը։ Տարրերը պահվում են դինամիկ ստեղծվող data զանգվածում։

template
class Heap {
protected:
  static const int size = 32;

  unsigned int capacity;
  unsigned int count;
  T* data;

Դասի կոնստրուկտորներից մեկը պարզապես ստեղծում է դատարկ օբյեկտ, իսկ մյուսը բուրգի մեջ է ավելացնում արժեքավորող ցուցակով տրված տարրերը։ Իսկ դեստրուկտորը պարզապես ազատում է տարրերի զանգվածի զբաղեցրած հիշողությունը։

public:
  Heap()
    : capacity(size), count(0)
  {
    data = new T[capacity];
  }
  
  Heap( std::initializer_list<T> elems )
    : Heap()
  {
    for( auto e : elems )
      Add( e );
  }
    
  virtual ~Heap()
  {
    delete[] data;
  }

Նախապատվություններով հերթում նոր տարր ավելացնելիս նախ այն ավելացվում է զանգված վերջում, ապա, heapify գործողության կիրառմամբ զանգվածի տարրերը վերադասավորվում են այնպես, որ շարունակեն բավարարել բուրգի վերը նշված պահանջներին։ Եթե հերթական տարրն ավելացնելուց հետո պարզվում է, որ զանգվածի տեղերը սպառվել են (count == capacity), ապա զանգվածի երկարությունը կրկնապատկվում է։

  void Add( T val )
  {
    data[count] = val;
    ++count;
    heapify();
    if( count == capacity )
      enlarge();
  }

heapify գործողության ժամանակ տարրը տեղաշարժվում է դեպի ձախ այնքան ժամանակ, քանի դեռ այն փոքր է ծնոսի արժեքից։ Ի դեպ, տրված k ինդեքսով տարրի ծնողի ինդեքսը որոշվում է (k - 1)/2 բանաձևով։

  void heapify()
  {
    unsigned int i(count - 1);
    unsigned int k((i - 1) / 2);
    while( i > 0 && data[i] < data[k] ) {
      auto temp(data[i]);
      data[i] = data[k];
      data[k] = temp;
      i = k;
      k = (i - 1) / 2;
    }
  }

Զանգվածն ընդլայնող enlarge մեթոդը համակարգից պահանջում է գոյություն ունեցողից երկու անգամ մեծ հիշողություն, տարրերն արտագրում է այդ նոր տիրույթում և համակարգին է վերադարձնում հին տարածքը։

  void enlarge()
  {
    T* temp(data);
    capacity *= 2;
    data = new T[capacity];
    for( unsigned int i = 0; i < count; ++i )
      data[i] = temp[i];
    delete[] temp;
  }

Նախապատվություններով հերթից ամենաբարձր նախապատվություն ունեցող տարրը հեռացնելու համար գրված է TakeMinimal մեթոդը։ Այն հեռացնում է բուրգի գագաթի տարրը, ապա մյուս տարրերը վերադասավորում է այնպես, որ նրանք շարունակեն բավարարել բուրգի պայմաններին և վերադարձնում է հեռացված արժեքը։ Այս մեթոդում վերադասավորման համար օգտագործված է heapify մեթոդը։ Բայց գաղափարն այն է, որ ամենաներքևի մակարդակի ամենաաջ տարրը տեղափոխվում է բուրգի գագաթը, ապա այն փոխատեղվում է իր ժառանգներից ամենափոքրի հետ այնքան ժամանակ, քանի դեռ չի հասել իր իսկական տեղին։

  T TakeMinimal()
  {
    auto result(data[0]);
    data[0] = data[--count];
    heapify();
    if( count * 2 == capacity )
      reduce();
    return result;
  }

TakeMinimal մեթոդով որևէ տարր հեռացնելուց հետո ստգուգվում է տարրերի զանգվածի վիճակը։ Եթե զանգվածի տարողությունը երկու անգամ մեծ է տարրերի իրական քանակից՝ count * 2 == capacity, ապա զանգվածի չափը կրճատվում է երկու անգամ։ reduce մեթոդը ստեղծում է երկու անգամ փոքր տիրույթ, տարրերն արտագրում է նրա մեջ, ապա համակարգին է վերադարձնում ին մեծ տիրույթը։

  void reduce()
  {
    if( capacity > size ) {
      capacity /= 2;
      auto temp(data);
      data = new T[capacity];
      for( unsigned int i = 0; i < count; ++i )
        data[i] = temp[i];
      delete[] temp;
    }
  }
};

* * * Առայժմ այսքանը նախապատվություններով հերթերի մասին։ Չնայած որ տեքստը մի քիչ կցկտուր ստացվեց, բայց, կարծում եմ, որ ընդհանուր առմամբ այն հասկանալի է։