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

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

Python: Կապակցված ցուցակներ (I)

Որպես Python ծրագրավորման լեզվով գրված առաջին ընդգրկուն օրինակ ուզում եմ ներկայացնել կապակցված ցուցակները՝ նրանց ներքին կառուցվածքով և նրանց հետ կատարվող գործողությունների տիպիկ բազմությամբ։ Սկսեմ միակապ ցուցակներից, որոնց ամեն մի հանգույցը պարունակում է ինֆորմացիոն դաշտ և ցուցիչ իրեն հաջորդող հանգույցին։ Մոդելավորենք այդ հանգույցը Python լեզվով սահմանված Node դասով։ Այդ դասի data դաշտը նախատեսված է տվյալների համար, իսկ link դաշտը ցուցիչ է մեկ այլ հանգույցի։ Դասի դաշտերն արժեքավորող __init__ մեթոդը ստանում է հանգույցի data դաշտում գրվելիք տվյալը։

class Node:
  data = 0
  link = None

  def __init__(self, val):
    self.data = val

Node դասի Print մեթոդը արտածում է data դաշտի արժեքը, ապա, եթե link ցուցիչը տարբեր է None արժեքից՝ ցույց է տալիս մեկ այլ հանգույցի, ապա արտածում է ստորակետ սիմվոլը։

  def Print(self):
    c = ', ' if self.link != None else ''
    print(self.data, end=c)

Միակապ հանգույցներով կապակցված ցուցակը սահմանված է որպես List դաս։ Այդ դասի միակ head դաշտը ցույց է տալիս ցուցակի առաջին հանգույցին։

class List:
  data = None

Եթե head==None, ապա ցուցակը դատարկ է։ Այս վերջին փաստը ծրագրավորված է Empty մեթոդով։

  def Empty(self):
    return None == self.head

Ցուցակի պարունակությունն արտածելու համար սահմանված է Print մեթոդը։ Այն արտածում է «[» նիշը, անցում է կատարում ցուցակի հանգույցներով և ամեն մի հանգույցն արտածում է Node դասի Print մեթոդով, ապա վերջում արտածում է «]» նիշը։

  def Print(self):
    print('[', end='')
    temp = self.head
    while temp != None:
      temp.Print()
      temp = temp.link
    print(']')

Ցուցակի սկզբում նոր տարր (նոր հանգույց) ավելացնելու գործողությունը հասարակ է։ Պետք է ստեղծել նոր հանգույց, նրա link ցուցիչը կապել ցուցակի սկիզբը ցույց տվող head ցուցիչին, ապա head ցուցիչը տեղափոխել նոր ավելացրած հանգույցի վրա։

  def AddFront(self, val):
    nd = Node(val)
    nd.link = self.head
    self.head = nd

Քիչ ավելի շատ գործողություններ է պահանջվում նոր տարրը ցուցակի վերջում ավելացնելու համար։ Ստեղծվում է նոր հանգույց՝ տրված պարունակությամբ։ Եթե ցուցակը դատարկ է՝ head==None, ապա head ցուցիչը կապվում է նոր ստեղծված հանգույցին։ Եթե ցուցակը դատարկ չէ, ապա որևէ ժամանակավոր ցուցիչով որոշվում է ցուցակի վերջին հանգույցը և այդ վերջին հանգույցի link ցուցիչը կապվում է նոր հանգույցին։

  def AddBack(self, val):
    nd = Node(val)
    if self.head == None:
      self.head = nd
    else:
      tail = self.head
      while tail.link != None:
        tail = tail.link
      tail.link = nd

Ցուցակի սկզբից հանգույց հեռացնելու համար head ցուցիչը տեղափոխվում է առաջինին հաջորդող հանգույցի վրա (այն կարող է բացակայել, եթե ցուցակը պարունակում է միայն մեկ հանգույց), և վերադարձվում է հին առաջին (նախորդ) հանգույցի պարունակությունը։ Քանի որ Python-ը աղբի ավտոմատ հավաքման մեխանիզմով լեզու է, կարիք չկա բացահայտ կերպով ազատել հեռացված հանգույցի զբաղեցրած հիշողությունը։

  def RemoveFront(self):
    if self.head == None:
      return None
    t = self.head
    self.head = t.link
    t.link = None
    return t.data

