1 Введение

Широкий спектр современных моделей НЛП построен на компоненте нейронной сети, который производит векторные представления предложения, означающего (например,г., Суцкевер и др., 2014; Tai et al., 2015) . Этот компонент, кодировщик предложений, обычно формулируется как изученная параметрическая функция от последовательности векторов слов до вектора предложения, и эта функция может принимать различные формы. Обычные кодировщики предложений включают в себя модели рекуррентных нейронных сетей на основе последовательностей (RNN, см. Рисунок 0 (a)) с долгосрочной краткосрочной памятью (LSTM, Hochreiter and Schmidhuber, 1997) , которые накапливают информацию по предложению последовательно; сверточные нейронные сети (Kalchbrenner et al., 2014; Zhang et al., 2015) , которые накапливают информацию с помощью фильтров по коротким локальным последовательностям слов или символов; и древовидные рекурсивные нейронные сети (TreeRNNs, Goller and Küchler, 1996; Socher et al., 2011a, см. рисунок 0 (b)) , которые распространяют информацию вверх по двоичному дереву синтаксического анализа.

Из них TreeRNN, по-видимому, является принципиальным выбором, поскольку известно, что значение в предложениях на естественном языке строится рекурсивно в соответствии с древовидной структурой (Даути, 2007, т.а.) . TreeRNN показали многообещающие (Tai et al., 2015; Li et al., 2015; Bowman et al., 2015b) , но в значительной степени игнорировались в пользу RNN на основе последовательностей из-за их несовместимости с пакетными вычислениями и их зависимость от внешних парсеров. Пакетные вычисления - выполнение синхронизированных вычислений сразу для многих примеров - дает улучшение на порядок во времени выполнения модели и имеет решающее значение для обеспечения эффективного обучения нейронных сетей на больших наборах данных.Поскольку TreeRNN используют различную структуру модели для каждого предложения, как показано на рисунке 1, эффективное пакетирование невозможно в стандартных реализациях. Частично для решения проблем эффективности стандартные модели TreeRNN обычно работают только с предложениями, которые уже были обработаны синтаксическим анализатором, что замедляет и усложняет использование этих моделей во время тестирования для большинства приложений.

В этом документе представлена ​​новая модель для решения обеих этих проблем: нейронная сеть синтаксического интерпретатора с расширенным стеком, или SPINN, показанная на рисунке 2.SPINN выполняет вычисления древовидной модели в линеаризованной последовательности и может включать в себя синтаксический анализатор нейронной сети, который на лету создает необходимую структуру синтаксического анализа. Этот дизайн улучшает архитектуру TreeRNN по трем направлениям: во время тестирования он может одновременно анализировать и интерпретировать неанализируемые предложения, устраняя зависимость от внешнего синтаксического анализатора практически без дополнительных вычислительных затрат. Во-вторых, он поддерживает пакетные вычисления как для проанализированных, так и для не проанализированных предложений, что значительно ускоряет работу стандартных TreeRNN.Наконец, он поддерживает новую гибридную архитектуру древовидной последовательности для обработки локального линейного контекста при интерпретации предложений. Эта модель представляет собой в основном правдоподобную модель обработки человеческих предложений и дает существенный выигрыш в точности по сравнению с чистыми моделями, основанными на последовательностях или деревьях.

Мы оцениваем SPINN на задаче (SNLI, Bowman et al., 2015a) Стэнфордского логического вывода и обнаруживаем, что он значительно превосходит другие модели, основанные на кодировании предложений, даже при относительно простой и недостаточно мощной реализации встроенного -в парсере.Мы также обнаружили, что SPINN дает увеличение скорости до 25 раз по сравнению со стандартной реализацией TreeRNN.

2 Связанные работы

Существует довольно долгая история работы над созданием синтаксических анализаторов на основе нейронных сетей, которые используют основные операции и структуры данных из анализа на основе переходов, из которых синтаксический анализ сдвиг-сокращение является вариантом (Henderson, 2004; Emami and Jelinek, 2005 ; Титов, Хендерсон, 2010; Чен, Мэннинг, 2014; Байс, Блансом, 2015; Дайер и др., 2015; Кипервассер, Голдберг, 2016) .Кроме того, недавно были предложены модели, предназначенные в первую очередь для задач генеративного языкового моделирования, которые также используют эту архитектуру (Zhang et al., 2016; Dyer et al., 2016) . Насколько нам известно, SPINN - первая модель, использующая эту архитектуру для интерпретации предложений, а не для синтаксического анализа или генерации.

Socher et al. (2011a, b) представляют версии модели TreeRNN, которые могут работать с неанализируемыми входными данными. Однако эти методы требуют дорогостоящего поиска во время тестирования.Наша модель представляет собой гораздо более быстрый альтернативный подход.

3 Наша модель: SPINN

3.1 Предыстория: парсинг со сдвигом и уменьшением

SPINN основан на синтаксическом анализе (Aho and Ullman, 1972) , который строит древовидную структуру над последовательностью (например, предложением на естественном языке) путем однократного сканирования ее токенов слева направо. Формализм широко используется при синтаксическом анализе естественного языка (например, Shieber, 1983; Nivre, 2003) .

Синтаксический анализатор с уменьшением сдвига принимает последовательность входных токенов x = (x0,…, xN − 1) и потребляет переходы a = (a0,…, aT − 1), где каждый at∈ {\textcshift, \textcreduce} указывает один шаг процесса синтаксического анализа.Как правило, синтаксический анализатор также может генерировать эти переходы на лету, считывая токены. Он проходит слева направо через последовательность переходов, постепенно комбинируя входные токены x в древовидную структуру. Для любой бинарно-ветвящейся древовидной структуры над N словами это требует T = 2N − 1 переходов через всего T + 1 состояние.

Анализатор использует две вспомогательные структуры данных: стек S частично завершенных поддеревьев и буфер B токенов, которые еще предстоит проанализировать. Анализатор инициализируется с пустым стеком и буфером, содержащим токены x предложения по порядку.Обозначим это начальное состояние S, B⟩ = ⟨∅, x⟩. Затем он переходит к последовательности переходов, где каждый переход выбирает одну из двух следующих операций. Ниже символ ∣ обозначает оператор cons (конкатенации). Мы произвольно выбрали всегда минус слева в обозначениях ниже.

смена:

⟨S, x∣B⟩ → ⟨x∣S, B⟩. Эта операция выталкивает элемент из буфера и помещает его на вершину стека.

уменьшить:

⟨x∣y∣S, B⟩ → ⟨(x, y) ∣S, B⟩.Эта операция выталкивает два верхних элемента из стека, объединяет их и помещает результат обратно в стек.

3.2 Состав и представление

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

Композиционная функция

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

Функция композиции TreeLSTM (Tai et al., 2015) обобщает уровень нейронной сети LSTM на входные данные на основе дерева, а не последовательности, и разделяет с LSTM идею представления промежуточных состояний в виде пары активных состояний. представление → h и представление памяти → c.Наша версия сформулирована как:

где σ - сигмоидальная функция активации, ⊙ - поэлементное произведение, пары ⟨→ h2s, → c1s⟩ и ⟨→ h3s, → c2s⟩ - это два узла входного дерева, извлеченные из стека, а → e - необязательный вектор. -значный входной аргумент, который либо пуст, либо поступает из внешнего источника, такого как отслеживающий LSTM (см. раздел 3.3). Результат этой функции, пара ⟨→ h, → c⟩, помещается обратно в стек. Каждая перечисленная векторная переменная имеет размерность D, кроме → e, независимой размерности Dtracking.

Стек и буфер

Стек и буфер представляют собой массивы по N элементов каждый (для предложений до N слов) с двумя D-мерными векторами → h и → c в каждом элементе.

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

Мы используем представления слов на основе векторов 300D, предоставляемых GloVe (Pennington et al., 2014) . Мы не обновляем эти представления во время обучения. Вместо этого мы используем выученное линейное преобразование для отображения каждого вектора входного слова → xGloVe в пару векторов ⟨→ h, → c⟩, которая хранится в буфере:

3.3 Отслеживание LSTM

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

Входные данные отслеживания LSTM (желтые на рисунке 2) - это верхний элемент буфера → h2b (который будет перемещен при операции сдвига) и два верхних элемента стека → h2s и → h3s (которые будут объединены в уменьшить операцию).

Почему гибрид древовидной последовательности?

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

Было бы просто расширить SPINN для поддержки использования некоторого количества правостороннего контекста, но это добавило бы сложности модели, которая, по нашему мнению, в значительной степени не нужна: люди очень эффективно понимают начало предложений до того, как видел или слышал концы, предполагая, что можно обойтись без недоступного правого контекста.

3.4 Анализ: прогнозирование переходов

Для того, чтобы SPINN мог работать с неанализируемыми входными данными, ему необходимо создать свою собственную последовательность переходов a, а не полагаться на внешний синтаксический анализатор, который предоставит ее как часть входных данных. Для этого модель прогнозирует на каждом шаге с помощью простого двухстороннего классификатора softmax, входом которого является состояние отслеживания LSTM:

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

Во время тестирования модель использует любой переход (т. Е. Сдвиг или уменьшение), которому присвоена более высокая (ненормализованная) вероятность. Функция прогнозирования обучена имитировать решения внешнего синтаксического анализатора.Эти решения используются в качестве входных данных для модели во время обучения. Для SNLI мы используем двоичные синтаксические анализаторы Stanford PCFG Parser, которые включены в корпус. Мы не обнаружили, что запланированная выборка (Bengio et al., 2015) - модель использует собственные решения о переходе иногда во время обучения - может помочь.

3.5 Проблемы реализации

Эффективное представление стека

Наивная реализация SPINN должна обрабатывать стек размером O (N) на каждом временном шаге, любой элемент которого может быть задействован в последующих вычислениях.Тогда наивная реализация обратного распространения может потребовать сохранения каждого из стеков O (N) для обратного прохода, что приведет к требованию к пространству для каждого примера в O (NTD) float. Это требование недопустимо велико для значительных размеров пакетов или длин предложений N. Такая наивная реализация также потребовала бы копирования практически неизмененного стека на каждом временном шаге, поскольку каждая операция сдвига или сокращения записывает только одно новое представление в верхнюю часть стека.

Мы предлагаем компактное представление стека, вдохновленное техникой застежки-молнии (Huet, 1997) , которую мы называем тонким стеком.Для каждого входного предложения мы представляем стек с единственной матрицей S размером T × D. Каждая строка S [t] (для 0

1: функция Step (bufferTop, a, t, S, Q)

2: если a = shift, то

3: S [t]: = bufferTop

4: иначе, если a = уменьшить, то

5: справа: = S [Q.pop ()]

6: left: = S [Q.pop ()]

7: S [t]: = Написать (слева, справа)

8: Q.push (t)

Это представление стека требует значительно меньше места.Он сохраняет каждый элемент, участвующий в вычислении с прямой связью, ровно один раз, что означает, что это представление все еще может поддерживать эффективное обратное распространение. Кроме того, все обновления S и Q могут выполняться пакетно и на месте на графическом процессоре, что дает существенный выигрыш в скорости как по сравнению с более простой реализацией SPINN, так и со стандартной реализацией TreeRNN. Мы описываем результаты по скорости в разделе 3.7.

Подготовка данных

Во время обучения SPINN требует как переходную последовательность a, так и последовательность лексем x в качестве входных данных для каждого предложения.Последовательность токенов - это просто слова в предложении по порядку. a можно получить из любого синтаксического анализа избирательного округа для предложения, сначала преобразовав этот синтаксический анализ в немаркированный двоичный синтаксический анализ, затем линеаризуя его (с обычным обходом по порядку), затем взяв каждый токен слова как переход сдвига и каждый ')' как переход на сокращение, как здесь:

Разбор двоичного кода без метки: ((кот) (сел))
x: , cat , сб , вниз
a: сдвиг, сдвиг, уменьшение, сдвиг, сдвиг, уменьшение, уменьшение

Обработка предложений переменной длины

Для обучения любой модели предложения с помощью пакетных вычислений необходимо дополнить или обрезать предложения до фиксированной длины.Мы зафиксировали эту длину на N = 25 слов, что больше, чем примерно 98% предложений в SNLI. Последовательности переходов a обрезаются слева или дополняются сдвигами слева. Последовательности токенов x затем обрезаются или дополняются пустыми токенами слева, чтобы соответствовать количеству сдвигов, добавленных или удаленных из a, и затем могут быть дополнены пустыми токенами справа, чтобы соответствовать желаемой длине N.

3.6 TreeRNN-эквивалентность

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

3.7 Скорость вывода

В этом разделе мы сравниваем скорость тестирования нашего SPINN-PI-NT с эквивалентной TreeRNN, реализованной обычным способом и со стандартной моделью последовательности RNN.Хотя полные модели, оцениваемые ниже, реализованы и обучены с использованием Theano (Theano Development Team, 2016) , который достаточно эффективен, но не идеален для нашей модели, мы хотим сравнить хорошо оптимизированные реализации всех трех моделей. Для этого мы повторно реализуем прямую связь SPINN-PI-NT и базовый уровень LSTM RNN в C ++ / CUDA и сравниваем эту реализацию с реализацией C ++ / Eigen TreeRNN на базе ЦП из Irsoy and Cardie (2014) , которую мы модифицирован для выполнения тех же вычислений, что и SPINN-PI-NT.Такие TreeRNN могут работать только с одним примером за раз и поэтому плохо подходят для вычислений на GPU.

Каждая модель может работать с предложениями не более 30 токенов. Мы зафиксировали размерность модели D и размерность встраивания слов на 300. Мы запустили тест производительности ЦП на 16-ядерном процессоре Intel Xeon E5-2660 с тактовой частотой 2,20 ГГц с включенной гиперпоточностью. Мы тестируем нашу реализацию тонкого стека и модель RNN на графическом процессоре NVIDIA Titan X.

На рис. 3 сравниваются скорости кодирования предложений трех моделей на случайных входных данных. Мы наблюдаем существенную разницу во времени выполнения между ЦП и реализациями тонкого стека, которая увеличивается с размером пакета. С большим, но практичным размером пакета 512, наибольшим, на котором мы тестировали TreeRNN, наша модель примерно в 25 раз быстрее, чем стандартная реализация ЦП, и примерно в 4 раза медленнее, чем базовый уровень RNN.

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

4 эксперимента NLI

Мы оцениваем SPINN по задаче логического вывода на естественном языке (NLI, также известное как распознавание текстового следования, или RTE; Даган и др., 2006) . NLI - это задача классификации пар предложений, в которой модель читает два предложения (предпосылку и гипотезу) и выводит суждение о следствии, противоречии или нейтральности, отражающее взаимосвязь между значениями двух предложений.Ниже приведен пример пары предложений и суждения из корпуса SNLI, который мы используем в наших экспериментах:

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

Гипотеза: Девушка на улице играет в снегу.

SNLI - это корпус из 570 тысяч помеченных людьми пар описаний сцен, подобных этому. Мы используем стандартное разделение поезд-тест и игнорируем немаркированные примеры, в результате чего остается около 549 тыс. Примеров для обучения, 9 842 для разработки и 9824 для тестирования.Ярлыки SNLI примерно сбалансированы, причем наиболее частая маркировка составляет 34,2% от тестового набора.

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

4.1 Применение SPINN к SNLI

Создание классификатора пар предложений

Чтобы классифицировать пару предложений SNLI, мы запускаем две копии SPINN с общими параметрами: одна для предложения-предпосылки, а другая - для предложения гипотезы. Затем мы используем их выходные данные (состояния → h наверху каждого стека в момент времени t = T), чтобы построить вектор признаков → классификатор x для пары. Этот вектор признаков состоит из конкатенации этих двух векторов предложений, их разницы и их поэлементного произведения (согласно Mou et al., 2016) :

Этот вектор признаков затем передается серии слоев нейронной сети ReLU 1024D (т. Е. MLP; количество слоев настраивается как гиперпараметр), затем передается в линейное преобразование, а затем, наконец, передается на слой softmax, который дает распределение по трем меткам.

Целевая функция

Наша цель объединяет цель кросс-энтропии Ls для задачи классификации SNLI, цели кросс-энтропии Ltp и Lth для решения синтаксического анализа для каждого из двух предложений на каждом шаге t и член регуляризации L2 для обученных параметров. Члены взвешиваются с использованием настроенных гиперпараметров α и λ:

Инициализация, оптимизация и настройка

Мы инициализируем параметры модели, используя непараметрическую стратегию He et al.(2015) , за исключением параметров классификатора softmax, которые мы инициализируем с использованием случайных однородных выборок из [-0,005,0,005].

Мы используем SGD мини-пакета с оптимизатором RMSProp (Tieleman and Hinton, 2012) и настроенной начальной скоростью обучения, которая снижается с коэффициентом 0,75 каждые 10 тыс. Шагов. Мы применяем как выпадение (Srivastava et al., 2014) , так и пакетную нормализацию (Ioffe and Szegedy, 2015) к выходу слоя проекции встраивания слов и к векторам признаков, которые служат входами и выходами для MLP. который предшествует окончательному классификатору следования.

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

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

4.2 Оценено моделей

Мы оцениваем четыре модели. Все четыре используют архитектуру классификатора пар предложений, описанную в разделе 4.1, и отличаются только функцией вычисления кодировок предложений. Во-первых, однослойный LSTM RNN (аналогичный таковому у Bowman et al., 2015a) служит базовым кодером. Затем минимальная модель SPINN-PI-NT (эквивалент TreeLSTM) представляет дизайн модели SPINN. SPINN-PI добавляет в этот дизайн отслеживающий LSTM. Наконец, полный SPINN добавляет интегрированный синтаксический анализатор.

Мы сравниваем наши модели с несколькими базовыми показателями, включая самый сильный опубликованный результат, не основанный на нейронных сетях, из Bowman et al.(2015a) и предыдущие модели нейронных сетей, построенные на основе нескольких типов кодировщиков предложений.

4.3 Результаты

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

Мы обнаружили, что простая модель SPINN-PI-NT работает немного лучше, чем базовая линия RNN, но эта модель SPINN-PI с добавленным отслеживанием LSTM работает хорошо.Успех SPINN-PI, гибридной модели древовидной последовательности, предполагает, что методы кодирования на основе дерева и последовательности, по крайней мере, частично дополняют друг друга, при этом модель последовательности предположительно обеспечивает полезное локальное устранение неоднозначности слов. Полная модель SPINN с ее относительно слабым внутренним парсером работает немного хуже, но, тем не менее, значительно превосходит производительность базовой RNN.

И SPINN-PI, и полный SPINN значительно превосходят все предыдущие модели кодирования предложений.В частности, эти модели превосходят древовидную CNN из Mou et al. (2016) , который также использует древовидную структуру для извлечения локальных признаков, но использует более простые методы объединения для построения функций предложений в интересах эффективности. Наши результаты показывают, что модель, которая полностью использует древовидную композицию (SPINN), превосходит модель, которая использует ее только частично (древовидная CNN), которая, в свою очередь, превосходит модель, которая не использует ее вообще (RNN).

Полный SPINN показал умеренно хорошие результаты при воспроизведении синтаксического анализа Stanford Parser данных SNLI на уровне перехода за переходом, с 92.Точность 4% во время тестирования. Однако его ошибки предсказания перехода довольно равномерно распределены по предложениям, и большинству предложений были назначены частично недопустимые последовательности переходов, которые либо оставляли несколько слов вне окончательного представления, либо включали несколько маркеров заполнения в окончательное представление.

4.4 Обсуждение

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

В то время как у всех четырех исследуемых моделей есть проблемы с отрицанием, модели SPINN с древовидной структурой работают на этих парах значительно лучше. Вероятно, это связано с тем, что деревья синтаксического анализа позволяют относительно легко идентифицировать область действия любого экземпляра отрицания (отрицаемая часть содержания предложения) и отделять ее от остальной части предложения. Для пар предложений тестового набора, подобных приведенной ниже, где отрицание (, а не или не ) не появляется в посылке, но присутствует в гипотезе, RNN показывает точность 67%, в то время как все три модели с древовидной структурой превышают 73%.Только RNN ошибся в приведенном ниже примере:

Предпосылка: художественная гимнастка выполняет вольное упражнение на соревнованиях.

Гипотеза: Гимнастка не может закончить упражнение.

Обратите внимание, что наличие отрицания в гипотезе коррелирует с ярлыком противоречия в SNLI, но не так сильно, как можно было бы предположить - только 45% этих примеров в тестовой выборке помечены как противоречия.

Кроме того, кажется, что модели с древовидной структурой, и особенно гибридные модели с древовидной последовательностью, более эффективны, чем RNN при извлечении информативных представлений длинных предложений.Модель RNN падает в точности теста быстрее с увеличением длины предложения, чем модель SPINN-PI-NT, которая, в свою очередь, падает значительно быстрее, чем две гибридные модели, повторяя шаблон, более резко наблюдаемый на искусственных данных в Bowman et al. (2015b) . В парах из 20 или более слов точность RNN составляет 76,7%, а SPINN-PI достигает 80,2%. Все три модели SPINN правильно пометили следующий пример, а RNN - нет:

Предпосылка: Мужчина в очках и в рваном костюме играет на электрогитаре Jaguar и поет под аккомпанемент барабанщика.

Гипотеза: Мужчина в очках и в растрепанной одежде играет на гитаре и поет вместе с барабанщиком.

Мы подозреваем, что гибридная природа полной модели SPINN также ответственна за ее удивительную способность работать лучше, чем базовая RNN, даже когда ее внутренний синтаксический анализатор относительно неэффективен при создании правильных синтаксических разборов полного предложения. Он может действовать наподобие древовидной CNN, только с доступом к более крупным деревьям: использовать древовидную структуру для создания локальных значений фраз, а затем использовать отслеживающий LSTM, по крайней мере частично, для объединения этих значений.

Наконец, как это, вероятно, неизбежно для моделей, оцениваемых по SNLI, все четыре исследуемые модели показали на несколько процентов хуже на тестовых примерах, чья наземная метка истинности нейтральна, чем на примерах двух других классов. Путаницы «следствие-нейтральный» и «нейтральный-противоречие», по-видимому, намного труднее избежать, чем заблуждения «следствие-противоречие», где относительно поверхностные сигналы могут оказаться более полезными.

5 Выводы и дальнейшая работа

Мы представляем модельную архитектуру (SPINN-PI-NT), которая эквивалентна TreeLSTM, но на порядок быстрее во время тестирования.Мы расширяем эту архитектуру до гибридной модели с древовидной последовательностью (SPINN-PI) и показываем, что это дает значительный выигрыш в решении задачи вывода SNLI. Наконец, мы показываем, что можно использовать сильные стороны этой модели без необходимости во внешнем синтаксическом анализаторе путем интеграции быстрого синтаксического анализатора в модель (как в полном SPINN), и что отсутствие внешней синтаксической информации приводит к незначительным потерям в точность.

Поскольку цель данной статьи - представить модель общего назначения для кодирования предложений, мы не стремимся к использованию мягкого внимания (Bahdanau et al., 2015; Rocktäschel et al., 2016) , несмотря на продемонстрированную эффективность для задачи SNLI. Однако мы ожидаем, что появится возможность продуктивно сочетать нашу модель с мягким вниманием, чтобы достичь самых современных характеристик.

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

Для более амбициозной цели мы ожидаем, что будет возможно реализовать вариант SPINN поверх модифицированной структуры данных стека с дифференцируемыми операциями push и pop (как в Grefenstette et al., 2015; Joulin and Mikolov, 2015 ) . Это позволило бы модели научиться синтаксическому анализу с использованием указаний из цели семантического представления, которая в настоящее время заблокирована от влияния на ключевые параметры синтаксического анализа путем использования нами решений жесткого сдвига / сокращения.Это изменение позволит модели научиться производить синтаксические анализы, которые в совокупности лучше подходят для поддержки семантической интерпретации, чем те, которые предоставляются в обучающих данных.

Благодарности

Мы признательны за финансовую поддержку со стороны Google Faculty Research Award, Стэнфордской инициативы в области науки о данных и Национального научного фонда в рамках грантов №№. BCS 1456077 и IIS 1514268. Некоторые из Tesla K40, использованные для этого исследования, были подарены NVIDIA Corporation.Мы также благодарим Кельвина Гуу, Ноа Гудмана и многих других членов Стэнфордской группы НЛП за полезные комментарии.

Список литературы

• Ахо и Ульман (1972) Альфред В. Ахо и Джеффри Д. Ульман. 1972 г. Теория синтаксического анализа, перевода и компиляции. Prentice-Hall, Inc.
• Bahdanau et al. (2015) Дмитрий Богданов, Кёнхён Чо и Йошуа Бенжио. 2015 г. Нейронный машинный перевод путем совместного обучения выравниванию и перевести. В Proc. ICLR.
• Bengio et al.(2015) Сами Бенжио, Ориол Виньялс, Навдип Джайтли и Ноам Шазир. 2015 г. Запланированная выборка для предсказания последовательности с помощью повторяющейся нейронной сети сети. В Proc. НИПС.
• Bowman et al. (2015a) Сэмюэл Р. Боуман, Габор Анджели, Кристофер Поттс и Кристофер Д. Мэннинг. 2015a. Большой аннотированный корпус для изучения логического вывода на естественном языке. В Proc. ЕМНЛП.
• Bowman et al. (2015b) Сэмюэл Р. Боуман, Кристофер Д. Мэннинг и Кристофер Поттс. 2015b. Древовидная композиция в нейронных сетях без древовидные архитектуры.В Proc. Семинар NIPS по когнитивным вычислениям 2015 г .: Интеграция нейронного и символического подходов.
• Байс и Блансом (2015) Ян Байс и Фил Блансом. 2015 г. Генеративный инкрементный анализ зависимостей с помощью нейронных сетей. В Proc. ACL.
• Чен и Мэннинг (2014) Данки Чен и Кристофер Д. Мэннинг. 2014 г. Быстрый и точный парсер зависимостей с использованием нейронных сетей. В Proc. ЕМНЛП.
• Cheng et al. (2016) Цзянпэн Ченг, Ли Донг и Мирелла Лапата.2016 г. Сети с долговременной краткосрочной памятью для машинного чтения. arXiv: 1601.06733.
• Даган и др. (2006) Идо Даган, Орен Гликман и Бернардо Маньини. 2006 г. PASCAL распознает проблему следования тексту. В задачах машинного обучения. Прогнозирующая оценка неопределенность, классификация визуальных объектов и распознавание фактических следствие, Springer.
• Даути (2007) Дэвид Даути. 2007 г. Композиционность как эмпирическая проблема. В прямой композиционности, Oxford Univ.Нажмите.
• Дайер и др. (2015) Крис Дайер, Мигель Баллестерос, Ван Линг, Остин Мэтьюз и Ноа А. Смит. 2015 г. Анализ зависимостей на основе переходов с долгосрочным стеком объем памяти. В Proc. ACL.
• Дайер и др. (2016) Крис Дайер, Адигуна Кункоро, Мигель Баллестерос и Ноа А. Смит. 2016 г. Рекуррентные грамматики нейронных сетей. В Proc. NAACL.
• Эмами и Елинек (2005) Ахмад Эмами и Фредерик Елинек. 2005 г. Нейросинтаксическая языковая модель.Машинное обучение 60 (1–3).
• Голлер и Кюхлер (1996) Кристоф Голлер и Андреас Кюхлер. 1996 г. Изучение распределенных представлений, зависящих от задачи, с помощью обратное распространение через структуру. В Proc. Международная конференция IEEE по нейронным сетям.
• Grefenstette et al. (2015) Эдвард Грефенстетт, Карл Мориц Херманн, Мустафа Сулейман и Фил Блансом. 2015 г. Обучение преобразованию с неограниченной памятью. В Proc. НИПС.
• He et al. (2015) Кайминь Хэ, Сянюй Чжан, Шаоцин Жэнь и Цзянь Сунь.2015 г. Углубляемся в выпрямители: превосходя человеческий уровень производительности на Классификация ImageNet. В Proc. ICCV.
• Хендерсон (2004) Джеймс Хендерсон. 2004 г. Дискриминационное обучение статистического парсера нейронной сети. В Proc. ACL.
• Хохрайтер и Шмидхубер (1997) Зепп Хохрайтер и Юрген Шмидхубер. 1997 г. Долговременная кратковременная память. Нейронные вычисления 9 (8).
• Хуэ (1997) Жерар Юэ. 1997 г. Застежка-молния. Журнал функционального программирования 7 (5).
• Иоффе и Сегеди (2015) Сергей Иоффе и Кристиан Сегеди. 2015 г. Пакетная нормализация: ускорение глубокого обучения сети за счет сокращения внутренний ковариативный сдвиг. В Proc. ICML.
• Ирсой и Карди (2014) Озан Ирсой и Клэр Карди. 2014 г. Глубокие рекурсивные нейронные сети для композиционности в языке. В Proc. НИПС.
• Жулен и Миколов (2015) Арман Жулен и Томаш Миколов. 2015 г. Вывод алгоритмических шаблонов с повторяющимися сетями с расширением стека.В Proc. НИПС.
• Kalchbrenner et al. (2014) Нал Кальчбреннер, Эдвард Грефенстетт и Фил Блансом. 2014 г. Сверточная нейронная сеть для моделирования предложений. В Proc. ACL.
• Кипервассер и Гольдберг (2016) Элиягу Кипервассер и Йоав Гольдберг. 2016 г. Простой анализ зависимостей с помощью иерархических древовидных LSTM. arXiv: 1603.00375.
• Ли и др. (2015) Цзивэй Ли, Минь-Тханг Луонг, Дэн Джурафски и Эудард Хови. 2015 г. Когда древовидные структуры необходимы для глубокого изучения представления? В Proc.ЕМНЛП.
• Mou et al. (2016) Лили Моу, Мэн Руи, Ге Ли, Янь Сюй, Лу Чжан, Жуй Янь и Чжи Цзинь. 2016 г. Логический вывод на естественном языке с помощью древовидной свертки и эвристики соответствие. В Proc. ACL.
• Нивр (2003) Joakim Nivre. 2003 г. Эффективный алгоритм анализа проективных зависимостей. В Proc. IWPT.
• Pennington et al. (2014) Джеффри Пеннингтон, Ричард Сочер и Кристофер Д. Мэннинг. 2014 г. GloVe: глобальные векторы для представления слов.В Proc. ЕМНЛП.
• Rocktäschel et al. (2016) Тим Роктэшель, Эдвард Грефенстетте, Карл Мориц Херманн, Томаш Кочиску и Филом Блунсом. 2016 г. Рассуждения о привлечении нервного внимания. В Proc. ICLR.
• Шибер (1983) Стюарт М. Шибер. 1983 г. Устранение неоднозначности предложений с помощью техники синтаксического анализа shift-reduce. В Proc. ACL.
• Socher et al. (2011a) Ричард Сочер, Клифф С. Лин, Эндрю Й. Нг и Кристофер Д. Мэннинг. 2011a. Анализ естественных сцен и естественного языка с помощью рекурсивной нейронной сети сети.В Proc. ICML.
• Socher et al. (2011b) Ричард Сохер, Джеффри Пеннингтон, Эрик Х. Хуанг, Эндрю Й. Нг и Кристофер Д. Мэннинг. 2011b. Полууправляемые рекурсивные автоэнкодеры для прогнозирования настроений раздачи. В Proc. ЕМНЛП.
• Srivastava et al. (2014) Нитиш Шривастава, Джеффри Хинтон, Алекс Крижевский, Илья Суцкевер и Руслан Салахутдинов. 2014 г. Dropout: простой способ предотвратить переоснащение нейронных сетей. JMLR 15.
• Суцкевер и др.(2014) Илья Суцкевер, Ориол Виньялс, Куок В. Ле. 2014 г. Последовательность для последовательного обучения с помощью нейронных сетей. В Proc. НИПС.
• Tai et al. (2015) Кай Шенг Тай, Ричард Сохер и Кристофер Д. Мэннинг. 2015 г. Улучшенные семантические представления из длинных древовидных сети краткосрочной памяти. В Proc. ACL.
• Команда разработчиков Theano (2016) Команда разработчиков Theano. 2016 г. Theano: среда Python для быстрого вычисления математических выражения.arXiv: 1605.02688.
• Тилеман и Хинтон (2012) Таймен Тилеман и Джеффри Хинтон. 2012 г. Лекция 6.5 - RMSProp: Разделите градиент на скользящее среднее его недавние масштабы. В разделе «Нейронные сети для машинного обучения», Coursera.
• Титов и Хендерсон (2010) Иван Титов и Джеймс Хендерсон. 2010 г. Модель скрытых переменных для анализа генеративной зависимости. В Гарри Бунте, Паоле Мерло и Йоакиме Нивре, редакторах журнала Trends in Технология синтаксического анализа, Springer.
• Вендров и др.(2016) Иван Вендров, Райан Кирос, Саня Фидлер и Ракель Уртасун. 2016 г. Порядок встраивания изображений и языка. В Proc. ICLR.
• Ван и Цзян (2016) Шуохан Ван и Цзин Цзян. 2016 г. Изучение логического вывода на естественном языке с помощью LSTM. В Proc. NAACL.
• Zhang et al. (2015) Сян Чжан, Цзюньбо Чжао и Янн ЛеКун. 2015 г. Сверточные сети на уровне символов для классификации текста. В Proc. НИПС.
• Zhang et al. (2016) Синсин Чжан, Лян Лу и Мирелла Лапата.2016 г. Нисходящее дерево сетей с долговременной краткосрочной памятью. В Proc. NAACL.

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

Итак, остановимся на первичном наблюдение, что «слово w похоже на слова w1, ..., wk потому что он появляется в аналогичных контекстах »и трактует w, w1, ..., wk как метка класса для w.

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

Теперь сходство двух слов w и w ′ можно измерить процент общих контекстов по отношению ко всем контекстам, в которых они появляются. Деканг ​​Лин предоставляет принципиальную меру [13] :

Где я - информация.

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

например Сегмент из записи «несколько» оценивается для одного из наших корпусов:

 несколько {несколько, 1 значимо, 0,047 незначительно, 0,043
значительно, 0,036 существенно, 0,025 далеко, 0,025 и много, 0,024
больше & и, 0,024 один & или, 0,024 много, 0,022 став, 0,021
вероятно & будет & быть, 0.021 a & little, 0,02 считается, 0,018 ничего, 0,017
скорее 0,017 так и много, 0,016 относительно, 0,016 что-то, 0,015
конечно, 0,014 вполне, 0,014 в целом, 0,014 получения, 0,014 все же, 0,012
следовательно, 0,011 сделано, 0,011 часто, 0,011 и конечно, 0,01 даже, 0,0097
очень, 0,0083 всегда, 0,0082 и очень, 0,008 один раз, 0,0073
далее, 0,0072 мало, 0,0071 меньше, 0,007 реально, 0,0066 ...}

 

Если вектор состоит из набора пар (слово, оценка), а оценка - это значение выбранной функции сходства между парой «в некоторой степени» и другие слова в словаре.

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

парсинг | Латынь ЯВЛЯЕТСЯ английским!

1. T ense

2. V oice

3. M ode (или Mood )

4. P Эрсон

5. N Умбер

Или, как мудро провозглашал мой начинающий профессор греческого языка (в нашу эпоху ухудшения качества телезрителей) через сокращение первых букв каждого из приведенных выше слов: “ T V M akes P eople N auseas! »

«Разбор» латинского «образца» 1-го спряжения глагола laudo («Я хвалю… хваляю… хваляю»): Настоящее, Активное, Указательное, 1-е лицо, Единственное число.А теперь давайте подробнее рассмотрим, что представляют собой эти «синтаксические» компоненты -

1. T ense передает «вид» действия и, как правило, только в индикативном режиме, «время» действия. Итак, для приведенного выше глагола Настоящее время будет означать как настоящее время, так и непрерывное «действие» (то есть активность в реальном, настоящем времени). Конечно, из вашего дополнительного исследования в другом месте вы узнаете, что латинские времена - это Настоящее, Несовершенное (непрерывное «действие» в прошлом), Будущее, - Pluperfect (эквивалент английского Прошлого. Perfect), и Future Perfect.

2. V oice ( «активный» или «пассивный» ) сообщает, как действие глагола связано с подлежащим. При active «voice» субъект глагола «активен» через глагол, чаще всего с прямым объектом. Например, Deum laudo = «Я, , восхваляю Бога». С помощью пассивного голоса, объект обрабатывается.Например, Бог восхваляется ». Обратите внимание на схему ниже. Даже направление стрелок поможет вам запомнить, что происходит с «активными» и «пассивными» голосовыми глаголами.

3. M ode (или Mood ) сообщает, что глагол утверждает, его отношение к «реальности».

Ориентировочная - декларативы, простые утверждения, опросы.
сослагательное наклонение - слегка условное, неуверенное утверждение; режим вероятности.
Повелительный - приказы или мольбы; режим «воли».

4. P erson обозначает, кто действует как субъект. В латыни 1st, 2nd и 3rd личных местоимений (т.е. I, you, he, she, it , we, you, и они ) включены в окончания глагольной формы.

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

Последнее слово о латинском глаголе «синтаксический анализ». Поскольку синтаксический анализ глагола содержит всю информацию, необходимую для перевода слова - при условии, конечно, что вы знаете его первоначальное значение корня - будь то Настоящее Активное Индикативное 1-е лицо единственного числа или Будущее Активное Показательное 2-е лицо множественного числа или Несовершенный Пассивный Указательный 3 человека в единственном числе; неважно что это:

Заинтересованы в посещении «живого интерактивного» онлайн-курса

Заявка на патент США для ПОМОЩИ СОСТАВЛЕНИЯ ИМЕНИ ПРИ РАССЫЛКЕ СООБЩЕНИЙ Заявка на патент (Заявка № 20210044557, выданная 11 февраля 2021 г.)

Настоящая заявка является продолжением U.Заявка на патент S. Сер. No. 16/559808, поданной 4 сентября 2019 г., которая является продолжением заявки на патент США сер. № 14/089830, поданной 26 ноября 2013 г., в которой испрашивается преимущество даты подачи предварительной заявки на патент США № 61/904 731, поданной 15 ноября 2013 г., полное раскрытие которой включено в настоящий документ посредством ссылки. .

Настоящее раскрытие в целом относится к приложениям электронного обмена сообщениями и, в частности, к составлению сообщений в приложениях электронного обмена сообщениями.

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

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

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

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

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

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

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

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

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

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

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

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

РИС. 11 - схема, иллюстрирующая реализацию электронного устройства , 100, в соответствии, по меньшей мере, с одним вариантом осуществления настоящего раскрытия.

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

РИС. 1-11 иллюстрируют примерные методы для предоставления помощи в автоматизированном составлении имен в теле сообщения электронного сообщения, составляемого на электронном устройстве. По меньшей мере, в одном варианте осуществления электронное устройство идентифицирует одно или несколько имен кандидатов-получателей на основе контекста сообщения и, в ответ на идентификацию, пользователь составляет приветствие или другое приветствие, которое, как ожидается, будет включать имя получателя в тело сообщения, предоставляет имя помощь в составлении с использованием одного или нескольких идентифицированных имен кандидатов для облегчения точного составления имени получателя.Помощь в составлении имени может быть предоставлена ​​в виде графического представления выбранного имени кандидата в соответствии с одним или несколькими вариантами представления, такими как вариант автоматического предложения («автозаполнение»), вариант автоматического завершения («автозаполнение»), и возможность автоматического исправления («автокоррекция»). Для опции автозаполнения после идентификации пользовательского ввода, указывающего на триггер приветствия (например, ввод приветствия, такого как «Привет» или «Уважаемый», или инициирования ввода первого слова тела сообщения), одно или несколько имен кандидатов являются графически представлены в виде выбираемой пользователем опции через графический интерфейс пользователя (GUI) электронного устройства, и выбор пользователем выбираемой пользователем опции приводит к автоматическому заполнению («автозаполнению») выбранного имени кандидата в теле сообщения. как часть приветствия.Для опции автозаполнения после идентификации триггера приветствия и получения пользовательского ввода, указывающего состав начальных букв не приветствующего термина в теле сообщения, выбирается имя кандидата (если имеется более одного имени кандидата), и электронное устройство предоставляет графическое представление имени кандидата путем автономного завершения слова в теле сообщения на основе выбранного имени кандидата. Затем пользователь может принять это завершенное слово как предполагаемое имя получателя или отклонить завершенное слово и, таким образом, вызвать его удаление из тела сообщения.Для опции автозамены электронное устройство определяет, включает ли приветствие в теле сообщения слово, соответствующее имени кандидата, и, если есть несоответствие, отображает уведомление о том, что пользователь мог ошибиться при составлении имени получателя в теле сообщения. Это уведомление может включать в себя выбираемую пользователем опцию для замены слова в приветствии предложенным именем кандидата. Опция автозамены может использоваться после завершения приветствия и перед составлением остальной части тела сообщения, после того как тело сообщения было составлено (например,g., когда пользователь дал команду приложению обмена сообщениями инициировать передачу составленного электронного сообщения) и т.п. Ввод приветствий и других слов может осуществляться путем набора текста на клавиатуре, набора текста на виртуальной клавиатуре (сенсорного экрана), проведения пальцем по виртуальной клавиатуре, выбора букв с помощью мыши или сенсорной панели, набора текста на клавиатуре или с помощью набора клавиш, распознавания речи или другого типа ввод текста.

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

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

РИС. 1 иллюстрирует электронное устройство , 100, , использующее автоматизированную помощь в составлении имени получателя во время составления электронного сообщения в соответствии с, по меньшей мере, одним вариантом осуществления настоящего раскрытия.Электронное устройство 100 может включать в себя любое из множества устройств, которые могут использоваться для обмена электронными сообщениями, например сотовый телефон с поддержкой вычислений («смартфон») или часы с возможностью вычислений («умные часы»), планшетный компьютер, ноутбук. компьютер, настольный компьютер, игровая консоль, персональный цифровой помощник (КПК) и т.п.

В изображенном примере электронное устройство 100 включает в себя приложение для обмена сообщениями 102 , которое работает для передачи электронных сообщений между электронным устройством 100 и другими электронными устройствами через поставщика электронных сообщений 104 , доступного через одно или несколько сети 106 .Чтобы проиллюстрировать, приложение для обмена сообщениями , 102, может включать в себя веб-приложение электронной почты (например, Google Gmail ™), которое взаимодействует с сервером электронной почты в Интернете (один вариант осуществления поставщика сообщений , 104 ) через Интернет (один вариант осуществления сеть 106 ). В качестве другого примера приложение для обмена сообщениями 102 может включать в себя почтовый клиент Microsoft Outlook ™, который взаимодействует с сервером Microsoft Exchange ™ (один из вариантов поставщика сообщений 104 ) через внутреннюю корпоративную сеть, Интернет или их комбинацию. .В качестве еще одного примера приложение для обмена сообщениями , 102, может включать в себя приложение для обмена мгновенными сообщениями (IM), которое обменивается данными с веб-сервером IM (один вариант осуществления поставщика сообщений , 104 ) через Интернет. Другие примеры приложения для обмена сообщениями , 102, включают, например, приложение для обмена текстовыми сообщениями (например, приложение простой службы обмена сообщениями (SMS) или приложение службы обмена мультимедийными сообщениями (MMS)), приложение для микроблогов (например, приложение «твиттер»). предоставлено Twitter Inc.), приложение для социальных сетей (например, Facebook ™ или Google Circles ™) и т.п. В некоторых реализациях приложение для обмена электронными сообщениями , 102, отправляет и принимает электронные сообщения в координации с операционной системой (ОС) 108 (или другим системным программным обеспечением) электронного устройства , 100, . Чтобы проиллюстрировать, ОС , 108, может облегчить доступ к проводному или беспроводному сетевому интерфейсу, который соединяется с сетью , 106, , доступ к дисплею и устройствам пользовательского ввода (например,g., сенсорный экран, микрофон, мышь или клавиатура) электронного устройства 100 и т.п.

