Made available in DSpace on 2015-04-11T14:03:04Z (GMT). No. of bitstreams: 1
Daniel Pereira de Oliveira.pdf: 1962605 bytes, checksum: 022c425ec0a87d2146c7cae3f274903b (MD5)
Previous issue date: 2006-03-03 / In the current days, the Internet has become the largest information repository available. However, this huge variety of information is mostly represented in textual format and it necessarily requires human intervention to be effectively used. On the other hand, there exists a large set of Web pages that are in fact composed of collections of implicit data objects. For instance, on-line catalogs, digital libraries and e-commerce Web sites in general. Extracting the contents of these pages and identifying the structure of the data objects available allow for more sophisticated forms of processing besides hyperlink browsing and keyword-based searching. The task of extracting data from Web pages is usually executed by specialized programs called wrappers. In the present work we propose and evaluate a new approach to the wrapper development problem. In this approach, the user is only responsible for providing examples for the atomic
items that constitute the objects of interest. Based on these examples, our method automatically generates expressions for extracting other atomics items similar to those presented as example and infers a plausible and meaningful structure to organize them. Our method for generating extraction expression uses techniques inherited from solutions for the multiple string alignment problem. The method is able to produce good extraction expressions that can be easily encoded as regular expressions. Inferring a meaningful structure for the objects whose atomic values were extracted is the task of the HotCycles algorithm, that were previously proposed and which we have revised and extended in this work. The algorithm assembles an adjacency graph for these atomic values, and executes a structural analysis over this graph, looking for patterns that resemble structural constructs such as tuples and lists. From such constructs, a complex object type can be assigned to the extracted data. The experiments carried out using 21 collections of real Web pages have demonstrated the feasibility of our extraction method, reaching 94% of effectiveness using no more than 10 examples for each attribute. The HotCycles algorithm was able to infer a meaningful structure for the objects present in all used collections. Its effectiveness, combined with our atom extraction method, reached 97% of structures correctly inferred, also using no more than 10 examples per attribute. The association of these two methods has demonstrated to be extremely feasible. The high number of correctly inferred structures together with the high precision and recall values of the extraction process demonstrates that this new approach is indeed a promising one. / Hoje em dia a Web se apresenta como o maior repositório de informações da humanidade. Contudo, essa imensa gama de informação é formada principalmente por conteúdo textual e
necessariamente requer interpretação humana para se tornar útil. Por outro lado, existe uma grande quantidade de páginas na Web que são, na verdade, formadas por um conjunto implícito de objetos. Isso ocorre, por exemplo, em páginas oriundas de sites de catálogos on-line, bibliotecas
digitais e comércio eletrônico em geral. A extração desse conteúdo e a identificação da estrutura dos objetos disponíveis permite uma forma mais sofisticada de processamento além da tradicional navegação por hiperlinks e consultas por palavras-chave. A tarefa de extrair dados de páginas Web é executada por progamas chamados extratores ou wrappers. Neste trabalho propomos uma nova abordagem para o desenvolvimento de extratores. Nessa abordagem o usuário se restringe a fornecer exemplos de treinamento para os atributos que constituem os objetos de interesse. Baseado nesses exemplos, são gerados automaticamente padrões para extrair dados inseridos em contextos similares áqueles fornecidos como exemplos. Em seguida, esses dados são automaticamente organizados segundo uma estrutura plausível. Nosso método de geração de padrões de extração utiliza técnicas herdadas de soluções para o problema do alinhamento múltiplo de seqüências. O método é capaz de produzir padrões de extração que podem ser facilmente transformados em expressões regulares. A tarefa de inferir
uma estrutura plausível para os objetos extraídos é realizada pelo algoritmo HotCycles, que foi previamente proposto e que foi revisto e ampliado neste trabalho. O algoritmo constrói um grafo de adjacências para esses dados, e realiza nele, uma análise estrutural em busca de padrões que indiquem construtores estruturais como tuplas e listas. A partir de tais construtores, é associado um tipo aninhado aos dados que foram extraídos da página. Experimentos realizados em 21 coleções de páginas reais da Web demonstram a viabilidade
do método de extração de valores atômicos, obtendo um desempenho superior a 94% e utilizando no máximo 10 exemplos de treinamento por atributo. O algoritmo HotCycles foi capaz de inferir uma estrutura plausível para os objetos em todas as coleções utilizadas. Seu desempenho combinado
com o método de extração de valores atômicos chegou a 97% de estruturas corretamente inferidas com a utilização também até 10 exemplos por atributo. A combinação desses dois métodos demonstrou-se extremamente viável. Os altos índices de estruturas corretamente inferidas juntamente com os elevados índices de precisão e revocação do processo de extração demonstram que esta é sem dúvida uma abordagem promissora.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/2936 |
| Date | 03 March 2006 |
| Creators | Oliveira, Daniel Pereira de |
| Contributors | Silva, Altigran Soares da |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, BR, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | -312656415484870643, 600 |
Page generated in 0.002 seconds