Aaaaa988

333

Sep 25th, 2021
752
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <set>
  4. #include <fstream>
  5. #include "libBook.h"
  6.  
  7. using namespace std;
  8.  
  9. int** initMatrix(int size){
  10.     int** matrix = new int*[size];
  11.     for (int i = 0; i < size; i++)
  12.         matrix[i] = new int[size];
  13.     for (int i = 0; i < size; i++){
  14.         for (int j = 0; j < size; j++){
  15.             matrix[i][j] = 0;
  16.         }
  17.     }
  18.     return matrix;
  19. }
  20.  
  21.  
  22. void fillMatrixFromString(int** matrix, string str){
  23.         for (int i = 0, byte; i < str.size(); i++){
  24.             byte = str[i];
  25.             if(byte == -1)
  26.                 byte = 1;
  27.             matrix[0][i] = byte;
  28.         }
  29.         for (int i = 1; i < str.size(); i++){
  30.             for (int j = 0; j < str.size(); j++){
  31.                 matrix[i][j] = matrix[0][(j+i)%str.size()];
  32.             }
  33.         }
  34. }
  35.  
  36. void outputMatrix(int** matrix, int N){
  37.     cout<<endl;
  38.     cout.setf(ios::fixed);
  39.     for (int i = 0; i < N; i++){
  40.         for (int j = 0; j < N; j++){
  41.             if(matrix[i][j] == -1 || matrix[i][j] == 10){
  42.                 if(matrix[i][j] == 38)
  43.                     cout<<setw(4)<<"eof"<<" ";
  44.                 if(matrix[i][j] == 10)
  45.                     cout<<setw(4)<<"\\n"<<" ";
  46.             }else{
  47.                 cout<<setw(4)<<(char)matrix[i][j]<<" ";
  48.             }
  49.         }
  50.         cout<<endl;
  51.     }
  52.     cout<<endl;
  53. }
  54.  
  55. void outputMatrix(int** matrix, int N, int M){
  56.     cout<<endl;
  57.     for (int i = 0; i < N; i++){
  58.         for (int j = 0; j < M; j++){
  59.             if(j == 0){
  60.                 if(matrix[i][j] == -1 || matrix[i][j] == 10){
  61.                     if(matrix[i][j] == 38)
  62.                         cout<<i<<"eof"<<" ";
  63.                     if(matrix[i][j] == 10)
  64.                         cout<<i<<"\\n"<<"  ";
  65.                 }else{
  66.                     cout<<i<<" "<<(char)matrix[i][j]<<"  ";
  67.                 }
  68.             }else{
  69.                 cout<<" "<<matrix[i][j]<<"  ";
  70.             }
  71.  
  72.         }
  73.         cout<<endl;
  74.     }
  75.     cout<<endl;
  76. }
  77.  
  78. void outputArray(int* array, int size){
  79.     for (int j = 0; j < size; j++){
  80.         if(array[j] == -1 || array[j] == 10){
  81.             if(array[j] == 38)
  82.                 cout<<"eof"<<" ";
  83.             if(array[j] == 10)
  84.                 cout<<"\\n"<<"  ";
  85.         }else{
  86.             cout<<" "<<(char)array[j]<<"  ";
  87.         }
  88.     }
  89.     cout<<endl;
  90. }
  91.  
  92. void quickSort(int *Array, int size, int L, int R){
  93.     while(L < R){
  94.         int x = Array[L], i = L, j = R;
  95.         while (i <= j){
  96.             while (Array[i] < x) i++;
  97.             while (x < Array[j]) j--;
  98.             if (i <= j){
  99.                 int temp;
  100.                 temp = Array[i];
  101.                 Array[i] = Array[j];
  102.                 Array[j] = temp;
  103.                 i++; j--;
  104.             }
  105.             if((j - L) > (R - i)){
  106.                 quickSort(Array, size, i, R);
  107.                 R = j;
  108.             }else{
  109.                 quickSort(Array, size, L, j);
  110.                 L = i;
  111.             }
  112.         }
  113.     }
  114. }
  115.  
  116. void quickSort(int **Array, int size, int L, int R, int pointer){
  117.     while(L < R){
  118.         int x = Array[L][pointer], i = L, j = R;
  119.         while (i <= j){
  120.             while (Array[i][pointer] < x) i++;
  121.             while (x < Array[j][pointer]) j--;
  122.             if (i <= j){
  123.                 int temp;
  124.                 for(int k = 0; k < size; k++){
  125.                     temp = Array[i][k];
  126.                     Array[i][k] = Array[j][k];
  127.                     Array[j][k] = temp;
  128.                 }
  129.                 i++; j--;
  130.             }
  131.             if((j - L) > (R - i)){
  132.                 quickSort(Array, size, i, R, pointer);
  133.                 R = j;
  134.             }else{
  135.                 quickSort(Array, size, L, j, pointer);
  136.                 L = i;
  137.             }
  138.         }
  139.     }
  140. }
  141.  
  142. void sortMatrix(int** array, int size, int begin, int end, int pointer){
  143.     int currentItem = 0;
  144.     int series = 0;
  145.     if(pointer == size-2)
  146.         quickSort(array, size, 0, size-1, pointer);
  147.     for(int i = begin; i < end; i++){
  148.         if (currentItem == array[i][pointer]){
  149.             series++;
  150.         }else{
  151.             if(series > 0){
  152.                 quickSort(array, size, i-series-1, i-1, pointer-1);
  153.                 sortMatrix(array, size, i-series-1, i , pointer-1);
  154.                 series = 0;
  155.             }
  156.             currentItem = array[i][pointer];
  157.         }
  158.     }
  159.     if(series > 0){
  160.         quickSort(array, size, end-series-1, end-1, pointer-1);
  161.         sortMatrix(array, size, end-series-1, end , pointer-1);
  162.     }
  163. }
  164.  
  165. int* getBWT(int** array, int size){
  166.     int* BWT = new int[size];
  167.     for(int i = 0; i < size; i++){
  168.         BWT[i] = array[i][size-1];
  169.     }
  170.     return BWT;
  171. }
  172.  
  173. void copyArray(int* array1, int* array2, int size){
  174.     for(int i = 0; i < size; i++)
  175.         array2[i] = array1[i];
  176. }
  177.  
  178. int** initSecondArray(int size){
  179.     int** array = new int*[size];
  180.     for(int i = 0; i < size; i++){
  181.         array[i] = new int[2];
  182.     }
  183.     return array;
  184. }
  185.  
  186. void fillSecondArray(int* BWT, int* firstArray, int** secondArray, int size){
  187.     for(int i = 0; i < size; i++){
  188.         for(int j = 0; j < size; j++){
  189.             if(BWT[i] == firstArray[j]){
  190.                 secondArray[i][0] = BWT[i];
  191.                 secondArray[i][1] = j;
  192.                 firstArray[j] = 0;
  193.                 break;
  194.             }
  195.         }
  196.     }
  197. }
  198.  
  199. string restoreMessage(int** secondArray, int index, int size){
  200.     if (size == 0) return "";
  201.     string str = string(1,secondArray[index][0]);
  202.     //string str = to_string(secondArray[index][0]) + " ";
  203.     return  str + restoreMessage(secondArray, secondArray[index][1], size-1);
  204. }
  205.  
  206. int* StringToBTW(string str){
  207.     int* BTW = new int[str.size()];
  208.     char item;
  209.     for(int i = 0; i < str.size(); i++){
  210.         item = str[i];
  211.         BTW[i] = (int)item;
  212.     }
  213.     return BTW;
  214. }
  215.  
  216. string BWTToString(int* BWT, int size){
  217.     string str = "";
  218.     for(int i = 0; i < size; i++){
  219.         str += string(1, (char)BWT[i]);
  220.     }
  221.     return str;
  222. }
  223.  
  224. int* getRowWithFirstChar(int**matrix, int size){
  225.     int* result = new int[size];
  226.  
  227.     for(int i = 0; i < size; i++){
  228.         result[i] = matrix[1][i];
  229.     }
  230.     return result;
  231. }
  232.  
  233. int searchIndexRowWithFirstChar(int**matrix, int size, int* firstRow){
  234.     bool equals = true;
  235.     for(int i = 0; i <size; i++){
  236.         for(int j = 0; j <size; j++){
  237.             if(firstRow[j] != matrix[i][j])
  238.                 equals = false;
  239.         }
  240.         if(equals)
  241.             return i;
  242.         equals = true;
  243.     }
  244.     return 0;
  245. }
  246.  
  247. string getblockBWT(int**matrix, int*BWT, string message){
  248.     if(message == "") return "";
  249.     matrix = initMatrix(message.size());
  250.     fillMatrixFromString(matrix, message);
  251.     //outputMatrix(matrix, message.size());
  252.     int* firstCharRow = getRowWithFirstChar(matrix, message.size());
  253.  
  254.     sortMatrix(matrix, message.size(), 0, message.size(), message.size()-2);
  255.     //outputMatrix(matrix, message.size());
  256.     BWT = getBWT(matrix, message.size());
  257.  
  258.     return BWTToString(BWT, message.size()) + (char)(searchIndexRowWithFirstChar(matrix, message.size(), firstCharRow)+33);
  259. }
  260.  
  261. int main() {
  262.     string fileName = "../lol.txt";
  263.  
  264.     int blockSize = 50;
  265.     int countChar = blockSize;
  266.     int** charMatrix = nullptr;
  267.     int* BWT = nullptr;
  268.     int* firstDecodeArray = new int [countChar];
  269.     int** secondDecodeArray = initSecondArray(countChar);
  270.     string BWTstr = "";
  271.  
  272.     ifstream fin;
  273.     char symbol;
  274.     string blockText = "";
  275.     fin.open(fileName);
  276.     bool eof = true;
  277.     if(!fin.is_open()){
  278.         cout<<"fail read from file";
  279.     }else{
  280.         while(eof){
  281.             for(int i = 0; i < blockSize; i++){
  282.                 symbol = fin.get();
  283.                 blockText += symbol;
  284.                 if(symbol == -1){
  285.                     eof=false;
  286.                     break;
  287.                 }
  288.             }
  289.             //cout<<blockText<<endl;
  290.             BWTstr += getblockBWT(charMatrix, BWT,  blockText);
  291.             blockText = "";
  292.         }
  293.     }
  294.     cout<<"BWT\n"<<BWTstr<<endl;
  295.  
  296.     set<char> Alphabet = readAlphabetFromStr(BWTstr);
  297.     string bookCode = "";
  298.  
  299.     int* arrayAlphabet;
  300.     int sizeArray = Alphabet.size();
  301.     arrayAlphabet = new int[sizeArray];
  302.  
  303.     set<char>::iterator setIt = Alphabet.begin();
  304.     for(int i = 0; i < sizeArray; i++, setIt++){
  305.         arrayAlphabet[i] = *setIt;
  306.     }
  307.  
  308.     bookCode = stackBookStr(BWTstr, arrayAlphabet, sizeArray);
  309.     cout<<endl;
  310.     cout<<"Text into F1Code : \n"<<bookCode<<endl<<endl;
  311.  
  312.     setIt = Alphabet.begin();
  313.     for(int i = 0; i < sizeArray; i++, setIt++){
  314.         arrayAlphabet[i] = *setIt;
  315.     }
  316.  
  317.     int bitCountCode = bookCode.size();
  318.     int bitCountFile = weightBitOfFile(fileName);
  319.  
  320.     string BookToBTW = stackBookDecode(f1_decode(bookCode), arrayAlphabet, sizeArray);
  321.     //cout<<"Restored BWT : \n"<<  BookToBTW <<endl;
  322.     cout<<endl;
  323.     cout<<"Bits in Code = "<< bitCountCode << ", Bits in File = " << bitCountFile <<endl;
  324.     cout<<"Compression ratio "<<(float)bitCountFile/bitCountCode<<endl;
  325.  
  326.     blockText = "";
  327.     char firstItem;
  328.     string result = "";
  329.     for(int i = 0, j = 0; i < BookToBTW.size(); i+=j){
  330.         for(j = 0; j < blockSize; j++){
  331.             if (i+j > BookToBTW.size())
  332.                 break;
  333.             blockText += BookToBTW[i+j];
  334.         }
  335.         firstItem = BookToBTW[i+j];
  336.         j++;
  337.         if(blockText.size() < blockSize){
  338.             firstItem = (int)blockText[blockText.size()-2];
  339.             blockText = blockText.substr(0, blockText.size()-2);
  340.         }
  341.  
  342.         int* restoredBWT = StringToBTW(blockText);
  343.         copyArray(restoredBWT, firstDecodeArray, blockText.size());
  344.         quickSort(firstDecodeArray, blockText.size(), 0 , blockText.size()-1);
  345.  
  346.         fillSecondArray(restoredBWT, firstDecodeArray, secondDecodeArray, blockText.size());
  347.         result += restoreMessage(secondDecodeArray, ((int)firstItem)-33, blockText.size());
  348.  
  349.         //cout<<blockText <<"|| "<< ((int)firstItem)-33<<endl;
  350.         blockText = "";
  351.     }
  352.     cout<<endl;
  353.     cout<<"Restored Text:\n"<<result;
  354.  
  355.     return 0;
  356. }
RAW Paste Data