Методы повышения показателей качества фильтрации dlp-систем на основе предметно-ориентированной морфологической модели естественного языка

Алгоритм VF2 
Алгоритм Ульмана 
Лучший случай 
Худший случай 
Таблица 3.1.1. Временная сложность алгоритмов поиска подграфов в графах. 
Из приведенной выше табл. 3.1.1 видно, что временная сложность алгоритма 
поиска подграфов в графе достигает 
.
Как уже упоминалось выше, для построения семантической модели текстов 
естественного языка сейчас, как правило, используются графы. При 
необходимости реализовать поиск в графе (графе семантического описания 
защищаемого документа) подграфа (подграфа передаваемого сообщения) 
прийдется использовать один из обозначенный выше алгоритмов. В таком случае 
в связи с большой временной сложностью этих алгоритмов DLP-система 
столкнется с проблемой производительности уже на небольших документах.
Чтобы показать это рассмотрим документ на русском языке, состоящий из 
двух сраниц шрифта «Times New Roman», размер шрифта 12. По грубой оценке в 
таком документе содержится около 100 предложений, в среднем из семи слов. 
После синтаксического анализа можно ожидать семантический граф 
размерностью порядка 300 узлов. В случае большого количества циклов в графе 
необходимо рассматривать «худший» случай для оценки временной сложности 

---

92 
алгоритма поиска подграфа в графе. В этом случае временная сложность будет 
оцениваться числом 
. 
При использовании современных средств 
вычислительной техники операции такой сложности будут выполняться 
недопустимо долго, что делает невозможным использование алгоритмов поиска 
пографов в графах для идентификации защищаемых данных в передаваемых 
сообщениях. 
Предлагаемый в данной работе метод идентификации защищаемых данных в 
передаваемых сообщениях основан на анализе связей между словами, и не 
предполагает построения дереьев. С точки зрения вычислительной сложности его 
можно описать следующим образом. 
1. Формирование последовательности связей 
мощностью 
, где 
– 
число вершин графа синтаксического описания передаваемого соощения. 
2. Формирование последовательности 
на основе полученного на 
предыдущем шаге множества с учетом синонимов и дополнения нулями.
3. Вычисление функции корреляции (2.5.5.1) для 
. 
∑
, 
где 
| 
|, а
– последовате связей защищаемого документа. 
Оценим временную вычислительную сложность предлагаемого метода.
Вычислительная сложность первого шага 
оценивается слудующим 
образом. 
(3.1.3) 
Вычислительная сложность 
второго шага не зависит от числа вершин 
, 
и является константой. 
(3.1.4) 
Вычислительная сложность 
третьего шага, как видно из (2.5.5.2), линейно 
зависит от 
(3.1.5) 

---

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