Integración de datos - Cadenas

Fernando Berzal, berzal@[Link]

Integración de datos

Descripción de fuentes de datos

Emparejamiento de cadenas [string matching]

Medidas de similitud

Escalabilidad

Integración de esquemas

Emparejamiento de esquemas [schema matching]

Correspondencias entre esquemas [schema mapping]

Gestión de modelos

Emparejamiento de datos [data matching]

Wrappers

Apéndice: Procesamiento de consultas 1
Emparejamiento de cadenas
Problema
Encontrar cadenas que se refieren a la misma entidad.

[Link]. MSFT & Microsoft & Microsoft Corporation

Gran Vía, 35 & G.Vía 35
F. Berzal & Fernando Berzal

Crítico para muchas tareas:

Integración de esquemas [schema matching & mapping]

Integración de datos [data matching]

Extracción de información

… 2

Emparejamiento de cadenas
Formalización del problema

Dados dos conjuntos de cadenas X e Y,

encontrar todos los pares (x,y), con x∈X e y∈Y,
que hacen referencia a la misma entidad en el mundo real.

Cada par (x,y) identificado será un emparejamiento [match].

3
Emparejamiento de cadenas
Desafíos prácticos

Precisión [accuracy]:
Las cadenas que debemos emparejar no siempre son
iguales (typos, errores de OCR, formatos diferentes,
abreviaturas y omisiones, apodos, cambios de orden… ).

Escalabilidad [scalability]:
Emparejar cada cadena con todas las demás
no es práctico, O(n2), por lo que deberemos
reducir el número de comprobaciones necesario.

Medidas de similitud
Las cadenas que desearíamos emparejar
no siempre aparecen de la misma forma:

Errores mecanográficos
David vs. Davod

Errores de OCR
datos vs. dalos

Abreviaturas (en ocasiones, no estándar) y omisiones
Calle Real vs. C/ Real vs. C./ Real vs. Cl. Real vs. Call. Real

Diferentes nombres y apodos
José vs. Jose vs. Pepe
¿?

Cambios de orden en subcadenas
ETSIIT, Universidad de Granada
5
vs. Universidad de Granada, ETSIIT
Medidas de similitud
Solución
Definir una medida de similitud s(x,y) ∈ [0,1]

Cuanto mayor sea la similitud s(x,y),

mayor es la probabilidad de que x e y casen.

Normalmente, x e y emparejan si s(x,y) ≥ t.

NOTA
También se pueden utilizar
funciones de coste o métricas de distancia:
cuanto menor sea su valor, mayor es la similitud. 6

Medidas de similitud
Distintas formas de medir la similitud entre cadenas:

Medidas basadas en secuencias:

Distancia de edición, Needleman-Wunch, affine gap,
Smith-Waterman, Jaro, Jaro-Winkler…

Medidas basadas en conjuntos:

solapamiento, Jaccard, TF/IDF…

Medidas híbridas (e.g. Monge-Elkan)

Medidas fonéticas (e.g. Soundex) 7

Medidas de similitud
Distancia de edición (a.k.a. Distancia Levenshtein)

d(s,t) mide la diferencia entre dos cadenas s y t como el

número mínimo de operaciones de edición que hay que
realizar para convertir una cadena en otra:
d(“data mining”, “data minino”) = 1
d(“efecto”, “defecto”) = 1
d(“poda”, “boda”) = 1
d(“night”,”natch”) = d(“natch”,”noche”) = 3

Aplicaciones: Correctores ortográficos, reconocimiento

de voz, detección de plagios, análisis de ADN, traducción…

NOTA: Para datos binarios, es la distancia de Hamming. 8

Medidas de similitud
Distancia de edición (a.k.a. Distancia Levenshtein)

Operadores de edición (de coste 1)

Borrar un carácter.

Insertar un carácter.

Sustituir un carácter por otro.

Puede adaptarse para incorporar diferentes

errores mecanográficos típicos
([Link]. intercambiar dos caracteres)

9
Medidas de similitud
Distancia de edición (a.k.a. Distancia Levenshtein)
Cálculo mediante programación dinámica.

