1313
правок
Усиление степени сжатия текста: различия между версиями
Материал из WEGA
Усиление степени сжатия текста (посмотреть исходный код)
Версия от 03:58, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 42: | Строка 42: | ||
(1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | (1) добавить в концу строки s специальный символ $, который меньше любого другого символа в <math>\Sigma \;</math>; | ||
(2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат | (2) сформировать ''концептуальную'' матрицу <math>\mathcal{M} \;</math>, строки которой содержат циклические сдвиги строки s$, отсортированные в лексикографическом порядке; | ||
(3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1). | (3) построить преобразованный текст <math>\hat{s} = bwt(s) \;</math>, взяв последний столбец матрицы <math>\mathcal{M} \;</math> (см. рис. 1). | ||
| Строка 109: | Строка 109: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Исследование нескольких алгоритмов сжатия, основанных на усилении, и сравнение их с другими современными способами сжатия приведено в работе [4]. Эксперименты показывают, что техника усиления является более надежной по сравнению с другими подходами и хорошо работает даже с менее эффективными алгоритмами сжатия нулевого порядка. Однако положительные результаты достигаются за счет использования большего количества ресурсов (времени и памяти). | Исследование нескольких алгоритмов сжатия, основанных на усилении, и сравнение их с другими современными способами сжатия приведено в работе [4]. Эксперименты показывают, что техника усиления является более надежной по сравнению с другими подходами на базе алгоритма bwt и хорошо работает даже с менее эффективными алгоритмами сжатия нулевого порядка. Однако положительные результаты достигаются за счет использования большего количества ресурсов (времени и памяти). | ||
== Наборы данных == | == Наборы данных == | ||
| Строка 140: | Строка 140: | ||
8. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv.39(1) (2007) | 8. Navarro, G., Makinen, V.: Compressed full text indexes. ACM Comput. Surv.39(1) (2007) | ||
[[Категория: Совместное определение связанных терминов]] | |||
9. Salomon, D.: Data Compression: the Complete Reference, 4th edn. Springer, London (2004) | 9. Salomon, D.: Data Compression: the Complete Reference, 4th edn. Springer, London (2004) | ||
10. Schapire, R.E.: The strength of weak learnability. Mach. Learn. 2,197-227 (1990) | 10. Schapire, R.E.: The strength of weak learnability. Mach. Learn. 2,197-227 (1990) | ||
