Способ и сервер для прогнозирования предлагаемого варианта расширения частично введенного пользователем запроса

Изобретение относится к способу и серверу для обучения алгоритма машинного обучения (MLA) для определения вариантов расширения частично введенного пользователем запроса. Техническим результатом является повышение точности определения варианта расширения частично введенного пользователем запроса. Способ включает в себя прием и разделение прошлых запросов на n-граммы. Каждая n-грамма связана с соответствующими признаками n-граммы, указывающими на попарное совместное появление n-грамм в прошлых запросах. Способ для данной n-граммы из данного прошлого запроса включает в себя: выбор по меньшей мере одной возможной n-граммы из множества n-грамм в зависимости от попарного совместного появления; формирование соответствующих векторов признаков для данной n-граммы и по меньшей мере одной возможной n-граммы; формирование для данной n-граммы обучающего набора, который содержит входной сегмент и сегмент метки; обучение алгоритма MLA на основе обучающего набора для определения предсказанного группового совместного появления по меньшей мере одной используемой возможной n-граммы и по меньшей мере одной используемой n-граммы. 2 н. и 18 з.п. ф-лы, 10 ил.

 

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

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

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

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

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

Раскрытие изобретения

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

Кроме того, традиционные системы обычно способны обеспечивать возможное продолжение частично введенного пользователем запроса в качестве предлагаемого варианта запроса. Например, если частично введенный пользователем запрос представляет собой слово «Moscow», традиционные системы могут предоставить такой вариант запроса, как «City», который будет продолжать частично введенный пользователем запрос. Тем не менее, такие продолжения могут не удовлетворять большое количество пользователей, поскольку для них могут оказаться полезными те варианты запроса, которые могут предшествовать частично введенному пользователем запросу, например,«Welcome to».

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

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

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

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

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

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

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

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

В некоторых вариантах реализации настоящей технологии признаки данной n-граммы могут указывать на попарное совместное появление каждой из множества n-грамм и данной n-граммы во множестве прошлых пользовательских запросов.

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

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

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

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

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

В некоторых вариантах реализации сервера он дополнительно может быть способен определять признаки n-граммы, которые должны быть связаны с каждой из множества n-грамм, на основе множества n-грамм и множества прошлых пользовательских запросов.

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

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

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

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

В некоторых вариантах реализации сервера признаки данной n-граммы могут указывать на попарное совместное появление каждой из множества n-грамм и данной n-граммы во множестве прошлых пользовательских запросов.

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

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

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

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

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

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

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

В контексте настоящего описания выражение «пригодный для использования в компьютере носитель информации» означает носители любого типа и вида, такие как ОЗУ, ПЗУ, диски (CD-ROM, DVD, гибкие диски, жесткие диски и т.д.), USB-накопители, твердотельные накопители, накопители на магнитных лентах и т.д.

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

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

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

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

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

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

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

На фиг. 3 представлены множество прошлых пользовательских запросов и множество n-грамм в соответствии с некоторыми вариантами осуществления настоящей технологии.

На фиг. 4 представлены множества возможных n-грамм, выбранных из множества n-грамм, представленного на фиг. 3, в соответствии с некоторыми вариантами осуществления настоящей технологии.

На фиг. 5 показаны формируемые для обучающего набора векторы признаков и метки для обучения алгоритма машинного обучения (MLA), представленного на фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

На фиг. 6 приведена процедура обучения алгоритма MLA, представленного на фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

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

На фиг. 8 показан этап использования алгоритма MLA, представленного на фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

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

На фиг. 10 приведена блок-схема способа обучения алгоритма MLA, представленного на фиг. 1, в соответствии с некоторыми вариантами осуществления настоящей технологии.

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

На фиг. 1 представлена схема системы 100, пригодной для реализации вариантов осуществления настоящей технологии, не имеющих ограничительного характера. Очевидно, что система 100 приведена только для демонстрации варианта реализации настоящей технологии. Таким образом, дальнейшее описание системы представляет собой описание примеров, иллюстрирующих настоящую технологию. Это описание не предназначено для определения объема или границ настоящей технологии. В некоторых случаях также приводятся полезные примеры модификаций системы 100. Они способствуют пониманию, но также не определяют объема или границ настоящей технологии. Эти модификации не составляют исчерпывающего списка. Как понятно специалисту в данной области, вероятно, возможны и другие модификации. Кроме того, если в некоторых случаях модификации не описаны (т.е. примеры модификаций отсутствуют), это не означает, что они невозможны и/или что описание содержит единственный вариант реализации того или иного элемента настоящей технологии. Специалисту в данной области очевидно, что это не так. Кроме того, следует понимать, что система 100 в некоторых случаях может представлять собой упрощенную реализацию настоящей технологии, и что такие варианты представлены, чтобы способствовать лучшему ее пониманию. Специалисту в данной области очевидно, что различные варианты реализации настоящей технологии могут быть значительно сложнее.

В целом, система 100 способна обеспечивать варианты запросов и/или результаты поиска для устройства 104 с целью отображения пользователю 102. Система 100 содержит устройство 104, связанное с пользователем 102. Устройство 104 иногда может называться электронным устройством, оконечным устройством, клиентским электронным устройством или просто устройством. Следует отметить, что связь электронного устройства 104 с пользователем 102 не означает необходимости предполагать или подразумевать какой-либо режим работы, например, вход в систему, регистрацию и т.п.

На реализацию устройства 104 не накладывается каких-либо особых ограничений. Например, устройство 104 может быть реализовано как персональный компьютер (настольный, ноутбук, нетбук и т.д.), беспроводное устройство связи (смартфон, сотовый телефон, планшет и т.д.) или как сетевое оборудование (маршрутизатор, коммутатор, шлюз и т.д.). Устройство 104 содержит известные в данной области техники аппаратные средства, и/или прикладное программное обеспечение, и/или встроенное программное обеспечение (либо их сочетание) для выполнения браузерного приложения 106. Браузерное приложение 106 обеспечивает пользователю 102 доступ к одному или нескольким веб-ресурсам. На реализацию браузерного приложения 106 не накладывается каких-либо особых ограничений. Например, браузерное приложение 106 может быть реализовано как браузер Yandex™.

На фиг. 2 представлено окно 200 браузера браузерного приложения 106, отображаемое посредством устройства 104 пользователю 102 в первый момент времени. На фиг. 7 представлено окно 200' браузера браузерного приложения 106, отображаемое посредством устройства 104 во второй момент времени. На фиг. 9 представлено окно 200'' браузера браузерного приложения 106, отображаемое посредством устройства 104 в третий момент времени. Следует отметить, что окна 200, 200' и 200'' браузера, пронумерованные отдельно, могут представлять собой одно и то же окно браузера, отображаемое посредством устройства 104 пользователю 102 в различные моменты времени.

Окно 200 браузера содержит универсальную панель 202 (omnibar). Следует отметить, что окна 200' и 200'' браузера также содержат универсальные панели 202' и 202'', соответственно, которые представляют собой универсальную панель 202 в различные моменты времени. В целом, универсальная панель 202 представляет собой многофункциональную панель, способную поддерживать различные функции браузерного приложения 106.

Универсальная панель 202 поддерживает функции адресной строки и отображает текущие универсальные указатели ресурсов (URL), а также обеспечивает пользователю 102 возможность ввода с клавиатуры (или иным образом) указателей URL в универсальную панель 202 для перехода к выбранному пользователем веб-ресурсу. Например, пользователь 102 может осуществлять доступ к одному или нескольким веб-ресурсам путем ввода с клавиатуры (или путем копирования в буфер обмена и вставки, или выбора ссылки, или речевого ввода) указателя URL, связанного с одним или несколькими веб-ресурсами, в универсальную панель 202. В результате устройство 104 может быть способно получать информацию, относящуюся к одному или нескольким веб-ресурсам, связанным с введенным с клавиатуры (или иным образом) указателем URL, и отображать ее пользователю 102 посредством браузерного приложения 106 в области 204 отображения окна 200 браузера. Следует отметить, что окна 200' и 200'' браузера также содержат области 204' и 204'' отображения, соответственно, которые представляют собой область 204 отображения в различные моменты времени.

Универсальная панель 202 также поддерживает функции строки поиска и обеспечивает пользователю 102 возможность ввода с клавиатуры (или иным образом) и отправки пользовательских запросов на поиск определенной информации. Например, пользователь 102 может с помощью универсальной панели 202 отправить некоторый введенный пользователем запрос, который может передаваться устройством 104 в данную поисковую систему для поиска определенной информации, связанной с этим введенным пользователем запросом. В результате устройство 104 может затем принимать определенную информацию и отображать ее пользователю 102 в области 204 отображения окна 200 браузера. Иными словами, универсальная панель 202 может быть связана с данной поисковой системой, расположенной на данном сервере (таком как сервер 112, показанный на фиг. 1), для отправки в нее введенного пользователем запроса, таким образом универсальная панель 202 поддерживает функции строки поиска.

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

