Модификация алгоритма Валианта для задачи поиска подстрок
https://doi.org/10.15514/ISPRAS-2020-32(2)-11
Аннотация
Теория формальных языков активно изучается и находит широкое применение во многих областях. Например, в биоинформатике в задачах распознавания и классификации иногда требуется найти подпоследовательности генетических цепочек, обладающие некоторыми характерными чертами, которые могут быть описаны с помощью грамматики. Задача поиска этих подпоследовательностей сводится к проверке их принадлежности некоторому формальному языку, заданному грамматикой. При этом часто требуется эффективная обработка больших объёмов данных, что приводит к необходимости усовершенствования существующих методов синтаксического анализа. На данный момент среди алгоритмов синтаксического анализа, работающих с произвольной КС-грамматикой, одним из самых быстрых является алгоритм Валианта, основанный на использовании матричных операций. В данной работе предложен алгоритм, который является модификацией алгоритма Валианта. Его основным достоинством является возможность разбиения матрицы разбора на подслои непересекающихся подматриц, которые могут быть обработаны независимо. Доказана корректность и приведена оценка сложности предложенного алгоритма. Проведенные эксперименты показывают, что он сохранил основные преимущества исходного алгоритма, главное из которых – высокая производительность, полученная за счет использования эффективных методов перемножения матриц. Также предложенный алгоритм позволил заметно уменьшить время, затрачиваемое на поиск подстрок, сократив большое количество избыточных вычислений.
При поддержке: Данная работа выполнена при поддержке гранта РНФ 18-11-00100 и JetBrains Research
Об авторах
Юлия Алексеевна СУСАНИНА
Санкт-Петербургский государственный университет
Россия
Студентка магистратуры
Россия
Студентка магистратуры
Анна Никитична ЯВЕЙН
Санкт-Петербургский государственный университет
Россия
Студентка магистратуры
Россия
Студентка магистратуры
Семен Вячеславович ГРИГОРЬЕВ
Санкт-Петербургский государственный университет
Россия
Кандидат физико-математических наук, преподаватель
Россия
Кандидат физико-математических наук, преподаватель
Список литературы
1. Okhotin A. Conjunctive grammars. Journal of Automata, Languages and Combinatorics, vol. 6, no. 4, 2001, pp. 519-535.
2. Chomsky N. On certain formal properties of grammars. Information and control, vol. 2, no. 2, 1959, pp. 137-167.
3. Kasami T. An efficient recognition and syntax analysis algorithm for context-free languages. Technical Report AFCRL-65-758, Air Force Cambridge Research Laboratory, 1965.
4. Younger D.H. Recognition and parsing of context-free languages in time n3. Information and control, vol. 10, no. 2, 1967, pp. 189-208.
5. Valiant L.G. General context-free recognition in less than cubic time. Journal of computer and system sciences, vol. 10, no. 2, 1975, pp. 308-315.
6. Okhotin A. Conjunctive and Boolean grammars: the true general case of the context-free grammars. Computer Science Review, vol. 9, 2013, pp. 27-59.
7. Okhotin A. Boolean grammars. Information and Computation, vol. 194, issue 1, 2004, pp. 19-48.
8. Okhotin A. Parsing by matrix multiplication generalized to Boolean grammars. Theoretical Computer Science, vol. 516, 2014, pp. 101-120.
9. Albrecht M., Bard G. The M4RI Library. The M4RI Team. 2019. Available at: https://bitbucket.org/malb/m4ri, accessed 20.01.2010.
10. Earley J. An effcient context-free parsing algorithm. Communications of the ACM, vol. 13, no. 2, 1970, pp.94-102
11. Bernardy J.P., Claessen K. Effcient divide-and-conquer parsing of practical context-free languages. ACM SIGPLAN Notice, vol. 48, no. 9, 2013, pp.111-122
12. Grigorev S., Lunina P. The Composition of Dense Neural Networks and Formal Grammars for Secondary Structure Analysis. In Proc. of the 12th International Joint Conference on Biomedical Engineering Systems and Technologies, vol. 3, 2019, pp. 234-241.
13. Rivas E., Eddy S.R. The language of RNA: a formal grammar that includes pseudoknots. Bioinformatics, vol. 16, no. 4, 2000, pp. 334-340.
14. Knudsen B. and Hein J. Rna secondary structure prediction using stochastic context-free grammars and evolutionary history. Bioinformatics, vol. 15, no. 6, 1999, pp. 446-454.
15. Dowell R.D., Eddy S.R. Evaluation of several lightweight stochastic context-free grammars for rna secondary structure prediction. BMC bioinformatics, vol. 5, no. 1, 2004, Article number: 71.
16. Durbin R., Eddy S., Krogh A., and Mitchison G. Biological sequence analysis. Cambridge University Press, 1996, 356 p.
17. Hopcroft J.E., Ullman J.D. Formal languages and their relation to automata. Addison-Wesley, 1969, 242 p.
Рецензия
Для цитирования:
СУСАНИНА Ю.А., ЯВЕЙН А.Н., ГРИГОРЬЕВ С.В. Модификация алгоритма Валианта для задачи поиска подстрок. Труды Института системного программирования РАН. 2020;32(2):135-148. https://doi.org/10.15514/ISPRAS-2020-32(2)-11
For citation:
SUSANINA Yu.A., YAVEYN A.N., GRIGOREV S.V. Modification of Valiant’s algorithm for the string-matching problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2020;32(2):135-148. (In Russ.) https://doi.org/10.15514/ISPRAS-2020-32(2)-11
Послать статью по эл. почте 