4

想知道将二叉搜索树变成拼写检查器的最有效方法，方法是读入 1000 个单词的字典文件，然后让它检查另一个文档，说有几个段落。

4

8 回答 8

8

三叉树树会更有效

于 2008-12-05T02:22:19.593 回答
3

您是否对使用二叉搜索树一无所知？布隆过滤器可能是一种更有效的数据结构。

于 2008-12-05T03:34:11.087 回答
1

该站点应该可以帮助您在 java 中实现。

于 2011-06-12T03:07:19.873 回答
1

如果您只是想查看字典中是否存在特定单词（即拼写正确），那么我认为二叉搜索树不是您所追求的。存储该信息的更好方法是采用树形样式，其中树上的每个连续节点都是一个字符，读取到末端节点的路径可以为您提供该单词的拼写。您还需要添加一个标记来指示词尾。

例如：假设你的字典中有这些词：car、cart、cat、cup、cut

- C
  - A
    - R
      - end
      - T
    - T
      - end
  - U
    - P
      - end
    - T
      - end

检查一个单词是否存在是一个单独查看每个字母的问题，以及它是否存在于当前节点的子节点中。

Check for "cat"
Does "C" exist at the root level? Yes, move to the next letter.
Does "A" exist underneath C? Yes, move on.
Does "T" exist underneath A? Yes, move on.
Is there a word ending after the T? Yes. Word exists.

Check for "cu"
Does "C" exist at the root level? Yes, move to the next letter.
Does "U" exist at the root level? Yes, move to the next letter.
Is there a word ending after the U? No. Word does not exist.

如何存储这些信息取决于您。正如 Steven 所指出的，三元搜索树可能是要走的路：每个节点将有 27 个可能的子节点。

于 2008-12-05T03:16:24.663 回答
0

如果您还需要进行自动建议/前缀搜索，那么帕特里夏树或基数树值得一看。

于 2008-12-05T02:26:26.917 回答
0

对于您给出的示例，性能可能无关紧要，因为在 PC 上，如果您不使用完全愚蠢的算法，整个操作将花费用户读取您显示的第一个结果所需时间的大约 1% . 但是，我仍然认为问题足够大，以至于性能是一个问题。

如果字典文件是预先排序的（大多数都是），并且如果文本相对于您所描述的字典很小，那么我会非常想对文本进行排序，也许会删除重复项，然后并排遍历两个列表-side 使用与合并排序相同的过程，除了您报告每个文本单词是否在字典中而不是输出合并列表。

这在大约 M log M 次比较中完成了这项工作，加上最多 N + M 次迭代比较，（可能更少，但不是更复杂）。这非常接近一次性操作的最佳复杂性：要摆脱 N 中的线性项，您需要找到根本不从磁盘读取整个字典的方法。我很确定可以搜索文件，特别是考虑到单词很短，但是对于小 N 来说，任何人都猜测寻找该位置是否实际上会比串行访问数据更快。

它具有以下特点：

  • 您不必将字典保存在内存中，只需保存文本即可。
  • 不过，您只需要遍历字典文件一次。
  • 您不需要对字典进行任何昂贵的处理。

当然，如果字典文件没有预先排序，那么这是行不通的，并且如果您可以将字典保留在内存中以进行下一次拼写检查操作，那么您可以摊销 I/O 的成本并将其处理成跨越多个不同文本的树，从长远来看，这将是一个胜利。

如果字典真的很大，那么您可能会受益于以预处理形式将其存储在磁盘上，该预处理形式相当于根据您的语言中各种单词的相对频率加权的不平衡树。然后，您可以对小文本进行少于 O(N) 的磁盘访问，并且在大多数操作系统上根本不需要将其加载到内存中，只需 mmap 文件并让操作系统担心它。对于一个大字典，包含以“二甲基”开头的单词的整个簇永远不需要被触及。

另一个考虑因素是字典的展开树。当您在其中查找内容时，展开树会使其自身失衡，以便更快地找到常用值。大多数文本重复使用少量单词，因此如果文本足够长以证明开销是合理的，那么最终将获胜。

以上两者都取决于 Steven A Lowe 的观点，即对于字符串，特里树胜过普通树。不过，不知道您是否会找到现成的 splay trie。

于 2008-12-05T02:55:11.040 回答
0

看到这是一个家庭作业问题，我将假设您必须使用普通的旧二叉树（没有红黑树、AVL 树、基数树等）。答案是在从单词列表构建树时尝试保持树的平衡。一种方法是在读入之前随机化列表，这会产生合理的结果。但是，如果您对输入序列进行排序（使用与树使用相同的比较），然后递归细分返回中点的输入，直到没有元素剩余，您可以获得更好的结果。结果是一棵平衡的树。

我在 C# 中找到了三种不同的方法：

private static IEnumerable<T> BinaryTreeOrder<T>(IList<T> range, int first, int last)
{
  if (first > last)
  {
    yield break;
  }

  int mid = (first + last) / 2;
  yield return range[mid];
  foreach (var item in BinaryTreeOrder(range, first, mid - 1))
  {
    yield return item;
  }
  foreach (var item in BinaryTreeOrder(range, mid + 1, last))
  {
    yield return item;
  }    
}

private static void BinaryTreeOrder<T>(IList<T> range, int first, int last, 
                                       ref IList<T> outList)
{
  if (first > last)
  {
    return;
  }

  int mid = (first + last) / 2;
  outList.Add(range[mid]);
  BinaryTreeOrder(range, first, mid - 1, ref outList);
  BinaryTreeOrder(range, mid + 1, last, ref outList);
}

private static void BinaryTreeOrder<T>(IList<T> range, int first, int last, 
                                       ref BinaryTree<T> tree) where T : IComparable<T>
{
  if (first > last)
  {
    return;
  }

  int mid = (first + last) / 2;
  tree.Add(range[mid]);
  BinaryTreeOrder(range, first, mid - 1, ref tree);
  BinaryTreeOrder(range, mid + 1, last, ref tree);
}
于 2011-04-20T20:27:55.200 回答
0

正如建议的那样，trie 比二叉树更有效，但您可以使用 hashmap 并对每个单词进行哈希处理。你有一个小字典（1000 个条目）。遍历文档时，检查单词是否在哈希图中。如果不是，则假定该词拼写错误。

这不会让您更正拼写错误的单词。它只是告诉你是或否（正确与否）。

如果您需要不正确单词的拼写建议，您可以从文件中的单词开始，然后生成 1 个编辑距离以外的所有单词并将它们添加为初始单词的子项。这样您就可以构建图表。深入 2 个级别以获得最大速度与准确性。如果您生成字典中的单词节点，您可以将其添加到可能的建议列表中。最后，返回可能的建议列表。

为了更好地进行拼写检查，还可以尝试添加语音匹配。

sea yuh -> 再见

这种方法（创建字符串图 1 编辑）是“慢”的。但这是一个很好的学术练习。运行时间为 O(n^branches)。

如果对这里感兴趣的是我自己构建的一个链接（为了好玩）：https ://github.com/eamocanu/spellcheck.graph

一些示例图：https ://github.com/eamocanu/spellcheck.graph/tree/master/graph%20photos

我还添加了一个 UI 组件来生成图表。这是一个外部库。

于 2011-12-15T21:26:08.783 回答