counting runs of a certain length in binary data

[John W. Eaton]

On  3-Mar-2000, Mike Miller <address@hidden> wrote:

| Here's a problem:  I want to count the number of times in a sequence of
| binary digits that I observe a run of N or more digits that are the same.  
| I think there must be an easy and efficient way to get Octave to pump out
| an answer.
| 
| For example, if this were my vector of binary digits
| 
| [0 1 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1]'
|    ^     # ^   #       ^   # ^     #
| 
| I would count four runs of length 2 or greater.  (I've marked the
| beginning of each run with '^' and the end with '#'.)
| 
| I have been able to get Octave to tell me how many times I have a run of
| length 2 or more using the code given in the third line below:
| 
| octave:1> m=100; n=10;
| octave:2> X=(rand(m,n)<.5);
| octave:3> sum(diff([ones(1,n);abs(diff(X))])==-1)
| ans =
| 
|   24  25  27  24  25  31  23  26  25  26
| 
| The first line tells the size of the matrix, the second line generates a
| matrix of binary scores and the third line counts the number of runs of
| length two or more for every column of the input matrix.
| 
| Does anyone have any neat ways of counting runs of length greater than
| two?  I assume 'diff' would be used repeatedly somehow.

Would the following work?

  y = [0; X; 0];
  find (diff (y) == -1) - find (diff (y) == 1)

X is the vector of binary digits.  The idea is that prepending and
appending zeros ensures that the first nonzero element of diff(y) will
be 1 and that the last nonzero element will be -1, and that there will
be an equal number of 1 and -1 elements.  Then the results of the two
find commands should always have the same length, and their difference
should be the run-lengths for the ones in the original vector.

jwe



-----------------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.che.wisc.edu/octave/octave.html
How to fund new projects:  http://www.che.wisc.edu/octave/funding.html
Subscription information:  http://www.che.wisc.edu/octave/archive.html
-----------------------------------------------------------------------