Advertisement
Guest User

lz77

a guest
Feb 24th, 2018
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.80 KB | None | 0 0
  1. #include "ReadWriterEncoder.h"
  2. using namespace std;
  3.  
  4. // Поиск максимальной грани для подстроки
  5. int findBorder(string& input, int index, char newChar, int* bordersArray)
  6. {
  7.     if (index == 0) // подстрока из одного элемента не имеет собственных граней
  8.         return 0;
  9.     int lastBorderLength = bordersArray[index - 1]; // длина максимальной грани предыдущей подстроки
  10.  
  11.     if (input[lastBorderLength] == newChar) // если символ совпал с последним, то грань увеличилась на 1
  12.         return lastBorderLength + 1;
  13.     else if (lastBorderLength == 0) // если последняя грань была нулевой, то ничего не изменилось
  14.         return 0;
  15.     else
  16.         return findBorder(input, lastBorderLength, newChar, bordersArray); // ищем подстроку, в которой символ будет входить в грань
  17. }
  18.  
  19.  
  20. // Поиск подстроки p в строке t
  21. Node findNewNode(string& prevBuf, string& histBuf)
  22. {
  23.     string input = prevBuf + "*" + histBuf;
  24.  
  25.     int* bordersArray = new int[input.length()];
  26.  
  27.     int maxSubstrLength = 0; // длина самой большой одинаковой подстроки
  28.     int maxSubstrIndex = 0; // индекс конца самой большой одинаковой подстроки в буфере истории
  29.     for (int i = 0; i < input.length(); ++i)
  30.     {
  31.         int r = findBorder(input, i, input[i], bordersArray);
  32.         bordersArray[i] = r;
  33.         if (i > prevBuf.length() && r > maxSubstrLength) // обновляем максимальный индекс только в истории
  34.         {
  35.             maxSubstrLength = r; // новая найденная грань - длина максимального совпадения
  36.             maxSubstrIndex = i - maxSubstrLength - prevBuf.length();//для поиска начала сдвигаем на длину грани и буфера
  37.         }
  38.     }
  39.     int lastBorder = bordersArray[input.length() - 1];
  40.     delete[] bordersArray;
  41.  
  42.     if (maxSubstrLength == 0)
  43.         return Node(0, 0, prevBuf[0]);
  44.  
  45.     if (lastBorder == 0)
  46.         return Node(histBuf.length() - maxSubstrIndex, maxSubstrLength, prevBuf[maxSubstrLength]);
  47.  
  48.     int lastBorderLength = lastBorder;
  49.     int lastBorderIndex = histBuf.length() - lastBorderLength;
  50.  
  51.     int i = 0;
  52.     int j = lastBorderIndex;
  53.     while (i < prevBuf.length() & lastBorderLength != 0)
  54.     {
  55.         if (prevBuf[i++] == histBuf[j++])
  56.             lastBorderLength += 1;
  57.         else
  58.             break;
  59.         if (j >= histBuf.length())
  60.             j = lastBorderIndex;
  61.     }
  62.     lastBorderLength = lastBorderLength - lastBorder;
  63.  
  64.     if (lastBorderLength > maxSubstrLength)
  65.         return Node(bordersArray[input.length() - 1], lastBorderLength, prevBuf[lastBorderLength]);
  66.     return Node(histBuf.length() - maxSubstrIndex, maxSubstrLength, prevBuf[maxSubstrLength]);
  67. }
  68.  
  69.  
  70. // s — исходная строка
  71. // res - вектор троек (offs, len, ch)
  72. // histBufMax, prevBufMax - Макс длины буферов истории и предпросмотра
  73. // функция возвращает список блоков
  74. void encodeLZ77(string& s, vector<Node>& res, int histBufMax, int prevBufMax)
  75. {
  76.     int histStart = 0;
  77.     int histEnd = 0;
  78.     int prevStart = 0;
  79.     int prevEnd = prevBufMax;
  80.  
  81.     while (prevStart < s.length())
  82.     {
  83.         string histBuf = s.substr(histStart, histEnd - histStart);
  84.         string prevBuf = s.substr(prevStart, prevEnd - prevStart);
  85.  
  86.         Node node = findNewNode(prevBuf, histBuf);
  87.         res.push_back(node);
  88.  
  89.         histEnd += node.len + 1;
  90.         prevStart += node.len + 1;
  91.         prevEnd += node.len + 1;
  92.  
  93.         if (histBuf.length() > histBufMax)
  94.             histStart += histBuf.length() - histBufMax;
  95.     }
  96. }
  97.  
  98. int main(int argc, const char* argv[])
  99. {
  100.     //Здесь предлагается задать размер окна в байтах (отдельно буфера предыстории и предпросмотра)
  101.     //В сумме должны образовывать столько, сколько надо в задании
  102.     //history buffer 3 kb
  103.     int histBufMax = 1024*3;
  104.     //preview buffer 1 kb
  105.     int prevBufMax = 1024;
  106.  
  107.     ReadWriter rw;
  108.     string s = "";
  109.     rw.readString(s);
  110.  
  111.     //Основной структурой выбран вектор, так как заранее неизвестно какое количество элементов будет записано
  112.     vector<Node> v;
  113.  
  114.     encodeLZ77(s, v, histBufMax, prevBufMax);
  115.  
  116.     rw.writeCode(v);
  117.     return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement