ஆமவடை

ஏற்கணவே பதிவு செய்த  இடத்தில் இருந்து தொடருவோம்:

ஆமவடை

படம் 1: ஆமவடை

Corollary 2 of  Theorem 3: ஒரே சொல்லில் எழுத்து இரடிக்கப்பட்டால் அந்த சொல் டோரசில் ஒரு சுழலுடன் [loop] கொண்டபடி அமையும்.

Lemma 2:  படுக்கவசமாகவும், நிமிர்ந்துவசமாகவும் அமைகப்பட்ட சொர்கள் மொழியில் இல்லாதவை.

Corollary 3 or Theorem 3: டோரசில் படுக்கவசமாகவும், நிமிர்ந்துவசமாகவும் பாதைகள்/எழுத்துக்கள் இல்லாதவை.

Theorem 4: ஒரு அகராதியில் உள்ள சொர்கள் அனைத்தையும் டோரசில் பிரதிபலித்தால் அந்த குறுக்கிடும் இடங்களின் [intersecting points] ஒன்று அல்லது மெர்பட்ட சொற்களை] எண்ணிக்கை அளவை மிக குறைவாக்கும் வண்ணம் அமைக்க முடியாது. அதாவது ஒரு அகராதியின் சொற்கள் அனைத்து எவ்வித அமைப்பில் உள்ள டோரசானாலும் சரி அதன் குறுக்கிடும் இடங்களின் எண்ணிக்கை மாராது. இது ஒரு மாறிலி [invariant].

Corollary 1 of Theorem 4: மேர்கண்ட டோரசில் [அதன் ஒரு பிரதிபலிப்பில் – ‘அ,ஆ,இ,ஈ, … ,ஒ,ஓ,ஔ‘ என்றும் ‘கசடதபரயரலவழள – ….’  என்றும் வரிசையிலோ, அல்லது வேறு பரிமாணங்களில்  அடுக்கியிருந்தால்] ஒவ்வொரு அகராதிக்கும் ஒரு சிரப்பான குறுக்கிடும் இடங்களின் எண்ணிக்கை கிடைக்கும். இந்த எண் அகராதியின் கையொப்பம் [signature] என்றும் சொல்லாம்.

Theorem 5: டோரசில் உள்ள ஓவ்வொரு அகராதி சொல்லும் ஒரு பாதை என்று கொள்ளலாம். சொல்லின் தொடக்க எழுத்து  பாதையின் தொடக்கத்தையும், சொல்லின் கடைசி எழுத்து பாதையின் முடிவையும் குறிக்கும்; பாதை திசைகொண்ட பாதையாக இருக்கும் – ஒரு அம்பு தொடக்கத்தில் இருந்து முடிவின் திசையில் வழி காட்டும். ஆகையால் அகராதியில் இல்லாத பாதைகள் பிழையாக எழுதப்பட்ட  அகராதி சொற்களுக்கு சமம், அல்லது அகராதியில் இல்லாத புதிய சொற்களுக்கு சமம்.

வாதம் [ஆதாரத்தின் தொடக்கமாக கருத்ப்படலாம்]:  டோரசில்ஒவ்வொரு சொல்லும் [அதன் பாதையும்] அகராதியில் உள்ள சொற்களாகவே இருக்கவேண்டும். Coding-theory / error correction codes theory படி இவ்வகை சரியான எழுத்துக்கள் உள்ள பாதைகள், சரியான சொற்களாகவும், தவான சொற்கள் [இல்லாத சொற்கள்] பிழையானவை என்வும் அமையும். இவ்வாரான சொற்கள் சரியானவையையின் சொற்பிழை எனவும் கருதப்பாடும்.

Corollary 1 of Theorem 5: மேர்கண்ட டோரசில் முழு அகராதி பிரதிபலிக்கப்பட்டதால், இதனைக்க்கொண்டு ஒரு சொற்பிழை திருத்தி செய்யலாம். பிழையான் சொல்லின் திருத்தம், அதன் நெருங்கிய தொலைவில் உள்ள சரியான் சொல் என்பதை நடைமுரைவிதியாகக்கொண்டு இதனை அமல்படுத்தலாம்.

