Тип работы:
 Предмет:
 Язык работы:


Эффективные алгоритмы анализа закономерностей в строках

Работа №104006

Тип работы

Авторефераты (РГБ)

Предмет

математика

Объем работы18
Год сдачи2016
Стоимость2000 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
18
Не подходит работа?

Узнай цену на написание


Общая характеристика работы
Список литературы

Актуальность темы исследования. В теории сложности, теории алгоритмов и вообще компьютерных науках строка — один из центральных объектов. Любая последовательность, будь то последовательность байтов в файле или последовательность слов в тексте, — это строка. Естественно, что такой общий взгляд на природу обрабатываемых данных оправдан не для всех проблем, но круг вопросов, оперирующих столь абстрагированным представлением, по-прежнему очень широк, ведь зачастую закономерности в исходных данных либо слишком сложны для формализации, либо вообще не известны. Алгоритмы, эффективно решающие подобные проблемы, почти всегда явно или неявно решают задачу выделения в строках определённых закономерностей, специфичных для данного конкретного вопроса. В настоящей работе исследуются как закономерности, играющие важную роль в ряде прикладных вопросов, так и закономерности, интересные с теоретической точки зрения и только нащупывающие возможности для применения.
Область, изучающая алгоритмы на строках, ещё в 1985 году получила название стрингология (англ, stringology от string — строка) [7], которое сейчас стало общепринятым. Стрингология уже успела обрасти множеством публикаций, рядом монографий и по меньшей мере двумя ежегодными специализированными конференциями с высоким уровнем цитируемости: SPIRE и СРМ (не говоря о нескольких менее значимых конференциях). Красноречивое свидетельство живого и активного интереса к рассматриваемым вопросам — это список литературы к настоящей диссертации, в котором почти половина работ написана не ранее 2010-го года и в большинстве случаев опубликована в трудах наиболее цитируемых конференций по компьютерным наукам.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

