개요
offline memo app, 개인프로젝트의 Preview Component를 구현할 당시 나는 Textarea에 입력한 값을 Mark Down 문법으로 변환하는 기능의 알고리즘에 Naïve String Search(우직한 문자열 검색)을 사용하였다.
Naïve String Search(우직한 문자열 검색법)
1번째부터 m번째 글자까지, 2번째부터 m+1번째 글자까지, 이런 식으로 문자열을 일일이 찾아가면서 탐색한다. 이 경우 길이가 각각 n, m인 문자열과 패턴에 대하여 Θ((n−m)m)의 탐색 횟수를 거친다. 작동 시간이 오래 걸리지만 구현이 편하기 때문에, 충분히 작은 입력이라면 이런 알고리즘을 사용하는 것도 나쁘지 않다.
출처 - 문자열 알고리즘 나무위키
EX.
# 제목
## 부제목
- 리스트1
- 리스트2
- 리스트3
__이태릭체__입력값으로 해당 값이 들어갈 경우, 해당 값을 '# 제목\n\n## 부제목\n\n- 리스트1\n- 리스트2\n -리스트3\n\n__이태릭체__'라는 string 값으로 하여금 # 로 시작하는 값에는 <h1>제목</h1>, - 로 시작하는 값은 리스트 형식으로 변환하는 등 해당 문자열에 대한 규칙을 하나씩 체크하며 찾았다.
왜 교체하였는가.
처음 구현했을 당시 입력한 문자열에 대해 제대로 작동을 했고, 딱히 기능적으로 문제가 없다고 생각했다. 그러나 코드 중복을 최소화하는 작업을 진행하면서 해당 컴포넌트에 대해 생각했다.
만약 해당 문자열의 길이가 1억 개가 된다면?
나는 독학으로 프론트엔드를 배울 당시 생활 코딩 유튜브를 보면서 공부를 했었는데, 그때 가장 기억에 남았던 말이 바로 해당하는 값이 1억 개일 경우? 라는 말이었다. 그래서 내 프로젝트에 적용해보았을 때 해당 문자열이 1억 개가 된다면 어떻게 될까?
그렇다면 1억 개의 문자열을 일일이 확인하면서 마크다운 문법 변환을 위해 규칙을 찾을 것이다. 물론 연산 자체가 인간보다 빠르다고는 하지만 그렇게 될 경우 해당 기능에 대한 성능 이슈가 생길 수 있다고 판단하여 변경하였다.
어떻게 변경하였는가.
문자열 검색 알고리즘을 구글링하던 중 Knuth-Morris-Pratt Algorithm 이라는 알고리즘을 발견하였다. 해당 알고리즘은 원래 불일치가 발생하기 직전까지 같았던 부분은 다시 비교하지 않고 패턴을 검색하는 알고리즘이며, 비교 횟수를 줄이고 효율성을 높이는 알고리즘이었다. 그러나 내 기능에는 완벽히 KMP 알고리즘을 적용하기에 적합하지 않았으나 알고리즘 사용법을 확인하던 중 적용하는 것이 아닌 영감만 받아 스스로 구현하는 것이 더 적합하다고 생각했다.
바로 접두사(prefix)를 확인하여 패턴을 검색하는 것.
마크다운의 경우 시작하는 첫 글자에 따라 해당하는 문법으로 바뀐다. 그렇다면 내 기능에는 어떻게 적용할 수 있을까? 가장 먼저 예제 '# 제목\n\n## 부제목\n\n- 리스트1\n- 리스트2\n -리스트3\n\n__이태릭체__' 에서 \n 에 대해 문자열을 split 한 후 여러 개의 문자열로 나누는 것이다. 이후 접두사에 대해 패턴을 검색하고 마크다운에 적합한 패턴이 있을 경우 해당 패턴으로 바꾼 뒤 비교를 중지하게 된다.
이 말은 즉 # 제목 에 대해 # 은 <h1></h1> 의 패턴이므로 해당 문자열을 마크다운 문법으로 변환한 후 이후 문자에 대한 비교를 중지한다. 그러면 우직한 문자열 검색법을 사용했을 때보다 시간이 절감되고 1억 개라는 말도 안되는 길이의 문자열이 들어와도 패턴만 체크한 후 나머지 시간은 검색하지 않으니 그 시간만큼의 성능을 개선할 수 있게 된다.
그러나 문제가 생긴 부분
만약 문자열 중간에 패턴이 들어갈 경우는 어떻게 할 것인가?
예를 들어, '안녕하세요. __프론트엔드 개발자__를 꿈 꾸는 XXX입니다.' 라는 문자열이 들어올 경우 위와 같은 방식이면 중간에 들어온 해당 패턴도 변환해야 하는 패턴인데 변환하지 못하고 넘어가게 된다.
그래서 이것을 대비하여 접두사(prefix)의 패턴이 존재하지 않을 경우 접두사를 하나씩 늘려간다. 그렇게 늘려간 접두사의 끝이 마크다운 문법에 일치하는 패턴이 생길 경우 그 부분부터 다시 접두사를 만드는 과정으로 변경하여 해당 문제를 해결했다.
결론
따지고 보면 처음의 O((N-M)M)의 시간 복잡도에서 크게 벗어나지는 않았지만, 최소 O(N+M)의 성능을 낼 수 있는 기능을 만들 수 있게 되었다. 아직은 많이 부족하지만 처음으로 프로젝트 리펙터링을 하면서 성능 관련하여 생각할 수 있었던 경험이 되었고, 앞으로도 이러한 상황이 찾아온다면 새롭게 알고리즘을 변경하는 경험을 하여 성장의 발판으로 삼는 것도 내게는 큰 도움이 된다고 생각한다.
