Способ поиска входной строки в дереве поиска с индексацией узлов дерева поиска Российский патент 2017 года по МПК G06F17/30 

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

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

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

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

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

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

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

Публикация 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Б с помощью утолщенных контурных линий.

На этапе 203 средство построения дерева 291 выполняет индексацию дерева поиска 222, которое после индексации имеет структуру, отображенную на Фиг. 2В. Средство построения дерева 291 присваивает индексы узлам, у которых есть соседние узлы на том же уровне дерева поиска 222 (в общем случае тем узлам, у которых одинаковый родительский узел). Например, это узлы 0 и 1 (родительский узел без индекса - «\REGISTRY\MACHINE\S»); узлы 2, 3 и 4 (родительский узел - 1); узлы 5 и 6 (родительский узел - 4); узлы 7 и 8 (родительский узел без индекса - «*\»); узлы 9,10 и 11 (родительский узел - 8). При этом присвоенный индекс для каждого узла имеет уникальное числовое значение. Индексы узлов дерева поиска 222 указаны в скобках на Фиг. 2В.

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

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

На этапе 204 средство поиска 292 определяет множество индексов узлов, которые будут использованы при поиске входной строки по дереву поиска 222. Для этого по таблице индексации для последнего символа строки, которую надо найти, определяется набор индексов узлов, по которым необходимо выполнить поиск. Так, например, в строке «REGISTRY\MACHINE\SYSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP» последним символом является «Р», поэтому согласно таблице индексации, при поиске необходимо использовать узлы (3), (10) дерева поиска 222. Кроме того, так как дерево поиска 222 содержит произвольный символ в конечном узле, индексы узлов, ведущие к нему, тоже учитываются средством поиска 292, то есть при поиске необходимо также использовать узлы (1), (2), (0), (8), (11). Средство поиска 292 объединяет наборы индексов узлов во множество индексов узлов, в результате чего определяет, что при поиске упомянутой строки среди узлов, в которых есть ветвление (родительский узел имеет более одного дочернего узла), выполнять сравнение нужно только в узлах (3), (10), (1), (2), (0), (8), (11). В одном из вариантов реализации множество индексов узлов может быть по значению индекса.

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

Так, в примере, рассмотренном выше, поиск упомянутой входной строки «REGISTRY\MACHINE\SYSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP» выполняется с использованием узлов (3), (10), (1), (2), (0), (8), (11) дерева поиска 222. Самый верхний узел дерева поиска 222 не имеет индекса, подстрока «\REGISTRY\MACHINE\S», содержащаяся в нем, является частью упомянутой входной строки. Эта часть строки удаляется из входной строки, поиск продолжается для строки «YSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP», с которой сравнивается подстрока «OFTWARE\» узла дерева поиска 222 с индексом (1). Индекс этого узла включен в таблицу индексации, это означает, что в дочерних узлах ветвлений дерева поиска 222 существует подстрока, заканчивающаяся на символ «Р» или содержащая маску. Однако подстрока узла с индексом (1) не является частью строки, для которой продолжается поиск. Поиск не продолжается с использованием дочерних узлов узла с индексом (1), а продолжается с использованием узла с индексом (0), который также входит в определенное ранее множество индексов узлов. Так как строка «YSTEM\CONTROLSET» является частью строки поиска, строка поиска принимает вид «001\ENUM\ROOT\LEGACY_KLP», и поиск продолжается с использованием дочерних узлов узла (0). Дочерний узел только один, не имеет индекса, поэтому выполняется поиск его подстроки в строке поиска. Так как подстрока этого узла имеет вид «*\» (то есть содержит маску), используются упомянутые способы поиска подстроки с использованием масок. Так, в результате такого поиска подстрока «001\» эквивалентна подстроке «*\». Входная строка принимает вид «ENUM\ROOT\LEGACY_KLP», и поиск продолжается. Узел с индексом (7) не входит в определенное ранее множество индексов узлов, поэтому поиск с использованием данного узла не производится. Узел с индексом (8) входит в определенное ранее множество индексов узлов, подстрока «ENUM\ROOT\LEGACY_KL» узла (8) является частью строки. В результате строка для поиска принимает вид «Р». В определенное ранее множество индексов узлов не входит узел (9), но входят узлы (10) и (11), поэтому происходит поиск подстроки узла (10) в строке поиска. Поиск не успешен, далее происходит поиск подстроки узла (11) в строке поиска. Так как подстрока этого узла имеет вид «?» (то есть содержит маску), используются упомянутые способы поиска подстроки с использованием масок. Так, в результате такого поиска подстрока «Р» эквивалентна подстроке «?». Таким образом, упомянутая входная строка найдена средством поиска 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. Следует уточнить, что сетевые соединения являются лишь примерными и не обязаны отображать точную конфигурацию сети, т.е. в действительности существуют иные способы установления соединения техническими средствами связи одного компьютера с другим.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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