Быстрое установление соответствия при адресации по содержанию (контенту)

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

 

Перекрестная ссылка на родственные заявки

Приоритет настоящей заявки основан на родственной предварительной патентной заявке US 61/414327 под названием "Fast matching for content-based addressing" (Быстрое установление соответствия при адресации по содержанию), поданной 16 ноября 2010 г., которая во всей полноте в порядке ссылки включена в настоящую заявку.

Область техники, к которой относится изобретение

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

Предпосылки создания изобретения

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

Краткое изложение сущности изобретения

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

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

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

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

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

на фиг.3 показана блок-схема, иллюстрирующая один из примеров способа построения согласующего дерева согласно настоящему изобретению,

на фиг.4 показана блок-схема, иллюстрирующая один из примеров согласующего дерева согласно настоящему изобретению,

на фиг.5 показана блок-схема, иллюстрирующая один из примеров способа построения согласующего дерева согласно настоящему изобретению,

на фиг.6 показана блок-схема, иллюстрирующая построение одного из примеров согласующего дерева согласно настоящему изобретению,

на фиг.7 показана блок-схема, иллюстрирующая построение одного из примеров согласующего дерева путем добавления другого запроса согласно настоящему изобретению,

на фиг.8 показана блок-схема, иллюстрирующая построение одного из примеров согласующего дерева путем добавления другого запроса согласно настоящему изобретению,

на фиг.9 показана блок-схема, иллюстрирующая построение одного из примеров согласующего дерева путем добавления другого запроса согласно настоящему изобретению,

на фиг.10 показана блок-схема, иллюстрирующая один из примеров способа установления соответствия сообщения согласующему дереву согласно настоящему изобретению,

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

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

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

Подробное описание

На фиг.1 показана блок-схема одного из примеров системы 100 эффективного установления соответствия при адресации по содержанию. В систему 100 может входить машина-отправитель 101 и машина-получатель 103. В одном из вариантов осуществления в систему 100 может входить сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений. В одном из вариантов осуществления в систему 100 может дополнительно входить сервер 109 форматов. Хотя на фиг.1 показан сервер 107 промежуточного программного обеспечения, в одном из вариантов осуществления в систему 100 может не входить сервер 107 промежуточного программного обеспечения, при этом машина-отправитель 101 может поддерживать связи непосредственно с машиной-получателем 103, а сервер 109 форматов может поддерживать связи непосредственно как с машиной-отправителем 101, так и с машиной-получателем 103.

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

Машина-отправитель 101 может содержать приложение 132, генерирующее сообщения с определенным содержанием для передачи серверу 107 промежуточного программного обеспечения, ориентированного на обработку сообщений. Сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, может оценивать адресацию по содержанию, чтобы определять, следует ли передавать сообщение машине-получателю 103. Приложение 132 может содержать механизм 134 обработки сообщений для обработки данных адресации по содержанию, содержания, полей и сведений о форматировании для передачи сообщения машине-получателю 103. Приложение 132 также может содержать интерфейс 130 прикладного программирования (API) в качестве средства сопряжения сервера 107 промежуточного программного обеспечения, ориентированного на обработку сообщений.

Хотя на фиг.1 проиллюстрирована одна машина-отправитель 101, в систему 100 может входить несколько машин-отправителей 101, поддерживающих связь с сервером 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, или с машиной-получателем 103. В некоторых вариантах осуществления показанная на фиг.1 машина-отправитель 101 может принимать и обрабатывать запросы.

Машина-получатель 103 может содержать приложение 133, генерирующее запросы для передачи серверу 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, с целью сравнения с сообщениями, переданными машиной-отправителем 101. Запросом может являться запрос, исходящий от приложения 133, такой как, например, запрос на возврат всех сообщений с адресацией по содержанию, которые содержат поле A со значением 1 и поле B со значением 4. Приложение 133 может дополнительно содержать механизм 135 обработки запросов для обработки информации о запросе, данных, полей и сведений о форматировании для заданного запроса или набора запросов. С использованием ограничений формата входящих сообщений и запросов может быть построена древовидная структура из запросов, а затем эффективным способом согласована с поступающими данными. Механизм 135 обработки запросов в любое время может добавлять или удалять запросы. Чтобы отражать это, древовидная структура может быть модифицирована, а входящее сообщение может согласовываться с модифицированной древовидной структурой. Механизм 135 обработки запросов может быть сконфигурирован на построение древовидной согласующей структуры, как подробнее описано со ссылкой на фиг.6-9. Механизм 135 обработки запросов также может быть сконфигурирован на поиск согласующих узлов поля в согласующем дереве, как подробнее описано со ссылкой на фиг.10. Приложение 133 также может содержать интерфейс 131 прикладного программирования (API) в качестве средства сопряжения сервера 107 промежуточного программного обеспечения, ориентированного на обработку сообщений.

