Способ и сервер для поиска точки деления потока данных на основе сервера

Способ и сервер для поиска точки деления потока данных на основе сервера

Иллюстрации

Показать все

Реферат

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

[0001] Настоящее изобретение относится к области информационных технологий и, в частности, к способу и серверу для поиска точки деления потока данных на основе сервера.

УРОВЕНЬ ТЕХНИКИ

[0002] С увеличением объемов данные, критически важной задачей становится обеспечение достаточного хранилища данных в области хранения в настоящее время. В настоящее время, такая задача решается с использованием технологии дедупликации посредством признака избыточности данных, которые необходимо хранить, для уменьшения объем хранимых данных.

[0003] В алгоритме устранения дублированных данных на основании фрагмента, определяемого содержимым (Content Defined Chunk, CDC) в уровне техники, поток данных, подлежащий сохранению, сначала делится на множественные фрагменты данных. Для разделения потока данных на фрагменты данных, необходимо найти подходящую точку деления в потоке данных, и данные между двумя соседними точками деления в потоке данных образуют один фрагмент данных. Вычисляется значение признака фрагмента данных для определения, существуют ли фрагменты данных, имеющие одно и то же значение признака. Если найдены фрагменты данных, имеющие одно и то же значение признака, делается вывод, что дублированные данные существуют. В частности, в технологии устранения дублированных данных на основании фрагмента, определяемого содержимым, применяется метод скользящего окна (Sliding Window Technique) для поиска точки деления фрагмента на основании содержимого файла, то есть рабиновского характерного признака данных в окне вычисляется для определения точки деления потока данных. Предполагается, что поиск точки деления осуществляется слева направо в потоке данных. Характерный признак данных в скользящем окне вычисляется каждый раз, и после осуществления операции по модулю на значении характерного признака на основании данного целого числа k, результат операции по модулю сравнивается с данным остатком R. Если результат операции по модулю равен данному остатку R, правый конец окна является точкой деления потока данных. В противном случае окно продолжает скользить вправо на один байт, и вычисление и сравнение осуществляются последовательно и циклически, пока не будет достигнут конец потока данных. В процессе устранения дублированных данных на основании фрагмента, определяемого содержимым, необходимо расходовать большое количество вычислительных ресурсов для поиска точки деления потока данных, что препятствует повышению производительности устранения дублированных данных.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0004] Согласно первому аспекту, вариант осуществления настоящего изобретения предусматривает способ поиска точки деления потока данных на основе сервера, причем правило заранее задается на сервере, причем правило предусматривает: для точки потенциального деления k, определение M точек px, окна Wx[px-Ax, px+Bx], соответствующего точке px, и заранее заданного условия Cx, соответствующего окну Wx[px-Ax, px+Bx], где x указывает последовательные натуральные числа от 1 до M, M≥2, и Ax и Bx являются целыми числами; и способ включает в себя:

(a) определение точки piz и окна Wiz[piz-Az, piz+Bz], соответствующего точке piz, для текущей точки потенциального деления ki согласно правилу, где i и z являются целыми числами, и 1≤z≤M;

(b) определение, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz; и

когда, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] не удовлетворяет заранее заданному условию Cz, пропуск N минимальных единиц U для поиска точки деления потока данных от точки piz в направлении поиска точки деления потока данных, где N*U не превышает ‖Bz‖+max_x(‖Ax‖+‖(ki-pix)‖), для получения новой точки потенциального деления, и осуществление этапа (a); и

(c) когда, по меньшей мере, часть данных в каждом окне Wix[pix-Ax, pix+Bx] из M окон текущей точки потенциального деления ki удовлетворяет заранее заданному условию Cx, выбор текущей точки потенциального деления ki в качестве точки деления потока данных.

[0005] Согласно первому аспекту, в первом возможном варианте реализации, правило дополнительно предусматривает, что, по меньшей мере, две точки pe и pf удовлетворяют условиям Ae=Af, Be=Bf и Ce=Cf.

[0006] Согласно первому возможному варианту реализации первого аспекта, во втором возможном варианте реализации, правило дополнительно предусматривает, что: относительно точки потенциального деления k, по меньшей мере, две точки pe и pf ориентированы в направлении, противоположном направлению поиска точки деления потока данных.

