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



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

 


Владельцы патента RU 2620996:

Акционерное общество "Лаборатория Касперского" (RU)

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

 

Область техники

Изобретение относится к решениям для поиска информации по дереву, а более конкретно к способам поиска входной строки в дереве поиска, содержащем маски.

Уровень техники

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

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

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

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

Публикация US 8880507 описывает систему поиска IP-адресов, использующую дерево, в узлах которого содержатся подстроки.

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

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

Сущность изобретения

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

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

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

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

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

Краткое описание чертежей

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

Фиг. 1 изображает пример работы программного обеспечения на компьютере.

Фиг. 2А изображает способ поиска входной строки в дереве поиска, содержащем маски.

Фиг. 2Б отображает структуру дерева поиска.

Фиг. 2В отображает структуру дерева поиска после индексации.

Фиг. 3 представляет пример компьютерной системы общего назначения, на которой может быть реализовано настоящее изобретение.

Описание вариантов осуществления изобретения

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

Фиг. 1 изображает пример работы приложений на вычислительном устройстве.

В общем случае вычислительное устройство работает под управлением операционной системы 110. Приложения 120 обращаются к различным файлам, веткам реестра, путям в локальной сети. Для вычислительных устройств могут быть определены политики безопасности 170, в соответствии с которыми каждое приложение имеет свой определенный набор путей, по которым приложению разрешен доступ. Приложение безопасности (например, антивирусное приложение) 160 может наблюдать за другими приложениями 120 и сравнивать пути, к которым обращаются приложения, а при возникновении нарушений политик безопасности приложениями 120 блокировать доступ этих приложений 120 к ресурсам по неразрешенным политиками путям. В общем случае приложение безопасности 160 выполняет наблюдение за активностью других приложений и блокирует их доступ с использованием перехвата вызовов API-функций. Например, приложение безопасности 160 может перехватывать вызовы API-функций приложением 120, определять параметры перехваченного вызова, которые в свою очередь могут содержать пути, и сравнивать параметры с политиками безопасности 170.

В частном случае количество путей, контролируемых приложением безопасности 160, может быть достаточно большим. Также политики безопасности могут содержать как правила, содержащие только разрешенные пути, так и правила, содержащие запрещенные пути. Пути могут представлять собой:

- локальные пути к файлам и каталогам 130 (в зависимости от типа устройства и операционной системы формат путей может отличаться);

- пути к веткам реестра 140;

- пути в локальной сети 150;

- адреса ресурсов в сети интернет 155;

- пути к определенным сервисам и серверам (например, строка связи с базой данных 165 на SQL-сервере);

- любые другие пути и адреса, которые можно представить в виде форматированной строки.

Пути, разрешенные или запрещенные для приложения, могут быть описаны в базе данных, которую использует приложение безопасности 180. Зачастую множество путей содержит пути из одного каталога, которые могут быть описаны с помощью масок. В общем случае маска - это строка, с помощью которой может быть описано множество похожих строк. В общем случае маски описываются с помощью специальных символов (спецсимволов), например, «?» (маска произвольного одиночного символа) и «*» (маска произвольного числа произвольных символов). Описание с помощью масок сокращает общее количество путей, контролируемых приложением безопасности 160, например, пути «C:\Windows\System\Drivers» и «D:\Windows\System32\Drivers» могут быть описаны с помощью маски «?:\Windows\System*\Drivers». Однако количество контролируемых (разрешенных или запрещенных) путей даже в случае использования масок может быть значительным. При линейном последовательном поиске сравнение пути, к которому обращается приложение, со всеми разрешенными (запрещенными) путями занимает значительное время, так как является последовательным сравнением строк друг с другом. При этом возможно замедление работы как отдельного приложения 120, так и приложения безопасности 160 или операционной системы 110 в целом. При выполнении ресурсоемких задач, например, при математических расчетах или обработке запросов к базе данных, на вычислительном устройстве (например, компьютере или сервере) замедление недопустимо, необходимо решение для быстрого поиска пути, по которому обращается приложение, во множестве разрешенных путей.

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

