ВУЗ:
Составители:
3
Предисловие
Задачи идентификации языков, реализуемые цифровым автоматом-распознавателем,
имеют в настоящее время очень широкое применение. В частности, идентификация цепо-
чек символов входит как составная часть во многие задачи, связанные с редактированием
текстов, поиском данных и символьной обработкой. Многие программы для редактирова-
ния текстов разрешают пользователю задавать типы замен в цепочке - тексте. Например,
пользователю необходимо заменить какое-то слово другим словом во всем тексте или его
части. Чтобы выполнить такое действие, программа редактирования текста должна су-
меть найти вхождение слова и определить его местоположение. Некоторые искусные ре-
дактирующие программы разрешают пользователю в качестве множества заменяемых це-
почек символов указывать регулярное множество [1]. Например, пользователь может по-
ставить задачу: "Заменить [Z*] в тексте W пустой цепочкой", имея в виду, что в W следу-
ет стереть пару квадратных скобок и символы между ними. Антивирусной программе,
для обнаружения "простых" вирусов необходимо найти последовательность байт (сигна-
туру), а при поиске "полиморфных" вирусов обнаружение сигнатуры может входить как
одна из составляющих технологии поиска.
В данном пособии приводятся методы и примеры решения таких задач. При проверке
алгоритмов использовалась система "СОМПА", в разработке которой принимали самое
активное участие студенты Синев С. А. (гр. 95В1), Антонов А. В., Токарев А. Н. (гр.
96ВВ1). Использованы также результаты курсовой работы студента Евдокимова А.С. (гр.
96ВВ3).
1 Задачи идентификации
В типичной задаче идентификации цепочек -образов - задаются входная последова-
тельность W (например, символов или пронумерованные фрагменты графических файлов
и т.п.)) и множество цепочек-образов {z
1
, z
2
, ... z
n
}. Требуется найти либо хотя бы одно
вхождение какой-то цепочки-образа, либо m из n (1
≤
m<n), либо вхождения всех n цепо-
чек-образов в W. При этом множество цепочек-образов часто является регулярным мно-
жеством, которое можно задать регулярным выражением алгебры событий. В главе 1 бу-
дут показаны приемы решения такого рода задач
1.1 Язык регулярных выражений алгебры событий и недетерминированные ко-
нечные автоматы
Поскольку предлагаемое решение таких задач
основано на использовании языка ре-
гулярных выражений алгебры событий (РВАС) и модели недетерминированного конеч-
ного автомата (НДКА), то далее будут приведены основные положения этих теорий, а бо-
лее подробный материал по РВАС и НДКА приведен в [1].
Следуя [1], приведем некоторые понятия и определения. Событие в любом алфавите
Z есть произвольное множество слов в этом алфавите. Элементарными событиями в ал-
фавите Z=[z
1
,z
2
, ... ,z
n
] называются события, состоящие из одной любой буквы алфавита Z,
и событие s=e, где е -пустое слово. Под алгеброй событий в алфавите Z понимается мно-
жество всех событий в этом алфавите, на котором определены две двухместные опера-
ции: сцепление (конкатенация, умножение) и объединение (дизъюнкция), а такжe одна
одноместная операция, называемая итерацией. Сцепление двух
событий s
1
•
s
2
это собы-
тие, состоящее из всех слов вида k
1
•
k
2
, где k
1
любое слово из s
1
, а k
2
любое слово собы-
тия s
2
. При этом s
1
•
s
2
≠ s
2
•
s
1
. В дальнейшем знак cцепления событий. (
•
) для обозначе-
ния этой операции будем опускать. Дизъюнкция двух событий s
1
∨ s
2
это теоретико -
множественное объединение этих событий. Итерация события s , записываемая в виде { s
Предисловие
Задачи идентификации языков, реализуемые цифровым автоматом-распознавателем,
имеют в настоящее время очень широкое применение. В частности, идентификация цепо-
чек символов входит как составная часть во многие задачи, связанные с редактированием
текстов, поиском данных и символьной обработкой. Многие программы для редактирова-
ния текстов разрешают пользователю задавать типы замен в цепочке - тексте. Например,
пользователю необходимо заменить какое-то слово другим словом во всем тексте или его
части. Чтобы выполнить такое действие, программа редактирования текста должна су-
меть найти вхождение слова и определить его местоположение. Некоторые искусные ре-
дактирующие программы разрешают пользователю в качестве множества заменяемых це-
почек символов указывать регулярное множество [1]. Например, пользователь может по-
ставить задачу: "Заменить [Z*] в тексте W пустой цепочкой", имея в виду, что в W следу-
ет стереть пару квадратных скобок и символы между ними. Антивирусной программе,
для обнаружения "простых" вирусов необходимо найти последовательность байт (сигна-
туру), а при поиске "полиморфных" вирусов обнаружение сигнатуры может входить как
одна из составляющих технологии поиска.
В данном пособии приводятся методы и примеры решения таких задач. При проверке
алгоритмов использовалась система "СОМПА", в разработке которой принимали самое
активное участие студенты Синев С. А. (гр. 95В1), Антонов А. В., Токарев А. Н. (гр.
96ВВ1). Использованы также результаты курсовой работы студента Евдокимова А.С. (гр.
96ВВ3).
1 Задачи идентификации
В типичной задаче идентификации цепочек -образов - задаются входная последова-
тельность W (например, символов или пронумерованные фрагменты графических файлов
и т.п.)) и множество цепочек-образов {z1, z2, ... zn}. Требуется найти либо хотя бы одно
вхождение какой-то цепочки-образа, либо m из n (1 ≤ m
