# String matching algorithm

**URL:** <https://www.ruby-forum.com/t/string-matching-algorithm/121182>\
**Category:** Ruby\
**Created:** [November 24, 2007, 11:40pm UTC](https://www.ruby-forum.com/t/string-matching-algorithm/121182 "2007-11-24T23:40:53Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![dawillis](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/ebca7d/32.png) [@dawillis](https://www.ruby-forum.com/u/dawillis)\
**Post date:** [November 24, 2007, 11:40pm UTC](https://www.ruby-forum.com/t/string-matching-algorithm/121182/1 "2007-11-24T23:40:53Z")

</div>

Problem: 1 million+ strings (Set A) need to be matched with 1 million+  
substrings (Set B). For example:

Set A =  
iliketotraveltohawaii  
travelmagazine

Set B =  
travel  
hawaii

A(1,2) match “travel”  
A(1) matches “hawaii”

What is the best approach to take with this problem? I have tried using  
ferret:

[http://www.ruby-forum.com/topic/132772](http://www.ruby-forum.com/topic/132772)

Indexing is fast, but search is very slow. I think ferret could be a  
good choice if I had the substrings split out so iliketotraveltohawaii  
 → “i like to travel to hawaii”. I have a solution to this problem but  
it can’t be trusted with misspellings (that’s an entirely different  
forum topic). Is there something obvious that I’m missing here?

---

<div class="post-metadata">

**Author:** ![dawillis](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/ebca7d/32.png) [@dawillis](https://www.ruby-forum.com/u/dawillis)\
**Post date:** [November 24, 2007, 11:55pm UTC](https://www.ruby-forum.com/t/string-matching-algorithm/121182/2 "2007-11-24T23:55:15Z")

</div>

-------- Original-Nachricht --------

> Datum: Sun, 25 Nov 2007 07:40:50 +0900  
> Von: David W. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> An: removed\_email\_address@domain.invalid  
> Betreff: string matching algorithm

> ## → “i like to travel to hawaii”. I have a solution to this problem but it can’t be trusted with misspellings (that’s an entirely different forum topic). Is there something obvious that I’m missing here?
> 
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

Dear David,

just curious: how fast is Array#grep ?

a=%w[liketotraveltohawaii travelmagazine]  
b=%w[travel hawaii]

b.each\_with\_index{|x,i|  
if a.grep(x)  
puts 'entry ’ + i.to\_s + ’ in Array a matches ’ + x  
end  
}

Best regards,

Axel

---

<div class="post-metadata">

**Author:** ![dawillis](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/ebca7d/32.png) [@dawillis](https://www.ruby-forum.com/u/dawillis)\
**Post date:** [November 24, 2007, 11:59pm UTC](https://www.ruby-forum.com/t/string-matching-algorithm/121182/3 "2007-11-24T23:59:20Z")

</div>

-------- Original-Nachricht --------

> Datum: Sun, 25 Nov 2007 07:40:50 +0900  
> Von: David W. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> An: removed\_email\_address@domain.invalid  
> Betreff: string matching algorithm

> ## → “i like to travel to hawaii”. I have a solution to this problem but it can’t be trusted with misspellings (that’s an entirely different forum topic). Is there something obvious that I’m missing here?
> 
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

Dear David,

sorry, the last post wasn’t correct. I mean:

a=%w[liketotraveltohawaii travelmagazine]  
b=%w[travel hawaii]

b.each\_with\_index{|x,i|  
a.each{|y|  
if y.grep(x)  
puts 'entry ’ + y + ’ in Array a contains ’ + x  
end  
}  
}

Best regards,

Axel

---

<div class="post-metadata">

**Author:** ![dawillis](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/ebca7d/32.png) [@dawillis](https://www.ruby-forum.com/u/dawillis)\
**Post date:** [November 25, 2007, 2:05am UTC](https://www.ruby-forum.com/t/string-matching-algorithm/121182/4 "2007-11-25T02:05:39Z")

</div>

David W. wrote:

> A(1,2) match “travel”  
> A(1) matches “hawaii”
> 
> What is the best approach to take with this problem?

Bloom filters? It’s the fastest thing I can think of.

---

<div class="post-metadata">

**Author:** ![dawillis](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/ebca7d/32.png) [@dawillis](https://www.ruby-forum.com/u/dawillis)\
**Post date:** [November 25, 2007, 3:34am UTC](https://www.ruby-forum.com/t/string-matching-algorithm/121182/5 "2007-11-25T03:34:44Z")

</div>

I think I’m going to end up answering my own question here. I tried a  
bloom filter kind of approach and various grep schemes. None of which  
scaled well to large data sets. So far my best solution has been to use  
Ferret and index on trigrams instead of unigrams like I was doing  
before. That sped up my search by ~100x. I’m open to other ideas if  
anyone has them, but for now this should be fast enough.