java

多模式匹配 WM 算法

算法其实不是很难,但是算法是通过数学模型描述的,不是很好理解哦.个人认为在多模式匹配中该算法的整体性能优于自动机算法,特别是在模式比较多的时候.再者就是自动机巨耗内存,而且启动很慢,最重要的速度本人也觉的,没有WM 算法快.本算法不提供原代码.
WM 算法的基本思想如下：假设模式的长度为m。我们比较tm（文本的第m个字符）和模式的最后一个字符。如果不匹配的话，那么我们根据tm在模式中的最右出现来决定移动的距离。例如，如果tm在模式中没有出现，我们可以安全地移动m个字符并且查看t2m；如果tm和模式的第4个字符匹配，我们可以移动m-4，依此类推。在自然语言文本中，移动的距离为m或接近m的情况会经常发生。然而，对于多模匹配，会出现文本的多个字符和和一些模式的最后一个字符匹配的情况。我们要证明怎样克服这个问题并保持WM算法的精华（速度）

第一个阶段是预处理模式集合。在这个阶段我们建立三张表，移动表 (SHIFT table)、哈希表（HASH table）、前缀表（PREFIX table）。移动表和WM算法的类似，但不完全相同。它用来决定当文本被扫描的时候，文本中的多少个字符可以被移动（跳过）。哈希表和前缀表是移动值为 0时被使用的。他们用来决定哪个模式是匹配的后选，并验证匹配。

我们做的第一件事情就是计算每个模式的最小长度，称为m，并且只考虑每个模式的头m个字符。换句话说，我们强加一个要求：所有的模式都具有相同的长度。这个要求对算法的效率是至关重要的。假设其中一个模式非常的短，长度仅为 2，那我们移动的距离就不可能超过2，所以短模式会使算法的效率降低。

移动表的建立

我们考虑一块大小为B的字符串，而不是一个一个地查看文本的字符。设M为所有模式的总的大小，M=k*m，设c为字母表的大小。一个好的B的取值应该是logc2M；实际上，我们取B= 2或B=3。这里的移动表和正常的BM算法的移动表（SHIFT TABLE）起相同的作用，除此之外它还决定最后B个字符的移动而不是仅仅一个字符。例如，如果文本中一个有B个字符的字符串并不出现在任何模式中，那么我们可以移动m-B+1个字符。我们假设现在移动表为每个可能的大小为B的字符串都包含一个入口，那么它的大小应为|∑|B。（实际上我们使用一个压缩的表把一些字符串匹配到相同的入口以节省空间。）每个大小为B的字符串匹配一个整数作为移动表的索引。这些值决定了当我们扫描文本时我们能向前移动多远。设 X=x1…xB为我们当前正在扫描的文本中的B个字符，假设X和移动表的第i个入口匹配。这里有两种情况：

1、X和任何模式中的子串都不匹配

在这种情况下，我们可以移动文本的m-B+1个字符。任何小一点的移动都会使文本的后B个字符和其中一个模式的子串不匹配。所以我们记录移动表SHIFT[i]的值为m-B+1。

2、X出现在一些模式中

在这种情况下，我们找出X在所有模式中的最右出现。我们假设X在模式Pj的位置q处结束，并且X并不结束在任何其他模式中比q大的位置。我们记录SHIFT [i]的值为m-q。为了记录移动表的值，我们单独地考虑每个模式pi=a1a2…am。我们匹配pi的每个大小为B的子串aj-B+1…aj到移动表，并且设置相应的值为当前的最小值（所有的初始值都为m-B+1）和m-j(到达这个子串需要移动的距离 )。移动表的值是可以移动的最大安全值。把移动表的任何入口替换为小一点的值会使移动距离变短而花费更多的时间。但是这样会更安全：没有匹配会被错过。所以我们使用一个压缩的表，把一些字符串匹配到相同的入口只要我们设置他们的最小移动为相同的值。在我们的算法中采用了两种方法。当模式的数量少时，我们选取B=2，并且使用精确的移动表；否则，我们选取B=3并且使用压缩的移动表

哈希表的建立