Definición recursiva de la solución:

 d (i − 1, j − 1) si s[i ] = t[ j ]
d (i , j ) = 
1 + min{d (i − 1, j ), d (i, j − 1), d (i − 1, j − 1)} si s[i ] ≠ t[ j ]

Casos

Mismo carácter: d(i-1,j-1)

Inserción: 1 + d(i-1,j)

Borrado: 1 + d(i,j-1)
10

Sustitución: 1 + d(i-1,j-1)

Medidas de similitud
Distancia de edición (a.k.a. Distancia Levenshtein)
int LevenshteinDistance (string s[1..m], string t[1..n])
{
for (i=0; i<=m; i++) d[i,0]=i;
for (j=0; j<=n; j++) d[0,j]=j;

for (j=1; j<=n; j++)

for (i=1; i<=m; i++)
if (s[i]==t[j])
d[i,j] = d[i-1, j-1]
else
d[i,j] = 1+ min(d[i-1,j],d[i,j-1],d[i-1,j-1]);

return d[m,n];
} 11
Medidas de similitud
Distancia de edición (a.k.a. Distancia Levenshtein)
EJEMPLO
y0 y1 y2 y3 y4 y0 y1 y2 y3 y4
x = dva d a v e d a v e

y = dave x0 0 1 2 3 4 x0 0 1 2 3 4

x1 d 1 0 1 x1 d 1 0 1 2 3

x2 v 2 x2 v 2 1 1 1 2

x3 a 3 x3 a 3 2 1 2 2

x=d–va
d(x,y)=2
y=dave

Algoritmo O(|x||y|) 12

Medidas de similitud
Distancia de edición (a.k.a. Distancia Levenshtein)

¿Cómo convertimos una medida de distancia

en una medida de similitud?

s(x,y) = 1 – d(x,y) / max { length(x), length(y) }

EJEMPLO

d (‘David Smiths’, ‘Davidd Simth’) = 4

s (‘David Smiths’, ‘Davidd Simth’) = 1 – 4 / max(12, 12) = 0.67
13
Medidas de similitud
Medida de Needleman-Wunch
Generalización de la distancia de edición de Levenshtein.

IDEA BÁSICA: Alineación de secuencias

Correspondencia entre los caracteres de x e y,
permitiendo la existencia de huecos

- C T G A C C T A C C T
C C T G A C - T A C A T

Se asigna un coste a cada alineación

y se devuelve la asignación de menor coste… 14

Medidas de similitud
Medida de Needleman-Wunch

Dadas dos secuencias,

X = (x1 x2 … xm) e Y = (y1 y2 … yn),
encontrar la forma de alinearlas con un coste mínimo.

¿Cómo medimos ese coste?

δ [gap penalty], cuando en una cadena no aparece un
símbolo que sí está en la otra.

αpq [mismatch penalty], cuando en la cadena X
aparece el símbolo p pero en la cadena Y aparece q.
15
Medidas de similitud
Medida de Needleman-Wunch
EJEMPLOS
C T G A C C T A C C T
C C T G A C T A C A T
αTC + αGT + αAG + 2αCA

- C T G A C C T A C C T
C C T G A C - T A C A T
2δ + αCA

δ [gap penalty]
16

αpq [mismatch penalty]

Medidas de similitud
Medida de Needleman-Wunch

Una alineación M es un conjunto de pares (xi,yj) tal

que cada uno de los elementos xi e yj aparece como
mucho en un par y no se produce ningún cruce.

Los pares (xi,yj) y (xi’,yj’) se cruzan si i<i’ pero j>j’.

El coste de la alineación M, por tanto, viene dado por:

coste ( M ) = ∑α
( x , y )∈ M
xi y j + ∑ δ+ ∑ δ
x ∉M y ∉M
1i42
j i
43 1 42 j
4 43 4 17
errores huecos
Medidas de similitud
Medida de Needleman-Wunch
EJEMPLO
CTACCG vs. TACATG

x1 x2 x3 x4 x5 x6

