[알고리즘] 문자열 검색

브루트 포스(Brute Force)

선형검색을 단순하게 확장한 것으로 가능한 모든 위치에서 패턴을 일치시키는 과정을 반복하여 검색하는 방법이다.

 

예시

# 브루트 포스
# 문자열에서 C 찾기(대소문자 구분 X)
string = input("영어 문자열을 입력해주세요 : ")
matchContainer = []
for idx,c in enumerate(string):
    if c.upper() == 'C':
        print(f'"{c}" match? -> Yes')
        matchContainer.append(idx)
    else:
        print(f'"{c}" match? -> No')
if matchContainer == []:
    print("문자열 내에 C가 없습니다.")
else:
    print(f"문자열 {string}에서 C의 위치는 -> {matchContainer}입니다.")

 

 

파이썬의 멤버십 연산자로 찾기

멤버십 연산자 in과 not in을 사용하면 리스트에서 해당 문자열이 포함되는지 확인이 가능하다. 

그러나 어느 위치에 있는지는 알 수 없다.

# 멤버십 연산자1
string1 = input("문자열을 입력해주세요 : ")
string2 = input("찾을 문자열을 입력해주세요 : ")
print(f'입력된 문자열 -> {string1}')
print(f"'{string2}'가 '{string1}'안에 있습니다.") if string2 in string1 else print(f"'{string2}'가 '{string1}'안에 없습니다.")

# 멤버십 연산자2
string1 = input("문자열을 입력해주세요 : ")
string2 = input("찾을 문자열을 입력해주세요 : ")
print(f'입력된 문자열 -> {string1}')
print(f"'{string2}'가 '{string1}'안에 없습니다.") if string2 not in string1 else print(f"'{string2}'가 '{string1}'안에 있습니다.")

 

 

파이썬의 표준 라이브러리 함수로 찾기

파이썬 표준 라이브러리 함수를 사용하면 문자열에서 문자의 위치를 찾거나 그 문자열로 시작하거나 끝나는지 알 수 있다.

 

find(sub[, start[, end]])

• 문자열에서 주어진 부분 문자열 sub의 첫 번째 등장 위치를 찾는다.
• start와 end는 검색 범위를 지정할 수 있으며, 옵션으로 사용할 수 있다.
• 부분 문자열을 찾으면 해당 위치를 반환하고, 찾지 못한 경우에는 -1을 반환한다.
  
  

rfind(sub[, start[, end]])

• find 메서드와 비슷하지만, 문자열을 뒤에서부터 검색하여 가장 오른쪽에 등장하는 위치를 찾는다.

 

index(sub[, start[, end]])

• find 메서드와 동일한 역할을 수행하지만, 부분 문자열을 찾지 못할 경우 ValueError 예외를 발생시킨다.

 

rindex(sub[, start[, end]])

• index 메서드와 비슷하지만, 문자열을 뒤에서부터 검색하여 가장 오른쪽에 등장하는 위치를 찾는다.
  
  

startswith(prefix[, start[, end]])

• 문자열이 주어진 접두사 prefix로 시작하는지 여부를 확인한다.
• 만약 접두사로 시작한다면 True를 반환하고, 그렇지 않은 경우에는 False를 반환한다.
• start와 end를 통해 검색 범위를 지정할 수 있다.
  
  

endswith(suffix[, start[, end]])

• 문자열이 주어진 접미사 suffix로 끝나는지 여부를 확인한다.
• 접미사로 끝난다면 True를 반환하고, 그렇지 않은 경우에는 False를 반환한다.
• start와 end를 통해 검색 범위를 지정할 수 있다.

# 표준 라이브러리
text = input("문자열을 입력해주세요 : ")
target = input("찾을 문자열을 입력해주세요 : ")

# find
print("------------find()------------")
result = text.find(target)
print(f"'{target}'은 [{result}]위치에 있습니다.") if result != -1 else print(f"찾는 문자열이 '{text}'에 없습니다.")
print("------------------------------")
# rfind
print("------------rfind()------------")
result = text.rfind(target)
print(f"'{target}'은 [{result}]위치에 있습니다.") if result != -1 else print(f"찾는 문자열이 '{text}'에 없습니다.")
print("-------------------------------")
# index
try:
    print("------------index()------------")
    result=text.index(target)
    print(f"'{target}'은 [{result}]위치에 있습니다.")
    print("-------------------------------")