[0007] Согласно первому возможному варианту реализации или второму возможному варианту реализации первого аспекта, в третьем возможном варианте реализации, правило дополнительно предусматривает, что расстояние между, по меньшей мере, двумя точками pe и pf равно 1 U.

[0008] Согласно первому аспекту, или любому из возможных вариантов реализации с первого по третий первого аспекта, в четвертом возможном варианте реализации, определение, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz, в частности, включает в себя:

определение, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz.

[0009] Согласно четвертому возможному варианту реализации первого аспекта, в пятом возможном варианте реализации, определение, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz, в частности, содержит: определение, с использованием хэш-функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz.

[0010] Согласно первому аспекту, или любому из возможных вариантов реализации с первого по пятый первого аспекта, в шестом возможном варианте реализации, когда, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] не удовлетворяет заранее заданному условию Cz, N минимальных единиц U для поиска точки деления потока данных пропускается от точки piz в направлении поиска точки деления потока данных, для получения новой точки потенциального деления, и, согласно правилу, левая граница окна Wic[pic-Ac, pic+Bc], соответствующая точке pic, которая определена для новой точки потенциального деления, совпадает с правой границей окна Wiz[piz-Az, piz+Bz], или левая граница окна Wic[pic-Ac, pic+Bc], соответствующая точке pic, которая определена для новой точки потенциального деления, попадает в диапазон окна Wiz[piz-Az, piz+Bz], где точка pic, определенная для новой точки потенциального деления, является точкой, занимающей первую позицию в последовательности, которая получена согласно направлению поиска точки деления потока данных, из M точек, которые определены для новой точки потенциального деления согласно правилу.

[0011] Согласно четвертому возможному варианту реализации первого аспекта, в седьмом возможном варианте реализации, определение, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz, в частности, включает в себя:

выбор F байтов в окне Wiz[piz-Az, piz+Bz], и повторное использование F байтов H раз для получения всего F*H байтов, где F≥1, каждый байт образован 8 битами, которые обозначены как am_,1, ..., и am_,8, представляющими биты с 1-го по 8-й m-го байта в F*H байтов, биты, соответствующие F*H байтам можно представить как: , причем, когда am_,n=1, Vam_,n=1, и когда am_,n=0, Vam_,n=-1, где am_,n представляет любой из am_,1, ..., и am_,8, матрица Va получается согласно соотношению преобразования между am_,n и Vam_,n из битов, соответствующих F*H байтам, причем матрица Va представлена как: , F*H*8 случайных чисел выбирается из случайных чисел, подчиняющихся нормальному распределению, для формирования матрицы R, причем матрица R представлена как: , случайные числа в m-й строке матрицы Va и m-й строке матрицы R перемножаются, и произведения суммируются для получения значения, которое, в частности, представляется как Sam=Vam_,1*hm_,1+Vam_,2*hm_,2+...+Vam_,8*hm_,8, Sa₁, Sa₂, ..., и SaF_*H получаются таким же образом, подсчитывается количество k значений, больших 0, из Sa₁, Sa₂, ..., и SaF_*H, и когда k является четным числом, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] удовлетворяет заранее заданному условию Cz.

[0012] Согласно второму аспекту, вариант осуществления настоящего изобретения предусматривает способ поиска точки деления потока данных на основе сервера, причем правило заранее задается на сервере, причем правило предусматривает: для точки потенциального деления k, определение M окон Wx[k-Ax, k+Bx] и заранее заданного условия Cx, соответствующего окну Wx[k-Ax, k+Bx], где x указывает последовательные натуральные числа от 1 до M, M≥2, и Ax и Bx являются целыми числами; и

способ включает в себя:

(a) определение соответствующего окна Wiz[ki-Az, ki+Bz] для текущей точки потенциального деления ki согласно правилу, где i и z являются целыми числами, и 1≤z≤M;

(b) определение, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz; и

когда, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] не удовлетворяет заранее заданному условию Cz, пропуск N минимальных единиц U для поиска точки деления потока данных от текущей точки потенциального деления ki в направлении поиска точки деления потока данных, где N*U не превышает ‖Bz‖+max_x(‖Ax‖), для получения новой точки потенциального деления, и осуществление этапа (a); и

