데이터구조와 알고리즘 4回_문자열의 일치

4回 문자열의 일치_文字列の照合

#문자열의 일치_文字列の照合

긴문자열(text)에서 짧은 문자열(pattern)을 찾는것

(여러차례 출현하는 경우도 모두)

이 수업에서는 두가지 알고리즘을 설명한다.

-기본적인 알고리즘

-BM(보이어 무어)법

長い文字列（テキスト）から、短い文字列（パターン）を探す 

(複数回出現する場合は、すべて探し出す) 

二つの方法を解説

 – 基本的なアルゴリズム 

– BM法

‡기본적인 알고리즘_基本的なアルゴリズム

텍스트(긴문자열)의 첫번째 문자와 패턴(짧은 문자열)의 첫번째 문자에 맞춰서

첫 글자부터 순서대로 비교

->모두 일치하면 발견

그다음 패턴을 한칸 오른쪽으로 밀어 패턴의 두번째 문자와

텍스트의 두번째 문자와 맞춰 또 비교

->이와같이 하나씩 밀어서 처음부터 비교 

テキストの1文字目にパターンの1文字目を合わせて、先頭の文字から 順に比較

 –> 全部一致したら見つかったことになる

  パターンをひとつ右にずらして、テキストの2文字目に合わせて先頭か ら比較 

–>以下同様に、ひとつずつずらしては、先頭から比較

---------------------------------------------------기본적인 알고리즘 설명--------------------------------------------------------

텍스트와 패턴의 선두를 맞춘다.

패턴의 선두에서부터 비교를 시작한다.

두번째 문자에서 불일치!

패턴을 오른쪽으로 한칸 민다.

다시 패턴의 선두에서부터 비교를 시작한다.

(반복)

--------------------------------------------------------------------------------------------------------------------------------------------------

‡기본적인 알고리즘의 계산량_基本的なアルゴリズムの計算量

텍스트길이 : 𝑛

패턴의 길이 : 𝑚

매번 처음부터 끝까지 비교했다고 가정(최악의 경우)

매번비교횟수 : 𝑛𝑚

따라서 전체 계산량: 𝑂(𝑛𝑚)

テキストの長さ： 𝑛 

パターンの長さ： 𝑚 

毎回先頭から末尾まで比較したとする (これが最悪のケース) 

毎回の比較は𝑛𝑚回 

よって全体では𝑂(𝑛𝑚) 

‡BM(보이어 무어)법_BM（ボイヤー・ムーア）法

텍스트의 첫번째 문자와 패턴의 첫번째 문자를 맞추고 마지막 문자에서 순서대로 앞으로 비교

->모두 일치하면 발견

불일치의 경우 패턴의 정보를 잘 사용하여 가능하면 한 문자보다 많이 뛰어넘는다.

(문자마다 뛰어넘는 갯수가 다르다)

정확하게, 이것은 BM의 단순화 버전이다.

テキストの1文字目にパターンの1文字目を合わせて、末尾の文字から 順に比較 

–>全部一致したら見つかったことになる

 不一致の場合、パターンの情報をうまく使って、可能な場合はパターン を1文字より多くずらす

 (文字によってずらす数が違う) 

正確には、これはBM法の単純化版（1つめのアイデアのみ）

‡보조테이블

패턴 속 각문자에 대해 가장 마지막에 나오는 위치를 구한다.

"a"=10 

"c"=9 

"k"=5 

"s"=11

다른 문자에 대해서는 -1로 설정

-----------------------------------------------------------------BM 알고리즘 설명------------------------------------------------------------

텍스트와 패턴의 선두를 맞춘다.

뒤에서부터 비교한다. 'k'와 's'이므로 불일치

보조테이블에서 k는5이다. 현재 11번째 이므로 불일치. 패턴을 11-5=6 만큼 이동시킨다.

그렇게 하면 텍스트의 불일치 지점이었던 K에 패턴의 마지막 K를 맞춰진다.

  

다시 끝에서부터 비교한다.

k와 s이므로 불일치

아까와 같은 방식으로 패턴을 11-5=6칸 이동시킨다.

텍스트의 k와 패턴의 k가 맞춰진다.

다시 끝에서부터 비교한다.

c와 k이므로 불일치

보조 테이블에서 c는 9이다. 현재는 1번째 이므로 불일치. 패턴을 1-9=-8 만큼 이동시킨다.

c가 맞춰지지만 패턴이 앞으로 되돌아가 버린다. 

되돌아간 경우는 취소하고 한칸 뒤로 옮긴다.

다시 뒤에서부터 비교한다.

a와 s이므로 불일치.

보조테이블에서 a는 10이다. 현재 패턴에서 11번째이으로 불일치. 패턴을 11-10=1만큼 이동시킨다.

다시 뒤에서부터 비교한다.

k와 s이므로 불일치.

11-5=6만큼 이동시킨다.

다시 뒤에서부터 비교한다.

불일치.

보조테이블에서 k는 5이다. 현재 패턴에서는 9번째이므로 불일치. 패턴을 9-5=4만큼 이동시킨다.

다시 끝에서부터 비교한다.

모두 일치!!

모두 일치한 경우에서 한칸만 뒤로 이동시킨다.

(반복)

---------------------------------------------------------------------------------------------------------------------------------------------------

‡텍스트 파일 읽기_テキストファイルを読む

第4回課題

기본적인 알고리즘의 코드와 BM법의 코드를 구현.

*'수업자료'의 샘플 데이터를 사용해야한다.

->두가지 방법의 결과가 일치하는지 확인

샘플 데이터

seq_sample.txt

targets.txt

text_Bagic.c

text_BM.c

처음에 무작정 하다가 total이 하나에 400개넘게 나오고 이러길래 학교에서 리눅스로 도저히 안되겠다싶어서

집에와서 비쥬얼 스튜디오로 브레이크걸어서 컴파일하면서 조금씩 해보니까 됬다ㅠㅠ

처음엔 뭔가 막막해서 구글링했는데 딴 코드보니까 더 혼란스러워서 그냥 내 방법대로 해보자! 하고 끝까지 해봤는데 

결과가 나와서 너무나 감격스러웠다ㅠㅠ 나같은 빠가사리한테도 조그마한 희망이ㅎㅎㅎ

생각보다 간단하게 코드를 짠 것 같아서 뭔가 더 맘에 든다. 맞는건진 모르겠지만 과제점수는 10점 만점을 받았다.

하면서 깨달은 거지만 나는 너무 주석을 안쓰는 것 같다. 이제 주석 많이 다는 연습도 해야겠다.