Как показано на фиг. 7, можно предположить, что пользователь 102 ввел с клавиатуры (или иным образом) слово «dog» в универсальную панель 202' окна браузерного приложения 200' во второй момент времени. Должно быть понятно, что слово «dog» может представлять собой данный желательный пользовательский запрос пользователя 102 или данный частично введенный пользователем 102 запрос, если пользователь 102 предполагает ввести больше слов. В данном примере пользователь 102 может пожелать ввести с клавиатуры любой из множества предполагаемых пользовательских запросов, таких как «black dog», «shepherd dog», «brown dog is cute», «german shepherd dog» и т.д., каждый из которых содержит слово «dog». Тем не менее, должно быть понятно, что в случае, когда слово «dog» представляет собой данный частично введенный пользователем запрос, желательный пользовательский запрос пользователя 102 заранее неизвестен.

В некоторых вариантах осуществления настоящей технологии браузерное приложение 106 может быть способным определять, что слово «dog» представляет собой частично введенный пользователем запрос. Например, после нажатия кнопки пользователем 102 может активироваться триггер расширения запроса. В этом примере триггер расширения запроса может активироваться после нажатия пользователем 102 кнопки для ввода буквы «g» из слова «dog». Предполагается, что триггер расширения запроса может активироваться после каждого нажатия кнопки пользователем 102. Также предполагается, что без выхода за границы настоящей технологии другие подходящие триггеры расширения запроса могут использоваться для определения того, что слово «dog» представляет собой данный частично введенный пользователем запрос.

После активации триггера расширения запроса универсальная панель 202 (браузерное приложение 106) может разрешать передачу устройством 104 слова «dog» в качестве частично введенного пользователем запроса 701 серверу 112. Например, устройство 104 может быть способно формировать пакет 150 данных, представленный на фиг. 1, который содержит информацию, указывающую на то, что слово «dog» представляет собой частично введенный пользователем запрос 701. Пакет 150 данных может передаваться серверу 112 через сеть 110 связи. Реализация сети 110 связи описана далее.

Устройство 104 может принимать различные предлагаемые варианты расширения запроса для частично введенного пользователем запроса 701. Например, устройство 104 может принимать с сервера 112 через сеть 110 связи пакет 160 данных, который содержит информацию, указывающую на различные предлагаемые варианты расширения запроса.

Как описано ранее, на фиг. 9 представлено окно 200'' браузера браузерного приложения 106, отображаемое пользователю 102 в третий момент времени. Предлагаемые варианты 901 и 902 расширения запроса для частично введенного пользователем запроса 701 «dog» могут отображаться пользователю 102 в области 206'' расширения запроса окна 200'' браузера, чтобы пользователь 102 мог завершить частично введенный пользователем запрос 701 «dog», не вводя с клавиатуры (или иным образом) оставшуюся часть данного желательного пользовательского запроса в универсальную панель 202''.

В целом, это способно помочь пользователю 102 во время отправки желательных пользовательских запросов в соответствующую поисковую систему. Например, пользователь 102 может выбрать по меньшей мере один из предлагаемых вариантов 901 и 902 расширения запроса, чтобы дополнить частично введенный пользователем запрос 701 «dog» для отправки более точного запроса в соответствующую поисковую систему.

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

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

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

Пусть имеется пример данной текстовой строки: «cat is red». В одном варианте реализации данная текстовая строка содержит основанные на словах n-граммы, такие как «cat», «is» и «red». В другом варианте реализации данная текстовая строка содержит основанные на буквах n-граммы, такие как «с», «а», «t», «s», «r», «е» и «d». В еще одном варианте реализации предполагается, что данная текстовая строка содержит основанные на слогах n-граммы, и т.д.

Представленное на фиг. 1 устройство 104 соединено с сетью 110 связи с возможностью передачи данных для доступа к серверу 112 и/или другим веб-ресурсам (не показаны). В некоторых не имеющих ограничительного характера вариантах осуществления настоящей технологии в качестве сети 110 связи может использоваться сеть Интернет. В других не имеющих ограничительного характера вариантах осуществления настоящей технологии сеть 110 связи может быть реализована иначе, например, в виде любой глобальной сети связи, локальной сети связи, личной сети связи и т.п. Реализация линии связи (не пронумерована) между устройством 104 и сетью 110 связи зависит, среди прочего, от реализации устройства 104.

Только в качестве примера, не имеющего ограничительного характера, в тех вариантах осуществления настоящей технологии, в которых устройство 104 реализовано как беспроводное устройство связи (такое как смартфон), линия связи может быть реализована как беспроводная линия связи (такая как канал сети связи 3G, канал сети связи 4G, Wireless Fidelity или сокращенно WiFi^®, Bluetooth^® и т.п.). В тех примерах, где устройство 104 реализовано как ноутбук, линия связи может быть беспроводной (такой как Wireless Fidelity или сокращенно WiFi^®, Bluetooth^® и т.д.) или проводной (такой как соединение на основе Ethernet).

Система 100 также содержит сервер 112, который может быть реализован как традиционный компьютерный сервер. В примере осуществления настоящей технологии сервер 112 может быть реализован как сервер Dell™ PowerEdge™, работающий под управлением операционной системы Microsoft™ Windows Server™. Очевидно, что сервер 112 может быть реализован с использованием любых других подходящих аппаратных средств, прикладного программного обеспечения и/или встроенного программного обеспечения, либо их сочетания. В представленных не имеющих ограничительного характера вариантах осуществления настоящей технологии сервер 112 представляет собой один сервер. В других не имеющих ограничительного характера вариантах осуществления настоящей технологии функции сервера 112 могут быть распределены между несколькими серверами.

В целом, сервер 112 может управляться и/или администрироваться поставщиком услуг поисковой системы (не показан), таким как оператор поисковой системы Yandex™. В связи с этим, как описано ранее, на сервере 112 размещена поисковая система, связанная с универсальной панелью 202 (см. фиг. 2) и/или с браузерным приложением 106. Сервер 112 может быть способен выполнять один или несколько поисков после получения желательных пользовательских запросов, переданных с использованием универсальной панели 202.

Как описано ранее, сервер 112 после приема частично введенного пользователем запроса способен с использованием пакета 160 данных передавать различные предлагаемые варианты расширения запроса в устройство 104 для отображения пользователю 102 с помощью браузерного приложения 106.

Сервер 112 также реализует алгоритм 116 машинного обучения (MLA) и связан с возможностью передачи данных с главной базой 120 данных, базой 122 данных запросов и базой 124 данных результатов поиска.

На представленной иллюстрации главная база 120 данных, база 122 данных запросов и база 124 данных результатов поиска показаны как различные физические объекты. Это требование необязательно для всех вариантов осуществления настоящей технологии. Главная база 120 данных, база 122 данных запросов и база 124 данных результатов поиска могут быть реализованы как единая база данных. Кроме того, главная база 120 данных, база 122 данных запросов или база 124 данных результатов поиска могут быть разделены между несколькими распределенными хранилищами данных. Аналогичным образом алгоритм 116 MLA, главная база 120 данных, база 122 данных запросов и база 124 данных результатов поиска (или любое их сочетание) могут быть реализованы в одном физическом устройстве.

Главная база 120 данных способна хранить информацию, извлеченную или определенную иным образом или сформированную сервером 112 во время обработки. В целом, главная база 120 данных способна принимать с сервера 112 данные, которые были извлечены или определены иным образом или сформированы сервером 112 во время обработки, для временного и/или постоянного хранения и выдавать сохраненные данные серверу 112 для их использования.

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

Сервер 112 может быть способен предоставлять результаты поиска после получения данного желательного пользовательского запроса. База 124 данных результатов поиска способна хранить информацию, связанную с по меньшей мере некоторыми из всех возможных результатов поиска, которые сервер 112 способен предоставлять после получения желательных пользовательских запросов. На виды результатов поиска и способ реализации базы 124 данных результатов поиска не накладывается каких-либо особых ограничений. Достаточно указать, что сервер 112 может получать набор результатов поиска из базы 124 данных результатов поиска для желательного поискового запроса, отправленного серверу 112 пользователем 102 устройства 104 (или любым другим пользователем поисковой системы), а также может выдавать набор результатов поиска в устройство 104 для отображения пользователю 102 (или любому другому пользователю поисковой системы).

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

Этап обучения алгоритма 116 MLA

Как описано ранее, сервер 112 может использовать архивную информацию, собранную из большого количества прошлых пользовательских запросов. Сервер 112 способен принимать множество 300 прошлых пользовательских запросов, представленное на фиг. 3. Например, сервер 112 может принимать множество 300 прошлых пользовательских запросов из базы 122 данных запросов. Множество 300 прошлых пользовательских запросов может содержать прошлые пользовательские запросы, ранее отправленные в поисковую систему сервера 112.

