2.1 A variety of approaches

A variety of techniques for storing and deploying very large n-gram models have been recently described in the language modeling literature. Approaches vary with the underlying requirements for speed and memory use, hardware availability, and field of application. Brants et al. (Reference Brants, Popat, Xu, Och and Dean2007) and Emami, Papineni and Sorensen (Reference Emami, Papineni and Sorensen2007) describe methods for processing very large language models on distributed server clusters. We restrict our attention to architectures that can be deployed on a single machine, since this is still the more practical and simpler approach in many cases. For deployment on a single machine, n-gram database architectures fall into three main classes: (a) file-based indexing, (b) relational databases, and (c) specialized systems (LM toolkits).

Following the release of the Google Web1T dataset (Brants and Franz Reference Brants and Franz2006), some deployment solutions for this huge collection (88GB, or 25-GB gzip compressed) utilize the original flat files with additional inverted indexing for binary search (Yuret Reference Yuret2008; Giuliano Reference Giuliano2007). Islam and Inkpen (Reference Islam and Inkpen2009a) describe a file-based inverted index approach for managing all 5-grams of the Web1T collection. A sophisticated method to speed up file-based index lookup via hashing is described by Hawker, Gardiner and Bennetts (Reference Hawker, Gardiner and Bennetts2007). Ceylan and Mihalcea (Reference Ceylan and Mihalcea2011) have presented a very efficient indexer for large n-gram corpora. This system uses a B+ tree for compactly holding an index to the set of flat files and shows best retrieval speed among the file-based approaches. As a search/retrieval method, file-based indexing over original tabulated n-gram data tends to be relatively slow (compared with LM toolkits). Depending on implementation, such approaches are also restricted in the kind of queries that can be easily processed – typically supporting only literal queries. Systems by Hawker et al. (Reference Hawker, Gardiner and Bennetts2007) and Ceylan and Mihalcea (Reference Ceylan and Mihalcea2011) do allow wildcard capabilities at the expense of slower performance or a huge additional index. With file-based indexing, limitations of portability may arise when deploying such systems on a different platform. Finally, this approach is not well suited for data updating, for example, incrementally generating very large n-gram collections from text documents (‘streaming’ data). The indexes need to be regenerated when data are modified, and, since data are constantly updated, in practice, indexing is done only when data are finalized.

Storing a language model in a relational database is a viable solution for large datasets. Carlson and Fette (Reference Carlson and Fette2007) report on using the Web1T stored in a MySQL database on a dedicated server. Advantages of this approach include rich SQL-based querying capabilities, support for wildcard queries (with additional indexing); and inherent support for updating with more data. Disadvantages of this approach are a need for a powerful platform (possibly requiring a dedicated server), restricted portability between different platforms, and potential license, and maintenance costs for some Relational Database Management System (RDBMS). Evert (Reference Evert2010) describes a very promising architecture – storing and indexing the Web1T collection with a set of Perl scripts and an embedded SQLite database suitable for deployment on servers and some desktops. Populating a modern RDBMS with more than a billion of n-grams and generating applicable indexes may take quite a long time – Evert (Reference Evert2010) reports two weeks indexing on a 16-GB RAM server. Query performance speed with RDBMS can be adequate for exploratory linguistic research, but may fall short of the needs of intensive NLP applications. For example, Guthrie and Hepple (Reference Guthrie and Hepple2010b) report that MySQL 5.0 on a 64-GB RAM server achieves the rate of processing 527 queries/second (on a dataset of about 56 million bigrams and unigrams), while modern LM toolkits process many thousands of queries per second.

Originating from earlier use of n-gram models for speech recognition, custom-engineered encoding approaches (LM toolkits) focus on speed of query processing and minimizing the size of language models in memory (Stolcke Reference Stolcke2002). To facilitate fast processing, n-gram models ‘should ideally reside locally in memory to avoid time-consuming remote or disk-based look-ups’ (Talbot and Osborne Reference Talbot and Osborne2007a). Such requirement poses a challenge for language models that serve very large n-gram collections. Accomplishing this is the current trend of LM architectures. Yet, loading a very large model into memory is sometimes unsuitable, even on platforms that do have enough memory – for example, if there is a need to run other applications concurrently on the same platform.

Two principles have guided the development of modern optimized LM architectures: (1) providing efficient data structures for encoding/retrieval, (2) use of compression methods to minimize the storage and memory requirements. Given that language models are basically mappings from strings (keys) to ‘payload’ data, optimizing a large language model involves two orthogonal directions: (a) compress the set of n-grams stored in the model, and (b) compress the payload – the frequency counts (or probability values) and the back-off weights stored for each n-gram entry. Compression and optimization are typically tightly related to the core data structure for a given architecture, but there are some common principles.

One widely used approach for compressing the payload is quantization – a lossy compression method that maps values from a continuous range onto a discrete set. During encoding of an n-gram model, the actual count and back-off values associated with each n-gram are replaced with quantized values from a limited set, thus reducing the storage requirements. A simple and common approach is 8-bit quantization, which allows for 256 distinct values. Different methods of dividing the continuous range of values into quantized sets were explored (Whittaker and Raj Reference Whittaker and Raj2001; Federico and Bertoldi 2006). Notably, quantization is a light obstacle for updateability – when data are added or updated, a quantization scheme may be compromised and the whole dataset may need to be re-quantized. Still, quantization remains one of the most widely used methods for reducing the storage requirements (Harb et al. Reference Harb, Chelba, Dean and Ghemawat2009).

