Год выпуска: 2011 Автор: Павел Айткулов Издательство: LAP Lambert Academic Publishing Страниц: 76 ISBN: 9783845426679
Описание
Работа в текстовом редакторе, поисковые запросы в базе данных, задачи в биоинформатике, лексический анализ программ требуют эффективных алгоритмов работы со строками.Задачи поиска образца в тексте используются в криптографии, различных разделах физики, сжатии данных, распознавании речи.Существует два основных подхода в алгоритмах точного поиска образца: преобразование образца и суффиксные структуры данных.В первом подходе образец является статичным, а исходный текст динамичен. Для каждого поискового запроса требуется прочитать исходный текст заново.Если исходный текст является статичным, то стоит воспользоваться суффиксными структурами данных. Поисковый запрос к таким структурам требует линейных от длины образца ресурсов.К недостаткам существующих алгоритмов построения суффиксных структур данных относится то, что для построения структуры требуется вся строка целиком. Это ограничивает использование суффиксных структур данных с потоковыми данными. Далее мы будем устранять этот...
