2

我使用 Trys 数据结构来存储单词。现在，我有一个要求，如果在同一段落中存在某些短语，则需要查找给定段落。

这样做最有效的方法是什么？短语总数不会超过 100 个。

4

2 回答 2

2

如果我是你，我会先使用 boost::multi_index_container 把一些东西放在一起，因为如果你以后有更多的需求，进一步扩展它会很容易。如果稍后您测量并发现它表现不佳，那么您可以将其替换为优化的数据结构。

于 2015-08-20T05:15:32.503 回答
1

指定的 trie 在许多方面都不是最优的。

  • 首先，它为每个插入的项目构建多个节点。正如作者所写，“输入键的每个字符都作为一个单独的 trie 节点插入。” 这是一个可怕的，不必要的惩罚！在这里使用ALPHABET_SIZE大于 2 会雪上加霜；不仅一个 50 字节的短语需要 50 个节点，而且每个节点的大小可能超过 100 个字节……使用该代码，每个 50 个字节长度的项目或“短语”可能需要多达 5KB 的存储空间！这还不是最糟糕的。
  • 该算法在内部提供了嵌入malloc，因此很难优化。每个节点都是自己分配的，insert非常malloc繁重。分配细节应该与数据结构处理分开，如果不是为了优化目的，那么为了使用简单。大量使用此代码的程序可能会遇到与内存碎片和/或缓存未命中相关的性能问题，除了将 trie 替换为其他内容之外，看不到任何简单或显着的优化。
  • 这不是这里唯一的问题......这段代码也不太便携！如果您最终在使用 EBCDIC 而不是 ASCII 的旧（不是那么旧；它们仍然存在！）大型机上运行此代码，则此代码将产生缓冲区溢出，并且将调用程序员（您）来修复它。<sarcasm>这太理想了，对吧？</sarcasm>

我编写了一个 PATRICIA trie 实现，它每个项目只使用一个节点，字母大小为 2（它使用每个字符的位，而不是每个字符），并允许您使用您希望的任何分配......唉，我还没有在重构它的界面上付出很多努力，但它应该相当接近最优。您可以在此处找到该实现。您可以在patricia_test.c测试用例文件中看到插入（使用patricia_add）、检索（使用patricia_get）和删除（使用）的示例。patricia_remove

于 2015-08-20T04:59:59.677 回答