Theorem 6: Tries எனப்படும் சொல்மரங்களைக்கொண்ட தரவமைப்பை டோரசில் குறியிட்டால், அது தொடர்பாதையாக ஒரே தொடக்கமும், பல பாதைமுடிவுகளையும் கொண்டதாக அமையும். இவற்றில் சில பாதைகள் சேரும் வகையில் முடிவுபெரும் வகையிலும் அமையலாம்.

படம் 2: Trie மரம் என்ற தரவமைப்பு. இதில் ‘to’, ‘tea’, ‘ted’, ‘ten’, ‘A’, ‘in’, மற்றும் ‘inn’ ஆகிய சொற்கள் இடம் பெற்றுள்ளன.

உதாரணத்திற்கு, படம் 2-இல் முடியும் நிலை நுனிகள் ‘n’ என்பவை டோரசில் வரும்பொழுது சேரும் வகையில் முடிவுபெரும் வகையில் அமையும்.

-முத்து.

Language Transformations

Question  of Translation

How can you convert a text like “Me Amor!” to “என் உயிரே!” [from Spanish to தமிழ்] ? Lets  assume we have Spanish to English and Tamil to English translators [bidirectional with English] then we can convert Spanish to English then to Tamil. Likewise one can translate between any two languages from a clique of languages [so far as the clique is defined such that each language can be translated to at least one other language in clique].

Development – Theory

Language can exist as text (print/message/document) or speech (audio, conversations) etc. Ideas are represented in any language. Ideas originate from one language and move to another, or sometimes originate iñ many lañguages simultaneously. Ideas cañ cross from oñe language to añother via text or speech.

In mathematical terms if we write L as set of lañguages = { L1, L2, .. Ln} and then if we define each language as a tuple Li = (Ti,Si) then we may further define mathematical function operating on text and converting it to speech as :

TTSi : Ti -> Si

we may define a function speech recognition as,

ASRi : Si -> Ti

we may also define a translation function as,

TXij : Li -> Lj

Essentially what we can do is by representing the language as a node in a graph with two text and speech parts to it, we may connect these nodes to each other via the edges – functions – like ASR and TTS, and to nodes of other languages via translators function edge.

In a graph with only two languages [English, Tamil] with all edges representing functions like TTS, ASR within same language and functions like Translator between two languages (one for each direction) we see a graph like the following:

Screen Shot 2018-08-03 at 11.51.08 PM

Fig. 1: Language transformation graph. Nodes represent languages and their components. Edges represent functions like TTS, ASR [for same language] and Translators [directional between languages]. Clearly we may see this is a directed graph with ability to go from a specific language to another language in text or speech or both forms, provided a path exists from source to target language. Using such a graph with no orphan nodes, we may have universal translation powers from language A to language B [so far as bidirectional connectivity is present with at least one neighbor].

Problems to Ponder

So the curious reader now having a background of representing the translation problem as a graph problem of reaching node B from node A, can use rich set of path finding algorithms and shortest distance algorithms may attempt to answer some of these questions:

  1. What is the graph criteria for a language to have no translations ?
  2. What is the graph criteria for a language to not be able to have virtual assistant ? [Siri, Cortana, Alexa etc.]
  3. Conversely, to 2, what is minimum criteria [necessary but not sufficient] to have a virtual assistant [that can speak and listen] ?
  4. Given two paths to translating from language A -> F, which are of two different lengths which one would you choose and why? Assume all jumps have a uniform information loss. What if information loss at each edge is non-uniform, how can you optimized such a problem ?
  5. How would you introduce a new language into this graph so that it maybe translated to all other languages [unidirectionally] ?
  6. How would you introduce a new language into this graph so that it can be bi-directionally translated ?
  7. How can you represent the transliteration function in this graph ?

Answers will be posted soon! Feel free to leave your comments in section below.

-Muthu

காதல் -> தவம் – பாகம் 2