Ցուցակի վերջից հանգույց հեռացնելու համար էլի պետք է մի քանի գործողություն ավել անել։ Նախ, եթե ցուցակը դատարկ է, ապա ոչինչ անել պետք չէ։ Եթե ցուցակը պարունակում է միայն մեկ տարր, ապա head ցուցիչին վերագրվում է None և վերադարձվում է այդ միակ հանգույցի պարունակությունը։ Եթե ցուցակում մեկից ավելի հանգույցներ են, ապա որևէ ժամանակավոր ցուցիչով որոնվում է նախավերջին հանգույցը։ Այդ նախավերջին հանգույցի link ցուցիչին վերագրվում է None, և վերադարձվում է վերջին հանգույցի պարունակությունը։

  def RemoveBack(self):
    if self.head == None:
      return None
    if self.head.link == None:
      val = self.head.data
      self.head = None
      return val
    else:
      tail = self.head
      while tail.link.link != None:
        tail = tail.link
      val = tail.link.data
      tail.link = None
      return val

Ցունցակում տրված արժեքով հանգույցը որոնելու համար Search մեթոդում մի ժամանակավոր ցուցիչ նախ կապվում է ցուցակի առաջին հանգույցին, ապա ցիկլով այն տեղաշարժվում է դեպի ցուցակի վերջը։ Ցիկլն ավարտվում է, երբ կա՛մ ժամանակավոր ցուցիչը հասել է ցուցակի վերջին, կա՛մ ցույց է տալիս մի հանգույցի, որի data դաշտը պարունակում է որոնվող արժեքը։

  def Search(self, val):
    temp = self.head
    while temp != None and temp.data != val:
      temp = temp.link
    return temp

Ցուցակում տարրեր կարելի է ավելացնոլ ոչ միայն սկզբից կամ վերջից, այլ նաև որևէ հանգույցից առաջ կամ հետո։ InsertAfter մեթոդը ստանում է մի արժեք և ցուցակի մի որևէ հանգույց, ապա տրված արժեքով մի նոր հանգույց է ավելացնում ցուցակի տրված հանգույցից հետո։

  def InsertAfter(self, val, node):
    nd = Node(val)
    nd.link = node.link
    node.link = nd

Իսկ InsertBefore մեթոդը տրված արժեքով նոր հանգույց է ավելացնում ցուցակի տրվախ հանգույցից առաջ։

  def InsertBefore(self, val, node):
    self.InsertAfter(val, node)
    node.link.data, node.data = node.data, node.link.data

Համապատասխանաբար RemoveAfter և RemoveBefore մեթոդները հեռացնում են ցուցակի տրվաց հանգույցին հաջորդող ու նախորդող հանգույցները՝ վերադարձնելով հեռացված հանգույցի պարունակությունը։

  def RemoveAfter(self, node):
    if node.link == None:
      return None
    t = node.link
    node.link = t.link
    t.link = None
    return t.data

  def RemoveBefore(self, node):
    if self.head == node:
      return None
    temp = self.head
    while temp.link != node:
      temp = temp.link
    val = temp.data
    temp.data = node.data
    self.RemoveAfter(temp)
    return val

Եվ վերջապես, մի հետաքրքիր գործողություն ևս։ Reverse մեթոդը շրջում է կապակցված ցուցակը։ Ահա այդ պարզ ալգորիթմը։

  def Reverse(self):
    a = self.head
    b = None
    while a != None:
      c = a.link
      a.link = b
      b = a
      a = c
    self.head = b

Python: Բառարանի օգտագործումը

Այս գրառման մեջ ես առաջարկում եմ ևս մի լուծում իմ նախորդ գրառման մեջ առաջարկված և Tcl լեզվով լուծված խնդրի համար։ Նորից հիշեցնեմ խնդրի ձևակերպումը.

Տրված է որևէ գեղարվեստական ստեղծագործության տեքստ։ Կազմել տեքստում հանդիպող բառերի հաճախության բառարան, որտեղ ամեն մի բառին համապատասխանեցված է տեքստում նրա հանդիպելու քանակը։ Հաշվել տեքստի առանձին բառերի քանակի հարաբերությունը բոլոր բառերի քանակին։ Արտածել տաս ամենաշատ օգտագործված բառերի խմբերը։ Արտածել տաս ամենաերկար բառերը և նրանց հանդիպելու քանակը։ Արտածել միայն մեկ անգամ հանդիպող բառերի ցուցակը։

Այս անգամ նույն խնդրի լուծումը տալիս եմ Python ծրագրավորման լեզվով։


Եվ այսպես, տեքստից մեզ չհետաքրքրող (բառ չձևավորող) սիմվոլները հեռացնելու համար օգտագործելու ենք կանոնավոր արտահայտությունների re մոդուլը։

import re

Դատարկ բառարանը ստեղծվում է dict դասի կոնստրուկտորի կանչով։

