下载文档原格式
wm算法 java实现一、引言wm算法（Wagner-Fisher algorithm）是一种常用的字符串匹配算法，用于计算两个字符串之间的编辑距离（edit distance）。
编辑距离是指将一个字符串转换成另一个字符串所需的最少操作次数，操作包括插入、删除和替换字符。
wm算法通过动态规划的方式，计算出两个字符串之间的编辑距离，并可以根据需要获取具体的编辑操作序列。
二、算法原理wm算法的核心思想是将两个字符串进行逐个字符的比较，并计算出字符之间的编辑代价，然后根据代价的大小进行相应的操作。
具体步骤如下：1. 初始化一个二维数组dp，dp[i][j]表示字符串s1的前i个字符与字符串s2的前j个字符之间的编辑距离。
2. 初始化边界条件，即当i=0时，dp[0][j]等于j，表示将s1的空字符串转换成s2的前j个字符所需的操作次数；当j=0时，dp[i][0]等于i，表示将s2的空字符串转换成s1的前i个字符所需的操作次数。
3. 遍历字符串s1和s2的所有字符，计算dp[i][j]：- 当s1的第i个字符等于s2的第j个字符时，dp[i][j]等于dp[i-1][j-1]，表示不需要进行修改操作；- 当s1的第i个字符不等于s2的第j个字符时，dp[i][j]等于dp[i-1][j-1]+1，表示需要进行替换操作；- dp[i][j]还可能等于dp[i-1][j]+1（表示删除操作）或dp[i][j-1]+1（表示插入操作），取其中的最小值。
4. 最终dp[m][n]即为字符串s1和s2之间的编辑距离，其中m和n分别为字符串s1和s2的长度。
三、Java实现下面是wm算法的Java实现代码示例：```public class WmAlgorithm {public static int getEditDistance(String s1, String s2) {int m = s1.length();int n = s2.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {dp[i][0] = i;}for (int j = 0; j <= n; j++) {dp[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1.charAt(i - 1) == s2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];} else {int replace = dp[i - 1][j - 1] + 1;int delete = dp[i - 1][j] + 1;int insert = dp[i][j - 1] + 1;dp[i][j] = Math.min(replace, Math.min(delete, insert));}}}return dp[m][n];}public static void main(String[] args) {String s1 = "kitten";String s2 = "sitting";int editDistance = getEditDistance(s1, s2);System.out.println("编辑距离为：" + editDistance);}}```以上代码中，getEditDistance方法接收两个字符串s1和s2作为参数，并返回它们之间的编辑距离。
wm_concat date变科学计数法-回复什么是科学计数法？科学计数法（Scientific Notation），也被称为标准形式，是一种用于表示非常大或非常小的数字的方法。
它以10的幂的形式表示，其中基数在1和10之间，而指数被称为这个数字所移动的位数。
科学计数法的目的是使大量或小量的数值更易读和理解。
为什么要使用科学计数法？使用科学计数法有许多好处。
首先，它可以减少数字的位数，使其更易读。
例如，1,000,000可以简化为1 x 10^6，只用3个字符就能表示，而不是7个。
其次，科学计数法可以方便地进行大量和小量之间的比较。
例如，1 x 10^9和1 x 10^12之间的数量级差异很大，而在科学计数法中，可以轻松地进行比较和理解。
此外，在科学领域，科学计数法可以更方便地表示微观和宏观领域的数值，如原子和星系的数量。
如何将数字转换为科学计数法？将数字转换为科学计数法需要以下步骤：1. 确定一个数值，然后确定基数（介于1和10之间）和指数（表示数字的位移）。
2. 将数值中的小数点向左移动或向右移动，直到小数点位于非零第一位之后，形成一个数字介于1和10之间的值。
3. 计算移动过程中小数点的位数，并将其作为指数的绝对值。
4. 根据移动方向来确定指数的正负。
如果小数点向左移动，指数为正数；如果小数点向右移动，指数为负数。
5. 用基数和指数的形式表示原始的数值。
举例说明：假设要将2,540,000转换为科学计数法。
1. 确定数值为2.54，并确定基数介于1和10之间。
2. 将小数点向左移动6位，直到小数点位于非零第一位之后，得到2.54的值。
3. 移动过程中小数点的位数为6，作为指数的绝对值。
4. 小数点向左移动，因此指数为正数，即6。
5. 使用基数和指数的形式表示原始的数值，即2.54 x 10^6，结果就是2,540,000的科学计数法表示。
科学计数法在科学研究、工程领域、天文学和物理学等领域中具有重要的应用。
互联网广告综述之点击率预测系统(Logistic Regression)点击率预测是互联网广告业内普遍认可的评估流量质量的方法。
DSP 方可以在投放广告之前，借助点击率预测判断SSP 的请求广告是否满足不同广告主的投放需求（有些广告主能接受一定的单价要求一定的点击次数，有些广告主要求一定广告费内用获取一定的交互次数），从而达到优化广告，提高广告效益的目的。
从数据的角度，广告点击率的预估实际上是使用广告数据和用户数据的一次模型运算。
一般情况下不同类型的用户对某广告类型的点击率与最终是否点击的呈线性回归表示，故CTR 预测使用的逻辑算法的进行评估：z =w 0+w 1∗x 1+w 2∗x 2+⋯+w m ∗x mx 1、x 2、x 3……x m 是每个样本的m 个特征，w 0、w 1、w 2……w m 为每个特征值的权重。
按照sigmoid 函数形式求出：g (z )=1/(1+e −z )sigmoid 函数定义域（-INF,INF ）而值域在（0,1）之间，方便逻辑回归函数对两分类的目标值进行分类。
P =π(x)=1/(1+e −z )将sigmoid 函数可以看作样本的概率密度函数，每个样本点可以通过sigmoid 函数求出对应的概率。
那么权重W 0、W 1、W 2……W m 则需要最大似然率（MLE ）和优化算法来求出。
L (β)=∏π(x )y i mi=0π(x)1−y i上述为最大似然率公式，对其求导则可以得到：∑[y i −π(x i )]=∑[y i −e β0+β1x 1……βm x m 1+e β0+β1x 1……βm x m ]ni=1n i=1=0 ∑x ij [y i −π(x i )]=∑[y i −e β0+β1x 1……βm x m 1+e β0+β1x 1……βm x m ]ni=1n i=1=0 J=1,2,3,……p----p 为独立向量个数。
上式称为似然方程。
WM算法详解WM算法采用字符块技术，增大了主串和模式串不匹配的可能性,从而增加了直接跳跃的机会。
使用散列表选择模式串集合中的一个子集与当前文本进行完全匹配。
使用前缀表进一步过滤不匹配的模式串，使算法获得了较高的运行效率。
WM算法首先对模式串集合进行预处理。
预处理阶段将建立3个表格：SHIFT表，HASH 表和PREFIX表。
SHIFT表用于在扫描文本串的时候，根据读入字符串决定可以跳过的字符数，如果相应的跳跃值为0，则说明可能产生匹配。
HASH表用来存储尾块字符散列值相同的模式串。
PREFIX表用于存储尾块字符散列值相同的模式串的首块字符散列值。
假设模式串集合P中最短的模式长度为m，那么，后续仅考虑所有模式的前m个字符组成的模式串。
设X=x1…xB为T中的待比较的长度为B的子串，通过hash函数映像得到一个索引值index，以该索引值作为偏移得到SHIFT表中的值，该值决定读到当前子串x后可以跳过的位数。
假设X映射到SHIFT表的入口为index的表项，即index=hash(x)。
SHIFT表中值的计算原则为：（1）如果X不出现在模式串中，则SHIFT[h]=m-B+1。
（2）如果X出现在某些模式串中，而且在所有的模式串中的最右出现位置为q，则SHIFT[h]=m-q。
算法匹配的大致原理：（1）设当前比较的文本串X的hash值为h。
如果SHIFT[h]=0，说明可能产生了匹配，那么需要进一步的判断。
（2）用该h值作为索引，查HASH表找到HASH[h]，它存储的是指标，指向两个单独的表：一个是模式链表，另一个是PREFIX表。
模式链表中存放的是后B个字符的hash值同为h的所有模式。
（3）对于待比较长度为m的串，如果其长度为B的前缀与模式的前缀的hash值也相同，则再将相应的文本串与符合的模式逐一进行比较，最终判定是否完全匹配。
算法匹配的主要过程：基于后缀的模式匹配，每次扫描B个字符T[m-B+1]…..T[m]。
（1）扫描text的末B位T[m-B+1]…..T[m]通过hash function计算其哈希值h。
（2）查表，SHIFT[h]>0，text小指针后滑SHIFT[h]位，执行（1）；SHIFT[h]=0，执行那个（3）。
（3）计算此m位text的前缀的哈希值，记为text_prefix。
（4）对于每个p（HASH[h]≦p<HASH[h+1]），看是否PREFIX[p]=text_prefix。
（5）如果相等，让真正的模式串去和text匹配。
WM算法的代码网上已经有了，下面给出其中的一个参考：/index.php/post/1338.html这段代码对于初学者可能还是比较的晦涩，下面给出对这份代码的详细注释以及流程图。
首先给出的是对代码的详细注释：#ifndef WM_H#define WM_H#include <stdio.h>#include <stdlib.h>#include <string.h>#define HASHTABLESIZE (256*256)#define MAXLEN 256typedef struct wm_pattern_struct//每个模式串的结构{struct wm_pattern_struct *next;//指向下一个模式串unsigned char *psPat; //pattern array//模式串数组unsigned psLen; //length of pattern in bytes//模式串的长度}WM_PATTERN_STRUCT;#define HASH_TYPE short#define SHIFTTABLESIZE (256*256)typedef struct wm_struct//模式串集的结构{WM_PATTERN_STRUCT *plist; //pattern list//模式串列表WM_PATTERN_STRUCT *msPatArray; //array of patterns//模式串转变为WM_PATTERN_STRUCT后的结构unsigned short *msNumArray; //array of group counts, # of patterns in each hash group int msNumPatterns; //number of patterns loaded//模式串的个数unsigned msNumHashEntries;//HASH表的大小HASH_TYPE *msHash; //last 2 characters pattern hash table//HASH表unsigned char* msShift; //bad word shift table//SHIFT表HASH_TYPE *msPrefix; //first 2 characters prefix table//PREFIX表int msSmallest; //shortest length of all patterns//最短模式串的长度}WM_STRUCT;WM_STRUCT * wmNew();void wmFree(WM_STRUCT *ps);int wmAddPattern(WM_STRUCT *ps,unsignedchar *P,int m);int wmPrepPatterns(WM_STRUCT *ps);void wmSearch(WM_STRUCT *ps,unsigned char*Tx,int n);#endifWM.c文件如下：view plaincopy toclipboardprint?#include <stdio.h>#include <string.h>#include <stdlib.h>#include <ctype.h>#include "wm.h"extern int nline=1;extern int nfound=0;#define MAXN 10001 //模式串的最大长度MAXN –1#define MAXM 51//单词最大长度为MAXM –1 WM_STRUCT * wmNew(){WM_STRUCT *p=(WM_STRUCT *)malloc(sizeof (WM_STRUCT));if(!p) return 0;p->msNumPatterns=0;p->msSmallest=1000;return p;}void wmFree(WM_STRUCT *ps){if(ps->msPatArray){if(ps->msPatArray->psPat) free(ps->msPatArray->psPat);free(ps->msPatArray );}if(ps->msNumArray) free(ps->msNumArray); if(ps->msHash) free(ps->msHash);if(ps->msPrefix) free(ps->msPrefix);if(ps->msShift) free(ps->msShift);free(ps);}int wmAddPattern(WM_STRUCT *ps,unsigned char *q,int m)//m字符串长度，模式串转变为WM_STRUCT结构{/>WM_PATTERN_STRUCT *p;p=(WM_PATTERN_STRUCT *)malloc(sizeof (WM_PATTERN_STRUCT));if(!p) return -1;p->psPat=(unsigned char*)malloc(m+1);memset(p->psPat+m,0,1); //模式串最后一位位0，结束标志memcpy(p->psPat,q,m);p->psLen=m;ps->msNumPatterns++;if(p->psLen<(unsigned)ps->msSmallest) ps->msSmallest=p->psLen;p->next=ps->plist; 有点从后往前插入链表的感觉ps->plist=p;return 0;}static unsigned HASH16(unsigned char *T){return (unsigned short) (((*T)<<8) | *(T+1));}void sort(WM_STRUCT *ps)//字符串哈希值从小到大排列{int m=ps->msSmallest;int i,j;unsigned char *temp;int flag; //该值的作用是，当某一时刻的序列已经从小到大排列时，就无须再进行扫描了for(i=ps->msNumPatterns-1,flag=1;i>0 &&flag;i–) //以下为冒泡排序算法{flag=0;for(j=0;j<i;j++){if(HASH16(&(ps->msPatArray[j+1].psPat[m-2]))<HASH16(&(ps->msPatArray[j].psPat[m-2]))) {flag=1;temp=ps->msPatArray[j+1].psPat;ps->msPatArray[j+1].psPat=ps->msPatArray[j].psPat;ps->msPatArray[j].psPat=temp;}}}}static void wmPrepHashedPatternGroups(WM_STRUCT *ps)//计算有多少个不同哈希值，且从小到大{unsigned sindex,hindex,ningroup;int i;int m=ps->msSmallest;ps->msNumHashEntries=HASHTABLESIZE;ps->msHash=(HASH_TYPE*)malloc(sizeof(HASH_TYPE)* ps->msNumHashEntries);if(!ps->msHash){printf("No memory in wmPrepHashedPatternGroups()\n");return;}for(i=0;i<(int)ps->msNumHashEntries;i++){ps->msHash[i]=(HASH_TYPE)-1;}for(i=0;i<ps->msNumPatterns;i++){hindex=HASH16(&ps->msPatArray[i].psPat[m- 2]);sindex=ps->msHash[hindex]=i;ningroup=1;//此时哈希表已经有序了while((++i<ps->msNumPatterns) &&(hindex==HASH16(&ps->msPatArray[i].psPat[m-2])))ningroup++;ps->msNumArray[sindex]=ningroup;i–;}}static void wmPrepShiftTable(WM_STRUCT*ps)//建立shift表，算出每个字符块要移动的距离，像Horspool算法那样的{int i;unsigned short m,k,cindex;unsigned shift;m=(unsigned short)ps->msSmallest;ps->msShift=(unsigned char*)malloc (SHIFTTABLESIZE*sizeof(char));if(!ps->msShift)return;for(i=0;i<SHIFTTABLESIZE;i++){ps->msShift[i]=(unsigned)(m-2+1);}for(i=0;i<ps->msNumPatterns;i++){for(k=0;k<m-1;k++){shift=(unsigned short)(m-2-k);cindex=((ps->msPatArray[i].psPat[k]<<8) | (ps- >msPatArray[i].psPat[k+1]));//B为2if(shift<ps->msShift[cindex])ps->msShift[cindex]=shift;//k=m-2时，shift=0，}}}static void wmPrepPrefixTable(WM_STRUCT *ps)//建立Prefix表int i;ps->msPrefix=(HASH_TYPE*)malloc(sizeof (HASH_TYPE)* ps->msNumPatterns);if(!ps->msPrefix){printf("No memory in wmPrepPrefixTable()\n"); return;}for(i=0;i<ps->msNumPatterns;i++){ps->msPrefix[i]=HASH16(ps->msPatArray[i].psPat); //对每个模式串的前缀进行哈希}}void wmGroupMatch(WM_STRUCT *ps,//后缀哈希值相同，比较前缀以及整个字符匹配int lindex, //lindex为后缀哈希值相同的那些模式串中的一个模式串的indexunsigned char *Tx,unsigned char *T)WM_PATTERN_STRUCT *patrn;WM_PATTERN_STRUCT *patrnEnd;// int text_prefix;HASH_TYPE text_prefix; //changed by dklkt unsigned char *px,*qx;patrn=&ps->msPatArray[lindex];patrnEnd=patrn+ps->msNumArray[lindex]; //哈希值相同text_prefix=HASH16(T);for(;patrn<patrnEnd;patrn++){if(ps->msPrefix[lindex++]!=text_prefix) continue;else{px=patrn->psPat;qx=T;while(*(px++)==*(qx++) && *(qx-1)!=’\0′); // 整个模式串进行比较if(*(px-1)==’\0′){printf("Match pattern "%s" at line %d column%d\n",patrn->psPat,nline,T-Tx+1);nfound++;}}}}int wmPrepPatterns(WM_STRUCT *ps)//由plist得到msPatArray{int kk;WM_PATTERN_STRUCT *plist;ps->msPatArray=(WM_PATTERN_STRUCT*) malloc(sizeof(WM_PATTERN_STRUCT)*ps->msNumPatterns);if(!ps->msPatArray)return -1;ps->msNumArray=(unsigned short*)malloc (sizeof(short)*ps->msNumPatterns);if(!ps->msNumArray)return -1;for(kk=0,plist=ps->plist;plist!=NULL &&kk<ps->msNumPatterns;plist=plist->next){memcpy(&ps->msPatArray[kk++],plist,sizeof (WM_PATTERN_STRUCT));}sort(ps);wmPrepHashedPatternGroups(ps); wmPrepShiftTable(ps);wmPrepPrefixTable(ps);return 0;}void wmSearch(WM_STRUCT *ps,unsigned char *Tx,int n)//字符串查找{int Tleft,lindex,tshift;unsigned char *T,*Tend,*window;Tleft=n;Tend=Tx+n;if(n<ps->msSmallest)return;//T--------窗口-------Windowfor(T=Tx,window=Tx+ps->msSmallest-1;window<Tend;T++,window++,Tleft–){tshift=ps->msShift[(*(window-1)<<8) |*window];while(tshift) //此时tshift!=0,无匹配{window+=tshift;T+=tshift;Tleft-=tshift;if(window>Tend) return;tshift=ps->msShift[(*(window-1)<<8) |*window];}//tshift=0，表明后缀哈希值已经相同if((lindex=ps->msHash[(*(window-1)<<8) |*window])==(HASH_TYPE)-1) continue;lindex=ps->msHash[(*(window-1)<<8) |*window];wmGroupMatch(ps,lindex,Tx,T); //后缀哈希值相同，比较前缀及整个模式串}}int main(){int length,n;WM_STRUCT *p;char keyword[MAXM]; //单词char str[MAXN]; //模式串p=wmNew();printf("scanf the number of words–>\n"); scanf("%d", &n);printf("scanf the words–>\n");while(n –){scanf("%s", keyword);length=strlen(keyword); wmAddPattern(p,keyword,length);}wmPrepPatterns(p);printf("scanf the text string–>\n"); scanf("%s", str);length=strlen(str);wmSearch(p,str,length);wmFree(p);return(0);}下面部分为程序代码的流程图，有助于更好的理解上面的程序Main(){WM_STRUCT* p=wmNew();--->(1)While(n--)wmAddPattern(p,keyword,klength);--->(2)wmPrepPatterns(p);---->(3)wmSearch(p,str,slength);----->(8)wmFree(p);---->(10)}(1) new(p)以及p的初始化(2) keyword-----add-->p->list(3) plist---得到->msPatArraysort(ps);-->(4)wmPrepHashedpatternsGroup(ps);-->(5)wmPrepShiftTable(ps);-->(6)wmPrepPrefixTable(ps);--->(7)(4)冒泡排序，字符串哈希值从小到大排列(5) HASH表初始化计算有多少个不同哈希值，且从小到大拉链：(6)构建SHIFT表SHIFT[index]= m-B+1;//无匹配min(shift);//最短移动距离(7)构建PREFIX表Ps->msPrefix[i]=HASH16(ps->msPatArray[i].psPat);(8)求tshift若tshift!=0 移动tshift若tshift=0 hash值不存在，continue;wmGroupMatch--->(9)(9) for(;patrn<patrnEnd;patrn++)比较ps->msprefix[index++]和text_prefix若相等，再比较整个模式串(10) free(p)队列构建Trie下面为要构建的树结构：创建两个指针p,q。