Одна из функций обмена сообщениями, предоставляемая приложением для обмена сообщениями 102 , - это представление графического пользовательского интерфейса (GUI) для облегчения составления пользователем электронных сообщений, которые должны быть переданы одному или нескольким получателям через провайдер обмена сообщениями 104 . Составление электронного сообщения управляется посредством ввода 110 состава пользователя, полученного через один или несколько интерфейсов пользовательского ввода, связанных с этим графическим интерфейсом пользователя, например сенсорный экран, микрофон, мышь или клавиатуру.Пользовательский ввод состава , 110, обычно включает в себя инструкцию для инициирования составления электронного сообщения, такую ​​как выбор пользователем кнопки «составить», отображаемой в графическом пользовательском интерфейсе (GUI), предоставляемом приложением для обмена сообщениями 102 или через голос пользователя. команды, инструктирующие электронное устройство 100 инициировать новое электронное сообщение. Пользовательский ввод состава , 110, также включает пользовательский ввод для предоставления адресов сообщения получателя в одном или нескольких полях адреса сообщения, а также пользовательский ввод для предоставления текста и другого типографского содержимого в тело сообщения составляемого электронного сообщения.

В ходе составления электронного сообщения пользователь электронного устройства 100 может пожелать обратиться к одному или нескольким получателям по имени в теле сообщения, например, инициируя содержание тела сообщения приветствием, которое включает одно или несколько имен получателей. Однако существует значительная вероятность того, что пользователь может неправильно написать имя предполагаемого получателя в теле сообщения, либо потому, что пользователь не знаком с именем (например, оно может не распространяться в культуре пользователя), оно может иметь несколько возможных написание (e.g., «Карл» против «Карл»), или это может иметь написание, очень похожее на другое слово. Для иллюстрации получателя электронного сообщения можно назвать «Gulprit», которое пользователь может непреднамеренно ввести как «Culprit» в теле сообщения из-за сходства их написания. Чтобы уменьшить или избежать ошибок написания имени получателя, по крайней мере, в одном варианте осуществления приложение для обмена сообщениями , 102, обеспечивает автоматическую помощь в составлении имени получателя, идентифицируя имена кандидатов на основе контекста сообщения, а затем автономно способствуя правильному использованию имени в теле сообщения с помощью различной помощи пользователя. параметры, такие как параметр автозаполнения, параметр автозаполнения, параметр автозамены и т. д.