[1] A comparison of index-based Lempel-Ziv LZ77 factorization algorithms / A. Al-Hafeedh, M. Crochemore, L. Ilie et al. // ACM Computing Surveys (CSUR). - 2012. - Vol. 45, no. 1. - P. 5.
[2] Apostolico A., Breslauer D. An optimal O(loglogn)-time parallel algo¬rithm for detecting all squares in a string // SIAM J. on Computing.-
1996. -Vol. 25, no. 6. P. 1318-1331.
[3] Diverse palindromic factorization is NP-complete / H. Bannai, T. Gagie, S. Inenaga et al. // DLT 2015 / Springer International Publishing. — Vol. 9168 of LNCS. - 2015. - P. 85-96.
[4] Belazzougui D., Puglisi S. J. Range predecessor and Lempel-Ziv pars¬ing // arXiv preprint arXiv:1507.07080. — 2015.
[5] Crochemore M., Kolpakov R., Kucherov G. Optimal searching of gapped repeats in a word // arXiv preprint arXiv:1509.01221. - 2015.
[6] A subquadratic algorithm for minimum palindromic factorization / G. Fici, T. Gagie, J. Karkkainen, D. Kempa // J. of Discrete Algo¬rithms. — 2014. — Vol. 28. — P. 41-48.
[7] Galil Z. Open problems in stringology // Combinatorial Algorithms on Words. — Springer, 1985. — P. 1-8.
[8] Galil Z., Seiferas J. A Linear-Time On-Line Recognition Algorithm for “Palstar” // J. of ACM (JACM). - 1978. - Vol. 25, no. 1. P. 102-111.
[9] Faster longest common extension queries in strings over general alpha¬bets / P. Gawrychowski, T. Kociumaka, W. Rytter, T. Walen // arXiv preprint arXiv:1602.00447. — 2016.
[10] Gawrychowski P., Uznamki P. Tight tradeoffs for approximating palin¬dromes in streams // arXiv preprint arXiv:1410.6433. — 2014.
[11] Groult R., Prieur E., Richomme G. Counting distinct palindromes in a word in linear time // Information Processing Letters. — 2010. — Vol. 110.-P. 908-912.
[12] Guo C., Shallit J., Shur A. M. On the combinatorics of palindromes and antipalindromes // arXiv preprint arXiv:1503.09112. — 2015.
[13] Gusfield D. Algorithms on strings, trees and sequences: computer science and computational biology. — Cambridge university press, 1997.
[14] Karkkainen J., Kempa D., Puglisi S. J. Lightweight Lempel-Ziv parsing // SEA 2013. - Vol. 7933 of LNCS. - Springer, 2013. - P. 139-150.
[15] Karkkainen J., Kempa D., Puglisi S. J. Linear time Lempel-Ziv factor¬ization: Simple, fast, small // CPM / Springer. — Vol. 7922 of LNCS.— 2013. -P. 189-200.
[16] Kempa D. Efficient construction of fundamental data structures in large¬scale text indexing : Ph. D. thesis / D. Kempa ; University of Helsinki, Faculty of Science, Department of Computer Science. — 2015.
[17] Kolpakov R., Kucherov G. Finding maximal repetitions in a word in linear time // FOCS 1999. IEEE, 1999. P. 596-604.
[18] Koppl D., Sadakane K. Lempel Ziv computation in compressed space (LZ-CICS) // arXiv preprint arXiv:1510.02882. — 2015.
[19] Lempel A., Ziv J. On the complexity of finite sequences // IEEE Trans¬actions on Information Theory; 1976. Vol. 22, no. 1.— P. 75-81.
[20] Leung H.-F., Peng Z., Ting H.-F. An efficient online algorithm for square detection // Computing and Combinatorics. {{ Springer, 2004. {{ P. 432{ 439.
[21] Lothaire M. Combinatorics on words.-- Cambridge University Press,
1997.
[22] Main M. G. Detecting leftmost maximal periodicities // Discrete Applied Mathematics. {{ 1989. {{ Vol. 25, no. 1. {{ P. 145{153.
[23] Main M. G., Lorentz R. J. Linear time recognition of squarefree strings // Combinatorial Algorithms on Words. — Springer, 1985. — P. 271-278.
[24] Rubinchik M., Shur A. M. Eertree: An efficient data structure for process¬ing palindromes in strings // arXiv preprint arXiv:1506.04862. — 2015.
[25] Shur A. M. Generating square-free words efficiently // Theoretical Com¬puter Science. — 2015. — Vol. 601. — P. 67-72.
Работы автора в изданиях ВАК
[26] Kosolobov D. Faster lightweight Lempel-Ziv parsing // MFCS 2015 / Springer-Verlag Berlin Heidelberg.— Vol. 9235 of LNCS.— 2015.— P. 432-444.
[27] Kosolobov D. Lempel-Ziv factorization may be harder than computing all runs // STACS 2015. — Vol. 30 of LIPIcs. — Schloss Dagstuhl-Leibniz- Zentrum fuer Informatik, 2015. — P. 582-593.
[28] Kosolobov D. Online detection of repetitions with backtracking // CPM 2015 / Springer International Publishing. — Vol. 9133 of LNCS. — 2015. — P. 295-306.
[29] Kosolobov D. Computing runs on a general alphabet // Information Pro¬cessing Letters. — 2016. — Vol. 116, no. 3. — P. 241-244. — Elsevier.
[30] Kosolobov D., Rubinchik M., Shur A. M. Finding distinct subpalindromes online // Proc. Prague stringology conference 2013 / Ed. by Jan Holub, Jan Zdarek. — CTU, 2013.— P. 63-69.
[31] Kosolobov D., Rubinchik M., Shur A. M. Palk is linear recognizable online // SOFSEM 2015. -- Springer-Verlag Berlin Heidelberg, 2015. -¬Vol. 8939 of LNCS. - P. 289-301.

Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ
.