스물세번째 날: 오타를 허용하는 문자열 일치

저자

skyloader - 심지어 게으른 만년 Perl 초보자, 치킨을 먹기위해 Perl을 배운다는 후문, @JEEN_LEE와 동갑, skyloader at gmail.com

시작하며

펄은 문자열을 다루는데 아주 효율적인 언어입니다. 제 경우 업무와 관련해 문자열을 다뤄야 할 일이 생기면 으레 use strict;으로 시작하는 펄 코드를 작성해서 간단히 해결하곤 합니다. 하지만 회사의 모든 사람이 이나 파이썬, 루비와 같은 프로그래밍 언어를 능수능란하게 다루며 스크립트를 작성해 문자열을 일관되게 다루는 것은 아닙니다. 회사에서도 대부분의 사람들은 이런저런 이유로 인해 직접 손으로 문자열을 다루는 것이 대부분입니다.

슬프게도 문제는 여기에서 비롯되죠. 문자열을 직접 사람의 손을 거쳐 다루게 되면 오타가 생기거나 원래 주어진 문자열을 주관을 가지고 해석해 다르게 사용하는 경우가 빈번합니다. 이렇게 재생산된 문자열을 다시 넘겨받아 원본 문자열과 비교해 사용한다고 하면 사소한 오타와 미묘한 단어의 재배치로 인해 간단한 정규표현식을 통한 문자열 일치로는 원본과 정확하게 일치시키지 못하는 경우가 태반입니다. 이런 경우 문제가 있는 부분을 사람이 눈으로 확인하면 쉽게 구분할 수 있지만 스크립트를 통한 자동화를 하기에는 애매하기 짝이없죠. 이번 기사에서는 이러한 상황을 극복하고 원하는 작업을 수행할 수 있도록 도와주는 알고리즘과 펄 모듈을 소개합니다.

준비물

필요한 모듈은 다음과 같습니다.

직접 CPAN을 이용해서 설치한다면 다음 명령을 이용해서 모듈을 설치합니다.

$ sudo cpan Path::Tiny String::Trigram

사용자 계정으로 모듈을 설치하는 방법을 정확하게 알고 있거나 perlbrew를 이용해서 자신만의 Perl을 사용하고 있다면 다음 명령을 이용해서 모듈을 설치합니다.

$ cpan Path::Tiny String::Trigram

당면한 문제

예를 들어 다음과 같은 여러 요소를 담는 박스 목록이 있다고 해보죠.

Green  Box : Bat
Green  Box : Gloove
Green  Box : Uniform
Purple Box : Chocolate
Purple Box : Mint Candy
Purple Box : Apple Jelly
Blue   Box : Brush-middle
Blue   Box : Brush-wide
Blue   Box : Black Ink

동료 A는 이것을 굳이 자신만의 방식으로 기록했네요.

Box:Blue:Brush-middle
Box:Green:Gloove
Box:Purple:Mint Candy
Box:Purple:Apple Jelly
Box:Blue:Black Ink
Box:Green:Uniform
Box:Purple:Chocolate
Box:Green:Bat
Box:Blue:Brush-wide

아... 그리고 동료 B는 오타가 어마어마합니다.

Grean  Box : Uniform
Purfle Cox : Chocholate
Purple Box : Mint Dandy
Purlpe Box : Aple Jelly
Grean  Box : Bat
Grean  Box : Glove
Bule   Box : Brush-middle
Blue   Bix : Brush-wide
Blue   Box : Black Iink

휴... 어떤가요? 눈으로 살펴보면 동료 AB가 기록한 항목이 원본의 어떤 항목을 염두에 두고 기록했는지 대충 알수는 있을 것 같긴 하군요. 하지만 이 양이 몇 천 또는 몇 만줄이라면 어떨까요? 또 이렇게 비교해야 할 파일이 수십 개라면 어떨까요? 결국 이것을 프로그램으로 작성해 일관되게 일치되는 것끼리 엮어주어야 할텐데 방법이 잘 떠오르시나요? 물론 가능은 하겠지만 그리 녹녹하지만은 않아보입니다. :(

n-gram 알고리즘

n-gram 알고리즘은 통계와 확률을 바탕으로한 색인 분석 등에 널리 쓰이는 방식으로 초기 검색사이트가 취한 색인 검색 알고리즘의 하나입니다. 요즘엔 생명 공학 분야의 염기서열이나 분자구조 분석에 자주 등장하는 듯 합니다. 이론이 간단하고 빠르기 때문에 여러 학문에 적용하기 안성맞춤이지요.

n-gram 알고리즘의 기본적인 동작 방식은 다음과 같습니다.

[ ] : n == 3 window

algorithm
[ ]--------> alg
 [ ]-------> lgo
  [ ]------> gor
   [ ]-----> ori
    [ ]----> rit
     [ ]---> ith
      [ ]--> thm

n-gram 알고리즘은 n개의 문자열 크기만큼의 창(window)을 만들어 문자열을 왼쪽에서 오른쪽으로 한 단위씩 움직이며 추출되는 문자 요소 집합(character item set)의 출현을 수집합니다. 이러한 방식으로 두 개의 문자열 각각의 문자 요소 집합을 수집한 후 출현 빈도를 비교함으로써 두 문자열을 비교해서 그 결과를 수치로 표현합니다. 이때 n의 값은 의미가 있다고 생각하는 음절의 수로 지정하면 되는데 이 값이 1인 경우unigram, 2인 경우bigram, 3인 경우trigram이라고 부릅니다.

String::Trigram 모듈

오늘 소개할 String::Trigram 모듈은 이름에서 알 수 있듯이 n 값이 3인 trigram 모듈이지만 원한다면 n 값을 변경해 n-gram으로 사용할 수도 있습니다.

String::Trigram 모듈의 compare() 클래스 메소드는 인자로 받은 두 개의 문자열의 그 유사성을 1보다 작은 소수값으로 계산해 반환하는 함수입니다. 우리에게 필요한 것은 단지 이것 하나 뿐입니다! :)