В не имеющем ограничительного характера примере, представленном на фиг. 3, множество 300 прошлых пользовательских запросов содержит следующие прошлые пользовательские запросы:

Q1: «cat eats bird»;

Q2: «beautiful cat»;

Q3: «dog versus cat»;

Q4: «yellow bird»;

Q5: «jerry the cat»;

Q6: «cat and mouse»;

Q7: «bird escapes from cat».

Следует понимать, что множество 300 прошлых пользовательских запросов может содержать большое количество прошлых пользовательских запросов (например, 1000, 10 000, 100000 прошлых пользовательских запросов и т.д.) без выхода за границы настоящей технологии.

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

Сервер 112 может быть способен разделять:

Q1 на последовательность S1: «cat», «eats» и «bird»;

Q2 на последовательность S2: «beautiful» и «cat»;

Q3 на последовательность S3: «dog», «versus» и «cat»;

Q4 на последовательность S4: «yellow» и «bird»;

Q5 на последовательность S5: «jerry», «the» и «cat»;

Q6 на последовательность S6: «cat», «and» и «mouse»;

Q7 на последовательность S7: «bird», «escapes», «from» и «cat».

Следует отметить, что в прошлом пользовательском запросе Q1 n-грамма «cat» является предшествующей n-граммой для n-грамм «bird» и «eats». Точнее, в прошлом пользовательском запросе Q1 n-грамма «cat» является непосредственно предшествующей n-граммой для n-граммы «eats». Следует также отметить, что n-грамма «bird» является последующей n-граммой для n-грамм «cat» и «eats». Точнее, в прошлом пользовательском запросе Q1 n-грамма «bird» является непосредственно последующей n-граммой для n-граммы «eats».

В некоторых вариантах осуществления настоящей технологии некоторая n-грамма может определяться сервером 112 как появляющаяся совместно с другой n-граммой, когда данная n-грамма является (а) предшествующей или (б) последующей n-граммой для другой n-граммы в том же прошлом пользовательском запросе. Например, в этих вариантах осуществления можно сказать, что n-грамма «cat» появлялась совместно с n-граммой «eats» и с n-граммой «bird» в прошлом пользовательском запросе Q1. В этих вариантах осуществления согласно данному примеру, можно сказать, что n-грамма «eats» появлялась совместно с n-граммой «cat» и с n-граммой «bird» в прошлом пользовательском запросе Q1. В этих вариантах осуществления согласно данному примеру, можно сказать, что n-грамма «bird» появлялась совместно с n-граммой «cat» и с n-граммой «eats» в прошлом пользовательском запросе Q1.

В других вариантах осуществления настоящей технологии некоторая n-грамма может определяться сервером 112 как появляющаяся совместно с другой n-граммой, когда данная n-грамма является (а) непосредственно предшествующей или (б) непосредственно последующей n-граммой для другой n-граммы в том же прошлом пользовательском запросе. Например, в этих вариантах осуществления можно сказать, что в прошлом пользовательском запросе Q1 n-грамма «cat» появлялась совместно с n-граммой «eats», но не с n-граммой «bird». В этих вариантах осуществления согласно данному примеру, можно сказать, что n-грамма «eats» появлялась совместно с n-граммой «cat» и с n-граммой «bird» в прошлом пользовательском запросе Q1. В этих вариантах осуществления согласно данному примеру, можно сказать, что в прошлом пользовательском запросе Q1 n-грамма «bird» появлялась совместно с n-граммой «eats», но не с n-граммой «cat».

Сервер 112 способен разделять множество 300 прошлых пользовательских запросов на множество 304 n-грамм, содержащее все различные n-граммы из множества 300 прошлых пользовательских запросов. Например, сервер 112 может разделять множество 300 прошлых пользовательских запросов на множество 304 n-грамм, содержащее следующие n-граммы: «cat», «eats», «bird», «beautiful», «dog», «versus», «yellow», «jerry», «the», «and», «mouse», «escapes» и «from». Должно быть понятно, что, поскольку множество 300 прошлых пользовательских запросов может содержать большое количество других прошлых пользовательских запросов, отличающихся от прошлых пользовательских запросов Q1, Q2, Q3, Q4, Q5, Q6 и Q7, множество 304 n-грамм может содержать другие n-граммы, отличающиеся от указанных ранее, без выхода за границы настоящей технологии.

Каждая n-грамма из множества 304 n-грамм связана с по меньшей мере одним запросом из множества 300 прошлых поисковых запросов. Например, n-грамма «cat» из множества 304 n-грамм связана с прошлыми поисковыми запросами Q1, Q2, Q3, Q5, Q6 и Q7, поскольку n-грамма «cat» входит в состав каждого из прошлых поисковых запросов Q1, Q2, Q3, Q5, Q6 и Q7. В другом примере n-грамма «escapes» из множества 304 n-грамм связана с прошлым поисковым запросом Q7, поскольку n-грамма «escapes» входит в состав прошлого поискового запроса Q7.

Предполагается, что каждая n-грамма из множества 304 n-грамм может быть дополнительно связана с ее соответствующими позициями n-граммы во множестве 300 прошлых поисковых запросов. Например, n-грамма «escapes» из множества 304 n-грамм может быть связана с прошлым пользовательским запросом Q7 и со второй позицией n-граммы, поскольку она является второй n-граммой в последовательности S7 n-грамм.

Сервер 112 способен определять попарное совместное появление n-грамм из множества 304 n-грамм. Иными словами, сервер 112 может быть способен определять количество совместных появлений каждой возможной пары n-грамм из множества 304 n-грамм во множестве 300 прошлых поисковых запросов.

Например, если предположить, (а) что множество 300 прошлых поисковых запросов содержит только прошлые поисковые запросы Q1, Q2, Q3, Q4, Q5, Q6 и Q7 и (б) что данная n-грамма появляется совместно с другой n-граммой, когда данная n-грамма является (а) предшествующей или (б) последующей n-граммой для другой n-граммы в том же прошлом пользовательском запросе, то количество попарных совместных появлений пары n-грамм «cat» и «bird» равно двум, поскольку пара n-грамм «cat» и «bird» дважды совместно появляется во множестве 300 прошлых пользовательских запросов, а именно, в прошлых пользовательских запросах Q1 и Q7. С учетом аналогичных предположений количество попарных совместных появлений пары n-грамм «dog» и «bird» равно нулю, поскольку пара n-грамм «dog» и «bird» совместно не появляется ни в одном запросе из множества 300 прошлых пользовательских запросов.

Предполагается, что вероятность попарного совместного появления некоторой пары n-грамм может представлять собой отношение (а) количества совместных появлений данной пары n-грамм из множества 304 n-грамм во множестве 300 прошлых поисковых запросов и (б) количества прошлых поисковых запросов во множестве 300 прошлых поисковых запросов.

Например, если предположить, (а) что множество 300 прошлых поисковых запросов содержит только прошлые поисковые запросы Q1, Q2, Q3, Q4, Q5, Q6 и Q7 и (б) что данная n-грамма совместно появляется с другой n-граммой, когда данная n-грамма является (а) предшествующей или (б) последующей n-граммой для другой n-граммы в том же прошлом пользовательском запросе, то вероятность попарного совместного появления пары n-грамм «cat» и «bird» может быть равна 2/7.

Сервер 112 также способен связывать каждую n-грамму из множества 304 n-грамм с соответствующими признаками n-граммы. В целом, признаки соответствующей n-граммы содержат данные попарного совместного появления соответствующей n-граммы и каждой n-граммы из множества 304 n-грамм. В данном примере это означает, что признаки n-граммы «cat» содержат данные попарного совместного появления n-граммы «cat» и n-грамм «cat», «eats», «bird», «beautiful», «dog», «versus», «yellow», «jerry», «the», «and», «mouse», «escapes» и «from».

В целом, сервер 112 способен формировать обучающие наборы, предназначенные для использования при обучении алгоритма 116 MLA. Сервер 112 может быть способен формировать соответствующий обучающий набор для каждой n-граммы в каждом запросе из множества 300 прошлых запросов пользователей. Например, сервер 112 может быть способен формировать три обучающих набора для прошлого пользовательского запроса Q1, причем каждый из этих трех обучающих наборов связан с соответствующей n-граммой «cat», «eats» и «bird» из прошлого пользовательского запроса Q1. В другом примере сервер 112 может быть способен формировать четыре обучающих набора для прошлого пользовательского запроса Q7, причем каждый из этих четырех обучающих наборов связан с соответствующей n-граммой «bird», «escapes», «from» и «cat» из прошлого пользовательского запроса Q7.

