Как Apple находит дату, время и адреса в электронных письмах?

129

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

Наивный способ сделать это - иметь много регулярных выражений и запускать их все. Однако я не собираюсь хорошо масштабироваться и будет работать только для определенного языка или формата даты и т. Д. Я думаю, что Apple должна использовать некоторую концепцию машинного обучения для извлечения сущностей (20:00, 20:00, 20:00, 08:00, 20:00, 20:00, 20:00, 2000 и т. Д.).

Есть идеи, как Apple может так быстро извлекать объекты в своем почтовом клиенте? Какой алгоритм машинного обучения вы бы применили для выполнения такой задачи?

machine-learning nlp information-extraction named-entity-recognition Мартин
источник
5
Я тоже думал об этом, особенно о трюке с регулярным выражением. Я знаю, что у них есть патент, так что, может быть, ты попробуешь его поискать. Однако мне это тоже было бы очень интересно. +1
Thomas Jungblut
15
На самом деле трюк с регулярным выражением, вероятно, уловит 99% случаев с очень низкой частотой ошибок. И это очень быстро, если вы хорошо оптимизируете регулярные выражения. Поэтому я не удивлюсь, если это действительно просто набор регулярных выражений.
ВЫЙТИ - Anony-Mousse

Ответы:

153

Вероятно, они используют для этого методы извлечения информации .

Вот демонстрация инструмента SUTime из Стэнфорда:

http://nlp.stanford.edu:8080/sutime/process

Вы должны извлечь атрибуты о n-граммах (последовательных словах) в документе:

  • numberOfLetters
  • numberOfSymbols
  • длина
  • previousWord
  • NextWord
  • nextWordNumberOfSymbols
    ...

А затем используйте алгоритм классификации и скормите ему положительные и отрицательные примеры:

Observation  nLetters  nSymbols  length  prevWord  nextWord isPartOfDate  
"Feb."       3         1         4       "Wed"     "29th"   TRUE  
"DEC"        3         0         3       "company" "went"   FALSE  
...

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

Он может изучить такие правила, как

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

Вот достойное видео инженера Google на эту тему.

Нил МакГиган
источник
2
el шеф, по вашему мнению, какая модель лучше всего подойдет для этого? Байесовский?
Мартин
5
Я почти уверен, что такой подход не будет работать лучше, чем, скажем, f-мера прибл. 0,9. (Заметьте, это просто ощущение, я могу ошибаться). С другой стороны, я бы исключил наивный подход к кодированию всех распространенных форматов, чтобы он работал лучше (возможно, 0,99+, учитывая, что наиболее частые форматы никогда не будут пропущены) и чтобы было быстрее реализовать + во время выполнения.
b.buchhold
@ b.buchhold, возможно, но тогда вам придется проделать такой же объем работы для следующего языка и следующего языка, тогда как мое решение является общим.
Neil McGuigan
@ Нил МакГиган, правда. Но вам нужно будет предоставить множество обучающих данных для всех этих форматов / языков, что намного сложнее.
b.buchhold
@NeilMcGuigan большое спасибо за этот ответ. Я сделал то, что вы упомянули выше, но не смог понять, как обучить эти данные и какой алгоритм. Я не могу использовать дерево решений, так как атрибуты не одного типа
chopss
111

Это технология, которую Apple разработала очень давно Apple Data Detectors. Вы можете прочитать больше об этом здесь:

http://www.miramontes.com/writing/add-cacm/

По сути, он анализирует текст и обнаруживает шаблоны, которые представляют определенные фрагменты данных, а затем применяет к ним контекстные действия ОС. Это аккуратно.

jeffehobbs
источник
24
Это правильный ответ. Другие ответы могут рассказать вам, как вы могли бы это сделать, но этот говорит вам, как это делает Apple .
LaC,
2
не могли бы мы иметь немного больше деталей в описании? одинарные ссылки не добавляют так много
shigeta
14
А, вот откуда все хиты на моем веб-сайте :) FWIW, я был руководителем проекта Apple Data Detectors еще во времена ATG; что я могу добавить, так это то, что это была технология только для OS 8 и 9 - она ​​никогда не переходила на OS X. Очевидно, что некоторые похожие вещи происходят в OS X и IOS, и, хотя я больше не в Apple и поэтому не могу сказать, я не удивлюсь, если архитектура будет немного другой. Тем не менее, я ожидаю, что в его основе все еще лежит какая-то система грамматики / синтаксического анализа. В наши дни компьютеры работают быстро, а простые грамматики довольно дешевы.
Джим Миллер,
18

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

https://www.google.com/#hl=en&safe=off&sclient=psy-ab&q=timebank+timeml+timex

https://www.google.com/#hl=en&safe=off&sclient=psy-ab&q=temporal+expression+tagger

Грегори Мартон
источник
+1 за то, что сказал, что такое название «идентифицирующих выражений, относящихся ко времени» в некоторой / большей части литературы
arturomp
6

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

hburde
источник
2
Похоже, этот NSDataDetectorкласс - результат усилий Apple, приложенных для его реализации. Вопрос в том, как класс работает внутри?
Ole Begemann
3
он находится в NSRegularExpression.h, поэтому вполне возможно, что это, как уже указывалось, просто набор регулярных выражений.
riffraff
3

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

Ставрос Корокитакис
источник
Выдержка из Мирамонтеса «Жестко запрограммировать распознаватель атомарной структуры, такой как URL-адрес, нетрудно, но требуется значительная работа для создания архитектуры, которая открывает процесс создания сложных структур».
Реми