Quarto Trabalho Prático de GTI
Resolução
Exercício 1
Escreva um programa que, utilizando as funções de
semelhança entre strings disponibilizadas pelo LingPipe,
detecte os nomes de empresas duplicados no ficheiro
empresas.xml. Assuma que os elementos duplicados são
aqueles cujo limiar de similaridade está acima de 0.8
(considerando que a função retorna valores entre 0 e 1). O
resultado da execução do programa deverá ser a lista de
nomes de empresas para os quais existem potenciais
duplicados e, para cada um destes, os nomes em conflito.
Exercício 1
import java.io.*;
import java.util.*;
import org.w3c.dom.*;
import com.aliasi.util.*;
import com.aliasi.spell.*;
import com.aliasi.lm.*;
import com.aliasi.tokenizer.*;
import javax.xml.parsers.*;
import javax.xml.xpath.*;
public class FindDuplicates {
public static void main ( Strings args[] ) throws Exception {
DocumentBuilder builder=DocumentBuilderFactory.newInstance().newDocumentBuilder();
Document doc = builder.parse("empresas.xml");
XPathExpression exp = XPathFactory.newInstance().newXPath().compile("//empresa");
NodeList nodes=(NodeList)exp.evaluate(doc,XPathConstants.NODESET);
Distance dist = new JaroWinkler(0.5,5);
Exercício 1
exp = XPathFactory.newInstance().newXPath().compile(”nome");
for (int i=0; i<nodes.getLength(); i++) {
String emp1 = (NodeList)exp.evaluate(nodes.item(i),XPathConstants.STRING);
System.out.println("Duplicates for " + emp1);
for (int j=0; j<nodes.getLength(); j++) if(i!=j) {
String emp2 = (NodeList)exp.evaluate(nodes.item(j),XPathConstants.STRING);
double sim = 1-dist.distance(emp1,emp2);
if( sim > 0.85) System.out.println("\t " + emp2 + " (similarity: " + sim + ")");
}
}
}
}
Exercício 2
Proponha uma combinação de funções de semelhança (e.g. uma
média pesada) para diferentes elementos do ficheiro
empresas.xml (i.e. uma função para a semelhança entre os
URLs e outra para a semelhança entre os nomes) por forma a
calcular um valor adequado para a semelhança entre diferentes
elementos “empresa” no ficheiro empresas.xml. Justifique a
sua resposta com base nas vantagens associadas à utilização
das diferentes funções de similaridade (e.g. EditDistance, JaroWinkler, etc.).
Exercício 2
Para fazer a detecção de empresas duplicadas poderia ser usada uma combinação linear de
funções de similaridade aplicadas aos 3 elementos constítuintes de um elemento "empresa".
Empresas com uma similaridade acima de um dado limiar poderiam ser consideradas
duplicadas.
similaridade = (0.05 * similaridadeLocais) +
(0.35 * similaridadeURLs) +
(0.6 similaridadeNomes)
A combinação linear proposta dá uma importância baixa ao atributo "local", uma vez que existem
naturalmente várias empresas associadas a um mesmo local. O atríbuto local é portanto pouco
relevante para a detecção de empresas duplicadas. Já os URLs e os nomes das empresas são
mais relevantes para a detecção de empresas duplicadas (e.g. empresas com o mesmo nome
ou URL serão certamente duplicadas, sendo que pequenas diferenças nestes atríbutos
poderão estar relacionadas com duplicados parciais). Foi dada uma maior importância ao
elemento "nome," uma vez que este tem geralmente um comprimento maior que o URL e
poderem existir empresas com vários URLs diferentes.
Exercício 2
Em relação às funções de similaridade para cada um dos elementos, poderiam
ser consideradas as seguintes:



similaridadeLocais = 1/(1+EditDistance), uma vez que dá valores elevados
para strings com caracteres em comum nas mesmas posições.
similaridadeNomes = JaroWinkler, uma vez que dá valores elevados para
strings com o mesmo prefixo e com caracteres em comum.
similaridadeURLs = Smith-Waterman, uma vez que dá valores elevados
para strings com caracteres em comum que tenham prefixos e sufixos
diferentes.
Exercício 3
Escreva um programa que faça a correcção dos erros sintácticos
existentes no ficheiro empresas.xml. Deverão ser considerados
os seguintes dois tipos de erros:


URLs inconsistentes (i.e. com e sem o protocolo), podendo ser usada uma
expressão regular para testar se o URL é dado de uma forma completa. Os
URLs deverão ser normalizados através da adição de um protocolo default
(i.e. HTTP), ou através da remoção de informação sobre o protocolo.
Localidades com erros ortográficos. Para corrigir estes problemas, deverão
ser utilizadas as funcionalidades para correcção ortográfica de strings
oferecidas pelo LingPipe. Como dicionário para a correcção deverá ser
usado o ficheiro localidades.txt, o qual se encontra no material de suporte.
Exercício 3
import java.io.*;
import java.util.*;
import org.w3c.dom.*;
import com.aliasi.util.*;
import com.aliasi.spell.*;
import com.aliasi.lm.*;
import com.aliasi.tokenizer.*;
import javax.xml.parsers.*;
import javax.xml.xpath.*;
public class DoCorrections {
public static void main ( Strings args[] ) throws Exception {
DocumentBuilder builder=DocumentBuilderFactory.newInstance().newDocumentBuilder();
Document doc = builder.parse("empresas.xml");
Exercício 3
FixedWeightEditDistance dist = new FixedWeightEditDistance(0.0,-4.0,-1.0,-3.0,-2.0);
NGramProcessLM lm = new NGramProcessLM(5);
TokenizerFactory tok = new LineTokenizerFactory();
TrainSpellChecker sc = new TrainSpellChecker(lm,dist,tok);
sc.train(Files.readFromFile(new File("dictionary.txt"));
ByteArrayOutputStream aux = new ByteArrayOutputStream();
sc.compileTo(new ObjectOutputStream(aux));
CompiledSpellChecker spell = (CompiledSpellChecker)(new
ObjectInputStream(new ByteArrayInputStream(aux.toByteArray()))).readObject());
NodeList nodes = doc.getElementsByTagName("empresa");
for (int i=0; i<nodes.getLength(); i++) {
NodeList local
= ((Element)(nodes.item(i))).getElementsByTagName("local");
NodeList url =
= ((Element)(nodes.item(i))).getElementsByTagName("url");
if(url!=null && !url.item(0).getTextContent().matches("((ht)|f)tp://.*")) {
url.item(0).setTextContent( "http://" + url.item(0).getTextContent()
)
Exercício 3
if(local!=null) {
local.item(0).setTextContent(spell.didYouMean(local.item(0).getTextCon
tent()) );
}
Transformer
transformer=TransformerFactory.newInstance().newTransformer();
transformer.transform(new DOMSource(doc), new StreamResult(new
FileOutputStream("empresas2.xml")));
}
}
}
Exercício 4
Considere os sistemas de integração de dados introduzidos nas
aulas teóricas.


No sistema LSD (ver slides das aulas teóricas e artigo
apresentado no SIGMOD 2001), diga para que tipo de
elementos o classificador Naive Bayes produz melhores
resultados. Justifique a sua resposta.
Aponte uma vantagem e uma desvantagem do formalismo de
mapeamento entre esquemas Global-as-View utilizado no
sistema TSIMMIS.
Exercício 4
1. O classificador Naïve Bayes produz melhores resultados
quando há tokens suficientemente frequentes para indicarem
a categoria correcta (por exemplo, as palavras “bonito”,”
espaçoso”,”novo” num anúncio de imobiliária). Também
funciona bem quando só existem tokens fracamente
sugestivos mas em muita quantidade.
A técnica por detrás deste classificador é baseada em
probabilidades, portanto entra em linha de conta com as
frequências dos tokens.
2. Vantagem: : a resposta a uma interrogação colocada sobre o
esquem do mediador é calculada através de um processo de
expansão de vistas que é facilmente calculado.
Desvantagem: não é facilmente escalável, já que, quando
adicionamos uma fonte, é necessário conhecer o esquema
de todas as outras fontes. Só deste modo, se consegue
Exercício 5
Considere a tarefa de integrar diferentes instâncias do sistema de
leilões XBay, de modo a criar um XBay unificado.
1. Considere a versão relacional do problema, com base nos dois
esquemas relacionais que se apresentam abaixo. Escreva a
definição de uma vista em Datalog, composta por duas regras,
que combine a informação das duas tabelas.
Seller1(sellerID, rating, email, name, city, state, zip, url,
contactPerson, contactEmail)
Seller2(sellerID, rating, firstName, lastName, birthDate, affiliation,
netValue, email)
2. Escreva uma interrogação em Datalog que, colocada sobre a
vista da alínea anterior, devolva o valor de rating de todos os
vendedores (sellers). Use essa interrogação e a primeira regra
da alínea anterior e faça o unfold (ou expansão) da vista de
modo a que chegue a uma única interrogação sobre os dados
Exercício 5
1.
Sellers (sellerId, rating, email, name, city, state, zip, url, cPerson, cEmail,
null, null, null) :Seller1(sellerId, rating, email, name, city, state, zip, url, contactPerson,
contactEmail)
Sellers (sellerId, rating, email, fName | lName, null, null, null, null, null, null,
birthDate, affiliation, netValue) :Seller2(sellerId, rating, firstName, lastName, birthDate, affiliation, netValue,
email)
2. A interrogação é:
SellerRating(sellerId, rating) :- Sellers(sellerId, rating, -, -, -, -, -, -, -, -, -, -, -)
Usando a primeira regra de 1. e expandindo a vista, temos:
SellerRating(sellerId, rating) :- Seller1(sellerId, rating, -, -, -, -, -, -, -, -)