1 SOFTMEALY: “Generating finite-state transducers for semi-structured data extraction from the web.” Antonio Carlos Maraver Martín [email protected] Dirigido por: Dr. Rafael Corchuelo Gil

2 Índice Introducción Conceptos básicos Fases del algoritmo Ejemplo Conclusiones

3 Índice Introducción Conceptos básicos Fases del algoritmo Ejemplo Conclusiones

4 Explosión de internet

5 Información distribuida Información distribuida ………… ACCESO Mediadores de Información (Construidos con WRAPPER)

6 Extracción de información SOFTMEALY Info Extractor. Form Filler Navigator Ontologizer Varifier

7 Fuentes semi-estructuradas “Existe un modelo de datos definido que se puede inferir.”

8 MEALY & Delimitadores Base del algoritmo: Máquina de estados finito de Mealy. Detección de separadores. …, |Professor of Computer…

9 Índice Introducción Conceptos básicos Fases del algoritmo Ejemplo Conclusiones

10 Modelo de datos (Semi-Estructurados)

11 Clasificación de tokens

12 Separadores y reglas de contexto Separador  S = S L S R. S L ::= Html( ) Punc(,) Spc(_) Html( ) | Punc(_) NL(_) Spc(_) Html( ) | Punc(,) Spc(_), Html( ).. S R ::= C1Aplh(_) …, |Professor of Computer… SLSL SLSL SRSR SRSR

13 Máquina de estados finita (MEALY) Induce la extracción de atributos. Formada por: Σ 1 : Conjunto de sepadores. Σ 2 : Atributos de salida. Q: Conjunto finito de estados (e, b y otros). R: Reglas de contexto. E: Conjunto de aristas. FST

14 Índice Introducción Conceptos básicos Fases del algoritmo Ejemplo Conclusiones

15 Fases principales …, |Professor of … S R :== …… S L :== …… FST Atr1Atr2Atr3 ……… ……… ……… ……… ……… ………

16 Etiquetado de ejemplos Modelo de datos existente que se puede inferir. Al menos un ejemplo de cada tipo de tupla.

17 Generalización de reglas de contexto [word] nonword*| |nonword* [word] [word] nonword*| |nonword* [word]

18 Generalización de reglas de contexto

19 Contrucción de FST Estado inicial (e). Estado final (b). 1 atributo a extraer (A)  Dos estados (A y A). Transiciones nulas: Mismo estado. Transiciones entre estados: Atributos adyacentes. e e U U U U b b ?/ε S / ”U=” S / ε …

20 Explotación del FST

21 Índice Introducción Conceptos básicos Fases del algoritmo Ejemplo Conclusiones

22 Ejemplo de aplicación

23 Índice Introducción Conceptos básicos Fases del algoritmo Ejemplo Conclusiones

24 Algoritmo supervisado. Datos semi-estructurados. Busca separadores entre atributos. Robusto  Se adapta a permutaciones de los atributos y a valores perdidos. Requiere entrenamiento con cada posible tipo de tupla a extraer. Inconveniente: Posible ambigüedad en la extracción.

25 ¡Gracias!