Далее описан способ формирования сервером 112 первого обучающего набора 601 (см. фиг. 6) для n-граммы «cat» из прошлого пользовательского запроса Q1. Тем не менее, следует понимать, что сервер 112 может быть способен формировать второй обучающий набор 606 для n-граммы «eats» из прошлого пользовательского запроса Q1 подобно тому, как сервер 112 формирует первый обучающий набор 601 для n-граммы «cat» из прошлого пользовательского запроса Q1. Также следует понимать, что сервер 112 может быть способен формировать третий обучающий набор 612 для n-граммы «bird» из прошлого пользовательского запроса Q1 подобно тому, как сервер 112 формирует обучающий набор 601 для n-граммы «cat» из прошлого пользовательского запроса Q1. Кроме того, должно быть понятно, что сервер 112 может быть способен формировать обучающие наборы для каждого запроса из множества 300 прошлых пользовательских запросов подобно тому, как сервер 112 может формировать первый, второй и третий обучающие наборы 601, 606 и 612 для прошлого пользовательского запроса Q1.

Формирование первого обучающего набора 601 для n-граммы «cat» из прошлого пользовательского запроса Q1 далее описано со ссылками на фиг. 4 и 5. На фиг. 4 представлен разделенный прошлый пользовательский запрос Q1 (последовательность S1 n-грамм). Для формирования первого обучающего набора 601 для n-граммы «cat» из прошлого пользовательского запроса Q1 сервер 112 может быть способен выбирать по меньшей мере одну возможную n-грамму из множества 304 n-грамм в зависимости от попарного совместного появления n-граммы «cat» и каждой соответствующей n-граммы из множества 304 n-грамм.

В некоторых вариантах осуществления сервер 112 может быть способен выбирать n-граммы из множества 304 n-грамм в качестве возможных n-грамм, только если количество их попарных совместных появлений с n-граммой «cat» во множестве 300 прошлых пользовательских запросов отличается от нуля. Иными словами, сервер 112 может быть способен выбирать n-граммы из множества 304 n-грамм в качестве возможных n-грамм, только если они по меньшей мере один раз появляются совместно с n-граммой «cat» во множестве 300 прошлых пользовательских запросов.

Если предположить, что некоторая n-грамма совместно появляется с другой n-граммой, когда данная n-грамма является (а) предшествующей или (б) последующей n-граммой для другой n-граммы в том же прошлом пользовательском запросе, то все n-граммы из множества 304 n-грамм совместно появляются с n-граммой «cat» во множестве 300 прошлых пользовательских запросов, за исключением n-грамм «cat» и «yellow» из множества 304 n-грамм. Сервер 112 может быть способен выбирать для n-граммы «cat» первое множество 400 возможных n-грамм, каждая из которых по меньшей мере один раз появляется совместно с n-граммой «cat» во множестве 300 прошлых пользовательских запросов.

В других вариантах осуществления настоящей технологии сервер 112 может быть способен ранжировать множество 304 n-грамм в зависимости от их соответствующего попарного совместного появления с n-граммой «cat» во множестве 300 прошлых пользовательских запросов. Например, сервер 112 может быть способен определять ранжированное множество 402 n-грамм, содержащее все n-граммы из множества 304 n-грамм, упорядоченные в зависимости от их соответствующего попарного совместного появления с n-граммой «cat» во множестве 300 прошлых пользовательских запросов. Предположим, что n-грамма «beautiful» появлялась совместно с n-граммой «cat» во множестве 300 прошлых пользовательских запросов чаще, чем любая другая n-грамма из множества 304 n-грамм. Тогда n-грамма «beautiful» получает самый высокий ранг в ранжированном множестве 402 n-грамм.

Предполагается, что сервер 112 может определять второе множество 406 возможных n-грамм путем выбора n-грамм с наибольшим рангом из ранжированного множества 402 n-грамм. Как показано на фиг.4, сервер 112 выбирает шесть n-грамм с наибольшим рангом, например, в ранжированном множестве 402 n-грамм, в качестве второго множества 406 возможных n-грамм.

В некоторых вариантах осуществления сервер 112 может выбирать в ранжированном множестве 402 n-грамм только одну n-грамму с наибольшим рангом в качестве возможной n-граммы. В других вариантах осуществления сервер 112 может быть способен выбирать в ранжированном множестве 402 n-грамм заранее заданное количество n-грамм с наибольшим рангом в качестве второго множества 406 возможных n-грамм. В других вариантах осуществления сервер 112 может быть способен выбирать n-граммы из ранжированного множества 402 n-грамм для второго множества 406 возможных n-грамм, только если соответствующее количество их попарных совместных появлений с n-граммой «cat» во множестве 300 прошлых пользовательских запросов превышает заранее заданный порог. Предполагается, что заранее заданное количество количеств n-грамм с наибольшим рангом и/или заранее заданный порог могут быть определены оператором сервера 112 и зависят, среди прочего, от различных вариантов реализации настоящей технологии.

Должно быть понятно, что второе множество 406 возможных n-грамм содержит все n-граммы ранжированного множества 402 n-грамм за исключением n-грамм с низким рангом, входящих в состав подмножества 404 n-грамм ранжированного множества 402 n-грамм. Подмножество 404 n-грамм содержит n-граммы из множества 304 n-грамм, которые редко совместно встречаются с n-граммой «cat» во множестве 300 прошлых пользовательских запросов.

Предполагается, что сервер 112 может быть способен использовать первое множество 400 возможных n-грамм или второе множество 406 возможных n-грамм для формирования первого обучающего набора 601 (см. фиг. 6) для n-граммы «cat» из прошлого пользовательского запроса Q1. Несмотря на то, что дальше описано использование сервером 112 второго множества 406 возможных n-грамм для формирования первого обучающего набора 601, должно быть понятно, что без выхода за границы настоящей технологии сервер 112 аналогичным образом может использовать первое множество 400 возможных n-грамм для формирования первого обучающего набора 601.

Сервер 112 способен формировать соответствующий вектор признаков для (а) каждой возможной n-граммы из второго множества 406 возможных n-грамм и (б) n-граммы «cat». Иными словами, сервер 112 способен формировать множество 500 векторов признаков, содержащее векторы 502, 504, 506, 508, 510, 512 и 514 признаков, которые, соответственно, связаны с n-граммой «cat» и возможными n-граммами «beautiful», «mouse», «bird», «eats», «the» и «and» из второго множества 406 возможных n-грамм (см. фиг. 5). Сервер 112 способен формировать соответствующий вектор признаков для данной n-граммы в зависимости от ее соответствующих признаков. Как описано ранее, признаки данной n-граммы содержат данные попарного совместного появления данной n-граммы и каждой n-граммы из множества 304 n-грамм.

Например, вектор 502 признаков, связанный с n-граммой «cat», основан на данных попарного совместного появления n-граммы «cat» с каждой n-граммой из множества 304 n-грамм. В другом примере вектор 504 признаков, связанный с возможной n-граммой «beautiful» из множества 406 возможных n-грамм, основан на данных попарного совместного появления n-граммы «beautiful» с каждой n-граммой из множества 304 n-грамм.

Сервер 112 также способен формировать множество 560 меток, содержащее метки 524, 526, 528, 530, 532 и 534, соответственно связанные с каждой n-граммой из второго множества 406 возможных n-грамм. Сервер 112 способен формировать метку из множества 560 меток путем проверки совместного появления соответствующей возможной n-граммы из второго множества 406 возможных n-грамм и n-граммы «cat» в прошлом пользовательском запросе Q1.

Если в этом случае предположить, что некоторая n-грамма появляется совместно с другой n-граммой, когда данная n-грамма является (а) предшествующей или (б) последующей n-граммой для другой n-граммы в том же прошлом пользовательском запросе, то путем выполнения проверки сервер 112 может определить, что возможные n-граммы «beautiful», «mouse», «the» и «and» не появляются совместно с n-граммой «cat» в прошлом пользовательском запросе Q1, а возможные n-граммы «bird» и «eats» появляются совместно с n-граммой «cat» в прошлом пользовательском запросе Q1. Для меток 524, 526, 532 и 534, соответственно связанных с возможными n-граммами «beautiful», «mouse», «the» и «and», назначается значение 0, а для меток 528 и 530, соответственно связанных с возможными n-граммами «bird» и «eats», назначается значение 1.

Можно сказать, что назначенные для множества 560 меток значения представляют собой вероятности совместного появления соответствующих возможных n-грамм из второго множества 406 возможных n-грамм и n-граммы «cat» в прошлом пользовательском запросе Q1. Тем не менее, поскольку прошлый пользовательский запрос Q1 известен, вероятности, связанные с возможными n-граммами из второго множества 406 возможных n-грамм, могут быть равны 1 (100%) или 0 (0%).

Должно быть понятно, что множество 560 меток указывает на групповое совместное появление данной группы n-грамм в прошлом пользовательском запросе Q1, причем данная группа n-грамм содержит n-грамму «cat» и возможные n-граммы «bird» и «eats» из второго множества 406 возможных n-грамм, поскольку возможные n-граммы «bird» и «eats» появляются совместно с n-граммой «cat» в виде данной группы в прошлом пользовательском запросе Q1.

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

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