விடை: சொல் ஏணி (word-ladder games ) என்பன காதல்-இல் இருந்து தவம் வரை மாற்ற உதவும் – இதை காண்க.

  1. அதாவது, ஒரு அகராதியை கொண்டு, முனை-ஓரம் படம் அமைக்கவும்.
  2. இரு சொற்கள் ஓரத்தால் இணைக்கப்பட்டால், அவை ஒன்ருடன் ஒன்று ஒரு எழுத்து மாற்றம் வழி தொடர்புடையது என்று அர்த்தம்.

இதை கொண்டு ஏற்கனவே ‘காதல் -> தவம்‘ எழுதினோம்.

மேலும் இந்த ஆய்வுக்கட்டுரை அழகாக உள்ளளது – (கட்டுரை) ‘Word Morph and Topological Structures: A Graph Generating Algorithm’, Jürgen Klüver, Jörn Schmidt, Christina Klüver, (2016), Complexity, Vol. 21, No. S1. Wiley Publications.

 

காதல் -> தவம் ?

எப்படி “காதல்” என்ற சொல்லை, ஓர் எழுத்து மாற்றத்தினால் மட்டுமே, “தவம்” என்று மாற்றுவது ?

காதல்
கானல்
காறல்
கால்
காழ்
சீழ்
சீவ
சீவம்
சைவம்
தவம்

இதனை எப்படி கண்டடைந்தோம் ?. இதனை எப்படி கணினிமயமாக்கலாம் ?

விரைவில்.

அல்கோரிதம் – அடுக்குகளை தலைகீழ் படுத்துவது எப்படி ?

Move 1,2,3 disks from peg #1 to peg #2, with peg #3 as intermediate. Move disk 4 from peg #1 to peg #4. Then move all disks from peg #2 to peg #3 using peg #1 as intermediate.

இந்த வாரம் அமெரிக்காவில் “long weekend” அதாவது மூன்று-நாள் வார விடுமுறை – காரணம் மே மதம் நான்காம் திங்கள் “Memorial day” என்கிற “அமெரிக்க போர்வீரர் நினைவு தினம்”. இதனை ஒட்டி சராசரி குடும்பங்கள் நாடெங்கும் உல்லாச பயணம், சுற்றுலா என்று செல்வது அமெரிக்க பண்பாடு. இந்த ஆண்டு எங்கள் வீட்டில் விருந்தினரை வரவேற்கிறோம் – பயணம் என்பது இந்த ஆண்டு எங்கள் விருந்திரனுக்கு மட்டுமே! சரி அப்போது ஒரு புதிய தரவமைப்பு பற்றி ஒரு blog post போடுவோம் என்று எழுத ஆரம்பித்தது இங்கே.

அடுக்கு (Stack) என்பது ஒரு மிக அடிப்படை கணினி நிரலாக்க கோட்பாடு. ஒரு அடுக்கு தரவமைப்பில் செய்யக்கூடிய நடவடிக்கைகள் ஆனது : மேல் நுழை (push), மேல் நீக்கு (pop) என்பது.

ஒரு அடுக்கை இப்படி (கீழ் கண்டபடி) உருவாக்கலாம்:

எ = அடுக்கு()
மேல்_நுழை( எ, "அ" )
மேல்_நுழை( எ, "ஆ" )

இது கணினியில் ஒரு அடுக்கு போலவே உருவெடுக்கும்,

    
   --> [ ஆ ]
       [ அ ]
      --------
அடுக்கு "எ" என்பதில் இரண்டு உருப்படிகள் உள்ளது; 
இதில் "மேல்" உருப்படி "ஆ" என்ற மதிப்பாகும்.

மேலும் இந்த அடுக்கில் மற்ற உயிரெழுத்துக்களை முழுதாக சேர்க்கலாம்:

மேல்_நுழை( எ, "இ" )
மேல்_நுழை( எ, "ஈ" )
மேல்_நுழை( எ, "உ")
மேல்_நுழை( எ, "ஊ")
மேல்_நுழை( எ, "எ")
மேல்_நுழை( எ, "ஏ")
மேல்_நுழை( எ, "ஐ")
மேல்_நுழை( எ, "ஒ")
மேல்_நுழை( எ, "ஓ")
மேல்_நுழை( எ, "ஔ")