В одном варианте осуществления этой помощи в составлении имени получателя способствует различная информация, хранящаяся в электронном устройстве 100 . Такая информация может включать в себя, например, контекст сообщения , 112, самого сообщения. Этот контекст сообщения , 112 может включать внутренний контекст сообщения, который представляет собой информацию в полях составляемого сообщения, такую ​​как информация в полях адреса получателя сообщения, например, адреса электронной почты в полях «Кому:», «Копия:» и «Bcc:» адресные поля, имена или другая основанная на имени информация, уже присутствующая или впоследствии добавленная в тело сообщения, и т.п.Этот контекст сообщения , 112 также может включать в себя внешний контекст сообщения, который представляет собой информацию, которая не получается напрямую из полей составляемого электронного сообщения, например, содержимое в другом приложении, которое инициировало составление электронного сообщения или контактную запись получатель, к которому осуществляется косвенный доступ с использованием некоторой информации из внутреннего контекста сообщения.

Приложение обмена сообщениями 102 может использовать этот контекст сообщения 112 для идентификации одного или нескольких имен кандидатов (то есть имен, которые могут быть использованы пользователем при составлении тела сообщения) либо напрямую, например, путем создания имена кандидатов из синтаксического анализа частей адресов электронной почты, зависящих от получателя, в полях получателя или косвенно, например, путем определения идентификаторов получателя из полей сообщения и последующего использования этих идентификаторов, зависящих от получателя, для поиска соответствующего имени получателя, например, база данных контактов 114 поддерживается на электронном устройстве 100 .База данных контактов , 114, может включать, например, постоянный список контактов с записями контактов, которые были собраны приложением для обмена сообщениями 102 или другим приложением, которое разрешило доступ к своей базе данных контактов, например, записи контактов Google, доступные в приложение Google Gmail ™, набор записей контактов, доступных в приложении Microsoft Outlook ™, или набор записей «друзей», доступных в учетной записи пользователя Facebook ™. Идентифицированные таким образом имена кандидатов могут храниться во временной базе данных , 116 имен кандидатов, которая может быть списком, таблицей или другой структурой данных, реализованной, например, в пространстве памяти или дисковом пространстве, выделенном приложению обмена сообщениями 102 , и может сохраняться в течение всего времени составления электронного сообщения, в течение всего времени, пока приложение для обмена сообщениями , 102, работает или иным образом активно, и т.п.Ниже подробно описаны различные методы идентификации имен кандидатов.

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

