Re: Trie?

["Andy Stark" <AStark@...>]

Lua list <lua@bazar2.conectiva.com.br> writes:

>> Hmmm... well... in this specific case... it's for implementing 
>> something like a full text search... e.g. given 'hell' and 'hello' 
>> return both for a partial match on 'hel'... a trie looks like an 
>> attractive structure for such search, no?
>
>I'd create a table of possible matches from a list of words.
>For instance,
>	t['hell'] = { 'hell', 'hello', ... }

If you want to index a text to allow searching for any substring (ie, not
just individual words) then this method might be a problem because you
would need a table with all possible substrings as keys and all possible
text positions for each substring in the list (just having strings in the
list doesn't tell you where in the text the pattern occurred). So you
would have:-

"he was there"
   .
   .
t['e'] = {2, 10, 12}
   .
   .
t['he'] = {1, 9}

I think the number of distinct substrings is roughly proportional to (n
(n-1)) / 2 where n is the length of the string. A Patricia tree is
probably what you are looking for if you are doing indexed text search:-

     http://en.wikipedia.org/wiki/Patricia_tree

Unfortunately, I don't have an implementation, which was what you
originally asked for ;-)

&.


#####################################################################################
This e-mail message has been scanned for Viruses and Content and cleared 
by MailMarshal.
The Blackpool Sixth Form College.
#####################################################################################