(c) когда, по меньшей мере, часть данных в каждом окне Wix[ki-Ax, ki+Bx] из M окон текущей точки потенциального деления ki удовлетворяет заранее заданному условию Cx, выбор текущей точки потенциального деления ki в качестве точки деления потока данных.

[0013] Согласно второму аспекту, в первом возможном варианте реализации, правило дополнительно предусматривает, что, по меньшей мере, два окна Wie[ki-Ae, ki+Be] и Wif[ki-Af, ki+Bf] удовлетворяют условиям | Ae+Be|=|Af+Bf| и Ce=Cf.

[0014] Согласно первому возможному варианту реализации второго аспекта, во втором возможном варианте реализации, правило дополнительно предусматривает, что Ae и Af являются положительными целыми числами.

[0015] Согласно первому возможному варианту реализации или второму возможному варианту реализации второго аспекта, в третьем возможном варианте реализации, правило дополнительно предусматривает, что Ae-1=Af и Be+1=Bf.

[0016] Согласно второму аспекту, или любому из возможных вариантов реализации с первого по третий второго аспекта, в четвертом возможном варианте реализации, определение, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz, в частности, включает в себя:

определение, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz.

[0017] Согласно четвертому возможному варианту реализации второго аспекта, в пятом возможном варианте реализации, определение, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz, в частности, содержит: определение, с использованием хэш-функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz.

[0018] Согласно второму аспекту, или любому из возможных вариантов реализации с первого по пятый второго аспекта, в шестом возможном варианте реализации, когда, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] не удовлетворяет заранее заданному условию Cz, N минимальных единиц U для поиска точки деления потока данных пропускается от текущей точки потенциального деления ki в направлении поиска точки деления потока данных, для получения новой точки потенциального деления, и, согласно правилу, левая граница окна Wic[ki-Ac, ki+Bc], которая определена для новой точки потенциального деления, совпадает с правой границей окна Wiz[ki-Az, ki+Bz], или левая граница окна Wic[ki-Ac, ki+Bc], которая определена для новой точки потенциального деления, попадает в диапазон окна Wiz[ki-Az, ki+Bz], где окно Wic[ki-Ac, ki+Bc], определенное для новой точки потенциального деления является окном, занимающим первую позицию в последовательности, которая получена согласно направлению поиска точки деления потока данных, из M окон, которые определены для новой точки потенциального деления согласно правилу.

[0019] Согласно четвертому возможному варианту реализации второго аспекта, в седьмом возможном варианте реализации, определение, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz, в частности, включает в себя:

выбор F байтов в окне Wiz[ki-Az, ki+Bz], и повторное использование F байтов H раз для получения всего F*H байтов, где F≥1, каждый байт образован 8 битами, которые обозначены как am_,1, ..., и am_,8, представляющими биты с 1-го по 8-й m-го байта в F*H байтов, биты, соответствующие F*H байтам можно представить как: , причем, когда am_,n=1, Vam_,n=1, и когда am_,n=0, Vam_,n=-1, где am_,n представляет любой из am_,1, ..., и am_,8, матрица Va получается согласно соотношению преобразования между am_,n и Vam_,n из битов, соответствующих F*H байтам, причем матрица Va представлена как: , F*H*8 случайных чисел выбирается из случайных чисел, подчиняющихся нормальному распределению, для формирования матрицы R, причем матрица R представлена как: , случайные числа в m-й строке матрицы Va и m-й строке матрицы R перемножаются, и произведения суммируются для получения значения, которое, в частности, представляется как Sam=Vam_,1*hm_,1+Vam_,2*hm_,2+...+Vam_,8*hm_,8, Sa₁, Sa₂, ..., и SaF_*H получаются таким же образом, подсчитывается количество k значений, больших 0, из Sa₁, Sa₂, ..., и SaF_*H, и когда k является четным числом, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] удовлетворяет заранее заданному условию Cz.

