많은 분야와 응용에서 우리는 때때로 몇 개의 단어나 단어를 비교하고 그 유사성을 계량화해야 한다.
이에 대해 상당히 유행하는 개념은 편집 거리다.

거리를 편집합니까?이게 어떻게 된 일입니까?

편집 거리는 하나의 문자열을 다른 문자열로 변환하는 데 필요한 작업량을 계산하여 두 문자열 간의 차이를 계량화하는 도량입니다.선택한 알고리즘에 따라 허용되는 작업은 추가, 삭제, 교체, 최종 번역을 포함할 수 있습니다.
그런 다음 측정값을 사용하여 다음 공식을 사용하여 두 문자열 간의 유사도 비율을 계산할 수 있습니다.

(maxLength - distance) / maxLength

다양한 유형의 편집 거리

두 개의 서로 다른 문자열의 편집 거리를 계산할 수 있는 많은 알고리즘이 있다.
그 중에서 가장 유명한 것은 다음과 같다.

Levenstein 거리로 삽입, 삭제, 교체가 가능합니다.이것은 가장 유명한 편집 거리 알고리즘이지만, 네가 어떻게 생각하든지 간에, 그것은 항상 가장 적합한 것은 아니다.

Damerau-Levenstein 거리로 추가, 삭제, 교체 및 전환이 가능합니다.
이 알고리즘은 두 가지 다른 방법이 있는데 OSA(가장 좋은 문자열 정렬 거리)는 하위 문자열로만 전환할 수 있고 인접 전환은 필요에 따라 가능한 한 많은 전환을 할 수 있지만 고정된 자모표가 필요하다.

LCS 거리(최장 공통 하위 시퀀스)로 추가 및 삭제가 가능합니다.그것은 가장 긴 공공 서열 알고리즘을 바탕으로 한다.

한명 거리는 같은 길이의 문자열에만 적용되며, 문자만 바꿀 수 있습니다.

Jaro 거리는 0에서 1 사이의 귀일화 유사성 지수만 전환하고 되돌릴 수 있습니다.
두 문자열의 공통 접두사를 고려하고 계산에 더 큰 권한을 부여하는 Jaro-Winkler라는 변체가 있다.

유니코드 호환성을 갖춘 이 모든 알고리즘의 Golang 구현은 다음과 같습니다.
https://github.com/hbollon/go-edlib
이 과정의 나머지 부분에서 우리는 Levenstein 알고리즘을 중점적으로 소개할 것이다.

그것은 무엇에 쓰입니까?

편집 거리는 다음 응용 분야에 사용할 수 있습니다.

모호 검색 알고리즘

맞춤법 오류 수정

문자 완성

DNA 서열 비교 알고리즘

모드 일치

이상!

거리 편집

Levenstein은 가장 유명한 편집 거리 알고리즘 중 하나입니다.그것은 소련의 수학자 프라기미르 레빈슈타인이 창립한 것으로 1965년에 이 거리를 고려했다.삽입, 삭제 또는 교체를 허용합니다.
예를 들어 "kitten"과 "siting"사이의 Levenshtein 거리는 3입니다. 하나를 다른 것으로 변경하려면 적어도 세 번의 편집이 필요하기 때문입니다.

마리 고양이→ sitten("k"대신 "s")

sitten→ sittin('e'대신'i')

sittin→ 앉으세요.

해석하다

두 문자열 사이의 Levenshtein 거리는 lev a, b(|a |, |b |)로 정의됩니다.

a, b: 두 개의 입력 문자열

|a |:

길이

| b | 길이b

우리는 Wikipedia에서 Levenstein 함수를 찾을 수 있다

그러나 처음에는 이해하기 어려웠다.
먼저 입력 문자열 중 하나가 비어 있으면 편집 거리가 다른 문자열의 길이입니다.

그렇지 않으면 Levenstein 알고리즘을 구합니다.

이 섹션에서 1(aᵢ≠bⱼ) 마땅히ᵢ≠bⱼ 그렇지 않으면 1과 같다.그것

aᵢ 위치 i

에 있는 문자열 a의 문자

bⱼ 위치 j

곳의 문자열 b를 가리키는 문자
서로 같지 않은지 확인해야 합니다. 서로 같으면 편집할 필요가 없기 때문에 편집 거리에 1을 추가해서는 안 됩니다.그러나 만약 그것들이 같지 않다면, 우리는 1을 추가하고 싶다.

알고리즘과 복잡성

Levenshtein 알고리즘은 몇 가지 실현이 있지만 모든 실현이 효과적인 것은 아니다.
우리는 전 행렬을 가진 교체 방법을 연구할 것이다.
행렬은 입력된 문자열의 모든 접두사 사이의 거리를 포함하고 동적 기획 방식으로 행렬 값을 계산할 수 있으며, 마지막으로 두 개의 전체 문자열 사이의 거리를 마지막으로 계산한 값으로 찾을 수 있습니다.
예를 들어 우리는 고양이와 앉은 자세 행렬을 가지고 있다.

보시다시피 고양이와 앉은 자세 사이의 편집 거리는 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)입니다. 다음은 간략하게 설명합니다.

Golang 구현

이 모든 것이 좋다는 것을 알지만, 진정한 프로그래밍 언어에서 그것을 실현하는 것은 어떻습니까?
이를 위해, 우리는 Go을 사용할 것이다.이것은 현대의 번역 언어로 설계된 구글이다.
우리의 구현은 유니코드와 호환되기 때문에 이모티콘이나 수학 기호를 입력 문자열에 넣을 수 있습니다!
우선, 함수를 만듭시다!

func LevenshteinDistance(str1, str2 string) int {

}

두 개의 입력 문자열을 받아들여 편집 거리를 되돌려줍니다.
이제 문자열을 유니코드와 호환되도록 문자 그룹으로 변환해야 합니다.

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

Go에서 룬은 int32(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
}

utils.Equal은 제가 정의한 실용 함수입니다. 두 문자 그룹의 상등성을 검사하는 데 사용됩니다. here을 검색할 수 있습니다.또는 입력한 문자열을 직접 비교할 수 있습니다.
더 간단하게 말하자면, 우리의 실현은 행렬이 아니라 간단한 절편을 사용할 것이다. 그러나 원리는 같다.
거리 그룹을 만들고 초기화합니다.

// 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]

utils.이전과 마찬가지로 Min은 here을 검색할 수 있는 사용자 정의 함수입니다.
그렇습니다!이제 원하는 단어나 문장 사이의 Levenstein 거리를 계산할 수 있습니다!
만약 네가 어떤 잘못도 범하지 않았다면, 너는 마땅히 있어야 한다.

// 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
}

나는 진심으로 네가 이 과정을 좋아하고 너무 어지럽지 않기를 바란다.프랑스 학생으로서 처음으로 이야기를 써 보았습니다. 어떤 피드백도 환영합니다!:)
거리와 문자열을 비교한 소스 라이브러리 Go-Edlib을 편집했습니다.
그것은 가장 유행하는 편집 거리 알고리즘을 실현했다. 곧 이 알고리즘들을 모두 실현했다.현재 Levenshtein, LCS, Hamming, Damerau Levenshtein(OSA와 인접 변환 알고리즘), Jaro/Jaro-Winkler를 포함한다.
모든 이 알고리즘의 실현 방식은 유니코드와 완전히 호환된다
편집 거리를 기반으로 한 모호한 검색 알고리즘과 다른 문자열 비교 함수도 포함된다.
이 라이브러리를 개선하거나 새로운 기능 아이디어를 추가하기 위해 피드백과/또는 공헌을 적극적으로 찾고 있습니다!