Задача


Привет, Хабр! Увлёкся я навыками для Алисы и стал думать, какую пользу они бы могли принести. На площадке много разных прикольных игр (в том числе мои), но вот захотелось сделать рабочий инструмент, который действительно нужен в голосовом исполнении, а не просто копирует существующего чат-бота с кнопками.


Голос актуален тогда, когда либо руки заняты, либо нужно выполнять много последовательных операций, особенно на экране телефона. Так возникла идея навыка, который по одной команде выделяет из текста указание на дату и время и добавляет событие с этим текстом в Google Calendar. Например, если пользователь скажет Послезавтра в 11 вечера будет красивый закат, то в календарь на послезавтра в 23:00 уходит строка Будет красивый закат.


Под катом описание алгоритма работы библиотеки Hors: распознавателя даты и времени в естественной русской речи. Хорс — это славянский бог солнца.


Github | NuGet


Существующие решения


dateparser на Python
Заявлена поддержка русского языка, но на русском библиотека не справляется даже с базовыми вещами:


>>> import dateparser
>>> dateparser.parse(u'13 января 2015 г. в 13:34')
datetime.datetime(2015, 1, 13, 13, 34)
>>> dateparser.parse(u'через неделю')
>>> dateparser.parse(u'в следующий четверг в 9 вечера')
>>> dateparser.parse(u'13 октября')
datetime.datetime(2019, 10, 13, 0, 0)
>>> dateparser.parse(u'13 октября в 9 вечера')

chronic на Ruby
Известная рубистам библиотека, которая, говорят, делает свою работу отлично. Но поддержка русского не обнаружена.


Google Assistant
Раз мы говорим о добавлении в Google Calendar голосом, спрашивается, а почему бы не воспользоваться Ассистентом? Можно, но идея проекта в том, чтобы делать работу одной фразой без лишних телодвижений и нажатий. И чтобы делать это надёжно. В Ассистенте пока есть проблемы с этим:



Предустановки