கணினியில் இதன் தோற்றம் இப்படி இருக்கும்,

   --> [ ஔ ]
       [ ஓ ]
       [ ஒ ]
       [ ஐ ]
       [ ஏ ]
       [ எ ]
       [ ஊ ]
       [ உ ]
       [ ஈ ]
       [ இ ]
       [ ஆ ]
       [ அ ]
அடுக்கு "எ" என்பதில் பன்னிரண்டு உருப்படிகள் உள்ளது; 
இதில் "மேல்" உருப்படி "ஔ" என்ற மதிப்பாகும்.

நம்ம இங்கே ஆயுத எழுத்து “ஃ” என்பதை சேர்க்கவில்லை; உங்களுக்கு வேண்டுமானால் நீங்கள் சேர்த்து கொள்ளலாம்.

அடுக்கின் வரிசை மாற்றுவது எப்படி ?

இப்போது அடுக்கு “எ” இதன் வரிசை மாற்றுவது எப்படி ? ஒரு குவிப்பில் இருந்து “மேல் எடு” என்று செய்தால் என்ன விளைவு என்று முதல் படியாக பார்க்கலாம் – இதன் விளைவு மேல் உள்ள உருப்படியை அழிக்கும்.

மேல்_எடு( எ )
# தற்போது குவிப்பு 'எ' வில் 11 உருப்படிகள் மட்டும் இருக்கும்.
# ஏற்கெனவே உள்ள மேல் உருப்படி 'ஓ' அழிக்கப்பட்டது.
# புதிய மேல் உருப்படி 'ஓ' என்று ஆனது.

இப்போது இந்த அடுக்கின் நிலை,

 -->   [ ஓ ]
       [ ஒ ]
       [ ஐ ]
       [ ஏ ]
       [ எ ]
       [ ஊ ]
       [ உ ]
       [ ஈ ]
       [ இ ]
       [ ஆ ]
       [ அ ]
அடுக்கு : எ 

இப்போது அழித்த மேல் உருப்படியை புதிய அடுக்கு ‘ஏ’ வில் மேல் நுழைத்தால் – அதையே ‘எ’ என்ற அடுக்கில் உருப்படிகள் உள்ளவரை அதில் மேல் எடுத்து, ‘ஏ’ வில் மேல் நுழைத்துக்கொண்டே இருந்தால் என்ன ஆகும் ?
இதனை நிரல் படுத்தி பார்க்கலாம்.

ஏ  = அடுக்கு()
மேல்_நுழை( ஏ, "ஔ")
@( நீளம்( எ ) > 0 ) வரை 
    மதிப்பு = மேல்_எடு( எ )
    மேல்_நுழை( ஏ, மதிப்பு )    
முடி

தற்போது அடுக்கு ‘எ’-வின் நிலை காலியானது:

 -->[ ]
அடுக்கு : எ 

ஆனால் அடுக்கு ‘ஏ’-வின் நிலையோ – வரிசை மாற்றப்பட்டது!

-->[ அ ]
   [ ஆ ]
   [ இ ]
   [ ஈ ]
   [ உ ]
   [ ஊ ]
   [ எ ]
   [ ஏ ]
   [ ஐ ]
   [ ஒ ]
   [ ஓ ]
   [ ஔ ]
அடுக்கு : ஏ 

இந்த நிரல் துண்டு Python மொழியில் இப்படி எழுதலாம்,

# (C) 2017 Ezhil Language Foundation
# This code is shared under public domain
# Ref: https://ezhillang.wordpress.com
import tamil
import pprint

class Stack:
    def __init__(self):
        self.store = list()

    def top(self):
        return self.store(-1)

    def __len__(self):
        return self.store.__len__()

    def push(self,val):
        self.store.insert(-1,val)

    def pop(self):
        val = self.store.pop()
        return val

    def display(self):
        pprint.pprint(list(zip(range(self.__len__()-1,0,-1),self.store)))
        
