On the marriage of strings

Abstract

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.