久久精品人人做人人爽电影,国产精品99久久久精品无码 ,伊人色综合久久

程序員編程藝術-----第二十八 ~ 二十九章-----最大連續乘積子串、字符串編輯距離

Posted on 2013-05-28 22:18 鑫龍閱讀(342) 評論(0) 編輯收藏引用所屬分類: JULY_程序員編程藝術

第二十八~二十九章：最大連續乘積子串、字符串編輯距離

前言

時間轉瞬即逝，一轉眼，又有4個多月沒來更新blog了，過去4個月都在干啥呢？對的，今2013年元旦和朋友利用業余時間一起搭了個方便朋友們找工作的編程面試算法論壇：為學論壇http://www.51weixue.com/。最近則開始負責一款在線編程挑戰平臺：英雄會http://hero.pongo.cn/，包括其產品運營，出題審題，寫代碼測試，制定比賽規則等等。

前幾天跟百度的幾個朋友線下閑聊，聽他們說，百度校招群內的不少朋友在找工作的時候都看過我的blog，一聽當即便激起了自己重寫此blog的欲望，恰巧眼下陽春三月(雖說已是3月，奇妙的是，前兩天北京還下了一場大雪)，又是找工作的季節(相對于每年的9月份來說，3月則是一個小高潮)，那就從繼續更新專為IT人員找工作時準備筆試面試的程序員編程藝術系列開始吧。

再者從去年4月份上傳的編程藝術前27章的PDF文檔的1.3萬下載量來看http://download.csdn.net/detail/v_july_v/4256339，此系列確確實實幫助了成千上萬的人。Yeah，本文講兩個問題，

第二十八章、最大連續乘積子串，
第二十九章、字符串編輯距離，

這兩個問題皆是各大IT公司最喜歡出的筆試面試題，比如說前者是小米2013年校招筆試原題，而后者則更是反復出現，如去年9月26日百度一二面試題，10月9日騰訊面試題第1小題，10月13日百度2013校招北京站筆試題第二大道題第3小題，及去年10月15日2013年Google校招筆試最后一道大題皆是考察的這個字符串編輯距離問題。

OK，歡迎朋友們在本文下參與討論，如果在線編譯自己的代碼（編程語言任選C/C++/Java/C#），可以上英雄會提交你的代碼，有任何問題，歡迎隨時不吝批評或指正，感謝。

第二十八章、最大連續乘積子串

題目描述：給一個浮點數序列，取最大乘積連續子串的值，例如 -2.5，4，0，3，0.5，8，-1，則取出的最大乘積連續子串為3，0.5，8。也就是說，上述數組中，3 0.5 8這3個數的乘積3*0.5*8=12是最大的，而且是連續的。

提醒：此最大乘積連續子串與最大乘積子序列不同，請勿混淆，前者子串要求連續，后者子序列不要求連續。也就是說：最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence，LCS）的區別：

子串（Substring）是串的一個連續的部分，
子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；

更簡略地說，前者（子串）的字符的位置必須連續，后者（子序列LCS）則不必。比如字符串“ acdfg ”同“ akdfc ”的最長公共子串為“ df ”，而它們的最長公共子序列LCS是“ adf ”，LCS可以使用動態規劃法解決。

解答：

解法一、窮舉，所有的計算組合：
或許，讀者初看此題，自然會想到最大乘積子序列問題類似于最大子數組和問題：http://blog.csdn.net/v_JULY_v/article/details/6444021，可能立馬會想到用最簡單粗暴的方式：兩個for循環直接輪詢。

