பொதுவான நீண்ட துணைத்தொடர் புதிர்

பொதுவான நீண்ட துணைத்தொடர் புதிர் (Longest Common subsequence problem) என்பது பல எழுத்துத்தொடர்களிடையே (strings) காணப்படும் நீண்ட துணைத்தொடரைக் (subsequence) கண்டுபிடிப்பதாகும். இப்புதிர் பொதுவாக இரண்டு தொடர்களிடையே அமைந்த துணைத்தொடரைக் கண்டுபிடிப்பதாகவே அமையும். கணினியியலில் தொடர் என்பது எழுத்துகள், எண்கள் மற்றும் குறியீடுகளாலான (special characters) ஒரு சொற்றொடரைக் குறிக்கும். ஒரு தொடரின் துணைத்தொடர் என்பது, அத்தொடரிலுள்ள எழுத்தகளால் (அதே வரிசையில் ஆனால் தொடர்ச்சியாக இல்லாமல்) அமைந்த ஒரு தொடராகும். உதாரணத்திற்கு "வணக்கம்" என்பது தொடரானால், "வம்", "வணம்", "கம்", "வகம்" என்பவை துணைத்தொடர்களாகும். இவ்வாறு கொடுக்கப்படும் தொடர்களுள், அனைத்துத் தொடர்களிலும் பொதுவாக அமைந்துள்ள மிக நீளமான துணைத்தொடரைக் கண்டுபிடிப்பதே பொதுவான நீண்ட துணைத்தொடர் புதிராகும். உ.தா.: "பந்தாட்டம்" மற்றும் "பல வட்டம்" ஆகிய தொடர்களின் மிக நீண்ட துணைத்தொடர் "பட்டம்" ஆகும். இப்புதிரின் அடிப்படை, கோப்புகளை ஒப்பிடும் செயலியான டிஃப் (diff) போன்றவற்றில் பயன்படுத்தப்படுகிறது. உயிரித்தகவலியல் வரை இதன் பயன்பாடு நீள்கிறது.

இரு தொடர் புதிரின் தீர்வு

இப்புதிரை மேலும் பல சிறு எளிதான புதிர்களாகப் பிரிக்க இயலும். அச்சிறு புதிர்களை மென்மேலும் பல சிறு புதிர்களாகப் பிரிக்கலாம், இவ்வாறு அச்சிறு புதிர்களின் விடை கிடைக்கும் வரை அவற்றைப் பிரித்துக்கொண்டே செல்ல வேண்டும். ஒரு புதிரை இவ்வாறு சிறு புதிர்களாகப் பிரிக்கயியன்றால் உகம உள்ளமைப்பு (optimal substructure) கொண்ட புதிர் எனப்படும். இப்புதிரினைப் பல சார் புதிர்களாகப் பிரிக்கலாம். சார் புதிர் (overlapping subproblems) என்பது ஒரு புதிரின் விடை அதன் பிரிவுகளின் விடையைச் சார்ந்திருப்பதாகும். ஒரு புதிரில் உகம உள்ளமைப்பு மற்றும் சார் புதிர்களாகப் பிரிக்கும் தன்மையிருந்தால், எளிதான சிறு புதிர்களுக்குத் தீர்வு காண்பது மூலம் அப்புதிருக்குத் தீர்வு காண முடியும். இவ்வாறு தீர்வு காணும் முறையை ஆங்கிலத்தில் Dynamic Programming என்பர்.

முன்னொட்டுகள்

பொதுவான நீண்ட துணைத்தொடர் புதிரில் தொடர்களின் நீளத்தைக் குறைப்பதன் மூலம் எளிமையான சிறு புதிர்களை உருவாக்க இயலும். இவ்வாறு நீளம் குறைக்கப்பட்டத் தொடர்களை முன்னொட்டு (prefix) என்னும் பெயரின் மூலம் குறிக்கலாம். ஒரு தொடரின் முன்னொட்டென்பது, அத்தொடரின் முடிவில் வரும் எழுத்துகளைக் களைவதன் மூலம் கிடைப்பதாகும். உதாரணத்திற்கு "௨" என்னும் எழுத்து "ஆட்டம்" என்ற தொடரைக் குறிக்கிறதென்றால், "ஆட்ட" என்னும் தொடர் "௨" தொடரின் முன்னொட்டுகளில் ஒன்றாகும். முன்னொட்டுகள் தன் தாய் தொடரின் பெயரிலேயே குறிக்கப்பெறுகின்றன. முன்னொட்டுகளை வேறுபடுத்திக்காட்ட அவற்றில் கீழ்க்குறியீடாக அதன் நீளம் குறிக்கப்பெறும். உதாரணத்திற்கு "ஆட்ட" எனும் முன்னொட்டு "௨₃" என்ற பெயரால் குறிக்கப்படும்.