퍼지 검색

Fuzzy-search 검색어가 정확하지 않아도 유사한 항목을 찾아주는 검색 방식이다. 유전정보를 활용하는 생물학 분야 혹은 문자열 검색 등 여러 분야에 쓰이는데 이중 파일명을 검색하거나 함수 메서드등을 검색하는 기능이 아주 유용해 보인다.

사례

Sublime Text의 검색 기능을 들수 있다. 그리고 이 기능에 대해 궁금한 사람이 있었던 모양이다. 이런 Article 이 있다. 그리고 최근에 발견한 툴인데 fzf 라는 fuzzy-finder 가 있다. 아주 훌륭한 tool이고 정말 멋지다. 이 프로그램은 자기가 필요한 일만 멋지고 충분하게 딱 해내고 Cool하게 끝낸다. 정말 대단한 프로그램이다. 이건 한국사람이 만들었다.

알고리즘?

Sublime Text 관련 분석 블로그의 글에서 구현한 소스코드 는 구체적으로 어떤 알고리즘을 썼는지 명확하진 않다. 재귀호출로 처리하고 있다.

재귀적인 방법

자세히 이해하지 말고 대략적인 느낌만 살펴보자

  1. 문자열을 하나씩 살피면서 패턴의 맨 앞글자와 비교
  2. 일치하지 않으면 다음 문자 확인
  3. 일치하는 경우 문자열 하나 증가시켜서 재귀호출한다.
  4. 재귀호출결과중 가장 좋은 점수를 고른다.
  5. 현재 매칭을 기록하고 패턴문자 하나 증가
  6. 패턴문자가 NULL문자를 만났을때 match
  7. 그러면 각 매칭된 부분을 읽고 스코어 기준에 따라 점수를 매김

대략적으로 코드를 파악해본 결과는 위와 같다. 재귀적으로 가능한 패턴 위치를 탐색해서 가능 모든 조합에 대해서 점수를 매긴다. 가장 좋은 점수를 재귀호출 결과에서 계속적으로 업데이트한다. 이때 점수는 몇가지 기준에 따라서 매기게 된다.

  1. 일치하는 문자 + 0
  2. 연속 일치 문자 +5
  3. 시작거리 -1
  4. 구분기호 뒤 문자 + 10
  5. 대문자 (CamelCase) + 10

이런식으로 각 경우에 따라서 점수를 매기는데 차감도 가능하다.

fzf 의 알고리즘

fzf는 매우 친절하다. 소스코드 algo 부분 찾아 들어가면 알고리즘에 대해서 자세히 나온다. Smith-Waterman algorithm을 수정하여 사용하는 것으로 나온다.

algo

알고리즘을 시각화 하면 대략 위 GIF와 같은 느낌으로 진행이 된다. 저건 마치 일부 Dynamic Programming 해법 같아 보인다. 왼쪽으로 이동시 값이 차감되는 것을 볼 수 있는데 이걸 Gap-penalty 라고 한다. 즉 일치하는 부분이 멀리 떨어질수록 점수를 점점 낮춰버리는 효과를 주는 것이다.

fzf는 위 알고리즘 외에도 여러가지 구현이 있고 unicode 및 각종 케이스를 감안한 로직이 있어서 이해하기 난해한 면이 있다. 하지만 위 Smith-Waterman algorithm이 핵심 로직이라는 사실을 이해하고 살펴보면 될 것 같다.

설계하기

Smith-Waterman algorithm을 응용해서 구현하는게 간단하면서도 빠른성능을 보여줄 것 같다. 원래 염기서열의 부분 일치 등을 찾는 알고리즘 이지만 이를 텍스트에서 부분일치 패턴과 매치를 시키기 위해 몇가지 사항을 고려해 보자

  • 패턴 길이가 검색 대상 문자열보다 짧다.
  • 패턴 문자는 전부 매칭되어야 한다.
  • 텍스트에서 특정부분은 보너스 점수를 얻는다.
  • 연속 매칭되는 부분을 좀더 우위를 준다.

위 fzf의 gif 그림파일로도 알수 있듯이 왼쪽 상단부터 오른쪽 하단 방향으로 어떤 점수를 기록하고 비교해서 큰것을 입력하면서 내려온뒤에 전부 다 기록이 된뒤 거꾸로 큰 값을 기준으로 거꾸로 찾아 올라가며 경로를 찾아낸다. 이건 완전히 점화식이 몇가지 방향으로 분리되는 Dynamic Programming 방식이다. 이때 패턴문자가 전부 매칭되어야 한다는 사실을 생각해보고 row에 패턴문자를 column에 텍스트 문자를 배치시켜보자

