Wednesday, February 26, 2014

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

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

Thursday, February 20, 2014

Common Lisp: Առաջին հայերեն գիրքը

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

Ահա գրքի առաջին երկու գլուխները. https://github.com/armenbadal/clne

Sunday, February 9, 2014

Հայերեն TeX: «Քաջարի զինվոր Շվեյկի արկածները»

Ես արդեն ավելի հաճախ եմ հանդիպում այն հարցին, թե ինչպես plain TEX կամ LATEX համակարգերում գրել հայերեն տեքստեր։ Շնորհիվ Unicode նիշերի համակարգով աշպխատող XeTeX իրականացման, այդ երկու համակարգերում էլ հայերեն տեքստերի պատրաստումն արվում է շատ պարզ ու սովորական եղանակով։

Այս գրառման մեջ ես մի ամբողջական գիրք ձևավորելու օրինակով ցուց կտամ հայերեն տեքստ պատրաստելու ամբողջ ընթացքը։ Եվ այդ նպատակի համար օգտագործելու եմ վերջերս իմ թվայնացրած վեպերից մեկի՝ Յարոսլավ Հաշեկի «Քաջարի զինվոր Շվեյկի արկածները» գրքի տեքստը (ամբողջական տեքստը Լիտոպեդիա բանասիրության հանրագիրարանում)։ Ես այստեղ մանրամասնորեն չեմ ներկայացնի բոլոր մակրոսների վարքը, պարզապես մի քանի բառով ցույց կտամ դրանցից ամեն մեկի նպատակը։

OCR-ից հետո մաքրագիր տեքստը պահպանել եմ markdown ֆորմատով, որպեսզի հետագայում հնարավոր լինի այն թարգմանել այլ ֆորմատների։ Մասնավորապես՝ mediawiki ֆորմատը ստանալու համար օգտագործել եմ pandoc թարգմանիչը։ Բայց pandoc-ի ներդրված ֆորմատներում կա միայն LATEX-ի թարգմանիչ, և plain TEX-ի թարգմանելու համար ես գրեցի մի շատ պարզ սկրիպտ, որը տրված markdown տեքստից ստանում է իմ նախապատրաստած TEX մակրոսները պարունակող ֆորմատավորում։

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

Տպատառերի տեսակներն ու չափերը.
  1. Հիմնական տեքստը տպագրված է «Գրքի սովորական» տառատեսակով։ Էջատակի նշումները և չափածո տեքստերը՝ նույն տառատեսակի ավելի մանր տարբերակով։ Տեքստում կան նաև հազվադեպ հանդիպող շղագիր հատվածներ։
  2. Մասերի ու գլուխների վերնագրերը տպագրված են Snas Serif (Գրոտեսկ) ինչ-որ տառատեսակով։

Էջերի տեսակները.
  1. Գրքի մասերը սկսող էջեր։ Դրանք չորսն են և տեղավորված են կենտ համարների վրա, այսինքն՝ բացված գրքի աջ էջին։ Այս տիպի էջերի հակառակ երեսը դատարկ է։
  2. Գրքի գլուխները սկսող էջեր։ Սրանք տպագիր գրքում սկսվում են նկարով, բայց քանի որ ես որոշել եմ գիրքը ձևավորել առանց նկարների, այս տիպի էջերի վերևի մասը դատարկ կթողնեմ։ (Միգուցե հետագայում կհավաքեմ նաև նկարներով տարբերակը։) Գլխի վերնագրը թավ տառերով է. առաջին տողում համարն է, երկրորդ տողում՝ գլխատառերով գրված վերնագիրը։ Համարն ու վերնագիրը հավասարեցված են դեպի ձախ։
  3. Սովորական տեքստի էջեր։ Գրքի տպագիր տարբերակում այս էջերը պարունակում են սովորական տեքստ, էջատակի նշումներ և էջի համարը՝ ներքևից կենտրոնում։ Որոշ էջերի վերին մասում կա նկար։ Էջատակի նշումները ամեն էջում սկսվում են 1-ից։ Տեքստում կան նաև աստղանիշով նշված ծագոթագրություններ, որոնց տեքստը բերված է գրքի վերջում՝ հղվելով աստղանիշը պարունակող էջին։ Տեքստում հանդիպում են նաև չափածո հատվածներ՝ էջի կենտրոնում ձախ հավասարեցումով։