Также должно быть понятно, что групповое совместное появление не только указывает на совместное появление n-граммы «cat» и возможных n-грамм «bird» и «eats» в виде данной группы n-грамм в прошлом пользовательском запросе Q1, но также указывает на то, что возможные n-граммы «beautiful», «mouse», «the» и «and» из второго множества 406 возможных n-грамм не входят в состав данной группы n-грамм, совместно появляющихся в прошлом пользовательском запросе Q1.

Как описано ранее, на фиг. 6 представлен первый обучающий набор 601 для n-граммы «cat» из прошлого пользовательского запроса Q1. Обучающий набор 601 содержит первый входной сегмент 602 и первый сегмент 604 метки.

Первый входной сегмент 602 содержит информацию, указывающую на (а) n-грамму «cat» из прошлого пользовательского запроса Q1, (б) второе множество 406 возможных n-грамм и (в) множество 500 векторов признаков. Предполагается, что первый входной сегмент 602 также содержит информацию, указывающую на связи между n-граммой «cat» из прошлого пользовательского запроса Q1 и вектором 502 признаков, а также на связи между каждой n-граммой из второго множества 406 возможных n-грамм и соответственно связанными векторами признаков из множества 500 векторов признаков.

Первый сегмент 604 метки содержит информацию, указывающую на множество 560 меток. Предполагается, что первый сегмент 604 метки также содержит информацию, указывающую на связи между каждой n-граммой из второго множества 406 возможных n-грамм и соответствующей меткой из множества 560 меток. Как описано ранее, множество 560 меток указывает на групповое совместное появление данной группы n-грамм в прошлом пользовательском запросе Q1, причем данная группа n-грамм содержит n-грамму «cat» и возможные n-граммы «bird» и «eats». Поэтому можно сказать, что первый сегмент 604 метки также указывает на групповое совместное появление данной группы n-грамм в прошлом пользовательском запросе Q1, причем данная группа n-грамм содержит n-грамму «cat» и возможные n-граммы «bird» и «eats».

Предполагается, что первый сегмент 604 метки также указывает на то, что возможные n-граммы «beautiful», «mouse», «the» и «and» из второго множества 406 возможных n-грамм не входят в состав группы n-грамм, которые совместно появляются в прошлом пользовательском запросе Q1.

Как описано ранее, несмотря на то, что на фиг.6 представлены только три обучающих набора, причем первый обучающий набор 601, второй обучающий набор 602 и третий обучающий набор 612 связаны с соответствующими n-граммами из прошлого пользовательского запроса Q1, должно быть понятно, что сервер 112 может быть способен формировать другие обучающие наборы для каждой n-граммы из каждого запроса из множества 300 прошлых пользовательских запросов подобно тому, как сервер 112 может формировать первый, второй и третий обучающие наборы 601, 606 и 612 для прошлого пользовательского запроса Q1.

Таким образом, сервер 112 способен выполнять процедуру 600 обучения алгоритма 116 MLA. Обучение алгоритма 116 MLA основано на первом обучающем наборе 601, втором обучающем наборе 606 и третьем обучающем наборе 612 (и на других обучающих наборах для каждой n-граммы из каждого запроса из множества 300 прошлых поисковых запросов). Путем выполнения процедуры 600 обучения алгоритм 116 MLA в известном смысле обучается обнаруживать взаимосвязи и/или закономерности в данных для возможных n-грамм и для данной n-граммы, в их соответствующем попарном совместном появлении с каждой n-граммой из множества 304 n-грамм и в групповом совместном появлении с данной n-граммой в соответствующем прошлом пользовательском запросе. Можно сказать, что алгоритм 116 MLA не только устанавливает, какие пары n-грамм часто совместно появляются во множестве 300 прошлых пользовательских запросов, но также устанавливает, какие группы n-грамм совместно появляются во множестве 300 прошлых пользовательских запросов.

Например, алгоритм 116 MLA может обнаружить, что n-грамма «light» часто появляется совместно с n-граммой «green» (на основе попарного совместного появления) и с n-граммой «red» (на основе попарного совместного появления). В этом примере алгоритм 116 MLA также может обнаружить, что n-грамма «light» более часто появляется совместно с n-граммой «green» (на основе попарного совместного появления), чем с n-граммой «red» (на основе попарного совместного появления). Тем не менее, алгоритм 116 MLA может также обнаружить, что если n-грамма «light» появляется совместно с n-граммой «stop» в прошлом пользовательском запросе, то данный прошлый пользовательский запрос более вероятно содержит группу n-грамм «red», «light» и «stop» (на основе группового совместного появления), а не группу n-грамм «green», «light» и «stop» (на основе группового совместного появления).

После обучения алгоритм 116 MLA на этапе его использования может использоваться сервером 112 для определения предсказанного группового совместного появления данной используемой группы n-грамм, содержащей (а) по меньшей мере одну данную используемую n-грамму и (б) по меньшей мере одну данную используемую возможную n-грамму. Предсказанное групповое совместное появление данной используемой группы n-грамм может применяться сервером 112 для определения того, какая из по меньшей мере одной данной используемой возможной n-граммы должна применяться в качестве по меньшей мере одного предлагаемого варианта расширения запроса для данного частично введенного пользователем запроса, содержащего по меньшей мере одну данную используемую n-грамму.

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

Этап использования алгоритма 116 MLA

Как описано ранее, сервер 112 способен принимать показанный на фиг. 1 пакет 150 данных, который содержит информацию, указывающую на частично введенный пользователем запрос 701 «dog» (см. фиг. 7). Сервер 112 также способен разделять частично введенный пользователем запрос 701 на по меньшей мере одну используемую n-грамму подобно тому, как сервер 112 способен разделять множество 300 прошлых пользовательских запросов на множество 302 последовательностей n-грамм. Например, как показано на фиг. 8, сервер 112 может быть способен разделять частично введенный пользователем запрос 701 с получением используемой n-граммы 801 «dog».

Сервер 112 способен выбирать для используемой n-граммы 801 по меньшей мере одну используемую возможную n-грамму из множества 304 n-грамм на основе попарного совместного появления каждой n-граммы из множества 304 n-грамм и используемой n-граммы 801 подобно тому, как сервер 112 выбирает первое множество 400 возможных n-грамм или второе множество 406 возможных n-грамм. Например, можно предположить, что сервер 112 выбирает используемое множество 806 возможных n-грамм, содержащее используемые возможные n-граммы «cute», «brown», «grey», «labrador», «german» и «shepherd».

Сервер 112 способен формировать соответствующий вектор признаков для каждой используемой возможной n-граммы из используемого множества 806 возможных n-грамм и для используемой n-граммы 801 «dog» подобно тому, как сервер 112 способен формировать соответствующий вектор признаков для каждой возможной n-граммы из второго множества 406 возможных n-грамм и для n-граммы «cat» на этапе обучения алгоритма 116 MLA. Сервер 112 может быть способен формировать используемое множество 800 векторов признаков, содержащее вектор 811 признаков для используемой n-граммы 801 «dog», и векторы 812, 813, 814, 815, 816 и 817 признаков для соответствующих n-грамм из используемого множества 806 возможных n-грамм.

Сервер 112 способен вводить используемую n-грамму 801, используемое множество 806 возможных n-грамм и используемое множество 800 векторов признаков в обученный алгоритм 116 MLA, который формирует множество 850 предсказанных меток. Каждая метка из множества 850 предсказанных меток связана с соответствующей n-граммой из используемого множества 806 возможных n-грамм. Предсказанная метка 851 связана с используемой возможной n-граммой «cute», предсказанная метка 852 связана с используемой возможной n-граммой «brown», предсказанная метка 853 связана с используемой возможной n-граммой «grey», предсказанная метка 854 связана с используемой возможной n-граммой «labrador», предсказанная метка 855 связана с используемой возможной n-граммой «german», а предсказанная метка 856 связана с используемой возможной n-граммой «shepherd».

Должно быть понятно, что множество 850 предсказанных меток указывает на предсказанное групповое совместное появление данной предполагаемой группы n-грамм, которая должна совместно появляться в данном предполагаемом пользовательском запросе, причем предполагаемая группа n-грамм содержит используемую n-грамму 801 и по меньшей мере одну n-грамму из используемого множества 806 возможных n-грамм.

В этом случае алгоритм 116 MLA формирует множество 850 предсказанных меток, причем конкретная метка из множества 850 предсказанных меток представляет собой вероятность того, что соответствующая n-грамма из используемого множества 806 возможных n-грамм должна входить в состав данной предполагаемой группы n-грамм (например, данного предполагаемого пользовательского запроса), если (а) используемая n-грамма 801 «dog» включена в состав данной предполагаемой группы n-грамм и (б) данная предполагаемая группа n-грамм содержит по меньшей мере одну другую n-грамму, входящую в состав используемого множества 806 возможных n-грамм.

