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

Բոլորդ էլ երևի թե առընչվել եք ծրագրերի, որոնք թույլ են տալիս «սեղմել» տվյալները (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 բայթ հիշողություն։

Դե ինչ, եկե՛ք գրենք ծրագիր, որը կսեղմի մուտքագրված տողը նկարագրված ալգորիթմով։ Պարզության համար կարող ենք ենթադրել, որ մուտքագրված տողը չի պարունակում թվեր։ Ծրագիրը պետք է էկրանին տպի մուտքագրված տեքստը, մուտքագրված տեքստի չափը, սեղմված տողը և սեղմված տողի չափը։

#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
}

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

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