In multimedia, text or bioinformatics databases, applicat ions query sequences of n consecutive symbols called n-grams. Estimating the number of distinct n-grams is a view-size estimation problem. While view sizes can be estimated by sampling under statistical assumptions, we desire an unassuming algorithm with universally valid accuracy bounds. Most related work has focused on repeatedly hashing the data, which is prohibitive for large data sources. We prove that a one-pass one-hash algorithm is suffi cient for accurate estimates if the hashing is sufficiently independent. T o reduce costs further, we investigate recursive random hashing algorithms and show that they are sufficiently independent in practice. We compare our run ning times with exact counts using suffix arrays and show that, while we use ha rdly any storage, we are an order of magnitude faster. The approach further is extended to a one-pass one-hash computation of n-gram entropy and iceberg counts. The experiments use a large collection of English text from the Gutenberg Project as well as synthetic data.
@cite_28: A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that, in practice, they use three to five times less space. From a complexity standpoint, suffix arrays permit on-line string searches of the type, “Is W a substring of A?” to be answered in time @math , where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees. The only drawback is that in those instances where the underlying alphabet is finite and small, suffix trees can be constructed in @math time in the worst case, versus @math time for suffix arrays. However, an augmented algorithm is given that, regardless of the alphabet size, constructs suffix arrays in @math expected time, albeit with lesser space efficiency. It is ...
@cite_0: 
@cite_24: Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. It has been open for a long time whether these indices can be constructed in both O(n log n) time and O(n log n)-bit working space, where n denotes the length of the text. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. This paper breaks the long-standing time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n log sup spl epsi n) time and O(n)-bit working space for any 0 < spl epsi < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as Compressed Suffix Tree, Compressed Suffix Arrays and FM-index. We also study the general case where the size of the alphabet A is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log |A|)-bit working space while running in O(n log log |A|) time and O(n log sup spl epsi n) time, respectively. These are the first algorithms that achieve 0(n log n) time with optimal working space, under a reasonable assumption that log |A| = o(log n).
@cite_2: 
@cite_47: In the process of establishing the information theory, C. E. Shannon proposed the Markov process as a good model to characterize a natural language. The core of this idea is to calculate the frequencies of strings composed of n characters (n-grams), but this statistical analysis of large text data and for a large n has never been carried out because of the memory limitation of computer and the shortage of text data. Taking advantage of the recent powerful computers we developed a new algorithm of n-grams of large text data for arbitrary large n and calculated successfully, within relatively short time, n-grams of some Japanese text data containing between two and thirty million characters. From this experiment it became clear that the automatic extraction or determination of words, compound words and collocations is possible by mutually comparing n-gram statistics for different values of n.
@cite_13: This paper reports our implementation of the Virtual Corpus approach to deriving ngram statistics for ngrams of any length from large-scale corpora based on the suffix array data structure. In order to enable the VC to accommodate corpora with a vocabulary of different size, we first convert corpus tokens into integer codes. To accelerate the processing, we employ a bucket-radixsort for sorting the VC indices (or pointers, each of which represents a sequence of corpus tokens from its position to the end of the corpus). The time complexity of the sorting algorithm is of O(N log n N) in token code comparisons.
Using suffix arrays @cite_28 @cite_2 and the length of the maximal common prefix between successive prefixes, Nagao and Mori @cite_47 proposed a fast algorithm to compute @math -gram statistics exactly. However, it cannot be considered an online algorithm even if we compute the suffix array in one pass: after constructing the suffix array, one must go through all suffixes at least once more. Their implementation was later improved by Kit and Wilks @cite_13 . Unlike suffix trees @cite_0 , uncompressed suffix arrays do not require several times the storage of the original document and their performance does not depend on the size of the alphabet. Suffix arrays can be constructed in @math time using @math working space @cite_24 . Querying a suffix array for a given @math -gram takes @math time.