Для иллюстрации на фиг. 1 изображен графический интерфейс составления сообщения 118 приложения обмена сообщениями 102 для составления сообщения электронной почты получателю с именем «Gulprit» на адрес электронной почты «[email protected]», как указано в поле адреса to: 120 сообщения электронной почты.Этот графический интерфейс составления сообщений , 118 иллюстрирует реализацию опции автозаполнения, посредством которой приложение для обмена сообщениями 102 идентифицирует «Gulprit» как имя кандидата из адреса электронной почты «[email protected]» и в ответ на ввод пользователя, представляющий ввод слова «Привет» 130 в тело сообщения 122 сообщения электронной почты, приложение обмена сообщениями 102 предоставляет возможность автозаполнения для завершения приветствия, представляя выбираемый пользователем вариант 124 в графическом интерфейсе пользователя 118 , который предлагает графическое представление имени «Gulprit» в виде одной записи имени кандидата 126 , идентифицированной из контекста сообщения 112 , и графическое представление имени «Gillray» в качестве другой записи имени кандидата 128 , то есть идентифицируется, например, из предварительно определенного орфографического словаря, имеющего в качестве записи «Gillray».В то время как выбираемая пользователем опция 124 проиллюстрирована как графическое изображение списка выбираемых записей имени кандидата 126 , 128 , выбираемая пользователем опция 124 для автоматического предложения имен кандидатов может быть реализована в любом из разнообразие способов, согласующихся с изложенными здесь учениями. При отображении выбираемой пользователем опции 124 , предполагая, что пользователь намеревался обратиться к Gulprit в теле сообщения 122 , пользователь может выбрать запись имени кандидата «Gulprit» 126 из выбираемой пользователем опции 124 , в ответ на это приложение обмена сообщениями 102 подставляет имя «Gulprit» в текущее положение курсора в теле сообщения 122 .Таким образом, имя получателя «Gulprit» правильно вводится в тело сообщения 122 , и возможность ошибки пользователя при самостоятельном вводе имени «Gulprit» исключается.

ФИГ. 2, 3 и 4 показаны другие варианты помощи при автоматическом составлении имени получателя, которые могут быть предоставлены приложением обмена сообщениями 102 электронного устройства 100 на фиг. 1 в связи с составлением электронного сообщения. Например, фиг. 2 иллюстрирует графический интерфейс , 218 составления сообщения, который предоставляется приложением для обмена сообщениями 102 и который предоставляет возможность автозаполнения для помощи в составлении имен.Для опции автозаполнения приложение обмена сообщениями 102 отслеживает ввод состава пользователя 110 (фиг.1), чтобы обнаруживать ввод пользователя, представляющий ввод или другой ввод начального набора букв слова в теле сообщения 222 GUI составления сообщений 218 . В случае, если начальный набор букв совпадает с соответствующим начальным набором букв имени кандидата, идентифицированного из контекста сообщения 112 составляемого электронного сообщения, приложение обмена сообщениями 102 предоставляет графическое представление имени кандидата через вариант автозаполнения 224 , который представляет собой предлагаемое завершение слова в теле сообщения 222 .

В этом примере имя кандидата «Gulprit» идентифицируется из адреса электронной почты «[email protected]» в поле адреса «Кому» 220 . Для опции автозаполнения 224 , когда пользователь вводит приветственный триггер «Hi», за которым следует пробел, а затем три начальные буквы «Gul» слова 225 после приветственного триггера, приложение обмена сообщениями 102 идентифицирует этот начальный набор букв слова 225 в качестве достаточного совпадения с именем кандидата «Gulprit» и, таким образом, автоматически дополняет слово 225 в качестве имени кандидата «Gulprit».Как показано, это автозаполнение может включать, например, автоматическое введение оставшихся букв «prit» имени кандидата «Gulprit» в тело сообщения 222 после начальных букв «Gul» и предоставление некоторого индикатора того, что эти последние буквы 226 заполняются автоматически, например, с использованием текста другого цвета, подчеркивания и т.п. Если имя с автозаполнением - это слово, которое пользователь намеревался ввести, пользователь может указать свое согласие на автозаполнение, например, выбрав полосу «пробел» на клавиатуре или нажав кнопку «принять» или другую функцию принятия (не показано ), связанный с опцией автозаполнения 224 в графическом интерфейсе составления сообщений 218 .

РИС. 3 показан графический интерфейс 318 составления сообщений, который предоставляется приложением для обмена сообщениями 102 и который предоставляет возможность автозамены. Для этого подхода к помощи в составлении имени получателя приложение обмена сообщениями 102 предоставляет опцию автозамены 324 для замены слова с идентифицированным именем кандидата после того, как слово уже было набрано и заполнено в теле сообщения 322 . Таким образом, приложение для обмена сообщениями , 102, идентифицирует завершенное слово в теле сообщения 322 как потенциально представляющее имя получателя и проверяет, соответствует ли слово имени кандидата, идентифицированному для имени получателя.Если слово недостаточно соответствует имени кандидата, приложение обмена сообщениями 102 может отображать параметр автозамены 324 в графическом интерфейсе пользователя 318 , чтобы предоставить пользователю возможность заменить слово на имя кандидата, графически представленное в опция автокоррекции 324 915 10. В изображенном примере опция автозамены 324 включает в себя диалоговое окно, которое предлагает пользователю возможность заменить слово «Culprit» в теле сообщения на имя кандидата «Gulprit», идентифицированное из адреса электронной почты в адресе to: поле 320 .В этом примере слово «Culprit» может быть идентифицировано как потенциально неправильно набранное имя получателя, например, из-за того, что оно следует сразу после триггера приветствия «Привет», написано с заглавной буквы, но не является первым словом предложения, или потому что оно в основном совпадает с названием «Gulprit».