只要移动的距离大于0，我们就能安全地移动并继续扫描。这是大多数时间发生的情况。（在一个典型的例子中，对于100个模式5%的时间移动值为0，1000个模式27%的时间移动值为0，5000个模式53%的时间。）否则，文本中当前的子串和模式中的一些模式匹配。但是是哪个模式呢？为了避免和每个模式的子串都进行比较，我们使用哈希的技术来最小化需要比较的数量。我们已经计算了B个字符的一个整数匹配值用做移动表的索引。我们使用相同的整数值作为令一个表的索引，称为哈希表。哈希表的第i个入口HASH[i]，包含一个指针指向最后B个字符的哈希值为i的模式链表。这样哈希表的大小会小的多，因为它只包含一些模式，而移动表包含所有大小为B的可能的字符串。设h为当前文本后缀的哈希值，假设SHIFT[h]=0。HASH[h]的值是一个指针p同时指向两个单独的表：我们把模式的指针链表记为PAT_POINT，根据每个模式的后B个字符的哈希值来分类。指针p指向哈希值为h的模式链表的开头。为了发现这个链表的结尾，我们增加这个指针直到它的值等于HASH[h+1]（因为整个链表是根据哈希值来分类的）。例如，如果SHIFT[h]≠0，则HASH[h]=HASH[h+ 1](因为没有一个模式的后缀的哈希值为h)。

前缀表的建立

除此之外，我们记录一张前缀表称为PREFIX，下面我们简要地描述一下。 自然语言文本并不是随意的。例如，后缀“ion”或者“ing”是英文中非常常见的。这些后缀不会经常在文本中出现，但是它们很可能在一些文本中出现。它们会引起哈希表的冲突；也就是，所有的有相同后缀的模式在哈希表中有相同的入口。当我们遇到文本中这样一个后缀时，我们发现SHIFT值为0（假设它是一些模式的后缀），我们不得不单独检查所有带有这个后缀的模式看它是否和文本匹配。为了加速这个过程，我们引进另一张表，称为前缀表。除了匹配所有模式的后 B个字符，我们也匹配前缀表中的所有模式的头B’个字符。B’的最佳值为2。当我们发现一个移动值为0时，我们就转向哈希表决定是否存在一个匹配，我们检查前缀表的值。哈希表不仅包括，对每个后缀来说，含有这个后缀的所有模式链表，它也包括它们的前缀。我们计算文本的前缀（通过把文本向左移动m-B’个字符得到）并利用它来过滤那些后缀相同但是前缀不同的模式。这是一个有效的方法。因为很少出现这种情况：不同的模式有相同的后缀和相同的前缀。而且计算哈希值的额外的工作量只有移动值经常为0时才大一些。预处理过程看起来比较复杂，实际上做起来非常快。在我们的实验中，我们

扫描过程

算法的主循环包括以下几个步骤：
1、计算文本当前被扫描的B个字符的哈希值h(从tm-B+1…tm).
2、检查SHIFT[h]的值：如果>0，移动文本并转到步骤1；否则，转到步骤3
3、计算文本前缀的哈希值（从当前的位置向左m个字符），称为text_prefix.
4、检查每一个满足HASH[h]≤p<HASH[h+1]的模式p，并且当PREFIX[p]=text_pattern时，按照文本检查实际的模式（由PAT_POINT[p]给出）。

算法的主循环部分如下：

