string matching algorithm

D

David Weldon

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?
 
A

Axel Etzold

-------- Original-Nachricht --------
Datum: Sun, 25 Nov 2007 07:40:50 +0900
Von: David Weldon <[email protected]>
An: (e-mail address removed)
Betreff: string matching algorithm
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?

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
 
A

Axel Etzold

-------- Original-Nachricht --------
Datum: Sun, 25 Nov 2007 07:40:50 +0900
Von: David Weldon <[email protected]>
An: (e-mail address removed)
Betreff: string matching algorithm
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?

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
 
A

Alex Young

David said:
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?

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

David Weldon

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top