¿Cómo encuentra Apple las fechas, horas y direcciones en los correos electrónicos?

128

En el cliente de correo electrónico de iOS, cuando un correo electrónico contiene una fecha, hora o ubicación, el texto se convierte en un hipervínculo y es posible crear una cita o mirar un mapa simplemente tocando el enlace. No solo funciona para correos electrónicos en inglés, sino también en otros idiomas. Me encanta esta función y me gustaría entender cómo lo hacen.

La manera ingenua de hacer esto sería tener muchas expresiones regulares y ejecutarlas todas. Sin embargo, esto no va a escalar muy bien y funcionará solo para un idioma específico o formato de fecha, etc. Creo que Apple debe estar utilizando algún concepto de aprendizaje automático para extraer entidades (8:00 PM, 8PM, 8:00, 0800, 20:00, 20h, 20h00, 2000 etc.).

¿Alguna idea de cómo Apple puede extraer entidades tan rápidamente en su cliente de correo electrónico? ¿Qué algoritmo de aprendizaje automático aplicarías para lograr tal tarea?

Martín
fuente
55
También pensé en esto, especialmente en el truco regex. Sé que tienen una patente, así que tal vez puedas intentar buscarlo. Sin embargo, también me interesaría mucho. +1
Thomas Jungblut
15
En realidad, el truco regexp probablemente atrapará el 99% de los casos con una tasa de error muy baja. Y es súper rápido, cuando optimizas bien las expresiones regulares. Por lo tanto, no me sorprendería si fuera solo un conjunto de expresiones regulares.
HA SALIDO - Anony-Mousse

Respuestas:

153

Es probable que utilicen técnicas de extracción de información para esto.

Aquí hay una demostración de la herramienta SUTime de Stanford:

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

Extraería atributos sobre n-gramos (palabras consecutivas) en un documento:

  • numberOfLetters
  • numberOfSymbols
  • longitud
  • previo
  • nextWord
  • nextWordNumberOfSymbols
    ...

Y luego use un algoritmo de clasificación, y aliméntelo con ejemplos positivos y negativos:

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

Es posible que te salgas con 50 ejemplos de cada uno, pero cuantos más mejor. Luego, el algoritmo aprende basándose en esos ejemplos y puede aplicarse a ejemplos futuros que no ha visto antes.

Puede aprender reglas como

  • si la palabra anterior es solo caracteres y quizás puntos ...
  • y la palabra actual está en "febrero", "mar", "el" ...
  • y la siguiente palabra está en "duodécimo", any_number ...
  • entonces es la fecha

Aquí hay un video decente de un ingeniero de Google sobre el tema.

Neil McGuigan
fuente
44
¡Interesante! Nunca lo había pensado de esa manera. Gracias el jefe.
Martin
2
El jefe, en su opinión, ¿qué tipo de modelo sería mejor para eso? Bayesiano?
Martin
55
Estoy bastante seguro de que este enfoque no funcionará mejor que, digamos, una medida f de aprox. 0.9. (Nota, esto es solo un sentimiento, puedo estar equivocado). Por otro lado, excepto el ingenuo enfoque de codificar todos los formatos comunes para obtener un mejor rendimiento (posiblemente 0.99+ dado que nunca se perderán los formatos más frecuentes) y ser más rápido para implementar + en tiempo de ejecución.
b.buchhold
@ b.buchhold, tal vez, pero luego tendrías que hacer la misma cantidad de trabajo para el siguiente idioma y el siguiente idioma, mientras que mi solución es general.
Neil McGuigan
@Neil McGuigan, cierto. Pero tendría que proporcionar muchos datos de capacitación para todos esos formatos / idiomas, lo que es mucho más trabajo.
b.buchhold
110

Esa es una tecnología que Apple realmente desarrolló hace mucho tiempo llamada Apple Data Detectors . Puedes leer más sobre esto aquí:

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

Esencialmente analiza el texto y detecta patrones que representan datos específicos, luego le aplica acciones contextuales del sistema operativo. Está bien.

jeffehobbs
fuente
24
Esta es la respuesta correcta. Otras respuestas pueden decirle cómo podría hacerlo, pero esta le dice cómo lo hace Apple .
LaC
2
¿Podríamos tener un poco más de detalle en la redacción? las entradas de un solo enlace no agregan tanto
shigeta
14
Ah, entonces ESTO es de donde provienen todos los éxitos en mi sitio web :) FWIW, fui el líder del proyecto en los Detectores de datos de Apple en los días de ATG; lo que puedo agregar aquí es que esto era solo una tecnología OS 8 y 9: nunca dio el salto a OS X. Obviamente, están sucediendo algunas cosas similares en OS X e IOS, y, aunque ya no estoy en Apple y realmente no puedo decir, no me sorprendería si la arquitectura es un poco diferente. Sin embargo, espero que algún tipo de sistema de gramática / analizador siga siendo el núcleo de todo. Las computadoras son rápidas en estos días, y las gramáticas simples son bastante baratas.
Jim Miller
5

Una parte del rompecabezas podría ser la NSDataDetectorclase. Se utiliza para reconocer algunos tipos estándar, como los números de teléfono.

hburde
fuente
2
Parece que la NSDataDetectorclase es el resultado del esfuerzo que Apple puso en implementar esto. La pregunta es cómo funciona la clase internamente.
Ole Begemann
3
está en NSRegularExpression.h, por lo que parece bastante posible que sea, como se señaló, solo un conjunto de expresiones regulares.
riffraff
2

Una vez escribí un analizador para hacer esto, usando pyparsing. Es realmente muy simple, solo necesita acertar todas las formas diferentes, pero no hay muchas. Solo tomó unas horas y fue bastante rápido.

Stavros Korokithakis
fuente
Extracto de Miramontes "No es difícil codificar un reconocedor para una estructura atómica como una URL, pero se requiere un trabajo sustancial para crear una arquitectura que abra el proceso de creación de estructuras complejas".
Remy