a = Stack()
for letter in tamil.utf8.uyir_letters:
    a.push(letter)
a.display()

rev_a = Stack()

while len(a) > 0:
    val = a.pop()
    rev_a.push(val)

print("Original stack => ")
a.display()
print("Reversed stack => ")
rev_a.display()

இதன் வெளியீடோ கீழே உள்ளபடி:

[(11, 'ஆ'),
 (10, 'இ'),
 (9, 'ஈ'),
 (8, 'உ'),
 (7, 'ஊ'),
 (6, 'எ'),
 (5, 'ஏ'),
 (4, 'ஐ'),
 (3, 'ஒ'),
 (2, 'ஓ'),
 (1, 'ஔ')]
Original stack => 
[]
Reversed stack => 
[(11, 'ஔ'),
 (10, 'ஓ'),
 (9, 'ஒ'),
 (8, 'ஐ'),
 (7, 'ஏ'),
 (6, 'எ'),
 (5, 'ஊ'),
 (4, 'உ'),
 (3, 'ஈ'),
 (2, 'இ'),
 (1, 'ஆ')]

தரவமைப்பு வடிவங்களின் தமிழாக்கம் – கருத்து கணிப்புவிடைகள்

சென்ற வாரம் வெளியிட்ட தரவமைப்பு வடிவங்களின் தமிழாக்கம் – கருத்து கணிப்பு விடைகள் மற்றும் எனக்கு பிடித்த தமிழாக்கம் பரிந்துரைகளையும் இங்கு பதிவு செய்கிறேன்.

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

கருத்து கணிப்பு விடைகள்:

விடைகள்கி ழே; மின் அஞ்சல் மட்டும் சில சுய விவரங்கள் மறைக்க பட்டன. கருத்து கணிப்பில் பங்கேற்ற நிரலாளர்களின் கூடிய சராசரி அனுபவ்வம் 9 ஆண்டுகள்! பட்டியலில் உள்ளது போலவே பல தரவு வடிவங்களுக்கு தமிழாக்கம் பெயர்கள் உடன்பாடு இருந்தது. சிலதில் தவரான பொருள் இடத்து உண்டபாடும் இருந்தது.

பயனர் “stack” என்பது தமிழில் “heap” என்பது தமிழில் “dictionary” or “associative array” என்பது தமிழில் “linked list” என்பது தமிழில் “binary tree” என்பது தமிழில் “graph” என்பது தமிழில் “hash table” என்பது தமிழில் “queue” என்பது தமிழில் “priority queue” என்பது தமிழில் “circular list” என்பது தமிழில்
0 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் இரு கிளை மரம் முனை ஓரம் அடைவு எண்குறி அடைவு முறை வரிசை பிரதான வரிசை வட்ட தொடர் பட்டியல்
1 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் இரு கிளை மரம் வரைபடம் எண்குறி அடைவு முறை வரிசை முக்கிய வரிசை வட்டவடிவப் பட்டியல்
2 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் இரு கிளை மரம் முனை ஓரம் அடைவு கையெழுத்து அடைவு முறை வரிசை முக்கிய வரிசை தொடர் பட்டியல் வட்டம்
3 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் இரும மரம் முனை ஓரம் அடைவு சுறுக்கு குறி அடைவு வரிசை முறை முதன்மை வரிசை வட்ட தொடர் பட்டியல்
4 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் பின்னாக்கு கிளை வரைபடம் ரகசிய அடைவு வரிசை முதர்சன வரிசை வட்ட தொடர் பட்டியல்
5 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் பின்னாக்கு கிளை வரைபடம் ரகசிய அடைவு வரிசை முதர்சன வரிசை வட்ட தொடர் பட்டியல்
6 அடுக்கு குவிப்பு அடைவு தொடர் இருகிளையி எனச்சுருங்கச் சொல்லலாம் முனை ஓரம் என்றோ கோலம் என்றோ சொல்லலாம் எண்குறி அடைவு முறை வரிசை விருப்பவரிசை, முன்னுரிமை வரிசை சுற்றுச்சங்கிலித்தொடர்
7 அடுக்கு குவிப்பு அகராதி தொடர் பட்டியல் இரு கிளை மரம் வரைபடம் எண்குறி அடைவு வரிசை முன்னுரிமை வரிசை வட்டப்பட்டியல்
8 அடுக்கு குவிப்பு தொடர்புறு அணி தொடர் பட்டியல் இரு கிளை மரம் முனை ஓரம் அடைவு எண்குறி அடைவு நேர் வரிசை முக்கிய வரிசை வட்ட தொடர் பட்டியல

