[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

string matching algorithm

David Weldon

11/24/2007 10:41:00 PM

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-...to...

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-....
4 Answers

Axel Etzold

11/24/2007 10:55:00 PM

0


-------- Original-Nachricht --------
> Datum: Sun, 25 Nov 2007 07:40:50 +0900
> Von: David Weldon <dweldon@gmail.com>
> An: ruby-talk@ruby-lang.org
> 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-...to...
>
> 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-....

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/g...

Axel Etzold

11/24/2007 10:59:00 PM

0


-------- Original-Nachricht --------
> Datum: Sun, 25 Nov 2007 07:40:50 +0900
> Von: David Weldon <dweldon@gmail.com>
> An: ruby-talk@ruby-lang.org
> 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-...to...
>
> 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-....

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/mult...

Alex Young

11/25/2007 1:05:00 AM

0

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

David Weldon

11/25/2007 2:35:00 AM

0

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-....