내가 대신 Levenshtein 거리의 Longest Common Subsequence의 길이를 사용한다고 생각합니다. 그것은 귀하의 경우에 대한 더 나은 척도가되는 것 같습니다. 본질적으로, 그것은 내 의견에서 제안했듯이, 대체보다 삽입과 삭제를 우선시합니다.
"Ing"-> "Ingersoll"과 "Ing"-> "Boylan"(3 점과 1 점) 사이의 공백은 문제없이 처리됩니다 ("New Ing"-> "New Ingersoll" 여기서 "New Ing"-> "Boylan"은 다시 1 점을받습니다) "Ingsl"과 같은 약어를 사용하면 잘 작동합니다.
알고리즘은 간단합니다. 두 개의 문자열 길이가 m 및 n 인 문자열의 연속 접두사를 빈 접두어로 비교하고 크기가 m + 1, n + 1 인 행렬에 점수를 유지하십시오. 특정 쌍이 일치하는 경우 이전 두 접두사의 점수에 1을 더합니다 (매트릭스에 한 행 위로 한 열). 그렇지 않으면 그 접두사의 두 점수 중 가장 높은 점수를 유지하십시오 (바로 위의 항목과 즉시 남은 항목을 비교하여 최상을 취하십시오). 두 문자열을 모두 살펴 보았을 때 점수 매트릭스의 마지막 항목은 LCS의 길이입니다. "Ingsll"와 "잉거 솔"에 대한
예 점수 매트릭스 :
0 1 2 3 4 5 6
I n g s l l
---------------
0 | 0 0 0 0 0 0 0
1 I | 0 1 1 1 1 1 1
2 n | 0 1 2 2 2 2 2
3 g | 0 1 2 3 3 3 3
4 e | 0 1 2 3 3 3 3
5 r | 0 1 2 3 3 3 3
6 s | 0 1 2 3 4 4 4
7 o | 0 1 2 3 4 4 4
8 l | 0 1 2 3 4 5 5
9 l | 0 1 2 3 4 5 6
여기 길이의 ObjC 구현입니다. 여기서 복잡성의 대부분은 구성된 문자 시퀀스 (예 : @"o̶")를 올바르게 처리하려고하기 때문입니다.
#import <Foundation/Foundation.h>
@interface NSString (WSSComposedLength)
- (NSUInteger)WSSComposedLength;
@end
@implementation NSString (WSSComposedLength)
- (NSUInteger)WSSComposedLength
{
__block NSUInteger length = 0;
[self enumerateSubstringsInRange:(NSRange){0, [self length]}
options:NSStringEnumerationByComposedCharacterSequences | NSStringEnumerationSubstringNotRequired
usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
length++;
}];
return length;
}
@end
@interface NSString (WSSLongestCommonSubsequence)
- (NSUInteger)WSSLengthOfLongestCommonSubsequenceWithString:(NSString *)target;
- (NSString *)WSSLongestCommonSubsequenceWithString:(NSString *)target;
@end
@implementation NSString (WSSLongestCommonSubsequence)
- (NSUInteger)WSSLengthOfLongestCommonSubsequenceWithString:(NSString *)target
{
NSUInteger * const * scores;
scores = [[self scoreMatrixForLongestCommonSubsequenceWithString:target] bytes];
return scores[[target WSSComposedLength]][[self WSSComposedLength]];
}
- (NSString *)WSSLongestCommonSubsequenceWithString:(NSString *)target
{
NSUInteger * const * scores;
scores = [[self scoreMatrixForLongestCommonSubsequenceWithString:target] bytes];
//FIXME: Implement this.
return nil;
}
- (NSData *)scoreMatrixForLongestCommonSubsequenceWithString:(NSString *)target{
NSUInteger selfLength = [self WSSComposedLength];
NSUInteger targetLength = [target WSSComposedLength];
NSMutableData * scoresData = [NSMutableData dataWithLength:(targetLength + 1) * sizeof(NSUInteger *)];
NSUInteger ** scores = [scoresData mutableBytes];
for(NSUInteger i = 0; i <= targetLength; i++){
scores[i] = [[NSMutableData dataWithLength:(selfLength + 1) * sizeof(NSUInteger)] mutableBytes];
}
/* Ranges in the enumeration Block are the same measure as
* -[NSString length] -- i.e., 16-bit code units -- as opposed to
* _composed_ length, which counts code points. Thus:
*
* Enumeration will miss the last character if composed length is used
* as the range and there's a substring range with length greater than one.
*/
NSRange selfFullRange = (NSRange){0, [self length]};
NSRange targetFullRange = (NSRange){0, [target length]};
/* Have to keep track of these indexes by hand, rather than using the
* Block's substringRange.location because, e.g., @"o̶", will have
* range {x, 2}, and the next substring will be {x+2, l}.
*/
__block NSUInteger col = 0;
__block NSUInteger row = 0;
[target enumerateSubstringsInRange:targetFullRange
options:NSStringEnumerationByComposedCharacterSequences
usingBlock:^(NSString * targetSubstring,
NSRange targetSubstringRange,
NSRange _, BOOL * _0)
{
row++;
col = 0;
[self enumerateSubstringsInRange:selfFullRange
options:NSStringEnumerationByComposedCharacterSequences
usingBlock:^(NSString * selfSubstring,
NSRange selfSubstringRange,
NSRange _, BOOL * _0)
{
col++;
NSUInteger newScore;
if([selfSubstring isEqualToString:targetSubstring]){
newScore = 1 + scores[row - 1][col - 1];
}
else {
NSUInteger upperScore = scores[row - 1][col];
NSUInteger leftScore = scores[row][col - 1];
newScore = MAX(upperScore, leftScore);
}
scores[row][col] = newScore;
}];
}];
return scoresData;
}
@end
int main(int argc, const char * argv[])
{
@autoreleasepool {
NSArray * testItems = @[@{@"source" : @"Ingso̶ll",
@"targets": @[
@{@"string" : @"Ingersoll",
@"score" : @6,
@"sequence" : @"Ingsll"},
@{@"string" : @"Boylan",
@"score" : @1,
@"sequence" : @"n"},
@{@"string" : @"New Ingersoll",
@"score" : @6,
@"sequence" : @"Ingsll"}]},
@{@"source" : @"Ing",
@"targets": @[
@{@"string" : @"Ingersoll",
@"score" : @3,
@"sequence" : @"Ing"},
@{@"string" : @"Boylan",
@"score" : @1,
@"sequence" : @"n"},
@{@"string" : @"New Ingersoll",
@"score" : @3,
@"sequence" : @"Ing"}]},
@{@"source" : @"New Ing",
@"targets": @[
@{@"string" : @"Ingersoll",
@"score" : @3,
@"sequence" : @"Ing"},
@{@"string" : @"Boylan",
@"score" : @1,
@"sequence" : @"n"},
@{@"string" : @"New Ingersoll",
@"score" : @7,
@"sequence" : @"New Ing"}]}];
for(NSDictionary * item in testItems){
NSString * source = item[@"source"];
for(NSDictionary * target in item[@"targets"]){
NSString * targetString = target[@"string"];
NSCAssert([target[@"score"] integerValue] ==
[source WSSLengthOfLongestCommonSubsequenceWithString:targetString],
@"");
// NSCAssert([target[@"sequence"] isEqualToString:
// [source longestCommonSubsequenceWithString:targetString]],
// @"");
}
}
}
return 0;
}
할인 점수로 점수를 변경할 수 있습니까? 이 약어 사용 사례의 경우 삽입을 삽입하는 것보다 더 큰 거리로 대체해야하는 것처럼 보입니다. 당신은 내가 볼 수있는 한, 오자를 찾는 것이 아닙니다. –
맞아요, 대부분의 경우 시퀀스로 공백을 대체합니다. 그것은 실제로 큰 관찰입니다. 그래도 그걸 어떻게 생각하니? – Moshe
음, 득점의 세부 사항에 달려 있지만, 내가 말하는 것은 고전적인 Levenshtein 거리가 아니라 당신의 목적입니다. "I"- "B"는 "I"이상의 비용이들 것입니다. > "예". –