Java) 정규표현식

정규표현식이란?

---

정규표현식(Regular Expression)은 문자열에서 특정한 패턴을 찾거나 일치시키기 위해 사용되는 특수한 텍스트 스트링 Java에서 정규표현식을 사용하면 복잡한 문자열 검색, 매칭 및 변환 작업을 효율적으로 수행

 

정규표현식은 특별한 기능이 들어가는건 아니고 쉽게 얘기하면 문자열에서 패턴찾기입니다.

다만 이 문법이 좋은건 if 문 혹은 switch 문같은 조건문을 사용하지 않더라도 쉽게 찾는 문자열의 조건을 만드는 코드를 만들 수 있기 때문입니다.

 

정규표현식의 원리

---

정규표현식 엔진이 문자열을 매칭하는 원리는 크게 두 가지 방식으로 나뉩니다: NFA(Nondeterministic Finite Automaton, 비결정적 유한 오토마타) 방식과 DFA(Deterministic Finite Automaton, 결정적 유한 오토마타) 방식입니다. 자바의 정규표현식 엔진은 주로 NFA 방식을 사용합니다.

 

NFA 와 DFA

NFA

NFA 방식은 입력 문자열의 각 문자에 대해 가능한 모든 경로를 시도하여 패턴과 일치하는지를 검사합니다. 이 과정은 재귀적이며 백트래킹을 포함합니다. NFA 방식은 매우 유연하며 다양한 정규표현식을 처리할 수 있지만, 특정 경우에는 성능이 저하될 수 있습니다.

 

다음은 NFA 방식의 기본 원리입니다:

1. 패턴 컴파일: 정규표현식을 패턴으로 컴파일합니다. 이 단계에서 패턴을 상태(state)와 전이(transition)로 구성된 상태 머신으로 변환합니다.
2. 매칭 과정:
   • 현재 상태 유지: 현재 상태를 유지합니다.
   • 입력 문자열의 현재 문자 확인: 현재 상태에서 입력 문자열의 현재 문자가 정규표현식의 현재 상태와 일치하는지 확인합니다.
   • 일치하는 경우:
     • 상태를 전이합니다.
     • 입력 문자열의 다음 문자로 이동합니다.
   • 일치하지 않는 경우:
     • 백트래킹하여 이전 상태로 돌아가 다른 경로를 시도합니다.
     • 모든 경로를 시도한 후에도 일치하지 않으면 매칭 실패로 판단합니다.

예시

안녕하JS세요 제 이름은 JS 입니다.Js

이 문장에서 JS 를 검색하는 순서입니다.

원리 설명

1. 정규표현식 패턴 컴파일:
   • Pattern.compile("JS")를 사용하여 "JS"라는 패턴을 컴파일합니다.
   • 이 과정에서 "JS"라는 패턴은 내부적으로 상태 머신으로 변환됩니다.

     상태 0: 'J' 문자 대기 상태
     상태 1: 'S' 문자 대기 상태
     상태 2: 매칭 완료 상태

2. Matcher 객체 생성:
   • pattern.matcher(input)를 사용하여 입력 문자열과 컴파일된 패턴을 매칭하는 Matcher 객체를 생성합니다.
   • 이 Matcher 객체는 상태 머신과 입력 문자열을 가지고 매칭 작업을 수행할 준비를 합니다.
3. 매칭 과정:
   • matcher.find() 메서드를 호출하여 입력 문자열에서 패턴과 일치하는 부분을 찾습니다.
   • find() 메서드는 현재 인덱스에서부터 입력 문자열의 끝까지 탐색하면서 패턴과 일치하는 부분을 찾습니다.
   • 각 문자를 확인하여 상태 머신의 상태를 전이하며, 일치하는 부분이 있으면 true를 반환하고, 일치하는 부분이 없으면 false를 반환합니다.

매칭 과정의 자세한 설명

입력 문자열: "안녕하JS세요 제 이름은 JS 입니다.Js"

1. 첫 번째 find() 호출:
   • 상태 0에서 시작하여 입력 문자열의 첫 번째 문자 '안'을 확인합니다.
   • '안'은 'J'와 일치하지 않으므로 다음 문자 '녕'으로 이동합니다.
   • 이 과정을 반복하여 '하'까지 이동합니다.
   • '하'도 'J'와 일치하지 않으므로 다음 문자 'J'로 이동합니다.
   • 'J'는 'J'와 일치하므로 상태 1로 전이합니다.
   • 다음 문자 'S'를 확인합니다.
   • 'S'는 'S'와 일치하므로 상태 2로 전이하고, 매칭이 완료됩니다.
   • 매칭이 완료된 시작 인덱스(3)를 반환합니다.
