Erlang：这个 trie 实现最错误的地方是什么？

假期里，我的家人喜欢玩Boggle。问题是，我的Boggle 技术很糟糕。所以我做了任何优秀程序员都会做的事情：编写一个程序来给我玩。

该算法的核心是一个简单的前缀特里树 http://en.wikipedia.org/wiki/Trie，其中每个节点是一个dict下一个字母的参考文献。

这是trie:add执行：

add([], Trie) ->
    dict:store(stop, true, Trie);

add([Ch|Rest], Trie) ->
    % setdefault(Key, Default, Dict) ->
    %     case dict:find(Key, Dict) of
    %         { ok, Val } -> { Dict, Val }
    %         error -> { dict:new(), Default }
    %     end.
    { NewTrie, SubTrie } = setdefault(Ch, dict:new(), Trie),
    NewSubTrie = add(Rest, SubTrie),
    dict:store(Ch, NewSubTrie, NewTrie).  

您可以在此处查看其余部分以及如何使用它的示例（在底部）：

http://gist.github.com/263513 http://gist.github.com/263513

现在，这是我在 Erlang 中的第一个严肃的程序，我知道它可能有很多问题......但我最关心的是它使用800 MB 内存.

那么，我做的最错的是什么？我怎样才能让它少一点错误呢？

您可以通过简单地将单词存储在 ets 表中来实现此功能：

% create table; add words
> ets:new(words, [named_table, set]).
> ets:insert(words, [{"zed"}]).  
> ets:insert(words, [{"zebra"}]).    

% check if word exists
> ets:lookup(words, "zed").          
[{"zed"}]

% check if "ze" has a continuation among the words
78> ets:match(words, {"ze" ++ '$1'}).
[["d"],["bra"]]

如果 trie 是必须的，但您可以接受非功能性方法，那么您可以尝试digraph http://www.erlang.org/doc/man/digraph.htmls，正如保罗已经建议的那样。

如果您想保持功能正常，您可以通过使用使用较少内存的结构来节省一些字节的内存，例如proplist http://www.erlang.org/doc/man/proplists.htmls，或记录，例如-record(node, {a,b,....,x,y,z}).