A different perspective is to ask what payload data is actually useful. Recently, Brants et al. (Reference Brants, Popat, Xu, Och and Dean2007) have shown that smoothing (and therefore storage of back-off values) is not useful for n-gram collections based on more than a billion-word tokens. Thus, some recent LM toolkits support both variants (Pauls and Klein Reference Pauls and Klein2011).

Issues of storage and speed optimization play major role in describing the two most prominent modern architectures for very large language models – prefix trees and randomized hashing.

2.2 Prefix trees and n-gram models

A prefix tree (digital trie; Fredkin Reference Fredkin1960) is a common data structure for compact storage and efficient search of symbol sequences that have common prefixes. Each symbol in sequence is represented by a node in a tree structure. Nodes are connected via directed arcs and the sequence of arcs from common root uniquely defines each sequence (see Figures 1 and 2). When associated data are stored on trie nodes, trie serves as an indexing structure, with token sequences as search keys.

Fig. 1.

Generic data structure for a trie, with word-level granularity and words on level i+1 grouped into blocks by shared prefix on level i.

Fig. 2.

(a) Schematic character-level trie for a set of words (with fictional counts). (b) Same trie as a linked-list data structure (with: syntagmatic → and ‘alternative’ ↓ links). End-of-word nodes are shaded for illustration.

For language modeling, a classic design represents a model as a prefix tree with word-level nodes (Whittaker and Raj Reference Whittaker and Raj2001; Raj and Whittaker Reference Raj and Whittaker2003). The tree structure originates from a (virtual) root node, which branches out into unigram nodes, each of which branches out to bigram nodes at the second level and so on. Each word-node in the tree represents an n-gram that ends with that word, with a context represented by the sequence of words from the root of the tree. Each node has a fixed record structure that stores the word ID, associated value(s), and references to ‘next order’ word-nodes (successors). To improve memory locality during traversals and to reduce memory footprint, for any given node on depth i, child nodes at depth i+1 are typically grouped together into a block and stored in an array sorted by word ID.

For vocabularies with less than 65,536 words, 16-bit values are sufficient for numeric word IDs; larger vocabularies require 32-bit integer values. Various methods have been proposed for compact representation and compression of word IDs and associated data (Harb et al. Reference Harb, Chelba, Dean and Ghemawat2009). Raj and Whittaker (Reference Raj and Whittaker2003) describe a compression method where word IDs are stored in sorted arrays, and data values (probabilities) are compressed via quantization. For very large n-gram models, Federico and Cettolo (Reference Federico and Cettolo2007) use variable length records for each node. Germann, Joanis and Larkin (Reference Germann, Joanis and Larkin2009) use variable length encoding for both word IDs and probability values. Watanabe, Tsukada and Isozaki (Reference Watanabe, Tsukada and Isozaki2009) use word-level trie architecture and compress it in a succinct data structure that represents a static trie as a continuous bit string.

Pauls and Klein (Reference Pauls and Klein2011) present a system with several variants: one based on sorted arrays, another one extends this with variable length encoding of the data, and a third one uses hash tables instead of sorted arrays. Heafield (Reference Heafield2011) presents a system with two variants. One is a reverse trie (storing n-grams in reverse word order) with sorted arrays, and the other uses an advanced implementation of hashing techniques. Both systems exhibit outstanding compression and very fast n-gram searching.

Instead of loading a whole model into memory, portions of a model can be stored on disk and loaded into RAM as they are required. For trie-based architecture, a natural unit for on-demand loading is the block of successor nodes (see Figure 1; Ravishankar Reference Ravishankar1996). If a block of successors is stored as a contiguous region in file, it can be indicated by relative offset value(s). A relevant file-section can be loaded to RAM via memory-mapping (Federico and Cettolo Reference Federico and Cettolo2007; Zens and Ney Reference Zens and Ney2007). Then, looking for a specific successor word requires a binary search in a sorted array.

Another architectural issue is the use of mutable versus serialized representations. Mutable data structures represent tries in memory as collections of interlinked node objects (or records), using object references or memory pointers. Such implementation offers fast lookup and flexibility. For storage on disk, such data structure has to be serialized. A typical serialization is a contiguous array of records where reference pointers are substituted with offset values. Germann et al. (Reference Germann, Joanis and Larkin2009) propose a compression scheme where the whole model is encoded as a serialized array with variable length encoding. For search, the file is memory-mapped and traversed in RAM, without unfolding it into a mutable trie. Locally compressed data and offset values are decompressed on the fly in course of a search. However, such n-gram models are not updateable and must be loaded whole in memory (posing considerable memory requirements).

2.3 Randomized hashing for storing n-gram models

Randomized language models use random hash functions to map n-gram strings to their associated counts/probabilities. The basic idea is that the size of the stored model can be significantly reduced if the n-gram strings are not stored at all. Instead, hash values of n-gram strings are used as keys. During encoding, a set of random hash functions is used to represent each n-gram as a bit vector and all such vectors are stored together in a specialized data structure. During retrieval, the same hash functions are applied to a query n-gram and a bit vector is sought in the data structure. A huge reduction in storage size is achieved by the specialized data structure that stores all the bit-vectors in a massive, randomly overlapping way (many bits are shared by different keys). Talbot and Osborne (Reference Talbot and Osborne2007a, Reference Talbot and Osborne2007b) implemented this approach with the Bloom filter (Bloom Reference Bloom1970) as a basis for the specialized data structure. Talbot and Brants (Reference Talbot and Brants2008) describe a system using the Bloomier filter (Chazelle et al. Reference Chazelle, Kilian, Rubinfeld and Tal2004). Guthrie and Hepple (Reference Guthrie and Hepple2010a, Reference Guthrie and Hepple2010b) proposed an even more compact representation that uses minimal perfect hashing. For a concise technical description of randomized hashing, see Guthrie and Hepple (Reference Guthrie and Hepple2010a).