Сервер 112 на основе множества 850 предсказанных меток способен определять, какая n-грамма из используемого множества 806 возможных n-грамм должна применяться в качестве по меньшей мере одного предлагаемого варианта расширения запроса для частично введенного пользователем запроса 701. Для этого сервер 112 может быть способен ранжировать используемые возможные n-граммы из используемого множества 806 возможных n-грамм в зависимости от значений соответственно связанных предсказанных меток из множества 850 предсказанных меток, а также способен выбирать используемые возможные n-граммы с наибольшим рангом для применения в качестве предлагаемых вариантов расширения запроса для частично введенного пользователем запроса 701.

Например, сервер 112 может быть способен формировать ранжированный используемый список 866 возможных n-грамм, содержащий используемые возможные n-граммы из используемого множества 806 возможных n-грамм, которые упорядочены в зависимости от значений соответственно связанных предсказанных меток из множества 850 предсказанных меток. Используемая возможная n-грамма «shepherd» может располагаться первой в ранжированном используемом списке 866 возможных n-грамм, поскольку соответственно связанная предсказанная метка 856 указывает на вероятность 0,8 (80%), соответствующую наибольшему значению во множестве 850 предсказанных меток. Используемая возможная n-грамма «labrador» может располагаться последней в ранжированном используемом списке 866 возможных n-грамм, поскольку соответственно связанная предсказанная метка 854 указывает на вероятность 0,01 (1%), соответствующую наименьшему значению во множестве 850 предсказанных меток.

В этом примере сервер 112 может выбирать две используемые возможные n-граммы с наибольшим рангом из ранжированного используемого списка 866 возможных n-грамм в качестве предлагаемых вариантов 901 и 902 расширения запроса, показанных на фиг. 9.

Как описано ранее, сервер 112 может формировать показанный на фиг. 1 пакет 160 данных, который содержит информацию, указывающую на то, что предлагаемый вариант 901 расширения запроса представляет собой слово «shepherd», а предлагаемый вариант 902 расширения запроса представляет собой слово «german». Пакет 160 данных затем передается через сеть 110 связи и принимается устройством 104 для отображения пользователю 102 посредством браузерного приложения 106 предлагаемых вариантов 901 и 902 расширения запроса в третий момент времени, как показано на фиг. 9.

Пользователь 102 может выбрать по меньшей мере один из предлагаемых вариантов 901 и 902 расширения запроса для дополнения частично введенного пользователем запроса 701. После выбора по меньшей мере одного из предлагаемых вариантов 901 и 902 расширения запроса пользователь 102 может отправить желательный пользовательский запрос с целью получения результатов поиска, связанных с этим желательным пользовательским запросом.

В некоторых вариантах осуществления настоящей технологии сервер 112 может быть способен выполнять представленный на фиг. 10 способ 1000 обучения алгоритма 116 MLA для определения по меньшей мере одного предлагаемого варианта расширения запроса для данного частично введенного пользователем запроса. Далее более подробно описываются различные шаги способа 1000.

Шаг 1002: Прием множества прошлых пользовательских запросов

Способ 1000 начинается с шага 1002, на котором сервер 112 способен принимать множество 300 прошлых пользовательских запросов (см. фиг. 3). Как описано ранее, сервер 112 может использовать архивную информацию, собранную из большого количества прошлых пользовательских запросов. База 122 данных запросов, соединенная с сервером 112 с возможностью передачи данных, способна хранить информацию, связанную с отправленными серверу 112 прошлыми пользовательскими запросами.

Следовательно, сервер 112 может принимать множество 300 прошлых пользовательских запросов из базы 122 данных запросов. На количество прошлых пользовательских запросов, принимаемых сервером 112 в качестве множества 300 прошлых пользовательских запросов, не накладывается каких-либо особых ограничений. Достаточно указать, что множество 300 прошлых пользовательских запросов может содержать большое количество прошлых пользовательских запросов (например, 1000, 10 000, 100000 прошлых пользовательских запросов и т.д.) без выхода за границы настоящей технологии.

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

Шаг 1004: Разделение множества прошлых пользовательских запросов на множество n-грамм.

Способ 1000 продолжается на шаге 1004, на котором сервер 112 способен разделять множество 300 прошлых пользовательских запросов на множество 304 n-грамм (см. фиг. 3).

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

Каждая n-грамма из множества 304 n-грамм связана с по меньшей мере одним соответствующим прошлым пользовательским запросом из множества 300 прошлых поисковых запросов. Например, n-грамма «cat» из множества 304 n-грамм связана с прошлыми поисковыми запросами Q1, Q2, Q3, Q5, Q6 и Q7, поскольку n-грамма «cat» входит в состав каждого из прошлых поисковых запросов Q1, Q2, Q3, Q5, Q6 и Q7. В другом примере n-грамма «escapes» из множества 304 n-грамм связана с прошлым поисковым запросом Q7, поскольку n-грамма «escapes» входит в состав прошлого поискового запроса Q7.

Предполагается, что сервер 112 может быть способен хранить множество 304 n-грамм с соответственно связанными прошлыми пользовательскими запросами в главной базе 120 данных.

Сервер 112 может быть способен связывать каждую n-грамму из множества 304 n-грамм с соответствующими признаками n-граммы. В целом, признаки соответствующей n-граммы содержат данные попарного совместного появления соответствующей n-граммы и каждой n-граммы из множества 304 n-грамм. Например, признаки n-граммы «cat» содержат данные попарного совместного появления n-граммы «cat» и каждой n-граммы из множества 304 n-грамм: «cat», «eats», «bird», «beautiful», «dog», «versus», «yellow», «jerry», «the», «and», «mouse», «escapes» и «from». Предполагается, что сервер 112 может быть способен определять признаки n-граммы, которые должны быть связаны с каждой n-граммой из множества 304 n-грамм, на основе множества 304 n-грамм и множества 300 прошлых пользовательских запросов.

Для определения попарного совместного появления некоторой пары n-грамм, сервер 112 может быть способен определять количество совместных появлений данной пары n-грамм во множестве 300 прошлых поисковых запросов Предполагается, что вероятность попарного совместного появления данной пары n-грамм может также представлять собой соотношение (а) количества совместных появлений данной пары n-грамм из множества 304 n-грамм во множестве 300 прошлых поисковых запросов и (б) количества прошлых поисковых запросов во множестве 300 прошлых поисковых запросов.

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

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

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

Шаг 1006: Выбор для данной n-граммы из данного прошлого пользовательского запроса по меньшей мере одной возможной n-граммы из множества n-грамм в зависимости от попарного совместного появления каждой из множества n-грамм и данной n-граммы во множестве прошлых пользовательских запросов.

Способ 1000 продолжается на шаге 1006, на котором сервер 112 для данной n-граммы из данного прошлого пользовательского запроса из множества 300 прошлых пользовательских запросов способен выбирать по меньшей мере одну возможную n-грамму из множества 304 n-грамм в зависимости от попарного совместного появления каждой n-граммы из множества 304 n-грамм и данной n-граммы во множестве 300 прошлых пользовательских запросов.

Например, как показано на фиг. 4, для n-граммы «cat» из прошлого пользовательского запроса Q1 сервер может выбирать по меньшей мере одну возможную n-грамму из множества 304 n-грамм в зависимости от попарного совместного появления каждой n-граммы из множества 304 n-грамм и n-граммы «cat» во множестве 300 прошлых пользовательских запросов.

В некоторых вариантах осуществления настоящей технологии сервер 112 может определять первое множество 400 возможных n-грамм для n-граммы «cat». Каждая n-грамма из первого множества 400 возможных n-грамм по меньшей мере один раз появляется совместно с n-граммой «cat» во множестве 300 прошлых поисковых запросов. Поэтому можно сказать, что сервер 112 может быть способен выбирать n-граммы из множества 304 n-грамм в качестве возможных n-грамм, только если они по меньшей мере один раз появляются совместно с n-граммой «cat» во множестве 300 прошлых пользовательских запросов.

В других вариантах осуществления настоящей технологии сервер 112 может определять второе множество 406 возможных n-грамм. Для этого сервер 112 может (а) ранжировать множество 304 n-грамм в зависимости от их соответствующего попарного совместного появления с n-граммой «cat» во множестве 300 прошлых пользовательских запросов и, таким образом, определять ранжированное множество 402 n-грамм и (б) выбирать в ранжированном множестве 402 n-грамм n-граммы с наибольшим рангом для включения в состав второго множества 406 возможных n-грамм.

Должно быть понятно, что второе множество 406 возможных n-грамм содержит все n-граммы ранжированного множества 402 n-грамм за исключением n-грамм с низким рангом, которые входят в состав подмножества 404 n-грамм ранжированного множества 402 n-грамм. Предполагается, что подмножество 404 n-грамм содержит n-граммы из множества 304 n-грамм, которые редко встречаются совместно с n-граммой «cat» во множестве 300 прошлых пользовательских запросов.

