РАЗБИЕНИЕ И ОБЪЕДИНЕНИЕ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙ

1. Реализуемый в компьютерной системе, включающей в себя один или более процессоров и системную память, способ представления одного или более регулярных выражений в виде направленного ациклического графа, причем способ содержит этапы, на которых:
осуществляют доступ к одному или более графам ключевых слов, полученных разбиением из первого регулярного выражения, причем каждый из одного или более графов ключевых слов имеет корневой узел, один или более промежуточных узлов и листовой узел, при этом каждый из одного или более промежуточных узлов и листовой узел идентифицируют шаблон символов, который частично совпадает с первым регулярным выражением, при этом корневой узел и каждый из одного или более промежуточных узлов имеют один дочерний узел, и один из промежуточных узлов имеет листовой узел в качестве дочернего узла, причем каждый листовой узел маркируется как находящийся в состоянии совпадения для первого регулярного выражения;
осуществляют доступ ко второму графу, представляющему, по меньшей мере, часть второго регулярного выражения, причем второй граф имеет корневой узел, один или более промежуточных узлов и один или более листовых узлов, при этом каждый из одного или более промежуточных узлов и одного или более листовых узлов идентифицирует шаблон символов, который частично совпадает со вторым регулярным выражением;
объединяют один или более графов ключевых слов и второй граф в направленный ациклический граф, который в совокупности представляет собой как первое регулярное выражение, так и второе регулярное выражение, включая для каждого из одного или более графов ключевых слов подэтапы, на которых:
выбирают по отдельности граф ключевых слов;
идентифицируют любые позиционированные аналогичным образом промежуточные узлы в пределах выбранного графа ключевых слов и второго графа, которые имеют, по меньшей мере, частично перекрывающиеся шаблоны символов; и
для любых идентифицированных промежуточных узлов в выбранном графе ключевых слов и идентифицированных промежуточных узлов во втором графе, которые позиционированы аналогичным образом и имеют частично перекрывающиеся шаблоны символов, объединяют выбранный граф ключевых слов и второй граф в идентифицированных промежуточных узлах для представления эквивалентных состояний совпадения из выбранного графа ключевых слов и второго графа в направленном ациклическом графе, при этом данное объединение обеспечивает то, что граф ключевых слова становится частью второго графа.
2. Способ по п.1, в котором этап идентификации любых позиционированных аналогичным образом промежуточных узлов в пределах выбранного графа ключевых слов и второго графа, которые имеют, по меньшей мере, частично перекрывающиеся шаблоны символов, содержит этап, на котором идентифицируют промежуточный узел в выбранном графе ключевых слов и промежуточный узел во втором графе, которые полностью перекрываются.
3. Способ по п.2, в котором этап объединения выбранного графа ключевых слов и второго графа в идентифицированных промежуточных узлах содержит этап, на котором объединяют промежуточный узел в выбранном графе ключевых слов и промежуточный узел во втором графе в один узел, представляющий полностью перекрывающийся шаблон символов.
4. Способ по п.1, в котором этап идентификации любых позиционированных аналогичным образом промежуточных узлов в пределах выбранного графа ключевых слов и второго графа, которые имеют, по меньшей мере, частично перекрывающиеся шаблоны символов, содержит этап, на котором идентифицируют промежуточный узел в выбранном графе ключевых слов и промежуточный узел во втором графе, которые частично перекрываются.
5. Способ по п.4, в котором этап объединения выбранного графа ключевых слов и второго графа в идентифицированных промежуточных узлах содержит этап, на котором изменяют шаблон символов по меньшей мере одного из идентифицированных промежуточных узлов для устранения частично перекрывающегося шаблона символов.
6. Способ по п.4, в котором этап объединения выбранного графа ключевых слов и второго графа в идентифицированных промежуточных узлах содержит этап, на котором добавляют ребро между выбранным графом ключевых слов и вторым графом для компенсации изменения шаблона символов этого по меньшей мере одного из идентифицированных промежуточных узлов.
7. Компьютерный программный продукт для использования в компьютерной системе, при этом компьютерный программный продукт предназначен для реализации способа представления одного или более регулярных выражений в направленном ациклическом графе, причем компьютерный программный продукт содержит одно или более компьютерных запоминающих устройств, на которых сохранены машиноисполняемые инструкции, которые при их исполнении в процессоре предписывают компьютерной системе выполнять способ, включающий в себя следующие этапы, на которых:
осуществляют доступ к одному или более графам ключевых слов, полученных разбиением из первого регулярного выражения, причем каждый из одного или более графов ключевых слов имеет корневой узел, один или более промежуточных узлов и листовой узел, при этом каждый из одного или более промежуточных узлов и листовой узел идентифицируют шаблон символов, которые частично совпадают с первым регулярным выражением, причем корневой узел и каждый из одного или более промежуточных узлов имеют один дочерний узел, и один из промежуточных узлов имеет листовой узел в качестве дочернего узла, причем каждый листовой узел маркируется как находящийся в состоянии совпадения для первого регулярного выражения;
осуществляют доступ ко второму графу, представляющему второе регулярное выражение, причем второй граф имеет корневой узел, один или более промежуточных узлов и один или более листовых узлов, при этом каждый из одного или более промежуточных узлов и одного или более листовых узлов идентифицирует шаблон символов, который частично совпадает со вторым регулярным выражением;
объединяют один или более графов ключевых слов и второй граф в направленный ациклический граф, который в совокупности представляет как первое регулярное выражение, так и второе регулярное выражение, причем этап объединения включает в себя подэтапы, на которых:
идентифицируют любые позиционированные аналогичным образом промежуточные узлы в пределах одного или более графов ключевых слов и второго графа, которые имеют, по меньшей мере, частично перекрывающиеся шаблоны символов; и
для любых идентифицированных промежуточных узлов в графе ключевых слов и идентифицированных промежуточных узлов во втором графе, которые аналогичным образом позиционированы и имеют частично перекрывающиеся шаблоны символов, объединяют граф ключевых слов и второй граф в идентифицированных промежуточных узлах для представления эквивалентных состояний совпадения, представленных в графе ключевых слов и во втором графе, в направленном ациклическом графе.
8. Компьютерный программный продукт по п.7, дополнительно содержащий машиноисполняемые инструкции, которые при их исполнении предписывают компьютерной системе маркировать листовой узел каждого из одного или более графов ключевых слов как находящийся в состоянии совпадения для первого регулярного выражения.
9. Компьютерный программный продукт по п.7, дополнительно содержащий машиноисполняемые инструкции, которые при их исполнении предписывают компьютерной системе маркировать каждый конечный узел во втором графе как находящийся в состоянии совпадения для второго регулярного выражения.
10. Реализуемый в компьютерной системе, включающей в себя один или более процессоров и системную память, способ представления одного или более регулярных выражений в направленном ациклическом графе, причем способ содержит этапы, на которых:
осуществляют доступ к одному или более графам ключевых слов, полученных разбиением из первого регулярного выражения, причем каждый из одного или более графов ключевых слов имеет корневой узел, один или более промежуточных узлов и листовой узел, при этом каждый из одного или более промежуточных узлов и листовой узел идентифицируют шаблон символов, который частично совпадает с первым регулярным выражением, причем корневой узел и каждый из одного или более промежуточных узлов имеют один дочерний узел, и один из промежуточных узлов имеет листовой узел в качестве дочернего узла, причем каждый листовой узел маркируется как находящийся в состоянии совпадения для первого регулярного выражения;
осуществляют доступ ко второму графу, представляющему второе регулярное выражение, причем второй граф имеет корневой узел, один или более промежуточных узлов и один или более листовых узлов, при этом каждый из одного или более промежуточных узлов и одного или более листовых узлов идентифицирует шаблон символов, который частично совпадает со вторым регулярным выражением, и второй граф имеет один или более конечных узлов, маркированных как находящийся в состоянии совпадения для второго регулярного выражения; и
объединяют один или более графов ключевых слов и второй граф в направленный ациклический граф, который в совокупности представляет собой как первое регулярное выражение, так и второе регулярное выражение, причем этап объединения включает в себя подэтапы, на которых:
идентифицируют любые позиционированные аналогичным образом промежуточные узлы в пределах одного или более графов ключевых слов и второго графа, которые имеют, по меньшей мере, частично перекрывающиеся шаблоны символов; и
для любых идентифицированных промежуточных узлов в графе ключевых слов и идентифицированных промежуточных узлов во втором графе, которые аналогичным образом позиционированы и имеют частично перекрывающиеся шаблоны символов:
изменяют шаблон символов по меньшей мере одного из идентифицированных промежуточных узлов для устранения частично перекрывающегося шаблона символов и добавляют ребро между графом ключевых слов и вторым графом для компенсации изменения шаблона символов этого по меньшей мере одного из идентифицированных промежуточных узлов;
для любых идентифицированных промежуточных узлов в графе ключевых слов и идентифицированных промежуточных узлов во втором графе, которые аналогичным образом позиционируются и имеют полностью перекрывающиеся шаблоны символов:
объединяют вместе граф ключевых слов и второй граф путем объединения промежуточного узла в графе ключевых слов и промежуточного узла во втором графе в один узел, представляющий полностью перекрывающийся шаблон символов.