多くのドメインとアプリケーションでは、時にはいくつかの単語やフレーズを比較し、その類似性を定量化する必要があります.
これはかなり人気の概念は、編集距離です.

距離を編集?何ですか。

編集距離は、1つの別に変換するために必要な操作量を数えることによって2つの文字列間の相違点を定量化するために使用されるメトリックです.選択されたアルゴリズムによって、許可される操作は以下を含むかもしれません:加算、削除、置換と最終的に翻訳.
この測定は、この式で2つの文字列間の類似性のパーセンテージを計算するために使用することができます.

(maxLength - distance) / maxLength

編集距離の種類

つの異なる文字列の編集距離を計算する多くのアルゴリズムがあります.
最も有名なのは、
挿入、削除と置換を許しているLevenstein距離

.これは最も有名な編集距離アルゴリズムですが、何を考えても、それは常に最も適切ではありません.

加算、削除、置換と転位を許している

ダマレベンシュタイン距離.
このアルゴリズムの2つの方法は、OSA(最適文字列の配置距離)は、文字列と隣接するトランスポーズによって転位を可能にするだけでなく、必要に応じて多くの転位を可能にするが、固定アルファベットが必要です.

LCS距離(最長の一般的なサブシーケンス)の追加と削除を許可します.これは最長の共通部分系列アルゴリズムに基づいています.

同じ長さの文字列にのみ適用可能な距離をハミングすると、文字の置換だけが可能です.

JARO距離はトランスポーズのみを許容し、0と1の間の正規化された類似インデックスを返す.
バリアントが2つの文字列の一般的な接頭辞を考慮して、それを計算により大きな重みを与えるJaro Winklerと呼ばれます.

これらのアルゴリズムの全てのUnicode互換性を持つGolangの実装は、以下のようになります.
https://github.com/hbollon/go-edlib
このコースの残りの部分については、我々はLevensteinアルゴリズムに焦点を当てます.

何用ですか。

編集距離は、次のようないくつかのアプリケーション領域で使用できます.

ファジィ検索アルゴリズム

スペルチェックエラーの修正

語完成242479182

DNA配列アラインメントアルゴリズム

パターンマッチング

とより多く!

レベンシュタイン距離

LevensTheinは最も有名な編集距離アルゴリズムの一つです.それはソ連の数学者ウラジーミルLevenshteinによって作成されました.これは挿入、削除や置換を許可します.
例えば、「子猫」と「座っている」の間のlevenshtein距離は3であるので、最小に、3つの編集が1つを他方に変えるのに必要です.

子猫→ sitten(KのためのSの代用)

sitten→ シットチン(E)

sittin→ 座っている(最後にGの挿入).

定義

2つの文字列の間のlevenshtein距離はlev a , b (

A、B:2つの入力ストリング

うるう:

の長さ

○○○B

の長さ
我々は、WikipediaでLevenstein関数を見つけることができます

しかし、最初は理解しにくい.
まず、入力文字列のうちの1つが空であるならば、編集距離はもう一方の長さです.

他に、我々はlevensteinアルゴリズムを解きます.

この部分ではᵢ≠bⱼ) はᵢ≠bⱼ を返します.It

Aᵢ 位置iの文字列Aの文字を指します

Bⱼ 位置J

でストリングBの性格を参照します
それらが等しいなら、編集が必要でないので、編集距離に1を加えてはいけません.しかし、彼らが等しくないならば、我々はそれに1を加えたいです.

アルゴリズムと複雑性

levenshteinのアルゴリズムのいくつかの実装がありますが、それらのすべてが効率的ではありません.
完全行列を用いた反復法に注目する.
マトリックスは入力文字列のすべての接頭語間の距離を含んでいます、そして、ダイナミックなプログラミングスタイルで行列値を計算することができて、最終的に計算される最後の値として2つの完全なストリングの間の距離を見つけます.
exempleのために、我々は子猫と座って、このマトリックスを持っています:

見ることができるように、子猫と座っている間の編集距離は3です.

パスカルアルゴリズム

Wikipediaでは、この実装の擬似コードアルゴリズムを見つけることができます.

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  declare int d[0..m, 0..n]

  set each element in d to zero

  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
      d[i, 0] := i

  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
      d[0, j] := j

  for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution

  return d[m, n]

通常、これまで述べてきたことを理解しているなら、大まかに理解してください.
このアルゴリズムはo ( n * m )の最悪の複雑さを持っています.

ゴランの実施

それはすべてのよく知っているすべてのこれを知って良いですが、実際のプログラミング言語でそれを実装する方法は?
このために、Goを使用します.これは、Googleで近代的でコンパイルされた言語のデザインです.
私たちの実装は、Unicodeと互換性がありますので、入力文字列で例えば絵文字や数学記号を置くことができるようになります!
まず、関数を作成しましょう!

