Grammar-based code
વ્યાકરણ-આધારિત સંકેતો અથવા વ્યાકરણ-આધારિત સંકોચન એ સંકોચન અલ્ગોરિધમ્સ છે જે શબ્દમાળાને સંકુચિત કરવા માટે સંદર્ભ-મુક્ત વ્યાકરણ (સી. એફ. જી.) બનાવવાના વિચાર પર આધારિત છે. ઉદાહરણોમાં સાર્વત્રિક લોસલેસ ડેટા કમ્પ્રેશન અલ્ગોરિધમ્સનો સમાવેશ થાય છે. માહિતી ક્રમને સંકુચિત કરવા માટે, વ્યાકરણ આધારિત કોડ સંદર્ભ-મુક્ત વ્યાકરણમાં પરિવર્તિત થાય છે. ઇનપુટ ક્રમ (સૌથી નાની વ્યાકરણ સમસ્યા) માટે સૌથી નાનું વ્યાકરણ શોધવાની સમસ્યા એન. પી.-હાર્ડ તરીકે ઓળખાય છે, તેથી ઘણા વ્યાકરણ-પરિવર્તન અલ્ગોરિધમ્સ સૈદ્ધાંતિક અને વ્યવહારુ દ્રષ્ટિકોણથી પ્રસ્તાવિત કરવામાં આવે છે. સામાન્ય રીતે, ઉત્પાદિત વ્યાકરણને અંકગણિત કોડિંગ જેવા આંકડાકીય સંકેતલિપી દ્વારા વધુ સંકુચિત કરવામાં આવે છે. ઉદાહરણો અને લાક્ષણિકતાઓ વ્યાકરણ આધારિત કોડનો વર્ગ ખૂબ વ્યાપક છે. તેમાં બ્લોક કોડ્સ, મલ્ટિલેવલ પેટર્ન મેચિંગ (એમ. પી. એમ.) અલ્ગોરિધમ, વૃદ્ધિશીલ લેમ્પેલ-ઝિવ કોડની વિવિધતા અને અન્ય ઘણા નવા સાર્વત્રિક લોસલેસ કમ્પ્રેશન અલ્ગોરિધમ્સનો સમાવેશ થાય છે. વ્યાકરણ આધારિત સંકેતો એ અર્થમાં સાર્વત્રિક છે કે તેઓ મર્યાદિત મૂળાક્ષર સાથે કોઈપણ સ્થિર, એર્ગોડિક સ્રોતનો એન્ટ્રોપી દર એસિમ્પ્ટોટિક રીતે પ્રાપ્ત કરી શકે છે. વ્યવહારુ અલ્ગોરિધમ્સ નીચેના સંકોચન કાર્યક્રમો બાહ્ય કડીઓમાંથી ઉપલબ્ધ છે. સેક્વિટુર એ એક શાસ્ત્રીય વ્યાકરણ સંકોચન અલ્ગોરિધમ છે જે ક્રમિક રીતે ઇનપુટ ટેક્સ્ટને સી. એફ. જી. માં અનુવાદિત કરે છે, અને પછી ઉત્પાદિત સી. એફ. જી. ને અંકગણિત કોડર દ્વારા એન્કોડ કરવામાં આવે છે. ફરીથી જોડી એ સૌથી વધુ વારંવાર-પ્રથમ અવેજીની વ્યૂહરચનાનો ઉપયોગ કરીને લોભી અલ્ગોરિધમ છે. કોમ્પ્રેસિવ પ્રદર્શન શક્તિશાળી છે, જો કે મુખ્ય મેમરી જગ્યાની જરૂરિયાત ખૂબ મોટી છે. જી. એલ. ઝેડ. એ., જે એક વ્યાકરણનું નિર્માણ કરે છે જે ઘટાડી શકાય તેવું હોઈ શકે છે, એટલે કે, પુનરાવર્તન ધરાવે છે, જ્યાં પુનરાવર્તનની "જોડણી" નો એન્ટ્રોપી-કોડિંગ ખર્ચ તેમને પકડવા માટેના નિયમ બનાવવા અને એન્ટ્રોપી-કોડિંગ ખર્ચ કરતાં ઓછો હોય છે. (સામાન્ય રીતે, સંકોચન-શ્રેષ્ઠ એસ. એલ. જી. ઈરીડ્યુસિબલ નથી, અને સૌથી નાની વ્યાકરણ સમસ્યા વાસ્તવિક એસ. એલ. જી. સંકોચન સમસ્યાથી અલગ છે.) શબ્દકોશ કોડર ગ્રામર ઇન્ડક્શન સ્ટ્રેટ-લાઇન વ્યાકરણ સંદર્ભો પણ જુઓ બાહ્ય કડીઓ GLZA ચર્ચા અને કાગળનું વર્ણન વ્યાકરણ આધારિત કોડ્સનું વર્ણન ઉદાહરણ સાથે સેક્વિટુર કોડ્સ રી-પેયર કોડ્સ રી-પેયર કોડ્સ ગોન્ઝાલો નવારોનું એક સંસ્કરણ છે. ગ્રામરવિઝ 2-જાવામાં સેક્વિટુર, રી-પેયર અને સમાંતર રી-પેયરનું અમલીકરણ. ડેટા સંકોચન કોડિંગ સિદ્ધાંત માહિતી સિદ્ધાંત