程序员经验分享-hwhale

如何使用 Trie 进行拼写检查

2024-04-30

我有一个根据单词词典构建的特里树。我想用它来进行拼写检查（并建议字典中最接近的匹配项，也许对于给定数量的编辑x）。我想我会在目标单词和字典中的单词之间使用 levenshtein 距离，但是有没有一种聪明的方法可以遍历 trie，而不需要对每个单词分别运行编辑距离逻辑？我应该如何进行遍历和编辑距离匹配？

例如，如果我有单词 MAN、MANE，我应该能够在 MANE 中重用 MAN 上的编辑距离计算。否则 Trie 就没有任何作用


我认为你应该尝试一下bk-trees http://en.wikipedia.org/wiki/BK-tree;它是一种非常适合拼写检查的数据结构，因为它可以让您有效地计算字典中单词的编辑距离。

This link http://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/深入了解应用于拼写检查的 BK 树

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

languageagnostic

spellchecking

Trie

如何使用 Trie 进行拼写检查 的相关文章

  • 用 C++ 生成 AST

    我正在用 C 制作一个解释器 到目前为止我已经有了词法分析器来生成标记 问题是我不确定如何生成 行走 解析树 我正在考虑使用数组数组来制作解析树 但我不确定如何以正确的顺序将标记实际插入到解析树中 我不确定是自上而下 左右还是自下而上 左右

  • “此应用程序已请求运行时以异常方式终止它”的原因是什么？

    Visual C 运行时抛出一个常见错误 此应用程序已请求运行时以异常方式终止它 请联系应用程序的支持团队以获取更多信息 该错误消息实际上是什么意思mean 让我用一个比喻来准确地解释我的问题 如果我看到一条消息 异常 访问冲突 0xc00

  • 使用并集查找（又名不相交集）检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两

  • shell脚本中关联数组的时间复杂度

    我想知道在 shell 脚本中使用关联数组时如何构造 实现 另外 我想知道基于 shell 脚本的关联数组的时间复杂度是否是最佳的 因为我们可以使用字母和数字作为它们各自的键 编辑 他们使用什么哈希函数 如果您使用关联数组 则不能通过 使用

  • 迭代任意大小的子集

    我可以迭代大小为 1 的子集 for int a 0 a lt size a 或大小为 2 的子集 for int a1 0 a1 lt size a1 for int a2 a1 1 a2 lt size a2 or 3 for int

  • 需要一种将网络块范围折叠为超集范围列表的算法

    我的数学不及格 我需要一种有效的方法将网络范围缩小为超集 例如如果我输入 IP 范围列表 1 1 1 1至2 2 2 5 1 1 1 2至2 2 2 4 10 5 5 5至155 5 5 5 10 5 5 6至10 5 5 7 我想返回以下

  • 具有 2 个属性的背包算法。如何在 3d 数组中实现它？

    当有超过 1 个属性时 我无法理解背包问题 当有 1 个属性时 我必须编写一个使用具有 2 个属性的背包算法的程序 老师告诉我们 它必须在 3d 数组中完成 错误的实现将导致 O 2 n 处理时间 我无法想象这样的数组会是什么样子 假设这是

  • 负整数的基数排序

    我正在尝试对整数 包括负整数 实现基数排序 对于非负整数 我计划为数字0 9创建一个10个队列的队列 并实现LSD算法 但我对负整数有点困惑 我现在的想法是继续为它们创建另一个包含 10 个队列的队列 并分别对它们进行排序 然后在最后 我将

  • 在 O(n) 时间内排序？

    我被这个问题困扰了 2周 知道如何处理它吗 令 L 为 n 个不同整数的列表 假设 L 的 x 的元素在 1 750 范围内 设计线性排序算法对 L 的元素进行排序 我已经尝试过插入排序 但我不确定我的方法是否正确 Construct an

  • 实施二分查找有哪些陷阱？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 二分查找比看起来更难实现 虽然二分搜索的基本思想相对简单 但细节可能出人意料地棘手 Donald Knuth 新的二分搜索实现中最有可

  • Java递归方法求阶乘返回负输出[重复]

    这个问题在这里已经有答案了 我知道这是溢出 但问题是 20 是相对较小的数字 这不应该发生 对吧 有没有更好的方法来查找大数 例如 1000 的阶乘 而不会得到这种奇怪的结果 public class RecursiveFunctionsE

  • 解开 Knuth 的结：如何重构意大利面条式代码？

    这个问题的灵感来自如何将流程图转化为实施 https stackoverflow com questions 36647765它询问如何通过算法消除goto代码中的语句 这answer https stackoverflow com a 3

  • 每个术语出现的次数

    我得到了一个数组a n 2 where n can be 10 5最大时有n个科目和n个学生 全部编号为 1 2 n a i 0 and a i 1 1 lt i lt n 表示在第 i 个科目中 所有来自a i 0 to a i 1 通过

  • 哪些不同的术语表示相同的事物（或不同的术语，但人们认为它们表示相同的意思）？ [关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 Locked 这个问题及其答案是locked help locked posts因为这个问题是题外话 但却具有历史意义 目前不接受新的

  • 选择一组数字以达到最小总数的算法

    给定 一组数字n 1 n 2 n 3 n x 还有一个数字M 我想找到最好的组合 n a n b n c n gt M 该组合应达到达到或超过 M 所需的最小值 没有其他组合可以提供更好的结果 将在 PHP 中执行此操作 因此可以使用 PH

  • 应用对数来导航树

    我曾经知道一种使用对数从树的一片叶子移动到树的下一个 有序 叶子的方法 我认为它涉及获取 当前 叶子的位置值 排名 并将其用作从根向下到新目标叶子的新遍历的种子 一直使用对数函数测试来确定是否沿着右或左节点向下到达叶子 我已经不记得如何运用

  • AStar-名称解释

    我正在寻找 AStar A 算法为何被称为 AStar 的解释 所有类似的 最短路径问题 算法通常都以其开发者的名字命名 那么 AStar 代表什么 有称为 A1 和 A2 的算法 后来证明A2是最优的 实际上也是可能的最好算法 所以他给它

  • “对象之间通过传递消息进行通信”到底是如何实现的？

    在几本有关面向对象编程的介绍性文本中 我遇到过上述陈述 来自维基百科 在 OOP 中 每个对象都能够接收消息 处理数据 以及发送消息与其他对象相关 并且可以被视为具有独特角色或责任的独立 机器 该语句在代码中到底意味着什么 class A

  • 优先连接，Matlab 中的复杂网络

    大家好 我现在正在 MATLAB 中研究优先附件模型 在理解以下内容时遇到一些困难 假设我一开始有 4 个节点 连接如下 time 0 1 lt gt 2 3 lt gt 4 在下一个时间步骤中 我添加一个节点和 4 个连接 然后添加另一个

  • pytesseract 无法从图像中识别复杂的数学公式

    我在用pytesseractpython 中的模块 pytesseract从图像中识别文本 但它不适用于包含复杂数学公式 例如根 推导 积分数学问题或方程 的图像 代码2 py Import modules from PIL import

随机推荐

热门标签