使用n元組的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。

雖然它在小數據集上運行良好，但對於大數據集，該映射變得非常龐大〜3,65,000。 什麼可能是一個有效的數據結構，用於n-gram創建和預測的檢索時間。

我們嘗試過使用Trie。檢索速度非常快，但創作速度緩慢。它消耗了大量的RAM。

Answer 1

爲n-gram可能的數據結構可能是

1. 哈希表（已使用）
2. B +樹
3. 三元AVL樹
4. 混合AVL樹

在我意見樹對於快速搜索問題會更好，更多詳情請參閱this。