One drawback of randomized hashing architectures is the possibility of errors. Methods based on the Bloom filter may sometimes return incorrect count for stored n-grams (Guthrie and Hepple Reference Guthrie and Hepple2010a). All randomized hashing architectures have false-positive errors: For an n-gram that was never stored in the model, a system may return some value instead of reporting that the n-gram was not found. There are methods to minimize such errors by storing some small additional information for each n-gram (the so-called ‘fingerprints’). By controlling the size of “fingerprints”, probability of errors can be adjusted, but this increases the size of the stored model.

Since randomized hashing architectures do not store the actual n-grams, the n-grams in a model cannot be enumerated. While this is not a requirement for applications that only need handling of literal queries, it does mean that wildcard queries cannot be supported with such architecture, at least in its current formFootnote ¹.

For operational deployment, purely hash-based language models must be completely loaded in memory. This carries an advantage and a disadvantage. All queries are served in RAM, so performance is quite fast. The disadvantage is that such architectures do not allow partial loading. Therefore, even if hash-based architecture can store a language model in significantly less space than trie-based approaches, it still imposes considerable limitations for hardware. For example, one of the methods described by Guthrie and Hepple (Reference Guthrie and Hepple2010b) may store the entire Web1T collection in about 10 GB, but it also means that a computer will need at least that amount of RAM available to work with such modelFootnote ².

Another aspect of randomized hashing architectures concerns updateability – adding new n-grams and updating counts for stored n-grams. Talbot (Reference Talbot2009) and Van Durme and Lall (Reference Van Durme and Lall2009) have demonstrated methods for approximate counting (count updates) in randomized hashing models. In addition to probabilistic storage of n-grams and counts, these solutions introduce data structures to support probabilistic updates, which are lossy in the sense that they may lead to estimation errors (reporting inaccurate counts). Here again, probability of errors can be lowered by assigning more memory to the probabilistic counters, which increases the memory footprint of the whole encoded model.

Architecture presented by Guthrie and Hepple (Reference Guthrie and Hepple2010a, Reference Guthrie and Hepple2010b) does allow changing of counts, so it is partially updateable. Yet, like the other hashing-based methods, it does not allow insertion of new keys after compilation. Variants of Minimal Perfect Hash Rank (MPHR) use quantization based on corpus statistics – this allows very tight compression, but precludes updateability of counts – because updating would change corpus statistics and would require re-encoding of the whole dataset.

Static randomized hashing approaches cannot incorporate new data without fully retraining from scratch (Levenberg and Osborne Reference Levenberg and Osborne2009). An inherent property of randomized hashing models is that the size of the full set of keys (number of distinct n-grams) must be available (or estimated) when the randomized hashing data structure is constructed – to achieve adequate hashing and prevent collisions. This sets a limitation on growth of the model – the model can be populated with new n-grams only up to a pre-estimated limit, beyond that new n-grams cannot be added to the model (adding new keys will compromise the hashing). Efficient estimation of hashing parameters a priori (without scanning the target dataset) remains an open research question (Talbot Reference Talbot2009). The choice of parameters also predefines model size – the model is constructed a priori to accommodate a certain number of distinct n-grams and the corresponding memory footprint is reserved, rather than growing incrementally with population. Levenberg and Osborne (Reference Levenberg and Osborne2009) present a dynamic variant of randomized hashing, one that allows inserting new material into a language model (and even deleting some stored data). This is achieved by introducing an overflow data structure that stores data beyond the predefined capacity of the core randomized structure, and relying on the assumption that if the core data are trained on a large corpus, truly new n-grams will be rare and can thus be accommodated in the overflow.

Static randomized hashing models do achieve excellent compression. Some comparisons of such models with trie-based models are presented by Heafield (Reference Heafield2011) and Pauls and Klein (Reference Pauls and Klein2011).

3.1 The choice of granularity

Word-level granularity is traditionally preferred for trie-based word n-gram models because it is considered more memory-efficient, especially when words are represented with numeric IDs. However, more sharing of common prefixes is possible with character symbols. Instead of using word-level symbols (Figure 1), we opted for character-level granularity (Figure 2). With character-level encoding for n-grams, we must explicitly encode inter-word delimiters (we use the ‘_’ symbol). Yet, with adequate compression, an efficient and flexible character-level trie for large word n-gram models is feasible.

3.2 System structure

The TrendStream architecture is outlined in Figure 3. Conceptually, the whole trie for a large n-gram model is a tree of linked nodes with a single root. We use a simple forward trie: n-grams are stored without any rotations. Each node represents one character (but see Section 3.8, which describes a node-per-byte correspondence).

Fig. 3.

Schematic outline for word n-gram trie, with character-level granularity. Shaded triangles represent sub-trees.

Only a small portion of the trie is active in memory at any time (‘Active Trie’). The whole trie is stored on a disk in a serialized compressed form. The whole file, or portions of it, can be loaded into memory (via memory-mapping), and only relevant parts of the memory-mapped chunks are unfolded (decompressed) into mutable linked-nodes structure, a process that is automatically guided by the trie search algorithm (see next section).

