주어진 두 문자열의 거리 유사성 측정을 계산하는 방법은 무엇입니까?
두 문자열의 유사성을 계산해야합니다. 그래서 정확히 무엇을 의미합니까? 예를 들어 설명하겠습니다.
- 진짜 단어 :
hospital - 잘못된 단어 :
haspita
이제 내 목표는 실제 단어를 얻기 위해 잘못된 단어를 수정해야하는 문자 수를 결정하는 것입니다. 이 예에서는 2 개의 문자를 수정해야합니다. 그렇다면 백분율은 얼마입니까? 나는 항상 진짜 단어의 길이를 취합니다. 따라서 2/8 = 25 %가되므로이 2 개의 주어진 문자열 DSM은 75 %가됩니다.
성능을 주요 고려 사항으로 삼고이를 어떻게 달성 할 수 있습니까?
찾고있는 것은 편집 거리 또는 Levenshtein 거리 입니다. 위키 백과 문서는 계산 방법을 설명하고 하단에 멋진 의사 코드를 제공하여 C #에서이 알고리즘을 매우 쉽게 코딩 할 수 있도록합니다.
다음은 아래 링크 된 첫 번째 사이트의 구현입니다.
private static int CalcLevenshteinDistance(string a, string b)
{
if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)) {
return 0;
}
if (String.IsNullOrEmpty(a)) {
return b.Length;
}
if (String.IsNullOrEmpty(b)) {
return a.Length;
}
int lengthA = a.Length;
int lengthB = b.Length;
var distances = new int[lengthA + 1, lengthB + 1];
for (int i = 0; i <= lengthA; distances[i, 0] = i++);
for (int j = 0; j <= lengthB; distances[0, j] = j++);
for (int i = 1; i <= lengthA; i++)
for (int j = 1; j <= lengthB; j++)
{
int cost = b[j - 1] == a[i - 1] ? 0 : 1;
distances[i, j] = Math.Min
(
Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1),
distances[i - 1, j - 1] + cost
);
}
return distances[lengthA, lengthB];
}
나는 몇 주 전에 똑같은 문제를 해결했습니다. 누군가 지금 물어 보니까 코드를 공유하겠습니다. 철저한 테스트에서 내 코드는 최대 거리가 제공되지 않은 경우에도 Wikipedia의 C # 예제보다 약 10 배 빠릅니다. 최대 거리가 제공되면이 성능 이득은 30x-100x +로 증가합니다. 성능에 대한 몇 가지 핵심 사항에 유의하십시오.
- 동일한 단어를 계속해서 비교해야하는 경우 먼저 단어를 정수 배열로 변환하십시오. Damerau - Levenshtein 알고리즘은 많은>, <, == 비교를 포함하고
ints훨씬 더 빨리보다 비교chars. - 거리가 제공된 최대 값을 초과하는 경우 종료하는 단락 메커니즘이 포함되어 있습니다.
- 내가 다른 곳에서 본 모든 구현에서와 같이 거대한 매트릭스 대신 회전하는 세 배열 세트를 사용하십시오.
- 배열이 더 짧은 단어 너비에 걸쳐 슬라이스되는지 확인하십시오.
바꿀 경우 코드 (이 동일한 동작 int[]으로 String매개 변수 선언에서 :
/// <summary>
/// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of
/// integers, where each integer represents the code point of a character in the source string.
/// Includes an optional threshhold which can be used to indicate the maximum allowable distance.
/// </summary>
/// <param name="source">An array of the code points of the first string</param>
/// <param name="target">An array of the code points of the second string</param>
/// <param name="threshold">Maximum allowable distance</param>
/// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns>
public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) {
int length1 = source.Length;
int length2 = target.Length;
// Return trivial case - difference in string lengths exceeds threshhold
if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; }
// Ensure arrays [i] / length1 use shorter length
if (length1 > length2) {
Swap(ref target, ref source);
Swap(ref length1, ref length2);
}
int maxi = length1;
int maxj = length2;
int[] dCurrent = new int[maxi + 1];
int[] dMinus1 = new int[maxi + 1];
int[] dMinus2 = new int[maxi + 1];
int[] dSwap;
for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; }
int jm1 = 0, im1 = 0, im2 = -1;
for (int j = 1; j <= maxj; j++) {
// Rotate
dSwap = dMinus2;
dMinus2 = dMinus1;
dMinus1 = dCurrent;
dCurrent = dSwap;
// Initialize
int minDistance = int.MaxValue;
dCurrent[0] = j;
im1 = 0;
im2 = -1;
for (int i = 1; i <= maxi; i++) {
int cost = source[im1] == target[jm1] ? 0 : 1;
int del = dCurrent[im1] + 1;
int ins = dMinus1[i] + 1;
int sub = dMinus1[im1] + cost;
//Fastest execution for min value of 3 integers
int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del);
if (i > 1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2])
min = Math.Min(min, dMinus2[im2] + cost);
dCurrent[i] = min;
if (min < minDistance) { minDistance = min; }
im1++;
im2++;
}
jm1++;
if (minDistance > threshold) { return int.MaxValue; }
}
int result = dCurrent[maxi];
return (result > threshold) ? int.MaxValue : result;
}
어디에 Swap:
static void Swap<T>(ref T arg1,ref T arg2) {
T temp = arg1;
arg1 = arg2;
arg2 = temp;
}
사용할 수있는 많은 수의 문자열 유사성 거리 알고리즘이 있습니다. 여기에 나열된 일부 (완전히 나열되지는 않음) :
- Levenstein
- Needleman Wunch
- 스미스 워터맨
- 스미스 워터맨 고토
- Jaro, Jaro Winkler
- Jaccard 유사성
- 유클리드 거리
- 주사위 유사성
- 코사인 유사성
- 몽지 엘칸
이들 모두에 대한 구현을 포함하는 라이브러리를 Java 및 C # 구현이 모두있는 SimMetrics 라고 합니다.
나는 것을 발견했다 Levenshtein 및 JARO 윈 클러가 같은 문자열 타협 작은 차이를 위해 중대하다 :
- 철자 오류; 또는
- 사람 이름에서 o 대신 ö .
그러나 텍스트의 상당 부분은 동일하지만 가장자리에 "노이즈"가있는 기사 제목과 같은 것을 비교할 때 Smith-Waterman-Gotoh 는 환상적이었습니다.
다음 2 개의 제목을 비교하십시오 (동일하지만 다른 출처에서 다른 단어로 표시됨).
자외선 조사 DNA에 단일 폴리 뉴클레오티드 사슬 가위를 도입하는 대장균 의 엔도 뉴 클레아 제
엔도 뉴 클레아 제 III : 자외선 조사 DNA에서 단일 폴리 뉴클레오타이드 사슬 가위를 도입하는 대장균의 엔도 뉴 클레아 제
문자열의 알고리즘 비교를 제공하는이 사이트 는 다음을 보여줍니다.
- 레벤 슈타인 : 81
- 스미스-워터맨 고토 94
- 자로 윙클러 78
Jaro Winkler와 Levenshtein은 유사성을 감지하는 데 Smith Waterman Gotoh만큼 유능하지 않습니다. 동일한 기사는 아니지만 일치하는 텍스트가있는 두 제목을 비교하는 경우 :
고등 식물의 지방 대사. 아실-코엔자임 A 및 아실-아실 운반 단백질 s 의 대사에서 아실 티오 에스 테라 제의 기능
고등 식물의 지방 대사. 복잡한 지질 혼합물에서 아실-아실 운반 단백질 및 아실 코엔자임 A 의 결정
Jaro Winkler는 위양성을 제공하지만 Smith Waterman Gotoh는 다음과 같이하지 않습니다.
- 레벤 슈타인 : 54
- 스미스-워터맨 고토 49
- 자로 윙클러 89
으로 Anastasiosyal는 지적 SimMetrics는 이러한 알고리즘의 자바 코드가 있습니다. SimMetrics 의 SmithWatermanGotoh 자바 코드를 사용하여 성공 했습니다 .
여기 Damerau Levenshtein Distance의 구현은 유사성 계수뿐만 아니라 수정 된 단어로 오류 위치를 반환합니다 (이 기능은 텍스트 편집기에서 사용할 수 있음). 또한 내 구현은 다양한 오류 가중치 (대체, 삭제, 삽입, 전치)를 지원합니다.
public static List<Mistake> OptimalStringAlignmentDistance(
string word, string correctedWord,
bool transposition = true,
int substitutionCost = 1,
int insertionCost = 1,
int deletionCost = 1,
int transpositionCost = 1)
{
int w_length = word.Length;
int cw_length = correctedWord.Length;
var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1];
var result = new List<Mistake>(Math.Max(w_length, cw_length));
if (w_length == 0)
{
for (int i = 0; i < cw_length; i++)
result.Add(new Mistake(i, CharMistakeType.Insertion));
return result;
}
for (int i = 0; i <= w_length; i++)
d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None);
for (int j = 0; j <= cw_length; j++)
d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None);
for (int i = 1; i <= w_length; i++)
{
for (int j = 1; j <= cw_length; j++)
{
bool equal = correctedWord[j - 1] == word[i - 1];
int delCost = d[i - 1, j].Key + deletionCost;
int insCost = d[i, j - 1].Key + insertionCost;
int subCost = d[i - 1, j - 1].Key;
if (!equal)
subCost += substitutionCost;
int transCost = int.MaxValue;
if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1])
{
transCost = d[i - 2, j - 2].Key;
if (!equal)
transCost += transpositionCost;
}
int min = delCost;
CharMistakeType mistakeType = CharMistakeType.Deletion;
if (insCost < min)
{
min = insCost;
mistakeType = CharMistakeType.Insertion;
}
if (subCost < min)
{
min = subCost;
mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution;
}
if (transCost < min)
{
min = transCost;
mistakeType = CharMistakeType.Transposition;
}
d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType);
}
}
int w_ind = w_length;
int cw_ind = cw_length;
while (w_ind >= 0 && cw_ind >= 0)
{
switch (d[w_ind, cw_ind].Value)
{
case CharMistakeType.None:
w_ind--;
cw_ind--;
break;
case CharMistakeType.Substitution:
result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution));
w_ind--;
cw_ind--;
break;
case CharMistakeType.Deletion:
result.Add(new Mistake(cw_ind, CharMistakeType.Deletion));
w_ind--;
break;
case CharMistakeType.Insertion:
result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion));
cw_ind--;
break;
case CharMistakeType.Transposition:
result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition));
w_ind -= 2;
cw_ind -= 2;
break;
}
}
if (d[w_length, cw_length].Key > result.Count)
{
int delMistakesCount = d[w_length, cw_length].Key - result.Count;
for (int i = 0; i < delMistakesCount; i++)
result.Add(new Mistake(0, CharMistakeType.Deletion));
}
result.Reverse();
return result;
}
public struct Mistake
{
public int Position;
public CharMistakeType Type;
public Mistake(int position, CharMistakeType type)
{
Position = position;
Type = type;
}
public override string ToString()
{
return Position + ", " + Type;
}
}
public enum CharMistakeType
{
None,
Substitution,
Insertion,
Deletion,
Transposition
}
이 코드는 내 프로젝트의 일부입니다 : Yandex-Linguistics.NET .
몇 가지 테스트를 작성 했는데 방법이 작동하는 것 같습니다.
그러나 의견과 발언은 환영합니다.
다음은 다른 방법입니다.
댓글이 너무 깁니다.
유사성을 찾는 일반적인 방법은 Levenshtein 거리이며 사용 가능한 코드가있는 라이브러리는 의심 할 여지가 없습니다.
Unfortunately, this requires comparing to every string. You might be able to write a specialized version of the code to short-circuit the calculation if the distance is greater than some threshold, you would still have to do all the comparisons.
Another idea is to use some variant of trigrams or n-grams. These are sequences of n characters (or n words or n genomic sequences or n whatever). Keep a mapping of trigrams to strings and choose the ones that have the biggest overlap. A typical choice of n is "3", hence the name.
For instance, English would have these trigrams:
- Eng
- ngl
- gli
- lis
- ish
And England would have:
- Eng
- ngl
- gla
- lan
- and
Well, 2 out of 7 (or 4 out of 10) match. If this works for you, and you can index the trigram/string table and get a faster search.
You can also combine this with Levenshtein to reduce the set of comparison to those that have some minimum number of n-grams in common.
Here's a VB.net implementation:
Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer
Dim cost(v1.Length, v2.Length) As Integer
If v1.Length = 0 Then
Return v2.Length 'if string 1 is empty, the number of edits will be the insertion of all characters in string 2
ElseIf v2.Length = 0 Then
Return v1.Length 'if string 2 is empty, the number of edits will be the insertion of all characters in string 1
Else
'setup the base costs for inserting the correct characters
For v1Count As Integer = 0 To v1.Length
cost(v1Count, 0) = v1Count
Next v1Count
For v2Count As Integer = 0 To v2.Length
cost(0, v2Count) = v2Count
Next v2Count
'now work out the cheapest route to having the correct characters
For v1Count As Integer = 1 To v1.Length
For v2Count As Integer = 1 To v2.Length
'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required)
'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1),
'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and
cost(v1Count, v2Count) = Math.Min(
cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1),
Math.Min(
cost(v1Count - 1, v2Count) + 1,
cost(v1Count, v2Count - 1) + 1
)
)
Next v2Count
Next v1Count
'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix
'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length)
Return cost(v1.Length, v2.Length)
End If
End Function
'IT Share you' 카테고리의 다른 글
| ASP MVC-기본 콘텐츠 형식에 대한 상수가 있습니까? (0) | 2020.12.13 |
|---|---|
| 명시 적 및 암시 적 C # (0) | 2020.12.13 |
| Xcode에서 특정 방법으로 이동하는 방법이 있습니까? (0) | 2020.12.13 |
| 플롯 영역에 상대적인 범례 배치, ggplot (0) | 2020.12.13 |
| 두 UIImage 객체를 비교하는 방법 (0) | 2020.12.13 |