Click here to Skip to main content
13,301,664 members (64,964 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


7 bookmarked
Posted 5 Feb 2014

Counting Occurrences

, 6 Feb 2014
Rate this:
Please Sign up or sign in to vote.
A simple algorithm for counting occurrences of symbols in files


Counting occurrences of symbols can answer the question: "How many blanks are in this text?". Among other amenities, it could be used as the preliminary step in some data compression algorithms.

Here, I am going to show the implementation of a trivial algorithm using the programming languages C and Lua. In addition, a C++ implementation is available for downloading. For the sake of brevity, I don't report it here.

The Problem

Given some input data, say "hello world!", produce an output similar to:


Where 'code' is the ASCII code of the character (the value of the byte). Since we want to process large binary files, let's state it this way: "count the occurrences of each byte value (0..255) in a binary file, then sort them by occurrences".

The Algorithm

The algorithm is very simple: suppose we are reading data, one byte at time and the value of the current one is, say, 104 (i.e., the 'h' character was just read): we have to increment the occurrences of 104 and repeat such operation with the next byte, until the whole input data has been processed. A fast way for "incrementing the occurrences of a byte value" uses an array of occurrences, with the implicit assumption that the occurrences of a value are stored by the item having index equal to the value itself (e.g. the occurrences of 104 are stored in occurrences[104]). The array is eventually sorted in order to obtain the expected output.

C Code

The C implementation is pretty straightforward: The program initializes the array of occurrences, then reads data from stdin using a 4KiB buffer. After each read operation, a function is called for updating the occurrences array. Finally, the sort step is performed using the C library qsort function.

Here follows the struct holding a symbol code and its occurrences (we need to store the symbol code in order to perform the sort step).

#define BYTES 256
typedef struct TagSymbolInfo
  int symbol; // the byte [0..255] value
  int occurrences; // number of occurrences of the symbol in the given buffer
} SymbolInfo;

The initialization function (sets the symbol codes, resets the occurrences).

// initialise the symbol array
void reset_occurrences(SymbolInfo si[])
  int n;
  for (n = 0; n < BYTES; ++n)
    si[n].symbol = n;
    si[n].occurrences = 0;

The following function is the workhorse of the algorithm: it processes the input data in order to update the occurrences array:

 // counts the occurrences in the given buffer, updating accordingly the array of symbols
int increment_occurrences(SymbolInfo si[], const void * buffer, size_t size)
  unsigned char * p = (unsigned char *) buffer;
  int success = 0;
  while ( size-- )
    si[p[size]].occurrences++; // since si[n].symbol == n, we can use p[size] as index.
    if ( ! si[p[size]].occurrences )
      success = -1; // error on counter overflow
  return success;

The function used for ordering items by occurrences (and code, when occurrences are equal)

// this is the predicate for qsort.
int compare_symbols(const void * symbola, const void * symbolb)
  const SymbolInfo * a = (const SymbolInfo *) symbola;
  const SymbolInfo * b = (const SymbolInfo *) symbolb;
  if ( a->occurrences > b->occurrences || 
  (a->occurrences == b->occurrences && a->symbol > b->symbol)) return -1;
  return 1;

Finally the main function, with some boilerplate code:

 #define INBUFSIZE 4*1024
int main()
  long total = 0; // total number of occurrences, must be equal to file size
  unsigned char buffer[INBUFSIZE]; // the read buffer
  int n;
  SymbolInfo si[BYTES]; // the array of symbols

  reset_occurrences(si); // initialization

  // reading stdin until EOF (or error)
    int nread = fread (buffer, sizeof(buffer[0]), INBUFSIZE, stdin);
    if ( ! nread ) break;
    if ( increment_occurrences(si, buffer, nread) )
      printf("occurrences counter(s) overflow\n");
  // calling qsort for the sorting step
  qsort( si, BYTES, sizeof(si[0]), compare_symbols);
  // some output
  for (n=0; n<BYTES; ++n)
    char c = si[n].symbol;
    if (! si[n].occurrences) break;
    total += si[n].occurrences;
    c = isprint(c) ?  c : '.';
    printf("{symbol ='%c', code= %3d,  
    occurrences = %d}\n", c, si[n].symbol, si[n].occurrences);
  printf("total occurrences = %ld\n", total);
  return 0;