The use of uncompressed mutable data structure in the Active Trie has several advantages. Many searches follow the same prefix paths. Keeping those paths in memory (as kind of cache) allows faster search than uncompressing them for each query. On the other hand, with mutable linked lists, parts of the Active Trie can be dropped – thus allowing programmatic regulation of memory loads. A third advantage is that data in the Active Trie can be easily updated (e.g., adding new n-grams). Thus, when needed, the same encoded n-gram model can be used in read/write mode.

3.3 Node structure and search

For a character-level trie, a simple linked-list implementation for each node may have two links: a syntagmatic link (next character in sequence) and ‘alternative’ link (next character in list, see Figure 2(b)). To facilitate faster searches, we use a Ternary Search Trie (TST) data structure (Bentley and Sedgewick Reference Bentley and Sedgewick1997). In TST, each node may have up to three children, rather than two, and the inter-node linking structure is analogous to alphabetically sorted order. A TST search compares (by numeric value) the current character in the search string with the character at the node. If the search character is less, the search branches into a child that has a lesser char-value (‘lo-child’); if the search character is greater, the search branches to the child that has a higher char-value (‘hi-child’). When the search character is equal (a match), the search goes to the ‘next child’ (syntagmatic link) and proceeds to the next character in the search string. Bentley and Sedgewick have shown that ternary recursive decomposition, applied character-by-character on strings, is a very efficient search strategy, with search time linear in the length of the search key.

The classic TST is well suited for in-memory implementation (Bentley and Sedgewick Reference Bentley and Sedgewick1998). Here we describe a method to efficiently load portions of the trie from serialized form. We use unidirectional linking, so any child-node is logically accessible only from its parent node. In our Active Trie, a node has a hybrid structure (see Table 1) – it has in-memory references to its children, and also carries the values of children's offsets in the serialized data structure (e.g., on disk). This hybrid structure is the key for flexibility.

Table 1.

Fields for a mutable hybrid TST node

When a node is loaded into the Active Trie, it carries the offset values of its children. Any child-node, when requested for the first time, is loaded by the offset value. Upon loading a child, the parent node drops the child's offset value and stores a pointer to child-node. When a child is unloaded, the parent will store the child-offset value again – this allows reloading a child when necessary. The offset of the root node is kept in the header of the trie file, and the root node is always the first one that is loaded. Any other nodes are loaded into the Active Trie only when required by the search process.

3.4 Counts versus probability values

The core data associated with every n-gram in a model are the count (whole integers) or probability (floating-point numbers). The advantage of counts is that they are easily and locally updatable. Our implementation stores a count value for every n-gram. Cumulative counts are maintained for each n-gram order (e.g., 1–5, or higher) and are stored in the file header. Fractional probability values, when required, are computed on the fly during query processing. This design allows easy encoding of the existing tabulated n-gram collections and also generation/update of n-gram models from text.

3.5 Serialized data structure and compression

The serialized structure of a single node derives from the TST node structure described above. Essentially, we serialize a linked-list structure where each node may have up to three links to children. Links are represented by offset values. For each node, we store character value, offset values of its children and the associated data (count value, though more complex data is also used sometimes, see Table 2 and also Section 3.8). All nodes are encoded, in post-order, into a continuous sequence of records on disk. For very large n-gram models, the resulting sequence may take several gigabytes (even with compression), hence we use 64-bit offset values.

Table 2.

Serialized record structure for a TST node

Note: data sizes are ‘conceptual’, actual nodes are tightly compressed with variable length encoding.

Compression is used to minimize the overall file size, and to keep the memory-mapped portions small. For pinpoint activation, each record is compressed separately, independently of other records. The record length is variable. Only two fields are mandatory – an indicator flag and character ID (1-byte each). Child offset values are encoded only for children that actually exist (no space is reserved for potential children). Coding takes two steps: First, we use simple delta compression – encode only the differences between node's own offset and the children's offsets. Next, we use variable length encoding of integers. However, instead of varying on the bit-level, or using representation in base-128,Footnote ³ we use the core byte-level numeric types as afforded by the programming language (i.e., 1-/2-/4- or 8-byte integers) and specify the field lengths in the indicator flag. The single-byte indicator flag indicates several things at once: how many children there are, their roles (hi/lo/next), how many bytes are used to encode each value, and whether the node carries any data or not. This overloading is achieved by using 250 pre-arranged fixed values, while six more values are reserved for special cases. If data is present, we use an additional 1-byte indicator flag (which signifies the data type and how many bytes are used), followed by a variable-length encoded count value. When necessary, more complex associated data can be stored in a similar manner.

3.6 Updateability and optimization

When working in updateable mode, counts for stored n-grams may change and new n-grams may be added, thus introducing new nodes and new children for existing nodes in the trie. In TrendStream, all changes always occur in the mutable Active Trie in memory. Serialization works in two steps: (a) basic update, and (b) optional later optimization.

