Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "ReadWriterEncoder.h"
- using namespace std;
- // Поиск максимальной грани для подстроки
- int findBorder(string& input, int index, char newChar, int* bordersArray)
- {
- if (index == 0) // подстрока из одного элемента не имеет собственных граней
- return 0;
- int lastBorderLength = bordersArray[index - 1]; // длина максимальной грани предыдущей подстроки
- if (input[lastBorderLength] == newChar) // если символ совпал с последним, то грань увеличилась на 1
- return lastBorderLength + 1;
- else if (lastBorderLength == 0) // если последняя грань была нулевой, то ничего не изменилось
- return 0;
- else
- return findBorder(input, lastBorderLength, newChar, bordersArray); // ищем подстроку, в которой символ будет входить в грань
- }
- // Поиск подстроки p в строке t
- Node findNewNode(string& prevBuf, string& histBuf)
- {
- string input = prevBuf + "*" + histBuf;
- int* bordersArray = new int[input.length()];
- int maxSubstrLength = 0; // длина самой большой одинаковой подстроки
- int maxSubstrIndex = 0; // индекс конца самой большой одинаковой подстроки в буфере истории
- for (int i = 0; i < input.length(); ++i)
- {
- int r = findBorder(input, i, input[i], bordersArray);
- bordersArray[i] = r;
- if (i > prevBuf.length() && r > maxSubstrLength) // обновляем максимальный индекс только в истории
- {
- maxSubstrLength = r; // новая найденная грань - длина максимального совпадения
- maxSubstrIndex = i - maxSubstrLength - prevBuf.length();//для поиска начала сдвигаем на длину грани и буфера
- }
- }
- int lastBorder = bordersArray[input.length() - 1];
- delete[] bordersArray;
- if (maxSubstrLength == 0)
- return Node(0, 0, prevBuf[0]);
- if (lastBorder == 0)
- return Node(histBuf.length() - maxSubstrIndex, maxSubstrLength, prevBuf[maxSubstrLength]);
- int lastBorderLength = lastBorder;
- int lastBorderIndex = histBuf.length() - lastBorderLength;
- int i = 0;
- int j = lastBorderIndex;
- while (i < prevBuf.length() & lastBorderLength != 0)
- {
- if (prevBuf[i++] == histBuf[j++])
- lastBorderLength += 1;
- else
- break;
- if (j >= histBuf.length())
- j = lastBorderIndex;
- }
- lastBorderLength = lastBorderLength - lastBorder;
- if (lastBorderLength > maxSubstrLength)
- return Node(bordersArray[input.length() - 1], lastBorderLength, prevBuf[lastBorderLength]);
- return Node(histBuf.length() - maxSubstrIndex, maxSubstrLength, prevBuf[maxSubstrLength]);
- }
- // s — исходная строка
- // res - вектор троек (offs, len, ch)
- // histBufMax, prevBufMax - Макс длины буферов истории и предпросмотра
- // функция возвращает список блоков
- void encodeLZ77(string& s, vector<Node>& res, int histBufMax, int prevBufMax)
- {
- int histStart = 0;
- int histEnd = 0;
- int prevStart = 0;
- int prevEnd = prevBufMax;
- while (prevStart < s.length())
- {
- string histBuf = s.substr(histStart, histEnd - histStart);
- string prevBuf = s.substr(prevStart, prevEnd - prevStart);
- Node node = findNewNode(prevBuf, histBuf);
- res.push_back(node);
- histEnd += node.len + 1;
- prevStart += node.len + 1;
- prevEnd += node.len + 1;
- if (histBuf.length() > histBufMax)
- histStart += histBuf.length() - histBufMax;
- }
- }
- int main(int argc, const char* argv[])
- {
- //Здесь предлагается задать размер окна в байтах (отдельно буфера предыстории и предпросмотра)
- //В сумме должны образовывать столько, сколько надо в задании
- //history buffer 3 kb
- int histBufMax = 1024*3;
- //preview buffer 1 kb
- int prevBufMax = 1024;
- ReadWriter rw;
- string s = "";
- rw.readString(s);
- //Основной структурой выбран вектор, так как заранее неизвестно какое количество элементов будет записано
- vector<Node> v;
- encodeLZ77(s, v, histBufMax, prevBufMax);
- rw.writeCode(v);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement