Levenshtein distance

Apr20th
2012 3 Comments Written by Ahmed Toulan

Introduction

Levenshtein distance (some times also called Edit distance) is an algorithm developed by Vladimir Levenshtein in the year 1965. It can be defined as the smallest number of transformations needed to changed one string to another. These transformations can be either substitution, insertion or deletion. So, in other words, if we want to convert one string to another we would do some operations. The minimum number of operations is the Levenshtein distance we’re looking for.

Levenshtein distance has a lot of applications including plagiarism detection, cryptanalysis and our dear everyday use with spelling correction.

Example

To understand it in a better way assume we have 2 strings ‘a’ and ‘b’. Now I would try to solve this in a brute force way and then get the minimum distance.

Option 1: Substitute ‘a’ with ‘b’ , therefore the distance will be 1

‘a’ => ‘b’

Option 2: Delete ‘a’ then insert ‘b’, therefore the distance will be 2

‘a’ => ” => ‘b’

It goes without saying that Option 1 is the distance we are looking for. For trivial examples like the one I just gave above there is no need for a special algorithm, but when the inputs look like this,

shsakljhfjsahfdkljshdfkjsajhsdakjfhsasjddshfkjhjsdhfkjhfksjhfjshjfhsk

uiweyriuwqerbcvnbzxgwygrsdjndsfhidfhncvmncvkljadhiahdfkljd

we can’t really do anything without the algorithm.

The algorithm

Levenshtein distance is calculated using Dynammic programming algorithm which is concerned with solving smaller (constrained) versions of the problem till we find the best solution of our problem. We will follow a simple example to show how the algorithm is used. Some forms of the algorithm give different weights for different transformations, but we will assume that all transformations have the same weight and that is equal to 1 for the sake of simplicity.

Example

Assume we have the 2 strings ‘low’ and ‘twin’. We want to find the minimum distance between them. To do this we construct a table that looks like this.

		t	w	i	n
	0	1	2	3	4
l	1
o	2
w	3

This is your starting point. Each cell of this table is a small constrained version of the problem that we need to find its solution. Now lets start with our smallest problem, and that’s the comparison of the first 2 letters from both words. In our example ‘l’ and ‘t’ are not equal. So a transformation is needed, in other words we have the value one (if equal the value will be zero since there are no transformations needed). Now wait before you place that one in the cell. This comparison depends on comparisons from cells adjacent to it, as we are trying find the least possible transformations for the whole string. So we calculate the following,

The cell on the upper left (diagonally):

0 + transformation error(in this case one) = 0 + 1 = 1

The cell on the left(horizontal):

1 + 1 = 2

The cell directly above(vertical):

1 + 1 = 2

and since one is less than two we can safely say that this cell will have a value of one.

		t
	0	1
l	1	1

We will continue to do the same with the next cell. The same as before we will consider the three cells adjacent to it.

The cell on the upper left (diagonally):

1 + 1 = 2

The cell on the left(horizontal):

1 + 1 = 2

The cell directly above(vertical):

2 + 1 = 3

From the above values the minimum transformations are 2.

		t	w
	0	1	2
l	1	1	2

We will continue to do this until the table is complete,

		t	w	i	n
	0	1	2	3	4
l	1	1	2	3	4
o	2	2	2	3	4
w	3	3	2	3	4

that last cell is the minimum number of transformations needed to transform ‘low’ to ‘twin’.

You can check the algorithm’s implementation in several programming languages here.

Thanks for reading and comments are really welcome.

Programming algorithm, Programming

Grouping Python dictionaries in hierachical form

Apr15th
2012 Leave a Comment Written by Ahmed Toulan

This is based on a question I asked on stackoverflow

Assuming we have data that looks like this:

[{'dept':1, 'age':10, 'name':'Sam'},
{'dept':1, 'age':12, 'name':'John'},
{'dept':2,'age':20, 'name':'Mary'},
{'dept':2,'age':11, 'name':'Mark'},
{'dept':2,'age':11, 'name':'Tom'}]

This is a sorted list of dictionaries. Now if we want to group the data using one key, dept for example, we can use itertools to do the job:

group_list = []
for key, items in itertools.groupby(res, operator.itemgetter('dept')):
    group_list.append({key:list(items)})

and the output would be:

