问题标签 [prefix-tree]

我有以下数据结构： 此树仅存储小写字符。

我正在尝试构建一种递归查找树中最长单词的方法。我很难构建这种递归检查每个节点分支的方法。

这是我正在使用的给定类，仅显示相关方法：

我必须实现一个从给定字符串中修剪前缀的函数。前缀列表可能非常大，因此一个接一个地尝试常规 Scala 函数stripPrefix会很昂贵。所以我求助于 Lucene 来创建一个 FSA，它可以更小、更有效地测试前缀。

在这个Stackoverflow 问题之后，我发现我正在寻找的自动机是DaciukMihov Automaton。但是我不知道如何使用自动机来获取与字符串匹配或不匹配的前缀。所以我有两个补充问题：

1. 您如何使用泛型Automaton来获取匹配的开始和结束字符？
2. 你如何强制匹配发生在字符串的开头？

我了解插入的“规则”

我正在考虑改进前缀树。它允许我搜索包含输入字符串的指定数量的单词。

任务：我们需要一个通过子字符串实现公司名称列表的类——从所有可用名称的列表中，输出以输入行开头的一定数量的公司。假设在具有高 RPS（每秒请求数）的网站/移动应用程序上填写表单时将调用该类。

我的解决方案：

树类：

该解决方案运行良好，并且似乎可以非常有效地工作，但我对它的不满程度已经足够了。根据条件，我们必须返回数量等于 numberOfSuggest 数量的单词列表。

我强制树返回所有包含输入的单词。然后我才从结果列表中获取所需数量的单词：

我想尽量节省时间，并教树返回一个现成的受 numberOfSuggest 数量限制的单词列表。

实验：https ://scastie.scala-lang.org/m0MxnlChT0GkpGJIBnNnUQ

我在地图中有数万条记录。映射键是字符串，如s3://mybucket/some/path/2021/03/03/file.txt, s3://mybucket/some/path/2021/03/04/file.txt，值是0or 1。到目前为止我使用 HashMap 但内存使用率太高，我想减少它。

我正在寻找一种键值对并利用关键部分可重用性的东西。自然想到的是使用一些树结构来存储前缀。

有人可以指出一个适当的实现，最好是轻量级的吗？

给定一个成对向量（符号：它的码字长度），为这些符号构造一个二叉霍夫曼树。如果这样的树不存在，则会出错。

例如，给定输入 { a : 1, b : 2, c: 2}，输出树应该是：