C T A C C - G
coste ( M ) = ∑α
( x , y )∈ M
xi y j + ∑ δ+ ∑ δ
x ∉M y ∉M
- T A C A T G 1i42
j i
43 1 42 j
4 43 4
y1 y2 y3 y4 y5 y6 errores huecos

Alineación M = { (x2,y1), (x3,y2), (x4,y3), (x5,y4), (x6,y6) }

18
Coste de la alineación: coste(M) = 2δ + αCA

Medidas de similitud
Medida de Needleman-Wunch
OPT(i, j) Coste mínimo de alineación de las secuencias
Xi=(x1 x2 … xi) e Yj=(y1 y2 … yj).

Caso 1: (xi,yj) está en la mejor alineación MOPT

Hay que pagar el coste de emparejar xi con yj, a lo que
habrá que añadir el coste de alinear las secuencias
Xi-1=(x1 x2 … xi-1) e Yj-1=(y1 y2 … yj-1).

Caso 2a: MOPT deja xi sin emparejar
Hay que pagar una penalización δ más el coste de alinear
las cadenas Xi-1=( x1 x2 … xi-1) e Yj=(y1 y2 … yj).

Caso 2b: MOPT deja yj sin emparejar
Penalización δ más el coste de alinear las cadenas 19
Xi=( x1 x2 … xi) e Yj-1=(y1 y2 … yj-1).
Medidas de similitud
Medida de Needleman-Wunch
OPT(i, j) Coste mínimo de alineación de las secuencias
Xi=(x1 x2 … xi) e Yj=(y1 y2 … yj).

Definición recursiva de la solución:

 jδ si i = 0
 α xi y j + OPT (i − 1, j − 1)
 
OPT (i, j ) =  min δ + OPT (i − 1, j ) en otro caso
 δ + OPT (i, j − 1)
 
 iδ si j = 0
20

Medidas de similitud
Medida de Needleman-Wunch
NeedlemanWunch (X, Y, δ, α)
{
for i = 0 to [Link]
δ;
M[0, i] = i*δ
for j = 0 to [Link]
δ;
M[j, 0] = j*δ
for i = 1 to [Link]
for j = 1 to [Link]
M[i, j] = min ( α[X[i]][Y[j]] + M[i-1][j-1],
δ + M[i-1][j],
δ + M[i][j-1]);
return M[[Link]][[Link]];
21
}
Medidas de similitud
Medida de Needleman-Wunch
Algoritmo basado en programación dinámica

Eficiencia

Tiempo: Θ(|X||Y|)

Espacio: Θ(|X||Y|)

Otras aplicaciones…

Reconocimiento de voz con DTW, |X|<100, |Y|<100, OK.

Biología computacional: |X|=|Y|=100000

1010 operaciones, OK

Array con 1010 entradas > 10 GB !!! 22

Medidas de similitud
Medida de Needleman-Wunch
EJEMPLO
spq [score matrix] =
δ [gap penalty] = 1

23
Medidas de similitud
Affine gap
Extensión de la medida de Needleman-Wunch
para manejar huecos de longitud variable…

EJEMPLO
“David Smith” vs. “David R. Smith”

Needleman-Wunch OK (hueco de longitud 2).

“David Smith” vs.

“David Richardson Smith”

