1 FiVaTech: Extracción de datos Web a partir de plantillas de páginas Antonio R. Gómez Sotelo

2 Índice Introducción Algoritmo Experimentos Conclusiones

3 Índice Introducción Algoritmo Experimentos Conclusiones

4 Introducción Generación de Páginas Web: DatosPlantillaPáginas Web

5 Introducción Definición 1: Datos Estructurados 1.Tipo Básico β = Cadena de tokens. 2.Listas ordenadas T=. a.Tupla  b.Opcional  ( T )? c.Conjunto  { T } d.Disyunción  T1| T2|...| Tn

6 Introducción Ejemplo: { >, {“Feature1_1”}, >, {“Feature1_1”, “Feature2”}}

7 Introducción Características de FiVaTech - Entrada: Árboles DOM de páginas Web. - Objetivo: Deducir la plantilla y el esquema de datos del sitio Web. - Modo: Combinando múltiples árboles DOM - Automático - Problema: ¿Cómo fusionar múltiples árboles al mismo tiempo? - Solución: Tratar árboles como cadenas. Árbol patrón.

8 Índice Introducción Algoritmo Experimentos Conclusiones

9 Algoritmo

10 Suposiciones Iniciales: 1.Nodos internos  Pertenecen a plantilla  Datos en nodos hojas 2. Toda instancia de un conjunto  mismo nodo padre

11 Algoritmo Pasos: 1.Tomar Raíz común 2.Reconocimientos nodos iguales 3.Expandir 3.1 Alineación de la matriz par 3.2 Extracción de Patrones 3.3 Fusionar nodos opcionales 4.Extraer plantilla y esquema Crear Árbol patrón

12 Algoritmo (Paso 1) 1. Tomar nodo raíz común: Trivial  Tomar R = Árbol vacío Paso 1. R

13 Algoritmo (Paso 2) 2. Identificación nodos iguales: Comparar si dos nodos (con la misma raíz) son similares  Distancia de edición Umbral d  Asignar símbolo a cada subárbol (nodo).

14 Algoritmo (Paso 3) 3. Expandir: - Hacer los siguientes 3 pasos por cada nodo interno n. - De forma recursiva. 3.1 Alineación de la matriz par 3.2 Extracción de Patrones 3.3 Fusionar nodos opcionales

15 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par: - Crear matriz de nodos: M 1aaa 2bbb 3ccc 4ddb 5bec 6c d 7b e 8c 9d 10e

16 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : row = 1 Mientras M no alineada Mientras filaNoAlineada (row, M) Obtener shiftColumn y shiftLength Desplazar (row, shiftColumn,shiftLength,M) row ++ childList = alignmentResult

17 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : - Conceptos: - Matriz Alineada - Fila alineada - shiftColumn  nodo n rc - shiftLength

18 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : - Selección de shiftColumn y shiftLength: - span (n rc ) = ciclo de máxima longitud (sin rep.) + 1 1, si (r-rup) > span (n rc ) - checkSpan (n rc ) = 0, si (r-rup) = span (n rc ) -1, si (r-rup) < span (n rc ) 1, en otro caso M[r][c] = M[up][c’] ?

19 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : span(b)= span(c)= span(d)= 3 span(a)= span(e)= 0  nodos libres checkSpan(n 41 ) = checkSpan(n 42 )=1 checkSpan (n 43 ) = -1  r-rup = 4 – 2 = 2 < 3 (span b) M 1aaa 2bbb 3ccc 4ddb 5bec 6c d 7b e 8c 9d 10e p abcdbcbbcdeedc d p abc cba p e

20 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : - Selección de shiftColumn y shiftLength: - Una vez tenemos span y checkSpan de los nodos, - Aplicar Reglas (en orden): R1 - izq. checkSpan = -1  shiftLength = 1 R2 - checkSpan = 1 y M[r][c]=M[r down ][c’]   shiftLength = r down - r R3 – R1 y R2 fallan  Dividir fila en 2 partes

21 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : Ej. Filas 1, 2, 3  Alineadas Fila 4: span(d) = 3 span(b) = 3 checkSpan(n 41 ) = 1 checkSpan(n 42 )=1 checkSpan (n 43 ) = -1  r-rup = =4 – 2 = 2 < 3 Aplicar R1 sobre n 43 M 1aaa 2bbb 3ccc 4ddb 5bec 6c d 7b e 8c 9d 10e M 1aaa 2bbb 3ccc 4dd- 5beb 6c c 7b d 8c e 9d e

22 Algoritmo (Paso 3.1) 3.1 Alineación Matriz Par : Ej. ChildList M 1aaa 2bbb 3ccc 4ddb 5bec 6c d 7b e 8c 9d 10e M 1aaa 2bbb 3ccc 4dd- 5beb 6c c 7b d 8c e 9d e … M 1aaa 2bbb 3ccc 4dd- 5b-b 6c-c 7--d 8b-- 9c-- d-- 11eee a b c d b c d b c d e

23 Algoritmo (Paso 3.2) 3.2 Extracción Patrones Repetitivos : - Descubrir patrones repetitivos  datos Tipo conjunto - Patrones anidados dentro de otros. - Desde longitud pequeña a longitud grande. - Ej. abcdbcdbcde  abcde + nodo padre virtual tipo conjunto  bcd

24 Algoritmo (Paso 3.3) 3.3 Agrupar nodos opcionales : - Vector ocurrencia  (b1,b2,…, bn) - Regla: 1. nodos adyacentes mismo vect. ocurrencia o comp. V(a)=(1,1,1) V(b) =(1,1,1,1,1,1) V(d) = (1,0,1,1,0,1)

25 Algoritmo (Ejemplo) - b4 y 2º asterisco mismo vector de ocurrecia  nodo virtual común

26 Algoritmo (Paso 4) 4. Detección Esquema de Datos : - Pasos anteriores: Detección datos tipo básico, conjuntos y opcionales. - Paso actual: Centrarnos en detección de tuplas y obtener el esquema común. - Ignorar datos no variantes. - Cada nodo interno no virtual  Considerar para Tupla

27 Algoritmo (Paso 4) 4. Detección Esquema de Datos : }>, }>

28 Índice Introducción Algoritmo Experimentos Conclusiones

29 Experimentos 1.FiVaTech como extractor de esquema 2.FiVaTech como extractor de SRRs Nota: Siempre 2 ó 3 páginas web como entrada

30 Experimentos 1.FiVaTech como extractor de esquema

31 Experimentos 1.FiVaTech como extractor de SRRs

32 Índice Introducción Algoritmo Experimentos Conclusiones

33 Combinar múltiples árboles DOM. No supervisado. Nuevo algoritmo alineación cadenas (datos opcionales y datos tipo conjunto). Fácil extracción del esquema y la plantilla de un sitio Web. Eficiencia  2 o 3 páginas Web como entrada

34 ¡Gracias! ¿Preguntas?