Фиг. 2А изображает способ поиска пути по дереву поиска, содержащему маски путей.

Тип дерева поиска - не бинарное, каждый узел (англ. node) может иметь более одного потомка или не иметь потомков вообще. Дерево поиска представляет собой дерево, где подстроки, входящие в состав пути, располагаются в узлах дерева 220. Кроме того, в одном из вариантов реализации узлы одного уровня, у которых одинаковый родительский узел, могут быть связаны между собой в виде направленного списка (узел дерева содержит указатель на другой узел).

На начальном этапе 201 средство создания дерева 291 создает словарь символов. Словарь символов содержит символы и спецсимволы, которые могут быть использованы средством создания дерева 291 при создании дерева. Например, в качестве символов используются только английские символы в верхнем регистре. Кроме того, в качестве спецсимволов могут использоваться упомянутые символы «?» и «*». Расположение спецсимволов в строке адреса произвольное, количество спецсимволов не ограничено. В общем случае запрещается использовать комбинации из рядом расположенных спецсимволов (то есть нельзя указать «*?», «?*» или «**»).

В одном из вариантов реализации для каждого символа в словаре средство создания дерева 291 добавляет индекс - числовое значение. Например, элементы словаря, состоящего из английских символов в верхнем регистре, цифр и спецсимволов, имеют индексы от «0» до «36» (26 индексов добавляются для букв алфавита, 10 индексов для цифр, индекс «36» добавляется для спецсимволов).

Пример дерева поиска 220, построенного на этапе 202 средством создания дерева 291 для набора путей:

отображен на Фиг. 2Б.

При построении дерева поиска 220 средство создания дерева 291 сохраняет (помещает) в узлы дерева поиска 220 подстроки (англ. substring), состоящие из символов словаря, при этом каждая строка из набора путей разделяется на подстроки. В общем случае реализации настоящего изобретения из каждой строки из набора путей выделяется и помещается в отдельный узел дерева поиска 220 подстрока, являющаяся префиксом строки из набора путей, содержащая символы до спецсимвола («?» или «*»). В одном из вариантов реализации спецсимвол «?» также помещается в отдельный узел дерева поиска 220. Оставшаяся подстрока (оставшаяся часть строки из набора путей) также (по вышеуказанным правилам) разделяется на подстроки, если содержит другие спецсимволы, в ином случае помещается в отдельный узел дерева поиска 220. В случае, если строка из набора путей содержит подстроку, которая содержится в подстроке одного из узлов дерева поиска 220, подстрока этого узла разделяется на две подстроки, при этом первая подстрока сохраняется в этом узле дерева поиска 220, а вторая - в дочернем. Узел дерева поиска 220, в который помещается последняя подстрока входящей в набор путей строки, является конечным, но может содержать потомков. Конечные узлы дерева поиска 222 отмечены на Фиг. 2Б с помощью утолщенных контурных линий.

При построении дерева поиска средство построения дерева 291 сохраняет в узле дерева индекс пути из набора путей, подстрока которого хранится в этом узле. При этом индекс пути - это в общем случае номер строки в наборе путей, по которому строится дерево поиска. В одном узле может храниться более одного индекса пути. Индексы путей, хранящиеся в узлах дерева поиска 220, указаны на Фиг. 2Б в квадратных скобках. Так, например, узел «\REGISTRY\MACHINE\S» хранит индексы путей с [1] по [9], так как указанная подстрока содержится в каждом пути из набора путей.

На этапе 203 средство построения дерева 291 выполняет индексацию дерева поиска 222, которое после индексации имеет структуру, отображенную на Фиг. 2В. Средство построения дерева с использованием словаря символов строит таблицу индексации. В каждом конечном узле средство построения дерева 291 выбирает последний символ подстроки узла, и в таблице индексации сохраняет индексы путей, которые содержат подстроку, хранящуюся в данном конечном узле.