double max=0;
double start=0;
double end=0;
for (int i=0;i<num;i++) {
double x=arrs[i];
for (int j = i+1; j < num; j++) {
x*=arrs[j];
if(x>max){
max=x;
start=arrs[i];
end=arrs[j];
}
}

解法二、雖說類似于最大子數組和問題，但實際上具體處理起來諸多不同。為什么呢，因為乘積子序列中有正有負也還可能有0。我們可以把問題簡化成這樣：數組中找一個子序列，使得它的乘積最大；同時找一個子序列，使得它的乘積最小（負數的情況）。因為雖然我們只要一個最大積，但由于負數的存在，我們同時找這兩個乘積做起來反而方便。也就是說，不但記錄最大乘積，也要記錄最小乘積。So，我們讓

maxCurrent表示當前最大乘積的candidate，
minCurrent反之，表示當前最小乘積的candidate，
而maxProduct則記錄到目前為止所有最大乘積candidates的最大值。

（以上用candidate這個詞是因為只是可能成為新一輪的最大/最小乘積）

由于空集的乘積定義為1，在搜索數組前，maxCurrent，minCurrent，maxProduct都賦為1。
假設在任何時刻你已經有了maxCurrent和minCurrent這兩個最大/最小乘積的candidates，新讀入數組的元素x(i)后，新的最大乘積candidate只可能是maxCurrent或者minCurrent與x(i)的乘積中的較大者，如果x(i)<0導致maxCurrent<minCurrent，需要交換這兩個candidates的值。
當任何時候maxCurrent<1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent為1，類似的可以更新minCurrent。任何時候maxCurrent如果比最好的maxProduct大，更新maxProduct。
代碼一：

template <typename Comparable>
Comparable maxprod( const vector<Comparable>&v)
{
int i;
Comparable maxProduct = 1;
Comparable minProduct = 1;
Comparable maxCurrent = 1;
Comparable minCurrent = 1;
//Comparable t;
for( i=0; i< v.size() ;i++)
{
maxCurrent *= v[i];
minCurrent *= v[i];
if(maxCurrent > maxProduct)
maxProduct = maxCurrent;
if(minCurrent > maxProduct)
maxProduct = minCurrent;
if(maxCurrent < minProduct)
minProduct = maxCurrent;
if(minCurrent < minProduct)
minProduct = minCurrent;
if(minCurrent > maxCurrent)
swap(maxCurrent,minCurrent);
if(maxCurrent<1)
maxCurrent = 1;
//if(minCurrent>1)
// minCurrent =1;
}
return maxProduct;
}

代碼二：思路，記錄以第i個結尾的最大乘積M和最小乘積m，并且記錄這兩個區間的起點（終點都是i），不斷更新，來源http://www.51weixue.com/thread-246-1-1.html：

pair<int,int> maxproduct(double *f,int n) { //返回最大乘積的起點終點
int R = 0, r = 0; //最大最小區間的起點
pair<int,int> ret = make_pair(0, 0); //最大最小的區間下標
double M = f[0], m = f[0], answer = f[0]; // 最大最小值
for (int i = 1; i < n; ++i) {
double t0 = f[i] * M, t1 = f[i] * m;
if (t0 > t1) {
M = t0;
m = t1;
}
else {
int t = R;
R = r;
r = t;
M = t1;
m = t0;
}
if (M < f[i]) {
M = f[i];
R = i;
}
if (m > f[i]) {
m = f[i];
r = i;
}
if (answer < M) {
answer = M;
ret = make_pair(R, i);
}
}
return ret;
}

解法三、
本題除了上述類似最大子數組和的解法，也可以直接用動態規劃求解（其實，上述的解法一本質上也是動態規劃，只是解題所表現出來的具體形式與接下來的解法二不同罷了。這個不同就在于下面的解法二會寫出動態規劃問題中經典常見的DP方程，而解法一是直接求解）。具體解法如下：
假設數組為a[]，直接利用動歸來求解，考慮到可能存在負數的情況，我們用Max來表示以a結尾的最大連續子串的乘積值，用Min表示以a結尾的最小的子串的乘積值，那么狀態轉移方程為：
Max=max{a, Max[i-1]*a, Min[i-1]*a};
Min=min{a, Max[i-1]*a, Min[i-1]*a};
初始狀態為Max[1]=Min[1]=a[1]。

C/C++代碼一，很簡潔的一小段代碼：

double func(double *a,const int n)
{
double *maxA = new double[n];
double *minA = new double[n];
maxA[0] = minA[0] =a[0];
double value = maxA[0];
for(int i = 1 ; i < n ; ++i)
{
maxA[i] = max(max(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
minA[i] = min(min(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
value=max(value,maxA[i]);
}
return value;
}

C/C++代碼二：

/*
給定一個浮點數數組，有正有負數，0，正數組成,數組下標從1算起
求最大連續子序列乘積，并輸出這個序列，如果最大子序列乘積為負數，那么就輸出-1
用Max[i]表示以a[i]結尾乘積最大的連續子序列
用Min[i]表示以a[i]結尾乘積最小的連續子序列因為有復數，所以保存這個是必須的
*/
void longest_multiple(double *a,int n){
double *Min=new double[n+1]();
double *Max=new double[n+1]();
double *p=new double[n+1]();
//初始化
for(int i=0;i<=n;i++){
p[i]=-1;
}
Min[1]=a[1];
Max[1]=a[1];
double max_val=Max[1];
for(int i=2;i<=n;i++){
Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);
if(max_val<Max[i])
max_val=Max[i];
}
if(max_val<0)
printf("%d",-1);
else
printf("%d",max_val);
//內存釋放
delete [] Max;
delete [] Min;
}

C#版完整代碼(代碼來自參加英雄會在線編程挑戰之1019、最大乘積連續子串：http://hero.pongo.cn/Question/Details?ID=19&ExamID=19的在線提交代碼的用戶)：

//答題英雄：danielqkj
using System;
public class Test
{
void Max(double a, double b, double c)
{
double d = (a>b)?a:b;
return (d>c)?d:c;
}
void Min(double a, double b, double c)
{
double d = (a>b)?b:a;
return (d>c)?c:d;
}
public static void Main()
{
int n = Int32.parse(Console.readline());
double[] a = new double[n];
double maxvalue = a[0];
double[] max = new double[n];
double[] min = new double[n];
double start, end;
String[] s = Console.readline().split(' ');
for (int i = 0; i < n; i++)
{
a[i] = Double.parse(s[i])
}
max[0] = a[0];
min[0] = a[0];
start = 0, end = 0;
for (int i = 1; i < n; i++)
{
max[i]=Max(a[i], a[i]*max[i-1], a[i]*min[i-1]);
min[i]=Min(a[i], a[i]*max[i-1], a[i]*min[i-1]);
if (max[i] > maxvalue)
{
maxvalue = max[i];
end = i;
}
}
double mmm = maxvalue;
while ( (mmm - 0.0) > 0.00001 )
{
start = end;
mmm = mmm / a[start];
}
Console.Writeline(a[start] + " " + a[end] + " " + maxvalue);
}
}

變種

此外，此題還有另外的一個變種形式，即給定一個長度為N的整數數組，只允許用乘法，不能用除法，計算任意（N-1）個數的組合中乘積最大的一組，并寫出算法的時間復雜度。

我們可以把所有可能的（N-1）個數的組合找出來，分別計算它們的乘積，并比較大小。由于總共有N個（N-1）個數的組合，總的時間復雜度為O（N2），顯然這不是最好的解法。
OK，以下解答來自編程之美
解法1

解法2
此外，還可以通過分析，進一步減少解答問題的計算量。假設N個整數的乘積為P，針對P的正負性進行如下分析（其中，AN-1表示N-1個數的組合，PN-1表示N-1個數的組合的乘積）。
1.P為0

那么，數組中至少包含有一個0。假設除去一個0之外，其他N-1個數的乘積為Q，根據Q的正負性進行討論：

Q為0
說明數組中至少有兩個0，那么N-1個數的乘積只能為0，返回0；
Q為正數
返回Q，因為如果以0替換此時A_N_-1中的任一個數，所得到的P_N_-1為0，必然小于Q；
Q為負數
如果以0替換此時A_N_-1中的任一個數，所得到的P_N_-1為0，大于Q，乘積最大值為0。

2. P為負數

根據“負負得正”的乘法性質，自然想到從N個整數中去掉一個負數，使得P_N_-1為一個正數。而要使這個正數最大，這個被去掉的負數的絕對值必須是數組中最小的。我們只需要掃描一遍數組，把絕對值最小的負數給去掉就可以了。

3. P為正數

類似地，如果數組中存在正數值，那么應該去掉最小的正數值，否則去掉絕對值最大的負數值。
上面的解法采用了直接求N個整數的乘積P，進而判斷P的正負性的辦法，但是直接求乘積在編譯環境下往往會有溢出的危險（這也就是本題要求不使用除法的潛在用意），事實上可做一個小的轉變，不需要直接求乘積，而是求出數組中正數（+）、負數（-）和0的個數，從而判斷P的正負性，其余部分與以上面的解法相同。

在時間復雜度方面，由于只需要遍歷數組一次，在遍歷數組的同時就可得到數組中正數（+）、負數（-）和0的個數，以及數組中絕對值最小的正數和負數，時間復雜度為O（N）。

第二十九章、字符串編輯距離

題目描述：給定一個源串和目標串，能夠對源串進行如下操作：
1.在給定位置上插入一個字符
2.替換任意字符
3.刪除任意字符
寫一個程序，返回最小操作數，使得對源串進行這些操作后等于目標串，源串和目標串的長度都小于2000。

提醒：上文前言中已經說過了，此題反復出現，最近考的最多的是百度和Google的筆試面試經常考察。下圖則是2013年Google的校招試題原景重現：

解答：

解法一、此題跟上面的最大連續乘積子串類似，常見的思路是動態規劃，下面是簡單的DP狀態方程：

//動態規劃：
//f[i,j]表示s[0...i]與t[0...j]的最小編輯距離。
f[i,j] = min { f[i-1,j]+1, f[i,j-1]+1, f[i-1,j-1]+(s[i]==t[j]?0:1) }
//分別表示：添加1個，刪除1個，替換1個（相同就不用替換）。

解法二、本解法來自為學論壇：http://www.51weixue.com/thread-482-1-1.html。

編輯距離的定義和計算方法如下：
Given two strings A and B, edit A to B with the minimum number of edit operations:

a) .Replace a letter with another letter
b) .Insert a letter
c) .Delete a letter

E.g.
A = interestingly _i__nterestingly
B = bioinformatics bioinformatics__
1011011011001111
Edit distance = 11
Instead of minimizing the number of edge operations, we can associate a cost function to the
operations and minimize the total cost. Such cost is called edit distance. Instead of using string edit, in computational biology, people like to use string alignment.We use similarity function, instead of cost function, to evaluate the goodness of the alignment.
E.g. of similarity function: match – 2, mismatch, insert, delete – -1.
Consider two strings ACAATCC and AGCATGC.
One of their alignment is

In the above alignment, space (‘_’) is introduced to both strings. There are 5 matches, 1
mismatch, 1 insert, and 1 delete.The alignment has similarity score 7.
A_CAATCC
AGCA_TGC
Note that the above alignment has the maximum score.Such alignment is called optimal
alignment.String alignment problem tries to find the alignment with the maximum similarity
score!String alignment problem is also called global alignment problem.
Needleman-Wunsch algorithm
Consider two strings S[1..n] and T[1..m].Define V(i, j) be the score of the optimal alignment
between S[1..i] and T[1..j].
Basis:
V(0, 0) = 0
V(0, j) = V(0, j-1) + d(_, T[j])：Insert j times
V(i, 0) = V(i-1, 0) + d(S, _)：Delete i times
that is:

Example :

下面是代碼，測試數據比較少，若有問題請指正：

//copyright@ peng_weida
//實現代碼如下：
//頭文件StrEditDistance.h
#pragma once
#include <string>
class CStrEditDistance
{
public:
CStrEditDistance(std::string& vStrRow, std::string& vStrColumn);
~CStrEditDistance(void);
int getScore() { return m_Score; }
int getEditDis() { return m_EditDis; }
void setEditDis(int vDis) { m_EditDis = vDis; }
void setScore(int vScore) { m_Score = vScore; }
private:
void process(const std::string& vStrRow, const std::string& vStrColumn);
int getMaxValue(int a, int b, int c)
{
if (a < b){ if (b < c) return c; return b; }
else { if (b > c) return a; return a < c ? c : a; }
}
private:
int m_EditDis;
int m_Score;
};
//源文件StrEditDistance.cpp
#include "StrEditDistance.h"
#include <iostream>
#include <iomanip>
#define MATCH 2
#define MISS_MATCH -1
#define INSERT -1
#define DELETE -1
CStrEditDistance::CStrEditDistance(std::string& vStrRow, std::string& vStrColumn)
{
process(vStrRow, vStrColumn);
}
CStrEditDistance::~CStrEditDistance(void)
{
}
//FUNCTION:
void CStrEditDistance::process(const std::string& vStrRow, const std::string& vStrColumn)
{
int editDis = 0; //編輯距離
int row = vStrColumn.length();
int column = vStrRow.length();
const int sizeR = row + 1;
const int sizeC = column + 1;
int **pScore = new int*[sizeR]; //二維指針
for (int i = 0; i <= row; i++)
pScore = new int[sizeC];
//初始化第一行和第一列
for (int c = 0; c <= column; c++)
pScore[0][c] = 0 - c;
for (int r = 0; r <= row; r++)
pScore[r][0] = 0 - r;
//從v(1,1)開始每列計算
for (int c = 1; c <= column; c++)
{
for (int r = 1; r <= row; r++)
{
//計算v(i,j)
int valueMatch;
if (vStrColumn[r-1] == vStrRow[c-1])
valueMatch = MATCH;
else
valueMatch = MISS_MATCH;
int A = pScore[r-1][c] + INSERT;
int B = pScore[r][c-1] + DELETE;
int C = pScore[r-1][c-1] + valueMatch;
pScore[r][c] = getMaxValue(A, B, C);
}
}
//計算編輯距離
int r = row, c = column;
while(r > 0 && c > 0)
{
if (pScore[r][c]+1 == pScore[r-1][c]) { editDis++; r--; continue; }
else if (pScore[r][c]+1 == pScore[r][c-1]) { editDis++; c--; continue; }
else if (pScore[r][c]+1 == pScore[r-1][c-1]){ editDis++; r--; c--; continue; }
else { r--; c--; }
}
if (r > 0 && c == 0) editDis += r;
else if (c > 0 && r == 0) editDis += c;
std::cout << std::endl;
//----------------DEBUG-------------------//
//打印數據
for (int i = 0; i <= row; i++)
{
for (int j = 0; j <= column; j++)
std::cout << std::setw(2) << pScore[j] << " ";
std::cout << std::endl;
}
std::cout << std::endl;
//設置編輯距離和得分
setEditDis(editDis);
setScore(pScore[row][column]);
for (int i = 0; i <= row; i++) //釋放內存
{
delete pScore;
pScore = NULL;
}
delete[] pScore;
}

類似

上述問題類似于編程之美上的下述一題「以下內容摘自編程之美第3.3節」：

許多程序會大量使用字符串。對于不同的字符串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來把兩個不相同的字符串變得相同，具體的操作方法為：

修改一個字符（如把“a”替換為“b”）；
增加一個字符（如把“abdd ”變為“aebdd ”）；
刪除一個字符（如把“travelling”變為“traveling”）。

比如，對于“abcdefg”和“abcdef ”兩個字符串來說，我們認為可以通過增加/減少一個“g”的方式來達到目的。上面的兩種方案，都僅需要一次操作。把這個操作所需要的次數定義為兩個字符串的距離，而相似度等于“距離+1”的倒數。也就是說，“abcdefg”和“abcdef”的距離為1，相似度為1 / 2 = 0.5。
給定任意兩個字符串，你是否能寫出一個算法來計算出它們的相似度呢？

這樣，很快就可以完成一個遞歸程序，如下所示：

Int CalculateStringDistance(string strA, int pABegin, int pAEnd,
string strB, int pBBegin, int pBEnd)
{
if(pABegin > pAEnd)
{
if(pBBegin > pBEnd)
return 0;
else
return pBEnd – pBBegin + 1;
}
if(pBBegin > pBEnd)
{
if(pABegin > pAEnd)
return 0;
else
return pAEnd – pABegin + 1;
}
if(strA[pABegin] == strB[pBBegin])
{
return CalculateStringDistance(strA, pABegin + 1, pAEnd,
strB, pBBegin + 1, pBEnd);
}
else
{
int t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB,
pBBegin + 1, pBEnd);
int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd,
strB,pBBegin, pBEnd);
int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,
strB,pBBegin + 1, pBEnd);
return minValue(t1,t2,t3) + 1;
}
}