Basic update works as follows: Both new nodes and affected –old nodes are compressed and serialized individually, as described above. Records for new nodes are appended at the end of the file. Updated old nodes can rarely fit into their old tight places in the file. We use two approaches for growing the serialized file. One approach uses a simple ‘hop-trace’ solution: store an old node in a new location at the end of file and overwrite the record in old location, leaving a hop-trace. A hop-trace includes two components: a flag value indicating that the data is a ‘hop’ offset, and an offset value to the new location. When n-gram collection grows very big, ‘hop’ offsets may need 64-bit integer values. Since an ‘old’ location is often just 3–4 bytes long, in many cases it cannot store a hop-trace. To ensure that any record can be overwritten with a ‘hop-trace’, a record must have minimal size. Thus, we use the same serialization format in two modes: padded and unpadded. The padded format differs in that any record that is too small after compression is padded with empty bytes up to a minimal required size. A serialized file with hop-traces is fully operational for literal and wildcard n-gram searches, and for further updating. An alternative approach goes without any hop-traces. When an updated node is serialized, it is always written in a new location, and its parent is required to update itself as well. In serialization, child nodes are always encoded before their parents and this prevents catastrophic chains of updates – by the time a parent node needs to be serialized, all of its children and descendants are already accommodated.

For optimization, the system includes a compaction process that recodes a whole file (trie) and eliminates hop-traces and ‘dead’ sections. The compaction process can also add or remove record padding. Conversion between padded and unpadded formats is simple, always available, and is very fast. Notably, a file is updateable even after optimization.

With this design, incremental encoding of the existing tabulated collections and collecting from streaming text is essentially the same process, with just different methods for reading source data. Examples of the process are given in Section 4.1.

3.7 Loading by offsets and memory-mapping

In TrendStream, decompression of a node does not depend on other nodes. Any node can be individually found in the serialized sequence by offset value, and quickly decompressed. Depending on memory utilization policy, the whole serialized sequence, or parts of it, can be memory-mapped and kept in RAM (as Compressed Cache) for fast decompression. This section describes how partial on-demand loading is facilitated.

As indicated by the previous research (Ravishankar Reference Ravishankar1996; Federico and Cettolo Reference Federico and Cettolo2007; Zens and Ney Reference Zens and Ney2007), a block of immediate successor words for a given word is a natural and efficient unit for on-demand loading. With a character-level trie, a block of successor words is actually a sub-tree (see Figure 3). Sub-trees corresponding to successor-blocks are automatically identified during compaction–optimization stage of encoding. For each block, nodes are serialized and compressed individually, in post-order, with an additional provision: They are grouped together and saved as a contiguous sequence in the trie file. For on-demand loading, the start- and end-of-block offset values are stored in the record of the inter-word delimiter character (the root of the sub-tree).

In on-demand loading mode, efficient loading of blocks is done in the following manner. When the search algorithm encounters an inter-word delimiter in the Active Trie, a file-chunk (the serialized sub-tree) is memory-mapped and is then ready for fast pinpoint decompression of individual nodes. There is no need to decompress all of the nodes in a block – only those are decompressed that are specified by the search process. The Compressed Cache manages all memory-mapped chunks. To optimize memory usage, it tracks the ‘usefulness’ of on-demand-loaded chunks and unloads chunks that are not used for a while. Note that dropping a sub-tree from the Active Trie is not the same as dropping a memory-mapped chunk from the Compressed Cache. The two complementary components have separate memory policies that contribute to overall system flexibility.

3.8 Word recoding and byte-level granularity

A character-level trie can be made significantly smaller by recoding all words into shorter code words. During model encoding, we sort all unigrams and assign them with integer IDs in decreasing order of frequency (i.e., static pseudo-Huffman codingFootnote ⁴). Numeric codes are then converted into base-254-byte sequences. The 254 most frequent words are coded as 1-byte code words, the next 64,516 most frequent words are assigned 2-byte code words. More than 16 million additional words can be encoded as 3-byte sequences, which is enough to cover a reasonable natural language vocabulary. For example, an n-gram such as ‘with_admirable_style’ may be converted into a much shorter sequence like ‘o_z8H_b7’. We use base-254 rather than 256 since we reserve 1-byte value for inter-word delimiter ‘_’, and one additional value is reserved for special uses.

The TrendStream algorithms for search, serialization, and compression work with nodes that have byte-value identities. The TrendStream trie structure has byte-level granularity. This allows uniform treatment of words or code words – both kinds are treated as sequences of byte-valued nodes.

In practice, we do not recode the first word of any n-gram. Thus, the layer of unigrams in a trie also serves as a dictionary for translating words into code words. Unigrams are encoded as sequences of nodes where each node carries one-character byte value. A node that encodes the last byte of a unigram carries a complex associated data structure, which includes the unigram frequency (count) and the associated code word byte sequence. When TrendStream is queried about any given literal n-gram, it searches each word separately as a unigram, and attempts to retrieve code words for each word of the query (except first). If this step is unsuccessful, the n-gram is not in the model and the search quickly terminates. Otherwise, a code-worded n-gram equivalent (byte-sequence) is assembled and searched for in the trie. Although a recoding step takes time for each query, it allows fast rejections and shorter searches in the trie.

3.9 Supporting pattern matching queries

Pattern matching searches are supported on the core trie structure without any additional indexes. With literal n-gram queries, the related questions are, ‘is this word-sequence in the database?’ and ‘what is its count/frequency?’. With wildcard queries, we usually need to retrieve n-gram strings as well. Iteration over index keys is a principled integral feature for prefix-treesFootnote ⁵. Since TrendStream stores codeword byte sequences, it needs to be able to convert them back to word strings. The layer of unigrams serves as a dictionary from words to code words, and there is an inverse dictionary from code words to words. This dictionary is stored as a separate trie in the same serialized format, in the same file as the core trie, and uses the same load and search methods. This inverse dictionary has the same number of entries as the unigram layer in the core trie. Inverse dictionary is automatically updated whenever a new unigram is inserted into the system.

