0

这个问题与语言无关，更多的是关于了解如何实现 trie 或尝试是否适合我的程序应该做的事情。假设我有一串这样的文本。

string= "a tale about an ant and an android";

“a”对应的 trie 看起来像这样

      a(7)      
     /    \     
    b(1)  n(4)
    /     /   \
  o(1)  t(1)  d(2)
  /              \
 u(1)            r(1)
 /                 \
t(1)               o(1)
                     \
                     i(1)
                       \
                        d(1)

我想找到每个单词的出现次数。尽管“a”在文本中出现了 6 次，但只有一个实例将其用作单词。相同的规则适用于“an”和“and”。

我希望我的最终频率计数器看起来像这样：

a：发生 1 次而不是 7 次：2 和：1 等等..

我怎么可能记录完整的字数？

我在 php 中工作，试图处理大量文本并访问过这个问题，这不是我想要的。性能很重要，但内存效率更可取，因为我正在解析一万亿个单词。谢谢，我很感激你的意见。

4

2 回答 2

0

我建议使用三元树，然后在第三条边存储单词。然后你可以在其中实现一个单词计数器。

于 2013-04-15T23:17:58.957 回答
0

你可以通过两种方式做到这一点：

  1. 不是每次单词通过时都增加一个节点，而是仅在它结束时才增加

  2. 在单词的末尾有一个伪字母（比如空白），只有当单词在那里结束时才会增加。

于 2013-04-15T23:48:56.193 回答