Приложение для обмена сообщениями 102 может анализировать тело электронного сообщения, составляемого, на предмет возможности представить вариант автозамены в одном или нескольких точках в процессе составления сообщения.В примере на фиг. 3, адрес обмена сообщениями получателя (например, «[email protected]») уже введен в поле адреса сообщения получателя электронного сообщения, составляемого в момент начала составления тела сообщения, и, таким образом, приложение обмена сообщениями 102 может использовать этот адрес обмена сообщениями получателя, чтобы идентифицировать одно или несколько имен кандидатов для опции автозамены. Таким образом, когда сигнализируется о завершении потенциального слова имени в теле сообщения (например, когда пользователь вводит символ «пробел» или другой символ пробела после слова), приложение обмена сообщениями 102 может проверить слово в то время завершения.Однако в некоторых случаях пользователь может инициировать составление тела сообщения до заполнения любого из полей получателя электронного сообщения, и, таким образом, может быть недостаточно контекста сообщения для приложения обмена сообщениями 102 , чтобы идентифицировать имя кандидата в время написания сообщения. Соответственно, в других случаях анализ тела сообщения для одного или нескольких потенциальных слов для автозамены имени может быть отложен до тех пор, пока пользователь не введет информацию о получателе.

РИС. 4 иллюстрирует пример процесса задержки опции автозамены до тех пор, пока составление сообщения не будет по существу завершено. В этом примере снимок экрана , 400 иллюстрирует состояние графического пользовательского интерфейса составления сообщения 418 после того, как пользователь набрал сообщение в теле сообщения 422 , но до заполнения любого из полей адреса сообщения получателя графического интерфейса составления сообщения. 418 . Сообщение, введенное пользователем, включает неправильное представление имени «Gulprit» как «Culprit».Однако, поскольку поля адреса сообщения получателя еще не заполнены на этом этапе, приложение обмена сообщениями 102 может быть не в состоянии идентифицировать ошибку, потому что имена кандидатов не могут быть идентифицированы, а слово «виновник» написано правильно. , и, следовательно, не будет обнаружен с помощью стандартного процесса проверки орфографии с предопределенным орфографическим словарем. Напротив, снимок экрана 402 иллюстрирует графический интерфейс составления сообщения 418 после того, как пользователь заполнил поле адреса 420 с псевдонимом «Gulprit» (которое приложение обмена сообщениями 102 понимает как соответствующее «gulprit @» Gmail.com »в этом примере), и пользователь указал, что составление сообщения электронной почты было завершено, инициируя передачу сообщения электронной почты, например, путем выбора значка« отправить » 423 графического интерфейса пользователя 418 составления сообщения.

В ответ на это указание на то, что составление завершено, приложение для обмена сообщениями 102 может затем повторно оценить поля адреса сообщения получателя, чтобы определить, можно ли по ним определить имя кандидата. В этом случае приложение обмена сообщениями может идентифицировать имя кандидата «Gulprit» и, таким образом, при анализе тела сообщения 422 , может идентифицировать слово «Culprit» потенциально как версию имени кандидата «Gulprit» с ошибкой и, таким образом, предоставить опция автозамены, такая как опция автозамены 324 на ФИГ.3, заменить «Culprit» на «Gulprit» в теле сообщения 422 . Таким образом, приложение для обмена сообщениями , 102, может продолжать обновлять процесс помощи в составлении имен по мере того, как становится доступным дополнительный контекст сообщения.

РИС. 5 иллюстрирует примерный способ 500 работы приложения обмена сообщениями 102 электронного устройства 100 для предоставления помощи в составлении имени во время составления электронного сообщения в соответствии с, по меньшей мере, одним вариантом осуществления.Метод 500 запускается на этапе 502 , когда пользователь выполняет действие, чтобы инициировать составление электронного сообщения. Это действие может включать, например, ввод пользователя, указывающий инструкцию для приложения обмена сообщениями 102 , чтобы начать составление сообщения, например, путем выбора значка «составить сообщение» в графическом интерфейсе приложения для обмена сообщениями 102 или в графическом интерфейсе пользователя ОС 108 (РИС. 1). В некоторых случаях составление электронного сообщения может быть инициировано косвенно.Чтобы проиллюстрировать, отдельное приложение может связывать или иным образом перенаправлять пользователя к приложению обмена сообщениями 102 для составления сообщения. Чтобы проиллюстрировать, веб-сайт, отображаемый в веб-браузере, может включать в себя ссылку, которая инициирует вызов интерфейса прикладного программирования (API) к приложению обмена сообщениями 102 , чтобы позволить пользователю составлять электронное сообщение, связанное с веб-сайтом (например, пересылка статьи на веб-сайте указанному получателю или пересылка сообщения получателю, связанному с веб-сайтом).

В ответ на этот ввод инициации на этапе 504 приложение обмена сообщениями 102 генерирует и отображает графический интерфейс составления сообщения, чтобы облегчить пользователю ввод для составления электронного сообщения. Графический интерфейс составления сообщения обычно включает в себя несколько полей, включая одно или несколько полей адреса сообщения получателя (например, поля адреса электронной почты to :, cc: и bcc:) и одно или несколько полей тела сообщения, то есть адрес не получателя. поля (обратите внимание, что термин «тело сообщения» может включать, например, поле строки темы сообщения электронной почты, поскольку оно сродни заголовку сообщения).При отображении графического пользовательского интерфейса составления сообщения в блоке 506 начальный ввод состава пользователя принимается приложением для обмена сообщениями 102 через графический интерфейс составления сообщения.

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

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

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

С определением одного или обоих из контекста внутреннего сообщения и внешнего контекста сообщения на этапе 514 приложение обмена сообщениями 102 идентифицирует одно или несколько имен кандидатов для электронного сообщения из внутреннего и внешнего контекста сообщения. Как более подробно описано ниже, идентификация этих имен кандидатов может включать в себя синтаксический анализ информации, относящейся к имени, во внутреннем контексте сообщения, поиск имени на основе специфической для получателя информации из контекста сообщения и т.п.Любые идентифицированные таким образом имена кандидатов могут быть сохранены во временной базе данных 116 имен кандидатов (фиг. 1), поддерживаемой приложением обмена сообщениями 102 для электронного сообщения.

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

В ответ на обнаружение триггера приветствия на этапе 518 приложение обмена сообщениями 102 выбирает имя кандидата (если существует более одного имени кандидата), которое может отражать имя получателя, к которому пользователь собирается или пытается к, вход в сочетании с триггером приветствия. Этот процесс выбора может включать применение одного или нескольких правил приоритизации. Например, правило приоритизации может предусматривать, что имена кандидатов, определенные из полей адреса сообщения получателя электронного сообщения, могут иметь приоритет выбора по сравнению с именами кандидатов, определенными из полей адреса не получателя, то есть полей тела сообщения.Кроме того, правило приоритизации может предусматривать, что имена кандидатов, определенные из поля to: address, могут иметь приоритет выбора по сравнению с именами кандидатов, определенными из поля cc: address, которые, в свою очередь, получают приоритет выбора над именами кандидатов, определенными из поля bcc: address и т. д. В ситуациях, когда триггер приветствия включает в себя ввод пользователем начального набора букв слова, которое, как ожидается, будет именем получателя, приоритет выбора среди нескольких имен кандидатов может быть отдан тому имени кандидата, которое наиболее близко соответствует начальному набору букв. .

С выбранным именем кандидата на этапе 520 приложение обмена сообщениями 102 может облегчить составление имени получателя, предоставляя через графический интерфейс составления сообщений один или оба варианта автозаполнения (например, фиг. 1) или автозаполнения вариант (например, фиг. 2), который графически представляет имя кандидата пользователю для включения в тело электронного сообщения таким образом, чтобы предотвратить многие вероятные ошибки ввода пользователем для имени получателя. В случае, если вариант автозаполнения / вариант автозаполнения не принимается пользователем, или в случае, если ни один из вариантов не представлен, на этапе 522 приложение обмена сообщениями 102 продолжает отслеживать ввод композиции пользователя, чтобы определить, действительно ли пользователь завершил слово, предполагаемое пользователем как имя получателя, которое несовместимо с одним или несколькими идентифицированными именами кандидатов (например,g., не соответствует ни одному из идентифицированных имен кандидатов). Этот анализ может быть выполнен относительно быстро после того, как пользователь завершил ввод слова (например, после того, как после слова был введен пробел) или после того, как пользователь сигнализировал о завершении составления электронного сообщения, например, выбрав «сохранить »Или при попытке инициировать передачу электронного сообщения путем выбора значка« отправить ».

Если такое несоответствие имени кандидата / завершенного слова или несоответствие возникает в теле сообщения, то на этапе 524 приложение обмена сообщениями 102 может предоставить опцию автозамены (например.g., фиг. 3 и 4), чтобы уведомить пользователя о потенциальной ошибке и дать пользователю возможность исправить ошибку (если это ошибка), заменив вместо этого спорное слово предложенным именем кандидата. После внесения этого исправления или, если такое исправление вообще не требуется, на этапе 526 приложение обмена сообщениями 102 завершает составление электронного сообщения и отправляет электронное сообщение провайдеру обмена сообщениями 104 (фиг.1) для рассылки по одному или нескольким адресам обмена сообщениями получателя, указанным в полях адреса сообщения получателя электронного сообщения.

РИС. 6-10 иллюстрируют примерные методы, которые могут использоваться приложением обмена сообщениями 102 , OS 108 или другим компонентом электронного устройства 100 на фиг. 1 для идентификации одного или более имен кандидатов из контекста сообщения 112 составляемого электронного сообщения. В частности, фиг.6-8 иллюстрируют методы, которые идентифицируют имена кандидатов из внутреннего контекста сообщения (то есть информации в полях самого сообщения), а фиг. 9 и 10 иллюстрируют методы, которые идентифицируют имена кандидатов из внешнего контекста сообщения (то есть контекста из внешних источников, к которому осуществляется доступ или который идентифицируется на основе внутреннего контекста сообщения).

РИС. 6 иллюстрирует методику идентификации одного или более имен кандидатов из адресов сообщения получателя, присутствующих в полях адреса сообщения получателя электронного сообщения.В этом подходе синтаксический анализатор , 600 приложения обмена сообщениями 102 обращается к зависящей от получателя части адреса сообщения получателя и анализирует вероятные слова имени из зависящей от получателя части. Однако, поскольку имя получателя может включать в себя несколько слов, синтаксический анализатор , 600, дополнительно может сгенерировать различные комбинации слов имени, проанализированных из адреса сообщения получателя, для генерации нескольких имен кандидатов. Чтобы проиллюстрировать, в изображенном примере синтаксический анализатор , 600 обращается к адресу электронной почты получателя 602 (один из вариантов адреса сообщения получателя) из поля адреса to: или поля адреса cc:, или из исходного сообщения электронной почты, включенного в теле сообщения в случае, если составляемое сообщение электронной почты является ответным сообщением электронной почты или пересылаемым сообщением электронной почты.Адреса электронной почты обычно состоят из части, зависящей от получателя, за которой следует доменная часть с символом «@», разделяющим их. Таким образом, адрес электронной почты «[email protected]» включает в себя специфичную для получателя часть «gulprit.singh» и часть домена «gmail.com». Таким образом, синтаксический анализатор , 600, может анализировать специфичную для получателя часть, чтобы идентифицировать одно или несколько потенциальных слов имени, посредством чего синтаксический анализатор , 600 может использовать различные ограничители общих слов имени, такие как точка («.»), Подчеркивание (« _ »), тире (« - ») и т.п. для обнаружения отдельных слов. Таким образом, для специфической для получателя части «gulprit.singh» адреса электронной почты получателя 602 синтаксический анализатор 600 может сгенерировать слова имени «gulprit» и «singh», и из комбинаций этих слов имени получить три имена кандидатов 604 , 606 , 608 - «Гулприт», «Сингх» и «Гулприт Сингх» соответственно. «Сингх Гулприт» также может быть разумным кандидатом на имя, если в системе адресации электронной почты принято помещать фамилию или фамилию первыми в адресе электронной почты.Затем синтаксический анализатор 600 может поместить эти имена кандидатов 604 , 606 и 608 в базу данных кандидатов 116 электронного устройства 100 для последующего использования при помощи композиции имен, как описано выше. Этот процесс может быть аналогичным образом применен для анализа имен файлов файлов, перечисленных в поле вложения электронного сообщения.