பரிந்துரைகள்  – எனக்கு பிடித்த தமிழாக்கம்

எனது பரிந்துரைகளை முன்வைக்கும் முன்னரே எனக்கு உள்ள சில நிபந்தனைகளை சொல்கிறேன்.

நிபந்தனைகள் (criteria)

  1. அறிவியல் தமிழ் அல்லது கணித தமிழில் ஏற்கனவே பயன்பாடு கொண்டதாக இருக்க வேண்டும்; எ. கா. arrays என்றல் அணி என்று ஏற்கனவே உள்ளது
  2. சக்கரத்தை மறுபடி கண்டுபிடிக்க வேண்டாம். உள்ளதை அப்படியே எடுத்து கொள்ளலாம்.
  3. கணிமை சொற்களுடன் எளிதாக எழுதும் வகையில், பேசும் வகையில் இருக்கவேண்டும்
  4. நடைமுறை, இயல்பு தமிழ், மற்றும் கணிமை கோட்பாடுகளை சரியே குணாதிசியங்களை போதிக்கும் திறன் கொண்ட சொற்களாக அமைய வேண்டும்.

பரிந்துரைகள்

  1.  array அணி
  2.  set கணம்
  3. stack அடுக்கு
  4. heap குவிப்பு
  5. dictionary அடைவு, தொடர்புறு அணி
  6. linked list தொடர் பட்டியல், தொடர்
  7. circular list வட்ட தொடர் பட்டியல்
  8. graph நுனி ஓரம் / முனை ஓரம் அடைவு
  9. queue முறை வரிசை, நேர் வரிசை
  10. priority queue முன்னுரிமை வரிசை, முதர்சன வரிசை
  11. hash table எண்குறி அடைவு, சுறுக்கு குறி அடைவு
  12. binary tree  இரும மரம், இரு கிளை மரம்

நிறைய பெயர்கள் எ. க. ‘dictionary’ என்பன நேர்வழி தமிழில் ‘அகராதி’ என்றும் ‘graph’ என்பது ‘வரைபடம்’ என்றும் மொழி பெயர்க்க முடியாது – கணினி தரவமிப்பில் தமிழில் இதை அடைவு அல்லது தொடர்புறு அணி என்று சொன்னால் சரியாக இருக்கும்; ‘graph’ என்பது ‘கோலம்’ அல்லது ‘முனை ஓரம அடைவு’/’நுனி ஓரம் அடைவு’ என்றும் சொன்னால் பொருளளவில் தமிழாக்கம் செய்யப்படும்.

 

தொடர் பட்டியல் (Linked lists)

தொடர் பட்டியல் என்பது ஒரு எளிதான தரவு வடிவம். சுலபமாக பல ஆயிரக்கணக்கான மதிப்புகளை சேமிக்க இந்த தொடர் பட்டியல் பயன்படுத்தலாம்.

தொடர் பட்டியல் அவதாரங்கள்

இந்த தொடர் பட்டியல் இரண்டு வகையாக அமையும்: ஒருபடை தொடர் பட்டியல் (singly linked list) மற்றும் இருபடை(doubly linked list) இவை கீழே படங்களில் காணலாம். இதனையும் தாண்டி வட்டம் தொடர் பட்டியல் (circular linked list) என்றும் செய்யலாம் இதனை கடைசியில் காண்போம்.

408px-singly-linked-list-svg