Хотя на фиг.1 проиллюстрирована одна машина-получатель 103, в систему 100 может входить несколько машин-получателей 103, поддерживающих связь с сервером 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, или с машиной-получателем 103. В некоторых вариантах осуществления показанная на фиг.1 машина-получатель 103 может принимать и обрабатывать запросы.

Машина-отправитель 101 и машина-получатель 103 могут поддерживать связь с сервером 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, посредством сети 140. В одном из вариантов осуществления сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, также могут поддерживать связь с сервером 109 форматов по сети 140. Так, в одном из вариантов осуществления машина-отправитель 101 и машина-получатель 103 поддерживают связь с сервером 109 форматов посредством сервера 107 промежуточного программного обеспечения, ориентированного на обработку сообщений. Сервер 109 форматов может передавать информацию о формате машине-отправителю 101 и машине-получателю 103 и может содержать механизм 112 форматирования информации о формате. Информация о формате включает без ограничения сведения о форматировании для типов данных адресации по содержанию, операндов, полей, информации о формировании запросов и т.д. и служит для улучшения высокоэффективного обмена сообщениями в системе 100. Сервер 109 форматов может задавать формат для каждого из полей каждого узла поля, как подробнее описано со ссылкой на фиг.4, и может форматировать каждый узел поля согласно этому формату.

Сервер 109 форматов также может поддерживать связь с хранилищем 111 данных по сети 140. Сервер 109 форматов может осуществлять доступ к данным, информации о формате, установкам ограничений данных и оператора, информации о формировании запросов и т.д. из хранилища 111 данных. Хранилище 111 данных также может содержать библиотеку форматов для хранения информации о формате сообщений. В одном из вариантов осуществления машина-администратор 105 может поддерживать связь с сервером 109 форматов, позволяющим администратору взаимодействовать с системой 100 по сети 140.

В одном из вариантов осуществления машина-отправитель 101 и машина-получатель 103 могут поддерживать связь посредством связи между равноправными устройствами (Р2Р) по сети 140. В конфигурации Р2Р машина-отправитель 101 может содержать маршрутизатор обработки запросов, который находится в машине-отправителе 101. Хотя показаны только одна машина-отправитель 101 и одна машина-получатель 103, в систему 100 может входить любое число машин-отправителей 101 и любое число машин-получателей 103, поддерживающих связь Р2Р непосредственно друг с другом по сети 140. Множество машин-отправителей 101 может поддерживать связь с множеством машин-получателей 103.

Сеть 140 может представлять собой любую форму сети связи для поддержания связи с коммутацией каналов, коммутацией пакетов и/или связи любого другого применимого типа между машиной-отправителем 101, машиной-получателем 103, сервером 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, сервером 109 форматов и любыми другими элементами на фиг.1. Сеть 140 может дополнительно содержать любые другие узлы системы 100, способные передавать и/или принимать информацию по сети связи. Хотя сеть 140 показана на фиг.1 как единый элемент, она может содержать одну или несколько отдельных сетей (включающих целиком или частично несколько различных сетей), которые разделены и обслуживают различные соответствующие элементы, проиллюстрированные на фиг.1. Сеть 140 может содержать маршрутизаторы, концентраторы, коммутаторы, брандмауэры, коммутаторы содержания, шлюзы, контроллеры вызовов и/или любые другие применимые компоненты в любой применимой форме или компоновке. Сеть 140 может содержать целиком или частично одну или несколько защищенных и/или зашифрованных виртуальных частных сетей (ВЧС), способных связывать друг с другом один или несколько сетевых элементов путем взаимодействия или поддержания связи посредством элементов сети связи общего пользования или внешней сети связи. Обычно сеть 140 может содержать любое сочетание аппаратуры связи общего пользования или частной аппаратуры связи, такой как элементы коммутируемой телефонной сети общего пользования (PSTN), всемирной вычислительной сети, такой как сеть Интернет, локальной вычислительной сети (ЛВС), глобальной вычислительной сети (ГВС) или другой соответствующей аппаратуры связи. В некоторых вариантах осуществления сеть 140 может не использоваться, если все компоненты находятся в одной и той же машине.

