УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта

Обработка символьных массивов


Автор(ы): Айткулов П. Г.
Название статьи:  Обработка символьных массивов
Выпуск: 28
Год: 2010
Библиография: Айткулов П. Г. Обработка символьных массивов / Управление большими системами. Выпуск 28. М.: ИПУ РАН, 2010. С.126-178.
Дата опубликования: 31.03.2010
Ключевые слова: алгоритмы на строках, суффиксный массив, наибольшая общая подстрока
Аннотация: Суффиксный массив для строки представляет собой структуру данных, которая позволяет искать все вхождения образца за линейное время от длины образца. Построены алгоритмы модификации суффиксного массива при добавлении одного символа, при добавлении блока к исходной строке и удалении блока из строки. Найдено применение построенных алгоритмов к индексации текстовых записей в базах данных и имен файлов в файловой системе. Построен алгоритм поиска наибольшей общей подстроки для k-строк для динамического случая.


Author(s): Ajtkulov P. G.
Article title: Symbol array processing
Issue: 28
Year: 2010
Keywords: string matching, suffix array, longest common substring
Abstract: Suffix array for a string is a data structure, which allows searching all occurrences of the sample in linear time on the sample length. We build the algorithms for modifying a suffix array by adding one character, by adding blocks to the original string, and by removing the block from the string. We suggest applying these algorithms to index text entries in databases and file names in a file system. We also develop the algorithm for online search of the longest common substring in k-strings.


в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 6494; загрузок: 2924, за месяц: 26.

Назад

ИПУ РАН © 2007. Все права защищены