Succinct data structure
கணினி அறிவியலில், ஒரு சுருக்கமான தரவு அமைப்பு என்பது ஒரு தரவு கட்டமைப்பாகும், இது தகவல்-கோட்பாட்டு கீழ் வரம்பிற்கு "நெருக்கமாக" இருக்கும் இடத்தைப் பயன்படுத்துகிறது, ஆனால் (மற்ற சுருக்கப்பட்ட பிரதிநிதித்துவங்களைப் போலல்லாமல்) இன்னும் திறமையான வினவல் செயல்பாடுகளை அனுமதிக்கிறது. பிட் திசையன்கள், (பெயரிடப்படாத) மரங்கள் மற்றும் பிளானர் வரைபடங்களை குறியாக்கம் செய்ய இந்த கருத்து முதலில் ஜேகப்சனால் அறிமுகப்படுத்தப்பட்டது. பொதுவான இழப்பற்ற தரவு சுருக்க வழிமுறைகளைப் போலல்லாமல், சுருக்கமான தரவு கட்டமைப்புகள் அவற்றை முதலில் சிதைக்காமல், அவற்றைப் பயன்படுத்தும் திறனைத் தக்க வைத்துக் கொள்கின்றன. ஒரு தொடர்புடைய கருத்து என்னவென்றால், ஒரு சுருக்கப்பட்ட தரவு அமைப்பு, சேமிக்கப்பட்ட அல்லது குறியிடப்பட்ட தரவின் அளவு இதேபோல் தரவின் குறிப்பிட்ட உள்ளடக்கத்தைப் பொறுத்தது. சில தரவுகளைச் சேமிக்கத் தேவையான தகவல்-கோட்பாட்டு உகந்த பிட்களின் எண்ணிக்கை இது என்று வைத்துக்கொள்வோம். இந்த தரவின் பிரதிநிதித்துவம் அழைக்கப்படுகிறதுஃ இது பிட் அளவு இடத்தை எடுத்துக் கொண்டால் மறைமுகமாகவும், பிட் அளவு இடத்தை எடுத்துக் கொண்டால் சுருக்கமாகவும், பிட் அளவு இடத்தை எடுத்துக் கொண்டால் கச்சிதமாகவும் இருக்கும். எடுத்துக்காட்டாக, சேமிப்பகத்தின் பிட்களைப் பயன்படுத்தும் ஒரு தரவு அமைப்பு கச்சிதமானது, பிட்கள் சுருக்கமானவை, பிட்களும் சுருக்கமானவை, பிட்கள் மறைமுகமானவை. மறைமுக கட்டமைப்புகள் பொதுவாக உள்ளீட்டு தரவின் சில வரிசைமாற்றத்தைப் பயன்படுத்தி தகவல்களைச் சேமிக்கும் வகையில் குறைக்கப்படுகின்றன; இதற்கு மிகவும் நன்கு அறியப்பட்ட எடுத்துக்காட்டு குவியல் ஆகும். தரவரிசை/தேர்ந்தெடுக்கப்பட்ட அகராதிகள் என்றும் அழைக்கப்படும் தனித்துவமான குறியீட்டு அகராதிகள், பைனரி மரங்கள்,-ஆரி மரங்கள் மற்றும் பல தொகுப்புகள், அதே போல் பின்னொட்டு மரங்கள் மற்றும் வரிசைகள் உள்ளிட்ட பல சுருக்கமான பிரதிநிதித்துவ நுட்பங்களின் அடிப்படையை உருவாக்குகின்றன. ஒரு பிரபஞ்சத்தின் துணைக்குழுவை சேமித்து வைப்பதே அடிப்படை சிக்கலாகும், இது பொதுவாக ஒரு பிட் வரிசையாக குறிப்பிடப்படுகிறது, அங்கு ஒரு குறியீட்டு அகராதி அகராதிகளில் வழக்கமான முறைகளையும் (வினவல்கள், மற்றும் டைனமிக் வழக்கில் செருகல்கள்/நீக்குதல்கள்) பின்வரும் செயல்பாடுகளையும் ஆதரிக்கிறதுஃ வேறு வார்த்தைகளில் கூறுவதானால், நிலைக்கு சமமான உறுப்புகளின் எண்ணிக்கையை வழங்குகிறது, அதே நேரத்தில்-வது நிகழ்வின் நிலையை வழங்குகிறது. ஒரு எளிய பிரதிநிதித்துவம் உள்ளது, இது சேமிப்பு இடத்தின் பிட்களைப் பயன்படுத்துகிறது (அசல் பிட் வரிசை மற்றும் ஒரு துணை அமைப்பு) மற்றும் தரவரிசையை ஆதரிக்கிறது மற்றும் நிலையான நேரத்தில் தேர்ந்தெடுக்கிறது. இது வரம்பு-குறைந்தபட்ச வினவல்களுக்கு ஒத்த ஒரு யோசனையைப் பயன்படுத்துகிறது; ஒரு வரையறுக்கப்பட்ட அளவிலான துணைப் பிரச்சினையில் நிறுத்துவதற்கு முன்பு நிலையான எண்ணிக்கையிலான மறுநிகழ்வுகள் உள்ளன. பிட் வரிசை அளவு பிட்களின் பெரிய தொகுதிகளாகவும், அளவு பிட்களின் சிறிய தொகுதிகளாகவும் பிரிக்கப்பட்டுள்ளது. ஒவ்வொரு பெரிய தொகுதிக்கும், அதன் முதல் பிட்டின் தரவரிசை ஒரு தனி அட்டவணையில் சேமிக்கப்படுகிறது; அத்தகைய ஒவ்வொரு உள்ளீடும் மொத்த சேமிப்பு பிட்களுக்கு பிட்களை எடுக்கும். ஒரு பெரிய தொகுதிக்குள், மற்றொரு அடைவு அதில் உள்ள ஒவ்வொரு சிறிய தொகுதிகளின் தரவரிசையையும் சேமிக்கிறது. இங்குள்ள வித்தியாசம் என்னவென்றால், ஒவ்வொரு உள்ளீட்டிற்கும் பிட்கள் மட்டுமே தேவை, ஏனெனில் பெரிய தொகுதியைக் கொண்ட முதல் பிட்டின் தரவரிசையிலிருந்து வேறுபாடுகள் மட்டுமே சேமிக்கப்பட வேண்டும். எனவே, இந்த அட்டவணை மொத்தம் பிட்களை எடுக்கும். ஒரு தேடல் அட்டவணையைப் பயன்படுத்தலாம், இது சாத்தியமான ஒவ்வொரு தரவரிசை வினவலுக்கும் பதிலை ஒரு பிட் நீள சரத்தில் சேமிக்கிறது; இதற்கு சேமிப்பக இடத்தின் பிட்கள் தேவை. எனவே, இந்த துணை அட்டவணைகள் ஒவ்வொன்றும் இடத்தை எடுத்துக்கொள்வதால், இந்த தரவு அமைப்பு நேரம் மற்றும் இடத்தின் பிட்களில் தரவரிசை வினவல்களை ஆதரிக்கிறது. நிலையான நேரத்தில் ஒரு வினவலுக்கு பதிலளிக்க, ஒரு நிலையான நேர வழிமுறை கணக்கிடுகிறதுஃ நடைமுறையில், தேடல் அட்டவணையை பிட்வைஸ் செயல்பாடுகள் மற்றும் சிறிய அட்டவணைகளால் மாற்றலாம், அவை சிறிய தொகுதிகளில் அமைக்கப்பட்ட பிட்களின் எண்ணிக்கையைக் கண்டறிய பயன்படுத்தப்படலாம். இது பெரும்பாலும் நன்மை பயக்கும், ஏனெனில் சுருக்கமான தரவு கட்டமைப்புகள் பெரிய தரவுத் தொகுப்புகளில் அவற்றின் பயன்பாடுகளைக் காண்கின்றன, இந்த விஷயத்தில் தற்காலிக சேமிப்பு தவறுகள் மிகவும் அடிக்கடி நிகழ்கின்றன மற்றும் நெருக்கமான CPU தற்காலிக சேமிப்புகளிலிருந்து தேடல் அட்டவணை வெளியேற்றப்படுவதற்கான வாய்ப்புகள் அதிகமாகின்றன. தரவரிசைக்கு பயன்படுத்தப்படும் அதே துணை கட்டமைப்பில் பைனரி தேடலைச் செய்வதன் மூலம் தேர்ந்தெடுக்கப்பட்ட வினவல்களை எளிதில் ஆதரிக்க முடியும்; இருப்பினும், இது மோசமான விஷயத்தில் நேரம் எடுக்கும். கூடுதல் சேமிப்பகத்தின் பிட்களைப் பயன்படுத்தி மிகவும் சிக்கலான அமைப்பு நிலையான நேரத்தில் தேர்ந்தெடுக்கப்படுவதை ஆதரிக்க பயன்படுத்தப்படலாம். நடைமுறையில், இந்த தீர்வுகளில் பல குறியீட்டில் மறைக்கப்பட்ட மாறிலிகளைக் கொண்டுள்ளன, அவை எந்தவொரு அறிகுறியற்ற நன்மையும் வெளிப்படுவதற்கு முன்பு ஆதிக்கம் செலுத்துகின்றன; பரந்த சொல் செயல்பாடுகள் மற்றும் சொல்-சீரமைக்கப்பட்ட தொகுதிகளைப் பயன்படுத்தி செயல்படுத்துவது பெரும்பாலும் நடைமுறையில் சிறப்பாக செயல்படுகிறது. என்ட்ரோபி-சுருக்கப்பட்ட தீர்வுகள் தனித்துவமான துணைக்குழுக்கள் (அல்லது சரியாக 1 இன் நீளத்துடன் பைனரி சரங்கள்) உள்ளன என்பதைக் குறிப்பிடுவதன் மூலம் விண்வெளி அணுகுமுறையை மேம்படுத்தலாம், இதனால் சேமிப்பதற்குத் தேவையான பிட்களின் எண்ணிக்கையில் ஒரு தகவல் கோட்பாட்டு கீழ் வரம்பாகும். ஒரு சுருக்கமான (நிலையான) அகராதி உள்ளது, இது இந்த வரம்பை அடைகிறது, அதாவது இடத்தை பயன்படுத்துகிறது. இந்த கட்டமைப்பை தரவரிசையை ஆதரிக்கவும், கேள்விகளைத் தேர்ந்தெடுக்கவும் நீட்டிக்க முடியும் மற்றும் இடம் எடுக்கும். இருப்பினும், இந்த கட்டமைப்பில் சரியான தரவரிசை வினவல்கள் தொகுப்பில் உள்ள கூறுகளுக்கு மட்டுப்படுத்தப்பட்டுள்ளன, இது குறைந்தபட்ச சரியான ஹாஷிங் செயல்பாடுகள் எவ்வாறு செயல்படுகின்றன என்பதற்கு ஒத்ததாகும். அகராதியின் சேமிப்பு இடத்தை நேரம் எடுக்கும் வினவல்களுக்குக் குறைப்பதன் மூலம் இந்த வரம்பை ஒரு இடம்/நேர பரிமாற்றமாகக் குறைக்கலாம். தரவரிசையை ஆதரிக்கும் ஒரு குறியீட்டு அகராதியை உருவாக்கவும் முடியும் (ஆனால் தேர்ந்தெடுக்கப்படவில்லை) இது பிட்களை விட குறைவாக பயன்படுத்துகிறது. அத்தகைய அகராதி மோனோடோன் குறைந்தபட்ச சரியான ஹாஷ் செயல்பாடு என்று அழைக்கப்படுகிறது, மேலும் சில பிட்களைப் பயன்படுத்தி செயல்படுத்தலாம். ஒரு சுருக்கமான ஹாஷ் அட்டவணை, சுருக்கமான வரிசைப்படுத்தப்படாத அகராதி என்றும் அழைக்கப்படுகிறது, இது ஒரு தரவு கட்டமைப்பாகும், இது ஒரு பிரபஞ்சத்திலிருந்து விசைகளை விண்வெளி பிட்களைப் பயன்படுத்தி சேமித்து வைக்கிறது, மேலும் நிரந்தரமாக எதிர்பார்க்கப்படும் நேரத்தில் உறுப்பினர் வினவல்களை ஆதரிக்கிறது. ஒரு சுருக்கமான ஹாஷ் அட்டவணை நிலையான எதிர்பார்க்கப்பட்ட நேரத்தில் செருகல்கள் மற்றும் நீக்குதல்களை ஆதரிக்கிறது என்றால், அது டைனமிக் என்று குறிப்பிடப்படுகிறது, இல்லையெனில் அது நிலையான என்று குறிப்பிடப்படுகிறது. முதல் மாறும் சுருக்கமான ஹாஷ் அட்டவணை 2003 இல் ராமன் மற்றும் ராவ் காரணமாக இருந்தது. இந்த விஷயத்தில், அவற்றின் தீர்வு இடைவெளி பிட்களைப் பயன்படுத்துகிறது. அதைத் தொடர்ந்து, இந்த இடைவெளி வரம்பை எந்த நிலையான எண்ணிக்கையிலான மடக்கைக்கும் பிட்களாக மேம்படுத்த முடியும் என்று காட்டப்பட்டது. பிந்தைய தீர்வு அனைத்து செயல்பாடுகளையும் மோசமான நிலையில் நிலையான நேரத்தில் அதிக நிகழ்தகவுடன் ஆதரிக்கிறது. முதல் நிலையான சுருக்கமான ஹாஷ் அட்டவணை 1999 இல் பாக் காரணமாக இருந்தது. இந்த விஷயத்தில், அவற்றின் தீர்வு இடைவெளி பிட்களைப் பயன்படுத்துகிறது, மேலும் மோசமான நிலையான நேரக் கேள்விகளை ஆதரிக்கிறது. இந்த எல்லை பின்னர் பிட்களாகவும், பின்னர் பிட்களாகவும் மேம்படுத்தப்பட்டது. முதல் இரண்டு தீர்வுகள் மோசமான-வழக்கு நிலையான-நேர வினவல்களை ஆதரிக்கின்றன, இறுதி ஒன்று நிலையான எதிர்பார்க்கப்பட்ட-நேர வினவல்களை ஆதரிக்கிறது. இறுதி தீர்வுக்கு அளவின் தேடல் அட்டவணைக்கான அணுகலும் தேவைப்படுகிறது, ஆனால் இந்த தேடல் அட்டவணை சேமிக்கப்படும் கூறுகளின் தொகுப்பிலிருந்து சுயாதீனமாக உள்ளது. பிற எடுத்துக்காட்டுகள் தன்னிச்சையான நீளம் (பாஸ்கல் சரம்) கொண்ட ஒரு சரம் Z + பதிவு (Z) இடத்தை எடுத்துக்கொள்கிறது, இதனால் சுருக்கமாக உள்ளது. அதிகபட்ச நீளம் இருந்தால்-இது நடைமுறையில் உள்ளது, ஏனெனில் 232 = 4 ஜிபி தரவு மிக நீண்ட சரம், மற்றும் 264 = 16 ஐபி தரவு நடைமுறையில் உள்ள எந்த சரத்தையும் விட பெரியது-பின்னர் ஒரு நீளம் கொண்ட சரம் Z + k இடத்தை எடுத்துக்கொள்கிறது, இதில் k என்பது அதிகபட்ச நீளத்தைக் குறிக்கும் தரவுகளின் எண்ணிக்கை (எ. கா., 64 பிட்கள்). மாறி நீள உருப்படிகளின் வரிசையை (சரங்கள் போன்றவை) குறியிட வேண்டியிருக்கும் போது, பல்வேறு சாத்தியக்கூறுகள் உள்ளன. ஒரு நேரடி அணுகுமுறை ஒவ்வொரு பதிவிலும் ஒரு நீளத்தையும் ஒரு பொருளையும் சேமிப்பதாகும்-இவை பின்னர் ஒன்றன் பின் ஒன்றாக வைக்கப்படலாம். இது திறமையான அடுத்ததை அனுமதிக்கிறது, ஆனால் kth உருப்படியைக் கண்டுபிடிக்கவில்லை. ஒரு மாற்று என்னவென்றால், உருப்படிகளை ஒரு வரையறையுடன் (எ. கா., பூஜ்ய-முடிவடைந்த சரம்) வரிசையில் வைப்பதாகும். இது நீளத்திற்கு பதிலாக ஒரு எல்லை வரையறையைப் பயன்படுத்துகிறது, மேலும் இது கணிசமாக மெதுவாக உள்ளது, ஏனெனில் முழு வரிசையும் எல்லை வரையறைகளுக்கு ஸ்கேன் செய்யப்பட வேண்டும். இவை இரண்டும் விண்வெளி திறனுள்ளவை. ஒரு மாற்று அணுகுமுறை அவுட்-ஆஃப்-பேண்ட் பிரிப்பு ஆகும்ஃ பொருட்களை வெறுமனே ஒன்றன் பின் ஒன்றாக வைக்கலாம், எந்த வரம்புகளும் இல்லாமல். பொருள் வரம்புகள் பின்னர் நீளத்தின் வரிசையாக சேமிக்கப்படலாம், அல்லது இந்த வரிசையில் சிறந்த ஆஃப்செட்டுகளாக சேமிக்கப்படலாம். மாற்றாக, ஒரு பொருள் தொடங்கும் இடங்களில் 1s ஐக் கொண்ட ஒரு தனி பைனரி சரம், மற்ற எல்லா இடங்களிலும் 0s அதனுடன் குறியிடப்படுகிறது. இந்த சரத்தைப் பொறுத்தவரை, ஒவ்வொரு உருப்படியும் அதன் குறியீட்டைக் கருத்தில் கொண்டு எங்கு தொடங்குகிறது என்பதை செயல்பாடு விரைவாக தீர்மானிக்க முடியும். இது சுருக்கமானது, ஆனால் சுருக்கமாக இல்லை, ஏனெனில் இது 2Z இடத்தை எடுக்கும், இது O (Z) ஆகும். மற்றொரு எடுத்துக்காட்டு ஒரு பைனரி மரத்தின் பிரதிநிதித்துவமாகும்ஃ முனைகளில் ஒரு தன்னிச்சையான பைனரி மரத்தை பிட்களில் குறிப்பிடலாம், அதே நேரத்தில் எந்த முனையிலும் பல்வேறு செயல்பாடுகளை ஆதரிக்கலாம், இதில் அதன் பெற்றோர், அதன் இடது மற்றும் வலது குழந்தையைக் கண்டறிதல் மற்றும் அதன் துணை மரத்தின் அளவை திரும்பப் பெறுதல் ஆகியவை அடங்கும், ஒவ்வொன்றும் நிலையான நேரத்தில். முனைகளில் உள்ள வெவ்வேறு பைனரி மரங்களின் எண்ணிக்கை. பெரிய அளவில், இது சுமார்; எனவே அதை குறியாக்கம் செய்ய குறைந்தபட்சம் பிட்கள் தேவை. எனவே ஒரு சுருக்கமான பைனரி மரம் ஒரு முனைக்கு பிட்களை மட்டுமே ஆக்கிரமிக்கிறது. மேலும் காண்க மினிமல் பெர்பெக்ட் ஹாஷ் ஃபங்ஷன் சுசிங்க்ட் நோன்-இன்டராக்டிவ் ஆர்குமென்ட்ஸ் ஆஃப் நாலெட்ஜ் ரெஃபரன்ஸ்