Python String(문자열) 조작 마법사 되기(2) : 난이도 급상승 - 쾌속 단어매칭(find) 검색 알고리즘!

BJ Park·2021년 2월 5일
1

Python 개발 이야기

목록 보기
5/5
post-thumbnail

문자열 마법사되기 그 두번째!

1편에 너무 쉬운 난이도의 코드를 소개한 것 같아서
2편에서는 조금 깊이가 있는 문자열 조작을 다루어 보려고 한다.

오늘의 문제는?

단어사전을 가지고 문서 안에 있는 모든 단어를 매칭하는 과제!

이 글에서는 아래 메서드들을 비교하고
상황과 용도에 따라 어떻게 사용해야 하는지를 정리한다.

  • 정규표현식 라이브러리 re의 match()와 finditer()
  • 문자열의 기본 메서드 find()와 find_all() 커스텀 제작
  • 파이썬 빌트인 이터레이터 검색 연산자 in

결론부터 말하자면 실제로 아래 방법들에 따라 나는 50배 이상 작업속도를 개선했다.

미션 상세

뭐야 사전 데이터로 문서 내 단어 검색? 쉬운거 아냐?
쉽게 생각될 수 있지만 아래와 같은 세부미션과 악조건들이 작용하면 얘기는 다르다.

  1. 데이터의 양
    i) 단어사전에 단어가 수만개다.
    ii) 문서 길이가 수천자다.

  2. 데이터의 질
    i) 문서는 띄어쓰기가 없거나 마구잡이로 되어 있다.

  3. 미션의 세부과제
    i) 단어가 문서 내 여러번 출현가능하므로 항상 문서 전체를 훑어야 한다.
    ii) 매 단어가 출현한 정확한 위치(문서 내 인덱스)를 모두 기록해야 한다.

그냥 대충(편한대로) 짜서 돌리면 얼마나 걸리나?

문자열의 위치를 반환하는 파이썬 메서드는 대표적으로 find()가 있는데,
find()는 단어가 문자열 내에서 여러번 출현해도 첫 매칭 위치 하나만을 반환한다.
이러면 상기한 3번의 i)조건을 만족하도록 하기가 참 불편하다.
find_all()같은 기본 메서드 없나? 당연히 있을 줄 았았는데 그런거 없다.

그럼 정규식 라이브러리를 사용하면 어떨까?
re.match()외에 정규식에서는 re.finditer()를 제공한다.
매칭되는 좌표를 전부 리스트로 반환해주는 편리함!

하지만 이렇게 구현하면 데이터의 양(수천자 길이 문서, 수만개 단어)의 압박으로
사전 데이터로 문서 전체를 순회하는데 10분이 넘게 걸린다.
이대로는 문제가 있다! 이런 때야 말로 실전을 위해 알고리즘이 쓰일 때다.

3단계 해결책으로 50배는 빠르게 단어 매칭하기!

50배 빠른 단어 매칭을 위한 해결책 중 가장 핵심은 바로 in 연산자다.

in도 엄연한 파이썬 빌트인 연산자!

여기에서 말하는 in 연산자는
주로 for in문에서 이터레이터 내 항목의 값을
변수로 받아오는 바로 그 용법! 이 아.니.라.

while이나 if와 같은 조건 판별시에 자주 사용되는 boolean을 반환하는 연산자이다.
in도 엄연한 파이썬 빌트인 연산자라는 것이다.

그런데 단어가 매칭된 좌표를 찾아야 하는데 in은 boolean만 반환하기 때문에
그게 아무리 빨라봤자 소용 없는 거 아니야? 라고 생각할 수 있지만, 여기서
1. in이 너무너무 빠르기 때문에 가능한 트릭과
2. 지난시간에 다루었던 일정 길이로 문서 쪼개기 테크닉이 작용한다.

1단계 : 문서를 쪼개서 페이지화 한 뒤 페이지당 in 연산을 수행

문서를 쪼개는 목적은 in 연산자를 효과적으로 사용하기 위함이다.
반복문이 생겨버렸기 때문에 속도가 저하될 거라고 생각할 수 있지만 그렇지 않다.

일정 길이로 문서를 쪼개면 수천자의 문서가 수백자 수준의 페이지로 나눠질 수 있고
단어가 수만개이기 때문에 수백자의 문서 페이지 내에서 해당 단어가 나올 확률은? 낮아진다는 것!

  • in 연산은 다른 문자열 검색 메서드들보다 훨씬 빠르다
    (최대 약 10배, 문자열이 짧을 수록 in연산의 비교 우위가 더 큼)
  • 페이지 길이가 짧아지면 포함된 단어 수도 줄어든다.
    (in 연산에서 False가 반환될 확률이 커짐)
  • in으로 False가 반환되면 문자열 위치 검색 메서드 실행할 필요 자체가 없다.
    (극단적으로, 사전 내 단어가 문서에 한번도 출현 안할 경우 약 100배 빨라짐)

해당 단어 in 연산에서 False가 반환되면 좌표비교 없이 다음단어로 skip!

2단계 : 페이지당 반복문으로 모든 단어를 비교한다.

이제 단어가 페이지 내에서 출현하는게 확실시 된 상태에서 비교할 수 있게 되었다.
수만단어의 사전을 사용하기 때문에 in으로 걸러지는 단어가 전체의 99% 정도다.
이제 나머지 1%의 단어들은 천천히 위에서 짠 코드를 re.finditer()로 매칭해도 무방하다.
이미 이것만으로 단어 매칭에 걸리는 시간이 적어도 30~40배 감축되었을 것이기 때문이다.

하지만 만약 이정도로 만족할 수 없다면?
3단계로 넘어가보자.

3단계 : 정규표현식보다는 커스텀 find_all()이 더 빠르다! 메서드 선언!

정규표현식 라이브러리는 놀랄만큼 효과적으로 알고리즘이 짜여 있어서
오버헤드가 많음에도 꽤 좋은 성능을 보여준다.

re.match()는 find()함수와 비교했을 때,
빠를 때에는 약 55%의 시간을, 느릴 때에는 약 270%의 시간을 소요한다.

빠를 때와 느릴 때의 기준은 아래와 같다.

  • 문서의 전반부에 출현할 경우 : 정규식 match()가 find()보다 2.5배 이상 느림
  • 문서의 후반부에 출현할 경우 : 정규식 match()가 find()보다 2배 미만 빠름

결론 :
정규식은 빠를 때와 느릴 때의 조건 발생확률이 같다고 간주했을 때

대략 find()보다 약 1.6배의 시간을 소요한다.(문서길이에 따라 다름)

문서의 총 길이가 길어질 수록 정규식이 더 유리해지기 때문에 아직 재고의 여지는 있다.
물론 우리는 첫 단계에서 문서 길이를 충분히 줄이고 내려왔기 때문에 find()가 당연히 유리하도록 조건을 만들어두었다.

하지만 아직도 문서 페이지가 그래도 충분히 길어서인지, 나의 경우 match()가
find()보다 상기한 1.6배가 아니라 약 1.2배 정도 시간을 더 소요하는 것으로 나타났다.

어쨌든 종합적으로 판단했을 때에 속도를 우선시한다면 match()함수는 빠염.

정리

아래는 내가 find()함수를 사용해 단어 매칭 위치를 전부 찾기 위해 작성한 반복문 메서드이다.

커스텀 find_all 코드!

def find_all(word, page):
    jump = len(word)
    i = page.find(word)
    while i != -1:
        yield i
        i = page.find(word, i+jump)

jump로 단어 길이만큼 넘어가는 이유는 맨 아래 참조(*보이어-무어 알고리즘)

종합적으로 오늘의 문자열 매칭 최적화를 정리하자면

1) 연산자 속도 성능 (단순비교)

in 연산자 >약 10배> str.find() >약 1.6배> re.match( )

2) 최적화 테크닉

  • 문서 쪼개서 쓸 경우는 in + find() 조합
    • 같은 단어 중복 매칭의 경우 find_all()로 커스텀
  • 문서를 못 쪼개면 in + re.match() 조합
    • 문서를 못 쪼갰고 문서가 너무 길면 in 오버헤드 없애는 것 고려

참조


알고리즘 개선이 필요할 땐 삼성 SW Expert 아카데미를 참조하면 유용!
https://swexpertacademy.com/main/learn/course/lectureVideoPlayer.do

~fin~

profile
일 잘하는 백엔드 엔지니어

0개의 댓글