* * *
Հիմա անցնեմ բուն նյութին։ Եվ այսպես, գրքի տեքստը կառուցելու համար օգտագործելու եմ Mariam և Grapalat տառատեսակները՝ հիմնական տեքստի 12pt չափով։ Ստորև բերված կոդում TEX լեզվի \font հրամանով սահմանված են գրքի մեջ օգտագործվող բոլոր տառատեսակները։ Այդ սահմանումներն օգտագործվելու են հաջորդիվ սահմանվող մակրոսներում։
% 10pt չափը էջատակի նշումների համար է
\font\armsmall="GHEAMariam:mapping=tex-text" at 10pt
% 10pt serif տառերը էջախորագրերի (колонтитул) համար են
\font\armsfsmall="GHEAGrapalat" at 10pt
% 11pt չափը չափածո տեքստերի համար է
\font\armpoem="GHEAMariam:mapping=tex-text" at 11pt
% 12pt հիմնական տեքստի տառերի չափն է
\font\armtext="GHEAMariam:mapping=tex-text" at 12pt
% 12pt հիմնական տեքստի շղագիր տառերը
\font\armtextit="GHEAMariam/I" at 12pt
% 12pt հիմնական տեքստի թավ տառերը
\font\armtextbf="GHEAMariam/B" at 12pt
% 24pt չափը գրքի մասերի վերնագրերի համար է
\font\armpart="GHEAMariam/B" at 24pt
% 14pt չափը գրքի գլուխների վերնագրերի համար է
\font\armchap="GHEAMariam/B" at 14pt
Հաջորդ քայլում \armtext տառատեսակները դարձնում եմ հիմնական.
\armtext
Ճիշտն ասած, միայն այսքանը բավական է հայերեն փաստաթուղթ պատրաստելու համար, բայց հետաքրքիրն առջևում է։

