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

«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)