Needleman-Wunch no funciona bien:
Penalización excesiva por la longitud del hueco :-( 24

Medidas de similitud
Affine gap

En la práctica, los huecos suelen ser de longitud > 1.

Asignarle la misma penalización a cada carácter del

hueco penaliza en exceso los huecos largos.

Solución
Definir costes separados
para abrir un hueco y para continuarlo
cost (gap of length k) = c0 + (k-1)cr
c0 = cost of opening gap
25
cr = cost of continuing gap, c0 > cr
Medidas de similitud
Affine gap

EJEMPLO
“David Smith” vs.
“David Richardson Smith”

Needleman-Wunch: scoreNG = 6*2-10 = 2

Affine gap: scoreAG = 6*2-1-9*0.5 = 6.5

c0 = 1
cr = 0.5
26

Medidas de similitud
Affine gap
Cálculo utilizando programación dinámica:

27
Medidas de similitud
Medida de Smith-Waterman
MOTIVACIÓN

Las medidas anteriores consideran alineaciones globales

(emparejan todos los caracteres de x con todos los de y)

Sin embargo, en algunos casos no resulta adecuado:

ETS Ingeniería Informática

Escuela Técnica Superior de Ingeniería Informática

Prof. Fernando Berzal, Universidad de Granada

Fernando Berzal, Ph.D. 28

Medidas de similitud
Medida de Smith-Waterman
UNA IDEA MEJOR

Encontrar las subcadenas más similares de x e y.

En los casos anteriores:

Ingeniería Informática
ETS Ingeniería Informática
Escuela Técnica Superior de Ingeniería Informática

Fernando Berzal
Prof. Fernando Berzal, Universidad de Granada
Fernando Berzal, Ph.D. 29
Medidas de similitud
Medida de Smith-Waterman
ALINEACIÓN LOCAL
Encontrar la mejor alineación local de x e y.

Cambios clave con respecto a Needleman-Wunch:

El emparejamiento puede empezar en cualquier

posición de las cadenas (no limitado al comienzo).

El emparejamiento puede terminar en cualquier

posición de las cadenas (no necesariamente al final):
La reconstrucción de la alineación comienza desde
el mayor valor de la matriz, no desde su esquina.
30

Medidas de similitud
Medida de Smith-Waterman
Cálculo utilizando programación dinámica:

31
Medidas de similitud
Medida de Jaro
Para comparar cadenas cortas
([Link]. nombres y apellidos).

Se encuentran “caracteres comunes” xi e yj:

xi = yj tales que |i-j| ≤ min {|x|,|y|}/2
(caracteres idénticos posicionalmente cerca)

Si el i-ésimo carácter común de x no coincide con el i-

ésimo carácter común de y, tenemos una trasposición.

jaro(x,y) = 1 / 3[c/|x| + c/|y| + (c – t/2)/c],

donde c es el número de caracteres comunes
32
y t es el número de trasposiciones.

Medidas de similitud
Medida de Jaro
EJEMPLOS
x = jon, y = john

c = 3 (caracteres comunes {j, o, n})

t = 0

jaro(x,y) = 1 / 3(3/3 + 3/4 + 3/3) = 0.917

Distancia de edición: Similitud s(x,y) = 0.75
x = jon, y = ojhn

common(x) = jon

common(y) = ojn

t = 2
33

jaro(x,y) = 0.81
Medidas de similitud
Medida de Jaro-Winkler
Captura casos en los que las cadenas x e y tienen una
puntuación baja en la medida de Jaro pero comparten un
prefijo, por lo que es probable que emparejen…

jaro-winkler(x,y) = (1 – PL*PW)*jaro(x,y) + PL*PW

PL = Longitud del prefijo común más largo

PW = Peso dado al prefijo

34

Medidas de similitud
Medidas basadas en conjuntos
Interpretan las cadenas como conjuntos de tokens y
utilizan propiedades de esos conjuntos para determinar
la similitud entre cadenas.

GENERACIÓN DE TOKENS

Palabras delimitadas por espacios (eliminando “stop

words” y usando, opcionalmente, lematización)
[Link]. “Universidad de Granada”  {Universidad, Granada}
“integración de datos”  {integr, dat}

n-gramas (subcadenas de longitud n)

[Link]. “Granada”  3-gramas
35
{##G, #Gr, Gra, ran, ana, nad, ada, da#, a#}
Medidas de similitud
Medidas basadas en conjuntos

Bx = Conjunto de tokens de la cadena x

By = Conjunto de tokens de la cadena y

Solapamiento:
B x ∩ B y|
overlap(x,y) = |B
i.e. número de tokens comunes

Coeficiente de Jaccard:
Bx ∩ By|/ |B
jaccard(x,y) = |B B x ∪ B y|
36

Medidas de similitud
Medidas basadas en conjuntos
EJEMPLO
x = “dave”
y = “dav”

Bx = {#d, da, av, ve, e#}

By = {#d, da, av, v#}

Solapamiento:
overlap(x,y) = |Bx ∩ By| = 3

Coeficiente de Jaccard:
jaccard(x,y) = |Bx ∩ By|/ |Bx ∪ By| = 3/6 37
Medidas de similitud
Coeficiente de Jaccard generalizado

El coeficiente de Jaccard considera los tokens que se

solapan en x e y, que deben ser idénticos (demasiado
restrictivo en ocasiones).

EJEMPLOS

Taxonomías
“Energy & Transportation” vs. “Transportation, Energy, & Gas”

Errores ortográficos
energy vs. eneryg vs. energi

38

Medidas de similitud
Coeficiente de Jaccard generalizado
Bx = {x1, …, xn}
By = {y1, …, ym}

Pares de tokens en el conjunto de solapamiento suavizado:

Los pares para los que una medida de similitud s(xi, yj) ≥ α
forman un grafo bipartido, para el que se puede encontrar
la asignación de peso máximo M [max-weight matching].

Coeficiente generalizado de Jaccard:

Peso normalizado de M
GJ(x,y) = ∑ (xi,yj)∈∈M s(xi,yj) / (|Bx| + |By| - |M|) 39
Medidas de similitud
Coeficiente de Jaccard generalizado
GJ(x,y) = ∑ (xi,yj)∈∈M s(xi,yj) / (|Bx| + |By| - |M|)

GJ(x,y) = (0.7 + 0.9)/(3 + 2 – 2) = 0.53

40

Medidas de similitud
TF/IDF [Term Frequency / Inverse Document Frequency]

Muy usada en recuperación de información [IR]:

Dos cadenas son similares si comparten términos distintivos.

EJEMPLO x = Apple Corporation

y = IBM Corporation
z = Apple Corp.
Emparejamiento incorrecto: s(x,y)>s(x,z) usando la
distancia de edición o el coeficiente de Jaccard.
TF/IDF reconoce que Apple es el término distintivo,
mientras que “Corporation” es un término más común. 41
Medidas de similitud
TF/IDF [Term Frequency / Inverse Document Frequency]

Cada cadena se convierte en un conjunto de términos

(a los que llamaremos documento):

Frecuencia de un término: tf(t,d)

Número de veces que aparece en un documento.

Frecuencia inversa de documento: idf(t) = N / Nt

Número de documentos en la colección partido por el
número de documentos en los que aparece el término.
NOTA: Usualmente se toman logaritmos: log(idf(t)) = log (N / Nt ).

Vector de características asociado a cada documento:

vd(t) = tf(t,d) * idf(t) 42

Medidas de similitud
TF/IDF [Term Frequency / Inverse Document Frequency]
EJEMPLO
vd(t) = tf(t,d) * idf(t)

43
Medidas de similitud
TF/IDF [Term Frequency / Inverse Document Frequency]

Dados los vectores vd(t) = tf(t,d) * idf(t),

calculamos la similitud entre dos cadenas [documentos]
utilizando la distancia del coseno:

44

Medidas de similitud
TF/IDF [Term Frequency / Inverse Document Frequency]

TF/IDF es alto si las cadenas comparten muchos términos

frecuentes (TF alto) a no ser que los términos sean
comunes en otras cadenas (IDF bajo).

En la práctica, se suele suavizar la expresión:

Se suele usar vd(t) = log ( tf(t,d) + 1 ) * log(idf(t))
en lugar de vd(t) = tf(t,d) * idf(t).

Los vectores de características se suelen normalizar:

Σvd(t)2)
vd(t) = vd(t) / sqrt(Σ
45
Medidas de similitud
Soft TF/IDF
Similar al coeficiente generalizado de Jaccard,
salvo que usa TF/IDF como medida de similitud:

close(x,y,k) = Conjunto de términos t ∈ Bx que tienen

al menos un término cercano u ∈ By, i.e., s’(t,u) ≥ k

La similitud s(x,y) se calcula como en TF/IDF, pero

ponderando cada componente TF/IDF por s’:
s(x,y) = ∑ t∈close(x,y,k) vx(t) * vy(u*) * s’(t,u*)
u* ∈ By maximiza s’(t,u) ∀ u ∈ By
46

Medidas de similitud
Soft TF/IDF
EJEMPLO

47
Medidas de similitud
Similitud de Monge-Elkan
Mayor control sobre la forma de medir la similitud

Se descomponen las cadenas x e y en múltiples

subcadenas x=A1..An e y=B1..Bm.

Similitud s(x,y) = 1/n * Σi maxj s’(Ai, Bj)

donde s’ es una medida de similitud secundaria,
[Link]. Jaro-Winkler

Interpretación intuitiva: Se ignora el orden en el que

se emparejan las subcadenas y sólo se consideran 48
los mejores emparejamientos de cada subcadena.

Medidas de similitud
Similitud de Monge-Elkan
Mayor control sobre la forma de medir la similitud

EJEMPLO

x = Comput. Sci. and Eng. Dept.,
University of California, San Diego

y = Department of Computer Science,
Univ. Calif., San Dieg

NOTA: Se escoge una medida de similitud secundaria s’

que funcione bien con abreviaturas y acrónimos.
Muy útil en idiomas como el inglés :-) 49
Medidas de similitud
Medidas fonéticas

IDEA:
Emparejar cadenas de acuerdo a su pronunciación
en vez de atender a su ortografía
(que, además, no siempre es correcta).

Muy práctico para nombres propios

(especialmente en idiomas como el inglés):
Meyer, Meier & Mire
Smith, Smithe & Smythe
Leticia & Letizia
50

Medidas de similitud
Medidas fonéticas
Algoritmo más popular: SOUNDEX

Step 1: Keep the first letter of x,
subsequent steps are performed on the rest of x

Step 2:
Remove all occurences of W and H.
Replace the remaining letters with digits as follows:
B, F, P, V with 1; C, G, J, K, Q, S, X, Z with 2;
D, T with 3; L with 4, M, N with 5; R with 6

Step 3:
Replace sequence of identical digits by the digit itself.

Step 4:
Drop all non-digit letters,
return the first four letters as the soundex code.
NOTE: Soundex code is padded with 0 if there are not enough digits.51
Medidas de similitud
Medidas fonéticas
Algoritmo más popular: SOUNDEX

Se codifica cada apellido usando un código de 4 letras

y dos apellidos se consideran similares si comparten el
mismo código.

Robert & Rupert  R163

Funciona bien para muchos nombres ([Link]. occidentales),

aunque no para otros de distinto origen, como los
asiáticos que utilizan las vocales para discriminar…
52

Medidas de similitud
Medidas fonéticas
Algoritmo más popular: SOUNDEX

x = Ashcraft

Step 1: A

Step 2: A226a13

Step 3: A26a13

Step 4: A2613  A261

Resultado: A261

El mismo resultado para Ashcroft, Ascroft o Ascrofte

[Link] 53
Escalabilidad
Problema práctico
Emparejar cada cadena con todas las demás
no es práctico, O(n2), por lo que deberemos
reducir el número de pruebas necesario.

Solución
Calcular s(x,y) sólo para las parejas más prometedoras

for each x ∈ X
Z = candidatos(x) // Z ⊆ Y
for each y ∈ Z
if s(x,y) ≥ t
return (x,y) as a matched pair 54

Escalabilidad
Blocking
Técnicas que permiten reducir el número necesario de
comparaciones de cadenas.

Umbrella set (“conjunto paraguas”)

El conjunto Z de candidatos para una cadena x.

for each x ∈ X
Z = candidatos(x) // Z ⊆ Y
for each y ∈ Z
if s(x,y) ≥ t
return (x,y) as a matched pair 55
Escalabilidad
Técnicas

Índice invertido [inverted index]

Filtrado por longitud [size filtering]

Filtrado por prefijos [prefix filtering]

Filtrado por posición [position filtering]

Filtrado por cotas [bound filtering]

56

Escalabilidad
Índice invertido [inverted index]

Se construye un índice invertido sobre Y:

para cada término de los que aparecen en Y,
se mantiene la lista de cadenas en las que aparece.

Dado un término t, se utiliza el índice para acceder
rápidamente a las cadenas de Y que lo contienen.

Limitaciones

La lista de cadenas correspondientes a algunos
términos ([Link]. “stop words”) puede ser muy larga.

Requiere enumerar todos los pares de cadenas que
comparten al menos una palabra. 57
Escalabilidad
Índice invertido [inverted index]

58

Escalabilidad
Filtrado por longitud [size filtering]

Sólo se consideran cadenas de Y determinadas longitudes:

Dada una cadena x∈X, se infiere una restricción sobre la
longitud de las cadenas de Y con las que x pueda casar.

Se utiliza un árbol B como índice para acceder sólo a las
cadenas que satisfagan la restricción de longitud.

EJEMPLO: Coeficiente de Jaccard J(x,y) = |X ∩ Y| / |X ∪ Y|

Dos cadenas emparejan si J(x,y) ≥ t.

Dada una cadena x, sólo pueden emparejar con x
aquéllas cadenas y tales que |x|/t ≥ |y| ≥ |x|*t 59
Escalabilidad
Filtrado por longitud [size filtering]

x = {lake, mendota}
t = 0.8

Para que y∈Y case con x usando el coeficiente de Jaccard:

2/0.8 = 2.5 ≥ |y| ≥ 1.6 = 2*0.8

Ninguna cadena de Y satisface la restricción.

60

Escalabilidad
Filtrado por prefijos [prefix filtering]

IDEA
Si dos conjuntos comparten muchos términos,
subconjuntos grandes de ellos también los compartirán.

EJEMPLO: Solapamiento O(x,y) = |X ∩ Y|

Si |X ∩ Y| ≥ k, cualquier subconjunto X’⊆X de tamaño
al menos |X|-(k-1) se solapará con Y.

Para encontrar los pares (x,y) tales que |X ∩ Y| ≥ k,
podemos construir un subconjunto X’ de tamaño
|X|-(k-1) y utilizar un índice invertido para obtener
61
todas las cadenas y que se solapan con x.
Escalabilidad
Filtrado por prefijos [prefix filtering]

O(x,y) ≥ 2

x1 = {lake, mendota}  x1’= {lake}

El índice invertido nos da las cadenas
que contienen el término de x1’: {y4, y6} 62

Escalabilidad
Filtrado por prefijos [prefix filtering]
¿Cómo seleccionar el subconjunto de forma inteligente?

Se selecciona un subconjunto x’ de x para compararlo

con el conjunto completo de cadenas de Y.

Cuanto más pequeño sea el subconjunto de Y que
tengamos que considerar, mejor.

IDEA
Imponer un orden sobre los términos ([Link]. frecuencia
creciente) y seleccionar los términos menos frecuentes
de x para formar el subconjunto x’… 63
Escalabilidad
Filtrado por prefijos [prefix filtering]
¿Cómo seleccionar el subconjunto de forma inteligente?

PROPIEDAD
Dados dos conjuntos x e y tales que |x∩y|≥ k,
ordenamos sus elementos de menor a mayor frecuencia.
Sea x’ el prefijo de x de tamaño |x|-(k-1)
e y’ el prefijo de y de tamaño |y|-(k-1):
x’ e y’ se solapan.

64

Escalabilidad
Filtrado por prefijos [prefix filtering]
¿Cómo seleccionar el subconjunto de forma inteligente?

ALGORITMO

Se ordenan los términos de x∈X e y∈Y en orden
creciente de frecuencia.

Para cada y∈Y, se crea y’,
el prefijo de y de tamaño |y|-(k-1).

Se crea un índice invertido sobre los prefijos y’.

Para cada x∈X, se crea x’,
el prefijo de x de tamaño |x|-(k-1).

Se utiliza el índice invertido para encontrar las cadenas
y para las que el prefijo x’ se solapa con el prefijo y’. 65
Escalabilidad
Filtrado por prefijos [prefix filtering]
¿Cómo seleccionar el subconjunto de forma inteligente?
Índice sobre prefijos

vs.

NOTA: En la práctica, el índice invertido

sobre los prefijos es significativamente
x1 = {lake, mendota} más pequeño que el índice invertido
66
sobre las cadenas completas.
 x1’= {mendota}

Escalabilidad
Filtrado por prefijos [prefix filtering]
¿Cómo aplicarlo sobre el coeficiente de Jaccard?

‫ݐ‬
‫ݔ ܬ‬, ‫ݔ ܱ ⇔ ݐ ≥ ݕ‬, ‫= ߙ ≥ ݕ‬ · ( ‫ ݔ‬+ |‫)|ݕ‬
1+‫ݐ‬

El umbral α depende de |x| e |y|.

Se tienen que indexar los prefijos de y∈Y

de longitud |y|- t |y| + 1 para garantizar
que no se pierden posibles emparejamientos.
67
Escalabilidad
Filtrado por posición [position filtering]

Limita el conjunto de pares candidatos derivando una

cota superior sobre el solapamiento de x e y:

x = x’ ∪ x’’
y = y’ ∪ y’’

ܱ ‫ݔ‬, ‫ ݔ ≤ ݕ‬ᇱ ∩‫ ݕ‬ᇱ + min{ ‫ ݔ‬ᇱᇱ , ‫ ݕ‬ᇱᇱ }

68

Escalabilidad
Filtrado por posición [position filtering]

x = {dane, area, mendota, monona, lake}

y = {research, dane, mendota, monona, lake}

J(x,y) ≥ 0.8

Por un lado (filtrado por prefijos),
O(x,y) ≥ 4.44 = 0.8 / (1+0.8) * (5+5)

Por otro (filtrado por posición),
O(x,y) ≤ 4 = 1 + min{3,3}
Sin comparar las cadenas, descartamos el par (x,y).
69
Escalabilidad
Filtrado por cotas [bound filtering]
Optimización para el coeficiente de Jaccard generalizado:
GJ(x,y) = ∑ (xi,yj)∈∈M s(xi,yj) / (|Bx| + |By| - |M|)

Conjuntos de pares (xi,yj):

S1: Para cada xi∈Bx, encontrar el elemento yj∈By
de mayor similitud tal que s(xi,yj)≥α
S2: Para cada yj∈By, encontrar el elemento xi∈Bx
de mayor similitud tal que s(xi,yj)≥α

Cota superior:
UB(x,y) = ∑ (xi,yj)∈S1∪S2 s(xi,yj) / (|Bx| + |By| - |S1∪S2|)

Cota inferior:
LB(x,y) = ∑ (xi,yj)∈S1∩S2 s(xi,yj) / (|Bx| + |By| - |S1∩S2|) 70

Escalabilidad
Filtrado por cotas [bound filtering]
Optimización para el coeficiente de Jaccard generalizado:
GJ(x,y) = ∑ (xi,yj)∈∈M s(xi,yj) / (|Bx| + |By| - |M|)

Para cada (x,y) se calcula una cota inferior LB(x,y)

y una cota superior UB(x,y) sobre GJ(x,y):

Si UB(x,y) ≤ t, el par (x,y) puede ignorarse.

Si LB(x,y) ≥ t, el par (x,y) casa [sin compararlo].

En otro caso, se calcula GJ(x,y).

71
Escalabilidad
Filtrado por cotas [bound filtering]
Optimización para el coeficiente de Jaccard generalizado:
GJ(x,y) = ∑ (xi,yj)∈∈M s(xi,yj) / (|Bx| + |By| - |M|)

S1 = {(a,q), (b,q)}
S2 = {(a,p), (b,q)}
UB(x,y) = (0.8+0.9+0.7+0.9)/(3+2-3) = 1.65
LB(x,y) = 0.9/(3+2-1) = 0.225 72

Escalabilidad
Extensiones a otras medidas de similitud
Traducción del valor s(x,y) en restricciones sobre otras
medidas de similitud para las que funcione la técnica:

Distancia de edición
Filtrado de prefijos de longitud qε+1 usando q-gramas.

TF/IDF
Filtrado de prefijos de longitud |x|- t2|x| + 1.

73
Bibliografía recomendada

Hai Doan, Alon Halevy & Zachary Ives:

Principles of Data Integration
Morgan Kaufmann, 1st edition, 2012.
ISBN 0124160441
[Link]

Chapter 4: String Matching

74