java - 使用 n-grams 在 Java 中预测下一个单词的理想数据结构

Question

我正在尝试为 Android 上的自定义键盘实现下一个单词预测器。

目前的方法涉及计算 N-gram 并将其存储为 HashMap。句子是键，频率是值。

// NGram dictionary
Map<String, Integer> nGramMap = new HashMap();

一旦出现一系列单词，例如W1 W2 W3 W4，我正在搜索以 W1 W2 W3 W4 和 W2 W3 W4 等开头的 N-gram。

虽然它在小型数据集上运行良好，但对于大型数据集，这张 map 变得非常庞大，约为 3,65,000。对于预测的 n-gram 创建和检索时间来说，什么是有效的数据结构。

我们尝试使用 Trie。检索速度非常快，但创建速度很慢。而且它消耗了大量的内存。

Answer 1

n-gram 可能的数据结构可能是

1. 哈希表(你用过)
2. B+树
3. 三元AVL树
4. 混合 AVL 树

在我看来，树对于快速搜索问题会更好，有关更多详细信息，请参阅 this .