### 編輯距離算法 概念
> 指兩個字串之間,由一個轉成另一個所需的最少編輯操作次數,如果它們的距離越大,說明它們越是不同。許可的編輯操作包括將一個字符替換成另一個字符,插入一個字符,刪除一個字符。
這個概念是由俄羅斯科學家Vladimir Levenshtein在1965年提出來的,所以也叫 Levenshtein 距離。它可以用來做DNA分析,拼字檢測,抄襲識別等等。總是比較相似的,或多或少我們可以考慮編輯距離。
在概念中,我們可以看出一些重點那就是,編輯操作只有三種。`插入`,`刪除`,`替換`這三種操作,我們有兩個字符串,將其中一個字符串經過上面的這三種操作之后,得到兩個完全相同的字符串付出的代價是什么就是我們要討論和計算的。
舉例說明: 2個個單詞 hello world
| | | | | | | |
| --- | --- | --- | --- | --- | --- | --- |
| | | h | e | l | l | o |
| | 0 | 1 | 2 | 3 |4 | 5 |
| w | 1 |h≠w <br/> min(1+1,1+1,0+1) = 1| o≠w <br/> min(2+1,2+1,1+1) = 2| 3 |4|5 |
| o | 2 |h≠o <br/> min(2+1,1+1,1+1) = 2|2 | 3 | 4 | 4|
| r | 3 |h≠r <br/> min(3+1,2+1,2+1) = 3| 3 | 3 | 4| 5 |
| l | 4 |h≠l <br/> min(4+1,3+1,3+1) = 4 | 4 | 3 | 3 | 4 |
| d | 5 |h≠d <br/> min(5+1,4+1,4+1) = 5 | 5 | 4 | 4| o≠d <br/> min(4+1,4+1,3+1) = 4 |
- 虛擬機
- JVM內存結構
- JVM調優手段
- java對象生命周期
- 垃圾回收判斷對象死亡
- 垃圾回收算法
- 垃圾收集器
- JAVA基礎知識
- java事件機制
- java反射機制
- jvm創建對象
- java異常
- finally語句一定會執行嗎?
- 集合類介紹
- ArrayList
- LinkedList
- HashMap
- ConcurrentHashMap
- 多線程
- 為什么要使用線程池
- 線程死鎖
- 死鎖檢測和解除
- jstack
- jconsole
- 死鎖預防
- 常見線程池
- 線程池參數
- 工作隊列介紹
- 拒絕策略
- ThreadLocal
- CAS
- ReentrantLock
- AQS
- CountDownLatch
- Spring
- spring中bean的作用域
- REDIS
- redis數據結構
- redis hash實現
- redis rehash與hashmap擴容的區別
- Redis使用場景
- Redis為何這么快
- redis連接數不足導致錯誤
- 分布式
- 分布式事務
- ACID
- CAP
- BASE
- 事務隔離性
- 一致性哈希算法
- 負載均衡算法
- Hystrix 信號量和線程池隔離的差異
- Spring Cloud
- eureka
- MYSQL
- mysql優化經驗
- undo redo binlog
- web
- http協議
- http和https區別
- Cookie和session
- TCP三次握手、4次揮手
- TCP的time_wait和close_wait
- 算法問題
- 編輯距離算法
- MQ
- RabbitMq
- Kafka
- 安裝教程
- Win ELK安裝