В результате таблица индексации в одном из вариантов реализации выглядит так (сам символ, набор индексов путей):

На этапе 204 средство поиска 292 определяет множество индексов узлов, которые будут использованы при поиске входной строки по дереву поиска 222. Для этого по таблице индексации для последнего символа строки, которую надо найти, определяется набор индексов путей, по которым необходимо выполнить поиск. Так, например, в строке «REGISTRY\MACHINE\SYSTEM\CONTROLSET001NUM\ROOT\LEGACY_KLP» последним символом является «Р», поэтому согласно таблице индексации при поиске необходимо использовать пути [2], [5] дерева поиска 222. Кроме того, так как дерево поиска 222 содержит произвольный символ в конечном узле, индексы путей, ведущие к нему, тоже учитываются средством поиска 292, то есть при поиске необходимо также использовать пути [3], [4]. Средство поиска 292 объединяет наборы индексов путей во множество индексов путей, в результате чего определяет, что при поиске упомянутой строки выполнять сравнение нужно только в узлах, содержащих подстроки путей [2], [5], [3], [4].

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

Так, в примере, рассмотренном выше, поиск упомянутой входной строки «REGISTRY\MACHINE\SYSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP» выполняется с использованием узлов дерева поиска 222, хранящих индексы путей [2], [5], [3], [4]. Самый верхний узел дерева поиска 222 хранит индексы путей с [1] по [9], подстрока «\REGISTRY\MACHINE\S», содержащаяся в нем, является частью упомянутой входной строки. Эта часть строки удаляется из входной строки, поиск продолжается для строки «YSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP», с которой сравнивается подстрока «OFTWARE\» узла дерева поиска 222, хранящего индексы пути [4], [5], [6], [7], [8]. Индексы пути [4], [5] включены в таблицу индексации, это означает, что в дочерних узлах ветвлений дерева поиска 222 существует подстрока, заканчивающаяся на символ «Р» или содержащая маску. Однако подстрока узла «OFTWARE\» не является частью строки, для которой продолжается поиск. Поиск не продолжается с использованием дочерних узлов данного узла, а продолжается с использованием узла «YSTEM\CONTROLSET», который хранит индексы путей [0], [1], [2], [3], при этом путь [2] также входит в определенное ранее множество индексов путей. Так как строка «YSTEM\CONTROLSET» является частью строки поиска, строка поиска принимает вид «001\ENUM\ROOT\LEGACY_KLP», и поиск продолжается с использованием дочерних узлов данного узла. Дочерний узел только один, содержит среди индексов индексы пути [2], [3], которые включены в таблицу индексации. Так как подстрока этого узла имеет вид «*\» (то есть содержит маску), используются упомянутые способы поиска подстроки с использованием масок. Так, в результате такого поиска подстрока «001\» эквивалентна подстроке «*\». Входная строка принимает вид «ENUM\ROOT\LEGACY_KLP», и поиск продолжается. Узел «SERVICES\KL» не содержит индекс пути, входящий в определенное ранее множество индексов путей, поэтому поиск с использованием данного узла не производится. Узел с индексом «ENUM\ROOT\LEGACY_KL» содержит индексы путей [2], [3], входящие в определенное ранее множество индексов путей, подстрока «ENUM\ROOT\LEGACY_KL» узла является частью строки для поиска. В результате строка для поиска принимает вид «Р». В определенное ранее множество индексов путей узлов не входит узел «IF», но входят узлы «ОР» и «?», поэтому происходит поиск подстроки узла «ОР» в строке поиска. Поиск не успешен, далее происходит поиск подстроки узла «?» в строке поиска. Так как подстрока этого узла имеет вид «?» (то есть содержит маску), используются упомянутые способы поиска подстроки с использованием масок. Так, в результате такого поиска подстрока «Р» эквивалентна подстроке «?». Таким образом, упомянутая входная строка найдена средством поиска 292 в дереве поиска 222, то есть описана подстроками и масками, хранящимися в узлах дерева поиска 222.

