Page 1 of 1

Shannon-fano implementation problem

Posted: Tue Jan 04, 2011 6:22 pm
by ivelin1012
hello i am new with php.
I have a homework to implement shannon-fano algorithm in language of my choice.So i choce PHP
here is my function with accepts array as paramentur and performs the shannon-fano algoritm

Code: Select all

function divide_array($array)
{
  $sum=0;
  $mid=array_sum($array)/2;
  foreach($array as $k=>$v)
  {
    if($sum<$mid){
      $sum=$sum+$array[$k];
      $up[$k]=$array[$k];
      $codeArr[$k]=0;
    }
    else
    {
	
      $down=array_slice($array,$k+1);
      $codeArr[$k]=1;
	
    }
  }
  divide_array($up);
  divide_array($down);
  echo "<pre>";
  print_r($codeArr);
  echo "</pre>";
}
it gives me error Allowed memory size of 134217728 bytes exhausted (tried to allocate 261904 bytes) in
whats the problem :(

Re: Shannon-fano implementation problem

Posted: Wed Jan 05, 2011 4:39 pm
by ivelin1012
can someone find my mistake :(

Re: Shannon-fano implementation problem

Posted: Wed Jan 05, 2011 4:50 pm
by Benjamin
It's caught in an infinite loop.

Re: Shannon-fano implementation problem

Posted: Wed Jan 05, 2011 5:34 pm
by ivelin1012
Benjamin wrote:It's caught in an infinite loop.
how can i fix it ,my idea was to divide the given array in two arrays where the sum of its values is roughly equal. depending on which part of the divide is the elemnt and sets this value into the second array. then each of this arrays to be divided again until every element is in different array. for example if i have :
B=>5
A=>2
C=>1
D=>1 on the first divide has to become :
up-array :B=>5;
down-array:
A=>2
C=>1
D=>1
and in the other array to write :
codeArray
B=>0
A=>1
C=>1
D=>1
down array divides again to :
up1:
A=>2;
down1:
C=>1
D=>1
and codeArray Becomes:
B=>0
A=>10
C=>11
D=>11
then down1 array divides into:
up2:
C=>1
down2:
D=>1
and codeArray Becomes:
B=>0
A=>10
C=>110
D=>111
recursion stops and prints codeArray
can u help me realise it working