படம் 1: ஒருபடை தொடர் பட்டியல் (singly linked list). இதன் முதல் தலை நுனி ‘12’ என்ற மதிப்பை கொண்டது. இதன் ‘அடுத்த’ மதிப்பு ‘99’ மதிப்பு கொண்ட நுனியின் விலாசத்தை கொண்டது. மேலும் ‘99’ நுனி ‘37’ என்ற மதிப்பு கொண்ட நுனியின் விலாசம் கொண்டது. ‘37’ நுனி என்பது கடைசி நுனி என்பதால் இதற்க்கு அடுத்து மதிப்பு காலி என கொண்டது. இந்த ‘அடுத்து’ என்ற இணைப்பே ‘12’ நுனியில் தொடங்கி ‘37’ வரை செல்லும் அம்சத்தை தொடர் பட்டியல் என்று ஆகும் படி இந்த தரவு வடிவத்திற்கு அளிக்கிறது.

610px-doubly-linked-list-svg

படம் 2: படம் 1-ஐ போலவே தொடர் பட்டியல் ஆனால் ‘அடுத்து’ மதிப்பை போலவே கூடுதலாக ‘முந்தைய’ என்ற மதிப்பையும் ஒவ்வொரு நுனியும் கொண்டது. இதன் காரணமாக இதனை ‘இருபடை தொடர் பட்டியல்’.

 

தொடர் பட்டியல் அமைப்பு

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

# நுனி உருவாக்குதல்

நிரல்பாகம் ஒருபடை_நுனி( மதிப்பு )

      நு = {“அடுத்து” : [], “மதிப்பு” : மதிப்பு  }

      பின்கொடு நு

முடி

# நுனியின் அடுத்து விலாசத்தை மற்றோரு நுனியில் அமைத்தல் /

நிரல்பாகம் ஒருபடை_இணை( நுனி_முதல், நுனி_அடுத்து  )

      நுனி_முதல் [“அடுத்து”] = நுனி_அடுத்து

      பின்கொடு நுனி_அடுத்து

முடி

தொடர் பட்டியலில் அணுகுதல்

தொடர் பட்டியலின் முதல் நுனியை “தலை நுனி” என்று பெயரிடுவோம். இந்த தலை நுனியை மட்டும் நாம் கொண்டு முழு பட்டியலை ஒவ்வொன்றாக அணுகலாம். எப்படி ? நுனியில் “அடுத்து” என்ற நுனி விலாசம் உள்ளதை வைத்து நுனிக்கு செல்லலாம். இதனையே பலமுறை – அதாவது அடுத்து என்பதன் மதிப்பு காலி ஆகும் வரை – செய்தால் முழு பட்டியலையும் தலை நுனியில் இருந்து கடைசி நுனிவரை ஒவ்வொன்றாக அணுகலாம். இதனை “ஒருபடை_அணுகு()” என்ற நிரல்பாகம் நிரல்படுத்தும்.

தொடர் பட்டியலில் தேடல்

சரி – இப்ப இந்த பட்டியலில் ஒரு குறிப்பிட்ட மதிப்பு உள்ளதா என்று எப்படி தேடுவது ? இந்த செயல்முறையை நம்ம “ஒருபடை தொடர் பட்டியல் தேடல்” என்று பெயரிடுவோம். தேடல் என்பது பட்டியலில் உள்ள ஒவ்வொரு நுனியையும் அணுகி (அணுகுதல் என்ற நிரல்பாகம் கீழே எழுதப்பட்டதைப்போல்) குறிப்பிட்ட மதிப்பிற்கு சமமாக உள்ளதா என்று பார்க்கவேண்டும்.

# ஒருபடை தொடர் பட்டியலை வரிசையில் அணுகுதல்

நிரல்பாகம் ஒருபடை_அணுகு( நுனி  )

   நுனி_அடுத்து = []

   காலி =  []

   @(    நுனி != காலி  ) வரை  

       #பதிப்பி “முதிப்பு  => “,

       பதிப்பி நுனி [“மதிப்பு”]

       நுனி_அடுத்து = நுனி [“அடுத்து”]

       நுனி = நுனி_அடுத்து

   முடி

   பின்கொடு  நுனி_அடுத்து

முடி

