[algorithm] cascaded multi word multi pattern matching - dsindex/blog GitHub Wiki
- n개의 패턴이 있다고 가정하자.
예)
a b c
x y
b c d e
e f
- 순서를 유지하면서 불연속적인 패턴매칭이 필요한 경우, 어떤 알고리즘을 사용해야 효율적일까?
예)
in = 'axybzcode'
match = 'abc', 'xy', 'bcde'
- 모든 패턴에 대해서 최대 길이(토큰 단위)를 m이라고 하자. m개의 column을 생성한다.
예)
column-0
a
x
b
e
column-1
b
y
c
f
column-2
c
d
column-3
e
- 또한, 원본 패턴 파일을 만든다.
예)
a b c
x y
b c d e
e f
-
생성된 모든 column에 대해 AC(Aho-Corasick)를 빌드하고, 원본 패턴 파일도 TRIE로 만든다. 원본 패턴이 필요한 이유는 matching 결과를 validation 할 때 필요하기 때문이다.
-
code snippet
...
static void push_buffer(char* buf, int* limit, char* token)
{
char* p;
p = buf;
if( buf[0] != '\0' ) {
p = xstrlcat(p, " ", limit);
}
p = xstrlcat(p, token, limit);
}
static void pop_buffer(char* buf, int* limit)
{
char* p;
int before;
int after;
/*
* buf : a b c
* limit : 100
* ->
* buf : a b
* limit : 102
*
*/
before = strlen(buf);
p = strrchr(buf, ' ');
if( p ) {
*p = '\0';
after = strlen(buf);
*limit = *limit + (before - after);
} else {
buf[0] = '\0';
*limit = BUFFER_SIZE_MAX;
}
}
static int is_valid_boundary(char* string, int bpos, int epos)
{
...
}
static int filter_func(ac_obj_t** filter_ac,
int column,
trie_obj_t* filter_trie,
char* string,
char* buf,
int* limit)
{
...
// condition for termination
strval = check_trie(filter_trie, buf);
if( strval ) {
debug(
fprintf(stdout, "[FILTER TRIE MATCH]\t%d,%s,%s\n", column, buf, strval);
);
return 1;
}
if( column >= MAX_COLUMN ) return 0;
ac = filter_ac[column];
num = ac_search(ac, string, &val);
if( num != 0 ) {
for( i=0; i<num; i++ ) {
if(val != NULL) {
...
if( !is_valid_boundary(string, bpos, epos) ) {
profile(
fprintf(stdout, "[BOUNDARY]\t%s\t%d\t%d\t%s\t%s\n", string, bpos, epos, val->key->data, &string[bpos]);
);
val = val->next;
continue;
}
push_buffer(buf, limit, (char*)ac_data_key->data);
debug(
fprintf(stdout, "[FILTER AC(%d) MATCH]\t%d/%d\t%d,%d,%s,%s,%s\n", column, i, num-1, bpos, epos, val->key->data, val->val->data, buf);
);
ret = filter_func(filter_ac, column+1, filter_trie, &string[epos], buf, limit);
// termination
if( ret ) {
ac_val_clear(val);
return 1;
}
pop_buffer(buf, limit);
}
val = val->next;
}
}
ac_val_clear(val);
return 0;
}
int filter(res_t* res, char* string)
{
char buf[BUFFER_SIZE_MAX+1];
int limit = BUFFER_SIZE_MAX;
int ret;
if( string == NULL || *string == '\0' ) return 0;
buf[0] = '\0';
ret = filter_func(res->filter_ac, 0, res->filter_trie, string, buf, &limit);
return ret;
}
-
위 코드에서는 해당 패턴이 하나라도 매칭되면 리턴되기 때문에 filter로 활용하기 적합하다.
-
이런 방식을 알고리즘을 사용할 때, 장단점은 어떨까?
단점을 들자면,
예를 들어, m은 10이고, 모든 column에 ‘a’가 존재하는 경우,
입력 문자열이 ‘aaaaaaaaaa’라고 하면
첫번째 filter_func()에서 ‘a’는 10번 매칭된다.
각각의 포지션에 대해 recursive call을 수행하기때문에
최악의 경우 10 factorial 만큼 호출하게되는 문제가 있다.
장점은 패턴을 구성하는 token의 순서(order)를 구분해서
패턴매칭을 수행할 수 있다는 점과 m 값을 실제보다 작게해서
부분만 매칭되면 filter를 통과했다고 간주하는 경우에
응용 가능하다는 점을 들 수 있다.
- 이런 방식 말고 다른 방법이 있다면?
패턴에 대해서 inverted index를 만들어서 활용하는 방법도
있다.
예)
pattern array
1 a b c 3^1 2 3
2 x y 2^7 8
3 b c d e 4^2 3 4 5
4 e f 2^5 6
inverted index
a 1^1
b 1 3^2
c 1 3^3
d 3^4
e 3 4^5
f 4^6
x 2^7
y 2^8
첫번째 파일은 메모리에 구조체 배열로 저장하고, 두번째는 AC로 빌드한다.
입력으로 아래와 같이 들어오는 경우,
in = ‘axybzcode’
ac 매칭을 한번 수행하면
a,x,y,b,c,d,e 매칭되고
해당하는 패턴의 번호에 token 번호를 저장한다.
1 1,2,3
2 7,8
3 2,3,4,5
4 5
이제 매칭된 결과와 pattern array를 비교해서
실제로 매칭된 패턴을 뽑으면,
a b c
x y
b c d e
패턴이 대량인 경우에는 패턴 매칭된 결과를 저장하는 중간 자료구조가
커질 수 있는데, 이 문제만 제외하면 매우 효과적인 방식으로 볼 수 있다.