c - 如何在 C/C++ 中使用自动更正、自动完成、拼写检查实现字典

Question

我必须为具有以下功能的字典实现编写 C/C++ 代码：

单词基本上有定义（1个或多个）。

1) 插入

2）搜索（尽可能快）

3) 自动完成

4) 自动更正

5) 拼写检查

所以我需要知道怎么做？

哪种数据结构应该是最有效的？特里或哈斯特表或其他东西

使用哪种搜索技术...？

如何有效地实现自动完成和拼写检查..？

Answer 1

您通常会使用根据彼此之间的编辑距离排列的单词树，例如BK 树。

IIRC，这个想法是有一个平衡的树，每个单词通过根据编辑距离编号的边连接起来。如果你想找到一个词的最近匹配，你计算它到根词的编辑距离，然后跟随根词的相同数字的链接，重复这个过程，直到你到达一个叶子节点，它要么是同一个词，或最接近的匹配。

编辑：事后看来，我链接的那篇文章在解释它方面做得比我做得好得多。我只是建议通读它以获得对该方法的一个很好的解释。

Answer 2

Certainly you need a database with a list of words, then you need to split your text up into words and see if they exist in the database.

For Autocomplete you can just check that the text entered so far matches words in the dictionary (with a LIKE txt+'%' clause), implemented with an AJAX call.