Конференции ИВТ СО РАН

VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

27 - 29 ноября 2007 года, Новосибирск

Тезисы докладов

Информационные технологии

Многокритериальный анализ безвозратных алгоритмов поиска символьной информации

Атакищев О.И., Титенко Е.А., Евсюков В.С., Семенихин Е.А.

Курский государственный технический университет (Курск)

В общем виде задачи поиска в теории символьной информации сводятся к выявлению вхождения некоторой последовательности символов (образца) – поисковое слово – в заданную последовательность уже имеющейся информации (текст). В общем случае, и образец и заданный текст состоят из одномерной последовательности символов конечного алфавита, принимаемого заранее. Мощность алфавита меняется в зависимости от потребностей от двух символов, представленных кодами 0 и 1, до всех символов, например, китайского письма, что оказывает существенное влияние на временную сложность поисковых алгоритмов.

В настоящий момент существует обширное множество алгоритмов поиска символьной информации. Большинство из существующих алгоритмов ориентировано на неотступный (безвозвратный) поиск образцов в заданном тексте. Каждый алгоритм эффективен при тех или иных условиях, имеет свою временную зависимость. Но в практической реализации крайне мало алгоритмов ориентировано на параллельную обработку информации. В качестве критериев выбора алгоритмов поиска символьной информации определим их емкостную сложность, минимальное время предобработки входных данных, наличие побитовых операций, параллелизм вычислительных процессов, способность к нечеткому поиску.

Результатом поиска является обнаружение позиции/позиций вхождения образца в заданный текст или выявление отсутствия его вхождения.

Некоторые общеизвестные алгоритмы в той или иной мере возможно реализовать с помощью побитовых операций программно-аппаратным или аппаратным способом. Однако большинство алгоритмов за исключением алгоритма СДВИГ-И, который для поиска использует нуль-единичную матрицу, слабо ориентированы на параллелизм обработки символьной информации.

Вывод: анализ известных безвозвратных алгоритмов поиска показал, что ни один алгоритм поиска не удовлетворяет всей совокупности определенных критериев. Необходим комбинированный алгоритм безвозвратного поиска, совмещающий лучшие характеристики каждого из рассмотренных. Основу такого комбинированного алгоритма составит идея о реконфигурации структуры входной последовательности.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]