Systems and methods for optimizing very large n-gram collections for speed and memory

A computer-implemented method of populating a data structure in a computer memory, the data structure representing a ternary search tree, the ternary search tree representing multiple word n-grams for a corpus of documents, the method comprising:

• a) selecting a unit of a word n-gram with a processing system, wherein said word n-gram comprises a sequence of units;
• b) creating a node of a ternary search tree based on the first unit with the processing system, wherein the node is represented by a record of the data structure, the record being stored at said computer memory;
• c) selecting another unit of the word n-gram with the processing system;
• d) if said another unit does not already exist as a node in the ternary search tree for said word n-gram, creating another node of the ternary search tree based on said another unit with the processing system, wherein said another node is represented by another record of the data structure;
• and
• e) repeating steps (a)-(d) to create additional nodes of the ternary search tree for additional word n-grams;
• wherein each of said records comprises a plurality of fields,
• wherein the plurality of fields include:
• a first field for identifying a given unit of the sequence of units for a given node;
• a second field reserved for storing payload information for the given node;
• and
• plural child fields reserved for storing information for a first hi-child node, a second lo-child node and an third equal-child node of the given node;
• wherein the plural child fields store one of a null value indicating the absence of an associated child node or an identifier identifying a memory location of the respective child node;
• wherein, for at least one record of said data structure, at least one of said plural child fields stores an identifier identifying a memory location of another computer memory different than said computer memory;
• and
• wherein the ternary tree is configured to be searched by comparing units of a query to nodes of the ternary tree, wherein a current unit of the query is compared to the payload information of a current node of the ternary tree, and wherein i) if the current unit of the query matches the payload information, then selecting the equal-child node as the current node;
• ii) if the current unit of the query is less than the payload information, then selecting the lo-child node as the current node;
• and iii) if the current unit of the query is greater than the payload information, then selecting the hi-child node as the current node.