தேடிய ‘குறிப்பிட்ட மதிப்பு’ கிடைக்காவிட்டால் -1 என்ற மதிப்பு பின்கொடுக்கப்படும்; கிடைத்தால், தலை நுனியில் இருந்து தூரத்தை  வரிசை எண் என்று பின்கொடுக்கப்படும்

நிரல்பாகம் ஒருபடை_தேடு ( நுனி, குறிப்பிட்ட_மதிப்பு   )

   நுனி_அடுத்து = []

   காலி =  []

   வரிசை_எண்  = 1

   @(    நுனி != காலி  ) வரை

       @( நுனி [“மதிப்பு”] == குறிப்பிட்ட_மதிப்பு ) ஆனால்

           பின்கொடு வரிசை_எண்        

       முடி

        நுனி_அடுத்து = நுனி [“அடுத்து”]

        நுனி = நுனி_அடுத்து

        வரிசை_எண் = வரிசை_எண் + 1

   முடி

   பின்கொடு  -1

முடி

 

# நுனி உருவாக்குதல்

நு12 = ஒருபடை_நுனி( 12 )

நு99 = ஒருபடை_நுனி( 99 )

நு37 = ஒருபடை_நுனி( 37 )

 

# நுனியின் அடுத்து விலாசத்தை மற்றோரு நுனியில் அமைத்தல் /

ஒருபடை_இணை( நு12, நு99 )

ஒருபடை_இணை( நு99, நு37 )

 

# ஒருபடை தொடர் பட்டியலை வரிசையில் அணுகுதல்

ஒருபடை_அணுகு( நு12 )

#சாவே இல்லாத வீட்டிலே கைப்பிடி கடுகு  கிடைக்குமா ?

பதிப்பி ஒருபடை_தேடு(நு12, 10) 

பதிப்பி ஒருபடை_தேடு(நு12, 37)

இதன் வெளியீடு :  12, 99, 37. முழு நிரல் இங்கு.

இந்த மாதிரி தொடர் பட்டியலில் பல கேள்விகளை எழுப்பலாம், உதாரணத்திற்கு:

  1. இரண்டு தொடர்பட்டியலை எப்படி இணைப்பது ?
  2. ஒரு தொடர்பட்டியலில் குறிப்பிட்ட மதிப்பு எத்தனை முரை அவதானிக்கிறது ?
  3. தொடர்பட்டியலை முன்னுக்கு பின் எப்படி வேகமாக மாற்றுவது ?
  4. இரு தொடர் பட்டியலில் உள்ள பொதுவான மதிப்புகளை கண்டு எடுக்க முடியுமா ?
  5. அணிகள் (arrays) என்பதற்கும் தொடர் பட்டியல் என்பதற்கும் என்ன வித்யாசம் ?

இதனை போல கேள்விகளை பயிற்சிக்கு கேட்டு கொண்டே போகலாம். அனால் நீங்கள் இந்த இரண்டு புத்தகங்களை நேரம் கிடைக்கும் சமயம் கட்டாயம் படித்தால் எல்லாம் விளங்கும்.

  1. “Introduction to algorithms” by Cormen, Leiserson, Rivest, and Stein. MIT press இங்கு.
  2. “The Algorithm Design Manual” by Steven Skiena. இங்கு

இதை இரண்டையுமே நீங்கள் கரைத்து குடித்துவிட்டால் உங்களுக்கு நிரலாக்க திரையில் கிராக்கி அமோகமாக விளங்கும். அப்படி கார்பொரேட் கைதியாக இருக்கவேண்டாம் என்று வீரப்பாக இருந்தால் இந்த புத்தகத்தில் உள்ள லட்டு, ஜிலேபி இனிப்புகளை இன்பமாக அனுபவியுங்கள்.

மேலும் அடுத்த வாரம்.

-முத்து

கவனத்திற்கு: தொடர் பட்டியல் படங்கள் விக்கிபீடியா, புத்தக அட்டைகள் பதிப்பகத்திற்கு சொந்தம்; எழுத்து பிழைகள் எல்லாமே என்னோடது.