arXiv Open Access 2017

On estimating the alphabet size of a discrete random source

Philip Ginzboorg

Lihat Sumber

Abstrak

We are concerned with estimating alphabet size $N$ from a stream of symbols taken uniformly at random from that alphabet. We define and analyze a memory-restricted variant of an algorithm that have been earlier proposed for this purpose. The alphabet size $N$ can be estimated in $O(\sqrt{N})$ time and space by the memory-restricted variant of this algorithm.

Topik & Kata Kunci

cs.DS

Penulis (1)

Philip Ginzboorg

Format Sitasi

APA MLA BibTeX

Ginzboorg, P. (2017). On estimating the alphabet size of a discrete random source. https://arxiv.org/abs/1711.07545

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