Суть проекта состоит в реализации и анализе алгоритма из статьи [1]. Сперва требуется представить текст в специальной форме – в виде SLP-программы. Т.о. настоящий проект состоит из двух функциональных частей:
В свою очередь эта часть разделяется на две:
LZ-факторизация строится по алгоритму LZ77 (с фиксированным размером словаря), подробное описание которого можно найти в [3]. Часть, отвечающая за построение SLP-программы реализована по статье [2].
Построенная объектно-ориентированная модель позволяет с легкостью интегрировать эту функциональную часть в проект.
1. Медиа данные
Размер файла |
LZ-факторов |
SLP-правил |
LZ / Text ratio |
SLP / LZ ratio |
503808 |
372171 |
440238 |
0.739 |
1.183 |
566054 |
409181 |
491869 |
0.723 |
1.202 |
819204 |
558717 |
694860 |
0.682 |
1.244 |
1349903 |
966379 |
1163879 |
0.716 |
1.204 |
2119680 |
1606695 |
1886380 |
0.758 |
1.174 |
2. Исполн. файлы
Размер файла |
LZ-факторов |
SLP-правил |
LZ / Text ratio |
SLP / LZ ratio |
13824 |
2399 |
4946 |
0.174 |
2.062 |
23040 |
7476 |
13382 |
0.324 |
1.790 |
56320 |
18305 |
32917 |
0.325 |
1.798 |
69120 |
29285 |
46023 |
0.424 |
1.572 |
136704 |
40398 |
70997 |
0.296 |
1.757 |
3. Текст
Длина текста |
LZ-факторов |
SLP-правил |
LZ / Text ratio |
SLP / LZ ratio |
11603 |
3773 |
7559 |
0.325 |
2.003 |
34197 |
8947 |
20945 |
0.262 |
2.341 |
76483 |
18125 |
45552 |
0.237 |
2.513 |
114632 |
23490 |
60830 |
0.205 |
2.590 |
167726 |
35522 |
93845 |
0.212 |
2.642 |
216133 |
47407 |
127469 |
0.219 |
2.689 |
308094 |
69895 |
182861 |
0.227 |
2.616 |
509940 |
118062 |
307770 |
0.232 |
2.607 |
686799 |
162719 |
413013 |
0.237 |
2.538 |
1408380 |
329034 |
843592 |
0.234 |
2.564 |
4. Биол. данные
Размер файла |
LZ-факторов |
SLP-правил |
LZ / Text ratio |
SLP / LZ ratio |
1244 |
303 |
774 |
0.244 |
2.554 |
5119 |
1104 |
3144 |
0.216 |
2.848 |
11751 |
1995 |
6206 |
0.170 |
3.111 |
28213 |
4195 |
13896 |
0.149 |
3.313 |
129388 |
19150 |
68046 |
0.148 |
3.553 |
233137 |
36642 |
124541 |
0.157 |
3.399 |
5. Логи
Размер файла |
LZ-факторов |
SLP-правил |
LZ / Text ratio |
SLP / LZ ratio |
33872 |
3491 |
9561 |
0.103 |
2.739 |
267367 |
33151 |
89159 |
0.124 |
2.689 |
768527 |
94224 |
300118 |
0.123 |
3.185 |
1709275 |
250416 |
858526 |
0.147 |
3.428 |
2734372 |
317055 |
800907 |
0.116 |
2.526 |
* Использован алгоритм LZ77, с размером словаря 32K и размером буффера 1K
Эта часть реализована по статье [1]. На входе она получает два текста, представленных в виде SLP-программ – сам текст и некоторый шаблон. На выходе мы получаем информацию, входит ли данный шаблон в текст или нет. (Прим. По данным, вычисленным в программе, можно также узнать все номера позиций вхождений данного шаблона).
По ходу работы алгоритма мы запоминаем кол-во внешних и внутренних вхождений в процедуру локального поиска для последующего анализа глубины вхождений.
1. Текст
Длина текста |
Количество внутренних вхождений |
Количество внешних вхождений |
Глубина вхождений |
Количество расходуемой памяти |
826 |
4842949 |
502661 |
9.635 |
6461 |
1554 |
16287600 |
1505486 |
10.819 |
14958 |
3462 |
77032491 |
6366138 |
12.100 |
44845 |
7229 |
302773433 |
21303940 |
14.212 |
156454 |
2. Биол. данные
Размер файла |
Количество внутренних вхождений |
Количество внешних вхождений |
Глубина вхождений |
Количество расходуемой памяти |
1244 |
737138 |
8656399 |
11.743 |
23259 |
5119 |
12521799 |
170954270 |
13.653 |
328266 |
3. Логи
Размер файла |
Количество внутренних вхождений |
Количество внешних вхождений |
Глубина вхождений |
Количество расходуемой памяти |
2657 |
757388 |
13362111 |
17.642 |
11955 |
6476 |
6739732 |
126701659 |
18.799 |
61713 |
14396 |
27192400 |
538031077 |
19.786 |
497560 |
20371 |
13152294 |
346415809 |
26.339 |
444671 |
* Аномалия в последних данных для логов связана со структурой анализируемого файла
© Denis Kulagin, 2006