[번역]정규표현식으로는 5일 걸리는 작업, 15분만에 끝내기

이 글은 Vikash SinghRegex was taking 5 days to run. So I built a tool that did it in 15 minutes를 번역한 글입니다. 모든 저작권과 권리는 Vikash에게 있습니다. 
*This article is a translated version of
Vikash Singh’s article: Regex was taking 5 days to run. So I built a tool that did it in 15 minutes. All rights and credits back to him.
*최대한 이해하기 쉽도록 곳곳에 의역이 들어간 점 양해 부탁드립니다.
*도움이 되셨다면 Vikash의 원글에 clap 한번씩 부탁드립니다 :)

텍스트를 이용한 작업을 할 때, 일반적으로 개발자들은 먼저 데이터를 정리하는 과정을 거치게 된다. 그 중에는 키워드 치환(replace) 등의 작업이 포함되는데, 이를테면 “Javascript”를 “JavaScript” 로 교체하는 작업, 혹은 문서 내에 “JavaScript”라는 단어가 등장하는지를 확인하는 등의 작업들이 포함된다.

이런 식의 데이터 클리닝(Data cleaning) 작업은 대부분의 텍스트를 다루는 대부분의 데이터 사이언스 프로젝트의 대표적인 과정 중 하나이다.

데이터 사이언스는 데이터 클리닝으로 시작된다.

최근 위에서 언급한 작업을 할 기회가 있었다. 나는 Belong.co의 데이터 사이언티스트로 일하고 있고, 내 업무의 반 정도는 자연어 처리이다.

작업할 문서의 corpus(*역: 코퍼스.말뭉치. 자연언어 연구시에 특정한 목적으로 표본을 추출한 결과물)에 Word2Vec 모델을 적용시키자, 동의어(synonym)들이 비슷한 단어로 분류되었다. “Javascripting”이 “JavaScript”와 비슷한 단어로 인식되기 시작한 것이다.

이것을 해결하기 위해서, 나는 모든 동의어들을 표준화된 단어들로 교체하기 위해 정규표현식을 작성하였다. 이를테면 “Javascripting”을 “Javascript”로 교체하도록 작성하였는데, 이걸로 하나의 문제가 해결 되는 대신 다른 문제가 발생했다.

몇몇 사람들은 특정한 문제에 대해
“아 여기엔 정규표현식을 쓰면 되지” 라고 생각한다.
이 사람들은 이제 두가지 문제를 마주하게 된다.

위의 인용문은 이 stack-exchange 질문에서 가져온 것으로, 나에게도 같은 문제가 발생했다.

정규표현식은 백 단위의 키워드에 한해서 빠른 검색(search) 및 치환(replace) 처리를 가능케 한다. 하지만 나의 corpus는 2만개가 넘는 키워드와 3백만개의 문서로 이루어져 있었다.

내 정규표현식을 벤치마킹해본 결과, 한번 실행하는데에 5일이 넘는 시간이 걸릴 것임을 알게 되었다.

으 소름;

이런 경우 자연스럽게 병행(parallel) 실행을 해결책으로 떠올리게 된다. 하지만 몇천만 개의 문서와 몇십만 개의 키워드를 처리해야 하는 상황에서는 가능한 선택지가 아니었다. 뭔가 더 나은 방법이 있을 것이다! 
나는 방법을 찾아보기로 했다.

나는 사무실의 동료들과 스택오버플로우에 도움을 청했고, 몇가지 방안을 구할 수 있었다. Vinay Pandey, Suresh Lakshmanan, 그리고 스택오버플로우를 통해 나는 Aho-Corasick이라는 환상적인 알고리즘과 Trie 데이터구조 접근법으로 방향을 잡게 되었다. 기존에 존재하는 해결책이 없을까 싶었지만, 딱히 적절한 것을 찾기가 어려웠다.

그래서 내가 직접 툴을 작성하게 되었고, FlashText가 탄생하게 되었다.

FlashText가 어떻게 작동하는지를 알아보기 전에, 검색에 대해서 얼마나 퍼포먼스가 나오는지를 확인해보도록 하자.

붉은 선이 FlashText의 검색(search)에 걸린 시간

위의 차트는 한개의 문서에 대한 컴파일된 정규표현식(compiled regex)과 FlashText의 비교 차트이다. 키워드 숫자가 증가함에 따라, 정규표현식은 점점 더 오랜 시간이 소요되는 반면, FlashText는 관계없이 처리 속도가 유지된다.

FlashText가 실행 시간을 5일에서 14분으로 줄여주었다!

이제 안심이다 :)

치환 작업에 대한 FlashText의 처리 소요 시간은 다음과 같다:

붉은 선이 FlashText의 치환(replace) 에 걸린 시간

벤치마킹에 사용된 코드는 여기에서 볼 수 있고, 결과는 여기에서 볼 수 있다.

FlashText란?

FlashText는 내가 오픈소스로 GitHub에 등록한 파이썬 라이브러리이다. 키워드를 추출하는(extracting) 과정과 대체하는(replacing) 과정 모두에 효율적이다.

FlashText를 이용하기 위해서는 우선 키워드 리스트를 넘겨주어야 한다. 이 리스트는 내부적으로 Trie dictionary 를 생성하는데에 사용된다. 그 후에 문자열과 함께 치환(replace)작업을 할 것인지 검색(search) 작업을 할 것인지를 알려주면 된다.

