Use este identificador para citar ou linkar para este item: https://rd.uffs.edu.br/handle/prefix/2699
Tipo: Monografia
Título: On the marriage of strings
Autor(es): Galli, Gabriel Batista
Primeiro Orientador: Wuerges, Emílio
Primeiro coorientador: Bins, José
Abstract/Resumen: Given two sets L and R of strings such that R is the result of applying unknown transformations to L, match every string in L to its corresponding transformed string in R. This problem was proposed at the 2018 International Conference on Computer-Aided Design (ICCAD) CAD Contest, to which this work studies a deterministic solution using graph theory and approximate string matching. From graph theory, bipartite matching and stable marriage are reviewed; from approximate string matching, suffix array, edit distance, q-gram distance and q-gram index are considered. Three other algorithms are proposed based on these concepts, two of which only serve the purpose of being baselines to the others. The proposed solution itself is divided in three steps: the construction of filters (or indexes) on L and R with suffix array or q-gram index; the calculation of the adjacency (preference) lists for the graph G = ({L∪R},E) with edit or q-gram distance as edge weights; and, finally, the computation of the bipartite matching. A framework for benchmarking the run time and accuracy of this approach was built. It also allows an easy switching between the available algorithms. The most significant outcome of the benchmarks is that the filtering step is the bottleneck of the proposed methodology. It affects accuracy and prevents a proper reasoning about the impact of some of the compared algorithms. Never the less,the works of the winning teams of the contest managed to achieve 100% of accuracy. When they are published, it will be possible to study their solutions and perhapsbetter understand the compromises of our choices in order to propose improvements to our approach.
Palavras-chave: Ciência da computação
Algoritmos
Teoria dos grafos
Benchmarking
Idioma: eng
País: Brasil
Instituição: Universidade Federal da Fronteira Sul
Sigla da Instituição: UFFS
Faculdade, Instituto ou Departamento: Campus Chapecó
Tipo de Acesso: Acesso Aberto
URI: https://rd.uffs.edu.br/handle/prefix/2699
Data do documento: 2018
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
GALLI.pdf638,28 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.