A Fast and Compact Language Model Implementation Using Double-Array Structures
A Fast and Compact Language Model Implementation Using Double-Array Structures
复制标题
DOI：
10.1145/2873068
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Jun-ya Norimatsu;M. Yasuhara;Toru Tanaka;Mikio Yamamoto
中科院分区：
文献类型：
--
作者：
Jun-ya Norimatsu;M. Yasuhara;Toru Tanaka;Mikio Yamamoto
语言模型是自然语言处理、自动语音识别和光学字符识别等领域中广泛使用的组件。特别是，统计机器翻译使用语言模型，翻译速度和所需内存量受语言模型实现性能的影响很大。我们提出了一个快速和紧凑的实现n-gram语言模型，提高查询速度，减少内存使用，通过使用双数组结构，这是已知的是一个快速和紧凑的trie数据结构。我们提出了两种类型的实现：一种是向后后缀树，另一种是反向尝试。通过将模型参数嵌入到双阵列结构中未使用的空间中，优化了数据结构的空间效率。我们表明，我们的方法的反向trie版本是最小的国家的最先进的实现模型的大小与几乎相同的速度，执行最快的困惑计算任务的实现。同样，我们实现了更快的解码，同时保持紧凑的模型大小，我们证实，我们的方法可以利用双数组结构的效率，以实现翻译任务的速度和大小之间的平衡。
The language model is a widely used component in fields such as natural language processing, automatic speech recognition, and optical character recognition. In particular, statistical machine translation uses language models, and the translation speed and the amount of memory required are greatly affected by the performance of the language model implementation. We propose a fast and compact implementation of n-gram language models that increases query speed and reduces memory usage by using a double-array structure, which is known to be a fast and compact trie data structure. We propose two types of implementation: one for backward suffix trees and the other for reverse tries. The data structure is optimized for space efficiency by embedding model parameters into otherwise unused spaces in the double-array structure. We show that the reverse trie version of our method is among the smallest state-of-the-art implementations in terms of model size with almost the same speed as the implementation that performs fastest on perplexity calculation tasks. Similarly, we achieve faster decoding while keeping compact model sizes, and we confirm that our method can utilize the efficiency of the double-array structure to achieve a balance between speed and size on translation tasks.