Succinct data structure
કોમ્પ્યુટર વિજ્ઞાનમાં, સંક્ષિપ્ત માહિતી માળખું એ માહિતી માળખું છે જે માહિતી-સૈદ્ધાંતિક નીચલા બાઉન્ડની "નજીક" જગ્યાનો ઉપયોગ કરે છે, પરંતુ (અન્ય સંકુચિત રજૂઆતોથી વિપરીત) હજુ પણ કાર્યક્ષમ ક્વેરી કામગીરી માટે પરવાનગી આપે છે. આ ખ્યાલ મૂળરૂપે જેકબસન દ્વારા બીટ વેક્ટર, (લેબલ વગરના) વૃક્ષો અને પ્લાનર ગ્રાફને એન્કોડ કરવા માટે રજૂ કરવામાં આવ્યો હતો. સામાન્ય લોસલેસ ડેટા કમ્પ્રેશન અલ્ગોરિધમ્સથી વિપરીત, સંક્ષિપ્ત ડેટા સ્ટ્રક્ચર્સ તેમને પહેલા ડીકમ્પ્રેસ કર્યા વિના, તેમને સ્થાને ઉપયોગ કરવાની ક્ષમતા જાળવી રાખે છે. એક સંબંધિત ધારણા એ છે કે કોમ્પ્રેસ્ડ ડેટા સ્ટ્રક્ચર, જ્યાં સુધી સંગ્રહિત અથવા એન્કોડેડ ડેટાનું કદ તે જ રીતે ડેટાની ચોક્કસ સામગ્રી પર આધાર રાખે છે. ધારો કે તે કેટલાક ડેટાને સંગ્રહિત કરવા માટે જરૂરી બિટ્સની માહિતી-સૈદ્ધાંતિક શ્રેષ્ઠ સંખ્યા છે. આ માહિતીની રજૂઆતને કહેવામાં આવે છેઃ જો તે થોડી જગ્યા લે તો ગર્ભિત, જો તે થોડી જગ્યા લે તો સંક્ષિપ્ત અને જો તે થોડી જગ્યા લે તો સઘન. ઉદાહરણ તરીકે, ડેટા સ્ટ્રક્ચર કે જે સંગ્રહના બિટ્સનો ઉપયોગ કરે છે તે કોમ્પેક્ટ છે, બિટ્સ સંક્ષિપ્ત છે, બિટ્સ પણ સંક્ષિપ્ત છે, અને બિટ્સ ગર્ભિત છે. આ રીતે ગર્ભિત માળખાઓને સામાન્ય રીતે ઇનપુટ ડેટાના કેટલાક ક્રમચયનો ઉપયોગ કરીને માહિતી સંગ્રહિત કરવા માટે ઘટાડવામાં આવે છે; આનું સૌથી જાણીતું ઉદાહરણ ઢગલા છે. વિશિષ્ટ અનુક્રમિત કરી શકાય તેવા શબ્દકોશો વિશિષ્ટ અનુક્રમિત કરી શકાય તેવા શબ્દકોશો, જેને ક્રમ/પસંદ કરેલ શબ્દકોશો પણ કહેવાય છે, તે દ્વિસંગી વૃક્ષો,-એરી વૃક્ષો અને મલ્ટીસેટ્સ, તેમજ પ્રત્યય વૃક્ષો અને એરે સહિત સંખ્યાબંધ સંક્ષિપ્ત રજૂઆત તકનીકોનો આધાર બનાવે છે. મૂળભૂત સમસ્યા બ્રહ્માંડના સબસેટને સંગ્રહિત કરવાની છે, જેને સામાન્ય રીતે બીટ એરે તરીકે રજૂ કરવામાં આવે છે જ્યાં એક અનુક્રમિત શબ્દકોશ શબ્દકોશો પરની સામાન્ય પદ્ધતિઓ (ક્વેરીઝ, અને ડાયનેમિક કેસમાં નિવેશ/કાઢી નાખવા) તેમજ નીચેની કામગીરીઓને ટેકો આપે છેઃ માટે. બીજા શબ્દોમાં કહીએ તો, સ્થિતિ સુધી સમાન તત્વોની સંખ્યા પરત કરે છે જ્યારે-th ની ઘટનાની સ્થિતિ પરત કરે છે. એક સરળ રજૂઆત છે જે સંગ્રહ જગ્યાના બિટ્સ (મૂળ બીટ એરે અને સહાયક માળખું) નો ઉપયોગ કરે છે અને ક્રમને ટેકો આપે છે અને સતત સમયમાં પસંદ કરે છે. તે શ્રેણી-લઘુત્તમ પ્રશ્નો માટે સમાન વિચારનો ઉપયોગ કરે છે; મર્યાદિત કદની પેટા સમસ્યા પર રોકાતા પહેલા પુનરાવર્તનોની સતત સંખ્યા હોય છે. બીટ એરેને કદના બિટ્સના મોટા બ્લોક અને કદના બિટ્સના નાના બ્લોકમાં વિભાજિત કરવામાં આવે છે. દરેક મોટા બ્લોક માટે, તેના પ્રથમ બીટનો ક્રમ અલગ કોષ્ટકમાં સંગ્રહિત કરવામાં આવે છે; આવી દરેક એન્ટ્રી સંગ્રહના કુલ બિટ્સ માટે બિટ્સ લે છે. મોટા બ્લોકની અંદર, અન્ય ડિરેક્ટરી તેમાં સમાવિષ્ટ દરેક નાના બ્લોકનો ક્રમ સંગ્રહિત કરે છે. અહીં તફાવત એ છે કે તેને ફક્ત દરેક એન્ટ્રી માટે બિટ્સની જરૂર છે, કારણ કે મોટા બ્લોક ધરાવતા પ્રથમ બીટની રેન્કના તફાવતોને જ સંગ્રહિત કરવાની જરૂર છે. આમ, આ કોષ્ટક કુલ બિટ્સ લે છે. પછી એક લુકઅપ ટેબલનો ઉપયોગ કરી શકાય છે જે દરેક સંભવિત રેન્ક ક્વેરીના જવાબને લંબાઈના બીટ સ્ટ્રિંગ પર સંગ્રહિત કરે છે; આ માટે સંગ્રહ જગ્યાના બિટ્સની જરૂર છે. આમ, આ દરેક સહાયક કોષ્ટકો જગ્યા લે છે, તેથી આ માહિતી માળખું સમય અને જગ્યાના બિટ્સમાં ક્રમ ક્વેરીઝને ટેકો આપે છે. સતત સમય માટે ક્વેરીનો જવાબ આપવા માટે, સતત સમય અલ્ગોરિધમ ગણતરી કરે છેઃ વ્યવહારમાં, લુકઅપ ટેબલને બિટવાઇઝ ઓપરેશન્સ અને નાના કોષ્ટકો દ્વારા બદલી શકાય છે જેનો ઉપયોગ નાના બ્લોકમાં સેટ કરેલા બિટ્સની સંખ્યા શોધવા માટે થઈ શકે છે. આ ઘણીવાર ફાયદાકારક હોય છે, કારણ કે સંક્ષિપ્ત ડેટા સ્ટ્રક્ચર્સ મોટા ડેટા સમૂહોમાં તેમના ઉપયોગોને શોધી કાઢે છે, જે કિસ્સામાં કેશ મિસ વધુ વારંવાર બને છે અને નજીકના CPU કેશમાંથી લુકઅપ ટેબલને બહાર કાઢવાની શક્યતા વધારે બને છે. પસંદગીના પ્રશ્નોને ક્રમ માટે ઉપયોગમાં લેવાતા સમાન સહાયક માળખા પર દ્વિસંગી શોધ કરીને સરળતાથી સમર્થન આપી શકાય છે; જો કે, આ સૌથી ખરાબ કિસ્સામાં સમય લે છે. વધારાના સંગ્રહના બિટ્સનો ઉપયોગ કરીને વધુ જટિલ માળખાનો ઉપયોગ સતત સમયમાં પસંદગીને ટેકો આપવા માટે કરી શકાય છે. વ્યવહારમાં, આમાંના ઘણા ઉકેલોમાં સંકેતલિપીમાં છુપાયેલા અચળાંકો હોય છે જે કોઈપણ એસિમ્પ્ટોટિક લાભ સ્પષ્ટ થાય તે પહેલાં પ્રભુત્વ ધરાવે છે; બ્રોડવર્ડ ઓપરેશન્સ અને શબ્દ-સંરેખિત બ્લોકનો ઉપયોગ કરીને અમલીકરણ ઘણીવાર વ્યવહારમાં વધુ સારું પ્રદર્શન કરે છે. એન્ટ્રોપી-કોમ્પ્રેસ્ડ સોલ્યુશન્સ અવકાશ અભિગમને એ નોંધ કરીને સુધારી શકાય છે કે ત્યાં (અથવા બરાબર 1 ની લંબાઈના દ્વિસંગી શબ્દમાળાઓ) ના અલગ-અલગ ઉપગણ છે, અને આમ સંગ્રહિત કરવા માટે જરૂરી બિટ્સની સંખ્યા પરની માહિતી સૈદ્ધાંતિક રીતે ઓછી બંધાયેલ છે. એક સંક્ષિપ્ત (સ્થિર) શબ્દકોશ છે જે આ મર્યાદાને પ્રાપ્ત કરે છે, એટલે કે જગ્યાનો ઉપયોગ કરીને. આ માળખું ક્રમને ટેકો આપવા અને પ્રશ્નો પસંદ કરવા માટે વિસ્તૃત કરી શકાય છે અને જગ્યા લે છે. આ માળખામાં સાચા ક્રમના પ્રશ્નો જોકે સમૂહમાં સમાવિષ્ટ ઘટકો સુધી મર્યાદિત છે, જે ન્યૂનતમ સંપૂર્ણ હેશિંગ કાર્યો કેવી રીતે કાર્ય કરે છે તેના સમાન છે. સમય લેતા પ્રશ્નો સાથે શબ્દકોશની સંગ્રહ જગ્યાને ઘટાડીને આ મર્યાદાને જગ્યા/સમયના વિનિમયમાં ઘટાડી શકાય છે. અનુક્રમણિકા આધારિત સહાયક શબ્દકોશનું નિર્માણ કરવું પણ શક્ય છે (પરંતુ પસંદ નહીં) જે બિટ્સ કરતાં ઓછો ઉપયોગ કરે છે. આવા શબ્દકોશને મોનોટોન મિનિમલ પરફેક્ટ હેશ ફંક્શન કહેવામાં આવે છે, અને તેને ઓછા બિટ્સનો ઉપયોગ કરીને અમલમાં મૂકી શકાય છે. સંક્ષિપ્ત હેશ કોષ્ટકો એક સંક્ષિપ્ત હેશ કોષ્ટક, જેને સંક્ષિપ્ત અનિયમિત શબ્દકોશ તરીકે પણ ઓળખવામાં આવે છે, તે એક માહિતી માળખું છે જે અવકાશ બિટ્સનો ઉપયોગ કરીને બ્રહ્માંડમાંથી કીઓ સંગ્રહિત કરે છે, અને સતત અપેક્ષિત સમયમાં સભ્યપદના પ્રશ્નોને ટેકો આપે છે. જો સંક્ષિપ્ત હેશ ટેબલ સતત અપેક્ષિત સમયમાં નિવેશ અને કાઢી નાખવાનું પણ સમર્થન કરે છે, તો તેને ગતિશીલ તરીકે ઓળખવામાં આવે છે, અને અન્યથા તેને સ્થિર તરીકે ઓળખવામાં આવે છે. પ્રથમ ગતિશીલ સંક્ષિપ્ત હેશ ટેબલ 2003માં રમણ અને રાવને કારણે હતું. એવા કિસ્સામાં જ્યાં, તેમનું સોલ્યુશન સ્પેસ બિટ્સનો ઉપયોગ કરે છે. ત્યારબાદ, એવું દર્શાવવામાં આવ્યું હતું કે આ સ્પેસ બાઉન્ડને કોઈપણ સ્થિર સંખ્યામાં લઘુગણક માટે બિટ્સમાં સુધારી શકાય છે. બાદમાંનો ઉકેલ ઉચ્ચ સંભાવના સાથે સૌથી ખરાબ સ્થિતિમાં સતત તમામ કામગીરીને ટેકો આપે છે. પ્રથમ સ્થિર સંક્ષિપ્ત હેશ ટેબલ 1999માં પાઘને કારણે હતું. એવા કિસ્સામાં જ્યાં, તેમનો ઉકેલ સ્પેસ બિટ્સનો ઉપયોગ કરે છે, અને સૌથી ખરાબ-કેસ કોન્સ્ટન્ટ-ટાઇમ ક્વેરીઝને સપોર્ટ કરે છે. આ બાઉન્ડ પછીથી બિટ્સમાં અને પછી બિટ્સમાં સુધારવામાં આવ્યું હતું. જ્યારે પ્રથમ બે ઉકેલો સૌથી ખરાબ-કેસ સ્થિર-સમયના પ્રશ્નોને ટેકો આપે છે, ત્યારે અંતિમ ઉકેલ સતત અપેક્ષિત-સમયના પ્રશ્નોને ટેકો આપે છે. અંતિમ ઉકેલ માટે કદના લુકઅપ કોષ્ટકની પહોંચ પણ જરૂરી છે, પરંતુ આ લુકઅપ કોષ્ટક સંગ્રહિત કરવામાં આવતા તત્વોના સમૂહથી સ્વતંત્ર છે. અન્ય ઉદાહરણો મનસ્વી લંબાઈ (પાસ્કલ સ્ટ્રિંગ) ધરાવતી સ્ટ્રિંગ ઝેડ + લોગ (ઝેડ) જગ્યા લે છે, અને આમ સંક્ષિપ્ત છે. જો મહત્તમ લંબાઈ હોય-જે વ્યવહારમાં કેસ છે, કારણ કે 232 = 4 ગી. બી. ડેટા ખૂબ જ લાંબી સ્ટ્રિંગ છે, અને 264 = 16 ઈ. આઈ. બી. ડેટા વ્યવહારમાં કોઈપણ સ્ટ્રિંગ કરતા મોટો છે-તો પછી લંબાઈ ધરાવતી સ્ટ્રિંગ પણ ગર્ભિત છે, જે Z + k જગ્યા લે છે, જ્યાં k એ મહત્તમ લંબાઈ (દા. ત., 64 બિટ્સ) નું પ્રતિનિધિત્વ કરવા માટે ડેટાની સંખ્યા છે. જ્યારે ચલ-લંબાઈની વસ્તુઓ (જેમ કે શબ્દમાળાઓ) નો ક્રમ એન્કોડ કરવાની જરૂર હોય, ત્યારે વિવિધ શક્યતાઓ હોય છે. એક સીધો અભિગમ એ છે કે દરેક રેકોર્ડમાં લંબાઈ અને એક વસ્તુ સંગ્રહિત કરવી-આ પછી એક પછી એક મૂકી શકાય છે. આ કાર્યક્ષમ આગામી પરવાનગી આપે છે, પરંતુ kth આઇટમ શોધી શકતા નથી. એક વિકલ્પ એ છે કે વસ્તુઓને સીમાંકન (દા. ત., નલ-ટર્મિનેટેડ સ્ટ્રિંગ) સાથે ક્રમમાં મૂકવી. આ લંબાઈને બદલે સીમાંકનનો ઉપયોગ કરે છે, અને તે નોંધપાત્ર રીતે ધીમું છે, કારણ કે સીમાંકન માટે સમગ્ર ક્રમને સ્કેન કરવો આવશ્યક છે. આ બંને જગ્યા-કાર્યક્ષમ છે. એક વૈકલ્પિક અભિગમ આઉટ-ઓફ-બેન્ડ સેપરેશન છેઃ વસ્તુઓને સરળતાથી એક પછી એક મૂકી શકાય છે, જેમાં કોઈ સીમાંકન નથી. વસ્તુની મર્યાદાને પછી લંબાઈના ક્રમ તરીકે સંગ્રહિત કરી શકાય છે, અથવા વધુ સારી રીતે, આ ક્રમમાં ઓફસેટ કરી શકાય છે. વૈકલ્પિક રીતે, એક અલગ દ્વિસંગી શબ્દમાળા જેમાં વસ્તુ જ્યાંથી શરૂ થાય છે ત્યાં 1s હોય છે, અને દરેક જગ્યાએ 0s તેની સાથે એન્કોડ કરવામાં આવે છે. આ શબ્દમાળાને જોતાં, કાર્ય ઝડપથી નક્કી કરી શકે છે કે દરેક વસ્તુ ક્યાંથી શરૂ થાય છે, તેની અનુક્રમણિકા આપવામાં આવે છે. આ કોમ્પેક્ટ છે પરંતુ સંક્ષિપ્ત નથી, કારણ કે તે 2 ઝેડ જગ્યા લે છે, જે ઓ (ઝેડ) છે. બીજું ઉદાહરણ દ્વિસંગી વૃક્ષનું પ્રતિનિધિત્વ છેઃ ગાંઠો પર મનસ્વી દ્વિસંગી વૃક્ષને બિટ્સમાં રજૂ કરી શકાય છે જ્યારે કોઈપણ નોડ પર વિવિધ કામગીરીને ટેકો આપે છે, જેમાં તેના પેરેન્ટ, તેના ડાબા અને જમણા ચાઈલ્ડને શોધવાનો અને તેના સબટ્રીનું કદ પરત કરવાનો સમાવેશ થાય છે, દરેક સ્થિર સમયમાં. ગાંઠો પર વિવિધ દ્વિસંગી વૃક્ષોની સંખ્યા છે. મોટા માટે, આ લગભગ છે; આમ આપણે તેને એન્કોડ કરવા માટે ઓછામાં ઓછા લગભગ બિટ્સની જરૂર છે. એક સંક્ષિપ્ત દ્વિસંગી વૃક્ષ તેથી નોડ દીઠ માત્ર બિટ્સ પર કબજો કરશે. ન્યુનતમ સંપૂર્ણ હેશ કાર્ય પણ જુઓ સુકિન્ક્ટ નોન-ઇન્ટરેક્ટિવ આર્ગ્યુમેન્ટ્સ ઓફ નોલેજ રેફરન્સ