首页 文章
  • 1 votes
     answers
     views

    实施问题

    我正在为VB.NET中的预测文本输入实现一个trie - 就trie的使用而言基本上是自动完成 . 我已经使我的trie成为基于泛型字典类的递归数据结构 . 它基本上是: class WordTree Inherits Dictionary(of Char, WordTree) 单词中的每个字母(所有大写字母)都用作新WordTrie的键 . 叶子上的空字符表示单词的终止 . 为了找到一个以前...
  • 9 votes
     answers
     views

    实现Patricia Trie用作字典

    我正在尝试使用方法 addWord() , isWord() 和 isPrefix() 来实现Patricia Trie,作为存储大型单词词典以便快速检索(包括前缀搜索)的方法 . 我澄清了一个实现 . 我想知道(在Java或Python代码中)如何实现Trie,特别是节点(或者我应该递归地实现它) . 我看到一个人使用26个子节点的数组设置为null / None来实现它 . 是否有更好的策略(...
  • 19 votes
     answers
     views

    更快地构建trie

    我正在制作一个需要数千个快速字符串查找和前缀检查的移动应用程序 . 为了加快速度,我从单词列表中创建了一个Trie,它有大约180,000个单词 . 一切都很棒,但唯一的问题是构建这个巨大的trie(它有大约400,000个节点)需要 10 seconds 目前在我的手机上,这真的很慢 . 这是构建trie的代码 . public SimpleTrie makeTrie(String file) ...
  • 1 votes
     answers
     views

    排序Trie数据结构

    我需要跟踪文本中单词的出现,并且这种情况需要按降序排列 . 我最初使用哈希映射数据结构,但是当我进一步研究时,我发现了“Trie”数据结构 . 我认为“Trie”数据结构非常适合跟踪灵活性和复杂性方面的发生 . 但是还有一个要求,我需要按降序对事件进行排序 . 所以基本上首先遍历“Trie”的搜索 . 实施明智这有点棘手,所以我想知道我是否走在正确的轨道上 . 任何形式的意见都会很棒 . 在这种情...
  • 1 votes
     answers
     views

    如何在trie中存储和搜索字典[复制]

    这个问题在这里已有答案: Trie data structures - Java [closed] 3个答案 我需要为我的Boggle游戏创建一个Java的trie . 我已经尝试过在手边搜索这个站点的帮助,但只得到了C或Python的答案,但没有关于Java的答案 . 无论如何要保持简短,我想知道如何将字典(如文字文本的文字;大约100k字)存入一个字典 . 我已经阅读了关于trie的内容,...
  • 5 votes
     answers
     views

    “简单”Trie实施

    我需要为大学项目实现一个Trie(用Java) . Trie应该能够添加和删除字符串(适用于阶段1) . 我每天花费几个小时(最近几天)试图弄清楚如何做到这一点,并且每次都惨不忍睹 . 我需要一些帮助,互联网上的例子和我的教科书(Java中的数据结构和算法,Adam Drozdek)没有帮助 . 信息 我正在使用的节点类: class Node { public boolean is...
  • 0 votes
     answers
     views

    Java中的自定义Trie实现

    我正在尝试创建一个存储字符串的系统,并为每个字符串条目提供包含给定字符串作为子字符串的字符串数 . 所以,如果我有以下字符串 I am trying to create a custom implementation of a trie. 现在如果我传递一个查询 tr, ,它应该返回 trying 和 trie . 我知道这需要一个Trie,这就是我迄今为止编写的代码 . public cla...
  • 0 votes
     answers
     views

    搜索手机通讯录

    鉴于手机只有一个数字键盘,我们需要以一种快速搜索的方式存储联系人 . 用户将打入数字,我们必须在地址簿中显示所有以这些数字对应的字母开头的联系人 . 我在接受采访时被问到这个问题,我建议创建一个特里 . 对于地址簿中的每个名称,我建议将相应的号码添加到trie中 . 因此,如果地址簿有以下联系人: bob boby mat mav 我会使用相应的数字创建尝试 . 在这种情况下,trie将包含:...
  • 0 votes
     answers
     views

    基于阵列的Trie实现 . 子数组中的非null值

    我试图从http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/了解Trie的基于数组的实现(参见Java解决方案2 - 使用数组提高性能) . public void insert(String word) { TrieNode p = root; for(int i = 0; i...
  • 4 votes
     answers
     views

    Trie实现 - 将元素插入到trie中

    我正在开发一个 Trie 数据结构,其中每个节点代表一个单词 . 所以单词 st , stack , stackoverflow 和 overflow 将被安排为 root --st ---stack -----stackoverflow --overflow 我的Trie在内部使用 HashTable ,因此所有节点查找都将花费恒定时间 . 以下是我将算法插入到trie中的算法 . 检查t...
  • 2 votes
     answers
     views

    J2ME实现Trie(三元搜索树)

    我目前正在研究预测文本短信系统 . 我想使用TST数据结构和二元语法(基于当前键序列12键盘预测下一个可能的单词)来实现它 .目前我有一个语料库,并使用可用的应用程序来提出字典,二元组和频率 . 目前有以下问题: 在这种情况下,我可以找到J2ME TST实现或合适的Trie吗? (关于可用的TST特里的更详细解释可能很棒) 关于该项目方法的一般指导 注意:我已经看过类似的Trie实现,...
  • 0 votes
     answers
     views

    trie数据结构中的所有单词

    我试图将所有单词放在一个字符串中,一个单词由 eow 字段表示为trie数据结构中的某个字符是真的,因此trie可以有字母而不是单词, ex "abc"在trie中,但"c"的eow字段是假的所以"abc"不是一个字 这是我的数据结构 struct Trie { bool eow; //when a Trie field isWor...
  • 0 votes
     answers
     views

    (非压缩)Trie的使用

    我正在研究各种“前缀查找”数据结构,例如Tries和Radix Tries(Patricia Tries) . 在这一点上,我对try和radix尝试有了充分的理解,并且对它们的用例有了很好的理解 . 然而,有一个问题突然出现在我身上:使用普通的trie而不是压缩的trie(例如radix trie)是否有任何优势? 常规trie易于实现:每个节点存储一个字符 . Patricia Trie实现...
  • 7 votes
     answers
     views

    内存Trie Implementation的高效数据结构

    我在python中实现了一个Trie . 直到现在我遇到了两种不同的方法来实现它: 使用数据成员的类Node(类似于C中的struct Node) - char - 存储字符is_end - 存储单词结尾(true或false)prefix_count - 存储具有当前前缀child的单词数 - 节点类型dict(存储其他节点,即26个字母) class Node(object): ...
  • 0 votes
     answers
     views

    在Java中实现Trie

    我用Java实现了Trie数据结构,但是在运行代码时没有得到正确的答案 . 我用一些简单的字符串构建了trie . 我正在搜索单词和前缀,但结果不合适 . 我已经尝试了很多调试但仍然找不到它可能出错的地方 . Trie.java: public class Trie { public class Vertex { public int words; pub...
  • 2 votes
     answers
     views

    TRIE数据结构中搜索操作的时间复杂度

    我正在尝试实现基于字典的trie数据结构 . 请在下面找到python代码 . class Trie: def __init__(self): self.word_end = '_end_' self.root = {} def add_word(self, word): self.add_words([word]) def add_words(sel...
  • 0 votes
     answers
     views

    实现addWord的Trie数据结构

    我坚持一个项目,我必须创建一个“字校正器”,我必须使用“Trie数据结构”,事情是我必须从文件中获取单词(我知道如何做)但是我已经实现了这个界面 public interface Trie { public void add(); public boolean query(String word); public boolean isEmpty(); } 然后我有一个类 TreeTrie ,它...
  • 0 votes
     answers
     views

    在Java中实现数据结构和有效搜索

    我有一个关于数据结构和高效搜索的任务 . 第一个输入参数是一些包含字符串的大文本文件,每行都是一个新字符串 . 第二个输入参数是一些前缀 . 输出是在以给定前缀开头的大文件中找到的最短单词 . 所以,我使用了HashMap并使用每个字母作为键构建了一个Trie . 所以,我只是查看而不是迭代,这节省了时间和内存 . 唯一看起来对我不好的是搜索最短的单词 . 我的意思是现在我得到以给定前缀开头的单词...
  • 4 votes
     answers
     views

    在查找数据结构的顺序时感到困惑

    今天我参加了一家公司的书面测试 . 整体测试侧重于数据结构 . 我遇到了一个我认为已经解决的问题 . 但我在计算数据结构的Big O函数时遇到了困难 . 我将提出我想出的问题和答案 . 给定您需要存储的文档和文档中的单词,并且应该能够在输入任何单词时返回计数 . 您将获得char * GetNextWord() . 您将选择什么数据结构给出算法算法的顺序是什么 对于问题1,我写了我会去TRIE...
  • 1 votes
     answers
     views

    算法按字母顺序打印

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

    长尾分布中出现计数的数据结构

    我有一个很大的元素列表(数千万) . 我试图计算这些元素的几个子集的出现次数 . 事件分布是长尾的 . 数据结构目前看起来像这样(在OCaml-ish风格): type element_key type element_aggr_key type raw_data = element_key list type element_stat = { occurrence : (eleme...
  • 0 votes
     answers
     views

    对于以下用例,可以更快地实现trie?

    我试图解决problem,基本上我们需要从字典中找到所有具有字典顺序的给定前缀的单词 . 我正在使用Trie数据结构来完成任务,但我的解决方案只是超时判断,什么可以是更有效/更快的方法来解决这个问题? 我目前的实施是 class trie{ node root=new node(); class node{ node child[]=new node[26]; ...
  • 0 votes
     answers
     views

    从Haskell中的“Trie”数据类型中检索所有字符串

    我试图在Haskell中创建一个函数,它将Trie数据类型作为参数,并返回Trie中所有字符串的列表 . Trie定义如下(并且定义不能更改):所有单词以句点开头并以$结尾 . 字符必须按字母顺序排列 . 数据类型如下 data Trie = MakeTrie Char [Trie] deriving Eq 其中每个Trie由一个起始字符和其他Tries的子列表(如子树)组成 . 我假设我...
  • 14 votes
     answers
     views

    Trie实施

    我试图在Java中实现一个非常简单的Trie,支持3个操作 . 我希望它有一个insert方法,一个has方法(即trie中的某个单词),以及一个以字符串形式返回trie的toString方法 . 我相信我的插入工作正常,但是并且toString被证明是困难的 . 这是我到目前为止所拥有的 . 特里班 . public class CaseInsensitiveTrie implements Si...
  • 5 votes
     answers
     views

    如何在特里找到最长的单词?

    我无法理解特里的概念 . 来自"trie"维基百科条目我有这张照片: 如果我正确地看到这一点,则特里结构中的所有叶节点将拼写出整个单词,并且所有父节点都保持通向最终叶节点的字符 . 所以,如果我有一个名为DigitalTreeNode的类定义 public class DigitalTreeNode { public boolean isAWord; ...
  • 0 votes
     answers
     views

    为一组字符串构建一个trie

    #include <iostream> #include <vector> #include <string> #include <map> #include <stdlib.h> using namespace std; struct trienode { map<char, struct trienode*> m...
  • 0 votes
     answers
     views

    Trie实现 - getWords和getWordsWithPrefix

    我正在尝试用Java学习和实现Trie数据结构 . 这不是我正在尝试学习和实现trie的家庭作品,使用Arrays,而不是Map . 我正在寻找一种方法来获取trie中的所有单词,并在我的TrieNode实现中按照前缀获取所有单词 下面是我的Java代码 import java.util.Arrays; public class Solution { private TrieNode roo...
  • 1 votes
     answers
     views

    如何正确检查trie中是否存在单词的前缀?

    目前我的Trie类的“searchPrefix”功能定义如下: public Boolean searchPrefix(String word) { TrieNode temp = this.root; for(int i = 0; i < word.length(); i++){ if(temp.children.get(word.charAt(i)) ==...
  • 0 votes
     answers
     views

    使用C类Trie数据结构

    我正在尝试使用类在C中实现trie数据结构 . 在TrieNode类中,我有一个 TrieNode *children[26]; 数组和一个 isEndOfWord 布尔值来确定它是否是结束字 . 在同一个类中,我有其他适合函数的函数,如getter和setter,另外还有insert和search . 每当我尝试添加一个新单词时,通过将true设置为 isEndOfWord ,它也会在每个单词的...
  • 3 votes
     answers
     views

    英语词典的熵

    我有一个trie数据结构,存储一系列英语单词 . 例如,给定这些词,字典是这样的: aa abc aids aimed ami amo b browne brownfield brownie browser brut butcher casa cash cicca ciccio cicelies cicero cigar ciste conv cony crumply diarca diarchi...

热门问题