# string matching algorithm

Discussion in 'Ruby' started by David Weldon, Nov 24, 2007.

1. ### David WeldonGuest

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?
--
Posted via http://www.ruby-forum.com/.

David Weldon, Nov 24, 2007

2. ### Axel EtzoldGuest

-------- Original-Nachricht --------
> Datum: Sun, 25 Nov 2007 07:40:50 +0900
> Von: David Weldon <>
> An:
> 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?
> --
> 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
--
GMX FreeMail: 1 GB Postfach, 5 E-Mail-Adressen, 10 Free SMS.
Alle Infos und kostenlose Anmeldung: http://www.gmx.net/de/go/freemail

Axel Etzold, Nov 24, 2007

3. ### Axel EtzoldGuest

-------- Original-Nachricht --------
> Datum: Sun, 25 Nov 2007 07:40:50 +0900
> Von: David Weldon <>
> An:
> 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?
> --
> 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

--
Psssst! Schon vom neuen GMX MultiMessenger gehĂ¶rt?
Der kann`s mit allen: http://www.gmx.net/de/go/multimessenger

Axel Etzold, Nov 24, 2007
4. ### Alex YoungGuest

David Weldon wrote:
> 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.

--
Alex

Alex Young, Nov 25, 2007
5. ### David WeldonGuest

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.
--
Posted via http://www.ruby-forum.com/.

David Weldon, Nov 25, 2007