В систему 100 может входить машина-отправитель 101, машина-получатель 103, сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, и сервер 109 форматов, при этом каждое из перечисленного может представлять собой любое применимое вычислительное устройство, содержащее процессор и память для обеспечения описанных функциональных возможностей. Машина-отправитель 101, машина-получатель 103, сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, и сервер 109 форматов могут представлять собой одну или несколько машин, рабочих станций, портативных компьютеров, серверных модулей, групп серверов и/или автономных серверов. Машина-отправитель 101, машина-получатель 103, сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений и сервер 109 форматов могут содержать любое аппаратное обеспечение и/или управляющую логику для обмена информацией с одним или несколькими элементами, проиллюстрированными на фиг.1. Например, машина-отправитель 101, машина-получатель 103, сервер 107 промежуточного программного обеспечения, ориентированного на обработку сообщений, и сервер 109 форматов могут быть способны принимать и обрабатывать данные различных типов, которые могут передаваться посредством различных протоколов или форматов. Другие элементы, проиллюстрированные на фиг.1, также могут содержать аппаратное обеспечение и/или управляющую логику для обмена информацией с одним или несколькими элементами, проиллюстрированными на фиг.1.

В памяти может храниться любая применимая информация. Память может представлять собой любой набор и компоновку энергозависимых и/или энергонезависимых компонентов, применимых для хранения данных. Например, память может представлять собой запоминающие устройство с произвольной выборкой (ЗУПВ), постоянные запоминающие устройства (ПЗУ), магнитные запоминающие устройства, оптические запоминающие устройства и/или любые другие применимые запоминающие устройства для хранения данных. В частных вариантах осуществления память частично может представлять собой машиночитаемые запоминающие среды, в которых закодированы компьютерные команды и/или логика. Память может содержать число компонентов, находящихся в процессоре, вблизи процессора и/или доступных для процессора. Процессор может представлять собой и/или содержать любую форму компонента обработки, включая компьютеры общего назначения, выделенные микропроцессоры или другие устройства обработки, способные обрабатывать электронную информацию. Примеры процессора включают процессоры цифровой обработки сигналов (ЦОС), специализированные интегральные микросхемы (ASIC), программируемые пользователем вентильные матрицы (FPGA) и любые другие применимые процессоры специального или общего назначения.

Быстрое установление соответствия при адресации по содержанию

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

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

На фиг.2 показана высокоуровневая блок-схема, иллюстрирующая один из примеров способа 200 быстрого эффективного установления соответствия при адресации по содержанию. Шаги, представленные на фиг.2, могут выполняться машиной-получателем 103, более точно, приложением 133 или механизмом 135 обработки запросов в машине-получателе 103 или любым другим компонентом системы, выбранным для выполнения функций механизма 135 обработки запросов, таким как сервер 107 промежуточного программного обеспечения или машина-отправитель 101.

В процессе работы на шаге 202 механизм 135 обработки запросов посредством API 131 может принимать запрос от приложения 133. Запрос может содержать одно или несколько полей и одно или несколько значений, при этом одно или несколько полей связаны с операндом, отображающим категорию содержания, а одно или несколько значений связаны с содержанием.

С целью эффективного установления соответствия при адресации по содержанию система 100 может налагать ограничения на запросы, инициируемые машиной-получателем 103, чтобы обеспечить надлежащее форматирование запросов. Например, на данные и запросы налагаются следующие ограничения: (1) полями данных могут являться только целые числа или строки; (2) в запросах может использоваться только строгое равенство (например, "Тикер=TIBX"); (3) в запросах может использоваться только конъюнкция (например, "Тикер=TIBX и Значение=32"); и (4) поля могут использоваться максимально один раз в информационном сообщении. В этом варианте осуществления может подразумеваться дизъюнкция за счет использования набора запросов.