TXT
    pat:[rr]
    txt:[ReadMe]

    | R, e, a, d, M, e
   -+-----------------
   r|
   r|

패턴을 전부 매칭시키는 방법

방법은 위로가는 방향은 빼고 대각선, 왼쪽 두방향으로만 검색해서 최대값을 기록해 나가면 된다. 위로 올라가는 방향은 없으니 패턴은 항상 매칭이 될 수 밖에 없다.

TXT
     --t--tt---t-----tt
    r->\
    r---->\
    r      \-------->\
    r           \---->\

대략 위와 같은 느낌으로 이해하면 된다. 패턴문자(row)는 하나도 빠짐없이 매칭 되며 매칭되었을때는 대각선으로 하강한다. 텍스트문자는 중간중간 건너 뛰는 것을 볼 수 있다. 이를 Gap이라고 부르며 멀리 떨어질수록 Penalty 를 받게 된다.

최대값을 어떻게 선택하는가

위와 같은 상황에서 어떤 r번째 row와 c번째 col 상황을 가정해보자 이때 대각선 위의 값을 T(r-1, c-1) 이라고 가정하고 왼쪽을 T(r , c-1) 이라고 하자. 현재 T(r,c) 값을 두 값중 큰 값으로 선택한다고 했을때 T(r-1, c-1) 이 값도 사실 그 이전에 큰 값으로 선택해온 값이다. T(r, c-1) 도 마찬가지다. 이는 재귀적 구조를 지니고 있어 Dynamic Programming문제라고 할 수 있다.

r-2 r-1 r r+1
c-2 … … … …
c-1 … T(r-1, c-1) … …
c … T(r , c-1) 큰값을 선택
c+1 … … … …

보너스 점수는 어떻게 정하고 더하는가

보너스 점수는 파일경로와 같은 텍스트를 찾을때 디렉토리를 구분해주는 구분문자 그리고 파일명 디렉토리명에서 CamelCase 등에 좀더 매칭이 잘되게 하고 싶을때 보너스점수를 주는 것이다.

TXT
 pat:    tic
 txt:    /thits/iis/testcCase
 result: /[t]hits/[i]is/testc[C]ase

위와 같은 사례를 보면 앞 디렉토리명에서 t 는 두번 나오지만 /t 와 같이 경계에 붙어있는 문자로 선택을 하도록 유도한다. testcCase 도 마찬가지로 대문자C 앞에 소문자c가 먼저 나왔지만 CamelCase 를 더 선호하기 때문에 C를 선택한다.

fzf의 각종 점수는 다음과 같다.

  1. match 되었을 경우 : 16점
  2. 경계문자 : 8점
  3. 워드가 아닌 문자: 8점
  4. CamelCase : 7점
  5. 연속매칭 : 4점
  6. 갭페널티(최초발생) : -3점
  7. 갭페널티 : -1점

연속 매칭은 좀더 특수한 경우이다.

연속 매칭

연속이 발생하면 보너스를 주는 식으로 만들게 되면 어느 순간 너무 과도하게 연속에만 붙어버리는 현상이 관찰되었다. 이를 어떻게 해결하였을지 fzf를 살펴본 결과.. 현재보너스값, 연속매칭보너스값, 최초시작문자의보너스값 중 최대를 고른다. 계속 누적시키지 않았다!! 이런 것은 많은 실험을 거치면서 조정된 값들이라 믿을만 한 것 같다.

구현하기

점수배열은 가로,세로 하나 크게 작성

대각선과 왼쪽 값을 비교하는 로직이 있기 때문에 이 로직을 자연스럽게 반영하기 위해 matrix는 가로,세로 하나씩 큰 값으로 선택하여 0번째 row, 0번째 col은 비워두는 것이 좋아보인다. 사실 2차원 배열로 하지 않고 1차원배열로 만든뒤 인덱싱을 해서 구현했다.

C
    int colsize = strlen(txt) + START_IDX;
    int rowsize = strlen(pat) + START_IDX;
#define IDX(r,c) (((r) * colsize) + (c))

보너스 사전정보

