Programming/Algorithm
[Algorithm] KMP
gyu0
2020. 11. 23. 06:34
def kmp_match(txt:str,pat:str)->int:
#txt는 원본 텍스트를 말하며 pat는 비교되어지는 패턴을 말합니다.
"""KMP법으로 문자열 검색하기"""
pt=1 #txt를 따라가는 커서
pp=0 #패턴을 따라가는 커서
skip=[0]*(len(pat)+1)
###########과제 : length 길이에 왜 +1 인지?
# ABCABD를 예로 들었을 때
# 이 소스코드에서는 TXT가 1부터 시작할 때 PP 0과 1의 값을 먼저 비교하며
# 건너 뛰기 테이블에 인덱스를 TXT와 같이 쓰기 위해서 씁니다.
# 즉 TXT (PT)와 0부터 비교하지않고 SKIP과 인덱스를 맞추려니
# PT의 값도 +를 먼저 해주기 때문에 마지막으로 가면 인덱스가 6을 커서해서
# SKIP의 6 인덱스를 건들고나서 후위 판별로 WHILE이 끝나게 됩니다.
# 그래서 SKIP[1]을 0으로 준이유가 인덱스 0과 1을 비교했을 때 PT가 +1이 되고 나서야
# 0인 PP를 그 SKIP[2]에 0과 1을 비교한 결과를 저장해서 결국 SKIP [1]은 교과 DATA를 기준으로 한다면
# 접두사 접미사 비교 방식에 A와 A를 비교한결과라 비교하지 못하는 단독 A에 대해서는 0을 줍니다.
# ######################################################################
#이 소스코드에서는 pt는 +를 해주고 그에 맞는 값을 스킵에 후에 넣어주기 때문입니다.
#만약 첫번째 값을 비교하는 순서를 넣어주면 len 값도 +1없이 0부터 쓸 수 있습니다
#
#이 소스코드에서는 불필요한 첫번째 비교 연산을 줄여주려고 한것 같습니다.
########################################################################
# ABCABD를 예로 들자
# 건너뛰기 표를 만드는 곳
skip[pt]=0
while pt!=len(pat):
# pt의 값은 알고리즘 특성상 마이너스없이 계속가기 때문에
# len(pat)값이 되면 그만둡니다.
# 실질적으로 0,1,2,3,4,5 를 해주고 값 6이 되면 끝냅니다.
# pt의 초기 값은 1과 pp는 0이다.
# 이 말은 즉슨 처음 패턴의 pp와 pt를 0과 1인덱스를 비교한다.
if pat[pt]==pat[pp]:
pt+=1
pp+=1
skip[pt]=pp
# 만약에 pt값과 pp가 맞으면 건너뛰기에 pt인덱스에 하나가 맞으면 pp값이 +되었다(같으니까)
# -> 문자열중에 하나가 같으니까 그 PT인덱스+1에 (스킵에 포커스)에 1(pp가 +된 값)을 넣어줍니다.
# -> 문자열중에 넘어가서 연속으로 2개가 맞으면 pp는 2가되며 이것을 pt+1인덱스에(스킵에 pt 포커스)넣어주면
# ->2가 연속으로 두개가 맞았다는 것을 의미
# 0,1이 맞아서 또 넘어가면 1(PP),2(PT) 가 될것이니까 당연히 SKIP[pt+1]에 들어가는 원리
elif pp==0:
pt+=1
skip[pt]=pp
# 여기서 첫번째 IF를 거쳐서 같지않다면!!!!!!!!!!!!!!!!<이것을 주의해야됨
# 같지 않을때 이 ELIF로 오기때문에 같지않으면 SKIP 알맞은 인덱스에 0이 들어가야됨.
# 해당 1이든 2든 3이든 처음 인덱스 a(PP=0)와 같지 않지만 a 즉 처음이면
# pt만 +1을 해줌으로써 비교 당하는 인덱스를 0과 다음 pt+1을 비교함
# ->이유는 당연히 처음 인덱스와 그 인덱스가 안맞았으니
# ->처음 인덱스와 그의 다음인덱스(만약 계속 맞지 않다면 0과 pt+len(pat)까지 갈 것이다.)
# ->를 비교해야 합니다.
# ->그리고 건너뛰기표에 해당 인덱스는 하나도 맞지 않았다는 표시로 (PP=0)0을 집어넣습니다.
else:
pp=skip[pp]
# 제일 핵심부분
# 위의 내용까지는 단순 그 자체이다 근데 제일 헷갈렸던것은 여기입니다.
# 이쪽이 핵심부분인것 같기도 합니다.
# 근데 계속 봤더니 진짜 정말로 단순합니다.
# pt : 0 1 2 3 4 5 6
# value: - 0 0 1 2 #이 부분은 두개가 일치하다는 뜻 즉, 패턴의pt: 3,4인덱스와 pp=0,1인덱스가
# 맞아떨어졌다는 뜻인데 다음 pt=5 pp=2 (둘다 맞아서 +1씩 된상태) 일때 d와 c는 일치하지 않습니다.
# 그러면 일치하지 않는 pp의 이전 인덱스인 pp(2)-1 이다.(하지만 아직 조건(일치한다 첫번째 if)가 맞아떨어지지 않아서 1입니다.)
# pp=1을가지고 건너뛰기 그래프의 pp=1 skip[1]로 가게 되면 그 때 까지는 맞았던 건너뛰기 그래프의 값 0 (개수)만큼 pp로 돌아와서
# 이전으로 커서를 옮기고 (만약에 1이면 pp의 틀린 부분의 바로 1전인 부분부터 ) 옮겨진 그쪽 pt부터 해당 pt에 pp를 0으로놓고 다시
# 검사를 시작합니다.
# 다른 예로 만약 틀린 위치 pp에서 이전 pp인덱스로 skip을 찾아가면 어디서부터 비교를 해야하는지 (다시비교해야할 pp의 값) 를
# 제공합니다. 그러면 pp를 해당인덱스로 잡아서 틀린위치 pt는 그대로 두고 skip에서 제공받은 인덱스를 pp로 맞춰서 pt와 pp를 비교합니다.
# 교수님 이거는 제가 과제하면서 kmp알고리즘을 이해하기에 좋아서 일단 기록했습니다.
# https://www.youtube.com/watch?v=q-SMEUwcnJI ->part1
# https://www.youtube.com/watch?v=79F67cXaDUs ->part2
#######문자열을 검색하는 란 ########
pt=pp=0
while pt!=len(txt)and pp!=len(pat):#검색이니까 둘다 처음부터 비교
if txt[pt]==pat[pp]: #txt와 pat의 인덱스 문자열이 같으면
pt+=1
pp+=1
# 각각 인덱스를 +1시켜서 다음 문자열을 비교할거다!
elif pp==0:
pt+=1
# 만약에 문자열이 다르고 패턴의 첫번째 값을 txt값과 비교했으면
# pt에다가 +1을 시켜서 다음 텍스트인덱스에 패턴 첫번째와 같은 값이 있으면
# 이라는 조건이다.
else:
pp=skip[pp]
# 위에서 설명했던 것 처럼 검색 중 값이 맞지 않을 시에
# 단, 이 알고리즘 특성상 o(n+m) 이라서 pt는 계속 훑기만 +만 한다.
# n은 텍스트를 한번 훑는 횟수
# m은 건너뛰기 표를 만드는 횟수
# 그래서 검색에 실패할 시에는 매칭에 실패한 위치의 전 pp인덱스를 skip 인덱스로 취해 찾으면
# 어디서부터 다시 검색하면 될지 pp의 인덱스를 반환합니다.
return pt-pp if pp==len(pat) else -1
# len pat를 좇는 pp값이 pat len과 일치한다는 것은 pt -pp를 해주면
# ex) pt 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# pp 12 <len 이 12이며 pp도 12에 이르렀을 때
# pt는 15까지 while조건에 맞춰 다 카운트 했을거고
# 15 - pp(패턴 len)을 해주면 그 패턴의 시작 인덱스가 나옵니다
if __name__=='__main__':
s1=input('텍스트를 입력하세요.: ')
s2=input('패턴을 입력하세요.: ')
idx=kmp_match(s1, s2)
if idx==-1:#위에서 못찾았을때 -1 리턴
print('텍스트 안에 패턴이 존재하지 않습니다.')
else:
print(f'{(idx + 1)}번째 문자에서 일치합니다.')
https://www.youtube.com/watch?v=q-SMEUwcnJI ->part1
https://www.youtube.com/watch?v=79F67cXaDUs ->part2
참고 링크는 유투브 링크를 달았습니다.
강의 참 맛집이네요 감사합니다.
교수님께서 왜 코드의 skip 리스트가 +1이 되는지 적어오라고 하셔서 풀어봤습니다.
인덱스를 맞춰주기 위해선가요?... 교수님이 금요일에 피드백 해준다고 했으니까 그 때 다시 수정하는 걸로 하자!
맞겠지? 먼저 +를 시켜주고 +된 pp와 pt변수를 이용해서 skip을 조정해주는 거니까...
+가 필요 없기도 한데 저 소스코드의 while 조건 문을 맞추고 먼저 +시키는 pp와 pt를 나중에 연산시키면 될 것 같기도 하다.
아무튼 피드백은 금요일날 하는 걸로 하겠습니다!