nx 와 ny 에 대한 각 bigrams 의 개수를 구하고 그 중에 중복된 bigrams의 개수를 nt 라고 한다.
예를 들면 아래와 같다.
ni
,ig
,gh
,ht
}na
,ac
,ch
,ht
}공식에 대입하면 아래와 같은 결과를 얻을 수 있다.
s = (2 · 1) / (4 + 4) = 0.25.
참고 url : http://en.wikipedia.org/wiki/Dice's_coefficient
ni
,ig
,gh
,ht
}na
,ac
,ch
,ht
}공식에 대입하면 아래와 같은 결과를 얻을 수 있다.
s = (2 · 1) / (4 + 4) = 0.25.
참고 url : http://en.wikipedia.org/wiki/Dice's_coefficient
접기
std::set<std::string> get_shingle(const std::string& str, int size)
{
std::set<std::string> shingle;
int length = (int)(str.size());
int max_pos = length - size;
int i = 0;
for(i = 0; i<=max_pos; i++){
shingle.insert(str.substr(i, size));
}
return shingle;
}
bool get_resemblance(
const std::string& str1,
const std::string& str2,
double *r, double *c1, double *c2)
{
std::set<std::string> s1 = get_shingle(str1, 2);
std::set<std::string> s2 = get_shingle(str2, 2);
if(s1.empty() == true || s2.empty() == true) return false;
std::set<std::string> com;
std::set<std::string> all;
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(com, com.begin()));
std::set_union(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::inserter(all, all.begin()));
double com_size = (double)(com.size());
double union_size = (double)(all.size());
*r = com_size/union_size;
*c1 = com_size/s1.size();
*c2 = com_size/s2.size();
return true;
}
접기
완성형의 한글 코드 영역은 다음과 같다. 완성형은 KSC5601 문자셋을 의미한다.
* 상위 바이트 : 0xBO ~ 0xC8
* 하위 바이트 : 0xA1 ~ 0xFE
확장 완성형의 한글 코드는 완성형의 한글 코드에 아래의 한글 코드 영역이 추가된다. 확장 완성형은 MS CP949 를 의미한다. 중간 중간 빈 공간을 채워 넣었기 때문에 아래의 코드 영역은 연속적이지 않다.
* 상위 바이트 : 0x81 ~ 0xC6
* 하위 바이트 : 0x41 ~ 0xFE
유니코드에서 한글 코드 영역은 다음과 같다.
* 0xAC00 ~ 0xD7A3
[출처] 완성형 / 확장 완성형 / 유니코드 한글 코드 영역|작성자 까미유
Simon proposes using a dictionary to match mistyped URLs with real ones. I’d probably like the idea better if I actually understood it. Still using Levenshtein can be a bit easier than using a spell checker responsively.
Easier, but slow. I used existing implementation by Magnus Lie Hetland and made a test with 245 blog titles using a simple script. 100 iterations on aging powerbook produced:
1.766s, 29.152s, 9.399s (min, max, avg)
Average time to calculate distance between randomly chosen title and rest of them is 9.4 seconds, which is far too much to be useful. And there’s not even 250 of them.
There are two obvious ways to speed things up. Since minimum distance is at least as much as a difference in length of both strings, there’s no point in calculating it when difference already exceeds a limit we chose.
The other trick took into an account that Levenshtein’s algorithm of two strings of comparable length has complexity of O(n2) and that my blog titles are form quite sparse space. If strings are longer than a certain limit (I arbitrarily chose 10 letters), then first calculate edit distance on a small sparse substring and then calculate the real distance only if first one was close enough.
When I made 1000 iterations of randomly chosen title using only first test, I got following results:
0.003s, 0.284s, 0.167s (min, max, avg)
However, if I used both checks, the same 1000 iteration test got me:
0.003s, 0.162s, 0.027s (min, max, avg)
So, two simple checks can speed up search up to 350 times. Not bad, but I’m not happy. This is certainly fast enough for a personal website or sites where site structure effectively divides searching to relatively small sets of possible hits, but there are plenty of sites where it would be too slow.
#pragma warning(disable:4996) #include <stdio.h> #include <stdlib.h> #include "Search.h" //상수 정의 enum { ARRAY_SIZE = 100, MAX_VALUE = 1000 }; void fillArray(int *array, int size); void printArray(const int *array, int size); int compare(const void *p1, const void *p2); void main(void) { int array[ARRAY_SIZE]; int value, pos; fillArray(array, ARRAY_SIZE); printArray(array, ARRAY_SIZE); //순차 탐색 printf("[순차 탐색]\n"); while(1) { printf("입력 : "); scanf("%d", &value); if(value < 0 || value >= MAX_VALUE) { break; } pos = linearSearch(array, ARRAY_SIZE, value); printf("결과 : %s\n\n", (pos != -1) ? "성공" : "실패"); } printf("\n\n"); //정렬 qsort(array, ARRAY_SIZE, sizeof(array[0]), compare); printArray(array, ARRAY_SIZE); //이진 탐색 printf("[이진 탐색]\n"); while(1) { printf("입력 : "); scanf("%d", &value); if(value < 0 || value >= MAX_VALUE) { break; } pos = linearSearchSort(array, ARRAY_SIZE, value); printf("순차 : %s\n\n", (pos != -1) ? "성공" : "실패"); pos = binarySearch(array, ARRAY_SIZE, value); printf("이진 : %s\n\n", (pos != -1) ? "성공" : "실패"); } } void fillArray(int *array, int size) { int i; for(i=0; i<size; i++) { array[i] = rand() % MAX_VALUE; } } void printArray(const int *array, int size) { int i; for(i=0; i<size; i++) { printf("%3d ", array[i]); if(i%10 == 9) { printf("\n"); } } printf("\n\n"); } int compare(const void *p1, const void *p2) { return *(int*) p1 - *(int*) p2; }