all-order-markov-predictor-off.pl

2-order markov predictor

# 基于散列的预测器
# 1.维护两个散列：预测表PreTable和状态表StaTable;
# 2.预测表PreTable：关键字为上下文，数据内容为该上下文（关键字）下的预测结果；
# 3.状态表StaTable：关键字为状态，数据内容为该状态（关键字）出现的次数；某个状态是上下文与下一跳组成的串。




#K-Order Markov Predictor
#Input Parameters:k-the number of order;n-the length of the trace used;


#------------------------------------#
#        1 获取参数：k,n,mv          #
#        2  参数合法性检查           #
# -----------------------------------#
if ($#ARGV !=1){
     print "输入参数不正确！";
     exit;
}

$k=$ARGV[0];
$n=$ARGV[1];

if (($k!=1) && ($k!=2) && ($k !=3) && ($k !=4) && ($k !=5)){
     print "输入的阶数k错误！";
     exit;
}

$dir="..\\Data\\";

$tdir="..\\trace\\";
$ptdir="..\\\\trace\\\\";

opendir(dirfh,$dir);
@files=readdir(dirfh);
closedir(dirfh);

$stepLen=1;            #跨度

%AccuracyCount;        #存放相应准确度(index)出现的次数
$TotalCount=0;         #统计所有准确度出现的总次数

#用于划平均图
$MAXPOSI=$n;           #考虑的最大位置
$ASCNUM=2;             #两相邻位置间的间隔
@PosiCount;            #存放各位置出现的次数
@AccuSum;              #跟@Position对应，存放相应位置出现的准确度的和
for($i=0;$i<=$MAXPOSI;$i+=$ASCNUM){$PosiCount[$i]=0;}
for($i=0;$i<=$MAXPOSI;$i+=$ASCNUM){$AccuSum[$i]=0;}

#-----------------------------------------------#
#      进行一个目录下的所有原始数据文件处理        #
#-----------------------------------------------#
for ($fh_index=2;$fh_index<=$#files;$fh_index++){

     print $fh_index,"...\n";

     $mv=$files[$fh_index];
     $pmv=$mv;

     $tr=$tdir . "O-" . $k . "-tr-" . $mv;
     $ptr=$ptdir . "O-" . $k . "-tr-" . $mv;

     $mv=$dir . $mv;

     if (!(-e $mv)){
         print "数据文件 文件不存在！";
         exit;
     }

     #---------------------------------------#
     #            初始化模块                 #
     #     进行一些变量的初始化工作          #
     #---------------------------------------#

                 #清空两个表格
     while(($key,$value)=each(%PreTable)){
             delete $PreTable{$key};
     }
     while(($key,$value)=each(%StaTable)){
             delete $StaTable{$key};
     }

     #两个表的关键字
     $PreKey="nullkey";
     $StaKey="nullkey";

     #预测的AP与实际AP
     $PredictAP="nullap";

     #初始化上下文元素（上下文==$line[0].$line[1]...$line[$k-1]）
     for($num=0;$num<$k;$num++)
     {
          $line[$num]="NULL";
     }

     open(fh,$mv) || die "不能打开数据文件！";
     #open(newfh,">$tr");

     $S=0;                         #预测的总次数
     $H=0;                         #预测命中次数
     $AP_Num=0; #记录所处理过的AP的数目,用来保证n值的实现

     #----------------------------------------#
     #             构建M和预测模块            #
     #        一边构建M，一边进行预测。       #
     #----------------------------------------#


     $sn=1;

     while (<fh>) {  # read each line of input

         #-------------------------------------------#
         #              trace文件利用长度限制        #
         #-------------------------------------------#

         if ($AP_Num >=$sn){#根据n值限制使用mv文件的长度
             if ($S!=0){
                 $ratio=$H/$S;
             }else{
                 $ratio=0;
             }
             #print newfh "$AP_Num ";
             #print newfh "$ratio \n" ;

             $PosiCount[$AP_Num]++;
             $AccuSum[$AP_Num]+=$ratio;

             $sn=$sn+$stepLen;
             if ($sn>$n){
                 #goto end;
                 while(<fh>) { ; }
             }
         }


         #-------------------------------------------#
         #              读入新的AP名称               #
         #-------------------------------------------#
         @linedata=split;
         $CurrentAP=$linedata[1];
         $AP_Num++;


         #-------------------------------------------#
         #          预测评估与数据结构更新           #
         #-------------------------------------------#
         #更新状态表
         $StaKey=$PreKey.$CurrentAP;
         if($StaTable{$StaKey}>=1)
         {
               $StaTable{$StaKey}++;
         }
         else
         {
               $StaTable{$StaKey}=1;
         }

         #预测评估
         if ($PredictAP eq $CurrentAP){
              $H++;
         }
         else        #更新预测表
         {
              if($StaTable{$StaKey}>=$StaTable{$PreKey.$PreTable{$PreKey}})
              {
                  $PreTable{$PreKey}=$CurrentAP;
              }
         }
         $S++;


         #-------------------------------------------#
         #        根据当前上下文预测下一跳           #
         #-------------------------------------------#
         #构造当前上下文
         $line[$k]=$CurrentAP;
         for($num=0;$num<$k;$num++)
         {
              $line[$num]=$line[$num+1];
         }
         $PreKey=$line[0];
         for($num=1;$num<$k;$num++)
         {
              $PreKey=$PreKey.$line[$num];
         }

         #获取预测结果
         $PredictAP=$PreTable{$PreKey};
         if($PredictAP eq "")
         {
              $PredictAP="NULL";
         }
     }#end of while (<fh>)
     close(fh);
     #close(newfh);


      #-------------------------------------------#
      #            添加图13对应的数据             #
      #-------------------------------------------#
      $ratio=sprintf("%4.3f",$ratio);
      $TotalCount++;
      if($AccuracyCount{$ratio}<=0)
      {
          $AccuracyCount{$ratio}=1;
      }
      else
      {
          $AccuracyCount{$ratio}+=1;
      }
      for($indx=sprintf("%4.3f",$ratio+0.001);$indx<=1;$indx=sprintf("%4.3f",$indx+=0.001))
      {
          if($AccuracyCount{$indx}<=0)
          {
               $AccuracyCount{$indx}=1;
          }
          else
          {
               $AccuracyCount{$indx}+=1;
          }
      }

}#end of for dir

      #-------------------------------------------#
      #            输出图13对应的数据             #
      #-------------------------------------------#
open(alltracefile,">..\\all\\order-$k-$n-all\.tr");
for($indx=0.000;$indx<=1;$indx=sprintf("%4.3f",$indx+=0.001))
{
    print alltracefile $indx," ",$AccuracyCount{$indx}/$TotalCount,"\n";
}
close(alltracefile);

      #-------------------------------------------#
      #            添加图8+对应的数据             #
      #-------------------------------------------#
open(avgfh,">..\\all\\order-$k-$n-avg\.tr");
for($i=0;$i<=$MAXPOSI;$i+=$ASCNUM)
{
     if($PosiCount[$i]>0)
     {
         print avgfh $i," ",sprintf("%5.4f",$AccuSum[$i]/$PosiCount[$i]),"\n";
     }
}
close(avgfh);