当前位置：文江博客话题详情

C++ 中的自动完成库

发布于 2024-11-10 18:59:08 字数 258 浏览 1 评论 0原文

我需要一个 C++ 中的自动完成例程或库，用于 100 万个单词。我想我可以在网上找到像拉宾-卡普这样的例程。你知道有一个图书馆可以做到这一点吗？我在 Boost 中没有看到它。

另外，使用 MySql LIKE SQL 请求来做到这一点是一个疯狂的想法吗？

谢谢

编辑：确实，我需要的建议比自动完成更多（当用户输入前两个字母时建议十个单词）。我其实也有“尼康数码相机”的说法。但对于第一个版本，我只需要关于尼康“Ni”的建议，而不是“数码相机”的建议。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

终止放荡 2024-11-17 18:59:08

如果您从准备索引开始，则不必使用任何疯狂的算法。

一个简单的 Trie/二叉搜索树结构，保持单词按字母顺序排序，将允许有效的前缀搜索。

例如，在 C++ 中，std::map 类具有 lower_bound 成员，它将在 O(log N) 时间内指向可能扩展单词的第一个元素。

回复收藏 0 原文

ゝ偶尔ゞ 2024-11-17 18:59:08

嗯，如果您正在考虑使用 like，则很可能意味着您想要经典的自动完成功能（单词开头匹配）。

将您的数据（很好地）组织到 26 树（每个字母一个条目，或者如果您支持除字母之外的其他内容，则选择精心选择的 x 树）怎么样？这样，您只需组织一次数据，然后就可以通过树解析快速获得结果。如果您想限制自动完成中建议的结果数量，您可以调整树解析算法。看起来简单而高效（SQL 中类似的语法每次都必须比较表中的所有项目，而一旦正确设置数据，我的解决方案就会快得多）

其他解决方案，您可以查看 QCompleter （在代码上依赖 Qt 可能有点过分，我不知道）

回复收藏 0 原文

櫻之舞 2024-11-17 18:59:08

我曾经参与过一个项目，使用 CLucene 做了类似的事情。效果很好。

回复收藏 0 原文

乞讨 2024-11-17 18:59:08

您可以使用 trie（前缀树）来存储单词。

struct trie
{
  std::map<char, trie*> next;
  bool is_word;

  void insert(std::string w)
  {  
    trie * n = this;
    for (int i = 0; i < w.size(); ++i) {
      if (n->next.find(w[i]) == n->next.end()) {
        n->next[w[i]] = new trie();
      }
      n = n->next[w[i]];
    }
    n->is_word = true;
  }
};

然后您可以轻松地在子树上迭代获得前缀匹配。

You can use a trie (prefix tree) to store your words.

struct trie
{
  std::map<char, trie*> next;
  bool is_word;

  void insert(std::string w)
  {  
    trie * n = this;
    for (int i = 0; i < w.size(); ++i) {
      if (n->next.find(w[i]) == n->next.end()) {
        n->next[w[i]] = new trie();
      }
      n = n->next[w[i]];
    }
    n->is_word = true;
  }
};

Then you can easily get prefix matches iterating on subtrees.

回复收藏 0 原文