Shannon-fano implementation problem

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
ivelin1012
Forum Newbie
Posts: 3
Joined: Tue Jan 04, 2011 6:15 pm

Shannon-fano implementation problem

Post 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 :(
Last edited by Weirdan on Wed Jan 05, 2011 3:52 am, edited 1 time in total.
Reason: fixed indenting
ivelin1012
Forum Newbie
Posts: 3
Joined: Tue Jan 04, 2011 6:15 pm

Re: Shannon-fano implementation problem

Post by ivelin1012 »

can someone find my mistake :(
User avatar
Benjamin
Site Administrator
Posts: 6935
Joined: Sun May 19, 2002 10:24 pm

Re: Shannon-fano implementation problem

Post by Benjamin »

It's caught in an infinite loop.
ivelin1012
Forum Newbie
Posts: 3
Joined: Tue Jan 04, 2011 6:15 pm

Re: Shannon-fano implementation problem

Post 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
Post Reply