Technically, the same implementation supports two different syntax modes of wildcard queries. The ‘extended’ mode allows full regular expression syntax for any n-gram position, for example, ‘is_[ae].+|b..’ retrieves all bigrams where first word is ‘is’ and second word starts with ‘a’ or ‘e’, or starts with ‘b’ and has exactly three characters. The ‘simple’ mode supports just the two familiar wildcards: ‘?’ and ‘*’. The question mark stands for any character. When used alone, the asterisk stands for any single word. When used in a pattern with letters and ‘?’, the asterisk stands for any sequence of zero or more characters. For example, a query ‘a_g?*_*’ would retrieve all and only trigrams where the first word is ‘a’, the second word starts with two letters, of which the first must be ‘g’, the third word may be any word (query matches, for example, ‘a_good_day’).

Interpreting a wildcard query involves counting the number of components (separated by inter-word delimiters, for example, blank space or ‘_’). Each component is either a literal word or a wild-card pattern. Wild-card patterns are translated into regular expressions. In regex query mode, regex components of the query are directly interpreted as such. Search in the trie is recursive, with backtracking, starting with the first query-component. The search process iterates on the trie, generating candidates and filtering them against the query components.

For example, consider the query ‘a_g?*_*’ that starts with a literal component. If the first word, ‘a’ is found among the unigrams, the set of its successors (code words) is pinpointed by a single address and can be loaded from a trie file to the compressed cache, and searched exhaustively. Each candidate code word (a byte-sequence) is converted into a word (via the reverse dictionary) and if the word matches the regular expression, we have a viable candidate. The node for the last byte of the candidate byte-sequence holds the offset for loading the block of next successors – that block is where candidates are sought for the next component of the query. If a candidate byte-sequence is found there, and its corresponding word is matched by the regular expression, we have a global match for the query. The frequency count of the n-gram is in the very last node of the retrieved sequence. To find a next global match, the system tries to find a next match for the last candidate component, ‘*’. Upon exhausting all candidates for the last word (given the current state of candidates for all preceding components of the query), the system backtracks to the handler of the previous component, ‘g?*’. The block of (depth 3) successors that has been just exhausted is not needed anymore and may be unloaded from memory. If another candidate is found for the second component, a block of successors is loaded and searched. Eventually, the system backtracks to the first word/component and the search is exhausted. If the first component is not a literal but pattern, the recursion-backtracking process is repeated until backtracking reaches the root node. Handling of literal components is simpler. All literal components of a query are recoded into codeword byte-sequences. In any respective position on the trie, instead of searching a block of successors, only a single byte-sequence is sought. Complex regex or wild-card queries are served with very little memory load due to unloading of blocks (from Active Trie) upon backtracking.

When processing pattern-matching queries, in addition to returning all the matching n-grams from the database, TrendStream also automatically sums the counts (or frequencies) of all matching n-grams and outputs that value. There is also an alternate service mode. Instead of returning all the matching n-grams in one ‘batch’, a pattern-matching query can be served in Iterator Mode, in which matching n-grams are searched for, one by one, only when a hasNext() request is issued by a calling application.

4.1 Encoding: data and performance

We used data from two sources – Google Web1T and English Gigaword corpus (Graff and Cieri Reference Graff and Cieri2003). Encoding of the former demonstrates handling of pre-tabulated data, while the latter is an example of generating a large encoded collection of n-grams directly from streaming text.

