# String 'close-to' comparison

**URL:** <https://www.ruby-forum.com/t/string-close-to-comparison/133742>\
**Category:** Ruby\
**Created:** [April 3, 2008, 6:32am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742 "2008-04-03T06:32:15Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![kyleh](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a9a28c/32.png) [@kyleh](https://www.ruby-forum.com/u/kyleh)\
**Post date:** [April 3, 2008, 6:32am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742/1 "2008-04-03T06:32:15Z")

</div>

Hello, I have an array. It contains approximately twenty elements which  
are strings. I also have one string - this string was obtained using an  
OCR system. One of the strings in the array should ‘match’ the string  
gotten using the OCR system - unfortunately OCRs aren’t perfect!

I want to take this string, and compare it to every string in the array,  
and attempt to return the closest match.

I.E.,  
array = [‘Hello there, how are you?’, ‘What did you do over your  
break?’, 'I like my coffee brown.", “I just bought a new car.”]  
string = “What did you d0 over your brcak?”

And then have my comparison function return array[1]. As you can see,  
string has some ‘OCR errors’ - it’s usually 80-95% accurate, if not  
dead-on.

–  
Thanks, Kyle ‘Phenax’ Hunter  
[http://keletech.org/blog/](http://keletech.org/blog/)

---

<div class="post-metadata">

**Author:** ![kyleh](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a9a28c/32.png) [@kyleh](https://www.ruby-forum.com/u/kyleh)\
**Post date:** [April 3, 2008, 7:25am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742/2 "2008-04-03T07:25:57Z")

</div>

If you know all the possibilities that your OCR system _could_ pick up  
then you could always do something like this…

knownStrings = [‘Hello’,‘Goodbye’]  
out = []  
OCR\_strings = #new array of strings

OCR\_strings.each do |ocr|  
matches,len = 0,0  
knownStrings.each do |known|  
len = known.length  
(len-1).times do |i|  
if (i+1) \>= ocr.length  
break  
else  
if ocr[i] == known[i]  
matches += 1  
end  
end  
if matches / known.length \> 0.85  
out \<\< known  
else  
out \<\< “!#{known}”  
end  
end  
end  
end

…completely untested but i think you know what im getting at

---

<div class="post-metadata">

**Author:** ![kyleh](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a9a28c/32.png) [@kyleh](https://www.ruby-forum.com/u/kyleh)\
**Post date:** [April 3, 2008, 7:27am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742/3 "2008-04-03T07:27:59Z")

</div>

> ```
> if matches / known.length > 0.85
> out << known
> else
> out << "!#{known}"
> end
> 
> ```

should be more like

if matches / known.length \> 0.85  
out \<\< known  
end

---

<div class="post-metadata">

**Author:** ![kyleh](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a9a28c/32.png) [@kyleh](https://www.ruby-forum.com/u/kyleh)\
**Post date:** [April 3, 2008, 7:48am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742/4 "2008-04-03T07:48:00Z")

</div>

Hi,

Kyle H. wrote:

> Hello, I have an array. It contains approximately twenty elements which  
> are strings. I also have one string - this string was obtained using an  
> OCR system. One of the strings in the array should ‘match’ the string  
> gotten using the OCR system - unfortunately OCRs aren’t perfect!
> 
> I want to take this string, and compare it to every string in the array,  
> and attempt to return the closest match.
> 
> I.E.,  
> array = [‘Hello there, how are you?’, ‘What did you do over your  
> break?’, 'I like my coffee brown.", “I just bought a new car.”]  
> string = “What did you d0 over your brcak?”
> 
> And then have my comparison function return array[1]. As you can see,  
> string has some ‘OCR errors’ - it’s usually 80-95% accurate, if not  
> dead-on.
> 
> –  
> Thanks, Kyle ‘Phenax’ Hunter  
> [http://keletech.org/blog/](http://keletech.org/blog/)  
> Here is a simple score matching code:

array = [‘Hello there, how are you?’, ‘What did you do over your  
break?’,  
‘I like my coffee brown.’, ‘I just bought a new car.’]  
string = “What did you d0 over your brcak?”

def comp(str1,str2)  
a=str1.split(‘’).uniq  
b=str2.split(‘’).uniq  
(a+b).uniq.length\*1.0/(a.length+b.length)  
end

puts array.sort\_by{|x|comp(string,x)}.first

Regards,  
Park H.

---

<div class="post-metadata">

**Author:** ![kyleh](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a9a28c/32.png) [@kyleh](https://www.ruby-forum.com/u/kyleh)\
**Post date:** [April 3, 2008, 9:13am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742/5 "2008-04-03T09:13:10Z")

</div>

On Apr 2, 2008, at 10:32 PM, Kyle H. wrote:

> ## – Thanks, Kyle ‘Phenax’ Hunter [http://keletech.org/blog/](http://keletech.org/blog/)
> 
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

[http://amatch.rubyforge.org/](http://amatch.rubyforge.org/)

a @ [http://codeforpeople.com/](http://codeforpeople.com/)

---

<div class="post-metadata">

**Author:** ![kyleh](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/a9a28c/32.png) [@kyleh](https://www.ruby-forum.com/u/kyleh)\
**Post date:** [April 3, 2008, 8:15am UTC](https://www.ruby-forum.com/t/string-close-to-comparison/133742/6 "2008-04-03T08:15:54Z")

</div>

On Apr 2, 10:32 pm, Kyle H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> break?', 'I like my coffee brown.", “I just bought a new car.”]  
> string = “What did you d0 over your brcak?”
> 
> And then have my comparison function return array[1]. As you can see,  
> string has some ‘OCR errors’ - it’s usually 80-95% accurate, if not  
> dead-on.
> 
> ## – Thanks, Kyle ‘Phenax’ Hunterhttp://keletech.org/blog/
> 
> Posted viahttp://www.ruby-forum.com/.

It sounds like what you want is something like the Levenshtein  
distance ([Levenshtein distance - Wikipedia](http://en.wikipedia.org/wiki/Levenshtein_distance)).

HTH,  
Chris