except ValueError as ve:
    print(f"찾는 문자열이 '{text}'에 없습니다.")
    print("-------------------------------")
# rindex
try:
    print("------------rindex()------------")
    result=text.rindex(target)
    print(f"'{target}'은 [{result}]위치에 있습니다.")
    print("--------------------------------")
except ValueError as ve:
    print(f"찾는 문자열이 '{text}'에 없습니다.")
    print("-------------------------------")
# startswith
print("------------startswith()------------")
print(f"문자열이 '{target}'로 시작합니다.") if text.startswith(target) else print(f"문자열이 '{target}'로 시작하지 않습니다.")
print("------------------------------------")
# endswith
print("------------endswith()------------")
print(f"문자열이 '{target}'로 끝납니다.") if text.endswith(target) else print(f"문자열이 '{target}'로 끝나지 않습니다.")
print("----------------------------------")

 

 

정규표현식으로 찾기

파이썬에서 정규표현식을 사용하려면 re 모듈을 사용하면된다.

 

import re
text = input("문자열을 입력해주세요 : ")
# 문자열을 입력해주세요 : hello word apples

 

re.search(pattern, string, flags=0)

• 문자열에서 정규표현식 패턴 pattern과 일치하는 첫 번째 문자열을 찾는다.
• string은 검색 대상 문자열이며, flags는 옵션으로 사용될 수 있다. 검색에 성공하면 Match 객체를 반환하고, 실패하면 None을 반환한다.

# search
pattern = r"World"
match = re.search(pattern, text)
if match:
    print("일치하는 문자열:", match.group())
else:
    print("일치하는 문자열이 없습니다.")

 

re.match(pattern, string, flags=0)

• 문자열의 시작 부분부터 정규표현식 패턴 pattern과 일치하는 문자열을 찾는다.
• string은 검색 대상 문자열이며, flags는 옵션으로 사용될 수 있다.
• 검색에 성공하면 Match 객체를 반환하고, 실패하면 None을 반환한다.

# match
pattern = r"Hello"
match = re.match(pattern, text)
if match:
    print("일치하는 문자열:", match.group())
else:
    print("일치하는 문자열이 없습니다.")

 

re.findall(pattern, string, flags=0)

• 문자열에서 정규표현식 패턴 pattern과 일치하는 모든 문자열을 찾아 리스트로 반환한다.
• string은 검색 대상 문자열이며, flags는 옵션으로 사용될 수 있다.

# findall
pattern = r"\w+"
matches = re.findall(pattern, text)
print("일치하는 문자열:", matches)

 

re.finditer(pattern, string, flags=0)

• 문자열에서 정규표현식 패턴 pattern과 일치하는 모든 문자열을 찾아 이터레이터로 반환한다.
• string은 검색 대상 문자열이며, flags는 옵션으로 사용될 수 있다.
• 이터레이터는 Match 객체를 반환하며, 각각의 객체에서 일치하는 문자열을 가져올 수 있다.

# finditer
pattern = r"\w+"
match_iter = re.finditer(pattern, text)
for match in match_iter:
    print("일치하는 문자열:", match.group())

 

re.sub(pattern, repl, string, count=0, flags=0)

• 문자열에서 정규표현식 패턴 pattern과 일치하는 모든 부분을 repl로 대체한다.
• string은 대상 문자열이며, count는 최대 대체 횟수를 지정할 수 있는 옵션이다.
• flags는 옵션으로 사용될 수 있다. 대체된 결과 문자열을 반환한다.

# sub
pattern = r"Hello"
replacement = "Hi"
new_text = re.sub(pattern, replacement, text)
print("대체된 문자열:", new_text)

 

re.split(pattern, string, maxsplit=0, flags=0)

• 문자열을 정규표현식 패턴 pattern을 기준으로 분할하여 리스트로 반환한다.
• string은 대상 문자열이며, maxsplit은 최대 분할 횟수를 지정할 수 있는 옵션이다.
• flags는 옵션으로 사용될 수 있다.

# split
pattern = r",\s?"
tokens = re.split(pattern, text)
print("분할된 토큰:", tokens)

 

 

KMP(Knuth-Morris-Pratt)법