Implementation of TrendStream provides configuration settings for filtering of punctuation, digits/numbers, and out-of-vocabulary words – depending on the settings, each of these can be either accepted, rejected, or encoded as a class (punctuation as ‘# PUNC’, numbers as ‘#’, and unknown words as ‘# UNK’). For some practical text processing,Footnote ⁶ we generate n-gram models with controlled vocabulary of about 220 thousand word forms (a comprehensive coverage of English vocabularyFootnote ⁷), punctuations accepted, but numbers converted to ‘#’. In addition, all accepted n-grams are converted to lowercase, and identical n-grams are merged (counts summed). With such filtering, we retained about half of the original Web1T data (see Table 3). The resulting TrendStream-encoded file stores about 1.8 billion unique n-grams.

Table 3.

Original and filtered Google Web1T n-grams (unique n-gram types)

During encoding, TrendStream makes use of the inherent updateability of its data format. For example, with the Web1T data, we encode the unigrams first, then the bigrams, trigrams, etc. Each time, the system simply updates more data into the compressed format, without recalculating any of the data that are already stored. There is just one single pass over the source data, reading directly from gzipped original tabulated files, with all filters applied on the fly. A single-threaded TrendStream process, on a Linux server (specification B), completed filtering and encoding of the Web1T collection in about 12 hours, utilizing one CPU and up to 16 GB of RAM. The optimized file size is 10.77 GB, with storage ratio of 6.15 bytes/n-gram. A version of the whole Google Web1T collection, without filters, but with uniform conversion to lower case, retains 3.35 billion distinct n-grams (out of 3.79 billion). Encoding of this data takes about 40 hours, utilizing one CPU and up to 25 GB of RAM. The resulting database file size is 20.4 GB, and the storage ratio is 6.53 bytes/n-gram.

The process of generating a language model from Gigaword texts was slightly different. TrendStream sequentially processed the Gigaword data directly from four very large text files (corresponding to the four sections of the Gigaword 2003 corpus, in total 4.5 GB uncompressed). Upon opening a text file, TrendStream simply defines a window of size n on the text, generates all n-grams of order 1 to n in the window, applies filters according to settings, and stores the n-grams in the Active Trie. It then continues by sliding the window until it reaches the end of file (resetting the window at end of sentence or at end of paragraph – depending on settings). Millions of new n-gram types (unique sequences) are generated and counts for millions of n-grams are updated continuously. During encoding, TrendStream automatically compresses data from the Active Trie to the Compressed Cache and to disk, and it also moves data in the other direction – when updates are needed for stored n-grams that are no longer in the Active Trie. The single-threaded TrendStream process on a non-dedicated Linux server (spec. B) completes generation (with filtering) and optimized encoding of n-grams (orders 1–5) for the Gigaword corpus in about 24 hours using one CPU and up to 20 GB of RAM. The resulting optimized file size is 7.3 GB, with the storage ratio of 5.68 bytes/n-gram. Statistics for the Gigaword n-grams collection are presented in Table 4. Unlike the Web1T data, this dataset includes many n-grams with very low counts (e.g., 1, 2).Footnote ⁸ We henceforth refer to these databases, with filtered data, as Web1T.f and Gigaword.f.

Table 4.

Statistics for n-grams collection generated from the Gigaword 2003 corpus

Note: Includes n-grams that span across sentences, uses controlled vocabulary.

4.2 N-gram retrieval performance

The TrendStream n-gram retrieval performance was tested with a benchmark task. We used a collection of texts totaling about 10 million words.Footnote ⁹ Two massive retrieval tasks were defined – one for bigrams and another for 5-grams. On each task, the system scans text files with a window of two or five words (with punctuation marks treated as elements), and attempts to retrieve n-gram counts from the database. In this task, repeated queries come about only as they naturally occur in the text. Evaluation runs were conducted with the two filtered encoded language models described in the previous section, on three platforms differing in their computational power. Note that deploying of the language models was extremely simple – we just copied the TrendStream software (less than 1 MB) and the compiled n-grams file (7.3 or 10.77 GB).

Memory use and search times were measured for two different load options – on-demand loading and whole-model loading.Footnote ¹⁰ Since the on-demand mode heavily uses disk access, it was tested in two conditions – cold start (with empty OS-caches, all data read from disk) and warm start (some OS-caches are reused). For each condition, timing and memory values were averaged across three separate runs. Results are given in Table 5.

Table 5.

TrendStream retrieval performance for 2- and 5-grams, with two different models on several different platforms

Notes: Platform specifications (a)–(c) are listed in the Appendix. Timing values reflect pure search times (excluding text files I/O). Each memory value is sum of Active Trie and Compressed Cache, except for full loading mode where values reflect Active Trie only and Compressed Cache is the size of the database file.

In on-demand loading mode, disk access time is a notable factor – the system is rather slow in the cold-start runs (however, time to first response is always under 1 second). As the operating system caching kicks in, the TrendStream performance accelerates and reaches levels that are quite suitable for some intensive text-processing tasks. We get thousands and even hundreds of thousands of queries served per second.

Performance in the full-loading mode is about two to three times faster than on-demand loading with warm cache. However, there is a huge difference in memory consumption. Full loading consumes several gigabytes of RAM. With on-demand loading, TrendStream performs the same task a little slower, but with dramatically less memory. For bi-grams retrieval, memory use averages are below 150 MB and peak usage values are all below 220 MB. For the 5-grams, averages are below 500 MB, with peak loads all below 700 MB. Notably, on-demand loading is not just lazy memory-mapping from disk – the TrendStream memory manager actively releases parts of the trie from memory, which is why average memory values are much lower than peak values.

We also conducted an evaluation with a database that includes the full (unfiltered) set of data from Google Web1T (the compiled TrendStream file of 20.4 GB). Results are presented in Table 6. With a larger model, performance is slower (compared with Table 5) because search-space is larger, but the speed is still in thousands of queries per second.

Table 6.

TrendStream retrieval performance for 2- and 5-grams with all Google Web1T data on a high-end Linux server

Note: In full-load mode, RAM use is 20.4 GB + the amount indicated.

Full loading and on-demand loading are two extreme cases – the first optimized for speed, and the second optimized for minimizing memory consumption. TrendStream also provides a flexible mode of loading via a parameter setting that specifies how much memory should be used for mapping. For example, working with a 10-GB model file, we can specify to memory map 3 GB (or any other amount) and the rest is handled by on-demand loading.

With on-demand loading, TrendStream can run on platforms that do not have enough RAM for a whole model. This flexibility extends to using the system even on the modest desktop and laptop platforms. On modest platforms, n-gram models would not be used to analyze massive amounts of text, but they can be useful for research, and for NLP tasks that need quick processing of relatively small amount of text. One such task is contextual spelling correction. For example, Microsoft Office 2007 uses a pruned trigram language model that is tightly compressed into a few megabytes (Church, Hart and Jianfeng Reference Church, Hart and Jianfeng2007). Here we demonstrate running very large, multi-gigabyte 5-grams language models on the modest hardware. We use the same database files described above (Gigaword.f and Web1T.f), and the set of platforms includes a desktop and laptop, each with just 4-GB RAM (specifications D and E). For a small-scale performance evaluation task, we selected a single textFootnote ¹¹ with 103,666 tokens (83,592-word tokens and the rest are punctuation tokens). Separate evaluations were run for retrieval of two-grams and 5-grams: on each run, the text was processed with a two- or five-word sliding window. Timing values were averaged across three separate runs in each condition. Results are presented in Table 7. Not surprisingly, there is a marked difference in performance between cold and warm starts, indicating that disk access is the most significant source of delay. Even in cold start, on our slowest platform, the system serves between 460 bigrams and about 120 5-grams per second, which is suitable for immediate processing of short documents. On the modest platforms, with warm start the performance is thousands of queries per second, which is adequate for some serious NLP processing.Footnote ¹²

Table 7.

TrendStream retrieval performance for 2- and 5-grams, for one test file with two different models on several different platforms

Notes: Platform specifications (a)–(e) are listed in the Appendix. Average rate values reflect pure search times (not including text files I/O). Each memory value is sum of Active Trie and Compressed Cache.

For 2-gram retrieval task, the number of queries is 103,665, of them 93.3% are found in the Web1T.f model, 91.9% are found in the GigaWord.f model. For 5-gram retrieval task, the number of queries is 103,662, of them 25.5% are found in the Web1T.f model, 14.3% are found in the GigaWord.f model.

4.3 Performance with pattern matching queries

The TrendStream performance for pattern-matching queries is illustrated in Table 8. Six sample wildcard queries and three sample regex queries were run against the Web1T.f database file on three different platforms. On the Linux server (spec. B, 32-GB RAM), we ran queries in two different memory modes – one with full model loading to RAM, and another with on-demand loading. The Windows laptop has just 4-GB RAM, so only on-demand loading was used. All on-demand loading queries were run with warm OS-cache. Timing and memory-use values were averaged across three separate runs in each condition.

Table 8.

TrendStream retrieval performance for some wildcard and regex queries with Web1T.f database

Query 1, ‘to_*_b*d’, returns 19,466 trigrams, among them ‘to address beyond’ and ‘to international boulevard’. Query 2, ‘a_????_b*d_r*_*’, returns 165 5-grams, among them ‘a rock band rather than’ and ‘a very broad representation of’. Query 1 is much shorter, but it takes more time to process. This illustrates how the system uses query constraints to limit search. Both queries have a highly frequent first word (to/a), with large sets of successors for next word (depth 2). With query 1, for each candidate at depth 2 the system proceeds to a deeper level, seeking a third word. For query 2, it proceeds to a deeper level only for four-lettered candidates at depth 2. Notably, except for the ‘accept any’ (‘*’ or ‘.+’), all regular expressions are used as filters and help reduce the search space.

It might be expected that a fronted wildcard query would be quite difficult and time-consuming to process on the TrendStream data structure. However, this is not the case. We tested two fronted wildcard queries. Query 3, ‘*d’, retrieves unigrams, and Query 4, ‘* was’, retrieves bigrams. Query 3 scans over all the unigrams in the model. Query 4 also scans on all the unigrams, and for each one it checks the successors at depth 2. Performance on these simple fronted wildcard queries is quite fast, even faster than performance for the more constrained queries 1 and 2. To put the system to a more demanding test, we ran Query 5: ‘*t *t’. Here it must scan all unigrams, and for each accepted unigram it needs to perform a wildcard search at level 2. The system retrieves about half a million matching bigrams in 21 seconds (fastest, 85 seconds on the slowest machine). We then tried a more demanding Query 6, ‘*t *t a’, which returns 15,782 trigrams. This query has to visit all the n-grams that ‘*t *t’ visited, and for each of them steps into level 3, looking for next word ‘a’. Query 6 completes in 21 seconds (88 seconds on the slowest machine). Note that this is done without any additional indexing, inverted or rotated structures, and with very modest use of RAM.

With full regular expression syntax, TrendStream allows to formulate even more sophisticated conditions for n-gram retrieval: a regular expression (or a literal string) for every element ‘word’ of the query (but not across words). Sample Query 7 has regex first and third elements, and a very frequent second word. It returns 275 trigrams, among them ‘parking for free’ and ‘worked for money’. Query 8 starts with a frequent word (‘was’), and continues with three regular expressions, which require many ‘check the whole next level’ steps. Results include n-grams such as ‘was marked by innovation’ and ‘was considering this option’. Query 9 is quite complex – it has regular expressions for each of its three elements, and accepts any first word that is three- to five-letter long. Thus, it requires a deep and extensive scan into the database. It retrieves 15,063 trigrams, such as ‘polar express caboose’, ‘can impress audiences’, and ‘and compress video’.

Overall, performance times are rather fast, considering that the system searches in a database of 1.8 billion n-grams. In on-demand loading mode, performance on the slowest machine in our test set is only about four times slower than on the high-end server. Memory use for pattern matching queries is remarkably low. This is achieved by two factors. First, the search is automatically guided and loads (from disk) only those chunks of data that are potentially useful. Second, upon backtracking, the recursive search automatically releases memory by unloading used portions of the Active Trie – those from which it backtracks. Upon completion of the search, the system can either release all of the memory or keep some parts of the Active Trie for serving another query. For queries that are expected to return thousands of matches, there is some speed advantage when the n-gram model is fully loaded in memory. This advantage can also be effective when many pattern-matching queries need to be served (e.g., in a batch).

We have also run pattern-matching queries with the complete Web1T database (20.4-GB file). Query ‘.+\.com’ asks how many .com web addresses are among the unigrams in Web1T. With full model loaded in memory (Linux server, spec. B), the query is processed in 16 seconds (iterating over several million unigrams and applying pattern matching to each). Queries ‘* was’ and ‘* is’ are processed in 25 seconds each, ‘sit|sits|sat|sitting .+ .{1} chair’ takes 10 seconds, and ‘.+ly good fun’ takes 15 seconds.