1
$\begingroup$

My aim is to find an edit distance algorithm which penalises transformations differently depending on the phonetic context.

Take the Levenshtein algorithm, for example; it penalises the same operation - like a character substitution - equally, regardless of character context.

However, it seems to me that all substitutions/insertions/deletions are not made equal. For example, in some contexts, the transformation C->K should not be as harshly penalised as A->T.

A phonetic algorithm, like Double Metaphone, can help here. It maps both kosmetik and cosmetic to the same phonetic key, but it's aggressive and discards information. There's a clear difference between these two strings even though the phonetic key is the same.

Simply taking the Metaphone key and applying an edit distance algorithm is a poor choice for my goal.

Does a suitable method exist here? Or is the best option to manually fiddle with the internals of an edit distance algorithm?

$\endgroup$
1
$\begingroup$

The operations in the edit distance can have different weights that you can try to set manually. In Python, you can use e.g., strsympy or weighted-levenshtein package.

There is also Learnable Edit Distance algorithm that allows learning the operation weights from data. I think it might be a good idea first to estimate the operation cost first manually and then fine-tune it with the learning algorithm. Unfortunately, I am not aware of any reasonable implementation.

There is also a CRF-based classifier that is based on the learnable edit distance. Based on training data, it estimates the probability of one string being a transcription of another one. This approach requires positive and negative training examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.