특정 패턴을 효율적으로 찾는 데 사용된다. 일반적인 브루트 포스 알고리즘과 비교하여 KMP 알고리즘은 패턴을 한 번만 전처리하여 불필요한 비교를 줄이는 특징을 가지고 있다.

 

핵심 아이디어는 "실패 함수"를 계산하여 패턴의 일치 실패 시 패턴을 얼마나 이동시킬지 결정하는 것이다.

실패 함수는 패턴의 접두사와 접미사를 비교하여 일치하는 부분의 길이를 저장하는 배열이다.

이를 활용하여 패턴을 이동시키면서 비교를 수행하므로, 중복된 비교를 피하고 검색 속도를 향상시킬 수 있다.

 

예시 코드

1. 실패 함수

# 실패함수
def compute_failure_function(pattern:str)->list:
    failure = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            failure[i] = j
        else:
            if j != 0:
                j = failure[j-1]
                i -= 1
            else:
                failure[i] = 0
    return failure

2. kmp 수행 함수

# kmp
def kmp_search(text:str, pattern:str)->int:
    failure = compute_failure_function(pattern)
    i = 0  # 텍스트의 인덱스
    j = 0  # 패턴의 인덱스

    while i < len(text):
        if text[i] == pattern[j]:
            if j == len(pattern) - 1:
                return i - j  # 일치하는 패턴의 시작 인덱스 반환
            i += 1
            j += 1
        else:
            if j != 0:
                j = failure[j-1]
            else:
                i += 1

    return -1  # 패턴이 발견되지 않은 경우
    
# 사용
text = "ABABABABCABABABA"
pattern = "ABABC"

index = kmp_search(text, pattern)
if index != -1:
    print("패턴이 발견되었습니다. 시작 인덱스:", index)
else:
    print("패턴이 발견되지 않았습니다.")
    
# 패턴이 발견되었습니다. 시작 인덱스: 4

 

 

보이어 무어법(Boyer-Moor Method)

KMP법 보다 뛰어난 알고리즘으로 실제 문자열 검색에서 널리 사용하는 알고리즘이다.

먼저 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행한다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다.

 

보이어-무어 알고리즘의 핵심 아이디어는 "오른쪽 맞춤(align)"과 "나쁜 문자(불일치 문자)"를 활용하는 것이다.

 

오른쪽 맞춤(Align Heuristic)

• 패턴을 오른쪽 끝부터 왼쪽으로 비교한다.
• 텍스트의 문자를 패턴의 마지막 문자와 비교하며 일치하지 않는 경우, 패턴의 일부분을 텍스트에서 찾은 마지막 문자의 다음 위치로 맞춥니다.

 

나쁜 문자(불일치 문자) 휴리스틱

• 패턴에서 일치하지 않는 문자가 발견되면, 이동 거리를 결정하기 위해 미리 계산된 "오른쪽 이동 테이블"을 참조한다.
• 오른쪽 이동 테이블은 각 문자마다 패턴 내에서 더 오른쪽에 있는 동일한 문자의 위치를 저장하는 배열이다. 이를 활용하여 일치하지 않는 문자의 오른쪽 이동 거리를 결정한다.

 

예시 코드

# 나쁜 문자 테이블
def badCharTable(pattern:str)->dict:
    table = {}
    for i in range(len(pattern) - 1):
        table[pattern[i]] = i
    return table

# 보이어-무어 
def BoyerMoore(text:str, pattern:str)->int:
    m = len(pattern)
    n = len(text)
    if m > n:
        return -1

    badCharacterTable = badCharTable(pattern)
    i = m - 1  # 텍스트의 인덱스
    j = m - 1  # 패턴의 인덱스

    while i < n:
        if text[i] == pattern[j]:
            if j == 0:
                return i  # 일치하는 패턴의 시작 인덱스 반환
            i -= 1
            j -= 1
        else:
            if text[i] not in badCharacterTable:
                shift = m
            else:
                shift = max(1, j - badCharacterTable[text[i]])
            i += shift
            j = m - 1

    return -1  # 패턴이 발견되지 않은 경우


# 예시 사용
text = "ABABABABCABABABA"
pattern = "ABABC"

index = BoyerMoore(text, pattern)
if index != -1:
    print("패턴이 발견되었습니다. 시작 인덱스:", index)
else:
    print("패턴이 발견되지 않았습니다.")
    
# 패턴이 발견되었습니다. 시작 인덱스: 4