[0020] Согласно третьему аспекту, вариант осуществления настоящего изобретения предусматривает сервер для поиска точки деления потока данных, причем сервер включает в себя центральный процессор и основную память, центральный процессор осуществляет связь с основной памятью, и правило заранее задается на сервере, причем правило предусматривает: для точки потенциального деления k, определение M точек px, окна Wx[px-Ax, px+Bx], соответствующего точке px, и заранее заданного условия Cx, соответствующего окну Wx[px-Ax, px+Bx], где x указывает последовательные натуральные числа от 1 до M, M≥2, и Ax и Bx являются целыми числами; и

основная память выполнена с возможностью хранения исполнимой инструкции, и центральный процессор выполняет исполнимую инструкцию для осуществления следующих этапов:

(a) определения точки piz и окна Wiz[piz-Az, piz+Bz], соответствующего точке piz, для текущей точки потенциального деления ki согласно правилу, где i и z являются целыми числами, и 1≤z≤M;

(b) определения, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz; и

когда, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] не удовлетворяет заранее заданному условию Cz, пропуска N минимальных единиц U для поиска точки деления потока данных от точки piz в направлении поиска точки деления потока данных, где N*U не превышает ‖Bz‖+max_x(‖Ax‖+‖(ki-pix)‖), для получения новой точки потенциального деления, и осуществления этапа (a); и

(c) когда, по меньшей мере, часть данных в каждом окне Wix[pix-Ax, pix+Bx] из M окон текущей точки потенциального деления ki удовлетворяет заранее заданному условию Cx, выбора текущей точки потенциального деления ki в качестве точки деления потока данных.

[0021] Согласно третьему аспекту, в первом возможном варианте реализации, правило дополнительно предусматривает, что, по меньшей мере, две точки pe и pf удовлетворяют условиям Ae=Af, Be=Bf и Ce=Cf.

[0022] Согласно первому возможному варианту реализации третьего аспекта, во втором возможном варианте реализации, правило дополнительно предусматривает, что: относительно точки потенциального деления k, по меньшей мере, две точки pe и pf, ориентированы в направлении, противоположном направлению поиска точки деления потока данных.

[0023] Согласно первому возможному варианту реализации или второму возможному варианту реализации третьего аспекта, в третьем возможном варианте реализации, правило дополнительно предусматривает, что расстояние между, по меньшей мере, двумя точками pe и pf равно 1 U.

[0024] Согласно третьему аспекту, или любому из возможных вариантов реализации с первого по третий, в четвертом возможном варианте реализации, центральный процессор, в частности, выполнен с возможностью:

определения, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz.

[0025] Согласно четвертому возможному варианту реализации третьего аспекта, в пятом возможном варианте реализации, центральный процессор, в частности, выполнен с возможностью определения, с использованием хэш-функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz.

[0026] Согласно третьему аспекту, или любому из возможных вариантов реализации с первого по пятый, в шестом возможном варианте реализации, когда, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] не удовлетворяет заранее заданному условию Cz, N минимальных единиц U для поиска точки деления потока данных пропускается от точки piz в направлении поиска точки деления потока данных, для получения новой точки потенциального деления, и, согласно правилу, левая граница окна Wic[pic-Ac, pic+Bc], соответствующая точке pic, которая определена для новой точки потенциального деления, совпадает с правой границей окна Wiz[piz-Az, piz+Bz], или левая граница окна Wic[pic-Ac, pic+Bc], соответствующая точке pic, которая определена для новой точки потенциального деления, попадает в диапазон окна Wiz[piz-Az, piz+Bz], где точка pic, определенная для новой точки потенциального деления, является точкой, занимающей первую позицию в последовательности, которая получена согласно направлению поиска точки деления потока данных, из M точек, которые определены для новой точки потенциального деления согласно правилу.

[0027] Согласно четвертому возможному варианту реализации третьего аспекта, в седьмом возможном варианте реализации, определение, посредством центрального процессора с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz, в частности, включает в себя:

выбор F байтов в окне Wiz[piz-Az, piz+Bz], и повторное использование F байтов H раз для получения всего F*H байтов, где F≥1, каждый байт образован 8 битами, которые обозначены как am_,1, ..., и am_,8, представляющими биты с 1-го по 8-й m-го байта в F*H байтов, биты, соответствующие F*H байтам можно представить как: , причем, когда am_,n=1, Vam_,n=1, и когда am_,n=0, Vam_,n=-1, где am_,n представляет любой из am_,1, ..., и am_,8, матрица Va получается согласно соотношению преобразования между am_,n и Vam_,n из битов, соответствующих F*H байтам, причем матрица Va представлена как: , F*H*8 случайных чисел выбирается из случайных чисел, подчиняющихся нормальному распределению, для формирования матрицы R, причем матрица R представлена как: , случайные числа в m-й строке матрицы Va и m-й строке матрицы R перемножаются, и произведения суммируются для получения значения, которое, в частности, представляется как Sam=Vam_,1*hm_,1+Vam_,2*hm_,2+...+Vam_,8*hm_,8, Sa₁, Sa₂, ..., и SaF_*H получаются таким же образом, подсчитывается количество k значений, больших 0, из Sa₁, Sa₂, ..., и SaF_*H, и когда k является четным числом, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] удовлетворяет заранее заданному условию Cz.

Согласно четвертому аспекту, вариант осуществления настоящего изобретения предусматривает сервер для поиска точки деления потока данных, причем сервер включает в себя центральный процессор и первичную память, центральный процессор осуществляет связь с первичной памятью, и правило заранее задается на сервере, причем правило предусматривает: для точки потенциального деления k, определение M окон Wx[k-Ax, k+Bx] и заранее заданного условия Cx, соответствующего окну Wx[k-Ax, k+Bx], где x указывает последовательные натуральные числа от 1 до M, M≥2, и Ax и Bx являются целыми числами; и

основная память выполнена с возможностью хранения исполнимой инструкции, и центральный процессор выполняет исполнимую инструкцию для осуществления следующих этапов:

(a) определения соответствующего окна Wiz[ki-Az, ki+Bz] для текущей точки потенциального деления ki согласно правилу, где i и z являются целыми числами, и 1≤z≤M;

(b) определения, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz; и

когда, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] не удовлетворяет заранее заданному условию Cz, пропуска N минимальных единиц U для поиска точки деления потока данных от текущей точки потенциального деления ki в направлении поиска точки деления потока данных, где N*U не превышает ‖Bz‖+max_x(‖Ax‖), для получения новой точки потенциального деления, и осуществление этапа (a); и

(c) когда, по меньшей мере, часть данных в каждом окне Wix[ki-Ax, ki+Bx] из M окон текущей точки потенциального деления ki удовлетворяет заранее заданному условию Cx, выбора текущей точки потенциального деления ki в качестве точки деления потока данных.

[0028] Согласно четвертому аспекту, в первом возможном варианте реализации, правило дополнительно предусматривает, что, по меньшей мере, два окна Wie[ki-Ae, ki+Be] и Wif[ki-Af, ki+Bf] удовлетворяют условиям | Ae+Be|=|Af+Bf| и Ce=Cf.

[0029] Согласно первому возможному варианту реализации четвертого аспекта, во втором возможном варианте реализации, правило дополнительно предусматривает, что Ae и Af являются положительными целыми числами.

[0030] Согласно первому возможному варианту реализации или второму возможному варианту реализации четвертого аспекта, в третьем возможном варианте реализации, правило дополнительно предусматривает, что Ae-1=Af и Be+1=Bf.

[0031] Согласно четвертому аспекту, или любому из возможных вариантов реализации с первого по третий, в четвертом возможном варианте реализации, центральный процессор, в частности, выполнен с возможностью:

определения, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz.

[0032] Согласно четвертому возможному варианту реализации четвертого аспекта, в пятом возможном варианте реализации, центральный процессор, в частности, выполнен с возможностью определения, с использованием хэш-функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz.

[0033] Согласно четвертому аспекту, или любому из возможных вариантов реализации с первого по пятый, в шестом возможном варианте реализации, когда, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] не удовлетворяет заранее заданному условию Cz, N минимальных единиц U для поиска точки деления потока данных пропускается от текущей точки потенциального деления ki в направлении поиска точки деления потока данных, для получения новой точки потенциального деления, и, согласно правилу, левая граница окна Wic[ki-Ac, ki+Bc], которая определена для новой точки потенциального деления, совпадает с правой границей окна Wiz[ki-Az, ki+Bz], или левая граница окна Wic[ki-Ac, ki+Bc], которая определена для новой точки потенциального деления, попадает в диапазон окна Wiz[ki-Az, ki+Bz], где окно Wic[ki-Ac, ki+Bc], определенное для новой точки потенциального деления является окном, занимающим первую позицию в последовательности, которая получена согласно направлению поиска точки деления потока данных, из M окон, которые определены для новой точки потенциального деления согласно правилу.

