伙计们,我写了一段代码,给出了输出.现在,这是一个特里.现在我想以审美的方式展示.有人帮助我.我的代表应该是这样的http://en.wikipedia.org/wiki/File:Trie_example.svg
但我想要的是如何将这个巨大的怪物输出转换为整齐的输出,如[(1,2),(1,3),(1,4),(3,4)] ????
defaultdict(<type 'int'>, {'A': 1, 'W': 12})
defaultdict(<type 'int'>, {'A': 2, 'X': 25})
defaultdict(<type 'int'>, {'A': 3})
defaultdict(<type 'int'>, {'A': 4})
defaultdict(<type 'int'>, {'S': 5})
defaultdict(<type 'int'>, {'S': 6})
defaultdict(<type 'int'>, {'S': 7})
defaultdict(<type 'int'>, {'D': 8})
defaultdict(<type 'int'>, {'D': 9})
defaultdict(<type 'int'>, {'D': 10})
defaultdict(<type 'int'>, {'D': 11})
defaultdict(<type 'int'>, {})
defaultdict(<type 'int'>, {'R': 16, 'E': 13, 'F': 19})
defaultdict(<type 'int'>, {'E': 14})
defaultdict(<type 'int'>, {'E': 15})
defaultdict(<type 'int'>, {})
defaultdict(<type 'int'>, {'R': 17})
defaultdict(<type 'int'>, …我正在尝试在OCaml中构建一个trie:
type ('a, 'b) trie = Nil | Cons of 'a * 'b option * ('a, 'b) trie list;;
(* find place to insert key in a list of tries *)
let rec findInsert key x =
match x with
[] -> Nil
| x::xs -> let Cons(k, _, _) = x in
if key = k then x else findInsert key xs;;
(* inser pair in a trie *)
let rec insert ( key, value ) trie …我有一个类似 Set 的数据结构，作为 Trie 实现，其定义如下：
import qualified Data.Map as M
import Data.Foldable (Foldable, foldr)
import Prelude hiding (foldr)
import Data.Maybe (fromMaybe)
data Trie a = Trie { endHere :: Bool
, getTrie :: M.Map a (Trie a)
} deriving (Eq)
插入操作如下所示：
insert :: (Ord a, Foldable f) => f a -> Trie a -> Trie a
insert = foldr f (\(Trie _ m) -> Trie True m) where
f e a = overMap (M.alter (Just . a . fromMaybe (Trie …给定N 个64 位无符号整数，我希望将它们有效地存储在数据结构D中，并能够执行以下查询：
给定一个整数A，返回D中至少k 个最高有效位相同的所有整数。
例如，如果有一个包含 3 个 64 位整数的列表：
a. 1010010000000000010000000000000000000000100000000000000000000001
b. 0000000100001000000000010000000000000000000000000000000000000001
c. 1010010100000000000000010000000000000000000000000000000000000001
查询A是：
1010010000000000000000010000000000000000000000000000000000000001
我们选择 k = 7
它应该返回一个包含 2 个元素的列表：
a.1010010000000000010000000000000000000000100000000000000000000001
c.1010010100000000000000010000000000000000000000000000000000000001
如果查询 A1 是：
0010010000000000000000010000000000000000000000000000000000000001
k = 2
它应该返回一个包含一个元素的列表：
b. 0000000100001000000000010000000000000000000000000000000000000001
如果查询 A2 是：
1110010000000000000000010000000000000000000000000000000000000001
k = 3
它应该返回一个空列表。
N 的大小应为 5000 万个整数的量级。
你能指出最合适的数据结构吗？另外，如果我可以在创建数据结构 D 后对其进行插入/删除，那就太好了。
我尝试使用 Trie 数据结构来解决一些编码问题。对于 trie 中的每个节点，您通常会放置其子节点的引用列表。因此，如果查找中不存在某些子节点，我考虑使用 defaultdict 创建默认的空 trie 节点。但是，我不知道如何使用 defaultdict 来引用包含它的类。
我尝试了两种方法，都失败了。以下是我尝试过的。
from dataclasses import dataclass
from collections import defaultdict
@dataclass
class TrieNode():
is_word = False
children = defaultdict("TrieNode")
上面的代码产生
Traceback (most recent call last):
File "<stdin>", line 2, in <module>
File "<stdin>", line 4, in TrieNode
TypeError: first argument must be callable or None
Traceback (most recent call last):
File "<stdin>", line 2, in <module>
File "<stdin>", line 4, in TrieNode
TypeError: first argument must be callable or None …我正在尝试将这个trie实现用于ocaml:http://www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.html
这是我对模块"M"的实现:
module M =
struct
type key = int
type 'a t = (int * 'a) list
let empty = []
let equal x y = false
let compare f x y = 1
let find x l =
let pred e = fst e == x in
let z = List.find pred l in
snd z
let add x t m = (x,t)::m
let remove x m = filter (fun e -> fst e != x) …这是一个面试问题.给定一些字符串找到这样的字符串,这些字符串是其他字符串的前缀.例如,给定strings = {"a", "aa", "ab", abb"}结果是{"a", "ab"}.
最简单的解决方案是对字符串进行排序,如果第一个字符串是第二个字符串的前缀,则检查每对两个后续字符串.算法的运行时间是排序的运行时间.
我想还有另一个解决方案,它使用a trie,并且具有复杂性O(N),其中N是字符串的数量.你能建议这样的算法吗？
对于Data Structures项目,我必须找到两个单词之间的最短路径,如"cat"和"dog,但我只允许一次更改一个字母.我正在尝试通过实现trie来实现它,并且可以似乎能够实现最短路径搜索.
猫 - >小孩 - > cog - >狗
所有单词的长度都相同,我从字典文件中填充它们.我们必须一个接一个地移动.所以中间的词必须是一个有效的词.
我认为使用trie不太可能,但任何人都有任何知识吗？
我必须将输入字符串与一组前缀匹配。匹配应该是最大可能的匹配，因此如果同时存在abcd*和abcde*，则abcdef应该匹配abcde*。我正在为此使用特里。问题在于输入中的字符，并且前缀集中的字符可以是任何Unicode字符。因此，我们不可能在一个简单的Trie中拥有子数组（因为数组的大小将非常大，因此效率至少不够高）。使用map而不是array仍然效率低下。我应该如何解决呢？
我TrieMap在scala中读到了基于数组映射的trie,同时Vector读取位映射向量trie.
这两种结构都是由哈希特里的相同想法支持还是它们之间存在差异？