Hi,
Just encountered some weird behaviors of trie:is_prefixed/2.

76> Foo = trie:store("abc",value,trie:new()).
{97,97,{{"bc",value}}}
77> trie:is_prefixed("abcdefghijk",Foo).     
false

78> Bar = trie:store("abcd",value,Foo).      
{97,97,
 {{{98,98,{{{99,99,{{{100,100,{{[],value}}},value}}},error}}},
   error}}}
79> trie:is_prefixed("abcdefghijk",Bar).     
true

Although utterly unfamiliar with trie, is this behavior intended?
Or I'm just using it wrong? 😂

After a little source code digging, it seems like L625-626 only matches when calling trie:is_prefixed(Key,Trie) with a pre-existing Key in Trie, which is essentially calling

trie:is_prefixed("abc",Foo).

Maybe change it to this?

{MaybePreT, _} ->
    case lists:prefix(MaybePreT,T) of true -> true; false -> false end;

Will this break the properties of trie? 😂

FYC, some tracing messages:

7> trie:is_prefixed("abc",Foo).
(<0.41.0>) call trie:is_prefixed("abc",{97,97,{{"bc",value}}})
(<0.41.0>) returned from trie:is_prefixed/2 -> true
true

8> trie:is_prefixed("abcdefghijk",Foo).                                                                                   
(<0.41.0>) call trie:is_prefixed("abcdefghijk",{97,97,{{"bc",value}}})
(<0.41.0>) returned from trie:is_prefixed/2 -> false
false

9> trie:is_prefixed("abcdefghijk",Bar).     
(<0.41.0>) call trie:is_prefixed("abcdefghijk",{97,97,{{{98,98,{{{99,99,{{{100,100,{{[],value}}},value}}},error}}},error}}})
(<0.41.0>) call trie:is_prefixed("bcdefghijk",{98,98,{{{99,99,{{{100,100,{{[],value}}},value}}},error}}})
(<0.41.0>) call trie:is_prefixed("cdefghijk",{99,99,{{{100,100,{{[],value}}},value}}})
(<0.41.0>) returned from trie:is_prefixed/2 -> true
(<0.41.0>) returned from trie:is_prefixed/2 -> true
(<0.41.0>) returned from trie:is_prefixed/2 -> true
true

Hi,

It seems like fetch_keys_similar will sometimes return the keys from the whole tree rather than the ones I expect.

Here's an example:

L = [{"00", zeros}, {"11", ones}],
T = trie:from_list(L),
io:fwrite("Data: ~p\n", [L]),
io:fwrite("Keys that start with \"0\": ~p\n", [trie:fetch_keys_similar("0", T)]),

As output I get:

Data: [{"00",zeros},{"11",ones}]
Keys that start with "0": ["00","11"]

It doesn't seem to happen very often and it's quite rare when the trie is big. It doesn't happen with single character keys.

I did a little digging through the code and it seems like it's something to do with fold_similar_node when the child node is a binary, which ends up calling fold_similar_element on the whole trie. I'm not sure if that's helpful but there it is anyway ;-)

Cheers,
Sam.

Interesting library! For a search for similar things, like fold_similar, has there been any thinking around being able to reduce the number of search results, like being able to specify N, where N is the maximum number of search results one would like to be returned.

The use case is that one might use this library as part of some lookup engine where you might have many entries stored in the trie, but there really is no need to present the entire database (or all entries that match the first character) to the user as he/she searches, but just giving a few and then indicating that there would be others to be found if the user specifies further characters - pretty much how google search does it I guess. I suppose this could be done either in the form of providing search results as an iterator that you could iterate through or to, as mentioned above, being able to specify some offset and limit when performing fold_similar and the likes.

(feel free to close this issue if it's just irrelevant)

Hi
Thumbs up for the library. I am trying to use trie in elixir from v1.7.4.

And I just created some small tests, in which I try your samples , and I noticed that for example :trie.new([{"abcdefghijklmnopqrstuvwxyz", 1},{"aac", 2}]) throws an exception:
** (FunctionClauseError) no function clause matching in :trie.store/3 in trie/src/trie.hrl:1005: :trie.store/3

I also tried btrie, and this one is working. Maybe I am doing something wrong.

I tried the trie functionality in erlang shell and it is working, so it seams that it is crashing only in elixir ( I compiled the code before trying)

I have:
Erlang/OTP 21 and Elixir 1.7.3

Thank you,

I have a need for utf8 keys. How far away is support for these?

Not entirely sure weather this is me misusing it but I fail to get find_prefixes/2 to return any data other then an empty list.

3> T1 = btrie:append(<<"this is a test year really!">>, t, btrie:new()).
{116,116,{{<<"his is a test year really!">>,[t]}}}
4> btrie:find_prefixes(<<"this">>, T1).
[]
5> btrie:find_prefix(<<"this">>, T1).
prefix