words = dict()

Տեքստը տող առ տող ֆայլից կարդալու և բառերի տրոհելու համար with հրամանով ստեղծենք կատարման կոնտեքստ, որում fin փոփոխականին կապված է open հրամանով կարդալու համար բացված տեքստային ֆայլը (Ջեկ Լոնդոն, "Մարտին Իդեն"): Կատարման կոնտեքստում for հրամանով իտերացիա կազմակերպենք ֆայլի տողերով։ re մոդուլի sub մեթոդը տրված տողում փոխարինում է տրված կանոնավոր արտահայտությամբ ճանաչված հատվածները մեկ այլ տրված տեքստով։ Փոխարինումից հետո տողի բոլոոր մեծատառերը lower մեթոդով դարձնենք փոքրատառեր ու split մեթոդով տողը կտրտենք բառերի։ if հրամանով ստուգենք որ բառի երկարությունը մեծ լինի մեկից։ Հաջորդ if հրամանով և not in գործողությամբ ստուգենք ընթացիկ բառի առկայությունը բառարանում. եթե այն բացակայում է, ապա ավելացնում ենք՝ հաշվիչի 0 սկզբնական արժեքով։ Հաջորդ քայլում պարզապես հերթական բառի հաշվիչն ավելացնում ենք մեկով։

with open('martin-eden-jack-london.txt') as fin:
  for line in fin:
    line = re.sub('[^a-zA-Z]+', ' ', line)
    for wr in line.lower().split(' '):
      if len(wr) > 1:
        if wr not in words:
          words[wr] = 0
        words[wr] += 1

len ֆունկցիան վերադարձնում է dict օբյեկտի գրառումների քանակը։ մեր դեպքում դա տեքտի իրարից տարբեր բառերի քանակն է։ sum ֆունկցիան վերադարձնում է ցուցակի տարրերի գումարը։ Այստեղ ցուցակը words բառարանի արժեքների ցուցակն է, որի տարրերի գումարը ստացվում է տեքստի բոլոր բառերի քանակը։ format մեթոդը կատարում է տողի ֆորմատավորում, այն նաև տեղադրում է տրված արժեքները տողի նշված տեղերում։

uniwords = len(words)
allwords = sum(words.values())
print('{0} / {1} = {2}'.format(uniwords, allwords, 1.0 * uniwords / allwords))

sorted ներդրված ֆունկցիան վերադարձնում է արգումենտում տրված ցուցակի ըստ աճման կարգավորված տարբերակը։ Եթե reverse անվանված արգումենտը տրված է True, ապա վերադարձնում է ըստ արժեքների նվազման կարգավորված ցուցակը։ dict օբյեկտի values մեթոդը վերադարձնում է բառարանի արժեքների ցուցակը։ Մյուս, items մեթոդը հնարավորություն է տալիս իտերացիա կազմակերպել բառարանի բանալի-արժեք զույգերով։ in գործողությունը ստուգում է տարրի պատկանելիությունը ցուցակին։

tenbignums = sorted(words.values(), reverse=True)[0:10]
for word, count in words.items():
  if count in tenbignums:
    print('{0} : {1}'.format(word, count))

sorted ֆունկցիան key անվանված արգումենտով ստանում է այն բնութագիրը, ըստ որի պետք է համեմատվեն ցուցակի տարրերը։ Այստեղ որպես բնութագիր տրված է մի անանուն ֆունկցիա՝ ստեղծված lambda արտահայտության օգնությամբ, որը վերադարձնում է արգումենտի չափը։ Այս կերպ կարողանում ենք բառարանի բանալիների ցուցակը, որը ստացվում է keys մեթոդով, կարգավորել ըստ տարրերի երկարության։

tenbigwords = sorted(words.keys(), key=lambda w: len(w), reverse=True)[0:10]
for wd in tenbigwords:
  print('{0} : {1}'.format(wd, words[wd]))

Եվ վերջապես, տեքստում միայն մեկ անգամ օգտագործված գրված է մի հետաքրքիր արտահայտություն։ Այն կարելի է կարդալ մոտավորապես այսպես. "անցնել բառարանի տարրերով և ցուցակ կազմել այն բանալիներից, որոնց համապատասխանեցված արժեքը հավասար է մեկի"։

onlyone = [wd for wd, cnt in words.items() if cnt == 1]
print(onlyone)

* * *

Որպես գաղտնիք նշեմ, որ, չնայած խնդրի լուծումը համապատասխանում է պահանջին, բայց, այնուամենայինիվ, պարունակում է որոշ թերություններ։