[{1:[{'dept':1, 'age':10, 'name':'Sam'},
    {'dept':1, 'age':12, 'name':'John'}],
 {2:[{'dept':2,'age':20, 'name':'Mary'},
    {'dept':2,'age':11, 'name':'Mark'},
    {'dept':2,'age':11, 'name':'Tom'}]
]

Now if we try multiple keys, dept and age, the output would be:

[{(2, 20): [{'age': 20, 'dept': 2, 'name': 'Mary'}]},
 {(2, 11): [{'age': 11, 'dept': 2, 'name': 'Mark'},
            {'age': 11, 'dept': 2, 'name': 'Tom'}]},
 {(1, 10): [{'age': 10, 'dept': 1, 'name': 'Sam'}]},
 {(1, 12): [{'age': 12, 'dept': 1, 'name': 'John'}]}]

That’s great, but not exactly what I want. What I want should look like this:

[
    {
        2: {
            20: [
                {
                    'age': 20,
                    'dept': 2,
                    'name': 'Mary'
                }
            ]
        },
        {
            11: [
                {
                    'age': 11,
                    'dept': 2,
                    'name': 'Mark'
                },
                {
                    'age': 11,
                    'dept': 2,
                    'name': 'Tom'
                }
            ]
        }
    },
    {
        1: {
            10: [
                {
                    'age': 10,
                    'dept': 1,
                    'name': 'Sam'
                }
            ]
        },
        {
            12: [
                {
                    'age': 12,
                    'dept': 1,
                    'name': 'John'
                }
            ]
        }
    }
]

itertools doesn’t have built-in tree builder so it needs to be done using recursive calls.
The final code would be:

import itertools, operator

l = [{'dept':1, 'age':10, 'name':'Sam'},
        {'dept':1, 'age':12, 'name':'John'},
        {'dept':2,'age':20, 'name':'Mary'},
        {'dept':2,'age':11, 'name':'Mark'},
        {'dept':2,'age':11, 'name':'Tom'}]

groups = ['dept', 'age', 'name'] 

groups.reverse()
def hierachical_data(data, groups):
    g = groups[-1]
    g_list = []
    for key, items in itertools.groupby(data, operator.itemgetter(g)):
        g_list.append({key:list(items)})
    groups = groups[0:-1]
    if(len(groups) != 0):
        for e in g_list:
            for k,v in e.items():
                e[k] = hierachical_data(v, groups)

    return g_list

print hierachical_data(l, groups)

Programming itertools, Programming, python

Lucid Lynx Release Party at Cairo University

Apr26th
2010 Leave a Comment Written by Ahmed Toulan

Ubuntu-eg is organizing a Release Party for Lucid Lynx release. We are planning to give the following sessions beside helping people to install the newest release of Ubuntu.

Licensing and Free culture – Mohammed Gamal
How to install Ubuntu – Mohammed Saudi
Desktop programming using Qt – Ahmed Toulan
Desktop programming using GTK – Mohamed Habib
Drupal – AbdelRahman Ghareeb
Joomla – Jonathan
Software Alternatives and Desktop walkthrough – Mahmoud Mohammed
Graphic design using Inkscape – Anas Emad
Java programming on Ubuntu – Ahmed Saad
Open source 3D graphics using Blender – Islam AlWazery

Hope to see all of you there.

Announcements, ubuntu-eg release party, ubuntu-eg

Finally Qt is really open!

May12th
2009 Leave a Comment Written by Ahmed Toulan

Yesterday a great announcement was made. Qt is now open to the public. Nokia aimed to make Qt a defacto standard by changing the license to LGPL V2.1 last March.

Now with their repositories open everyone can join! So go ahead and visit http://qt.gitorious.org/ and have a role in the creation and refining of this great library.

Announcements qt

Robotic life

May7th
2009 1 Comment Written by Ahmed Toulan

The idea to have someone do things that we don’t like is common among all humans. That’s why we create machines to do our hard work. That’s why we hire someone to do stuff for us.

That’s pretty normal, but when it comes to social events for example, that’s pretty hard to do. I can’t imagine someone sending someone else to do a seminar by his name

I guess humanity in the future will have the chance to do that, how ? I will tell you how. Robots is the answer. The robotic technology has experienced dramatic advances in the last few years. Now we have robots that can do facial expressions talk and respond (still not perfect). Some robots can play music instruments and others can move just like us.

We try to make robots as perfect as possible, we want them to take the right decision(always). We don’t want them to get angry for example. So implicitly we don’t want them to have feelings. So the problem remains, they are still not us. People will surely notice that you sent your robot to the wedding you didn’t want to attend, because the robot will respond in different ways than yours. It will be a lot different than the normal human experience.

The only solution I can think of to solve this, is to do the processing in different situations on the human brain (the owner of the robot). We should have a method of communication between the robot, who will have to send all the input, to the owner’s brain, that will process all the data and send back the response to the robot.

That way the robot will get angry if you’ll get angry, laugh if you’ll laugh. He will act as a human.

Assuming that the robots will be able to collect the right data and act upon receiving the response, there are still a lot of technical problems of course. The amount of bandwidth we will need to send the info and receive the feedback. What type of protocols we can use ? What will happen if the communication faces some packet drops ? Will it be hard to the human brain to handle all this information ?

Unfortunately it may not happen in the near future. Being able to read information from the human brain isn’t science fiction anymore, but still a long way though.

Lets just wait and see …

Braindump, Future BCI, Future, robots

Levenshtein distance

Introduction

Example

The algorithm

Example

Grouping Python dictionaries in hierachical form

Lucid Lynx Release Party at Cairo University

Finally Qt is really open!

Robotic life

Let’s get social!

Recent Posts

Categories

Meta