问题标签 [trie]

我看到有些人将这种结构用于 Trie 节点：

是低效率，因为我们并不总是需要TREE_WIDTH每个数组的长度。

还是我误解了什么？

基数排序的时间复杂度是 O(kn)，其中 n 是要排序的键的数量，k 是键的长度。类似地，在 trie 中插入、删除和查找操作的时间复杂度为 O(k)。但是，假设所有元素都是不同的，不是 k>=log(n) 吗？如果是这样，这意味着基数排序的渐近时间复杂度为 O(nlogn)，与快速排序相同，而 trie 操作的时间复杂度为 O(logn)，与平衡二叉搜索树的时间复杂度相同。当然，常数因子可能有显着差异，但渐近时间复杂度不会。这是真的吗？如果是这样，基数排序和尝试比其他算法和数据结构有其他优势吗？

编辑：

Quicksort 及其竞争对手执行 O(nlogn)比较；在最坏的情况下，每次比较将花费 O(k) 时间（密钥仅在检查的最后一位数字处不同）。因此，这些算法需要 O(knlogn) 时间。按照同样的逻辑，平衡二叉搜索树操作需要 O(klogn) 时间。

我有一个很大的域名列表（大约六千个），我想看看哪些词的趋势最高，以大致了解我们的投资组合。

我遇到的问题是列表被格式化为域名，例如：

examplecartrading.com

examplepensions.co.uk

示例交易.org

examplesummeroffers.com

+5996

只是运行字数统计会带来垃圾。所以我想最简单的方法是在整个单词之间插入空格然后运行字数统计。

为了我的理智，我更愿意编写这个脚本。

我知道（非常）小python 2.7，但我愿意接受任何建议来解决这个问题，代码示例真的会有所帮助。有人告诉我，使用简单的字符串 trie 数据结构将是实现这一目标的最简单方法，但我不知道如何在 python 中实现它。

编辑：新问题。鉴于我怀疑这个问题比我最初想象的更难——可能是 NP 复杂的，我有一个不同的问题：什么是有用的算法可以接近最大化使用的字母数量？

我受到启发写了一个基于纸牌游戏 Scrabble Slam 的程序！但是，我是算法新手，想不出解决这个问题的有效方法：

您从一个包含英语有效的 4 个字母单词的字符串开始。您可以一次在该单词上放置一个字母，这样通过放置该字母就可以形成一个新的字典有效单词。您拥有的字母等于字母表中的字母。

例如，如果起始词是“cart”，这可能是一个有效的移动序列：

sand --> sane --> sine --> line --> lins --> pin --> fins 等。

目标是通过使用尽可能多的字母（不多次使用一个字母）来最大化序列中的单词数量。

我的算法找不到最长的序列，只是猜测最长的可能是什么。

首先，它获取所有单词的列表，这些单词可以通过改变起始单词的一个字母来组成。该列表称为“相邻列表”。然后它会查看相邻列表中的所有单词，并找出其中哪些单词具有最相邻的单词。无论哪个单词有最相邻的单词，它都会选择将起始单词变成。

例如，单词 sane 可以变成另外 28 个单词，单词 sine 可以变成另外 27 个单词，单词 line 可以变成另外 30 个单词——这些选择中的每一个都是为了最大化可能性并且可以拼出更多的单词。

解决这个问题的最佳方法是什么？什么样的数据结构是最优的？如何改进我的代码以使其更高效、更简洁？

我阅读了一些关于 Tries、散列、Map(stl) 和 BST 的博客和教程。我很困惑哪个更好用以及在哪里使用。我知道在它们之间做出这样的区别是无稽之谈，因为它们都依赖于实现。请您更具体地告诉我，请不要忘记提及复杂性（最坏、平均和最佳情况）。

提前致谢...

我需要一些关于如何正确索引代表货币的字段的指导。
我需要 130 来匹配 130.64。我尝试了下面的 trie float 配置。

当我在该字段中搜索 130 时，我没有得到任何结果。我试过增加和减少精度无济于事。

我如何让它索引部分数字？

我正在尝试将此 trie 实现用于 ocaml：http ://www.lri.fr/~filliatr/ftp/ocaml/ds/trie.ml.html

这是我对模块“M”的实现：

忽略不正确的语义（相等、比较等）。

我正在使用 ocaml 电池，这就是我尝试完成这项工作的方式：

我不明白这个错误。在我看来，我的模块“M”实现中的方法类型是有效的。

我也不明白为什么 ocaml 需要 TRIE 实现不需要的字段（标签、中缀等）。

我在内存中有一个 T9 字典（trie/hash_map）。字典包含单词评级对，因此当从字典中挑选一个单词时，它的评级会增加，并且单词评级对在单词列表中上升。

假设有一种方法可以从字典中挑选一个单词。该方法还执行一些单词评级程序。

在输入中，我有在电话上按下的数字字符串（1-9、'*' 来更改单词和''）。

问题：

1. 有什么算法可以快速解析字符串吗？
2. 哪种数据结构会更好？

升级版：

完整的问题文本（问题 D）

Hash_map 实现

尝试实现

我正在尝试做的事情：

• 构建一个移动 Web 应用程序，用户可以在其中获得帮助，在玩拼字游戏时找到要玩的单词
• 用户通过输入任意数量的字母和 0 个或多个通配符来获得单词建议

我是如何尝试这样做的：

• 将 MySQL 数据库与包含超过 400k 单词的字典一起使用
• 使用 ASP.NET 和 C# 作为服务器端编程语言
• 使用 HTML5、CSS 和 Javascript

我目前的计划：

• 使用数据库中的所有单词构建一个 Trie，以便我可以根据用户字母/通配符输入快速准确地搜索单词

如果您无法执行计划，那就没有好处了，这是我需要帮助的：

• 如何从数据库构建 Trie？（更新：我想使用数据库中已有的单词生成一个 Trie，完成后我将不再使用数据库进行单词匹配）
• 如何存储 Trie 以便快速方便地访问？（更新：所以我可以丢弃我的数据库）
• 如何使用 C# 根据字母和通配符使用 Trie 搜索单词？

最后：
非常感谢任何帮助，我仍然是 C# 和 MySQL 的初学者，所以请温柔

十分感谢！

我第一次使用 trie。我想知道在决定应该遍历的下一个分支时，哪个是用于 trie 的最佳数据结构。我正在寻找一个数组、一个哈希图和一个链表。