தரவமைப்புகள் – கருத்து கணிப்பு

வணக்கம்,

சில ஆண்டுகளாக தமிழில் data structures என்ற தரவமைப்புகளை முறையாக அணுகவேண்டும் என்று யோசித்து வருகிறேன். இதன் காரணமாக நம் சமூகத்தில் ஒரு கருத்து கணிப்பை உருவாக்கி இருக்கிறேன்.  இதில் அனைவரும் பங்கேற்குமாறு  கேட்டு கொள்கிறேன்.
சுட்டி இங்கு https://goo.gl/forms/ijmbWjFk5lV2L2m92
நன்றி,
முத்து

இரு கிளை மரம் தரவு உருவம் – (binary tree data structure)

கணிமையில் நமது மாறிலி (variables) மற்றும் தரவு மதிப்புகளை (data values) வரிசை படுத்தியோ அல்லது சீரற்ற வழியில் ஒரே மாதிரி அடுக்கி தரும் தரவு உருவம்  வகையில் (data structure) ஒன்று ‘இரு கிளை மரம்’ (binary tree)- இதனை இரட்டித்த மரம் என்றும் சுருக்கி சொல்லலாம்.

மரம் – நிஜமாவா ?

எண் ‘2’-ஐ  வேர் என்றும், ‘5’, ’11’, ‘4’, ‘2’ என்ற எண்கள் இலைகள் ஆகவும் இந்த இரட்டித்த மரம் அமைந்திருக்கு.

இது இயற்கையில் உள்ள இயற்கை மரம் போலவே காட்சி அளிக்குமோ என்று சந்தேக பட்டால், அது சரியானது! மரம் என்பதற்கு எப்படி,

  1. வேர் (root)
  2. கிளை (branch)
  3. இலைகள் (leaves)

உள்ளதோ அதே போன்று இந்த இரட்டித்த மரம் தரவு வகையில் இதற்கு இணையான (isomorphic) அம்சங்கள் இருக்கு. இந்த பதிவில் இதை பார்க்கலாம்.

இரட்டித்த மரம் நடுவோம் – கட்டுமானம்

மேல் கண்ட படத்தில் உள்ள மரத்தை எப்படி உருவாக்குவது ? இது சுலபம்.

மரத்தின் எல்லா மதிப்புகளையும்  நுனிகள் (nodes) என்று பெயரிடுவோம். இரட்டித்த மதத்தின் குணம் என்ன என்றால், நுனிகளில் இரண்டு கிளைகள் இருக்கும் – வலது (right) நுனி, இடது (left) நுனி, மற்றும் நுனியின் மதிப்பு (value).

முதலில் வேர் நுனி என எண் ‘2’ நியமிக்கவும். இந்த வேர் நுனியிர்க்கு இரண்டு வலது கிளை நுனி (right node) என எண் ‘5’-ம், இடது கிளை நுனி (left node) என எண் ‘7’-ம் அமைக்கவும்.

அடுத்து,  நுனி 7 என்பதில் வலது நுனி 6, இடது நுனி 2 எனவும் இணைக்கவும். நுனி 5-இல் வலது நுனி 9, மற்றும் 9-இன் இடது நுனி 4 எனவும் அமைக்கவும்.

கடைசியாக நுனி 6-இன் வலது புரம் 11 எனவும் இடது புரம் 5-உம் அமைக்கவும்.

இதனை போல் தொடர்ச்சியாக செய்தால் நமக்கு கணினி நினைவில் ஒரு ‘இரட்டித்த மரம்’ என்ற தரவு  உருவத்தை நீங்கள் செய்யலாம்.

விளக்க நிரல் எடுத்துகாட்டுகள் 

இந்த பதிவில் உள்ள நிரல்களை Github-இல் இருந்து இயக்கி பாருங்கள்.

பைதான் மொழியில், இதனை கீழ்கண்டவாறு செய்யலாம்:

root = make_tree(2)
node5 = make_tree(5)
node7 = make_tree(7)
set_right(root,node5)
set_left(root,node7)

node9 = make_tree(9)
node4 = make_tree(4)
set_right(node5,node9)
set_left(node9,node4)

node2 = make_tree(2)
node6 = make_tree(6)
set_right(node7,node6)
set_left(node7,node2)

node11 = make_tree(11)
node5 = make_tree(5)
set_right(node6,node11)
set_left(node6,node5)

எழில் மொழியில், இதனை கீழ்கண்டவாறு செய்யலாம்:

நிரல்பாகம் மரம்_செய்( அளவு )
# left, right,value
ம = {“இடது_நுனி”: [],”வலது_நுனி”: [], “மதிப்பு”:அளவு}
பின்கொடு ம
முடி

