2013-11-25 Edit distance and weights
I often had to implement an edit distance and I most of time chose to use uniform weights : every modification costs 1. That's the easy solution. However, I was looking for a quick way to give different weights to every comparison between twwo characters.
So I went to the site Gutenberg and downloaded a few texts. I then did the following:
- I split the text into lower case words.
- I grouped them by length.
- For all words having the same length, I looked for words with one letter difference.
- I counted the number of times the same pair was that differences.
- I normalized by the number of pairs and took 1-p where p the frequency of a pair.
more...
2013-02-10 Edit distance and sequence alignment
Some algorithms, you cannot avoid implementing them a couple of times every year. When you work for a search company, you always deal with text. You use regular expressions almost every week. The edit distance is one of these algorithms you never find in the company's wiki or not in the programming language you expect. The code references some weird assembly you don't need and don't want. Or simply, this time, you don't need the distance but the path between the two sequences. You expect to find this algorithm to be somewhere present, accessible, somewhere you don't have to look for, somewhere on the company's wiki. But surprisingly, everybody did his own, not documented, including unexpected paramters. I wish I could even keep myself some versions I made but I often implemented the edit distance in a way that it was faster for my specific needs at that time. Even for this blog (How to normalize an edit distance ?), I did it again. I remember one time doing it to prove my students the edit distance was another versions of the shortest path in a graph. I did it again today: edit_distance_alignment.py. Maybe it will be the last time?
2013-01-30 Graph matching and alignment
Pipelines became a quite popular way to represent a workflow. Many tools such as RapidMiner, Orange or Weka use graphs to represent the sequence of processes data follow. Most of the time, between two experiments, we just copy paste a previous one, we add or delete a few nodes. After a while, it becomes uneasy to find out what modifications were made. I was wondering how it would be possible to automate such a task. How to find what modifications were introduced in a graph ?
 |
 |
 |
| Graph 1 | Graph 2 | Two graphs we would like to merge into a single one. Vertices 00 and 11 represents the only root and the only leave. |
more...
2013-01-25 How to normalize an edit distance ?
An edit distance is usually used to compute a distance between two words. The basic version gives the same weight to every mistake or operation which means every comparison, every insertion or deletion between two words weight the same. The sum of all these errors gives a integer score and most of time, it is better to keep that score within an interval such as [0,1].
Most of the time, we divide the edit distance by the length of the longest word involved in that distance. This score is not a distance anymore in a sense it does not verify the triangular inequality. There are many option and the following document studies some aspects of normalizations. Based on that, the maximum length is not the best option, the minimum length is not very good either. A third option studied in that document seems to be the best, especially if this distance is used by a machine learned model as a feature.
|
Xavier Dupré
|