РИС. Фиг.7 иллюстрирует методику идентификации одного или нескольких имен кандидатов из поля отображаемого имени, связанного с адресом сообщения получателя, присутствующим в полях адреса сообщения получателя электронного сообщения.Часто по соображениям безопасности или по другим причинам организация, предоставляющая услуги электронного обмена сообщениями своим составляющим, может решить использовать специфичную для получателя часть адреса получателя сообщения, которая, будучи уникальной для получателя, не отражает имени получателя. Такие конфигурации затрудняют идентификацию имен кандидатов непосредственно из адреса получателя сообщения, если не делают невозможным. Однако протоколы электронной почты и другие протоколы обмена сообщениями часто предоставляют одно или несколько полей идентификации пользователя, которые могут быть более полезными при идентификации получателя, чем адрес получателя сообщений.Для иллюстрации, протоколы электронной почты предусматривают включение поля отображаемого имени в ассоциации с адресом электронной почты получателя, где поле отображаемого имени хранит удобное для пользователя отображаемое имя. Анализатор , 600, может использовать такие поля имени пользователя для идентификации одного или более имен кандидатов. В качестве примера, получатель составляемого сообщения электронной почты может быть указан в наборе полей 702 получателя электронной почты, который включает в себя поле адреса электронной почты 704 , в котором хранится адрес электронной почты «A100269 @ motorola».com »и поле отображаемого имени 706 , в котором хранится отображаемое имя« Gulprit Singh ». Специфическая для получателя часть адреса электронной почты «A100269» не содержит никакой полезной информации для прямой идентификации одного или нескольких слов имени, и, таким образом, синтаксический анализатор 600 вместо этого может проанализировать отображаемое имя «Gulprit Singh» в поле отображаемого имени 706 , чтобы идентифицировать одно или несколько имен кандидатов. Как и в примере на фиг. 6, анализ этого отображаемого имени может привести к именам кандидатов 604 , 606 , 608 - «Gulprit», «Singh» и «Gulprit Singh», соответственно, которые хранятся в базе данных имен кандидатов 116 для использования в составлении имен приложением обмена сообщениями 102 .

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

Чтобы проиллюстрировать, пример на фиг. 8 изображает поле 802 тела сообщения составляемого ответного сообщения электронной почты, при этом поле 802 тела сообщения включает в себя содержимое 804 исходного сообщения электронной почты. Этот контент , 804, включает строку подписи , 806, отправителя исходного сообщения.Таким образом, синтаксический анализатор , 600, может анализировать контент , 804, , чтобы идентифицировать строку подписи , 806, , используя любой из множества методов синтаксического анализа, а затем анализировать строку подписи , 806 , чтобы идентифицировать потенциальные слова имени. Этот синтаксический анализ может включать в себя, например, отбрасывание или игнорирование слов, предварительно идентифицированных, например, в словаре синтаксического анализа (не показан) как не указывающие имена получателей. При анализе проиллюстрированной строки подписи 806 анализатор 600 проигнорирует слова «CTO», «Motorola», «Mobility» и «Inc.», И таким образом получаем именные слова« Pathy »и« Sunil »как именные слова. Из комбинаций этих именных слов синтаксический анализатор 600 может сгенерировать, например, имена кандидатов 808 , 810 , 812 - «Пати», «Сунил» и «Пати Сунил» соответственно, и сохранить этих кандидатов. имена 808 , 810 , 812 в базе данных кандидатов для использования при составлении имен приложением обмена сообщениями 102 . Этот процесс может быть аналогичным образом применен к синтаксическому анализу содержимого файлов, перечисленных как вложения в поле вложения электронного сообщения.

РИС. 9 иллюстрирует метод косвенной идентификации одного или нескольких имен кандидатов с использованием базы данных , 114, контактов (фиг. 1), которая хранится в электронном устройстве 100 . Как отмечалось выше, адрес сообщения получателя может не содержать информации, полезной для прямой идентификации имен кандидатов, и может не быть отображаемого имени или другого удобного для пользователя поля именования, связанного с адресом сообщения получателя. Однако пользователь мог ранее иметь дело с получателем, связанным с адресом сообщения получателя, и, таким образом, может иметь контактную запись для получателя в базе данных контактов , 114, .Эта контактная запись может включать различную информацию о получателе, такую ​​как имя получателя, должность, работодатель, адрес, номер телефона и различные адреса электронных сообщений для получателя. Соответственно, в таких случаях приложение для обмена сообщениями , 102, или другой компонент электронного устройства 100 на фиг. 1 может использовать модуль поиска контактов для идентификации записи контакта, связанной с контекстом сообщения, идентифицированного в одном или нескольких полях составляемого электронного сообщения, и из этой записи контакта косвенно идентифицировать одно или несколько имен кандидатов.

Чтобы проиллюстрировать, в изображенном примере единственной информацией, идентифицирующей получателя создаваемого сообщения электронной почты, является адрес электронной почты 902 , который имеет специфичную для получателя часть «A100269», которая не отражает имя получателя, связанного с адрес электронной почты 902 . Соответственно, модуль поиска контактов , 900, может использовать эту специфичную для получателя часть для поиска в базе данных контактов , 114 записи контакта, которая имеет поле, которое соответствует специфической для получателя части «A100269».В этом примере база данных контактов , 114, имеет соответствующую запись контакта, связанную с человеком по имени «Гулприт Сингх», и, таким образом, модуль поиска контактов 900 может анализировать поля имени в этой совпадающей записи контакта, чтобы идентифицировать имя. слово 904 слова «Gulprit» и слово фамилии 906 слова Singh. Модуль поиска контактов 900 может затем сохранить эти слова имени 904 , 906 в базе данных имен кандидатов 116 , после чего синтаксический анализатор 600 (ФИГ.6) затем объединяет слова имени в различные имена кандидатов «Gulprit», «Singh» и «Gulprit Singh», или модуль поиска контактов 900 может сгенерировать эти имена кандидатов непосредственно перед их сохранением в базе данных имен кандидатов 116 . Таким образом, как показывает этот пример, модуль поиска контактов , 900, использует внутренний контекст сообщения, а именно адрес электронной почты получателя , 902, , чтобы косвенно идентифицировать одно или несколько имен кандидатов через внешний контекст сообщения, а именно контактную запись в базе данных контактов . 114 .

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

Чтобы проиллюстрировать, в изображенном примере веб-страница, отображаемая веб-браузером, включает в себя читаемый пользователем контент 1002 , который включает в себя текст, инструктирующий представление сделать резервирование на мероприятие, связавшись с «Хэ Юн Ким» по указанному адресу электронной почты «HYK1032» @ gmail.com », и при этом текст адреса электронной почты служит гипертекстовой ссылкой, которая при выборе зрителем через веб-браузер заставляет веб-браузер связываться с приложением для обмена сообщениями 102 , чтобы инициировать составление адресованного электронного сообщения. на «HYK1032 @ gmail.com ». Поскольку с этого адреса электронной почты невозможно проанализировать полезные имена кандидатов, синтаксический анализатор , 600, вместо этого может анализировать читаемое пользователем содержимое веб-страницы в непосредственной близости от гипертекстовой ссылки, чтобы идентифицировать одно или несколько имен кандидатов. В этом примере этот текст поблизости включает фразу 1003 «Чтобы ответить на приглашение на мероприятие, пожалуйста, свяжитесь с Хэ Юн Ким по адресу [email protected]», которую синтаксический анализатор 600 может проанализировать, чтобы идентифицировать слова имени «Hae , »« Юн »и« Ким », и которые могут быть объединены, например, в имена кандидатов 1004 , 1006 , 1008 и 1010 -« Хэ »,« Юн »,« Хэ Yun »и« Kim », соответственно, и хранятся в базе данных кандидатов 116 .

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

РИС. 11 иллюстрирует пример реализации электронного устройства 100 по фиг. 1 в соответствии по меньшей мере с одним вариантом осуществления настоящего раскрытия.В изображенном примере электронное устройство , 100, включает в себя по меньшей мере один процессор 1102 (например, центральное устройство обработки или ЦП), один или несколько энергонезависимых машиночитаемых носителей данных, таких как системная память 1104 или другой запоминающее устройство 1106 (например, флэш-память, оптический или магнитный дисковод, твердотельный жесткий диск и т. д.), сетевой интерфейс 1108 (например, интерфейс беспроводной локальной сети (WAN) или проводной интерфейс Ethernet), и пользовательский интерфейс (UI) 1110 , подключенный через одну или несколько шин , 1112, или другие межсоединения.UI 1110 включает в себя, например, устройство отображения 1114 и клавиатуру или сенсорный экран 1116 , а также другие компоненты ввода / вывода 1118 , такие как динамик или микрофон, для приема ввода от или предоставить информацию пользователю.

Процессор 1102 выполняет набор исполняемых инструкций, хранящихся на машиночитаемом носителе данных, таком как системная память 1104 или флэш-память, при этом набор исполняемых инструкций представляет одно или несколько программных приложений 1120 , например как приложение обмена сообщениями 102 на фиг.1. Программные приложения 1120 при выполнении манипулируют процессором 1102 для выполнения различных программных функций для реализации по меньшей мере части описанных выше методов, предоставляют визуальную информацию через устройство отображения 1114 , реагируют на пользовательский ввод через сенсорный экран 1116 и т.п. Таким образом, большая часть изобретательских функциональных возможностей и многие из изобретательских принципов, описанных выше, хорошо подходят для реализации с программными программами или в них.Ожидается, что специалист с обычными навыками, несмотря на возможные значительные усилия и множество вариантов дизайна, мотивированных, например, доступным временем, текущими технологиями и экономическими соображениями, руководствуясь концепциями и принципами, раскрытыми в данном документе, легко сможет создать такое программное обеспечение. инструкции и программы минимальные эксперименты. Следовательно, в интересах краткости и минимизации любого риска затруднения понимания принципов и концепций в соответствии с настоящим раскрытием, дальнейшее обсуждение такого программного обеспечения, если таковое имеется, будет ограничено основополагающим в отношении принципов и концепций в предпочтительных вариантах осуществления. .

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

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

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