நிரல்பாகம் வலது_நுனி_செய்( வேர்நுனி, நுனி )
வேர்நுனி[“வலது_நுனி”] = நுனி
முடி

நிரல்பாகம் இடது_நுனி_செய்( வேர்நுனி, நுனி )
வேர்நுனி[“இடது_நுனி”] = நுனி
முடி

# இரட்டித்த மரம் நடுவோம் – கட்டுமானம்
வேர் = மரம்_செய்(2)
நுனி5 = மரம்_செய்(5)
நுனி7 = மரம்_செய்(7)
வலது_நுனி_செய்(வேர்,நுனி5)
இடது_நுனி_செய்(வேர்,நுனி7)

நுனி9 = மரம்_செய்(9)
நுனி4 = மரம்_செய்(4)
வலது_நுனி_செய்(நுனி5,நுனி9)
இடது_நுனி_செய்(நுனி9,நுனி4)

நுனி2 = மரம்_செய்(2)
நுனி6 = மரம்_செய்(6)
வலது_நுனி_செய்(நுனி7,நுனி6)
இடது_நுனி_செய்(நுனி7,நுனி2)

நுனி11 = மரம்_செய்(11)
நுனி5 = மரம்_செய்(5)
வலது_நுனி_செய்(நுனி6,நுனி11)
இடது_நுனி_செய்(நுனி6,நுனி5)

# மரம் நுனிகளை அனைத்தயும் வரிசையில் எடுப்பது
ம_வரிசை = பட்டியல்()
வரிசையில்_எடு( வேர், ம_வரிசை )
பதிப்பி ம_வரிசை

மரம் நுனிகளை அனைத்தயும் வரிசையில் எடுப்பது :

கேள்வி : “வேர் நுனி மட்டும் கிடைத்தால் மரம் நுனிகளை அனைத்தயும் வரிசையில் எப்படி எடுப்பது ? ”

இது ஒரு சராசரியான செயல்பாடு; எப்போது இரட்டித்த மரம் என்றாலும் உடனடியாக அந்த இடத்தில் “அனைத்து நுனிகளை எடுக்க” என்ற செயல் புரியும் தேவை உங்கள் கணிமை programming-இல் வந்து விடும்.

சரி இதன் கேள்விக்கு விடை ஒரு induction வழியாக பார்க்கலாம்;

  1. நிலை : மரத்தில் வேர் மற்றும் உள்ளது – (மொத்தம் 1 நுனி)
    • வேர்[“மதிப்பு”] மட்டும் அணுகினால் போதும்.
    • நமது மரம் படத்தில், 2
  2. நிலை : மரத்தில் 2 அல்லது 3 நுனிகள் மட்டும் உள்ளன.
    • வேர்[“இடது_நுனி”][“மதிப்பு”],   வேர்[“மதிப்பு”], வேர்[“வலது_நுனி”][“மதிப்பு”] என்ற வரிசையில் நுனிகளை சிந்திப்போம்
    • நமது மரத்தில், 7, 2, 5 என்றும் காண்போம்
  3. நிலை : மரத்தில் 4,5,6,7 அல்லது 8 நுனிகள்
    1. இரண்டாம் படியில் வேர் என்ற மாறிலிக்கு பதில் வேர்[“இடது_நுனி”], வேர்[“வலது_நுனி”] என்றும் கூடுதலாக தொடக்கத்தில் மாற்றத்தை செய்து செயல் பட்டால் இது முடிந்து விடும்

ஆகவே நமது செயல்முறை வழி (algorithm) என்பது இதன்போல் காட்சி அளிக்கும்:

வரிசையில் அணுகு ( உள்ளீடு : மரம் வேர்_நுனி )

படி 1: மரத்தின் இடது பக்கத்தை வரிசையில் அணுகு, எடு

படி 2: தன்னிலை வேர்_நுனி மதிப்பை எடு

படி 3: மரத்தின் வலது பக்கத்தை வரிசையில் அணுகு, எடு