Lua Code

Lua is a wonderful scripting language, lightweight, fast and easily embeddable (more information can be found at Lua website).

Since it is a somewhat 'exotic language' here at CodeProject, I am going to give some details of the posted code.

local INBUFSIZE = 4096
local function init_occurrences()
  local si = {}
  for i=1,256 do
    si[i] = { occurrences = 0, symbol = (i-1) }
  return si

The init_occurrences function creates the occurrences array si and initializes it.

In more detail, the local si = {} statement creates a table, the only data structure Lua provides.

A table is a kind of associative array. Inside the for loop, a fresh table is created, initialized and assigned to every item of si.

The statement...

si[i] = { occurrences = 0, symbol = (i-1) } a shortcut for:

s[i] = {}
s[i]["occurrences"] = 0
s[i]["symbol"] = i-1 


s[i] = {}
s[i].occurrences = 0
s[i].symbol = i-1 

...using the 'syntactic sugar' provided with the dot operator.

Finally return si terminates the function and makes si available to the caller, avoiding its removal on next garbage collection.

The increment_occurrences function, pretty straightforward, shows the lack of the handy increment operators:

 local function increment_occurrences(si, buffer)
  for i=1,#buffer do
    local index = buffer:byte(i)+1
    si[index].occurrences = si[index].occurrences + 1

The remaining part of the program, boilerplate code...

 local function main()
  local total = 0
  local si = init_occurrences()
    local buf =
    if  buf then
      increment_occurrences(si, buf)
  until not buf
    function (a,b)
      if (a.occurrences > b.occurrences or (a.occurrences == b.occurrences and a.symbol > b.symbol)) then
        return true
  for i=1,256 do
    if si[i].occurrences == 0 then break end
    local c = string.char(i):match("([%g])") or "-"
    print(string.format("{symbol ='%s', code= %3d,  occurrences = %d}", c, si[i].symbol, si[i].occurrences));
    total = total + si[i].occurrences
  print("total occurrences = " .. total)


With a nice twist: the following statements sort the si table, using the table.sort function fed with an anonymous function.

  function (a,b)
    if (a.occurrences > b.occurrences or (a.occurrences == b.occurrences and a.symbol > b.symbol)) then
      return true

C++ Code

David Delaune, aka Randor suggested me a neat approach for reading input (you may find his comments in the thread at bottom of the page). Now it makes sense to show the C++ code:

struct SymbolInfo
  int symbol; // the byte value [0..255]
  int occurrences; // the number of occurrences of the symbol