На шаге 204 система 100 может генерировать в машине-получателе 103 древовидную структуру, упорядоченную одним или несколькими полями запроса, при этом древовидная структура содержит один или несколько узлов дерева, а один или несколько узлов дерева содержат один или несколько узлов запроса. На шаге 206 машина-получатель 103 может принимать и анализировать сообщение машины-отправителя 101. Сообщение может содержать одно или несколько полей содержания, связанных с одним или несколькими значениями содержания. На шаге 208 машина-получатель 103 может осуществлять поиск в древовидной структуре с использованием одного или нескольких полей содержания сообщения.

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

На фиг.3 показана блок-схема, иллюстрирующая один из примеров способа 300 построения согласующего дерева на основе запроса, поступившего от машины-получателя 103. На шаге 301 запрос может быть упорядочен любым путем (например, канонического упорядочения) путем сортировки операндов каждого запроса в определенном согласованном порядке на основании имен полей. Так, на шаге 301 запрос, записанный как А=1 и С=3 и В=4, может быть переписан в порядке А=1 и В=4 и С=3. Сортировка каждого запроса путем канонического упорядочения позволяет осуществлять поиск полей в одном и том же порядке и тем самым повышать производительность стадии установления соответствия способа (например, способа 200 на фиг.2) за счет выделения одного пути в дереве для каждого конкретного установления соответствия.

С целью построения дерева запросы могут обрабатываться по одному за один раз с созданием узлов дерева, содержащих один или несколько узлов поля, каждый из которых связан с одним или несколькими значениями. На шаге 303 анализируется первый запрос (например, А=1). На шаге 305 осуществляется построение линейного 1-арного дерева для первого запроса, при этом каждый узел дерева может отображать один операнд запроса (и, соответственно, содержит узел поля), а на шаге 307 узел поля располагаются таким образом, что первый операнд является корнем, последний операнд является листом, а промежуточные операнды следуют от первого до последнего операндов (от корня к листу).

На фиг.4 показана блок-схема, иллюстрирующая один из примеров согласующего дерева 400 для канонически упорядоченного запроса А=1 и В=4 и С=3. Как описано выше, в каждом узле дерева для первого запроса содержится отдельный операнд запроса и один узел поля. Как показано на фиг.4, самый верхний узел 405 дерева иллюстрирует операнд А=1. Узел 405 дерева содержит узел 407 поля, обозначенный ‘А’ со значением, равным 1. Узел 411 дерева содержит узел 413 поля, обозначенный ‘В’ со значением 415, равным 4. Узел 417 дерева содержит узел 419 поля, обозначенный ‘С’ со значением 421, равным 3.

В одном из вариантов осуществления, если узел дерева содержит запросы А=1, А=2 и В=3, в этом узле дерева могут присутствовать логически раздельные узел поля для А и В. Узел поля запроса А может содержать два вводимых значения 1 и 2, а узел поля запроса В может содержать один значимый элемент, равный 3. Каждый значимый элемент узла поля запроса (1, 2 и 3 в этом примере) имеет ребро, указывающее узел-потомок дерева.

Как показано на фиг.4, узлы поля, представленные пунктирными линиями, могут содержать один или несколько узлов поля, если к дереву добавляются другие запросы. Узлы поля, представленные сплошной линией и содержащие упорядоченный операнд (т.е. А, B, C и т.д.), также могут содержать несколько значений для каждого имени поля. Узел поля в сочетании со значением может образовывать узел запроса (т.е. А и 1, когда запросом является А=1). Чтобы добавить другой запрос к дереву, операнды нового запроса подвергаются итерации, при этом максимально долго могут повторно использоваться существующие узел поля (путем добавления новых вводимых значений по мере необходимости). Когда узел дерева не содержит согласующий узел поля, может быть добавлен новый узел поля, чтобы продолжить построение нового поддерева. Каждый узел запроса содержит логически раздельные элементы для имени поля и значения, а ребра могут соединять значимый элемент узла запроса с листом (потомком) узла дерева.

На фиг.5 показана блок-схема, иллюстрирующая один из примеров способа 500 построения согласующего дерева в механизме 135 обработки запросов. На шаге 501 определяют текущий запрос, начиная с первого запроса из набора запросов. Так, при первой итерации способа 500 текущим запросом является первый запрос. На шаге 503 выполняют итерацию способа с использованием операндов текущего запроса с целью построения узлов дерева для текущего запроса. На шаге 505 механизм 135 обработки запросов определяет, существует ли для текущего запроса согласующий узел поля. Если это так, существующий узел поля может повторно использоваться на шаге 507. (Примечание: когда первый запрос является текущим запросом, решение на шаге 505 не может являться отрицательным, и, соответственно, на шаге 509 может быть добавлен новый узел поля.)

