# How to check how much two string are alike?

Page 1 of 1

## 3 Replies - 4063 Views - Last Post: 09 March 2012 - 12:50 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=270013&amp;s=f7df89c5cf519d1816a762264106d31e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 lnc12

• D.I.C Regular

Reputation: 1
• Posts: 268
• Joined: 21-May 08

# How to check how much two string are alike?

Posted 08 March 2012 - 11:14 AM

Hey I am having som troubles coming up with an algorithm for this:

I have to check how much for instance:

Caffe and latte is alike, so a and e are alike so 2/5 letters are a like.

Hope you get the idea
Do anyone have an idea.

Of course the string can be treated as a CHAR[] but ain't there a better way?
Is This A Good Question/Topic? 0

## Replies To: How to check how much two string are alike?

### #2 NotarySojac

• D.I.C Regular

Reputation: 53
• Posts: 428
• Joined: 30-September 10

## Re: How to check how much two string are alike?

Posted 08 March 2012 - 11:54 AM

Did you see Karel-Lodewijk's genetic algo submission? He uses zip and map and he converts the letters to ordinals (or something like that) and detects their difference all in like one line.

```\$alphabet.zip(candidate).map{|x| (x[1].ord-x[0].ord)**2}.inject(:+)

```

This won't help you take into account the phonetic quality of the strings though, nor their language overlaps or senses =D

Zip will zip together two arrays.

```a = "Caffe".chars.to_a
b = "latte".chars.to_a

z = a.zip(B)/>

z= [[C, l]
[a, a]
[f, t]
[f, t]
[e, e]]

```

From there, map is used to compare the characters (again, you'll need to connect or download a database of word senses if you need to make further scrutinize the strings).

This post has been edited by NotarySojac: 08 March 2012 - 12:01 PM

### #3 lnc12

• D.I.C Regular

Reputation: 1
• Posts: 268
• Joined: 21-May 08

## Re: How to check how much two string are alike?

Posted 08 March 2012 - 12:30 PM

Okay will look at it thanks man

### #4 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## Re: How to check how much two string are alike?

Posted 09 March 2012 - 12:50 PM

Well there are different metrics you can use to decide how similar strings are. Which one works best depends on your requirements. If you are looking for something that quantifies how similar two strings are intuitively, you could use something like http://en.wikipedia....shtein_distance . In short it counts how many operations (delete/remove/substitute letter) it takes to transform one string into another.

This page has some code in some different programming languages including ruby http://rosettacode.o...n_distance#Ruby .

I personally wouldn't recommend my code as a good metric for string distance. For one it takes the alphabetic order into account. so the distance between "aaaa" and "bbbb" will be much smaller than the distance between "aaaa" and "zzzz". And secondly it always compares letters at the same position, so "bqz" will be very different from "abqz", while they are obviously quite similar. NotarySojac has quoted my code slightly out of context unless of course you are trying your hands at the genetic algorithm contest, in that case go ahead:)

This post has been edited by Karel-Lodewijk: 09 March 2012 - 02:41 PM