#!/usr/bin/env perl

use v5.16;
use strict;
use warnings;

use Path::Tiny;
use String::Trigram;

my @raw  = path('raw.input')->lines( { chomp => 1 } );
my @ed_a = path('a.input'  )->lines( { chomp => 1 } );
my @ed_b = path('b.input'  )->lines( { chomp => 1 } );

say "Text A";
say for get_similarity( \@raw, \@ed_a);

say "Text B\n";
say for get_similarity( \@raw, \@ed_b);

sub get_similarity {
    my $src  = shift;
    my $dest = shift;

    my @result;
    for my $s (@$src) {
        my $max_smlty = 0;
        my $max_smlty_item;
        for my $d (@$dest) {
            my $smlty = String::Trigram::compare($s, $d);
            next unless $smlty > $max_smlty;

            $max_smlty      = $smlty;
            $max_smlty_item = $d
        }
        push(
            @result,
            sprintf(
                "%-26s -> %-26s : similarity = %.2f",
                $s,
                $max_smlty_item,
                $max_smlty,
            );
        );
    }

    return @result;
}

실행 결과는 다음과 같습니다.

Text A
Green  Box : Bat            -> Box:Green:Bat              : similarity = 0.33
Green  Box : Gloove         -> Box:Green:Gloove           : similarity = 0.41
Green  Box : Uniform        -> Box:Green:Uniform          : similarity = 0.43
Purple Box : Chocolate      -> Box:Purple:Chocolate       : similarity = 0.47
Purple Box : Mint Candy     -> Box:Purple:Mint Candy      : similarity = 0.48
Purple Box : Apple Jelly    -> Box:Purple:Apple Jelly     : similarity = 0.50
Blue   Box : Brush-middle   -> Box:Blue:Brush-middle      : similarity = 0.53
Blue   Box : Brush-wide     -> Box:Blue:Brush-wide        : similarity = 0.50
Blue   Box : Black Ink      -> Box:Blue:Black Ink         : similarity = 0.48
Text B
Green  Box : Bat            -> Grean  Box : Bat           : similarity = 0.70
Green  Box : Gloove         -> Grean  Box : Glove         : similarity = 0.63
Green  Box : Uniform        -> Grean  Box : Uniform       : similarity = 0.75
Purple Box : Chocolate      -> Purfle Cox : Chocholate    : similarity = 0.47
Purple Box : Mint Candy     -> Purple Box : Mint Dandy    : similarity = 0.78
Purple Box : Apple Jelly    -> Purlpe Box : Aple Jelly    : similarity = 0.63
Blue   Box : Brush-middle   -> Bule   Box : Brush-middle  : similarity = 0.73
Blue   Box : Brush-wide     -> Blue   Bix : Brush-wide    : similarity = 0.78
Blue   Box : Black Ink      -> Blue   Box : Black Iink    : similarity = 0.88

와우, 놀랍군요! 수정본에 오타가 있든 순서가 바뀌어 있든 꽤나 눈으로 비교하는 것과 비슷한 수준으로 원하는 것들을 찾아서 일치시켜주고 있죠? ;-)

정리하며

물론 n-gram이 모든 유사성 검색 문제를 해결해주는 도깨비 방망이는 아닙니다. 여러분이 Daver와 같은 새로운 검색 엔진을 만들겠다면 이런 기초적인 수준의 알고리즘만으로는 부족하겠죠. 하지만 적어도 꽤 많은 상황에서 n-gram 알고리즘과 String-Trigram 모듈은 여러분이 갓 내린 커피 몇 잔과 비스켓을 즐기며 마음의 여유를 찾을 정도의 시간은 충분히 마련해줄 것입니다. 오타를 내거나 자신만의 형식으로 문서를 수정한 사람에게 분노 섞인 메일을 더이상 보내지 않아도 된다는 점은 덤이겠죠. ;-)

blog comments powered by Disqus