Если на шаге 505 установлено, что для текущего запроса не существует согласующий узел поля, на шаге 509 добавляется новый узел поля, и на шаге 511 строится новое поддерево на основании нового узла поля. Если на шаге 505 установлено, что для текущего запроса существует согласующий узел поля, на шаге 513 текущим запросом выбирается следующий запрос из набора запросов, и способ снова начинается с шага 501.

Как показано на следующих фигурах и лишь в качестве примера, обрабатывается набор из четырех запросов А=1 и В=4 и С=3; А=2 и С=3; А=1 и С=6; и В=7 и Е=2, а построение дерева осуществляется на четырех стадиях механизмом 135 обработки запросов. Дерево строится с использованием по одному запросу за один раз (пошагово), начиная с первого запроса А=1 и В=4 и С=3 в соответствии с заинтересованностью, выраженной машиной-получателем 103.

На фиг.6 показана блок-схема, иллюстрирующая первую стадию построения примера согласующего дерева 600. Как описано выше со ссылкой на фиг.3 и 4, для первого запрос строится линейное 1-арное дерево 600, в котором каждый узел 601, 603, 605 дерева отображает один операнд запроса и, соответственно, содержит один узел 602, 604, 606 поля каждый со значением 607, 608, 609. Узлы дерева расположены таким образом, чтобы первый операнд (А=1) является корневым узлом 601 дерева, последний операнд (С=3) является концевым узлом 605 дерева, а промежуточный операнд (В=4) является срединным узлом 603 дерева. Каждый узел 601, 603, 605 дерева содержит отдельный операнд запроса и один узел 602, 604, 606 полей для первого запроса. Соответственно, самый верхний узел дерева отображает операнд А=1, срединный узел дерева отображает операнд В=4, а самый нижний узел дерева отображает операнд С=3, при этом каждый операнд связан с узлом запроса.

На фиг.7 показана блок-схема, иллюстрирующая вторую стадию построения одного из примеров согласующего дерева 700 на основании примера согласующего дерева 600. Как показано на фиг.5 и 7, на шаге 501 определяют текущий запрос, которым является второй запрос (А=2 и C=3). На шаге 503 выполняют итерацию способа с использованием операндов второго запроса. На шаге 505 определяют, что для первого операнда второго запроса (А=2) существует согласующий узел поля. Соответственно, существующий узел 602 поля (для A=1 из первого запроса) может использоваться повторно, и на шаге 507 добавляют новый значимый элемент 702 (для A=2 из второго запроса). Существующий узел поля для A=1 (узел 601) может использоваться повторно для второго запроса, но поле значений разделено и содержит как значение 607 для A=1, так и значение 702 для A=2. Новое значение 702 поля становится корнем новой ветви дерева. Следующий операнд запроса (С=3) вводят в новую ветвь, в результате чего образуется новый узел 703 дерева, содержащий операнд C=3 узла 705 поля и значение 707. (В одном из вариантов осуществления операнд C не использует повторно узел 605 дерева C, который является потомком узла 603 дерева B из первого запроса, поскольку это дерево, а не ориентированный ациклический граф (DAG)).

На фиг.8 показана блок-схема, иллюстрирующая построение третьей стадии одного из примеров согласующего дерева 800 на основе примеров согласующих деревьев 600, 700. Как показано на фиг.5 и 8, на шаге 501 определяется текущий запрос, который является третий запрос (А=1 и C=6). На шаге 503 выполняют итерацию способа с использованием операндов третьего запроса. На шаге 505 определяют, что для первого операнда третьего запроса (А=1) существует согласующий узел поля. Соответственно, существующий узел 602 поля (для A=1 из первого запроса) может использоваться повторно для третьего запроса. Новые значимые элементы не добавляются, поскольку первый операнд третьего запроса также имеет значение A=1. Осуществление способа переходит к следующему узлу 603 дерева в ветви первого запроса. В этом узел 603 дерева добавляется новый узел 801 поля для отображения второго операнда третьего запроса (С=6), поскольку узел 604 поля (В=4) не согласуется с новым узлом 801 поля (С=6). Узел 603 дерева, который указывает A=1, может использоваться повторно для третьего запроса, но существующий узел B 604 поля не используется повторно и, соответственно, в узле 603 дерева создается новый узел C 801 поля со значением 803.

На фиг.9 показана блок-схема, иллюстрирующая дополнительную четвертую стадию построения примера согласующего дерева 900 на основании примеров согласующих деревьев 600, 700, 800. Как показано на фиг.5 и 9, на шаге 501 определяют текущий запрос, которым является четвертый запрос (В=7 и E=2). На шаге 503 выполняют итерацию способа с использованием операндов четвертого запроса. На шаге 505 определяют, что в четвертом запросе (В=7) отсутствует согласующий узел поля для первого операнда. Соответственно, на шаге 509 добавляют новый узел 901 поля со значением 903, и на шаге 511 строят новое поддерево на основе нового узла 901 поля. Таким образом, корневой узел 601 дерева может использоваться повторно, но поскольку ни один из узлов поля в корневом узле 601 дерева не является узлом поля, в корневом узле 601 дерева создается новый узел 901 поля, и начинается построение новой ветви дерева. В первый новый узел 905 дерева новой ветви дерева добавляют следующий операнд (Е=2) с узлом 907 поля и значением 909. Добавления могут продолжаться, пока в дерево не будут встроены все запросы.

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

В некоторых вариантах осуществления узлы согласующего дерева могут пополняться дополнительными данными с целью повышения производительности стадии установления соответствия. Пополнение может осуществляться в момент создания согласующего дерева. Узел дерева может содержать список полей в узлах поля, хэш-список концевых узлов (узлов-потомков) узла дерева, в котором каждый узел-потомок может быть представлен в виде комбинации имени его поля и значения поля, и список запросов, которые оканчиваются в этом узле дерева. За счет хранения этой информации в каждом узле дерева в процессе установления соответствия быстро определяется, соответствуют ли поступающие данные запросу, закодированному в дереве, и оптимизируется определение того, соответствует ли согласующее дерево поступающим данным, или соответствуют ли поступающие данные согласующему дереву. Возвращаясь к фиг.1, оптимальная стратегия зависит от размера и/или высоты дерева и длины поступающих данных и может оперативно выбираться последовательно для каждого узла по мере представления данных для установления соответствия механизмом 134 обработки запросов приложения 132. За счет списка запросов, которые оканчиваются в узле дерева, дерево может отображать запрос, который может являться префиксом другого запроса. Например, в дереве, проиллюстрированном на фиг.9, запрос А=1 и В=4 и С=3 может быть отображен в дереве посредством корня 915, помеченного как концевой запрос, помимо его роли в более длинном запросе.

Установление соответствия с деревом

В некоторых вариантах осуществления после того, как механизм 135 обработки запросов построил согласующее дерево на основании запроса машины-получателя 103, механизм 135 обработки запросов может согласовать входящее информационное сообщение с запросом, если какой-либо поднабор полей и значений в сообщении согласуется со всем и полями и значениями в запросе. Так, сообщение "А=1 и B=4 и F=9" соответствует запросу "А=1 и В=4," а сообщение "А=1 и В=4" не соответствует запросу "A=1 и B=4 и G=12", поскольку в сообщении имеется не согласующий узел ‘G=12’ запроса.

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

На фиг.10 показана блок-схема, иллюстрирующая один из примеров способа 1000 установления соответствия сообщения с согласующим деревом. На шаге 1001 сортируют поля сообщения путем канонического упорядочения. Способ 1000 предусматривает итерацию с использованием полей сообщения, прохождение дерева от его корневого узла и, поскольку частичные совпадения сообщения считаются соответствием, способ 1000 является несколько более сложным, чем однократное прохождение сообщения.

Способ 1000 предусматривает рекурсивное прохождение дерева в попытке найти согласующий узел поля в каждом узле дерева. Так, на шаге 1003 может осуществляться поиск согласующего узла поля в согласующем дереве для поля текущего сообщения (при первой итерации текущим полем сообщения является поле первого сообщения). Если на шаге 1005 найден согласующий узел поля, на шаге 1007 может быть продолжен рекурсивный поиск в узле-потомке. На шаге 1007 осуществляется попытка установления соответствия остающихся полей данных сообщения. Если на шаге 1009 не согласованы остающиеся поля данных сообщения, на шаге 1013 может быть задано поле нового текущего сообщения, и способ может быть снова начат с шага 1003. Если на шаге 1009 согласованы остающиеся поля данных сообщения, на шаге 101 может быть обнаружено соответствие.

Если на шаге 1005 не найден согласующий узел, текущее поле сообщения не дает совпадения, и способ 1000 может быть повторен с использованием поля нового сообщения путем определения поля нового текущего сообщения на шаге 1013 и снова начат с шага 1003. Если не найден согласующий узел поля, поиск может быть продолжен путем исключения поля текущего сообщения и использования конца сообщения, поскольку запрос может совпадать с поднабором полей в сообщении (не требуется соответствие всех полей).

На фиг.11 показана блок-схема, иллюстрирующая пример псевдокода 1100 для установления соответствия сообщения согласующему дереву. Применительно к фиг.11 передача параметров осуществляется по значению, а рекурсивный вызов команды findmatch() (поиска соответствия) не изменяет значение сообщения на уровне вызова, но могут использоваться другие разновидности. Установление соответствия может быть инициировано путем использования команды findmatch (корневого узла, сообщения), а получение результата "истина" указывает, что сообщение соответствует по меньшей мере одному из запросов, закодированных в дереве.

Одним из вариантов осуществления, в котором недостаточно простого псевдокода команды findmatch(), является случай, когда один запрос представляет собой префикс другого запроса. Древовидная структура данных может быть дополнена с целью маркировки внутренних узлов дерева, которыми оканчивается запрос. Например, добавление к согласующему дереву 900 на фиг.9 запроса A=1 и B=4, который является префиксом существующего запроса A=1 и B=4 и C=3, не вызовет каких-либо изменений структуры согласующего дерева 900, но узел второго уровня, отображающий B=4, должен быть маркирован как окончание запроса даже при том, что он не является концевым узлом (листом).

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

На фиг.12 показана блок-схема, иллюстрирующая пример псевдокода 1200 для определения окончания с внутренней маркировкой в способе установления соответствия согласующему дереву согласно настоящему изобретению. Этот псевдокод может сочетаться с псевдокодом на фиг.11 и позволяет обнаруживать соответствие на шаге 1011 способа 1000 (на фиг.10), когда на шаге 1009 найдено соответствие конечного узла или окончания запроса.

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

На фиг.13 показана блок-схема, иллюстрирующая способ 1300 установления соответствия между согласующим деревом и сообщением в машине-получателе 103. Способ 1300 начинается на шаге 1301 с корня дерева и на шаге 1302 определяется, могут ли последовательные узел поля в узле дерева иметь соответствие в сообщении. Если на шаге 1302 найдено соответствие, на шаге 1304 может быть осуществлена рекурсивная проверка этого узла поля. Если на шаге 1302 не найдено соответствие, на шаге 1310 может выполняться итерация с использованием следующего узла поля в узле дерева, способ может быть снова начат с шага 1302. Как и в предыдущем способе установления соответствия, на шаге 1308 обнаруживается соответствие, если установлено, что на шаге 1306 концевой узел или окончание имеет соответствие. Если на шаге 1306 не найдено соответствие концевого узла или окончания запроса, на шаге 1310 может выполняться итерация с использованием следующего узла поля в узле дерева, способ может быть снова начат с шага 1302.

В одном из вариантов осуществления может быть оптимизировано время установления соответствия узла поля запросу, когда узлу поля соответствует множество значений, как в случае узла A 602 поля на фиг.9, которому соответствуют значения 607, 702, равные 1 и 2, соответственно. С целью повышения эффективности имя узла 602 поля может быть сопоставлено с запросом, и при наличии соответствия с узлом поля может быть сопоставлено имя поля и/или сочетание значений сообщения. В других вариантах осуществления это последнее сопоставление может быть усовершенствовано за счет хэширования структур данных. Когда узлам поля соответствует множество значений, процесс может значительно ускоряться по сравнению с простым сравнением каждого имени поля/значения узла поля и сообщения.

Тот или иной из описанных способов установления соответствия может с более высокой эффективностью применяться в зависимости от числа узлов поля в узле дерева и числа пар поле-значение в сообщении (или любом остающемся его конце). Может применяться гибридный способ оценки остатка на каждом уровне рекурсии и использоваться более эффективное сравнение. Возвращаясь к фиг.1, механизм 135 это решение последовательно для каждого узла может принимать обработки запросов приложения 133 машины-получателя 103 во время оценки соответствия сообщений. В качестве альтернативы, решение может передаваться по сети 140 и выполняться последовательно для каждого узла во время оценки соответствия сообщений.

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

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

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

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

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

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

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

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

