Способ обработки информации для обнаружения идентификационных признаков в информационных потоках

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

 

Изобретение относится к области информатики и вычислительной техники и может использоваться для обработки информационных потоков и обнаружения в них заданных эталонных информационных признаков. Способ может быть использован в устройствах контроля информационных потоков с целью мониторинга информационного трафика (Трафик - совокупность сообщений, передаваемых по сети электросвязи (Постановление Правительства РФ от 19 октября 1996 г. N 1254 "Об утверждении Правил присоединения ведомственных и выделенных сетей электросвязи к сети электросвязи общего пользования", п.2).

Известен способ, реализованный в устройстве поиска информации по патенту RU №2133500, кл. G 06 F 17/30, заявленный 20.07.1999 г. Известный способ включает следующую последовательность действий. Предварительно запоминают формат блока данных протокола Frame Relay (G), типы передаваемых служебных сообщений V_n=(a,b,c,i, T391), возможные правила использования команд и ответов Р, возможные состояния пользователей V_t=(S₁, S₂, S₃). Принимают информационный поток, выделяют из него блоки данных, определяют тип передаваемого блока данных и формат блока данных. Сравнивают полученную структуру блока данных с эталонной G. На основании этого совпадения делают вывод об использовании или не использовании протокола FR.

Недостатком данного способа является узкая область его применения, т.к. известный способ может работать только со структурами протокола FR и, как следствие, недостаточное быстродействие при последовательном сравнении в случае использования данного способа в системах с большим числом признаков.

Также известен способ, реализованный в устройстве поиска информации по патенту RU №2116670, кл. 6 G 06 F 17/30, заявл. 27.07.98. Известный способ включает следующую последовательность действий. Предварительно запоминают структуру комбинаций начала сообщений (КНС), пороговые значения количества сообщений (S_пв, S_пн), максимальные значения символьной выборки N_max, принимают информационный поток, выбирают из него некоторую последовательность знаков N<N_max, выделяют в полученной последовательности КНС, суммируют общее количество КНС, сравнивают сумму со значениями S_пв, S_пн, на основании сравнения делают вывод об изменении интенсивности информационного потока.

Недостатком данного способа является то, что заключение об изменении состояния трафика делается только на основании уменьшения или увеличения числа КНС, что не в полной мере отражает картину изменения интенсивности трафика в канале связи.

Наиболее близким по технической сущности является способ, реализованный в устройстве обработки информации для информационного поиска по патенту РФ №2096825, МПК 6 G 06 F 17/00, G 06 F 17/30, заявл. 20.11.1997. Способ-прототип заключается в том, что предварительно формируют базу эталонных информационных значений, подлежащих выявлению в информационном потоке, запоминают их, запоминают количество символов в обрабатываемом текстовом фрагменте (ТФ), запоминают количество символов в словах (словосочетаниях), запоминают количество цифр и специальных символов в ТФ, запоминают предварительно выделенные комбинации символов, соответствующие структурным признакам ТФ, задают правила выделения ТФ из информационного потока.

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

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

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

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

Поставленная цель достигается тем, что в известном способе обработки информации, заключающемся в том, что предварительно формируют базу эталонных информационных признаков (БЭИП), подлежащих выявлению в информационном потоке, принимают информационный поток, последовательно выделяют и запоминают фрагменты принимаемого информационного потока, из которых выделяют по установленным правилам информационные признаки, сравнивают их с эталонными информационными признаками из БЭИП и по результатам сравнения фиксируют наличие или отсутствие в каждом фрагменте информационного потока идентификационных признаков, подлежащих выявлению. Новым в заявленном способе является то, что для формирования БЭИП выбирают совокупность из N≥1 эталонных информационных признаков, выделяют содержащиеся в них и отличающиеся друг от друга символы. Затем из выделенных символов формируют алфавит символов (АС), вычисляют число S содержащихся в нем символов, присваивают j-му, где j=1,2,...,S, символу номер n_j его позиции в алфавите символов и рассчитывают для заданного значения коэффициента заполнения К БЭИП ее объем N_k=N/K. После этого для i-го, где i=1,2,...,N, эталонного информационного признака вычисляют число m_i, образующих его символов и его морфологический коэффициент d_i, а также рассчитывают с использованием хэш-функции заданного вида f(d_i) адрес эталонного информационного признака A_i=f(d_i). Затем запоминают i-й эталонный информационный признак в БЭИП на позиции, соответствующей его адресу A_i. Для выделения из каждого фрагмента принимаемого информационного потока информационных признаков выделяют в нем группу двоичных знаков, находящихся между примыкающими друг к другу двумя пробелами, декодируют ее к виду информационного признака, вычисляют его морфологический коэффициент и адрес. После этого сравнивают выделенный и декодированный информационный признак с эталонными информационными признаками, запомненными по этому адресу в БЭИП.

Для i-го, где i=1,2,...,N, эталонного информационного признака вычисляют его морфологический коэффициент d_i по формуле:

где n_j - номер позиции j-го символа в алфавите символов, m_i - число символов, образующих i-ый признак, S - число символов алфавита символов, j=1,2,..., m_i - позиция символа в i-м признаке.

В качестве хеш-функции для вычисления адреса признака A_i=f(d_i) используют функцию вида

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

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

Результаты поиска известных решений в данной и смежной областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта показали, что они не следуют явным образом из уровня техники. Из уровня техники также выявлена известность влияния предусматриваемых отличительными существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности «изобретательский уровень».

Заявленный способ поясняется чертежами, на которых показаны:

на фиг.1 - пример построения БЭИП;

на фиг.2 - пример цифрового информационного потока, содержащего искомый признак.

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

Пусть для формирования базы эталонных информационных признаков выбраны N признаков, каждый длинной М символов. Иными словами, если на одну итерацию затрачивается время t, то на все итерации будет затрачено: Т=N·М·t. При практически используемых в настоящее время БЭИП в десятки тысяч признаков, указанный выше способ, используемый в аналогах, по своей структуре выполнения алгоритма поиска не может обеспечить требуемую на данный момент скорость поиска необходимых признаков.

Рассмотрение заявленного способа целесообразно провести на следующем примере. Пусть для формирования базы эталонных информационных признаков выбраны N=100 признаков, из которых первые семь имеют значение: банк, железо, маска, машина, рама, самолет, человек, а сотый признак имеет значение 1985-подъем. Из указанных N выбранных признаков выделяют содержащиеся в них и отличные друг от друга символы и формируют «алфавит символов» (АС) с присвоением каждому символу порядкового номера в АС. Будем считать, что в составе всех N признаков содержатся символы, сведенные в таблицу 1. Каждому символу из АС присвоен порядковый номер n_j. Например, символ «ж» имеет номер n=8, символ «9» имеет номер n=24 и т.д.

Таблица 1
nj	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
Наименование символа	пробел	А	Б	В	Г	Д	Е	Ж	3	И	К	Л	М	Н	O	П	Р	С	Т	Ч	Ш	Ъ	1	9	8	5	-

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

Затем вычисляют для заданного значения коэффициента заполнения К БЭИП ее объем N_k=N/K, т.е. число строк в формируемой БЭИП. Значение коэффициента заполнения БЭИП К выбирают лежащим в пределах [0,2-0,5]. При меньших значениях снижается эффективность использования памяти, при больших - возрастают трудности обеспечения неповторяемости адресов признаков в БЭИП (Кнут Д. Искусство программирования. Т.3. Сортировка и поиск. Пер. с англ. - М.: Издательский дом Вильяме, 2003. - 560 с.).

Полагаем, что в рассматриваемом примере K=0,2, соответственно число строк в базе эталонных информационных признаков будет равно:

N_k=100/0,2=500.

Далее для каждого i-го признака вычисляют его морфологический коэффициент d_i. В общем случае он может вычисляться различными способами. При использовании десятичной системы для определения адресной позиции эталонного признака в БЭИП, морфологический коэффициент d_i i-го эталонного признака рассчитывают по формуле (1).

В качестве примера рассмотрим вычисление морфологических коэффициентов признаков «банк» и «1985-подъем».

Для признака «банк»:

D₁=3·27³+2·27²+14·27+11=60896

Для признака «1985-подъем»:

d₁₀₀=23·27¹⁰+24·27⁹+25·27⁸+26·27⁷+27·27⁶+16·27⁵+15·27⁴+6·27³+22·27²+7·27+13=4925853783453586

Аналогичные расчеты, выполненные для рассматриваемых признаков, сведены в таблицу 2:

Таблица 2
№ п/п (i)	Количество символов в признаке (j)	Количество символов в АС (S)	Признак	Морфологический коэффициент (di)
1	4	27	БАНК	60896
2	6	27	ЖЕЛЕЗО	75706179
3	6	27	МАШИНА	188019684
4	7	27	САМОЛЕТ	7009479550
5	6	27	ЧЕЛОВЕК	7855527742
6	5	27	МАСКА	6961520
7	4	27	РАМА	672491
...	...	...	...	...
...	...	...	...	...
100	11	27	1985-ПОДЪЕМ	4925853783453586

Далее с учетом вычисленного значения морфологического коэффициента определяют адрес A_i каждого i-го признака, используя заданную хэш-функцию (формулу (2)), т.е. определяют позицию эталонного признака в БЭИП.

Например, адреса признаков А₁("банк") и А₁₀₀(«1985 - подъем») в БЭИП будут иметь значение:

A₁("банк")=(60896 mod 500)+1=396+1=397;

А₁₀₀("1985-подъем")=(4925853783453586 mod 500)+1=86+1=87.

Аналогичные расчеты, выполненные для рассматриваемых признаков, приведены в таблице на фиг.1.

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

Обработку принимаемого цифрового потока выполняют следующим образом.

Выделяют фрагмент цифрового сигнала, находящегося между примыкающими друг к другу пробелами (фиг.2). Символы пробелов в информационном потоке обозначают в виде двоичных международных кодов «00100», рекомендованных к использованию МККТТ (см. например В.А. Григорьев. Передача сообщений по зарубежным информационным сетям. - Ленинград: ВАС, 1989. - 18-19 с.).

Заключенный между ближайшими пробелами признак декодируют к виду искомого информационного признака, например, выявлен признак «банк». Порядок декодирования известен и описан в литературе, например в книге: В.А.Григорьев. Передача сообщений по зарубежным информационным сетям. - Ленинград: ВАС, 1989. - 14-27 с. Затем, аналогично рассмотренному выше примеру, вычисляют его морфологический коэффициент d_i (по формуле 1) и адрес А_i (по формуле 2), в рассматриваемом случае имеем: d₁=60896, A₁=397. После чего сравнивают его с эталонными информационными признаками, запомненными по этому адресу в базе эталонных информационных признаков. Из БЭИП (см. фиг.1) выделяют находящийся по найденному адресу А₁=397 признак «банк» и сравнивают его с признаком, выделенным из принимаемого цифрового потока (в рассматриваемом примере - признак «банк»). Совпадение сравниваемых признаков дает основание для фиксации присутствия в принимаемом информационном потоке искомого признака.

Таким образом в заявленном способе процесс поиска сводится к выделению из БЭИП признака, находящегося по вычисленному адресу, и последующее сравнение эталонного и выделенного из информационного потока признаков.

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

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

Предположим, что база эталонных информационных признаков (словарь признаков) имеет N=50000 признаков, каждый длиной М=8 знаков. При обнаружении признака поиск ведется сверху вниз, слева направо. Максимальное количество шагов (итераций) при последовательном способе поиска (прототипе) для случая, если признак находится в строке N:

R_max=N·М, →R_max=50000·8=4·10⁵.

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

R_min=N·(М-1)+1, →R_min=50000·(8-1)+1=350001.

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

1. Вычисляют морфологический коэффициент d_i, и адрес A_i i-го признака.

2. Сравнивают с эталонными информационными признаками, запомненными по этому адресу в базе эталонных информационных признаков.

Если на одну итерацию затрачивается время t=Δt, то на все итерации будет затрачено время: Т=N·М·Δt.

Для ближайшего аналога Т_посл=4·10⁵·Δt.

Для заявленного способа Т₃=2·Δt.

Следовательно, относительный выигрыш V по времени, необходимому для поиска признака будет составлять:

Таким образом, из рассмотренной сущности заявленного способа видно, что он обеспечивает сокращение времени идентификации адресов признаков в БЭИП. Этим достигается сформулированная цель - увеличение скорости обработки информации.

1. Способ обработки информации для обнаружения идентификационных признаков в информационных потоках, заключающийся в том, что предварительно формируют базу эталонных информационных признаков, подлежащих выявлению в информационном потоке, принимают информационный поток, последовательно выделяют и запоминают фрагменты принимаемого информационного потока, из которых выделяют информационные признаки, сравнивают их с эталонными информационными признаками из базы эталонных информационных признаков и по результатам сравнения фиксируют наличие или отсутствие в каждом фрагменте информационного потока идентификационных признаков, подлежащих выявлению, отличающийся тем, что для формирования базы эталонных признаков выбирают совокупность из N≥1 эталонных информационных признаков, выделяют содержащиеся в них и отличающиеся друг от друга символы, формируют из них алфавит символов, вычисляют число S содержащихся в нем символов, присваивают j-му, где j=1,2,...,S, символу номер n_j его позиции в алфавите символов и рассчитывают для заданного значения коэффициента заполнения К базы эталонных информационных признаков ее объем N_k=N/K, после чего для i-го, где i=1,2,...,N, эталонного признака вычисляют число m_i образующих его символов, и его морфологический коэффициент d_i, а также рассчитывают с использованием хэш-функции заданного вида f(d_i) адрес эталонного информационного признака A_i=f(d_i), затем запоминают i-й эталонный информационный признак в базе эталонных информационных признаков на позиции, соответствующей его адресу A_i, а для выделения из каждого фрагмента принимаемого информационного потока информационных признаков выделяют в нем группу двоичных знаков, находящихся между примыкающими друг к другу двумя пробелами, декодируют ее к виду информационного признака, вычисляют его морфологический коэффициент и адрес.

2. Способ по п.1, отличающийся тем, что морфологический коэффициент вычисляют по формуле

где n_j - номер позиции j-го символа в алфавите символов;

m_i - число символов, образующих i-й признак;

S - общее число символов в алфавите символов;

j=1,2,...;

m_i - позиция символа в i-м признаке.

3. Способ по п.1, отличающийся тем, что значение коэффициента заполнения базы эталонных информационных признаков выбирают в интервале К=0,2÷0,5.

4. Способ по п.1, отличающийся тем, что при расчете адреса A_i выбирают хеш-функцию вида f(d_i)=([d_i]modN)+1).