О применении суффиксных деревьев в задаче кластеризации текстовой информации

Секция «Методы и средства зашиты информации»

Основные шаги решения задачи распределения ресурсов

№ Описание

1 Сбор данных о системе

2 Выбор модели зависимостей информационных рисков и ресурсов и ее построение

3 Получение всех возможных решений задачи распределения ресурсов

4 Выбор решения, суммарные затраты на которое минимальны

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

© Панюшкина Л. В., 2014

УДК 004.056

А. Ю. Перевалова Научный руководитель - В. Г. Жуков Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

О ПРИМЕНЕНИИ СУФФИКСНЫХ ДЕРЕВЬЕВ В ЗАДАЧЕ КЛАСТЕРИЗАЦИИ

ТЕКСТОВОЙ ИНФОРМАЦИИ

Для организации электронных документов предлагается организация данных с помощью суффиксных деревьев, построенных по алгоритму Укконена.

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

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

При этом требуется выбрать способ организации классифицируемых данных.

Традиционно выделяют следующие методы организации данных:

- массивы;

- списки;

- графы;

- деревья;

- хэш-таблицы.

Морфологический словарь русского языка содержит около 5 млн словоформ. Поэтому способ организации данных с помощью хэш-таблиц является неэкономным. Также минусом хэш-таблиц являются коллизии.

При организации данных с помощью списков выполняется последовательный поиск путем полного перебора элементов списка - это неэффективно.

Основными способами представления словарей являются представление в виде алфавитно-упорядо-ченного списка либо в виде дерева [1].

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

Одним из перспективных подходов является использование структур данных на основе суффиксных деревьев (далее - СД) [2]. В СД все подстроки исходной строки образованы путем удаления первого символа строки-родителя. Суффикс - это последние (i-k) символов строки, где i - длина строки, k = 1...i. СД позволяет представить строку в виде, удобном при решении поставленной задачи.

Наиболее распространены алгоритмы построения СД Мак-Крейга и Укконена. Оба алгоритма строят СД за линейное время, но алгоритм Укконена строит дерево в режиме online, т.е. после начала работы алгоритма можно увеличивать длину строки.

В программной реализации эффективнее строить СД по буквам, а не по словам. Это обусловлено тем, что количество букв, в отличие от слов, ограничено (для русского языка - 33, для английского - 26).

Разрабатываемый программный модуль построения СД будет осуществлять кластеризацию информационных ресурсов (документов). На вход подаются документы (файлы) в определенном формате, затем они подвергаются отчистке от пунктуации и цифровой информации. Файл - одна большая строка. Далее

Актуальные проблемы авиации и космонавтики - 2014. Информационные технологии

происходит построение СД. Оно строится следующим образом:

1) к корневой вершине последовательно «прицепляются» все суффиксы строки, начиная с самого длинного;

2) если первый символ «прицепляемого» суффикса совпадает с уже существующим символом, происходит расщепление существующего ребра в месте совпадения.

Но одно дерево, построенное алгоритмом Укконе-на по одному файлу не имеет практической пользы для решения поставленной задачи. Качество кластеризации растет пропорционально количеству файлов. Построение СД по множеству файлов возможно двумя путями:

1) построение дерева по каждому файлу, а потом их объединение;

2) последовательное добавление к существующему дереву новых строк-файлов.

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

Для идентификации разных файлов в рамках одного дерева предлагается на каждом ребре (помимо «координат» символов в файле и вершины, в которую следует ребро) дополнительно хранить имя и путь к файлу, из которого взяты эти символы.

СД может быть представлено в виде, требующем О(п) памяти [3], т. е. объем памяти линейно зависит от объема входных данных. Дерево, построенное по

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

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

Таким образом, в данной работе рассмотрен алгоритм построения СД по нескольким файлам и его использование для кластеризации текстовой информации.

Библиографические ссылки

1. Гельбух А. Ф. Эффективно реализуемая модель морфологии флективного естественного языка. М. : Всерос. ин-т науч. и техн. информации, 1994.

2. Андрианов И. А. Построение индексов для расширенного поиска по текстовым полям // Интеллектуальные системы : материалы VI Междунар. симп. Саратов.

3. Moritz Maab Suffix Trees and their Applications // Department of Informatics, Technical University of Munich, 1993.

© Перевалова А. Ю., 2014

УДК 004.056

А. Г. Пятков Научный руководитель - В. В. Золотарев Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Красноярск

ОЦЕНКА НАДЕЖНОСТИ СИСТЕМЫ ЧЕЛОВЕК-МАШИНА

Рассматривается проблема оценки надежности систем человек-машина, предлагается метод для решения этой проблемы.

В наше время структурно-сложные технические системы используются в самых разнообразных отраслях человеческой деятельности (космос, новые технологии, на производстве и др.). Такие системы базируются на средствах вычислительной техники, включают в свой состав сложные измерительные и управляющие комплексы, технологическое оборудования, людей-операторов. Законы функционирования подобных систем не всегда известны, либо имеют вероятностную природу. Поведение систем во многом определяется человеческим фактором, создающим дополнительную неопределенность при попытке его учета. Создаваемые системы во многом уникальны, что не позволяет зачастую в полной мере использовать данные и информацию, полученные на других аналогичных системах. При этом оценить надежность системы человек-машина (СЧМ) необходимо.

СЧМ - система, состоящая из человека-оператора (группы операторов) и машины, посредством которой он (они) осуществляет трудовую деятельность [1]. Машиной в СЧМ называют совокупность технических средств, используемых человеком в своей деятельности. Можно разделить СЧМ по степени участия в работе системы человека (оператора) на автоматические (работающие практически без человека), автоматизированные (работа совместно) и неавтоматизированные (работает преимущественно человек). Однако даже в первых системах влияние человека имеет место ещё на этапах проектирования и создания технических средств. Поскольку поведение оператора имеет вероятностную природу, для оценки надежности СЧМ предлагается использовать логико-вероятностные методы. Однако классические логико-вероятностные методы ограничены (использующие