Предполагается, что сервер 112 может быть способен выбирать в ранжированном множестве 402 n-грамм заранее заданное количество n-грамм с наибольшим рангом для включения в состав второго множества 406 возможных n-грамм. В других вариантах осуществления сервер 112 может быть способен выбирать n-граммы из ранжированного множества 402 n-грамм для включения в состав второго множества 406 возможных n-грамм, только если соответствующее количество их попарных совместных появлений с n-граммой «cat» во множестве 300 прошлых пользовательских запросов превышает заранее заданный порог. Предполагается, что заранее заданное количество n-грамм с наибольшим рангом и/или заранее заданный порог могут быть определены оператором сервера 112 и зависят, среди прочего, от различных вариантов реализации настоящей технологии.

Также предполагается, что сервер 112 может быть способен хранить (а) первое множество 400 возможных n-грамм и/или (б) второе множество 406 возможных n-грамм в главной базе 120 данных связанными с n-граммой «cat».

Шаг 1008: Формирование для данной n-граммы из данного прошлого пользовательского запроса соответствующих векторов признаков для данной n-граммы и по меньшей мере одной возможной n-граммы в зависимости от соответствующих признаков n-грамм.

Способ 1000 продолжается на шаге 1008, на котором для данной n-граммы из данного прошлого пользовательского запроса (например, для n-граммы «cat» из прошлого пользовательского запроса Q1) сервер 112 в зависимости от соответствующих признаков n-граммы способен формировать соответствующий вектор признаков для данной n-граммы (например, для n-граммы «cat» из прошлого пользовательского запроса Q1) и по меньшей мере одной возможной n-граммы для данной n-граммы.

На фиг. 5 представлено множество 500 векторов признаков, содержащее векторы 502, 504, 506, 508, 510, 512 и 514 признаков, которые, соответственно, связаны с n-граммой «cat» и с возможными n-граммами «beautiful», «mouse», «bird», «eats», «the» и «and» из второго множества 406 возможных n-грамм. Например, вектор 502 признаков, связанный с n-граммой «cat», основан на признаках n-граммы «cat», следовательно, вектор 502 признаков основан на данных попарного совместного появления n-граммы «cat» с каждой n-граммой из множества 304 n-грамм.

Предполагается, что сервер 112 может формировать векторы признаков для каждой n-граммы из первого множества 402 возможных n-грамм подобно тому, как сервер 112 способен формировать векторы 504, 506, 508, 510, 512 и 514 признаков для соответствующих n-грамм из второго множества 406 возможных n-грамм.

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

Шаг 1010: Формирование для данной n-граммы из данного прошлого пользовательского запроса обучающего набора, содержащего входной сегмент и сегмент метки.

Способ продолжается на шаге 1010, на котором сервер 112 способен формировать соответствующий обучающий набор для данной n-граммы из данного прошлого пользовательского запроса (например, для n-граммы «cat» из прошлого пользовательского запроса Q1). Как показано на фиг.6, сервер 112 может формировать первый обучающий набор 601 для n-граммы «cat» из прошлого пользовательского запроса Q1.

Первый обучающий набор 601 содержит первый входной сегмент 602, основанный на n-грамме «cat» из прошлого пользовательского запроса Q1, втором множестве 406 возможных n-грамм и множестве 500 векторов признаков. Предполагается, что первый входной сегмент 602 содержит информацию, которая указывает на связи между n-граммой «cat» из прошлого пользовательского запроса Q1 и вектором 502 признаков, а также на связи между каждой n-граммой из второго множества 406 возможных n-грамм и соответственно связанными векторами признаков из множества 500 векторов признаков.

Первый обучающий набор 601 также содержит первый сегмент 604 метки. Первый сегмент 604 метки основана на множестве 560 меток (см. фиг. 5), которое может быть сформировано сервером 112. Множество 560 меток содержит метки 524, 526, 528, 530, 532 и 534, которые, соответственно связаны с каждой n-граммой из второго множества 406 возможных n-грамм. Сервер 112 способен формировать данную метку из множества 560 меток путем проверки совместного появления соответственно связанной возможной n-граммы из второго множества 406 возможных n-грамм и n-граммы «cat» в прошлом пользовательском запросе Q1.

В данном случае для меток 524, 526, 532 и 534, соответственно связанных с возможными n-граммами «beautiful», «mouse», «the» и «and», назначается значение 0, а для меток 528 и 530, соответственно связанных с возможными n-граммами «bird» и «eats», назначается значение 1.

Можно сказать, что назначенные для множества 560 меток значения представляют собой вероятности совместного появления соответствующих возможных n-грамм из второго множества 406 возможных n-грамм и n-граммы «cat» в прошлом пользовательском запросе Q1. Тем не менее, поскольку прошлый пользовательский запрос Q1 известен, вероятности, связанные с возможными n-граммами из второго множества 406 возможных n-грамм, могут быть равны 1 (100%) или 0 (0%).

Должно быть понятно, что множество 560 меток (и первый сегмент 604 метки, основанный на множестве 560 меток) указывает на групповое совместное появление данной группы n-грамм в прошлом пользовательском запросе Q1, причем данная группа n-грамм содержит n-грамму «cat» и возможные n-граммы «bird» и «eats» из второго множества 406 возможных n-грамм, поскольку возможные n-граммы «bird» и «eats» появляются совместно с n-граммой «cat» в виде данной группы в прошлом пользовательском запросе Q1.

В целом, в отличие от попарного совместного появления, которое указывает на количество совместных появлений данной пары n-грамм из множества 304 n-грамм во множестве 300 прошлых пользовательских запросов, групповое совместное появление указывает, появляется ли данная группа n-грамм совместно в данном прошлом пользовательском запросе.

Также должно быть понятно, что групповое совместное появление не только указывает на совместное появление n-граммы «cat» и возможных n-грамм «bird» и «eats» в виде данной группы n-грамм в прошлом пользовательском запросе Q1, но также указывает на то, что возможные n-граммы «beautiful», «mouse», «the» и «and» из второго множества 406 возможных n-грамм не входят в состав данной группы n-грамм, совместно появляющихся в прошлом пользовательском запросе Q1.

Предполагается, что сервер 112 может хранить первый обучающий набор 601, содержащий первый входной сегмент 602 и первый сегмент 604 метки, в главной базе 120 данных. Также предполагается, что сервер 112 формирует соответствующий обучающий набор для каждой n-граммы из каждого запроса из множества 300 прошлых пользовательских запросов и может сохранять эти обучающие наборы в главной базе 120 данных.

Шаг 1012: Обучение MLA для данной n-граммы из данного прошлого пользовательского запроса на основе обучающего набора.

Способ 1000 продолжается на шаге 1012, на котором сервер 112 для данной n-граммы из данного прошлого пользовательского запроса (например, для n-граммы «cat» из прошлого пользовательского запроса Q1) способен обучать алгоритм 116 MLA на основе первого обучающего набора 601.

Например, сервер 112 может выполнять процедуру 600 обучения (см. фиг. 6). Во время выполнения процедуры 600 обучения алгоритм 116 MLA может, среди прочего, обучаться на первом обучающем наборе 601, втором обучающем наборе 606 и третьем обучающем наборе 612.

Алгоритм 116 MLA в известном смысле обучается обнаруживать взаимосвязи и/или закономерности в данных между возможными n-граммами для данной n-граммы, их соответствующим попарным совместным появлением с каждой n-граммой из множества 304 n-грамм и групповым совместным появлением с данной n-граммой в соответствующем прошлом пользовательском запросе. Можно сказать, что алгоритм 116 MLA не только устанавливает, какие пары n-грамм часто совместно появляются во множестве 300 прошлых пользовательских запросов, но также устанавливает, какие группы n-грамм совместно появляются во множестве 300 прошлых пользовательских запросов.

Например, алгоритм 116 MLA может обнаружить, что n-грамма «light» часто появляется совместно с n-граммой «green» (на основе попарного совместного появления) и n-граммой «red» (на основе попарного совместного появления). В этом примере алгоритм 116 MLA также может обнаружить, что n-грамма «light» более часто появляется совместно с n-граммой «green» (на основе попарного совместного появления), чем с n-граммой «red» (на основе попарного совместного появления). Тем не менее, алгоритм 116 MLA может также обнаружить, что если n-грамма «light» появляется совместно с n-граммой «stop» в данном прошлом пользовательском запросе, то данный прошлый пользовательский запрос более вероятно содержит группу n-грамм «red», «light» и «stop» (на основе группового совместного появления), а не группу n-грамм «green», «light» и «stop» (на основе группового совместного появления).

Алгоритм 116 MLA обучается с целью определения на этапе его использования предсказанного группового совместного появления данной используемой группы n-грамм, содержащей (а) по меньшей мере одну данную используемую n-грамму и (б) по меньшей мере одну данную используемую возможную n-грамму. Предсказанное групповое совместное появление данной используемой группы n-грамм может применяться сервером 112, чтобы определять, какая из по меньшей мере одной данной используемой возможной n-граммы должна применяться в качестве по меньшей мере одного предлагаемого варианта расширения запроса для данного частично введенного пользователем запроса, содержащего по меньшей мере одну данную используемую n-грамму.