2. 두 번째 find() 호출:
   • 첫 번째 매칭이 완료된 위치 다음부터 다시 탐색을 시작합니다.
   • 상태 0에서 '세'를 확인하고, 일치하지 않으므로 계속 이동합니다.
   • '요', ' ', '제', ' ', '이름은', ' ', 'J'를 확인합니다.
   • 'J'는 'J'와 일치하므로 상태 1로 전이합니다.
   • 다음 문자 'S'를 확인합니다.
   • 'S'는 'S'와 일치하므로 상태 2로 전이하고, 매칭이 완료됩니다.
   • 매칭이 완료된 시작 인덱스(14)를 반환합니다.
3. 세 번째 find() 호출:
   • 두 번째 매칭이 완료된 위치 다음부터 다시 탐색을 시작합니다.
   • 상태 0에서 ' ', '입', '니', '다', '.', 'J'를 확인합니다.
   • 'J'는 'J'와 일치하므로 상태 1로 전이합니다.
   • 다음 문자 's'를 확인합니다.
   • 's'는 'S'와 일치하지 않으므로 매칭 실패하고, false를 반환합니다.

 

백트래킹

---

Backtracking (역추적)

검색 실패시에 정규식 엔진이 현재의 성공한 부분을 버리고 이전에 저장한 상태로 되돌아가서 다시 검색을 시도하는 것을 Backtracking이라고 한다.

 

백트래킹 예제

import java.util.regex.*;

public class RegexBacktrackingExample {
    public static void main(String[] args) {
        // 정규표현식 패턴을 컴파일합니다.
        Pattern pattern = Pattern.compile("(a+)+b");

        // 입력 문자열을 정의합니다.
        String input = "aaaaaab";

        // 패턴과 입력 문자열을 매칭시킵니다.
        Matcher matcher = pattern.matcher(input);

        // 패턴에 일치하는지 확인합니다.
        if (matcher.matches()) {
            System.out.println("The input string matches the pattern.");
        } else {
            System.out.println("The input string does not match the pattern.");
        }
    }
}

 

백트래킹 설명

위 예제에서 사용된 정규표현식 패턴 (a+)+b는 다음과 같이 해석됩니다:

• (a+) : 하나 이상의 'a'로 구성된 그룹
• (a+)+ : 앞서 정의한 그룹이 하나 이상 반복됨
• b : 마지막에 'b'가 옴

입력 문자열 aaaaaab는 이 패턴에 맞지만, 정규표현식 엔진이 매칭을 시도할 때 백트래킹이 발생합니다.

1. 먼저, (a+)가 가능한 많이 매칭됩니다. 즉, aaaaaa가 첫 번째 그룹 (a+)에 매칭됩니다.
2. 그 다음, 엔진은 마지막 b를 매칭하려고 시도하지만, 이미 모든 'a'를 소비했기 때문에 매칭에 실패합니다.
3. 그러면 엔진은 마지막에 매칭한 'a' 하나를 포기하고, 첫 번째 그룹 (a+)에 aaaaa만 매칭시킵니다. 그리고 남은 a와 b를 매칭하려고 시도합니다.
4. 이러한 과정이 반복되며, 모든 가능한 방법을 시도하여 패턴을 입력 문자열과 일치시키려고 합니다.

백트래킹이 발생하는 이유

백트래킹은 정규표현식에서 다음과 같은 경우에 자주 발생합니다:

• 중첩된 반복 ((a+)+)
• 조건부 패턴 (a|b)
• 선택적 요소 (a?b)

백트래킹을 피하는 방법

백트래킹을 피하기 위해서는 정규표현식을 더 간단하고 효율적으로 작성하는 것이 중요합니다. 위의 예제를 비효율적인 백트래킹 없이 해결하려면, 정규표현식을 a+b로 변경할 수 있습니다. 이는 동일한 결과를 더 효율적으로 얻을 수 있습니다:

 

Index 검색과의 비교

---

속도 비교

• indexOf 방식:
  • indexOf는 단순히 주어진 문자열에서 특정 부분 문자열을 찾는 작업을 수행합니다.
  • 내부적으로 루프를 돌며 각 문자와 패턴의 첫 문자를 비교하고, 일치하는 경우 패턴 전체와 비교합니다.
  • 매우 단순한 문자열 매칭 작업이기 때문에 속도가 빠릅니다.
• 정규표현식 방식:
  • 정규표현식은 패턴을 상태 머신으로 컴파일하고, 이 상태 머신을 사용하여 문자열을 매칭합니다.
  • 다양한 패턴을 지원하고 복잡한 매칭 작업을 수행할 수 있습니다.
  • 백트래킹과 같은 복잡한 작업이 포함될 수 있어 indexOf에 비해 성능이 낮을 수 있습니다.

 

코딩테스트의 속도를 위해서라면 Index 라고 생각하지만 차이가 거의 안나고

제 업무에서는 유지보수를 위해서 정규표현식을 사용하는 편이 더 좋다.

특히 String 의 replaceAll (추후 작성) 이 코드가 더 깔끔해진다.