Programming 01

🟢 Տվյալների սեղմում 🗄️

Բոլորդ էլ երևի թե առընչվել եք ծրագրերի, որոնք թույլ են տալիս «սեղմել» տվյալները (data compression), դրանց զբաղեցրած ծավալը նվազեցնելու համար (WinRAR, 7-zip, WinZIP, Gzip և այլն)։ Իսկ երբևէ մտածել եք, թե ինչպե՞ս է տեղի ունենում տվյալների սեղմումը, թե ի՞նչ եղանակով է հնարավոր պահել նույն տվյալը օգտագործելով ավելի քիչ քանակի հիշողություն։
Որպեսզի ավելի լավ պատկերացնեք, թե ինչպե՞ս է տեղի ունենում տվյալների սեղմումը, դիտարկենք տվյալների սեղման պարզ ալգորիթմ, որը հայտնի է «կոդավորում երկարությամբ» (Run length encoding) անունով։
Այս ալգորիթմը տողում հանդիպող հաջորդաբար կրկնվող սիմվոլները փոխարինում է այդ սիմվոլների կրկնության քանակով։
Օրինակ` DDDaadddddff -ը սեղմելուց կստանանք 3D2a5d2f տողը։
  • D տառը հաջորդաբար կրկնվում է 3 անգամ, DDD հաջորդականությունը կփոխարինվի 3D տողով։
  • a տառը հաջորդաբար կրկնվում է 2 անգամ, aa հաջորդականությունը կփոխարինվի 2a տողով։
  • d տառը հաջորդաբար կրկնվում է 5 անգամ, ddddd հաջորդականությունը կփոխարինվի 5d տողով։
  • f տառը հաջորդաբար կրկնվում է 2 անգամ,ff հաջորդականությունը կփոխարինվի 2f տողով։
Այսպիսով, սեղման ալգորիթմը կիրառելուց հետո, կստանանք “3D2a5d2f" տողը։
Տողում ամեն սիմվոլը զբաղեցնում է 1 բայթ հիշողություն։ Հետևաբար "DDDaadddddff" տողը զբաղեցնում է 12 բայթ, իսկ սեղմված 3D2a5d2f տողը արդեն կզբաղեցնի 8 բայթ հիշողություն։ Սեղման ալգորիթմը կիրառելուց հետո մենք կխնայենք 4 բայթ։
Դիտարկենք ևս մեկ օրինակ`“aaabbbccc" տողը զբաղեցնում է 9 բայթ։ Սեղման ալգորիթմը կիրառելուց հետո կստանանք “3a3b3c” տողը, որը արդեն զբաղեցնում է 6 բայթ հիշողություն։ Արդյունքում կխնայենք 3 բայթ հիշողություն։
Դե ինչ, եկե՛ք գրենք ծրագիր, որը կսեղմի մուտքագրված տողը նկարագրված ալգորիթմով։ Պարզության համար կարող ենք ենթադրել, որ մուտքագրված տողը չի պարունակում թվեր։ Ծրագիրը պետք է էկրանին տպի մուտքագրված տեքստը, մուտքագրված տեքստի չափը, սեղմված տողը և սեղմված տողի չափը։
 
notion image
 
#include <iostream>
#include <string>

std::string compress(std::string text) {
  //TODO: Put your code here
}

int main() {
    std::string text;
    std::cout << "Text: ";
    std::getline(std::cin, text);
    std::cout << text << std::endl;
    std::cout << "Original text size: " << text.size() << " bytes"<< std::endl;
    // TODO: Put your code here
}
 
Պարզ է, որ այս ալգորիթմը այդքան էլ էֆեկտիվ չէ սովորական տեքստերի սեղման համար, քանի որ սովորական տեքստում հազիվ թե հանդիպեք կրկնվող սիմվոլների երկար հաջորդականությունների։ Սակայն, եթե դիտարկենք նկարներ կամ վիդեո ֆայլեր, ապա կտեսնեք, որ այդպիսի ֆայլերը շատ հաճախ պարունակում են բավական երկար կրկնվող գույների հաջորդականություններ։ Կիրառելով նկարագրված ալգորիթմը նկարի ֆայլի վրա, մենք կարող ենք էֆեկտիվորեն սեղմել այն, պահելով միայն այս կամ այն գույնի հաջորդաբար կրկնությունների քանակը։
notion image
 
💡
Իհարկե, այս ալգորիթմը միակը չէ։ Եթե փորձեք փնտրել, համացանցում կգտնեք տվյալների սեղման բազմաթիվ ալգորիթմներ։ Ամենահայտնի ալգորիթմներից է, օրինակ, Հոֆմանի կոդը (Hoffman codeԳոյություն ունեն նաև բազմաթիվ այլ ալգորիթմներ։
 

Ծրագրավորման ոճ

Խնդիրը գրելուց առաջ, ևս մեկ անգամ կարդացեք “Ծրագրավորման ոճ” դասը։ Մի գրե՛ք ամբողջ ծրագիրը մեկ main ֆունկցիայի մեջ։ Մտածեք, թե ի՞նչ տրամաբանական հատվածների (ֆունկցիաների) է կարելի բաժանել ծրագիրը, որպեսզի կոդը լինի հնարավորինս ընթեռնելի։ Ֆունկցիաներ գրելիս, փորձեք պահպանել «եզակի պատասխանատվության» (single responsobility) սկզբունքը։ Օգտագործե՛ք մտածված և իմաստային անուններ և՛ փոփոխականների և՛ ֆունկցիաների համար։
 
 
 
 
 
 
 
 
 
 
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in