В некоторых вариантах осуществления настоящей технологии способ 1000 может дополнительно включать в себя прием частично введенного пользователем запроса 701 (см. фиг. 7). Например, сервер 112 может принимать пакет 150 данных (см. фиг. 1), который содержит информацию, указывающую на то, что слово «dog» представляет собой частично введенный пользователем запрос 701.

В некоторых вариантах осуществления настоящей технологии способ 1000 может дополнительно включать в себя разделение частично введенного пользователем запроса 701 на по меньшей мере одну используемую n-грамму. В приведенном примере по меньшей мере одна используемая n-грамма представляет собой используемую n-грамму «dog» (см. фиг. 8). Тем не менее, предполагается, что данный частично введенный пользователем запрос может разделяться на множество используемых n-грамм.

В некоторых вариантах осуществления настоящей технологии сервер 112 может быть способен определять признаки n-граммы, связанные с используемой n-граммой 801. Сервер 112 может определять признаки n-граммы, связанные с используемой n-граммой 801, подобно тому, как сервер определяет признаки n-граммы, связанные с n-граммой «cat» из прошлого пользовательского запроса Q1.

Предполагается, что сервер 112 может быть способен проверять, определялись ли ранее и сохранялись ли в главной базе 120 данных признаки n-граммы, связанные с n-граммой «dog». Если это так, сервер 112 может принимать признаки n-граммы, связанные с используемой n-граммой 801 «dog», из главной базы 120 данных.

В некоторых вариантах осуществления настоящей технологии способ 1000 может дополнительно включать в себя выбор по меньшей мере одной используемой возможной n-граммы из множества 304 n-грамм в зависимости от попарного совместного появления каждой n-граммы из множества 304 n-грамм и используемой n-граммы 801 во множестве 300 прошлых пользовательских запросов. Сервер 112 может выбирать по меньшей мере одну используемую возможную n-грамму из множества 304 n-грамм подобно тому, как сервер 112 выбирает (а) первое множество 400 возможных n-грамм (см. фиг. 4) или (б) второе множество 406 возможных n-грамм. Например, по меньшей мере одна используемая возможная n-грамма для n-граммы 801 «dog» может представлять собой используемое множество 806 возможных n-грамм (см. фиг. 8).

Предполагается, что сервер 112 может быть способен проверять, выбиралось ли ранее и сохранялось ли в главной базе 120 данных данное множество возможных n-грамм для n-граммы «dog». Если это так, сервер 112 может принимать используемое множество 806 возможных n-грамм для используемой n-граммы 801 «dog» из главной базы 120 данных.

В некоторых вариантах осуществления настоящей технологии сервер 112 может быть способен формировать соответствующие векторы признаков для используемой n-граммы 801 и используемого множества 806 возможных n-грамм в зависимости от соответствующих признаков n-грамм. Например, сервер 112 может формировать используемое множество 800 векторов признаков (см. фиг. 8) подобно тому, как сервер 112 формирует множество 500 векторов признаков.

Предполагается, что если сервер 112 принимает используемое множество 806 возможных n-грамм из главной базы 120 данных, то сервер 112 также может принимать используемое множество 800 векторов признаков из главной базы 120 данных.

В некоторых вариантах осуществления настоящей технологии способ 1000 может включать в себя применение сервера (путем выполнения алгоритма 116 MLA), который определяет предсказанное групповое совместное появление используемой n-граммы 801 и множества 806 используемых возможных n-грамм. Сервер 112 может определять предсказанное групповое совместное появление используемой n-граммы 801 и множества 806 используемых возможных n-грамм в зависимости от (а) используемой n-граммы 801, (б) множества 806 используемых возможных n-грамм и (в) используемого множества 800 векторов признаков.

Например, сервер 112 может быть способен вводить используемую n-грамму 801, используемое множество 806 возможных n-грамм и используемое множество 800 векторов признаков в обученный алгоритм 116 MLA, который формирует множество 850 предсказанных меток. Каждая метка из множества 850 предсказанных меток связана с соответствующей n-граммой из используемого множества 806 возможных n-грамм.

Должно быть понятно, что множество 850 предсказанных меток указывает на предсказанное групповое совместное появление данной предполагаемой группы n-грамм, которая должна совместно появляться в данном предполагаемом пользовательском запросе, причем данная предполагаемая группа n-грамм содержит используемую n-грамму 801 и по меньшей мере одну n-грамму из используемого множества 806 возможных n-грамм.

В этом случае алгоритм 116 MLA формирует множество 850 предсказанных меток, причем конкретная метка из множества 850 предсказанных меток представляет собой вероятность того, что соответствующая n-грамма из используемого множества 806 возможных n-грамм входит в состав данной предполагаемой группы n-грамм (например, данного предполагаемого пользовательского запроса), если (а) используемая n-грамма 801 «dog» включена в состав данной предполагаемой группы n-грамм и (б) данная предполагаемая группа n-грамм содержит по меньшей мере одну другую n-грамму, входящую в состав используемого множества 806 возможных n-грамм.

Сервер 112 на основе множества 850 предсказанных меток может быть способен определять, какая n-грамма из используемого множества 806 возможных n-грамм должна применяться в качестве по меньшей мере одного предлагаемого варианта расширения запроса для частично введенного пользователем запроса 701. Для этого сервер 112 может быть способен ранжировать используемые возможные n-граммы из используемого множества 806 возможных n-грамм в зависимости от значений соответствующих связанных предсказанных меток из множества 850 предсказанных меток, а также может быть способен выбирать используемые возможные n-граммы с наибольшим рангом для применения в качестве предлагаемых вариантов 901 и 902 (см. фиг. 9) расширения запроса для частично введенного пользователем запроса 701.

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

Например, как показано на фиг. 9, пользователю 102 предлагаются варианты 901 и 902 расширения запроса для частично введенного пользователем запроса 701. Пользователь 102 может выбрать любое сочетание предлагаемых вариантов 901 и 902 расширения запроса для дополнения частично введенного пользователем запроса 701 предшествующим и/или последующим термином запроса. В этом иллюстративном примере предлагаемый вариант 901 расширения запроса «shepherd» может выбираться пользователем 102 для размещения перед частично введенным пользователем запросом 701, чтобы в результате получить данный запрос «shepherd dog». Тем не менее, с такими предлагаемыми вариантами расширения запроса пользователь 102 также может выбрать предлагаемый вариант 902 расширения запроса «german» для размещения перед частично введенным пользователем запросом 701, чтобы в результате получить данный запрос «german dog». Кроме того, с такими предлагаемыми вариантами расширения запроса пользователь 102 также может выбрать оба предлагаемых варианта 902 и 901 расширения запроса «german» и «shepherd» для размещения после частично введенного пользователем запроса 701 «dog», чтобы в результате получить данный запрос «dog german shepherd». Это позволяет пользователю 102 получать пользу от предлагаемых вариантов 901 и 902 расширения запроса для дополнения частично введенного пользователем запроса 701 предшествующими и/или последующими терминами запроса.

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

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

- прием сервером множества прошлых пользовательских запросов;

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

для данной n-граммы из данного прошлого пользовательского запроса:

- выбор сервером по меньшей мере одной возможной n-граммы из множества n-грамм в зависимости от попарного совместного появления каждой n-граммы из множества n-грамм и данной n-граммы во множестве прошлых пользовательских запросов;

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

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

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

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

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

4. Способ по п. 1, отличающийся тем, что выбор по меньшей мере одной возможной n-граммы из множества n-грамм включает в себя:

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

- выбор сервером по меньшей мере одной n-граммы с наибольшим рангом из по меньшей мере некоторых n-грамм из множества n-грамм в качестве по меньшей мере одной возможной n-граммы.

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

6. Способ по п. 5, отличающийся тем, что предшествующая n-грамма является непосредственно предшествующей n-граммой, а последующая n-грамма является непосредственно последующей n-граммой.

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

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

- прием сервером частично введенного пользователем запроса;

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

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

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

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

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

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

11. Способ по п. 1, отличающийся тем, что данная n-грамма может являться по меньшей мере одной из следующих n-грамм:

основанная на буквах n-грамма;

основанная на фонемах n-грамма;

основанная на слогах n-грамма;

основанная на словах n-грамма.

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

- принимать множество прошлых пользовательских запросов;

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

для данной n-граммы из данного прошлого пользовательского запроса:

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

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

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

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

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

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

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

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

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

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

17. Сервер по п. 16, отличающийся тем, что предшествующая n-грамма является непосредственно предшествующей n-граммой, а последующая n-грамма является непосредственно последующей n-граммой.

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

19. Сервер по п. 12, отличающийся тем, что сервер дополнительно выполнен с возможностью:

- принимать частично введенный пользователем запрос;

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

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

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

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

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