序列模式挖掘算法BIDE

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class BIDE {
	public List<List<String>> db=new ArrayList<List<String>>();
	public List<Double> sup=new ArrayList<Double>();
	public int mm;
	public void init(){
		try {
			FileInputStream in=new FileInputStream("E:/in中文.txt");
			InputStreamReader fr=new InputStreamReader(in,"utf-8");
			BufferedReader br=new BufferedReader(fr);
			String line=null;
			List<String> tmp=null;
			int count=0;
			String pline=null;
			while((line=br.readLine())!=null){
				line=line.trim();
				System.out.println(line);
			
				if(line.contains("星期")){
					count++;
					if(count==9)
						break;
					 tmp=new ArrayList<String>();
					 db.add(tmp);
					 pline=null;
					 continue;
				}
				if(line.matches("[u4e00-u9fa5]*")){
					continue;
				}
				else {
					if(line!=pline)
					tmp.add(line);
					pline=line;
				System.out.println(line);	
				}
			}
		mm=(int)(count*0.8);
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
public static void main(String[] args){
	BIDE d=new BIDE();
	d.init();
	d.test();
Date st=new Date();
	List<List<String>> ans=d.Bide(d.db,d.mm);
	Date end=new Date();
	String pname=null;
	for(int k=0;k<ans.size();k++){
		List<String> s=ans.get(k);
		pname=null;
		for(int i=0;i<s.size();i++){
			String name=s.get(i);
			System.out.print(name+" ");
			pname=name;
			}
		System.out.print(d.sup.get(k));
		System.out.println("");
	}
	System.out.println("时间："+(end.getTime()-st.getTime()));
}
public List<List<String>> Bide(List<List<String>> sdb,int min_sup){
	
	List<List<String>> fcs =new ArrayList<List<String>>();
	Map<String,Integer> map=getFrequent_1_sequence(min_sup,sdb);
	List<String> F1=new ArrayList<String>();
	for(String s : map.keySet()){
		if(map.get(s)>=min_sup){
			F1.add(s);
		}
	}
	for(String f1 : F1){
		List<Integer> f1db=get_1_sdb(f1,sdb);
System.out.println(f1);
	List<String> pp=new ArrayList<String>();
	pp.add(f1);
	if(!backScan(pp,db)){
		int BEI=getBEI(db,pp);
		dfs(f1db,pp,BEI,min_sup,fcs,map.get(f1));
	}
	}
	return fcs;
}
//dfs-extension
public void dfs(List<Integer> pointer,List<String> prefix,int bei,int min_sup,List<List<String>> fcs,int min){
	System.out.println(">>"+prefix);
	Map<String,Integer> map=getLFI(pointer,min_sup);
	List<String> LFI=new ArrayList<String>();
	for(String s : map.keySet()){
		if(map.get(s)>=min_sup){
			LFI.add(s);
		}
	}
	int size=0;
	for(int i=0;i<pointer.size();i++){
		if(pointer.get(i)<db.get(i).size())
size++;
	}
	int FEI=getFEI(pointer,LFI,size);
	if(bei+FEI==0){
		fcs.add(prefix);
		sup.add(min*1.0/db.size());
	}

	for(String name : LFI){
		List<String> newPrefix=new ArrayList<String>();
		newPrefix.addAll(prefix);
		
		newPrefix.add(name);
		List<Integer> newpdb=getNewPdb(pointer,name);
		
		if(!backScan(newPrefix,db)){
			int BEI=getBEI(db,newPrefix);
			dfs(newpdb,newPrefix,map.get(name)>min?min:map.get(name));
		}
	}
}
//new_pdb
public List<Integer> getNewPdb(List<Integer> pointer,String name){
	List<Integer> result=new ArrayList<Integer>();
	result.addAll(pointer);
	for(int i=0;i<db.size();i++){
		List<String> ll=db.get(i);
		int flag=0;
		for(int j=pointer.get(i);j<ll.size();j++){
			if(ll.get(j).equals(name)){
				result.set(i,j+1);
				flag=1;
			break;
			}
		}
		if(flag==0)
			result.set(i,ll.size()+1);
	}
	return result;	
}
//forward -extension count
public int getFEI(List<Integer> pointer,List<String> lfi,int size){
	int count=0;
	Map<String,Integer> map=new HashMap<String,Integer>();
	Map<String,Integer> tmap=new HashMap<String,Integer>();
	String name=null;
	for(int i=0;i<db.size();i++){
		tmap.clear();
		List<String> ll=db.get(i);
		for(int j=pointer.get(i);j<ll.size();j++){
			name=ll.get(j);
			if(tmap.get(name)==null){
				map.put(name,map.get(name)==null?1:map.get(name)+1);
				tmap.put(name,1);
			}
		}
	}
	for(String name1 : map.keySet()){
		if(map.get(name1).equals(size))
			count++;
	}
	return count;
}
//local-frequent-items
public Map<String,Integer> getLFI(List<Integer> pointer,int min_sup){
	Map<String,Integer>();
	List<String> result=new ArrayList<String>();
	String name=null;
	for(int i=0;i<db.size();i++){
		tmap.clear();
		List<String> ll=db.get(i);
		for(int j=pointer.get(i);j<ll.size();j++){
			name=ll.get(j);
			if(tmap.get(name)==null){
				map.put(name,1);
			}
		}
	}
	return map;
}
//Backward-extention event count
public int getBEI(List<List<String>> sdb,List<String> prefix){
	int count=0;
	List<List<String>> result=new ArrayList<List<String>>();
	for(int i=1;i<=prefix.size();i++){
		result.clear();
		int flag=0;
		for(List<String> list : sdb){
			List<String> tmp=getmp(list,prefix,i);
			if(tmp==null){
				flag=1;
				break;
			}
			result.add(tmp);
		}
		Map<String,Integer>();
			Map<String,Integer>();
			System.out.println("flag:"+flag);
		if(flag==0){
			for(List<String> ll : result){
				tmap.clear();
				for(String name : ll){
					if(tmap.get(name)==null){
						map.put(name,map.get(name)==null?1:map.get(name)+1);
						tmap.put(name,1);
					}
				}
			}
			for(String s : map.keySet()){
				if(map.get(s).equals(sdb.size())){
					count++;
			
				}
				break;
			}
		}
	
	}
	return count;
}
//last_in_last
public int getLIL(List<String> list,int index){
	int i=0,j=0;
	int ll=-1;
	while(i<list.size()&&j<prefix.size()){
		if(list.get(i).equals(prefix.get(j))&&j<prefix.size()-1){
			i++;j++;
		}else if(list.get(i).equals(prefix.get(j))){
			i++;ll=i;
		}else
			i++;	
	}
	if(ll==-1)
		return -1;
	int ans=0;
	for(int k=0;k<ll;k++)
	if(prefix.get(index-1).equals(list.get(k))&&index-1<prefix.size()-1){
		for(int r=k+1;r<ll;r++){
			if(list.get(r).equals(prefix.get(index))){
				ans=k;
				break;
			}
		}
		
	}
		else if(prefix.get(index-1).equals(list.get(k)))
			ans=k;
	return ans;
	}
//test
public void test(){
	List<String> list=new ArrayList<String>();
	list.add("0");
	list.add("1");
	list.add("2");
	list.add("3");
	List<String> p=new ArrayList<String>();
	p.add("1");
	int end=getLIF(list,p,1);
	List<String> s=getsemi(list,1);
	System.out.println(s);
	System.out.println(end);
}
//i-th maximum period of a prefix
public List<String> getmp(List<String> list,int index){
	if(index==1){
		int end=getLIL(list,1);
		if(end==-1||end==0)
			return null;
		else
			return list.subList(0,end); 
	}
	else{
		int i=0,j=0;
		while(i<list.size()&&j<index-1){
			if(list.get(i).equals(prefix.get(j))){
				i++;j++;
			}else
				i++;
		}
		if(j!=index-1)
			return null;
		int end=getLIL(list,index);
		int start=i-1;
		if(end>start)
			return list.subList(start+1,end);
		else
			return null;
	}
}
//space prune
public boolean backScan(List<String> prefix,List<List<String>> f1db){
boolean ans=false;
List<List<String>> result=new ArrayList<List<String>>();
	for(int i=1;i<=prefix.size();i++){
		result.clear();
		int flag=0;
		for(List<String> list : f1db){
			List<String> tmp=getsemi(list,i);
			if(tmp==null){
				
				flag=1;
				break;
			}
		result.add(tmp);	
		}
		if(flag==0){
			
			Map<String,Integer>();
			for(List<String> ll : result){
				tmap.clear();
				for(String name : ll){
					if(tmap.get(name)==null){
						tmap.put(name,1);
						map.put(name,map.get(name)==null?1:map.get(name)+1);
					}
				}
			}
			Set<String> set=map.keySet();
			for(String s : set){
				if(map.get(s).equals(result.size())){
					return true;
					}
			}
		}
	}
	return false;
} 
// last-in-first
public int getLIF(List<String> list,int index){
	
	int i=0,j=0;
	while(i<list.size()&&j<prefix.size()){
		if(list.get(i).equals(prefix.get(j))){
			i++;j++;
		}else
			i++;
		
	}
	
	if(j!=prefix.size())
		return -1;
	int ans=0;

for(int k=0;k<i;k++){
	if(list.get(k).equals(prefix.get(index-1))&&index-1!=j-1){
		for(int r=k+1;r<i;r++)
			if(list.get(r).equals(prefix.get(index))){
				ans=k;
				break;
			}
	}
	else if(list.get(k).equals(prefix.get(index-1)))
		ans=k;
		
}
return ans;
}
//i-th semi-maximum period of a prefix sequence
public List<String> getsemi(List<String> list,int index){
	if(index==1){
		int end=getLIF(list,1);
		
		if(end>0){
			return list.subList(0,end);
		}
		else
			return null;
	}
	else{
	int i=0,j=0;
	while(i<list.size()&&j<index-1){
		if(list.get(i).equals(prefix.get(j))){
			i++;j++;
		}else{
			i++;
		}
	}
	if(j!=index-1)
		return null;
	int start=i-1;
	int end=getLIF(list,index);
if(end>start)
	return list.subList(start+1,end);
return null;}
}
public List<Integer> get_1_sdb(String prefix,List<List<String>> sdb){
	List<Integer> result=new ArrayList<Integer>();
	for(int i=0;i<db.size();i++)
		result.add(0);
	for(int i=0;i<sdb.size();i++){
		List<String> ll=sdb.get(i);
		int flag=0;
		for(int j=0;j<ll.size();j++){
			if(ll.get(j).equals(prefix)){
				result.set(i,ll.size()+1);
	}
	return result;
}
public Map<String,Integer> getFrequent_1_sequence(int min,List<List<String>> sdb){
	Map<String,Integer>();
	for(List<String> list : sdb){
		tmap.clear();
		for(String name : list){
			if(tmap.get(name)==null){
				tmap.put(name,1);
				map.put(name,map.get(name)==null?1:map.get(name)+1);
			}
		}
	}
	return map;
}
}