Я писал библиотеку на .NETStandard 2.0 (C#). Поскольку изначально библиотека делалась под Алису, то все числительные в тексте полагаются именно числами, потому что Алиса делает такое преобразование автоматически. Если у вас числительные строками, то здесь есть замечательная статья пользователя Doomer3D о том, как превращать слова в числа.


Морфология


При работе с голосовым вводом самым надёжным способом отличать правильные слова от неправильных является использование словоформ. Подробнее мы с другом говорили об этом в видеоуроке для Школы Алисы от Яндекса. В данной же статье я оставлю за кадром работу со словоформами. В коде будут встречаться вот такие конструкции:


Morph.HasOneOfLemmas(t, "прошлый", "прошедший", "предыдущий");

Эта функция возвращает true, если слово t является любой формой одного из трёх последующих слов, например: прошлого, прошедшие, предыдущих.


Теория


Чтобы понять, как вылавливать в тексте даты, нужно перечислить типовые фразы, которые мы используем для обозначения дат в реальных беседах. Например:


завтра пойду гулять
завтра вечером пойду гулять
в следующий четверг иду в кино
в следующий четверг в 9 вечера иду в кино
21 марта в 10 утра совещание


Мы видим, что слова в целом делятся на три вида:


  1. Те, которые всегда относятся к датам и времени (названия месяцев и дней)
  2. Те, которые относятся к дате и времени при определённом положении относительно других слов ("день", "вечер", "следующий", числа)
  3. Те, которые никогда не относятся к дате и времени

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


Готовим строку


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


Токен (слово) Символ, на который заменяем
"год" Y
название месяца M
название дня недели D
"назад" b
"спустя" l (lower L)
"через" i
"выходной" W
"минута" e
"час" h
"день" d
"неделя" w
"месяц" m
"прошлый", "прошедший", "предыдущий" s
"этот", "текущий", "нынешний" u
"ближайший", "грядущий" y
"следующий", "будущий" x
"послезавтра" 6
"завтра" 5
"сегодня" 4
"вчера" 3
"позавчера" 2
"утро" r
"полдень" n
"вечер" v
"ночь" g
"половина" H
"четверть" Q
"в", "с" f
"до", "по" t
"на" о
"число" #
"и" N
число больше 1900 и меньше 9999 1
неотрицательное число меньше 1901 0
уже обработанная алгоритмом дата @
любой другой токен _

ParserExtractors.cs

Keywords.cs

Вот что получается для строк, которые мы упоминали:


Строка Результат
завтра пойду гулять 5__
завтра вечером пойду гулять 5v__
в следующий четверг иду в кино fxD_f_
в следующий четверг в 9 вечера иду в кино fxDf0v_f_
21 марта в 10 утра совещание 0Mf0r_

Распознавание


— О, ужас! — скажете вы, — Стало только хуже! Такую абракадабру и человек понять не сможет. Да, пришлось пойти на некоторый компромисс между удобством чтения человеком и удобством работы с регулярками, ниже увидите, как именно.


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


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


Recognizer.cs

Причем, обработчики нужно вызывать в правильном порядке: от более "уверенных" к менее. Например, в самом начале нужно запустить обработчики, связанные со "строгими" словами, которые точно относятся к датам: названия дней, месяцев, слова вроде "завтра", "послезавтра" и так далее. А в конце обработчики, которые пытаются по необработанным остаткам определить, а может ли там быть ещё что-то, связанное с датой.


Например:


Число и месяц


"((0N?)+)(M|#)"; // 24, 25, 26... и 27 января/числа

Тут начинает проявляться прелесть применения регулярных выражений. Достаточно простым образом мы обозначили сложную последовательность токенов: ненулевое количество неотрицательных чисел меньше 1901 идут друг за другом, возможно, разделяясь союзом "и", а за ними идёт либо название месяца, либо слово "число".


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


DaysMonthRecognizer.cs

Промежуток времени


"(i)?((0?[Ymwdhe]N?)+)([bl])?";
// (через) год и месяц и 2 дня 4 часа 10 минут (спустя/назад)

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


if (match.Groups[1].Success ^ match.Groups[4].Success)

Где ^ это исключающее ИЛИ.


TimeSpanRecognizer.cs

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


Год


"(1)Y?|(0)Y"; // [в] 15 году/2017 (году)

Не могу ещё раз не отметить удобство подхода с регулярками. Опять же простым выражением мы обозначали сразу варианты: пользователь называет число, похожее на год, но без слова "год", либо пользователь называет двузначное число (которое может быть и датой), но добавляет слово "год", и появляется поддержка выражений "в 18 году", впрочем, имеется ли ввиду 1918 или 2018 мы не знаем, поэтому полагаем, что 2018.


YearRecognizer.cs

Время


"([rvgd])?([fot])?(Q|H)?(h|(0)(h)?)((0)e?)?([rvgd])?";
// (в/с/до) (половину/четверть) час/9 (часов) (30 (минут)) (утра/дня/вечера/ночи)

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


TimeRecognizer.cs

Все обработчики в порядке применения


Система модульная, подразумевается, что можно добавлять/удалять обработчики, менять их порядок и так далее. Я сделал 11 таких (сверху вниз в порядке применения):


Обработчик Regex Пример строки
HolidaysRecognizer.cs 1 W                                                    выходной, выходные
DatesPeriodRecognizer.cs f?(0)[ot]0(M|#) с 26 до 27 января/числа
DaysMonthRecognizer.cs ((0N?)+)(M|#) 24, 25, 26… и 27 января/числа
MonthRecognizer.cs ([usxy])?M [в] (прошлом/этом/следующем) марте
RelativeDayRecognizer.cs [2-6] позавчера, вчера, сегодня, завтра, послезавтра
TimeSpanRecognizer.cs (i)?((0?[Ymwdhe]N?)+)([bl])? (через) год и месяц и 2 дня 4 часа 10 минут (спустя/назад)
YearRecognizer.cs (1)Y?|(0)Y [в] 15 году/2017 (году)
RelativeDateRecognizer.cs ([usxy])([Ymwd]) [в/на] следующей/этой/предыдущей год/месяц/неделе/день
DayOfWeekRecognizer.cs ([usxy])?(D) [в] (следующий/этот/предыдущий) понедельник
TimeRecognizer.cs ([rvgd])?([fot])?(Q|H)?(h|(0)(h)?)((0)e?)?([rvgd])? (в/с/до) (половину/четверть) час/9 (часов) (30 (минут)) (утра/дня/вечера/ночи)
PartOfDayRecognizer.cs (@)?f?([ravgdn])f?(@)? (дата) (в/с) утром/днём/вечером/ночью (в/с) (дата)

1 Этот обработчик заменяет слово "выходной" на "суббота" и "выходные" на "суббота и воскресенье", чтобы передать обработчику по названию дней


Сшиваем воедино


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


Фиксация в нашем случае — это битовая маска внутри каждого токена даты-времени, которая показывает, какие элементы даты и времени в нём заданы.


public enum FixPeriod
{
    None          = 0,
    Time          = 1,
    TimeUncertain = 2,
    Day           = 4,
    Week          = 8,
    Month         = 16,
    Year          = 32
}

TimeUncertain — фиксация для обозначения времени, после которого может следовать уточнение, например вечера/утра. Нельзя сказать 18 часов утра, но можно сказать 6 вечера, поэтому число 6 обладает как бы меньшей "уверенностью" в том, какое время оно обозначает, чем число 18.


Фраза Фиксация Маска
26 марта 2019 года год, мес, нед, ден, врм1, врм2 111100
26 числа год, мес, нед, ден, врм1, врм2 000100
понедельник год, мес, нед, ден, врм1, врм2 000100
следующий понедельник год, мес, нед, ден, врм1, врм2 111100
на следующей неделе год, мес, нед, ден, врм1, врм2 111000
в 9 часов год, мес, нед, ден, врм1, врм2 000010
в 9 часов вечера год, мес, нед, ден, врм1, врм2 000011

Дальше воспользуемся двумя правилами:


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


Таким образом, если пользователь говорит в понедельник в 9 вечера, то токен в понедельник, где задан только день, объединяется с токеном в 9 вечера, где задано время. Но если он скажет в марте 10 и 15 числа, то последний токен 15 числа просто займёт месяц март у предыдущего токена.


Объединение тривиально, а с заимствованием поступим просто. Будем называть базовой дату, для которой мы занимаем, и второстепенной вторую, у которой мы хотим что-то занять. Затем скопируем второстепенную дату и оставим только те биты, которых нет у базовой:


var baseDate = data.Dates[firstIndex];
var secondDate = data.Dates[secondIndex];
var secondCopy = secondDate.CopyOf();

secondCopy.Fixed &= (byte)~baseDate.Fixed;

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


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


Collapse.cs

Отдельно нужно учесть пару нюансов:


  • У базовой даты может быть зафиксирован день, но не зафиксирована неделя. В таком случае нужно взять неделю из поглощаемой даты, но сам день недели из базовой.
  • Однако, если у поглощаемой даты не зафиксирован день, но зафиксирована неделя, нам нужно взять из неё день (то есть год+месяц+число) и задать таким способом неделю, потому что отдельной сущности "Неделя" в объекте DateTime нет.
  • Если у базовой даты зафиксировано TimeUncertain, а у поглощаемой Time, и при этом у поглощаемой количество часов больше 12, а у базовой меньше, то к базовой нужно прибавить 12 часов. Потому что нельзя сказать с 5 до 17 вечера. Время "неуверенной" даты не может быть из одной половины дня, если время "уверенной" даты рядом с ней — из другой половины дня. Люди так не говорят. Если же мы сказали фразу с 5 утра до 17, то здесь обе даты обладают "уверенным" временем, и проблемы не возникает.

После объединения, если у каких-то дат остались пустые биты, мы заменяем их на значения из текущей даты пользователя: например, если пользователь не назвал год, речь идёт о текущем годе, если не назвал месяц, то о текущем месяце и так далее. Разумеется в параметр "текущая дата" можно передать любой объект DateTime для гибкости.


Костыли


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


  • Объединение дат производится отдельно для токенов, которые начинаются с "в\с\со" и отдельно для токенов, которые начинаются с "по\до\на". Потому что, если пользователь назвал период, то объединять между собой токены из даты начала и даты конца нельзя.
  • Не стал вводить отдельный уровень фиксации для дня недели, потому что нужен он ровно в одном месте: там где явно задан словом с названием дня недели. Сделал флаг для этого.
  • Отдельным прогоном объединяются даты, которые стоят на некотором расстоянии друг от друга. Это контролируется параметром collapseDistance, по умолчанию равным 4 токена. То есть, например, сработает фраза: Послезавтра встреча с другом в 12. Но не сработает: послезавтра встреча с моим любимым и замечательным другом в 12.

Итог



  • Библиотеку можете использовать в своих проектах. Она справляется уже с многими вариантами, но я её дорабатываю и рефакторю. Пулл-реквесты с тестами приветствуются. И вообще, придумайте тест, который звучит реалистично (как люди говорят в жизни), но при этом ломает библиотеку.
  • Live demo на .NET Fiddle тоже работает, хотя код подчёркивается якобы с ошибками, но запускается. Внизу в консоли можно вводить фразы на русском, не забывая о том, что числительные должны быть числами.
  • Та же демка в виде консольного приложения

Вживую получилось так:


Комментарии (32)


  1. bvn13
    16.10.2019 14:19

    Почему-то распозналось по-разному.


    через 13 дней
      text: 
      date: SpanForward, NoTime, 10/29/2019 12:00:00 AM - 10/29/2019 11:59:59 PM
    
    спустя 13 дней
      text: Спустя
      date: Fixed, HasTime, 10/16/2019 1:00:00 PM

    upd. Понятно, почему именно :)


    1. bvn13
      16.10.2019 14:23

      следующий пример


      на следующей неделе во вторник
        text: 
        date: Fixed, NoTime, 10/22/2019 12:00:00 AM - 10/22/2019 11:59:59 PM
      
      через неделю во вторник
        text: 
        date: SpanForward, NoTime, 10/23/2019 12:00:00 AM - 10/23/2019 11:59:59 PM
        date: SpanForward, NoTime, 10/22/2019 12:00:00 AM - 10/22/2019 11:59:59 PM


      1. Enfriz Автор
        16.10.2019 16:27

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


        1. mokaton
          16.10.2019 17:44

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


          1. Enfriz Автор
            16.10.2019 17:46

            Ну окей, дискуссионно. По моему опыту так не говорят. Какой смысл мне был поддержать кучу разговорных фраз и не поддержать эту, если бы я её встречал в реальной жизни? :) Буду изучать логи работы с навыком, вносить в библиотеку правки.


            1. mokaton
              16.10.2019 17:50

              В любом случае — то что получилось, это круто! Буду использовать ваши либу в своём проекте, как раз «собрался с мыслями».


          1. Enfriz Автор
            16.10.2019 17:49

            Но тогда остаётся вопрос. Если сегодня воскресенье, то "через неделю во вторник" это через 2 дня или через 9 дней? Если через 9, то в какой момент переход? А если сегодня пятница? Очень неоднозначно.


            1. mokaton
              16.10.2019 17:51

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


    1. Enfriz Автор
      16.10.2019 16:26

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


    1. varnav
      16.10.2019 19:15

      Кстати больно смотреть на 10 число 29-го месяца. Может сделать выдачу в ISO формате даты по умолчанию?


      1. Enfriz Автор
        16.10.2019 19:18

        Это в .NET Fiddle так, потому что CultureInfo стоит американская. Но я поправлю, да. Библиотека все равно для русского языка.


        1. varnav
          16.10.2019 19:26

          Когда программа учитывает локаль — это иногда бывает скорее плохо чем хорошо. Особенно если видишь дату вроде 3/10/2019 в отрыве от контекста.


          1. Enfriz Автор
            16.10.2019 19:27

            Имел ввиду, я поправлю для демки на фиддле. В самой библиотеке трогать не буду, конечно.


  1. Warrangie
    16.10.2019 15:06

    А можно ли как-то использовать алису для автоматического распознавания текста и последующей отправки в какой-нибудь api?


    1. Enfriz Автор
      16.10.2019 16:25

      Да, у меня есть навык и для этого. Называется "Мой Исполнитель" )


  1. pewpew
    16.10.2019 16:09

    послезавтра вечером в 8 иду в кино

    Это и человеку-то не понять. В 8 выйдет в сторону кинотеатра или в 8 начало? Без контекста или известных умолчаний не понять.


    1. Enfriz Автор
      16.10.2019 16:52

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


  1. and7ey
    16.10.2019 16:13
    +1

    А чем именованные сущности Яндекса не подошли? Там вроде всё нужное делается "из коробки".


    https://yandex.ru/dev/dialogs/alice/doc/nlu-docpage/#nlu__datetime


    1. Enfriz Автор
      16.10.2019 16:28

      Они чуть меньше понимают, чем я бы хотел.


      1. vitalets
        16.10.2019 16:53

        А можно пару примеров, чего они не понимают?


        1. Enfriz Автор
          16.10.2019 23:37

          Тут не ловит 'утром'
          "request": {
              "command": "завтра утром иду гулять",
              "nlu": {
                "entities": [
                  {
                    "tokens": {
                      "end": 1,
                      "start": 0
                    },
                    "type": "YANDEX.DATETIME",
                    "value": {
                      "day": 1,
                      "day_is_relative": true
                    }
                  }
                ],
                "tokens": [
                  "завтра",
                  "утром",
                  "иду",
                  "гулять"
                ]
              },
              "original_utterance": "завтра утром иду гулять",
              "type": "SimpleUtterance"
            }
          


  1. shibanovan
    16.10.2019 16:51

    Эх… вот бы такое в питон :(


    1. mokaton
      16.10.2019 17:49

      В чем сложность «перенести»? Вроде никакой черной магии и всё в опенсорсе ))


  1. WhiteVolfVanilio
    16.10.2019 16:51

    вау) круто) пригодится, спасибо)


  1. inoyakaigor
    16.10.2019 17:23

    Очень круто! Но кое-какие речевые обороты остаются необработанными:


    1. Enfriz Автор
      16.10.2019 17:27

      Да, для таких я не сделал пока обработчик, буду добавлять.


  1. Aiditz
    16.10.2019 23:29
    +1

    Вот еще пара вариантов:

    через полчаса (полгода и т.п.)
    text: Через полчаса


    зимой 2012
    text: Зимой
    date: Period, NoTime, 1/1/2012 12:00:00 AM - 12/31/2012 11:59:59 PM


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

    месяц назад
    text:
    date: SpanBackward, NoTime, 9/16/2019 12:00:00 AM - 9/22/2019 11:59:59 PM


    через месяц
    text:
    date: SpanForward, NoTime, 11/11/2019 12:00:00 AM - 11/17/2019 11:59:59 PM


    И еще нужен специальный обработчик для тех, кто хочет сходить в Эрмитаж бесплатно :)

    в 3 четверг месяца
    text: Месяца
    date: Fixed, HasTime, 10/17/2019 3:00:00 PM

    в 3 четверг ноября
    text:
    date: Fixed, HasTime, 11/7/2019 3:00:00 PM


    1. Enfriz Автор
      16.10.2019 23:45

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

      As intended тут. Я должно думал, как распознавать через %название_промежутка%. И решил, что буду понижать на один уровень фиксации:

      • «через год» без дальнейшего уточнения — это промежуток длиной месяц
      • «через месяц» — неделю
      • «через неделю» — день

      Логика такая: если бы я спросил своего секретаря «Какие у меня встречи через месяц?», то точно не имел бы ввиду один конкретный день +30 дней относительно сегодня, а имел бы ввиду некоторый промежуток примерно через месяц.


      1. Aiditz
        16.10.2019 23:54

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


        1. Enfriz Автор
          17.10.2019 00:10

          Мне с трудом представляется, что, если я сегодня 17-го октября скажу «Записаться к стоматологу через месяц», то я буду иметь ввиду «17-е ноября ровно». Скорее всего я буду иметь ввиду некоторый промежуток примерно через месяц :)

          И «Поздравить друга через год» сказанное ровно в день рождения друга — так бывает? Но в любом случае, буду анализировать статистику использования и смотреть, как реально люди говорят. Может, я не прав.


  1. vagon333
    17.10.2019 06:14

    Можете посоветовать библиотеку трансляции русской речи в текст?
    Есть желание встроить в проект простое голосовое управление на русском.
    Может знакомы?