上面的遞歸程序，有什么地方需要改進呢？問題在于：在遞歸的過程中，有些數據被重復計算了。

　　我們知道適合采用動態規劃方法的最優化問題中的兩個要素：最優子結構和重疊子問題。另外，還有一種方法稱為備忘錄（memoization），可以充分利用重疊子問題的性質。

　　下面簡述一下動態規劃的基本思想。和分治法一樣，動態規劃是通過組合子問題的解而解決整個問題的。我們知道，分治算法是指將問題劃分成一睦獨立的子問題，遞歸地求解各子問題，然后合并子問題的解而得到原問題的解。與此不同，動態規劃適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題。在這種情況下，若用分治法則會做許多不必要的工作，即重復地求解公共的子子問題。動態規劃算法對每個子子問題只求解一次，將其結果保存在一張表中，從而避免每次遇到各個子問題時重新計算答案。

動態規劃通常應用于最優化問題。此類問題可能有很多種可行解，每個解有一個值，而我們希望找出一個具有最優（最大或最小）值的解。稱這樣的解為該問題的“一個”最優解（而不是“確定的”最優解），因為可能存在多個取最優值的解。

　　動態規劃算法的設計可以分為如下4個步驟：

　　1）描述最優解的結構。

　　2）遞歸定義最優解的值。

