有一個需求剩蟀，在一堆的字符串中罚勾，找出所有相似的字符串對刹帕。其中數(shù)據(jù)有這樣的特點：大部分差異很大渊涝，一些字符串相等，另一些有個別字符不一樣抛计。后找到了一個算法：最小編輯算法哄孤。原理就不說了，需要的去百度一下吹截。
當(dāng)然瘦陈，這個Edit distance算法的效率還是可以的，O(n^2)波俄，但我其實只需要判斷是否相似（最終代價小于某個值minV）晨逝，而不是差異有多大，因此想到優(yōu)化方案：如果當(dāng)前dp過程中懦铺，發(fā)現(xiàn)到終點的必經(jīng)之路的代價最小值大于minV捉貌，則判斷不相似，直接返回false冬念。因此趁窃，需要找到必經(jīng)之路，和計算最小值急前。
在經(jīng)典的ED算法中醒陆，結(jié)構(gòu)很簡單，一個嵌套的循環(huán)和一個狀態(tài)轉(zhuǎn)移方程裆针。
```java
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
a[i][j]=min(a[i-1][j]+1,a[i][j-1]+1,a[i-1][j-1]+(s1[i]==s2[j]?0:1));
```
大致下圖的順序
以獲得最終代碼為目標(biāo)统求，這樣差不多效率到了極致了。
但我不需要這么詳細(xì)的結(jié)果据块。
回到之前的需要：必經(jīng)之路和最小代價
顯然，要到達(dá)紅色位置折剃，必然經(jīng)過一個或多個黑色位置另假。
那么如果紅色的代價至少不小于黑色代價的最小值怕犁。這不是顯然的嘛...
當(dāng)然边篮，我們不能到終點了才判斷，那就沒意義了奏甫。往前擴展戈轿，可以得到下圖
但是，這里黑色區(qū)域的最小代價是0阵子，而已傳統(tǒng)的ED算法思杯，至少得算minV行才可能得到大于minV的代價。于是乎，修改一下遍歷順序：
這樣色乾，能很快得到第一個大于minV的必經(jīng)之路最小代價誊册。
需要計算兩行的最小代價（黃線）如果這些最小代價均大于minV，則最終代價一定大于minV暖璧，判定為不相似案怯。
有同學(xué)要問了，只計算黃線區(qū)域澎办，萬一邊上的代價小于或等于minV呢嘲碱？
能看懂箭頭吧：藍(lán)色>=minV麦锯，否則邊上的黑色(黃線)就不能保證>=minV+1，與黃線最小值大于minV不符至会。
效率比較：
造數(shù)據(jù)：生成500條隨機數(shù)據(jù)f(len,max)（執(zhí)行500*499/2次ED算法
）
len是隨機字符串長度离咐，max是每個字符的可能（或者說每個字符是1-minV中的一個）
如f(5,3)可能是31213
判斷相似的最小代價minV
附上我的測試結(jié)果：（在公司服務(wù)器上測的，所有每次結(jié)果都不一樣）
f(50,2) minV=5 標(biāo)準(zhǔn)ED耗時 2.7s 優(yōu)化ED耗時1.2s 相似對 0
f(50,2) minV=10?標(biāo)準(zhǔn)ED耗時 2.1s 優(yōu)化ED耗時2.5s 相似對 112
f(50,10) minV=10 標(biāo)準(zhǔn)ED耗時 2.3s 優(yōu)化ED耗時0.6s 相似對 0
f(50,10) minV=10?標(biāo)準(zhǔn)ED耗時 2.1s 優(yōu)化ED耗時0.9s 相似對 0
f(50,10)?minV=50 標(biāo)準(zhǔn)ED耗時 2.1s 優(yōu)化ED耗時3.1s 相似對 124750
結(jié)果符合預(yù)期：如果minV太大奉件，優(yōu)化ED更耗時宵蛀，因為運行效率的系數(shù)更大（似乎差距不算太大）
在數(shù)據(jù)差異很大，并且minV遠(yuǎn)小于len時县貌，效率有極大改善术陶。
不錯，很符合我的需求煤痕。bingo
（代碼在公司服務(wù)器上梧宫，沒法復(fù)制出來，就不貼出來了）
