Handling Massive N-Gram Datasets Efficiently
Handling Massive N-Gram Datasets Efficiently
复制标题
DOI：
10.1145/3302913
复制
发表时间：
2019-03-01
影响因子：
5.6
通讯作者：
Venturini, Rossano
中科院分区：
文献类型：
--
作者：
Pibiri, Giulio Ermanno;Venturini, Rossano
处理大型 n-gram 语言模型涉及两个基本问题：索引，即在不影响检索速度的情况下压缩 n-gram 和相关卫星值，以及估计，即计算从大型文本源中提取的 n-gram 的概率分布。有效执行这两个任务对于信息检索、自然语言处理和机器学习领域的多种应用至关重要，例如搜索引擎和机器翻译中的自动完成。关于索引问题，我们描述压缩、精确和无损的数据结构，相对于最先进的解决方案和相关软件包，同时实现大量空间缩减和无时间退化。特别地，我们提出了一种压缩的 trie 数据结构，其中固定长度 k 的上下文之后的 n-gram 的每个单词（即其前面的 k 个单词）被编码为一个整数，其值与该上下文之后的单词数量成正比。由于自然语言中给定上下文后面的单词数量通常非常小，因此我们将表示空间降低到以前从未达到过的压缩级别，从而允许对数十亿个字符串进行索引。尽管显着节省了空间，但我们的技术在查询时间上带来的损失可以忽略不计。具体来说，文献中最节省空间的竞争对手，它们都是量化的和有损的，占用的空间并不比我们的 trie 数据结构少，而且速度慢了 5 倍。相反，我们的 trie 与最快的竞争对手一样快，但在绝对空间上保留了高达 65% 的优势。关于估计问题，我们提出了一种新的算法来估计修改的 Kneser-Ney 语言模型，由于其相对较低的复杂度性能，该模型已成为学术界和工业界语言建模的事实上的选择。从大型文本源估计此类模型对设计能够节约磁盘使用的算法提出了挑战。最先进的算法在外部存储器中使用三个排序步骤：我们展示了一种改进的结构，通过利用提取的 n 元字符串的属性，该结构仅需要一个排序步骤。通过对数十亿个 n 元语法进行广泛的实验分析，我们发现之前方法的总运行时间平均提高了 4.5 倍。
Two fundamental problems concern the handling of large n-gram language models: Indexing, that is, compressing the n-grams and associated satellite values without compromising their retrieval speed, and estimation, that is, computing the probability distribution of the n-grams extracted from a large textual source.Performing these two tasks efficiently is vital for several applications in the fields of Information Retrieval, Natural Language Processing, and Machine Learning, such as auto-completion in search engines and machine translation.Regarding the problem of indexing, we describe compressed, exact, and lossless data structures that simultaneously achieve high space reductions and no time degradation with respect to the state-of-the-art solutions and related software packages. In particular, we present a compressed trie data structure in which each word of an n-gram following a context of fixed length k, that is, its preceding k words, is encoded as an integer whose value is proportional to the number of words that follow such context. Since the number of words following a given context is typically very small in natural languages, we lower the space of representation to compression levels that were never achieved before, allowing the indexing of billions of strings. Despite the significant savings in space, our technique introduces a negligible penalty at query time.Specifically, the most space-efficient competitors in the literature, which are both quantized and lossy, do not take less than our trie data structure and are up to 5 times slower. Conversely, our trie is as fast as the fastest competitor but also retains an advantage of up to 65% in absolute space.Regarding the problem of estimation, we present a novel algorithm for estimating modified Kneser-Ney language models that have emerged as the de-facto choice for language modeling in both academia and industry thanks to their relatively low perplexity performance. Estimating such models from large textual sources poses the challenge of devising algorithms that make a parsimonious use of the disk.The state-of-the-art algorithm uses three sorting steps in external memory: we show an improved construction that requires only one sorting step by exploiting the properties of the extracted n-gram strings. With an extensive experimental analysis performed on billions of n-grams, we show an average improvement of 4.5 times on the total runtime of the previous approach.