Реализация алгоритмов на сжатых текстах

Кулагин Денис, СПбГУИТМО

Руководитель: Юрий Лифшиц

Суть проекта состоит в реализации и анализе алгоритма из статьи [1]. Сперва требуется представить текст в специальной форме – в виде SLP-программы. Т.о. настоящий проект состоит из двух функциональных частей:

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

* Аномалия в последних данных для логов связана со структурой анализируемого файла

Исходные тексты программы и файлы экспериментальных данных

Список литературы

  1. Lifshits Y. Solving Classical String Problems on Compressed Texts [PDF]
  2. Rytter W. Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression [PDF]
  3. Navarro G., Raffinot M. A general Practical Approach To Pattern Matching over Ziv-Lempel Compressed Text [PS]

© Denis Kulagin, 2006