String matching algorithm

Ruby
1

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

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?

2

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

Datum: Sun, 25 Nov 2007 07:40:50 +0900
Von: David W. [email protected]
An: [email protected]
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/.

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

3

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

Datum: Sun, 25 Nov 2007 07:40:50 +0900
Von: David W. [email protected]
An: [email protected]
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/.

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

4

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.

5

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.