trie相关内容

为什么 hash map 比 trie map 好?

trie map 是指关联数组，其中有效负载存储在 trie 而不是哈希表中. 当我使用哈希映射/表时，我使用的键通常是字符串.与某些基于 trie 的映射相比，哈希映射有哪些优势?我已经读过哈希映射更快 - 但在我看来，一致的哈希函数必须检查 (char) 数组的每个元素以获取最终哈希 - 遍历数组一次.在 trie 中，您同样必须只对数组进行一次迭代. 在我看来，这在对小对象进行编 ..

发布时间：2022-01-08 14:20:42 data-structures hashtable hashmap hashcode trie 其他开发

抑制 TRIE 的嵌套 Maps 的 Clojure 拉链

如何为由嵌套映射表示的 TRIE 创建 Clojure 拉链，键是字母吗? 像这样: {\b {\a {\n {\a {\n {\a {'$ '$}}}}}} \a {\n {\a {'$ '$}}}} 代表一个带有 2 个单词 'banana' 和 'ana' 的树.(如有必要，可以在地图中进行一些更改..) 我试图通过 map?vals assoc 分别作为拉链的 3 个功能. ..

发布时间：2022-01-02 22:49:36 clojure trie zipper 其他开发

后缀树和尝试.有什么区别?

我正在阅读Tries，通常称为前缀树和后缀树. 尽管我找到了 Trie 的代码，但我找不到 Suffix Tree 的示例.另外我觉得构建 Trie 的代码与 Suffix Tree 的代码相同，唯一的区别是在前一种情况下我们存储前缀，但在后缀. 这是真的?谁能帮我在脑海中清除它?示例代码会很有帮助！ 解决方案 后缀树可以看作是建立在 trie 之上的数据结构，其中，除了将字符串本身添 ..

发布时间：2021-12-22 08:26:33 algorithm data-structures trie suffix-tree 其他开发

尝试复杂性和搜索

创建单词列表的 trie 的复杂度是多少?在该树中搜索其他单词集?当我有哈希表时，我应该使用 trie 进行字符串搜索吗? 解决方案 创建一个 trie 的复杂度是 O(W*L)，其中 W 是数字L 是单词的平均长度:您需要对中的每个 W 单词的平均值执行 L 查找集合. 稍后查找单词也是如此:您对每个 W 单词执行 L 步骤. 哈希插入和查找具有相同的复杂性:对于每个单词，您 ..

发布时间：2021-12-22 08:21:39 algorithm data-structures time-complexity hashtable trie 其他开发

Trie 数据结构 - Java

是否有任何库或文档/链接提供了在 Java 中实现 Trie 数据结构的更多信息? 任何帮助都会很棒！ 谢谢. 解决方案 您可以阅读 Java Trie 或查看 trie. ..

发布时间：2021-12-22 00:03:10 java data-structures trie Java开发

如何在哈希表和 Trie(前缀树)之间进行选择?

因此，如果我必须在哈希表或前缀树之间进行选择，有哪些区别因素会导致我选择一个而不是另一个.从我自己幼稚的角度来看，似乎使用 trie 有一些额外的开销，因为它没有存储为数组，但在运行时间方面(假设最长的键是最长的英文单词)它本质上可以是 O(1)(关于上限).也许最长的英文单词是 50 个字符? 哈希表是即时查找一旦您获得索引.然而，对键进行哈希处理以获取索引似乎很容易需要近 50 个步骤. ..

发布时间：2021-12-22 00:00:35 algorithm data-structures hashtable trie 其他开发

尝试实现

在 C/C++ 中是否有任何速度和缓存高效的 trie 实现?我知道什么是特里，但我不想重新发明轮子，自己实现它. 解决方案 如果您正在寻找 ANSI C 实现，您可以从 FreeBSD “窃取"它.您要查找的文件名为 radix.c.用于管理内核中的路由数据. ..

发布时间：2021-12-21 23:58:20 c++ c data-structures trie C/C++开发

用于搜索/自动完成的弹性搜索或 Trie?

我对自动完成/搜索文本/项目的理解如何在任何可扩展的产品(如亚马逊电子商务/谷歌)中在高级别工作是:- 基于弹性搜索(ES)的方法 文档存储在 DB 中.一旦持久化给弹性搜索，它会创建索引并将索引/文档(基于标记器)存储在内存或基于磁盘中配置. 一旦用户输入3个字符，它就会搜索ES下的所有索引(甚至可以配置为索引ngram)，根据权重对它们进行排名并返回给用户 但是在阅读谷 ..

发布时间：2021-12-13 12:08:08 algorithm elasticsearch autocomplete trie 其他开发

我在哪里可以找到 Java 中基于 Trie 的标准地图实现?

我有一个 Java 程序，它存储了大量从字符串到各种对象的映射. 现在，我的选择是依靠散列(通过 HashMap)或二分搜索(通过 TreeMap).我想知道在流行的高质量集合库中是否有一种高效且标准的基于树的地图实现? 我过去写过自己的，但我更愿意使用标准的东西(如果有的话). 快速澄清:虽然我的问题很笼统，但在当前项目中，我正在处理大量由完全限定的类名或方法签名索引的数据.因 ..

发布时间：2021-11-25 18:11:40 java algorithm optimization trie Java开发

Trie vs. 后缀树 vs. 后缀数组