int main()
  std::cin >> std::noskipws;
  std::array<SymbolInfo , 256> si={{0}};
  std::istream_iterator<unsigned char> input(std::cin),end;
  std::for_each(input,end,[&](unsigned char c){si[c].occurrences++;});

  for (int n=0; n<256; ++n) si[n].symbol=n;

  std::sort(si.begin(), si.end(),
    [](const SymbolInfo & a, const SymbolInfo &b) {return (a.occurrences > b.occurrences || (a.occurrences == b.occurrences && a.symbol > b.symbol));}

That is! (I have just omitted the include directives and the boilerplate printout code).

Using the Code

At the moment, the C/C++ code is ready to run on a Linux console (although modifying it for running on a Windows console is trivial) .

Lua code requires the Lua intepreter, available on Ubuntu-like distributions as package lua5.2 ( apt-get install lua5.2). In addition, binaries, also for Windows, are available here: Lua binaries at SourceForge.

C code

Compile with:

gcc -Wall -O3 -o occurrences occurrences.c

Run with:

./occurrences < <FILE PATH>

(e.g. ./occurrences < myfile.bin)

The input redirection operator (<) is mandatory in order to count occurrences of a file (otherwise the commands would count occurrences on stdin, that is characters typed by the user until CTRL^D.

C++ code

Compile progrma (1) with:

g++ -std=c++11 -Wall -O3 -o occurrences occurrences.cpp
and program (2) with:

g++ -std=c++11 -Wall -O3 -o occurrences_ran occurrences_ran.cpp  

(The C++ programs requires a fairly recent version of g++, I used the 4.7.3 one)

Run the same way the C one does.

Lua code

Of course it requires no compilation. You may run it this way:

lua occurrences.lua < <FILE PATH>  


I know it is not fair to compare the performances of Lua and C/C++ code using a rather low-level algorithm, however I am not fair, so here you are a little test.

  • Executed on a Lubuntu 13.04 system.
  • Input file: lubuntu-13.10-desktop-i386.iso (729,808,896 bytes).
  • g++ and gcc optimization level -O3.
  • Lua version 5.2.1.
  • Reported timings are generated with the Linux time command.
language file size (MiB)real (s)user (s)sys (s)speed (MiB/s)
C++ (1)6969.071.311.5176.74
C++ (2)69641.4737.203.5016.78
  1. 'Traditional' C++ program (the source file occurrences.cpp is available in the download section)
  2. More elegant program (the one shown in the article, available for download as occurrences_ran.cpp)
  • Apparently C and C++ (1) performances are very similar. They are dominated by the I/O as the real vs user and sys figures show.
  • C++ (2) is noticeably slower that C++ (1).
  • Lua is about 17 times slower than C/C++ , its execution time being dominated by the user part.


  • 8 Feb 2014 - Added the C++ code (thanks David Delaune aka Randor)
  • 6 Feb 2014 - Added the missing source files for download
  • 6 Feb 2014 - First release


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Software Developer (Senior) AEM S.p.A.
Italy Italy

Debugging? Klingons do not debug. Our software does not coddle the weak. Bugs are good for building character in the user.
-- The Klingon programmer

Beelzebub for his friends [^].

You may also be interested in...

Comments and Discussions

SuggestionYou're given Lua a bad name here. :-( Pin
m2mm4m4-Jun-15 13:22
memberm2mm4m4-Jun-15 13:22 
QuestionUnicode Support Pin
.dan.g.9-Feb-14 15:04
mvp.dan.g.9-Feb-14 15:04 
AnswerRe: Unicode Support Pin
CPallini9-Feb-14 23:28
mvpCPallini9-Feb-14 23:28 
SuggestionReading directly from the stream Pin
Randor 7-Feb-14 8:37
professional Randor 7-Feb-14 8:37 
GeneralRe: Reading directly from the stream Pin
CPallini7-Feb-14 8:56
mvpCPallini7-Feb-14 8:56 
GeneralRe: Reading directly from the stream Pin
Randor 7-Feb-14 9:36
professional Randor 7-Feb-14 9:36 
GeneralRe: Reading directly from the stream Pin
CPallini7-Feb-14 10:05
mvpCPallini7-Feb-14 10:05 
GeneralRe: Reading directly from the stream Pin
Randor 7-Feb-14 10:46
professional Randor 7-Feb-14 10:46 
GeneralRe: Reading directly from the stream Pin
CPallini7-Feb-14 11:24
mvpCPallini7-Feb-14 11:24 
GeneralRe: Reading directly from the stream Pin
Randor 7-Feb-14 11:53
professional Randor 7-Feb-14 11:53 
GeneralRe: Reading directly from the stream Pin
CPallini7-Feb-14 11:59
mvpCPallini7-Feb-14 11:59 
GeneralRe: Reading directly from the stream Pin
Randor 7-Feb-14 12:04
professional Randor 7-Feb-14 12:04 
GeneralRe: Reading directly from the stream Pin
CPallini7-Feb-14 12:09
mvpCPallini7-Feb-14 12:09 
QuestionMissing download? Pin
André Kraak5-Feb-14 23:02
memberAndré Kraak5-Feb-14 23:02 
AnswerRe: Missing download? Pin
CPallini5-Feb-14 23:48
mvpCPallini5-Feb-14 23:48 
GeneralRe: Missing download? Pin
Garth J Lancaster6-Feb-14 1:59
memberGarth J Lancaster6-Feb-14 1:59 
GeneralRe: Missing download? Pin
CPallini6-Feb-14 2:36
mvpCPallini6-Feb-14 2:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.171207.1 | Last Updated 6 Feb 2014
Article Copyright 2014 by CPallini
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid