보이어무어로 한글을 매칭하면 성능이 안좋다 ? (효율적으로 문자열 매칭하기)

 

 

이 글에서 도출된 결론은 제가 마주한 개발 상황에서 겪은 과정에 따른 것이며

개발 상황에 따라 달라질 수 있습니다.

---

 

✅ 선행 개념

당연히 보이어무어의 동작원리를 알고 와야한다.
보이어무어는 2가지 작동방식이 존재하고, 아래 2개의 링크를 첨부한다.
 
 
추가적으로 KMP와 함께 성능을 비교했고, 어떤점이 다른지 명확히 이해하고 싶다면 KMP알고리즘도 확인하자

 

1️⃣ Boyer Moore - 나쁜 문자 이동 방식

https://jie0025.tistory.com/537

[문자열 매칭] 보이어무어(Boyer-Moore) - Bad Character Heuristic

 

2️⃣ Boyer Moore - 착한 접미부 이동 방식

https://jie0025.tistory.com/538

[문자열 매칭] 보이어무어(Boyer-Moore) - Good Suffix Heuristics

 

3️⃣ KMP

https://jie0025.tistory.com/536

[문자열 매칭] KMP (knuth-morris-prett) 동작방식,수도코드

 
 

---

 
 

 ✅ 개요

보이어무어 알고리즘은 문자열매칭 알고리즘으로, 굉장히 빠른 속도를 자랑한다.
만약 문자열의 길이가 N일경우, 일반적으로는 N보다 작은 시간복잡도가 측정된다. (최악의 경우는 NM)
 

📣 보이어-무어 알고리즘의 성능이 좋은 이유

1. 문자열 매칭시 우측에서 매칭 실패할 가능성이 크다는 특징을 반영했으며
2. 문자열 매칭시 한칸씩 이동하며 매칭하지 않도록,  우측으로 이동시키는 방법이 2가지 존재해, 순간마다 더 많이 이동 가능한 방식을 채택하기 때문이다.
 
이런 이유로  보이어무어의 성능이 좋다고 확신을 했었다. 
 

📣 KMP와 비교하면?

KMP도 문자열 전체를 탐색하지 않고, 우측으로 이동하기 위한 방식으로
접두사이면서 접미사인 문자열의 최대 길이를 저장하는 테이블을 만들고 이동시키는데
 
KMP는 문자열 매칭을 왼쪽부터 시도하기 때문에 우측에서 불일치가 발생할 가능성이 크다.
 
이러한 이유로 (최악의 경우만 아니라면) 오른쪽부터 매칭을 시도하는 보이어무어가 훨씬 빠를 수 밖에 없다. 
 
 
 

오늘 한글 문자열 매칭에 대한 성능테스트를 진행했는데,
결론부터 말하면 2가지 이동 방법이 모두 적용된 보이어무어에서는 효율이 좋지 못하다는것을 알게 되었다. 

 
 

📊 성능 비교 이미지

이미지에서는 순서대로 아래 상황을 의미한다.
 

• 보이어무어1 (나쁜문자 이동방식만 적용)
• 보이어무어2 (나쁜문자 + 착한접미부 이동방식 함께 적용)
• KMP

 

✍️ 이미지를 통해 내린 결론

한글 문자열 매칭에선 다음과 같은 결론이 내려진다. 
 
1)  나쁜문자 이동방식만 적용된 보이어무어가 가장 뛰어난 성능을 보이고,
2) 나쁜문자와 착한 접미부 이동방식이 함께 적용된 보이어무어에선 가장 성능이 좋지 못하다.
3) 당연하게도 우측에서 매칭 시도를 하는 보이어무어1이 KMP보다 빠를 가능성이 높다.
 
 
 

 ✅ 왜 한글에서는 효율이 좋지 못할까?

먼저 보이어무어1이 보이어무어2보다 성능이 뛰어나다는 점에서 
우리는 보이어무어2에 추가된 착한접미부 이동방식에서 문제가 발생한다는것을 유추할 수 있다. 
 
 
 

🤔 그렇다면 왜 한글이  <착한 접미부 이동방식>에서 문제가 발생할까?

 
문자의 특성을 떠올려보면 추론이 가능하다.
 
 

1️⃣ 영어

영어 문자는 한 문자 자체가 한개의 글자가 되기 때문에, 착한 접미부를 발견할 가능성이 크다. 
 
 
Chat GPT에게 er이 많이 들어간 문장을 만들어 달라고 했다. 
 

"The faster runner was able to outrun all the other competitors and emerge as the winner."

 
위의 문장에선 5번의 er이 발생한다.
 
 
er뿐만 아니라 한글자 (예를 들면 e) 자체도 착한 접미부로써 활용될 수 있기 때문에 
한 Character 자체가 문자 그 자체인 영어에서는
 
무조건 착한 접미부 방식까지 적용된 보이어무어 2에서 성능이 뛰어날 수 밖에 없다.
 
 

2️⃣ 한글

드디어 한글이다. 
영어는 한 Character자체가 하나의 문자임을 나타내지만
한글은 초/중/종성이 모두 합쳐져야만 비로소 하나의 문자를 완성 할 수 있다. 
 
이 특징으로 인해 한글을 탐색할 경우 착한 접미부 방식에서 비효율적인 검사를 진행하게 만든다. 
 
 

일반적으로 한글로 구성된 문장에선, 같은 문자가 발생할 가능성이 굉장히 적다. 

방금 내가 위에 적은 문장에서도 여러번 출연하는 문자는 <적>, <문>  이런 것에서만 발생한다.
 
 
만약 위의 문장에서 <굉장히> 를 탐색한다고 가정하자.
 
굉/장/히 모든 문자는 문장에서 유일하다.
 
 
이것은 착한 접미부 이동 방식의 장점을 전혀 사용할 수 없게 만든다.
그럼에도 불구하고 착한접미부 방식이 가능한지 확인을 해야하기때문에 추가적인 연산을 만드는것 같다
 
 

✅ 결론 

결국 한글에선 착한 접미부 방식에서 매칭 실패로 이어질 가능성이 높기 때문에,
나쁜 문자 이동 방식을 적용하는것이 낫다는 판단이다.
 

사실 논문같은거 읽어보면 초중종성을 음절 단위로 나눠서 어떻게 하는 방법이 효율적이라고 하는데 지금 적용할 수 없다..

현재로써의 결론은
나쁜 문자 이동 방식만 적용된 보이어무어를 사용함으로써
우측을 먼저 검사하는것에서 효율을 찾아야 한다.