问题标签 [patricia-trie]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
332 浏览

dart - Patricia/​​Radix-Tree 的 Dart 实现

我正在编写一个颤振应用程序。为此,我必须缓存一些地方并想要搜索名称。为此,我想使用基数特里树。我已经在 dart 下搜索了实现,但我没有发现任何有用的东西。

有人知道我在哪里可以找到实现吗?或者有没有人打扰过?

问候达戈伯特

0 投票
1 回答
92 浏览

patricia-trie - 为什么 Patricia 尝试在某些节点中使用反向链接,它的逻辑是什么?

我正在尝试实现我自己的 Patricia Trie 库以用于学习目的,所以在添加一些节点时我被卡住了,因为我得到的每个示例都有这些奇怪的反向链接,这对我来说毫无意义。这些链接有什么意义?其背后的逻辑是什么?

我看过几十个视频、论文(包括 Edward Fredkin 的原始论文)、书籍(Drozdek、Chapman、Cormen 等)和演示文稿,但我无法找到线索。

这是我制作的插入例程,忽略最后的评论,我试图自学并惨遭失败。

所以代码似乎正在工作,但我不明白为什么以及如何。

0 投票
1 回答
178 浏览

memory - 如何创建、更新和读取不适合内存的基数树?

我有兴趣使用基数树(或 Patricia trie)来存储strings -> values. 但是,我发现我有太多的字符串无法放入内存。

我发现Algolia 的一篇文章,介绍了他们如何通过搜索索引解决这个问题,他们谈到了我正在尝试做的事情:在构建每个分支时将基数树刷新到磁盘,并且只读回您需要的分支。

但是,他们没有提到他们是如何做到这一点的。我能想到的存储基数树的唯一方法是作为完整(序列化)对象或作为简单的键/值存储的哈希/数组。

例如,使用键/值存储

然后进行前缀扫描以提取MATCH smil*. 然而,这种方式失去了基数树节省空间的优势,而且它需要在负载时重建至少部分基数树。

0 投票
0 回答
13 浏览

tree - 如何删除 Patricia 树节点?

如何从 Patricia 中删除节点?帕特里夏我特别指的是基数二树,它的节点在树中向上指向以结束搜索。

0 投票
0 回答
6 浏览

blockchain - 以太坊黄皮书澄清 - Merkle Patricia Tree

我有一个关于黄皮书最新出版物附录 D 的快速问题。这与c的定义有关,特别是在图 (202) 的第二行,我正在努力解释这种解释的where j = max{...}部分。我想知道是否有人可以帮助我解决这个问题。谢谢!