[0034] Согласно четвертому возможному варианту реализации четвертого аспекта, в седьмом возможном варианте реализации, определение, посредством центрального процессора с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] заранее заданному условию Cz, в частности, включает в себя:

выбор F байтов в окне Wiz[ki-Az, ki+Bz], и повторное использование F байтов H раз для получения всего F*H байтов, где F≥1, каждый байт образован 8 битами, которые обозначены как am_,1, ..., и am_,8, представляющими биты с 1-го по 8-й m-го байта в F*H байтов, биты, соответствующие F*H байтам можно представить как: , причем, когда am_,n=1, Vam_,n=1, и когда am_,n=0, Vam_,n=-1, где am_,n представляет любой из am_,1, ..., и am_,8, матрица Va получается согласно соотношению преобразования между am_,n и Vam_,n из битов, соответствующих F*H байтам, причем матрица Va представлена как: , F*H*8 случайных чисел выбирается из случайных чисел, подчиняющихся нормальному распределению, для формирования матрицы R, причем матрица R представлена как: , случайные числа в m-й строке матрицы Va и m-й строке матрицы R перемножаются, и произведения суммируются для получения значения, которое, в частности, представляется как Sam=Vam_,1*hm_,1+Vam_,2*hm_,2+...+Vam_,8*hm_,8, Sa₁, Sa₂, ..., и SaF_*H получаются таким же образом, подсчитывается количество k значений, больших 0, из Sa₁, Sa₂, ..., и SaF_*H, и когда k является четным числом, по меньшей мере, часть данных в окне Wiz[ki-Az, ki+Bz] удовлетворяет заранее заданному условию Cz.

[0035] Согласно пятому аспекту, вариант осуществления настоящего изобретения предусматривает сервер для поиска точки деления потока данных, причем правило заранее задается на сервере, причем правило предусматривает: для точки потенциального деления k, определение M точек px, окна Wx[px-Ax, px+Bx], соответствующего точке px, и заранее заданного условия Cx, соответствующего окну Wx[px-Ax, px+Bx], где x указывает последовательные натуральные числа от 1 до M, M≥2, и Ax и Bx являются целыми числами; и

сервер включает в себя: блок определения, выполненный с возможностью осуществления этапа (a):

(a) определения точки piz и окна Wiz[piz-Az, piz+Bz], соответствующего точке piz, для текущей точки потенциального деления ki согласно правилу, где i и z являются целыми числами, и 1≤z≤M; и

блок принятия решения и обработки, выполненный с возможностью: определения, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz;

когда, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] не удовлетворяет заранее заданному условию Cz, пропуска N минимальных единиц U для поиска точки деления потока данных от точки piz в направлении поиска точки деления потока данных, где N*U не превышает ‖Bz‖+max_x(‖Ax‖+‖(ki-pix)‖), для получения новой точки потенциального деления, причем блок определения осуществляет этап (a) для новой точки потенциального деления; и

когда, по меньшей мере, часть данных в каждом окне Wix[pix-Ax, pix+Bx] из M окон текущей точки потенциального деления ki удовлетворяет заранее заданному условию Cx, выбора текущей точки потенциального деления ki в качестве точки деления потока данных.

[0036] Согласно пятому аспекту, в первом возможном варианте реализации, правило дополнительно предусматривает, что, по меньшей мере, две точки pe и pf удовлетворяют условиям Ae=Af, Be=Bf и Ce=Cf.

[0037] Согласно первому возможному варианту реализации пятого аспекта, во втором возможном варианте реализации, правило дополнительно предусматривает, что: относительно точки потенциального деления k, по меньшей мере, две точки pe и pf ориентированы в направлении, противоположном направлению поиска точки деления потока данных.