replace의 경우 치환된 키워드로 새로운 문자열을 생성한다. search의 경우에는 문자열 내에서 발견된 키워드의 리스트를 반환한다. 한번 문자열을 입력하면 이 과정이 일어나는 것이다.

다음은 FlashText를 사용해본 한 행복한 사용자가 한 말이다:

*역: 천개 키워드 & 문서당 ~1만개의 토큰에 대해 컴파일된 정규표현식(compiled regexp)보다 28배 빠르다. 순수 파이썬이라서 다양하게 적용할 수도 있다. @RadimRehurek@gensim_py을 만들었다

FlashText는 어떻게 그렇게 빠른가?

이 부분은 예시를 이용해서 이해하도록 해보자. 우리가 3개의 단어로 이루어진 I like Python이라는 문장과 {Python, Java, J2ee, Ruby}라는 4개의 단어로 이루어진 corpus를 가지고 있다고 가정해보자.

corpus에서 가져온 각 단어가 문장에 존재 하는지 확인하기 위해서는 네번의 시도가 필요하다.

‘Python’이 문장 안에 있는가?
‘Java’가 문장 안에 있는가?

corpus가 n개의 단어를 가지고 있다면 n번의 반복(loop)을 거쳐야 한다. 또한 각각의 <단어>가 문장 안에 있는가? 라는 검색 단위에서도 시간이 소요된다. 이것이 정규표현식을 이용하면 발생하는 소요 시간이다.

이러한 첫번째 방법의 반대 방식을 이용하는 또 다른 접근 방법이 있다. 문장의 각 단어에 대해서 corpus에 존재 하는지를 먼저 확인하는 것이다.

‘I’ 가 corpus 안에 있는가?
‘like’ 가 corpus 안에 있는가?
‘python’이 corpus 안에 있는가?

만약 문장이 m개의 단어로 이루어져있다면, m번의 반복(loop)이 필요할 것이다. 이 경우에는 문장에 몇 개의 단어가 있는지에 따라 시간이 소요된다. 또한, <단어>가 corpus 안에 있는가?를 묻는 이 과정이 dictionary를 확인하는 것으로 해결되기 때문에 보다 더 신속하게 이루어질 수 있다.

FlashText 알고리즘은 두번째 접근 방식을 채택했다. Aho-Corasick 알고리즘과 Trie 자료구조에서 영감을 얻은 방법이다.

구체적인 방식은 이렇다:
우선 corpus로 Trie dictionary를 생성한다. 다음과 비슷한 형태가 될 것이다.

corpus의 Trie dictionary

시작과 EOT(End of Term *역: 단어의 끝)은 space, period(*역: 마침표)와 new_line 과 같은 구분자를 뜻한다. 키워드는 이와 같은 구분자들이 양쪽에 존재 할 때만 매치가 된다. 이렇게 함으로써 pineapple을 찾는데 apple이 매치되는 상황을 피할 수 있다.

그 다음, 인풋 문자열인 I like Python을 가지고 한글자씩 검색을 한다.

Step 1: <start>I<EOT> 가 딕셔너리 안에 있는가? No
Step 2: <start>like<EOT> 가 딕셔너리 안에 있는가? No
Step 3: <start>Python<EOT> 이 딕셔너리 안에 있는가? Yes
<Start> Python <EOT>은 딕셔너리 안에 존재한다.

이러한 과정은 글자 단위의 과정이므로, <start>like<EOT>의 경우 <start>l 의 단계에서 바로 건너뛸 수 있다. lstart와 연결되어있지 않기 때문이다. 이렇게 함으로써 없는 단어들은 매우 빠르게 건너뛸 수 있게 된다.

FlashText 알고리즘은 입력된 문자열인 ‘I like Python’의 각 글자만을 확인한다. 딕셔너리가 백만개의 키워드를 포함하고 있더라도 실행에 소요되는 시간은 영향을 받지 않게 된다. 이것이 FlashText 알고리즘의 힘이다.

그렇다면 언제 FlashText를 이용해야 할까?

간단한 답: 키워드 갯수가 500개 이상일 때.

FlashText가 500 키워드 이후로 정규표현식보다 앞서는 모습

복잡한 답: 정규표현식은 ^,$,*,\d,.와 같이 FlashText에서는 지원되지 않는 특수문자도 검색할 수 있다. 즉, word\dvc과 같은 단어 조각들을 찾고자 할 때에는 좋은 선택이 아니다. 하지만 word2vec과 같이 완성된 단어를 추출하고자 할 때에는 훌륭한 선택이다.

키워드 검색(search)을 위한 FlashText

FlashText를 이용한 간단한 추출 예제

키워드 치환(replace)을 위한 FlashText

키워드들을 추출하는 대신 치환하고자 하는 경우도 있을 것이다. 이럴 때에도 데이터 처리 파이프라인 내의 데이터 클리닝 과정으로 활용이 가능하다.

FlashText를 이용한 간단한 치환 예제

여러분 주변의 누군가가 텍스트 데이터, Entity 인식, 자연어처리, 혹은 Word2vec과 같은 작업을 하고 있다면, 이 글을 그들에게 공유해주기를 바란다.

우리는 이 라이브러리를 정말 잘 사용하고 있고, 다른 사람들에게도 유용하게 쓰일 것이라고 믿는다.

이상 글을 마친다. 여러분의 clap 에 미리 감사한다 😊