Функциональность средства построения дерева 291 и средства поиска 292 может быть реализована исключительно аппаратными средствами, а также в виде комбинации, где часть функциональности реализована программными средствами, а часть - аппаратными. В некоторых вариантах реализации программная часть функциональности упомянутых средств может быть исполнена на процессоре компьютера общего назначения (пример изображен на Фиг. 3).

Фиг. 3 представляет пример компьютерной системы общего назначения, персональный компьютер или сервер 20, содержащий центральный процессор 21, системную память 22 и системную шину 23, которая содержит разные системные компоненты, в том числе память, связанную с центральным процессором 21. Системная шина 23 реализована, как любая известная из уровня техники шинная структура, содержащая в свою очередь память шины или контроллер памяти шины, периферийную шину и локальную шину, которая способна взаимодействовать с любой другой шинной архитектурой. Системная память содержит постоянное запоминающее устройство (ПЗУ) 24, память с произвольным доступом (ОЗУ) 25. Основная система ввода/вывода (BIOS) 26 содержит основные процедуры, которые обеспечивают передачу информации между элементами персонального компьютера 20, например, в момент загрузки операционной системы с использованием ПЗУ 24.

Персональный компьютер 20 в свою очередь содержит жесткий диск 27 для чтения и записи данных, привод магнитных дисков 28 для чтения и записи на сменные магнитные диски 29 и оптический привод 30 для чтения и записи на сменные оптические диски 31, такие как CD-ROM, DVD-ROM и иные оптические носители информации. Жесткий диск 27, привод магнитных дисков 28, оптический привод 30 соединены с системной шиной 23 через интерфейс жесткого диска 32, интерфейс магнитных дисков 33 и интерфейс оптического привода 34 соответственно. Приводы и соответствующие компьютерные носители информации представляют собой энергонезависимые средства хранения компьютерных инструкций, структур данных, программных модулей и прочих данных персонального компьютера 20.

Настоящее описание раскрывает реализацию системы, которая использует жесткий диск 27, сменный магнитный диск 29 и сменный оптический диск 31, но следует понимать, что возможно применение иных типов компьютерных носителей информации 56, которые способны хранить данные в доступной для чтения компьютером форме (твердотельные накопители, флеш карты памяти, цифровые диски, память с произвольным доступом (ОЗУ) и т.п.), которые подключены к системной шине 23 через контроллер 55.

Компьютер 20 имеет файловую систему 36, где хранится записанная операционная система 35, а также дополнительные программные приложения 37, другие программные модули 38 и данные программ 39. Пользователь имеет возможность вводить команды и информацию в персональный компьютер 20 посредством устройств ввода (клавиатуры 40, манипулятора «мышь» 42). Могут использоваться другие устройства ввода (не отображены): микрофон, джойстик, игровая консоль, сканнер и т.п. Подобные устройства ввода по своему обычаю подключают к компьютерной системе 20 через последовательный порт 46, который в свою очередь подсоединен к системной шине, но могут быть подключены иным способом, например, при помощи параллельного порта, игрового порта или универсальной последовательной шины (USB). Монитор 47 или иной тип устройства отображения также подсоединен к системной шине 23 через интерфейс, такой как видеоадаптер 48. В дополнение к монитору 47, персональный компьютер может быть оснащен другими периферийными устройствами вывода (не отображены), например колонками, принтером и т.п.