«Болеть» - морфемный разбор слова, разбор по составу (корневой суффикс, префикс, окончание). «Больной»

Схема разбора композиции, чтобы заболеть:

больной

Разбор слова композиция.

Состав слова «болеть»:

Соединительная гласная: отсутствует

Постфикс: отсутствует

Морфемы - части слова, чтобы повредить

 > Импорт данных.Char 
> импортировать Data.Functor 
> импортировать Control.Monad  

  ** Не бойтесь монад **
  

  тип Parser = String -> StructuredObject  

  Вещь: правило 
; 
 Whatsit: rule 
; 
  

  Вещи: Вещи: Вещи {...} 
 EmptyThingy {...} 
; 
 Whatsits: Whatsit Whatsits {...} 
 EmptyWhatsit {...} 
; 
  

  тип Parser = String -> (StructuredObject, String)  

  "2-3-4"  

  Минус (Минус 2 3) 4  

  Минус 2 (Минус 3 4)  

 > Newtype Parser a = P (String -> [(a, String)])  

 > doParse (P p) s = p s  

 > oneChar :: Parser Char 
> oneChar = P (\ cs -> case cs of 
> c: cs '-> [(c, cs')] 
> _ -> [])  

 > twoChar0 = P (\ cs -> case cs of 
> c1: c2: cs '-> [((c1, c2), cs')] 
> _ -> [])  

 > twoChar9 = oneChar `pairP` oneChar  

  ghci> doParse oneChar "эй!" 
 [('h', "ey!")] 
 ghci> doParse oneChar "" 
 [] 
  

  pairP :: Parser a -> Parser b -> Parser (a, b) 
 pairP p1 p2 = P (\ cs -> 
 [((x, y), cs '') | (x, cs ') <- doParse p1 cs, 
 (y, cs '') <- doParse p2 cs '] 
)  

  twoChar :: Parser (Char, Char) 
 twoChar = P (\ cs -> case cs of 
 c1: c2: cs '-> [((c1, c2), cs')] 
 _ -> [] )  

 > twoChar = pairP oneChar oneChar  

  ghci> doParse twoChar "эй!" 
 [(('h', 'e'), "y!")] 
 ghci> doParse twoChar "" 
 [] 
  

  Newtype Parser a = P (String -> [(a, String)])  

  тип ST a = состояние -> (a, состояние)  

 : тип returnP 
 returnP :: a -> Parser a  

 > returnP x = P (\ cs -> [(x, cs)])  

 : введите bindP 
 bindP :: Parser a -> (a -> Parser b) -> Parser b  

 > p1 `bindP` fp2 = P (\ cs -> 
> [(y, cs '') | (x, cs ') <- doParse p1 cs 
>, (y, cs' ') <- doParse (fp2 x) cs '])  

 > экземпляр Monad Parser, где 
> (>> =) = bindP 
> return = returnP  

 > pairP px py = do x <- px 
> y <- py 
> return (x, y)  

 > failP = P $ const []  

 > satP :: (Char -> Bool) -> Parser Char 
> satP p = do 
> c <- oneChar 
> если p c, то вернуть c else failP  

 > строчные буквы P = satP isAsciiLower  

  ghci> doParse (satP ('h' ==)) "mugatu" 
 [] 
 ghci> doParse (satP ('h' ==)) "hello" 
 [('h', "ello")]  

 > alphaChar = satP isAlpha 
> digitChar = satP isDigit  

 > digitInt = do 
> c <- digitChar 
> return ((читать [c]) :: Int)  

  ghci> doParse digitInt "92" 
 [(9, "2")] 
 ghci> doParse digitInt "cat" 
 [] 
  

 > символ c = satP (== c)  

 > chooseP :: Parser a -> Parser a -> Parser a  

 > p1 `chooseP` p2 = P (\ cs -> doParse p1 cs ++ doParse p2 cs)  

 > alphaNumChar = alphaChar `chooseP` digitChar  

  ghci> doParse alphaNumChar "cat" 
 [('c', "at")] 
 ghci> doParse alphaNumChar "2cat" 
 [('2', "cat")] 
 ghci> doParse alphaNumChar "2at" 
 [('2', «в»)]  

 > grabn :: Int -> Parser String 
> grabn n | n <= 0 = return "" 
> | в противном случае = do c <- oneChar 
> cs <- grabn (n-1) 
> return (c: cs)  

 > grab2or4 = grabn 2 `chooseP` grabn 4  

  ghci> doParse grab2or4 "mickeymouse" 
 [("mi", "ckeymouse"), ("mick", "eymouse")]  

  ghci> doParse grab2or4 "mic" 
 [("mi", "c")] 
 ghci> doParse grab2or4 "m" 
 [] 
  

 > intOp = плюс `chooseP` минус` chooseP` умножить на `chooseP` div 
> где плюс = char '+' >> return (+) 
> minus = char '-' >> return (-) 
> раз = char '*' >> return (*) 
> div = char '/' >> return div  

 > calc = do x <- digitInt 
> op <- intOp 
> y <- digitInt 
> return $ x `op` y  

  ghci> doParse calc "8/2" 
 [(4, "")] 
 ghci> doParse calc "8 + 2cat" 
 [(10, "cat")] 
 
 ghci> doParse calc "8 / 2cat "
 [(4," cat ")] 
 
 ghci> doParse calc" 8-2cat "
 [(6," cat ")] 
 
 ghci> doParse calc" 8 * 2cat "
 [(16," cat ")] 
  

 > строка :: строка -> синтаксический анализатор строки  

  строка "" = return "" 
 строка (c: cs) = do char c 
 строка cs 
 return $ c: cs  

 > строка = mapM char  

  ghci> doParse (строка "mic") "mickeyMouse" 
 [("mic", "keyMouse")] 
 ghci> doParse (строка "mic") "donald duck" 
 [] 
  

 > manyP :: Parser a -> Parser [a] 
> manyP p = many1 `chooseP` many0 
> где many0 = return [] 
> many1 = do x <- p 
> xs <- manyP p 
> возврат (x: xs)  

  ghci> doParse (manyP digitInt) "123a" 
 [([], "123a"), ([1], "23a"), ([1, 2], "3a"), ([1, 2 , 3], «а»)]  

 > (<|>) :: Parser a -> Parser a -> Parser a 
> p1 <|> p2 = P $ \ cs -> case doParse (p1 `chooseP` p2) cs of 
> [] - > [] 
> x: _ -> [x] 
>  

 > mmanyP :: Parser a -> Parser [a] 
> mmanyP p = mmany1 <|> mmany0 
> где mmany0 = return [] 
> mmany1 = do x <- p 
> xs <- mmanyP p 
> возврат (x: xs)  

  ghci> doParse (manyP digitInt) «123a» 
 [([1,2,3], «a»), ([1,2], «3a»), ([1], «23a»), ([], «123a»)] 
 ghci> doParse (mmanyP digitInt) «123a» 
 [([1,2,3], «a»)] 
  

  oneInt :: Parser Integer 
 oneInt = do xs <- mmanyP digitChar 
 return $ ((read xs) :: Integer)  

  (a -> b) -> Parser a -> Parser b  

 > instance Functor Parser, где 
> fmap f p = do x <- p 
> return (f x)  

 > oneInt :: Parser Int 
> oneInt = читать `fmap` mmanyP digitChar  

  ghci> doParse oneInt "123a" 
 [(123, "a")]  

 > calc0 :: Parser Int 
> calc0 = binExp <|> oneInt 
> где binExp = do x <- oneInt 
> o <- intOp 
> y <- calc0 
> return $ x `o` y  

  ghci> doParse calc0 "1 + 2 + 33" 
 [(36, "")] 
 ghci> doParse calc0 "11 + 22-33" 
 [(0, "")] 
  

  ghci> doParse calc0 "11 + 22-33 + 45" 
 [(-45, "")]  

  11 + (22 - (33 + 45))  

 > calc1 :: Parser Int 
> calc1 = binExp <|> oneInt 
> где binExp = do x <- calc1 
> o <- intOp 
> y <- oneInt 
> return $ x `o` y  

  ghci> doParse calc1 "2 + 2"  

  ghci> doParse calc0 "10 * 2 + 100" 
 [(1020, "")]  

  10 * (2 + 100)  

 > addOp = plus `chooseP` минус 
> где plus = char '+' >> return (+) 
> minus = char '-' >> return (-) 
> 
> mulOp = times` chooseP` div 
> где times = char '*' >> return (*) 
> div = char '/' >> return div  

 > pP `chain` opP 
> = recP <|> pP 
> где recP = do x <- pP 
> o <- opP 
> y <- (pP` chain` opP) 
> return $ x ` o` y  

 > sumE = addE <|> prodE 
> где addE = do x <- prodE 
> o <- addOp 
> y <- sumE 
> return $ x `o` y 
> 
> prodE = mulE <| > factorE 
> где mulE = do x <- factorE 
> o <- mulOp 
> y <- prodE 
> return $ x `o` y 
> 
> factorE = parenE <|> oneInt 
> где parenE = do char '(' 
> n <- sumE 
> char ')' 
> return n  

  ghci> doParse sumE "10 * 2 + 100" 
 [(120, "")] 
 ghci> doParse sumE "10 * (2 + 100)" 
 [(1020, "")] 
  

  ПРОДУКТ + <ПРОДУКЦИЯ + <ПРОДУКЦИЯ + ... <ПРОДУКТ >>>  

  factorE * >>  

  ghci> doParse sumE "10-1-1" 
 [(10, "")]  

  sumE = addE <|> prodE 
 где addE = do x <- sumE 
 o <- addOp 
 y <- prodE 
 return $ x `o` y  

 > sumE1 = prodE1 >> = addE1 
> где addE1 x = grab x <|> return x 
> grab x = do o <- addOp 
> y <- prodE1 
> addE1 $ x `o` y 
> 
> prodE1 = factorE1 >> = mulE1 
> где mulE1 x = grab x <|> return x 
> grab x = do o <- mulOp 
> y <- factorE1 
> mulE1 $ x `o` y 
> 
 > factorE1 = parenE <|> oneInt 
> где parenE = do char '(' 
> n <- sumE1 
> char ')' 
> return n  

  ghci> doParse sumE1 "10-1-1" 
 [(8, "")]  

 > p `chainl` pop = p >> = rest 
> где rest x = grab x <|> return x 
> grab x = do o <- pop 
> y <- p 
> rest $ x` o `y  

 > parenP l p r = do char l 
> x <- p 
> char r 
> return x  

 > sumE2 = prodE2 `chainl` addOp 
> prodE2 = factorE2` chainl` mulOp 
> factorE2 = parenP '(' sumE2 ')' <|> oneInt  

  ghci> doParse sumE2 "10-1-1" 
 [(8, "")] 
 ghci> doParse sumE2 "10 * 2 + 1" 
 [(21, "")] 
 
 ghci> doParse sumE2 " 10 + 2 * 1 "
 [(12," ")]