在挖掘频繁遍历路径的算法中,Chen等人提出的最大向前引用方法是最常被采用的,例如IBM公司Watson实验室开发的Speed Tracer就是基于该算法。Chen等人认为,在一般情况下,一个浏览日志数据库,对于经历的每个链接,都包含一个(源路径,目的路径)等。对于新的路径的开始,由于还没有任何以前的浏览,源路径可以认为是空。
生成最大向前路径的算法表示如下:
最大向前路径生成算法:
Input:遍历路径(W1,W2,……Wn)
Output:最大向前路径(FW1,FW2……FWn)
步骤:
i:=1;m:=1;F:=1; backpos:=0; FW1:=W1;
Repeat
  i:=i+1;j:=1;
  while(j=<m)and(wi≠fwi) do j:=j+1;
  if j≤m then backpos:=j;
  if backpos≠0 then
     begin
       if F=1 then output (fw1,fw2,…,fwm) to DB
       m:=backpos; F:=0;
     end
   else
     begin
       m:=m+1;fwm:=wi;
       if F=0  then  F=1;
     end;
until i≥n;
if F=1 then output (fw1,fw2,…,fwm) to DB;
    该算法是由用户会话的遍历路径生成最大向前路径MFP。首先将MFP的第一页放于遍历路径的起始页,并用一标志F表明当前的遍历方向,初始为前进方向。然后顺序检查遍历路径中的每一页,并和MFP中记录的页面比较。若没有相同的,则将该页加入MFP中;若发现了相同的页面,表明该页面为已浏览过且由返回到达的页面。此时有两种情况:
   (1)若标志F为前进方向,则表示一个最大向前路径的终止,此时需要把当前的MFP输出,将F标志记为后退方向,并以返回前首次到达该页面的位置为起点调整MFP并继续生成新的MFP;
   (2)若标志F为后退方向,则表面页面仍处于后退状态,因此不输出MFP,仍将对MFP进行调整。如果在检查完遍历路径后,标志F仍为前进方向,则输出这个时候的MFP。