Персональный компьютер 20 способен работать в сетевом окружении, при этом используется сетевое соединение с другим или несколькими удаленными компьютерами 49. Удаленный компьютер (или компьютеры) 49 являются такими же персональными компьютерами или серверами, которые имеют большинство или все упомянутые элементы, отмеченные ранее при описании существа персонального компьютера 20, представленного на Фиг. 3. В вычислительной сети могут присутствовать также и другие устройства, например маршрутизаторы, сетевые станции, пиринговые устройства или иные сетевые узлы.

Сетевые соединения могут образовывать локальную вычислительную сеть (LAN) 50 и глобальную вычислительную сеть (WAN). Такие сети применяются в корпоративных компьютерных сетях, внутренних сетях компаний и, как правило, имеют доступ к сети Интернет. В LAN- или WAN-сетях персональный компьютер 20 подключен к локальной сети 50 через сетевой адаптер или сетевой интерфейс 51. При использовании сетей персональный компьютер 20 может использовать модем 54 или иные средства обеспечения связи с глобальной вычислительной сетью, такой как Интернет. Модем 54, который является внутренним или внешним устройством, подключен к системной шине 23 посредством последовательного порта 46. Следует уточнить, что сетевые соединения являются лишь примерными и не обязаны отображать точную конфигурацию сети, т.е. в действительности существуют иные способы установления соединения техническими средствами связи одного компьютера с другим.

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

1. Способ поиска входной строки в дереве поиска, в котором:

а) создают словарь символов с помощью средства создания дерева, определяющий множество символов, которое используется при поиске, при этом словарь содержит по меньшей мере:

- символы алфавита;

- маски, которыми являются по меньшей мере символ замены одного символа и символ обобщения, заменяющий произвольное число символов в строке;

б) создают дерево поиска с помощью средства создания дерева, при этом:

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

- в узлах (node) дерева сохраняются подстроки (substring) каждой строки, входящей в набор строк, при этом:

- в отдельный узел дерева поиска сохраняется подстрока, являющаяся префиксом входящей в набор строк строки, содержащая символы до маски;

- узел, в который сохраняется последняя подстрока входящей в набор строк строки, является конечным;

- в узлах дерева сохраняются индексы каждой строки, входящей в набор строк, при этом:

- индексом пути является номер строки в наборе строк;

- в одном узле хранится по меньшей мере один индекс строки;

в) выполняют индексацию дерева поиска с помощью средства создания дерева, создавая таблицу индексации, содержащую символы и набор индексов строк, входящих в набор строк, при этом:

- в таблице индексации используются символы из словаря символов;

- из подстроки, хранящейся в каждом конечном узле, выделяют последний символ, при этом выделенный символ может являться символом алфавита или маской;

- для каждого выделенного последнего символа в таблицу индексации добавляется набор индексов строк, хранящийся в конечном узле;

г) определяют множество индексов строк с помощью средства поиска, которое будет использовано при поиске входной строки по дереву поиска, при этом:

- выделяют последний символ входящей строки, которую необходимо найти в дереве поиска;

- из таблицы индексации выбирают набор индексов строк дерева поиска для поиска упомянутого символа, добавленный на этапе ранее;

- из таблицы индексации выбирают набор индексов строк, добавленный на этапе ранее для масок;

- объединяют выбранные наборы индексов строк во множество индексов строк;

д) выполняют поиск входной строки в дереве поиска с помощью средства поиска, при этом:

- из входящей строки последовательно выделяют подстроку, начиная с первого символа;

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

2. Способ по п. 1, в котором словарь символов дополнительно содержит цифры.

3. Способ по п. 1, в котором словарь символов дополнительно содержит знаки препинания.

4. Способ по п. 1, в котором конечный узел дерева имеет по меньшей мере один дочерний узел.



 

Похожие патенты:

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

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

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

Изобретение относится к способу блокировки доступа к данным на мобильных устройствах с использованием интерфейса программирования приложений, который используется для создания приложений для пользователей с ограниченными возможностями (Accessibility API).

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

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

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

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

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

Изобретение относится к электронной связи. Технический результат – эффективное резюмирование потоков сообщений электронной связи. Cпособ автоматического резюмирования электронного потока сообщений, содержащий этапы, где принимают поток сообщений, состоящий из электронных сообщений, обрабатывают электронные сообщения принятого потока сообщений, чтобы идентифицировать текстовые компоненты, причем текстовые компоненты включают в себя фразы в электронных сообщениях, выбирают по меньшей мере два из электронных сообщений для использования при генерировании резюме потока сообщений, отбрасывают из выбранных электронных сообщений электронные сообщения, являющиеся дубликатами других выбранных электронных сообщений, ранжируют выбранные электронные сообщения на основе критериев ранжирования, обрабатывают текстовые компоненты для идентификации ключевых слов на основе ранжирования выбранных электронных сообщений, генерируют резюме потока сообщений, содержащее часть ключевых слов и текстовых компонентов, при этом ключевые слова и текстовые компоненты выбираются на основе ранжирования выбранных электронных сообщений. 3 н. и 17 з.п. ф-лы, 6 ил.

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

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

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

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

Группа изобретений относится к медицине. Группа изобретений включает в себя способ сбора и анализа данных о запасах грудного молока, энергонезависимые машиночитаемые носители, контейнер для сбора сцеженного грудного молока у матери, способ управления прилегания соска матери внутри грудной чашки, систему для сбора сцеженного грудного молока у матери. Вычислительное устройство получает изображение сцеженного молока в кодифицированном контейнере. Кодификация позволяет программному обеспечению распознавать размер и тип контейнера, а также определять масштаб и ориентацию для того, чтобы преобразовать изображение в точный объем. Данные о молоке затем обрабатывают и анализируют для формирования обратной связи. Группа изобретений позволяет осуществить сбор и анализ данных о запасах грудного молока, а также провести анализ расположения соска матери внутри грудной чашки за счет получения по меньшей мере одного изображения контейнера, включающего в себя связанный с ним кодифицирующий элемент. 6 н. и 45 з.п. ф-лы, 5 ил.

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

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

Изобретение относится к безопасному подключению мобильных устройств к компьютерам. Технический результат - защита данных пользователя при подключении мобильного устройства к компьютеру. Согласно варианту реализации используется способ задания уровня безопасности подключения, в котором: получают по меньшей мере один набор параметров окружения по меньшей мере от одного мобильного устройства; получают от мобильного устройства для каждого набора параметров окружения флаг режима передачи данных; сохраняют в базу данных окружений параметры окружения и соответствующий каждому набору параметров окружения флаг режима передачи данных; задают с помощью средства анализа уровень безопасности для каждого набора параметров окружения в зависимости от параметров окружения и значения флага режима передачи данных в соответствии с правилами задания уровня безопасности. 2 н. и 14 з.п. ф-лы, 5 ил.

Изобретение относится к способам и системам для приближенного сравнения строк в базе данных с добавляемой записью в базу данных, находящуюся в сети обслуживания банковских карт. Техническим результатом является повышение скорости и эффективности получения приблизительного соответствия символьной строки в базе данных, без необходимости вычислять метрику подобия по всей базе данных. В способе сравнения символьных строк для сравнения символьной строки кандидата с множеством записей символьных строк, сохраненных в базе данных, выделяют символьную строку во множестве записей символьных строк для создания набора ссылочных символьных строк посредством факторного анализа основных компонент (PCFA). Генерируют для каждой символьной строки во множестве записей и для символьной строки кандидата двоичный индексный ключ, содержащий несколько бит двоичной информации. Каждый бит показывает степень подобия символьной строки набору ссылочных символьных строк. Определяют набор записей символьных строк, который включает двоичный индексный ключ, точно совпадающий с двоичным индексным ключом символьной строки кандидата. Индексируют запись символьной строки кандидата в базе данных, основанную на совпадении. 2 н. и 16 з.п. ф-лы, 10 ил., 14 табл.
Наверх