Re: Trie?

[PA <petite.abeille@...>]

On May 29, 2007, at 10:57, Philippe Lhoste wrote:

> PA, I am not sure my code can have any utility for you (it is mostly 
> to check whole words, although one can end before reaching the end) 
> but it was an opportunity to show it. ;-)

I'm always curious about, ahem, curiosities... so bring it on :)

To keep you company, here is a rather wacky pseudo implementation which 
uses the file system to persist its data structure...

Usage example:

local aTrie = Trie( 'trie' )

local aString = [[
It’s easy to find, in the mightily expanding iconography of American 
waste, the monumental (a ziggurat of flattened cars), the sinister 
(ocher sludge foaming on a riverbank) and the sublime (a plastic bag 
fluttering in a Japanese maple). The empty bottle and crushed aluminum 
can are none of these. They are almost too commonplace to notice, too 
dreary to evoke anything at all. Foundered on a roadside or slumped in 
a bag of spent Chinese takeout, the can without its Mountain Dew and 
the bottle without its Bud are unremarkable things. They’re just trash: 
something we once wanted and now can’t be bothered with.
]]

for aWord in aString:gmatch( '([%S]+)' ) do
    aWord = aWord:gsub( '%p', '' )
    aTrie[ aWord ] = aWord
end

for anIndex, aValue in ipairs( aTrie[ 'a' ] ) do
    print( anIndex, aValue )
end

> 1       a
> 2       at
> 3       are
> 4       anything
> 5       and
> 6       American
> 7       aluminum
> 8       almost
> 9       all

Attachment: Trie.lua
Description: Binary data