　　3）按自底向上的方式計算最優解的值。

　　4）由計算出的結果構造一個最優解。

　　第1~3步構成問題的動態規劃解的基礎。第4步在只要求計算最優解的值時可以略去。如果的確做了第4步，則有時要在第3步的計算中記錄一些附加信息，使構造一個最優解變得容易。

　　該問題明顯完全符合動態規劃的兩個要素，即最優子結構和重疊子問題特性。該問題的最優指的是兩個字符串的最短距離，子問題的重疊性可以從原書中的那個遞歸算法中看出。

　　下面再來詳細說說什么是重疊子問題。適用于動態規劃求解的最優化問題必須具有的第二個要素是子問題的空間要“很小”，也就是用來解原問題的遞歸算法可以反復地解同樣的子問題，而不是總在產生新的子問題。典型地，不同的子問題數是輸入規模的一個多項式。當一個遞歸算法不斷地調用同一問題時，我們說該最優問題包含重疊子問題。相反地，適合用分治法解決的問題只往往在遞歸的每一步都產生全新的問題。動態規劃算法總是充分利用重疊子問題，即通過每個子問題只解一次，把解保存在一個需要時就可以查看的表中，而每次查表的時間為常數。

根據以上的分析，我寫了如下的動態規劃算法：

/*DP Algorithm
　 * A loop method using dynamic programming.
　 * Calculate from bottom to top.
　 */
 int calculateStringDistance(string strA, string strB)
 {
　　　　 int lenA = (int)strA.length();
　　　　 int lenB = (int)strB.length();
　　　　 int c[lenA+1][lenB+1]; 
        // Record the distance of all begin points of each string
        //初始化方式與背包問題有點不同
　　　　 for(int i = 0; i < lenA; i++) c[i][lenB] = lenA - i;
　　　　 for(int j = 0; j < lenB; j++) c[lenA][j] = lenB - j;
　　　　 c[lenA][lenB] = 0;
　　　　 for(int i = lenA-1; i >= 0; i--)
　　　　　　　　 for(int j = lenB-1; j >= 0; j--)
　　　　　　　　 {
　　　　　　　　　　　　 if(strB[j] == strA[i])
　　　　　　　　　　　　　　　　 c[i][j] = c[i+1][j+1];
　　　　　　　　　　　　 else
　　　　　　　　　　　　　　　　 c[i][j] = minValue(c[i][j+1], c[i+1][j], c[i+1][j+1]) + 1;
　　　　　　　　 }
 
　　　　 return c[0][0];
 }