while (text <= textend) /* text指向文本当前被扫描的位置，如果*text不是文本的随后一个字符*/
{
h = (*text<用哈希功能给文本当前被扫描的B个字符匹配一个整数值作为入口，令Hbits=5*/
if (Long) h = (h< 当模式数量≥400且每个模式的长度≥2时，令Long=1，并令B=3 */
shift = SHIFT[h]; /* 我们使用的移动表大小为215 = 32768 */
if (shift == 0) /* 如果移动值为0 *
{
text_prefix = (*(text-m+1)<<8) + *(text-m+2); /* 计算当前被扫描文本的前缀值*/
p = HASH[h]; /*p指针指向后B个字符的哈希值为h的模式链表的开头*/
p_end = HASH[h+1];
while (p++ < p_end)
{ /*在具有相同哈希值的模式链表中循环*/
if(text_prefix != PREFIX[p]) continue;
px = PAT_POINT[p];
qx = text-m+1;
while (*(px++) == *(qx++)); /* 直接按照文本检查每个模式*/
if (*(px-1) == 0) { /* 0表明到了字符串的末尾*/
report a match /*报告发现了一个匹配*/
}
shift = 1;
}
text += shift;
}

WM多模匹配算法的分析

下面我们将证明该算法期望的运行时间小于线性时间。设N是文本的大小，P是模式的数量，m是每个模式的长度，M = m* P是所有模式的大小，假设N≥M，设C是字母表的大小，取B=logc2M。移动表包含了所有可能的大小为B的字符串。所以在移动表中有cb= clogc2M≤2Mc个入口。移动表的构造时间为O(M)，因为任何模式的每个大小为B的子串只被考虑一次，所以它平均消耗的是常数时间。我们把扫描时间分两种情况。第一种情况假设移动值非0；在这种情况下继续移动，在文本的那个位置上并不需要做额外的工作。第二种情况，假设移动值为0，在这种情况下，我们需要读入更多的模式和文本并查询哈希表。我们首先要证明下面一个引理：
引理 一个任意的大小为B的字符串的匹配一个移动值i（0≤i≤m-B+1）的概率≤1/2m
证明：对于所有的0≤i≤m-B+1。至多P=M/m个字符串匹配一个移动值i。但是所有的可能的大小为B的字符串最少有2M个。所以一个任意的大小为B的字符串匹配到一个移动值i的概率≤1/2m。对于移动值为0的情况亦真。
上面这个引理表明了一个移动的期待值≥m/2。因为计算一个哈希值需要花费的时间为O(B)，所有非0移动花费的时间为O(BN/m)。移动为0的工作量也是O(B)，除非存在一个匹配时，需要检查整个模式，花费的时间为O(m)。因为移动值为0的情况发生的概率≤1/2m(由上述的引理)，整个扫描过程花费的时间是O(BN/m)。
综上所述，该算法总的运行时间为O(M)+ O(BN/m)=O(mp)+ O(BN/m)。

 

 

 

以下为完整代码：

 

package com.test;

import java.util.Vector;

public class WmParser {
WmParser(){}
private boolean initFlag=false;
private UnionPatternSet unionPatternSet=new UnionPatternSet();
private int maxIndex=(int) java.lang.Math.pow(2,16);
private int shiftTable[]=new int[maxIndex];
public Vector<AtomicPattern>hashTable[]=new Vector[maxIndex];
private UnionPatternSet tmpUnionPatternSet=new UnionPatternSet();
public static void main(String args[]){
WmParser filterEngine=new WmParser();
filterEngine.AddFilterKeyWord("aaa bbb", 1);
filterEngine.AddFilterKeyWord("aaa bbb", 1);
filterEngine.AddFilterKeyWord("你好 我好 大家好", 1);
Vector<Integer>levelSet=new Vector<Integer>();
filterEngine.Parse("你好风大卡我好发电量撒大家好", levelSet);
System.out.println("levelSet.size="+levelSet.size());

levelSet.clear();
filterEngine.Parse("aa×a ×b×bb", levelSet);
System.out.println("levelSet.size="+levelSet.size());

filterEngine.clear();
levelSet.clear();
filterEngine.Parse("你好风大卡我好发电量撒大家好", levelSet);
System.out.println("levelSet.size="+levelSet.size());
}
private boolean AddFilterKeyWord(String keyWord,int level){
if(initFlag==true)return false;
UnionPattern unionPattern=new UnionPattern();
String strArray[]=keyWord.split(" ");
for(int i=0;i<strArray.length;i++){
Pattern pattern=new Pattern(strArray[i]);
AtomicPattern atomicPattern=new AtomicPattern(pattern);
unionPattern.addNewAtomicPattrn(atomicPattern);
unionPattern.setLevel(level);
atomicPattern.setBelongUnionPattern(unionPattern);
}
tmpUnionPatternSet.addNewUnionPattrn(unionPattern);
return true;
}
private boolean isValidChar(char ch){
if((ch >='0'&&ch<='9')||(ch >='A'&&ch<='Z')||(ch>='a'&&ch<='z'))return true;
if((ch>=0x4e00&&ch<= 0x7fff)||(ch>=0x8000&&ch<=0x952f)) return true;
return false;
}
public int Parse(String content, Vector<Integer>levelSet){
if(initFlag==false)init();
Vector<AtomicPattern> aps=new Vector<AtomicPattern>();
String preContent=preConvert(content);
for(int i=0;i<preContent.length();){
char checkChar=preContent.charAt(i);
if(shiftTable[checkChar]==0){
Vector<AtomicPattern> tmpAps=new Vector<AtomicPattern>();
tmpAps=findMathAps(preContent.substring(0,i+1),hashTable[checkChar]);
aps.addAll(tmpAps);
i++;
}else i=i+shiftTable[checkChar];
}
parseAtomicPatternSet(aps,levelSet);
return 0;
}
private void parseAtomicPatternSet(Vector<AtomicPattern> aps,Vector<Integer>levelSet)
{
while(aps.size()>0)
{
AtomicPattern ap=aps.get(0);
UnionPattern up=ap.belongUnionPattern;
if(up.isIncludeAllAp(aps)==true){
levelSet.add(new Integer(up.getLevel()));
}
aps.remove(0);
}
}
private Vector<AtomicPattern>findMathAps(String src, Vector<AtomicPattern>destAps)
{
Vector<AtomicPattern> aps=new Vector<AtomicPattern>();
for(int i=0;i<destAps.size();i++)
{
AtomicPattern ap=destAps.get(i);
if(ap.findMatchInString(src)==true)aps.add(ap);
}
return aps;
}
private String preConvert(String content)
{
String retStr=new String();
for(int i=0;i<content.length();i++)
{
char ch=content.charAt(i);
if(this.isValidChar(ch)==true){
retStr=retStr+ch;
}
}
return retStr;
}
//shift table and hash table of initialize
private void init(){
initFlag=true;
for(int i=0;i<maxIndex;i++)hashTable[i]=new Vector<AtomicPattern>();
shiftTableInit();
hashTableInit();
}
public void clear()
{
tmpUnionPatternSet.clear();
initFlag=false;
}
private void shiftTableInit()
{
for(int i=0;i<maxIndex;i++)shiftTable[i]=2;
Vector<UnionPattern> upSet=tmpUnionPatternSet.getSet();
for(int i=0;i<upSet.size();i++){
Vector<AtomicPattern> apSet=upSet.get(i).getSet();
for(int j=0;j<apSet.size();j++)
{
AtomicPattern ap=apSet.get(j);
Pattern pattern=ap.getPattern();
if(pattern.charAtEnd(1)!=0)shiftTable[pattern.charAtEnd(1)]=1;
if(pattern.charAtEnd(0)!=0)shiftTable[pattern.charAtEnd(0)]=0;
}
}
}
private void hashTableInit()
{
Vector<UnionPattern> upSet=tmpUnionPatternSet.getSet();
for(int i=0;i<upSet.size();i++){
Vector<AtomicPattern> apSet=upSet.get(i).getSet();
for(int j=0;j<apSet.size();j++)
{
AtomicPattern ap=apSet.get(j);
Pattern pattern=ap.getPattern();
if(pattern.charAtEnd(0)!=0){
hashTable[pattern.charAtEnd(0)].add(ap);
}
}
}
}
}
class Pattern{ //string
Pattern(String str){this.str=str;}
public char charAtEnd(int index){
if(str.length()>index){
return str.charAt(str.length()-index-1);
}
else return 0;
}
public String str;
public String getStr(){return str;};
}
class AtomicPattern{
public boolean findMatchInString(String str){
if(this.pattern.str.length()>str.length())return false;
int beginIndex=str.length()-this.pattern.str.length();
String eqaulLengthStr=str.substring(beginIndex);
if(this.pattern.str.equalsIgnoreCase(eqaulLengthStr))return true;
return false;
}
AtomicPattern(Pattern pattern){this.pattern=pattern;};
private Pattern pattern;
public UnionPattern belongUnionPattern;
public UnionPattern getBelongUnionPattern() {
return belongUnionPattern;
}
public void setBelongUnionPattern(UnionPattern belongUnionPattern) {
this.belongUnionPattern = belongUnionPattern;
}
public Pattern getPattern() {
return pattern;
}
public void setPattern(Pattern pattern) {
this.pattern = pattern;
}
}
class SameAtomicPatternSet{
SameAtomicPatternSet(){SAPS=new Vector<AtomicPattern>();};
public Vector<AtomicPattern>SAPS;
}
class UnionPattern{ //union string
UnionPattern(){this.apSet=new Vector<AtomicPattern>();}
public Vector<AtomicPattern> apSet;
public void addNewAtomicPattrn(AtomicPattern ap){this.apSet.add(ap);}
public Vector<AtomicPattern> getSet(){return apSet;}
public boolean isIncludeAllAp(Vector<AtomicPattern> inAps){
if(apSet.size()>inAps.size())return false;
for(int i=0;i<apSet.size();i++)
{
AtomicPattern ap=apSet.get(i);
if(isInAps(ap,inAps)==false)return false;
}
return true;
}
private boolean isInAps(AtomicPattern ap,Vector<AtomicPattern> inAps){
for(int i=0;i<inAps.size();i++)
{
AtomicPattern destAp=inAps.get(i);
if(ap.getPattern().str.equalsIgnoreCase(destAp.getPattern().str)==true)return true;
}
return false;
}
public void setLevel(int level){this.level=level;}
public int getLevel(){return this.level;}
private int level;
}
class UnionPatternSet{ //union string set
UnionPatternSet(){this.unionPatternSet=new Vector<UnionPattern>();}
public void addNewUnionPattrn(UnionPattern up){this.unionPatternSet.add(up);}
public Vector<UnionPattern> unionPatternSet;
public Vector<UnionPattern> getSet(){return unionPatternSet;}
public void clear(){unionPatternSet.clear();}
}