இதுவே recursion சார்ந்த செயல்முறை வழி. இதனை ‘inorder traversal’ (நேர் வரிசையில் அணுகுதல் என்றும் சொல்லலாம். இது எப்படி செயல்படுகிறது என்பதை ஒரு காகிதத்தில் நீங்களே எழுதி பார்த்தால் இன்னமும் எளிமையாக இருக்கும்.   காணொளிகளை மற்ற மென்பொருள் பறிச்சியாளர்கள் youtube-இல்பார்க்கவும் பதிவித்தார்கள்.

எழில் மொழியில் இந்த நேர் வரிசை அணுகல் என்பதை நிரல்க்கி பார்த்தால்,

# walk in in-order; ப – பட்டியல் என்ற மாறிலி (ப- variable is a list)
நிரல்பாகம் வரிசையில்_எடு(வேர்,ப)
@( வேர்[“இடது_நுனி”] != [] ) ஆனால்
வரிசையில்_எடு( வேர்[“இடது_நுனி”] , ப)
முடி

பதிப்பி “%d,”, வேர்[“மதிப்பு”]
பின்இணை( ப, வேர்[“மதிப்பு”] )

@( வேர்[“வலது_நுனி”] != [] ) ஆனால்
வரிசையில்_எடு( வேர்[“வலது_நுனி”] , ப)
முடி

பின்கொடு ப
முடி

பைதான் மொழியில் இதனை, inorder traversal என்றும் எழுதலாம்

# walk in in-order
def walk_inorder(root,listval):
if root.left:
walk_inorder(root.left,listval)
#print(“%d, “%root.value)
listval.append(root.value)
if root.right:
walk_inorder(root.right,listval)
return

இதே அணுகுமுறையை, வலது, இடது மாற்றியும் செய்தால் அதற்கு மற்ற விளைவுகள் உண்டு; இதனால் மரத்தின் நுனிகளை அணுக மூன்று முறைகள் சொல்லுவார்கள்,

  1. நேர் வரிசை அணுகல் – inorder traversal
    • அணுகும் வரிசை: இடது, வேர், வலது
  2. தன் முன் வரிசை அணுகல் – pre-order traversal
    • அணுகும் வரிசை: வேர்இடது, வலது
  3. தன் பின் வரிசை அணுகல்  – post-order traversal
    • அணுகும் வரிசை: இடது, வலது, வேர்

அடுத்த அத்தியாயத்தில் இந்த மூன்று அணுகு முறை இவற்றிகும் என்ன சிறப்பு அம்சங்கள் உண்டு என்றும், வேறு இரட்டித்த மரம் செயல்பாடுகளை பார்க்கலாம்.

2016 ஆண்டு நடப்பு அறிக்கை

உங்களுக்கு 2017 தை பொங்கல், மற்றும் புத்தாண்டு வாழ்த்துக்கள். இந்த கட்டுரையில் சென்ற ஆண்டில் நாங்கள் செய்த தமிழ் மென்பொருள் மேம்பாடுகள், வெளியீடுகள் பற்றி எழுதியுள்ளேன். தமிழ் கணிமை, மென்பொருள் போன்றது மெதுவாக வளர்ந்தாலும், இலக்கை நினைவுகொள்ளும் வகையில், என்றும் “eyes on the prize” போல, படிமேல் படி வைத்து செல்லுவோமாக.

We released important software updates in 2016 and entered the phase of Android application development fully. Our particular software releases and contributions from last year are documented here. As always I cannot be more thankful to everyone that collaborated, reviewed and most importantly contributed code in the pursuit of open-source Tamil computing.

  1. Ezhil Language code was maintained and updated several times last year. Our releases were,

  1. Open-Tamil project had several success too; we published our latest updates and developments in the Tamil Internet Conference at Dindugul, TamilNadu in 2016. Particularly the Open-Tamil was extended to work in Java as well laying foundation for easily developing Android apps.

    • v0.65 on Oct 22nd, 2016

    • v0.6 on Jan 10th, 2016

  1. We released the Kalsee app, a simple talkback Tamil calculator on Google Play Store; this app was also open-sourced at github where the concatenative synthesis technology maybe re-shared

  1. Karunakaran, graduating senior (final-year) from CS Engineering program, at S.K.P. Engineering college Thiruvannamalai, contributed an Android App for learning Ezhil language and using the website. We supported his work with a small scholarship.

  1. We conceived and created the MinMadurai project to bring published public domain works of Project Madurai to Android phones in an offline format. This project is under development with a alpha version software at Play Store.

அன்புடன், முத்து.

பொறியாளர் கவனத்தை பெரும் “சொல்லாழி”

சமீபத்தில் சொல்வனம் இதழில் “சொல்லாழி,” நாஞ்சில் நாடன் http://solvanam.com/?p=47917 அவர்களது வெளியானது. இந்த கட்டுரை பல அரிய தகவல்களை சுவையாக அளிக்கிறது. மேலும் கணினி மொழியியல் (computational linguistics) மற்றும் தரவு மொழியியல் (corpus linguistics) நோக்கில் படித்தால் மிகவும் சுவாரஸ்யாக இருக்கும்.

நாடன் அவர்கள் புள்ளியியல் துரையில் முதுகலை (Masters in Statistics) பட்டம் பயிற்சி பெற்றவர் என்பதையும் நினைவில் கொள்ள வேண்டும். இவரது தமிழ் விழிப்புணர்ச்சி பணி மிகவும் சிறந்தது, பொறியாளர் ஆன நமது கவனத்தை பெரும் ஒரு கட்டுரை.

-முத்து