Помимо этого, содержащиеся в описании заголовки разделов приведены в соответствии с рекомендациями статьи 1.77 Раздела 37 Свода федеральных нормативных актов США или для облегчения поиска информации. Эти заголовки не ограничивают и не описывают изобретение (-я), заявленное в каком-либо из пунктов формулы изобретения, который может вытекать из раскрытия. В частности и в качестве примера, хотя в описании содержится раздел под заголовком "Область техники, к которой относится изобретение", формула изобретения не должна быть ограничена содержанием этого раздела, в котором описана так называемая область техники. Кроме того, описание технологии в разделе "Предпосылки создании изобретения" не должно считаться признанием того, что определенная технология является прототипом какого-либо изобретения (-й), раскрытого в настоящем описании. Раздел "Краткое изложение сущности изобретения" также не должен рассматриваться в качестве описания изобретения (-й), заявленного в формуле изобретения. Помимо этого, любое упоминание в настоящем описании "изобретения" в единственном числе не должно использоваться для доказательства того, что в настоящем описании раскрыт лишь один обладающий новизной объект. Раскрытыми во множестве пунктов формулы изобретения признаками, вытекающими из настоящего описания, может быть охарактеризовано множество изобретений и соответственно в таких пунктах формулы изобретения заявлены охраняемые ими изобретение (-я) и его эквиваленты. Во всех случаях объем таких пунктов формулы изобретения рассматривается согласно их существу в свете настоящего описания и не должен быть ограничен приведенными в описании заголовками разделов.

1. Способ эффективного установления соответствия при адресации по содержанию, содержащий:

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

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

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

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

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

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

2. Способ по п.1, дополнительно включающий:

передачу второго запроса и

помещение второго запроса в древовидную структуру на основании порядка следования одного или нескольких полей второго запроса.

3. Способ по п.1, дополнительно включающий:

передачу второго запроса с таким же полем, как и поле первого запроса, и значением, отличающимся от значения первого запроса, и

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

4. Способ по п.1, дополнительно включающий:

передачу второго запроса с полем, отличающимся от поля первого запроса, и

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

5. Способ по п.1, в котором древовидная структура конструируется путем сортировки запросов машины-получателя путем канонического упорядочения на основании поля каждого запроса.

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

7. Способ по п.1, в котором полем является тикер, а значением является конкретный тикерный символ.

8. Способ по п.1, в котором запросом является "Тикер=TIBX".

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

10. Система эффективного установления соответствия при адресации по содержанию, содержащая:

машину-получателя, сконфигурированную на:

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

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

анализ сообщения машины-отправителя, содержащего поле содержания, связанное со значением содержания,

поиск в древовидной структуре с использованием поля содержание сообщения,

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

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

11. Система по п.10, в которой машина-получатель дополнительно сконфигурирована на:

передачу второго запроса и

помещение второго запроса в древовидную структуру на основании порядка следования одного или нескольких полей второго запроса.

12. Система по п.10, в которой машина-получатель дополнительно сконфигурирована на:

передачу второго запроса с таким же полем, как и поле первого запроса, и значением, отличающимся от значения первого запроса, и

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

13. Система по п.10, в которой машина-получатель дополнительно сконфигурирована на:

передачу второго запроса с полем, отличающимся от поля первого запроса, и

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

14. Система по п.10, в которой древовидная структура конструируется путем сортировки запросов машины-получателя путем канонического упорядочения на основании поля каждого запроса.

15. Система по п.10, в которой древовидная структура содержит один или несколько узлов запроса, которые содержат по меньшей мере одно поле и по меньшей мере одно значение, связанное с запросом.

16. Система по п.10, в которой полем является тикер, а значением является конкретный тикерный символ.

17. Система по п.10, в которой запросом является "Тикер=TIBX".

18. Система по п.10, в которой древовидная структура содержит корневой узел, один или несколько внутренних узлов и один или несколько концевых узлов.

19. Логическое средство для развертывания приложения, воплощенное на машиночитаемом носителе и рассчитанное при выполнении на:

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

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

анализ сообщения машины-отправителя, содержащего поле содержания, связанное со значением содержания,

поиск в древовидной структуре с использованием поля содержание сообщения,

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

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