Aaaaa988

33

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