Generalizing identity-based string comparison metrics: Framework and techniques

In this paper, we propose a framework that aims at handling metrics among strings defined over heterogeneous alphabets. Furthermore, we illustrate in detail its application to generalize one of the most important string metrics, namely the edit distance. This last activity leads us to define the Multi-Parameterized Edit Distance (MPED). As for this last metric, we investigate its computational properties and solution algorithms, and we present several experiments for its evaluation. As a final contribution, we provide several notes about some possible applications of MPED and other generalized metrics in different scenarios.