哪种结构提供了最好的性能结果；trie(前缀树)、后缀树还是后缀数组?还有其他类似的结构吗?这些结构有哪些好的 Java 实现? 编辑:在这种情况下，我想在大型名称词典和大型自然语言文本集之间进行字符串匹配，以识别文本词典的名称. 解决方案 trie 是第一个发现的此类数据结构. 后缀树是对 trie 的改进(它具有允许线性错误搜索的后缀链接，后缀树修剪了 trie 的不必要分 ..

发布时间：2021-11-18 02:52:36 java arrays data-structures trie Java开发

为什么我的尝试泄露数据?

我正在尝试使用 trie 制作拼写检查器，但我尝试添加到我的 trie 中的单词似乎没有输入.泄漏在哪里? 我花了几个小时使用调试器并逐步执行我的代码... 主要功能: /*** 实现拼写检查器.*/#include #include #include #include #include "dictionary.h"#undef 计算#undef getrusage//默认字典#de ..

发布时间：2021-09-09 19:58:03 c trie 其他开发

使用 Trie 在单词列表中查找复合词

给定一个单词列表，我想弄清楚如何在该列表中查找由列表中的其他单词组成的单词.例如，如果列表是 ["race", "racecar", "car"]，我想返回 ["racecar"]. 这是我的一般思考过程.我知道使用特里对这类问题有好处.对于每个单词，我可以使用 trie 找到它的所有前缀(也是列表中的单词).然后对于每个前缀，我可以检查单词的后缀是否由树中的一个或多个单词组成.但是，我很难 ..

发布时间：2021-09-09 19:58:00 python algorithm trie Python

编写带有节点步过的树状解析递归函数

目的:该函数通过匹配输入字符串的路径后面的字符串 trie 进行解析.当字符串中的所有字符都被解析后，返回true.如果仍然存在有效路径，我想跳过一个字符并返回. 应用程序:字符串是高速公路项目的位置层次结构.因此，项目 5 有一个路线 C，其偏移量为 N，工作区为 3；5CN3.但是，有时我想为涵盖所有位置的项目任务定义所有子位置的字符串.因此，“0"是所有位置；对于半天的操作，如等级泥土 ..

发布时间：2021-09-09 19:57:57 c++ visual-studio-2008 recursion trie C/C++开发

减少所有英语单词的 Trie 的大小

我正在使用 Trie 实现自动完成功能.使用 this 链接中的单词列表，我将每个单词插入到我的 Trie 中.我想减少 Trie 使用的内存，而不使用像有向无环字图这样太花哨的东西. Trie 是基于字典的，允许将其存储在 JSON 文件中.这是我当前的脚本: 导入json#试一试英文单词# 单词文件可以在 https://github.com/dwyl/english-words 找到 ..

发布时间：2021-09-09 19:57:54 python trie Python

按字母顺序打印尝试的算法

我一直忙于尝试用 C 编写一个 trie 有序树数据结构.我的程序一次一个地从 .txt 中读取一个句子中的单词，然后将每个单词存储在一个 trie 中，没有重复.然后它抓取该句子中的所有其他单词并将它们存储在存储的单词的子树中.例如，如果我们有以下句子:“为开源做出贡献."我的代码执行以下操作... 根ab'c'defghijklmn'o'pqr's''t'uvwxyz'o' 'p' 'o' ..

发布时间：2021-09-09 19:57:51 c trie 其他开发

使用特里树的 Python 拼写检查器

我正在尝试使用 trie 数据结构实现拼写检查器.我目前对 Node 有以下大纲: 类节点:def __init__(self):self.next = {}self.word_marker = Falsedef add_item(self, string):#如果字符串的长度为0则返回.当词尾#comes 将 word_marker 设置为 true如果 len(string) == 0:se ..

发布时间：2021-09-09 19:57:48 python trie Python

URL 的最长前缀匹配

我需要有关可用于 URL 上“最长前缀匹配"的任何标准 python 包的信息.我已经浏览了两个标准包 http://packages.python.org/PyTrie/#pytrie.StringTrie &'http://pypi.python.org/pypi/trie/0.1.1' 但它们似乎对 URL 上的最长前缀匹配任务没有用. 例如，如果我的集合有这些 URL 1->http ..

发布时间：2021-09-09 19:57:42 python url trie longest-prefix Python

尝试和树的区别?

我记得尝试不存储每个节点的全部数据，只存储父节点的后缀. 树存储整个数据的地方，但只根据前缀组织自己. 所以尝试变得更小，例如可以很好地压缩字典. 这真的是唯一的区别吗? 从实际应用中我记得尝试在范围查询中更快.甚至还有特殊的 solr/lucene trie 字段来加速范围查询.但是怎么会这样呢? 尝试和树的实际区别是什么，优缺点是什么? 解决方案 树是递归 ..

发布时间：2021-09-09 19:35:23 tree trie 其他开发

由于多个可变借用，无法将插入到 Rust 中的 C++ 代码移植到 Rust

我有以下 C++ 代码: #include #include 使用命名空间标准；结构特里{布尔值；//词尾字符值；向量chd;//孩子们void push_word(const string& word){特里&特里 = *这个;for (char c: word){if (trie.chd.empty() || trie.chd.back().val != c) {trie.chd.push_ ..

发布时间：2021-07-13 21:14:01 rust trie 其他开发

最小化正则表达式

我对编程世界还很陌生.我正在尝试创建一个通用的正则表达式，它只匹配给定的字符串列表，仅此而已. 例如，给定以下列表 List = ['starguide,'snoreguide','snoraguide','smarguides'] 它应该创建一个这样的正则表达式 - s(((tar|nor(e|a))(guide))|marguides) 我实现了一个尝试.只能设法获得 s(ma ..

发布时间：2021-07-06 20:56:14 python regex string trie Python