Grammar-based code
ব্যাকরণ-ভিত্তিক কোড বা ব্যাকরণ-ভিত্তিক সংকোচন হল সংকোচন অ্যালগরিদম যা স্ট্রিং সংকুচিত করার জন্য একটি প্রসঙ্গ-মুক্ত ব্যাকরণ (সিএফজি) নির্মাণের ধারণার উপর ভিত্তি করে। উদাহরণগুলির মধ্যে রয়েছে সর্বজনীন ক্ষতিহীন ডেটা কম্প্রেশন অ্যালগরিদম। একটি তথ্য ক্রম সংকুচিত করার জন্য, একটি ব্যাকরণ-ভিত্তিক কোড একটি প্রসঙ্গ-মুক্ত ব্যাকরণে রূপান্তরিত হয়। একটি ইনপুট ক্রমের (ক্ষুদ্রতম ব্যাকরণ সমস্যা) জন্য একটি ক্ষুদ্রতম ব্যাকরণ খুঁজে বের করার সমস্যাটি এনপি-হার্ড হিসাবে পরিচিত, তাই অনেক ব্যাকরণ-রূপান্তর অ্যালগরিদম তাত্ত্বিক এবং ব্যবহারিক দৃষ্টিকোণ থেকে প্রস্তাবিত হয়। সাধারণত, উৎপাদিত ব্যাকরণটি গাণিতিক কোডিংয়ের মতো পরিসংখ্যানগত এনকোডার দ্বারা আরও সংকুচিত হয়। উদাহরণ এবং বৈশিষ্ট্য ব্যাকরণ-ভিত্তিক কোডের শ্রেণীটি খুব বিস্তৃত। এর মধ্যে রয়েছে ব্লক কোড, মাল্টিলেভেল প্যাটার্ন ম্যাচিং (এমপিএম) অ্যালগরিদম, ইনক্রিমেন্টাল পার্সিং লেমপেল-জিভ কোডের বৈচিত্র্য এবং আরও অনেক নতুন সার্বজনীন ক্ষতিহীন সংকোচন অ্যালগরিদম। ব্যাকরণ-ভিত্তিক কোডগুলি এই অর্থে সর্বজনীন যে তারা একটি সীমাবদ্ধ বর্ণমালা সহ যে কোনও স্থির, এর্গোডিক উৎসের এনট্রপি হার অ্যাসিম্পটোটিকভাবে অর্জন করতে পারে। ব্যবহারিক অ্যালগরিদম নিম্নলিখিত কম্প্রেশন প্রোগ্রামগুলি বাহ্যিক লিঙ্কগুলি থেকে পাওয়া যায়। সেকুইটুর হল একটি ধ্রুপদী ব্যাকরণ সংকোচন অ্যালগরিদম যা ক্রমানুসারে একটি ইনপুট পাঠ্যকে একটি সি. এফ. জি-তে অনুবাদ করে এবং তারপরে উত্পাদিত সি. এফ. জি একটি গাণিতিক কোডার দ্বারা এনকোড করা হয়। রি-পেয়ার হল একটি লোভী অ্যালগরিদম যা সর্বাধিক-ঘন-প্রথম প্রতিস্থাপনের কৌশল ব্যবহার করে। কম্প্রেসিভ পারফরম্যান্স শক্তিশালী, যদিও প্রধান মেমরি স্থানের প্রয়োজনীয়তা খুব বড়। জি. এল. জেড. এ, যা এমন একটি ব্যাকরণ তৈরি করে যা হ্রাসযোগ্য হতে পারে, অর্থাৎ, পুনরাবৃত্তি ধারণ করে, যেখানে পুনরাবৃত্তির "বানান বের করার" এনট্রপি-কোডিং খরচ একটি নিয়ম তৈরি এবং এনট্রপি-কোডিং খরচের চেয়ে কম। (সাধারণভাবে, সংকোচন-সর্বোত্তম এসএলজি অপরিবর্তনীয় নয়, এবং ক্ষুদ্রতম ব্যাকরণ সমস্যা প্রকৃত এসএলজি সংকোচনের সমস্যা থেকে আলাদা।) আরও দেখুন ডিকশনারি কোডার গ্রামার ইন্ডাকশন স্ট্রেইট-লাইন ব্যাকরণ রেফারেন্স বাহ্যিক লিঙ্ক জিএলজেডএ আলোচনা এবং কাগজ ব্যাকরণ-ভিত্তিক কোডগুলির বিবরণ উদাহরণ সহ সেকুইটার কোড পুনরায় জোড়া কোড পুনরায় জোড়া কোড গঞ্জালো নাভারোর একটি সংস্করণ। গ্রামারভিজ 2-জাভাতে সেকুইটার, রি-পেয়ার এবং সমান্তরাল রি-পেয়ারের বাস্তবায়ন। তথ্য সংকোচন কোডিং তত্ত্ব তথ্য তত্ত্ব