深入

詳細讀者朋友們也已經看到了，百度/Google經常喜歡出這個字符串編輯距離，實際上，關于這個“編輯距離”問題在搜索引擎中有著重要的作用，如搜索引擎關鍵字查詢中拼寫錯誤的提示，如下圖所示，當你輸入“Jult”后，因為沒有這個單詞“Jult”，所以搜索引擎猜測你可能是輸入錯誤，進而會提示你是不是找“July”：
但這個拼寫錯誤檢查的原理是什么呢？Google是基于貝葉斯統計推斷的方法，相關原理詳情可以看下Google的研發總監Peter Norvig寫的這篇文章：http://norvig.com/spell-correct.html，以及fuanyif寫的這篇：http://www.ruanyifeng.com/blog/2012/10/spelling_corrector.html。
關于什么是“編輯距離”：一個快速、高效的Levenshtein算法實現，這個是計算兩個字符串的算法，Levenshtein距離又稱為“編輯距離”，是指兩個字符串之間，由一個轉換成另一個所需的最少編輯操作次數。當然，次數越小越相似。這里有一個BT樹的數據結構，挺有意思的：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees；
最后，Lucene中也有這個算法的實現(我想，一般的搜索引擎一般都應該會有此項拼寫錯誤檢查功能的實現)，下面是lucene的源碼(并沒有太多優化，與實際工程中java注重實用性的原則并不背離)：
1. public final class LevensteinDistance {
3. public LevensteinDistance () {
4. }
6. // Compute Levenshtein distance:
7. // see org.apache.commons.lang.StringUtils#getLevenshteinDistance(String, String)
9. public float getDistance (String target, String other) {
10. char[] sa;
11. int n;
12. int p[];
13. //'previous' cost array, horizontally
14. int d[];
15. // cost array, horizontally
16. int _d[];
17. //placeholder to assist in swapping p and d
19. sa = target.toCharArray();
20. n = sa.length;
21. p = new int[n+1];
22. d = new int[n+1];
24. final int m = other.length();
25. if (n == 0 || m == 0) {
26. if (n == m) {
27. return 1;
28. }
29. else {
30. return 0;
31. }
32. }
34. // indexes into strings s and t
35. int i;
36. // iterates through s
37. int j;
38. // iterates through t
40. char t_j;
41. // jth character of t
43. int cost;
44. // cost
46. for (i = 0; i<=n; i++) {
47. p[i] = i;
48. }
50. for (j = 1; j<=m; j++) {
51. t_j = other.charAt(j-1);
52. d[0] = j;
54. for (i=1; i<=n; i++) {
55. cost = sa[i-1]==t_j ? 0 : 1;
57. // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
58. d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
59. }
62. // copy current distance counts to 'previous row' distance counts
63. _d = p;
64. p = d;
65. d = _d;
66. }
69. // our last action in the above loop was to switch d and p, so p now
71. // actually has the most recent cost counts
72. return 1.0f - ((float) p[n] / Math.max(other.length(), sa.length));
73. }
75. }