Ընդունված է տողերի միջև հեռավորությունը վերցնել հիմնական տառատեսակի չափից 20 տոկոսով ավել։ \baselineskip-ը որոշում է հենց այդ չափը.
\baselineskip=16pt
Քանի որ TEX համակարգում չկա հայերեն տեքստերի համար նախատեսված տողադարձի կանոններ, \tolerance պարամետրը որոշում է տողադարձը կատարելու «համբերության» չափը։ Այս պարամետրին տալով ավելի մեծ արժեք, համակարգին խնդրում ենք ավելի «ներողամիտ» լինել տեղադարձերի նկատմամբ և, հնարավորության դեպքում, բացատների ընդլայնման օգնությամբ կատարել հավասարեցում (ինչպես անում են շատ տեքստային խմբագրիչներ)։
\tolerance=4000
Անգլերեն տեքստերում ընդունված է վերջակետից («.» նիշից) հետո թողնել սովորականից ավելի մեծ բացատ։ Բայց հայերենում վերջակետը «.» նիշը միջակետն է և նրանից հետո երկար բացատ դնել պետք չէ։ \frenchspacing հրամանն անջատում է կետից հետո երկար բացատը։
\frenchspacing
Շղագրի և թավ տեքստի համար plain TEX համակարգի \it և \bf մակրոսներին տալիս եմ նոր իմաստ, որպեսզի դրանք օգտագործեն իմ սահմանած տառատեսակները։
\let\it=\armtextit
\let\bf=\armtextbf
Էջատակի նշումները գրելու համար plain TEX-ն ունի \footnote մակրոսը, որը ստանում է երկու արգումենտ՝ ինդեքսը և տեքստը։ Բայց ես որոշել եմ էջատակի նշումների ինդեքսները դարձնել ավտոմատ՝ ամեն մի գլխի համար սկսելով 1-ից, իսկ տեքստի համար սահմանել եմ 10pt չափի \armsmall տառատեսակը։ \def մակրոսով սահմանել եմ \note մակրոսը, որն իր մարմնում օգտագործում է \footnote-ն։
\newcount\notecount \notecount=0
\def\note#1{\global\advance\notecount by1%
  \footnote{${}^{\the\notecount}$}{{\armsmall #1}}}
\newcount մակրոսը սահմանում է նոր հաշվիչ՝ ամբողջ թիվ, որի արժեքը կարելի է փոխել \advance մակրոսով, իսկ արժեքը կարելի է փաստաթղթում արտածել \the մակրոսով։

Ծանոթագրությունների հետ աշխատելը մի քիչ ավելի բարդ է։ Պետք է ստեղծել մի ֆայլ, որի մեջ TEX կգրանցի տեքստում հանդիպող ծանոթագրությունները, և գրքի վերջից արդեն կարող ենք կցել այդ ֆայլի պարունակությունը։ Գրելու համար ֆայլ կարելի է ստեղծել \newwrite մակրոսով և ֆայլը բացել՝ \openout մակրոսով։
\newwrite\rem \openout\rem=\jobname.rem
\def\remark#1#2{${}^*$%
  \immediate\write\rem{\string\remitem{\the\pageno}{#1}{#2}\par}}
\def\remitem#1#2#3{Էջ~#1.~{\it #2} --- #3\par}
Սահմանված \remark մակրոսն իր կիրառման տեղում գրում է «*» նիշը, իսկ տեքստը, ընթացիկ էջի համարի հետ միասին, գրում է ֆայլում։ \jobname մակրոսը վերադարձնում է այն ֆայլի անունը, որը տրվել է TEX-ի կոմպիլյատորին։ Օրինակ, եթե կատարելու համար հավաքել եմ «xetex svejk.tex» հրամանը, ապա \jobname մակրոսը կվերադարձնի svejk անունը։ Յուրաքանչյուր մեկնաբանություն ֆորմատավորվում է \remitem մակրոսով, որը տպում է հղվող էջի համար, շղագրով տպում է ծանոթագրվող տերմինը և հետո՝ ծանոթագրությունը։

Ծանոթագրությունների նմանությամբ մի ֆայլ էլ պետք է պահել գրքի բովանդակության ցանկի համար, և մի մակրոս էլ՝ բովանդակության ամեն մի տողը ֆորմատավորելու համար։
\newwrite\toc \openout\toc=\jobname.toc
\def\tocitem#1#2{\line{#1\dotfill#2}}
Ինչպես նշեցի վերևում, գրքի մեջ լինելու են երեք տիպի էջեր. ա) մասերը սկսող էջեր, բ) գլուխները սկսող էջեր և գ) հիմնական տեքստը պարունակող էջեր։ Ահա սահմանել եմ \part մակրոսը, որի կիրառումը հերթական կենտ համարով էջի կենտրոնից քիչ վերև տպում է գրքի մասի վերնագիրը և դատարկ է թողնում հաջորդող զույգ համարով էջը։ Այս մակրոսը նաև վերասահմանում է \partname մակրոսը՝ նրան վերագրելով մասի վերնագիրը, որպեսզի հետ դա օգտագործվի էջախորագրերի համար։ Եվ, իհարկե, այս մակրոսը գրքի բովանդակության ֆայլում ավելացնում է վերնագիրն ու ընթացիկ էջի համարը։
\def\partname{}
\def\part #1:#2\par{%
  \begingroup\headline={}\footline={}\vfill\eject% դատարկել էջախորագրերը
  \ifodd\pageno\else\null\vfill\eject\fi% եթե ընթացիկ էջը զույգ է, թողնել դատարկ էջ
  \global\def\partname{#1։ #2}% պահել վերնագիրը էջախորագրերի համար
  \immediate\write\toc{\string\tocitem{#1։ #2}{\the\pageno}}% գրել բովանդակության տողը
  \null\vskip.4\vsize% էջի վերևում թողնել նրա 40%-ի չափով ազատ տեղ
  \centerline{{\armpart #1}}\vskip25pt\centerline{{\armpart #2}}% արտածել վերնագիրը
  \vfill\eject\null\vfill\eject% թողնել դատարկ էջ
  \endgroup}
Գրքի գլուխները սկսելու համար սահմանել եմ \chapter մակրոսը։ Բայց, քանի որ գլուխները սկսող էջերը տարբերվելու են տեքստի մյուս էջերից, նախ սահմանել եմ \ifchapterpage պայմանը։ \chapter մակրոսը զրոյացնում է էջատակի նշումների հաշվիչը, սկսում է նոր էջ, \chaptername մակրոսը սահմանում է որպես ընթացիկ գլխի վերնագիր, բովանդակության ֆայլում գրում է գլխի վերնագիրն ու էջի համարը, էջի վերևից բաց է թողնում 30 տոկոսը, տողի կենտրոնում արտածում է գլիխի համարը, իսկ մյուս տողում՝ վերնագիրը։
\newif\ifchapterpage \chapterpagefalse
\def\chaptername{}
\def\chapter #1. #2\par{\global\notecount=0%
  \vfill\eject\chapterpagetrue%
  \global\def\chaptername{\uppercase{#1. #2}}%
  \immediate\write\toc{\string\tocitem{\qquad#1. #2}{\the\pageno}}%
  \null\vskip.3\vsize\centerline{{\armchap #1}}\vskip14pt%
  \halign{\centerline{{\armchap ##}}\cr #2\cr}%
  \vskip25pt}
Գրքի որոշ գլուխներ բաժանված են հռոմեական թվերով համարակալված ենթագլուխների։ Դրանք նշելու համար սահմանել եմ \subchapter մակրոսը։
\def\subchapter#1{\vskip16pt\centerline{{\armchap #1}}\vskip16pt}
Հայերեն հրատարակության որոշ գլուղներում տեքստի տրամաբանական տրոհում է արված մի փոքր ավելի մեծ դատարկ տարածությամբ քան պարբերությունների միջև եղած տարածքն է։ Ես որոշեցի դրա փոխարեն օգտագործել երեք աստղանիշերից բաղկացած բաժանիչ նշանը։
\def\tristar{\vskip8pt\centerline{\armchap * \raise1ex\hbox{*} *}\vskip6pt}
Չափածո տեքստի համար սահմանել եմ \poem մակրոսը։
\long\def\poem#1{\begingroup\leftskip=.1\hsize\armpoem\let\\=\par
  \obeylines #1\par\endgroup}
Եվ վերջապես, էջախորագրերը։ Տեքստի զույգ համարներով էջերի վերջում արտածվում է ընթացիկ մասի վերնագիրը, իսկ կենտ համարներով էջերի վերևում՝ ընթացիկ գլխի վերնագիրը։ \headline-ն սահմանելիս \ifchapterpage պայմանի օգնությամբ գլուխները սկսող էջերի վրա էջախորագիր չեմ արտածում։
\headline{\ifchapterpage\global\chapterpagefalse\null%
    \else\centerline{{\armsfsmall\ifodd\pageno\chaptername\else\partname\fi}}\fi}
\footline{\hfil\folio\hfil}
Այսքանը՝ գրքի ձևավորման համար նախապատրաստած մակրոսների մասին։
* * *
Ամբողջական գիրքը ստանալու համար մնում է markdown ֆորմատից ստանալ TEX ֆորմատով տեքստերը, ապա ստեղծել, օրինակ, svejk.tex անունով մի ֆայլ, որի սկզբում սահմանված են վերը ներկայացված մակրոսները։

Այնուհետև՝ գրքի տիտղոսաթերթի ֆորմատավորման կոդն է․
\begingroup
\headline={}\footline={}
\null
\centerline{{\armchap Յարոսլավ Հաշեկ}}

\vskip.3\vsize
\centerline{{\armpart ՔԱՋԱՐԻ ԶԻՆՎՈՐ}}
\vskip14pt
\centerline{{\armpart ՇՎԵՅԿԻ ԱՐԿԱԾՆԵՐԸ}}
\vskip14pt
\centerline{{\armpart համաշխարհային}}
\vskip14pt
\centerline{{\armpart պատերազմի ժամանակ}}

\vskip2cm
\centerline{({\armtext թարգմ. Սուրեն Վահունի})}

\vfill
\centerline{{\armtext Երևան -- 1973, 2014}}
\eject\null\vfill\eject\null
\endgroup
Հաջորդում են \input հրամանով գրքի գլուխների բեռնման հրահանգները․
\input svejk-preface.tex

\part ՄԱՍՆ ԱՌԱՋԻՆ: ԹԻԿՈՒՆՔՈՒՄ

\input svejk-1-01.tex

\input svejk-1-02.tex

\input svejk-1-03.tex

\input svejk-1-04.tex

% ... և հաջորդները
Վերջում արտածվում են գրքի ֆորմատավորման ժամանակ կառուցված ծանոթագրություններն ու բովանդակության ցանկը․
\vfill\eject

\def\partname{}\def\chaptername{}
\armpoem

\immediate\closeout\rem
\vfill\eject
\centerline{{\armchap Ծանոթագրություններ}}
\vskip30pt
\input \jobname.rem


\immediate\closeout\toc
\vfill\eject
\centerline{{\armchap Բովանդակություն}}
\vskip30pt
\input \jobname.toc
Եվ վերջ։ Հիմնական գործն արված է։ Մնում է միայն անցնել տեքստի վրայով և շտկել առանձին թերությունները (տողադարձեր, պարբերություններ և այլն)։

Բոլոր ֆայլերը․ https://github.com/armenbadal/armlit/tree/master/jaroslav-hašek