Tag: trie

使用Trie实现T9字典？

我必须实现T9字典。 基本上，当我按下9个按键中的任何一个时，它应该显示可以用该组合键启动的前5个单词。 如果我输入’46’，它可以给’酒店’或’好’，这取决于当我按下4时我是打算’g’还是’h’。 优先级取决于哪些单词相对受欢迎 – 例如，您可以使用前100,000个单词中的前5000 个单词。 我正在做的代码是： import import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.Date; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; T9Dict类 public class T9Dict { private static final Runtime s_runtime = Runtime.getRuntime(); public static void main(String[] args) throws Exception { runGC(); long heap1 = usedMemory(); long start = new Date().getTime(); […]

Trie节省空间，但如何？

我很困惑Trie实现如何以最紧凑的forms节省空间并存储数据！ 如果你看下面的树。 在任何节点上存储字符时，还需要存储对该字符的引用，因此对于存储其引用所需的字符串的每个字符。 好的，当一个普通角色到达时我们节省了一些空间，但是在存储对该角色节点的引用时我们失去了更多空间。 那么维护这棵树本身不是很多结构开销吗？ 相反，如果使用TreeMap代替这个，让我们说实现一个字典，这可以节省更多的空间，因为字符串将被保存在一个片段中因此没有浪费存储引用的空间，不是吗？

需要内存有效的方法来存储大量的字符串（是：在Java中的HAT-Trie实现）

我正在处理一大组（5到2千万）字符串键（平均长度为10个字符） ，我需要将其存储在内存数据结构中，该结构在恒定时间或接近恒定时间内支持以下操作： // Returns true if the input is present in the container, false otherwise public boolean contains(String input) 就吞吐量而言，Java的Hashmapcertificate是令人满意的，但占用了大量内存。 我正在寻找一种内存效率高的解决方案，并且仍然支持良好的吞吐量（与散列相当或几乎一样好）。 我不关心插入/删除时间。 在我的应用程序中，我将仅执行插入（仅在启动时），并且随后将仅使用应用程序生命周期中的contains方法查询数据结构。 我读到HAT-Trie数据结构最接近我的需求。 我想知道是否有一个具有实现的库。 其他建议与实现的指针欢迎。 谢谢。

哈希数组映射Trie（HAMT）

我试图了解HAMT的细节。 我已经用Java实现了一个只是为了理解。 我熟悉Tries，我认为我得到了HAMT的主要概念。 基本上， 两种类型的节点： 核心价值 Key Value Node: K key V value 指数 Index Node: int bitmap (32 bits) Node[] table (max length of 32) 为对象生成32位哈希。 一次遍历5位哈希。 (0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31)注意：最后一步（第7步）仅为2位。 在每个步骤中，找到位图中该5位整数的位置。 例如， integer==5 bitmap==00001 如果该位为1，则存在该部分哈希。 如果该位为0，则密钥不存在。 如果密钥存在，通过计算位图中0和位置之间的1的数量，找到它在表中的索引。 例如， integer==6 bitmap==0101010101 index==3 如果表指向键/值节点，则比较键。 如果表指向索引节点，则转到2向前移动一步。 我不太了解的部分是碰撞检测和缓解。 在链接的论文中，他暗示： 然后将现有密钥插入新的子哈希表中并添加新密钥。 每次使用5个比特的散列时，碰撞的概率减少1/32。 有时可能会消耗整个32位哈希值，并且必须计算新的哈希值才能确定两个密钥。 如果我要计算一个“新”哈希并将该对象存储在该新哈希中; 你怎么能够在结构中查找对象？ […]

实现Patricia Trie用作字典

我正在尝试使用addWord() ， isWord()和isPrefix()方法实现Patricia Trie，以便存储大型单词词典以便快速检索（包括前缀搜索）。 我已经阅读了这些概念，但他们只是没有澄清实现。 我想知道（在Java或Python代码中）如何实现Trie，特别是节点（或者我应该递归地实现它）。 我看到一个人使用26个子节点的数组设置为null / None来实现它。 是否有更好的策略（例如将字母视为位）以及如何实现它？