擴展

當然，面試官還可以繼續問下去，如請問，如何設計一個比較兩篇文章相似性的算法？這個問題的討論可以看看這里：http://t.cn/zl82CAH。OK，字符串編輯距離這個問題實用性很強，限于篇幅，詳情讀者自己深入吧。

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 程序員編程藝術-----第二十八 ~ 二十九章-----最大連續乘積子串、字符串編輯距離程序員編程藝術-----第二十七章-----不改變正負數相對順序重新排列數組程序員編程藝術-----第二十五章-----二分查找實現（Jon Bentley：90%程序員無法正確實現）程序員編程藝術-----第二十三 ~ 二十四章-----楊氏矩陣、不重復Hash編碼程序員編程藝術-----第十五 ~ 二十章-----全排列、跳臺階、奇偶、第一個出現一次字符、一致性hash 程序員編程藝術-----第十一 ~ 十四章-----海量整數處理、蓄水池抽樣、回文程序員編程藝術-----第十章-----最長公共子序列(LCS)問題程序員編程藝術-----第九章-----閑話鏈表追趕問題程序員編程藝術-----第八章-----從頭至尾漫談虛函數程序員編程藝術-----第七章-----求連續子數組的最大和

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

mysileng

導航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

程序員編程藝術-----第二十八 ~ 二十九章-----最大連續乘積子串、字符串編輯距離

第二十八~二十九章：最大連續乘積子串、字符串編輯距離

前言

第二十八章、最大連續乘積子串

變種

第二十九章、字符串編輯距離

類似

深入

擴展