Об алгебраических и прикладных аспектах задачи поиска информации

• Автор: Клепинин, Александр Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Екатеринбург
• Количество страниц: 78 с. : ил.

0 Введение

Содержание первой главы

Содержание второй главы

Глава I. О комбинаторных свойствах бесповторных

формальных языков

§1 Основные определения

§2 Последовательность Аршона и ее структурные свойства

§3 Последовательность Аршона и порождение эндоморфизмом

§4 Экспонента избегаемости языка Аршона

§5 Синтаксические конгруэнции бесповторных языков

Глава II. Об интеграции языка БОЬ с языками разработки

кроссплатформенных систем
§6 Обозначения и основные определения
§7 Примеры типичного использования БС^Ь и область применимости модели
§8 БС^Ь запросы и их абстрактное представление
§9 Пакеты запросов и их изоморфизм
ф §10 Менеджер запросов и наполнение пакетов
§11 Технология БСЩ
§12 Интеграция с БСЗЬ]
Заключительные замечания
Литература

В данной работе рассматриваются вопросы, связанные с задачей поиска и обработки информации.
В общем виде эту задачу можно сформулировать следующим образом. Есть некоторый (обычно конечный) набор данных. Требуется выяснить, присутствует ли в этом наборе информация, удовлетворяющая определенным критериям. И если информация присутствует, извлечь ее в удобном для потребителя виде. Легко понять, что в абстрактном алгоритмическом смысле проблемы как таковой нет, поскольку определить за конечное время наличие некоторого объекта в конечном множестве безусловно можно. Но сложность в том, что нужно уметь решать задачу поиска и извлечения информации быстро, чтобы обеспечить адекватное для человека время реакции поисковой системы на введенный запрос.
Какими же способами можно решать эту задачу? По всей видимости, можно выделить два пути.
1. Можно пытаться оптимизировать сам алгоритм поиска, когда за счет грамотного выбора структур данных, за счет использования параллелизма вычислительных систем уменьшается временная сложность алгоритма.
К этому направлению можно отнести, например, хорошо известные автоматные алгоритмы поиска слов в тексте. Эти алгоритмы настолько важны, что фактически выделяются в отдельную область исследования. Так, алгоритмам сортировки и поиска посвящен отдельный том классического трехтомника Дональда Кнута "Искусство программирования" (см. [22]). В более современном учебнике по компьютерной математике "Алгоритмы: построение и анализ" (см. [23]) алгоритмы сортировки и поиска также составляют значительную часть материала.
Но построение эффективных алгоритмов невозможно без исследований на втором пути.
2. Можно пытаться анализировать критерии поиска и свойства множества объектов, в котором поиск производится. И на основании этого анализа из известных теоретических результатов сделать вывод о наличии или отсутствии искомого объекта, сделать вывод о том, как провести поиск более эффективно.
В рамках этого направления следует упомянуть, в частности, результаты теории формальных языков в области избегаемости. Так, например, по виду шаблона можно сразу же сказать, присутствует ли он в текстовой строке или нет.
В данной работе изложены результаты, имеющие непосредственное отношение к обоим названным направлениям.
Отметим, что формальные языки были упомянуты не случайно. Именно в терминах формальных языков удобно описывать задачу поиска. Поэтому изучение свойств формальных языков является важным для решения задачи поиска в целом.
Первая глава данной работы как раз посвящена изучению некоторых комбинаторных свойств формальных языков. В ней исследуются свойства бес-повторных языков, устанавливаются взаимосвязи между комбинаторными свойствами и алгебраическими характеристиками объектов.
Вторая глава работы больше затрагивает алгоритмические вопросы. Но не с точки зрения оптимизации алгоритмов по скорости, а с точки зрения простоты реализации запросов на поиск и извлечение информации при помощи ставшего общепринятым языка запросов В этой главе приводится
модель организации большой и функционально сложной программ, позволяющая легко адаптировать ее под самые разнообразные системы хранения информации и дающая возможность повысить эффективность выполнения запросов 3<ЗЬ, используемых в программе.
Перейдем к более подробному изложению постановок задач и обзору полученных результатов.
Содержание первой главы
Формальные языки, исследованию которых посвящена первая глава данной работы, не случайно привлекают интерес исследователей. Даже если оставить за кадром обычные языки, на которых разговаривают люди в окружающем нас мире, найдется масса важных примеров формальных языков. Приведем лишь некоторые из них.
1. Фрагменты ДНК (цепочки генов) образуют формальный язык, исследования которого чрезвычайно важны для понимания механизмов хранения генетической информации.
2. Информация в компьютерах хранится в виде двоичных слов. Знание свойств таких слов, умение находить повторы или иные регулярности в структуре бинарных последовательностей позволяют эффективно сжимать информацию, снижая нагрузку на каналы связи, увеличивая емкость носителей.
3. Ход любой игры, допускающей лишь конечное множество игровых состояний, может быть представлен в виде слова. Тогда все возможные игровые стратегии, таким способом представленные в виде слов, образуют язык, знание свойств которого позволяет находить выигрышные стратегии, выявлять те или иные свойства игры.
Заметим также, что введенная группировка запросов по функциональности улучшает модульность и добавляет гибкость. А именно, такая группировка позволяет выбирать, какие из пакетов нужны программе для работы. Ненужные пакеты можно просто не загружать в память. Нужные же можно использовать одновременно в нескольких программных модулях.
Так, например, если пишется система, обслуживающая предприятие, в ней могут присутствовать: модуль обслуживания склада, бухгалтерский модуль, модуль для управленческого аппарата. Все эти модули будут взаимодействовать с базой данных. И при разделении пакетов по функциональности мы можем использовать одни и те же пакеты запросов в различных модулях системы, загружая их в зависимости от требующейся функциональности. Так, в нашем примере модуль для управленческого аппарата может пользоваться теми же самыми пакетами запросов, что и модули, обслуживающие бухгалтерию и склад. В то же время модулю обслуживания склада совсем не нужны запросы, относящиеся к бухгалтерскому модулю, и за счет разделения пакетов запросов эта изоляция легко достигается.
Итак, мы описали суть пакетов с точки зрения понятия изоморфизма. Осталось разобраться, что же соответствует пакету запросов с точки зрения программы. Посмотрим на UML-диаграмму, отражающую основные связи класса Package (пакет) с другими классами:
Следует обратить внимание на следующие факты.
1. Принадлежность пакета функциональному модулю удобно кодировать именем пакета.
2. Если есть желание получить доступ к входящим в пакет запросам по именам (а это предпочтительнее, чем обращение к запросам по их индексам в пакете, поскольку избавляет от необходимости исправлять номера запросов в программе при добавлении или удалении запросов в пакете), то имеет смысл для повышения производительности ввести в