Method, system, program, and data structure for a dense array storing character strings

Abstract

Disclosed is a system, method, and program for generating a data structure in computer memory for storing strings, such as words in a dictionary. Each string includes at least one character from a set of characters. An arrangement of nodes is determined to store the characters such that the arrangement of the nodes is capable of defining a tree structure. An array data structure is generated to store the nodes. The array includes a row for each node and a column for each character in the set of characters. A non-empty cell identifies a node for the character indicated in the column of the cell that has descendant nodes in the row indicated in the cell content for the node. The array data structure is processed to eliminate at least one row in the array data structure to reduce a number of bytes needed to represent the array data structure. In this way, the array data structure following the processing requires less bytes of storage space then before the processing.