경계문자, CamelCase, no-alnum 등은 사실 입력텍스트만 보고도 기록해 놓을 수 있다.

C
    /* 보너스 계산 */
    char t_cur, t_pre = 0;

    for(int col = START_IDX; col < colsize; col++)
    {
        t_cur = txt[col-START_IDX];

        if(isalnum(t_pre) == 0 && isalnum(t_cur))
            bonus[col] = g_bonus_boundary;
        else if(isalnum(t_cur) == 0)
            bonus[col] = g_bonus_no_alnum;
        else if(islower(t_pre) && isupper(t_cur))
            bonus[col] = g_bonus_camel;

        t_pre = t_cur;
    }

각 Row에서 첫번째 col 정하기

첫번째 패턴문자를 일치부분을 끝내고 그 다음 패턴문자를 가지고 작업할때 사실 첫번째 row를 사용했기 때문에 첫번째 매칭 col 이후부터 시작하면 된다. 이는 대략적으로 절반 정도 탐색 공간을 줄여준다.

C
int first_col_in_a_row = START_IDX;
...
for(int row=START_IDX; row < rowsize; row++)
{
    ...
    int is_first = 0; /* false */
    ...
    for(int col = first_col_in_a_row; col < colsize; col++)
    {
        ...
        /* match */
        if(tolower(p_cur) == tolower(t_cur))
        {
            /* 첫번째 시작 col 기록 */
            if(is_first == 0)
            {
                is_first = 1;
                first_col_in_a_row = col+1;
            }

대각선, 왼쪽 선택하기

위에서 설계한 대로 고르되 중요한 점은 대각선을 선택할 시에는 지금 패턴을 매칭하였을 때 인 것이고 왼쪽을 선택할 시에는 매칭하지 않고 갭 페널티까지 적용되었을 때 인 것이다.

C
/* 왼쪽 점수 결정 */
if(is_gap)
    left_score += g_penalty_ingap;
else
    left_score += g_penalty_firstgap; /* 첫 연속 실패시 패널티가 크다. */

/* 매칭시 */
if(tolower(p_cur) == tolower(t_cur))
{
    ...
    
    /* 대각선 */
    diag_score += g_score_match;

    /* 보너스 결정 */
    bonus_score = bonus[col];
    
    ...

    /* 대각선이 더 큰경우 패턴 선택 */
    if(left_score < diag_score + bonus_score)
        is_select = 1; /* true */
}
/* 선택되면 대각선, 안될경우 왼쪽 선택한다. */
if(is_select)
{
    is_gap = 0; /* false */
    matrix[IDX(row, col)] = diag_score + bonus_score;
    ...
}
else
{
    is_gap = 1; /* true */
    matrix[IDX(row  , col)] = left_score ;
}
/* 음수값 처리 */
if(matrix[IDX(row  , col)] < 0)
    matrix[IDX(row  , col)] = 0;

연속처리

C
/* 연속 개수 선정 */
cont_cnt = cont[IDX(row-1, col-1)] + 1;

/* 대각선 */
diag_score += g_score_match;

/* 보너스 결정 */
bonus_score = bonus[col];
if(cont_cnt > 1)
{
    /* 연속이면 현재보너스, 연속보너스점수, 연속시작문자보너스 중 최대값을 선정해서 정함 */
    if(bonus_score < g_bonus_continuous)
        bonus_score = g_bonus_continuous;
    if(bonus_score < bonus[col - cont_cnt + 1])
        bonus_score = bonus[col - cont_cnt + 1];
    bonus_score += 1;
}

역추적해서 패턴 위치 알아내기

기록해온 것의 반대방향으로 하면 된다.

C
    /* 역추적 */
    int back_row = rowsize - 1;
    int back_col = max_col;
    while(back_row >= START_IDX)
    {
        if(matrix[IDX(back_row, back_col-1)] <= matrix[IDX(back_row, back_col)])
        {
            back_row--; 
            position[back_col - START_IDX] = 1;
        }
        back_col --;
    }

구현결과

fzc 라는 툴을 만들었다. 파일을 퍼지검색으로 찾아내는 유틸이다. C언어로 작성하였다. unix , linux 등에서 사용할 수 있다. curses와 디렉토리 순회 등의 기능을 구현하여 유틸로 만들었다.

그 외 생각할 것들

  • 유니코드 지원, 멀티바이트 문자