标签: trie

我有一个C函数,可以生成大约600万个唯一数组.这些数组每个元素总共有17个元素,每个元素都是0到16之间的整数.我还有一个稍微修改过的函数版本,它也会产生大约600万个相同类型的独特数组.我的问题是,第二个产生的结果比第一个产生的结果少45,000,我想看看这些结果是什么.

所以我的方法是简单地存储第二个函数的所有结果(计算器告诉我这不应该超过400 MB,这可以保留在内存中),然后查找第一个的结果,打印出那些不存在

假设一般方法有意义(如果不是,请告诉),我正在寻找的是一个适当的数据结构(理想情况下在C中有一个很好的实现),它可以容纳大约600万个独特的排列

[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

(或其某些转换)然后对它们执行快速成员资格测试.正如标题所说,我确实怀疑哪些数据结构可以完成这项工作,但我不确定尝试或哈希图是最好的选择.

这是一种检测另一种算法中的缺陷的算法,而不是将在生产中使用的算法.我感兴趣的是这样做的方式将被编码并在人类术语中相对快速地返回结果,不一定要刮掉毫秒,因此存在易于完成大部分工作的grok库绝对是一个优点.

我试图在C中实现节省空间的特里结构。这是我的结构：

struct node {
char val; //character stored in node
int key; //key value if this character is an end of word
struct node* children[256];
};

当我添加节点时，它的索引是字符的无符号字符。例如，如果我要添加“ c”，则

children[(unsigned char)'c']

是指向新添加的节点的指针。但是，此实现要求我声明一个由256个元素组成的node *数组。我想做的是：

struct node** children;

然后在添加节点时，只需为该节点分配空间并具有

children[(unsigned char)'c']

指向新节点。问题是，如果我不首先为孩子分配空间，那么我显然不能引用任何索引，否则那将是一个很大的错误。

所以我的问题是：如何实现特里使它只存储指向其子代的非null指针？

我只是为词汇构建了一个字典树，然后我发现有很多分支共享相同的结构。我想将它们组合在一起成为DAWG。

我将使用什么算法将 trie 转换为 DAWG？

我真的很喜欢使用Chrome的网址栏,因为它会记住常访网站,并且通常建议根据我之前输入和/或访问过的内容进行良好的完成.因此,例如,我可以输入t网址栏,Chrome会自动填写twitter.com,或者我可以输入maps,Chrome会填写.google.com.这使我方便了数据驱动的域名快捷方式,而无需维护显式列表.

不过,我想知道Chrome是如何确定旧的快捷方式应该换成新的快捷方式的.例如,如果我twitter.com经常访问,那么当我输入时,这就完成了t.但是,如果我开始twilio.com经常访问,那么,经过一段时间后,Chrome将开始将其填入默认完成状态t.我无法弄清楚这种转变是如何或何时发生的.似乎还有(至少)涉及两种情况:一种用于域名,另一种用于路径字符串,因为如果我经常访问某个完整的URL,然后想要到达同一域的根,我结束必须输入整个域名才能让Chrome忽略完整的网址完成情况.

如果我不得不猜测,我认为Chrome会将我在URL栏中输入的内容存储在trie中,其值是特定字符串键入(和/或访问？)的次数.然后我想象它对于特里的"计数"有某种指数衰减模型.但这只是猜测.有谁知道这个更新过程是如何发生的？

我很难说服Agda终止检查fmap下面的函数,并且在a的结构上递归地定义了类似的函数Trie.A Trie是一个trie,其域是a Type,是一个由单元,产品和固定点组成的对象级类型(我省略了副产品以保持代码最小).问题似乎与我在定义中使用的类型级替换有关Trie.(表达式const (?? ?) * ?表示将替换const (?? ?)应用于类型?.)

module Temp where

   open import Data.Unit
   open import Category.Functor
   open import Function
   open import Level
   open import Relation.Binary

   -- A context is just a snoc-list.
   data Cxt {} (A : Set ) : Set  where
      ? : Cxt A
      _??_ : Cxt A ? A ? Cxt A

   -- Context membership.
   data _?_ {} {A …

我有一个包含100万英文单词的txt文件,其频率格式如下:

好345667
坏456777
...

我需要使用Java中的HashMap或Trie数据结构来存储它.稍后我需要从列表中查找单词而不需要其他操作.我的理解是,HashMap的查找速度比Trie慢,但是Trie将占用更多的内存,而Trie的实现也需要付出努力,而HashMap已经可以使用了.对于生产代码,您对哪种数据结构最适合这种情况有什么建议或建议吗？提前致谢.

此外,HashMap允许查找"恒定时间".它真的比英语单词的Trie慢吗？

我正在研究Trie的数据结构并遇到了这段代码

// R-way trie node
    private static class Node {
        private Object val;
        private Node[] next = new Node[26];
    }

我理解逻辑,但我没有得到的是,Node将被初始化的深度是多少？

您可以在http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/TrieST.java.html查看完整的代码.

我考虑了两个具有相似概念的集合 -ParHashMap来自 Scala 和来自 Java 的 ConcurrentHashMap。它们都具有相同的时间复杂度，并且都是线程安全和无锁的，但它们仅基于不同的概念——相应的特里和哈希表。这个推理导致了一个问题：为什么我们需要来自 Scala 的 ParHashMap 而有来自 Java 的 ConcurrentHashMap？

现在我知道之前有关于这个算法的问题，但是老实说我还没有遇到一个简单的 java 实现。许多人在他们的 GitHub 个人资料中复制粘贴了相同的代码，这让我很恼火。

因此，出于面试练习的目的，我计划使用不同的方法来制定和实施算法。

该算法往往非常具有挑战性。老实说，我不知道如何去做。只是逻辑说不通。我几乎花了 4 天的时间来描绘这种方法，但无济于事。

因此，请用您的智慧启发我们。

我主要是根据这些信息做算法 Intuition behind the Aho-Corasick string matching algorithm

如果可以在这里实施他们自己的解决方案，那将是一个很大的好处。

但这是我真正陷入困境的以下不完整且无效的解决方案：

如果您对代码感到不知所措，那么主要问题在于 Aho-Corasick 的主要算法。我们已经很好地创建了字典树。

但问题是，既然我们有了 trie 结构，我们如何真正开始实施。

所有资源都没有帮助。

public class DeterminingDNAHealth {
  private Trie tree;
  private String[] dictionary;
  private Node FailedNode;


  private DeterminingDNAHealth() {

  }

  private void buildMatchingMachine(String[] dictionary) {
    this.tree = new Trie();
    this.dictionary = dictionary;

    Arrays.stream(dictionary).forEach(tree::insert);

  }

  private void searchWords(String word, String[] dictionary) {

    buildMatchingMachine(dictionary);

    HashMap < Character, Node > children = tree.parent.getChildren();

    String matchedString = ""; …

我的理解是，自动完成/搜索文本/项目在任何可扩展产品（例如Amazon eCommerce / Google）中都可以在高水平上实现的高水平是：-

基于弹性搜索（ES）的方法

1. 文档存储在DB中。一旦持久化给弹性搜索，它就会创建索引并将索引/文档（基于令牌生成器）存储在基于内存或磁盘的配置中。

2. 用户键入3个字符后，它将搜索ES下的所有索引（可以配置为甚至对ngram进行索引），根据权重对它们进行排名并返回给用户

但是在阅读了谷歌的一些资源后，例如基于特里的搜索

看起来有些可伸缩产品还使用Trie数据结构来进行基于前缀的搜索。

我的问题是，基于特里的方法是否可以很好地替代ES或ES在内部使用，Trie还是我在这里完全错过了？