[0038] Согласно первому возможному варианту реализации или второму возможному варианту реализации пятого аспекта, в третьем возможном варианте реализации, правило дополнительно предусматривает, что расстояние между, по меньшей мере, двумя точками pe и pf равно 1 U.

[0039] Согласно пятому аспекту, или любому из возможных вариантов реализации с первого по третий, в четвертом возможном варианте реализации, блок принятия решения и обработки, в частности, определяет, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz.

[0040] Согласно четвертому возможному варианту реализации пятого аспекта, в пятом возможном варианте реализации, блок принятия решения и обработки в частности, выполнен с возможностью определения, с использованием хэш-функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz.

[0041] Согласно пятому аспекту, или любому из возможных вариантов реализации с первого по пятый, в шестом возможном варианте реализации, блок принятия решения и обработки выполнен с возможностью: когда, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] не удовлетворяет заранее заданному условию Cz, пропуска N минимальных единиц U для поиска точки деления потока данных от точки piz в направлении поиска точки деления потока данных, для получения новой точки потенциального деления, причем блок определения осуществляет этап (a) для новой точки потенциального деления, и, согласно правилу, левая граница окна Wic[pic-Ac, pic+Bc], соответствующая точке pic, которая определена для новой точки потенциального деления, совпадает с правой границей окна Wiz[piz-Az, piz+Bz], или левая граница окна Wic[pic-Ac, pic+Bc] попадает в диапазон окна Wiz[piz-Az, piz+Bz], где точка pic, определенная для новой точки потенциального деления, является точкой, занимающей первую позицию в последовательности, которая получена согласно направлению поиска точки деления потока данных, из M точек, которые определены для новой точки потенциального деления согласно правилу.

[0042] Согласно четвертому возможному варианту реализации пятого аспекта, в седьмом возможном варианте реализации, блок принятия решения и обработки в частности, выполнен с возможностью определения, с использованием случайной функции, удовлетворяет ли, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] заранее заданному условию Cz, в частности, которое включает в себя:

выбор F байтов в окне Wiz[piz-Az, piz+Bz], и повторное использование F байтов H раз для получения всего F*H байтов, где F≥1, каждый байт образован 8 битами, которые обозначены как am_,1, ..., и am_,8, представляющими биты с 1-го по 8-й m-го байта в F*H байтов, биты, соответствующие F*H байтам можно представить как: , причем, когда am_,n=1, Vam_,n=1, и когда am_,n=0, Vam_,n=-1, где am_,n представляет любой из am_,1, ..., и am_,8, матрица Va получается согласно соотношению преобразования между am_,n и Vam_,n из битов, соответствующих F*H байтам, причем матрица Va представлена как: , F*H*8 случайных чисел выбирается из случайных чисел, подчиняющихся нормальному распределению, для формирования матрицы R, причем матрица R представлена как: , случайные числа в m-й строке матрицы Va и m-й строке матрицы R перемножаются, и произведения суммируются для получения значения, которое, в частности, представляется как Sam=Vam_,1*hm_,1+Vam_,2*hm_,2+...+Vam_,8*hm_,8, Sa₁, Sa₂, ..., и SaF_*H получаются таким же образом, подсчитывается количество k значений, больших 0, из Sa₁, Sa₂, ..., и SaF_*H, и когда k является четным числом, по меньшей мере, часть данных в окне Wiz[piz-Az, piz+Bz] удовлетворяет заранее заданному условию Cz.

[0043] Согласно шестому аспекту, вариант осуществления настоящего изобретения предусматривает сервер для поиска точки деления потока данных, причем правило заранее задается на сервере, причем правило предусматривает: для точки потенциального деления k, определение M окон Wx[k-Ax, k+Bx] и заранее заданного условия Cx, соответствующего окну Wx[k-Ax, k+Bx], где x указывает последовательные натуральные числа от 1 до M, M≥2, и Ax и Bx являются целыми числами; и

сервер включает в себя: блок определения, выполненный с возможностью осуществления этапа (a):

(a) определения соответствующего окна Wiz[ki-Az, ki+Bz] для текущей точки потенциального деления ki согласно правилу, где i и z являются целыми числами, и 1≤z≤M; и

блок принятия реш