golang 字符串相似度算法

在使用cobra的时候，如果输入的command不对，会提示：

<pre><code>$ go run main.go pring katy Error: unknown command "pring" for "cobra" Did you mean this? print</code></pre>

很好奇这个怎么做的，没想到这竟然是一个字符串相似度的算法题 。

 

题目： 一个字符串可以通过增加一个字符，删除一个字符，替换一个字符得到另外一个字符串，假设，我们把从字符串A转换成字符串B，前面3种操作所执行的最少次数称为AB相似度
如  abc adc  度为 1
      ababababa babababab 度为 2
      abcd acdb 度为2


 字符串相似度算法可以使用 Levenshtein Distance算法(中文翻译：编辑距离算法) 这算法是由俄国科学家Levenshtein提出的。其步骤

<table border="1"><tbody><tr><th>Step</th><th>Description</th></tr><tr><td style="vertical-align:top;">1</td><td>Set n to be the length of s.
Set m to be the length of t.
If n = 0, return m and exit.
If m = 0, return n and exit.
Construct a matrix containing 0..m rows and 0..n columns.</td></tr><tr><td style="vertical-align:top;">2</td><td>Initialize the first row to 0..n.
Initialize the first column to 0..m.</td></tr><tr><td style="vertical-align:top;">3</td><td>Examine each character of s (i from 1 to n).</td></tr><tr><td style="vertical-align:top;">4</td><td>Examine each character of t (j from 1 to m).</td></tr><tr><td style="vertical-align:top;">5</td><td>If s[i] equals t[j], the cost is 0.
If s[i] doesn't equal t[j], the cost is 1.</td></tr><tr><td style="vertical-align:top;">6</td><td>Set cell d[i,j] of the matrix equal to the minimum of:
a. The cell immediately above plus 1: d[i-1,j] 1.
b. The cell immediately to the left plus 1: d[i,j-1] 1.
c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] cost.</td></tr><tr><td style="vertical-align:top;">7</td><td>After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].</td></tr></tbody></table>

 代码位置：https://github.com/spf13/cobra/cobra.go#ld

<pre><code class="language-Go">// ld compares two strings and returns the levenshtein distance between them. func ld(s, t string, ignoreCase bool) int { if ignoreCase { s = strings.ToLower(s) t = strings.ToLower(t) } d := make([][]int, len(s) 1) for i := range d { d[i] = make([]int, len(t) 1) } for i := range d { d[i][0] = i } for j := range d[0] { d[0][j] = j } for j := 1; j <= len(t); j { for i := 1; i <= len(s); i { if s[i-1] == t[j-1] { d[i][j] = d[i-1][j-1] } else { min := d[i-1][j] if d[i][j-1] < min { min = d[i][j-1] } if d[i-1][j-1] < min { min = d[i-1][j-1] } d[i][j] = min 1 } } } return d[len(s)][len(t)] }</code></pre>

 

到此这篇关于“golang 字符串相似度算法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
php比较字符串相似度的函数用法参考
golang 字符串相似度算法
php字符串函数有哪些
php字符串查找函数(strrpos与strchr)
php5 字符串处理函数汇总
PHP字符串函数与使用分析
golang计算字符串长度
php比较字符串相似度的实例代码
php similar_text函数怎么用
Golang——运算符和格式化输出