func LevenshteinDistance(str1, str2 string) int {

}

つの入力文字列を受け取り、編集距離を返します.
さて、文字列をルーン配列に変換してUnicode互換性を持たなければなりません.

// Convert string parameters to rune arrays to be compatible with non-ASCII
runeStr1 := []rune(str1)
runeStr2 := []rune(str2)

goでは、runeはint 32(32ビット整数)の別名です.
一旦それが行われるならば、我々はこれらのストリングの長さを取り戻して、これらのストリングが等しいか、それらのどれかが空であるならば、探し始めなければなりません.

// Get and store length of these strings
runeStr1len := len(runeStr1)
runeStr2len := len(runeStr2)
if runeStr1len == 0 {
    return runeStr2len
} else if runeStr2len == 0 {
    return runeStr1len
} else if utils.Equal(runeStr1, runeStr2) {
    return 0
}

UtilsEURは2つのルーン配列の等価性をチェックするために定義したユーティリティ関数です.また、直接文字列入力を比較できます.
より簡単にするために、我々の実装はマトリックスの代わりに単純なスライスを使用するでしょう、しかし、原則は同じです.
距離配列を作り、それを初期化しましょう.

// The slice size must be of the length of "runeStr1len+1"
column := make([]int, runeStr1len+1)
for y := 1; y <= runeStr1len; y++ {
    column[y] = y
}

最後に、Levensteinアルゴリズムを使用して列配列を計算し、入力文字列間の距離を返します.

for x := 1; x <= runeStr2len; x++ {
    column[0] = x
    lastkey := x - 1
    for y := 1; y <= runeStr1len; y++ {
        oldkey := column[y]
        var i int
        if runeStr1[y-1] != runeStr2[x-1] {
            i = 1
        }
        column[y] = utils.Min(
            utils.Min(column[y]+1, // insert
                column[y-1]+1), // delete
            lastkey+i) // substitution
        lastkey = oldkey
    }
}

return column[runeStr1len]

UtilsMINは以前と同様にカスタム関数です.
それだ!今、あなたは任意の単語や文章の間でレヴェンシュタインの距離を計算することができます!
間違いをしていない場合は、次のようにします.

// LevenshteinDistance calculate the distance between two string
// This algorithm allow insertions, deletions and substitutions to change one string to the second
// Compatible with non-ASCII characters
func LevenshteinDistance(str1, str2 string) int {
    // Convert string parameters to rune arrays to be compatible with non-ASCII
    runeStr1 := []rune(str1)
    runeStr2 := []rune(str2)

    // Get and store length of these strings
    runeStr1len := len(runeStr1)
    runeStr2len := len(runeStr2)
    if runeStr1len == 0 {
        return runeStr2len
    } else if runeStr2len == 0 {
        return runeStr1len
    } else if equal(runeStr1, runeStr2) {
        return 0
    }

    column := make([]int, runeStr1len+1)

    for y := 1; y <= runeStr1len; y++ {
        column[y] = y
    }
    for x := 1; x <= runeStr2len; x++ {
        column[0] = x
        lastkey := x - 1
        for y := 1; y <= runeStr1len; y++ {
            oldkey := column[y]
            var i int
            if runeStr1[y-1] != runeStr2[x-1] {
                i = 1
            }
            column[y] = min(
                min(column[y]+1, // insert
                    column[y-1]+1), // delete
                lastkey+i) // substitution
            lastkey = oldkey
        }
    }

    return column[runeStr1len]
}

// Return the smallest integer among the two in parameters
func min(a int, b int) int {
    if b < a {
        return b
    }
    return a
}

// Compare two rune arrays and return if they are equals or not
func equal(a, b []rune) bool {
    if len(a) != len(b) {
        return false
    }
    for i, v := range a {
        if v != b[i] {
            return false
        }
    }
    return true
}

私は心からあなたがこのコースを楽しんで、それはあまりにも乱雑ではないことを願っています!フランスの学生として、これは私の最初の話をしようとするので、任意のフィードバックを歓迎します!
私は編集距離とストリング比較オープンソースライブラリを行いました.
これは、最も人気のある編集距離アルゴリズムを実装し、すぐにすべてのそれらの!現在、それは含まれています:levenshtein、lcs、hamming、damerau levenshtein(osaと隣接転位アルゴリズム)、Jaro/Jaro Winkler.
これらのアルゴリズムは、Unicode
また、ファジー検索アルゴリズムを編集距離といくつかの他の文字列比較関数に基づいています.
私は積極的にフィードバックを探している/または貢献このライブラリを改善したり、新しい機能のアイデアを追加する必要があります!