[Data Structure] 문자열과 해시: String, Hash, Trie, KMP

String

• string : 문자들로 구성된 배열. s[0], s[1], ..., s[n-1], [\n0]
• Substring(부분문자열): S의 i번~j번의 연속된 글자로 구성된 문자열: s[i...j]
• cf)Subsequence(부분 수열): 문자열의 일부 글자가 원래 순서 유지하며 나열된 형태. 연속적이진 않지만 중간중간 뽑아내서 나열.
• prefix(접두사): S의 0번 글자부터 a번 글자까지 구성된 부분 문자열
• suffix(접미사): S의 a번 글자부터 끝까지로 구성된 부분 문자열

Hash

• 임의 길이의 데이터(ex. 문자열)를 고정된 길이의 데이터(ex. 정수)로 매핑하는 함수
• 해싱(hashing): 키(key, 매핑 전 데이터)를 값(hash value, 매핑 후 데이터)으로 매핑
• 해시테이블이라는 자료구조에 키(data), 해시값(index) 저장.
  • 버킷(bucket)(슬롯(slot))에 데이터 저장
• 장점
  • 적은 자원으로 많은 데이터를 효율적으로 관리 가능
  • index에 해시값을 사용 → 모든 데이터를 살피지 않고 검색, 삽입, 삭제를 빠르게 수행 가능
  • 계산복잡성 O(1) 지향
  • 키와 해시값 사이에 직접적인 연관이 없어 보안에 좋음
  • 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들어 '데이터 축약' 기능 수행 가능
• many-to-one 으로 대응 → 다른 데이터가 같은 해시 값으로 매핑되어 충돌되는 해시 충돌(Hash Collision) 발생
  • 해시 충돌 해결법
    • Chaining
      • 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않고 연결리스트로 체인처럼 노드를 추가해나가는 방식
      • 장점) 유연함
      • 단점) 메모리 문제 야기 가능
      • 시간복잡도: 삽입 - O(1) / 검색, 삭제 - O(1) (최악의 경우 O(n))
      • 
    • Open Addressing
      • 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용(이미 다른 데이터가 저장되어 있으면 다음 버킷에 저장)
      • 장점) 메모리 문제가 발생하지 않음(비어있는 테이블의 공간을 활용하기 때문)
      • 단점) 해시 충돌 발생 가능 → 해시테이블 내 새로운 주소를 찾는 탐사(probing)로 해결
        • 선형 탐사: 정해진 고정 폭으로 옯겨 해시값의 중복을 피함
        • 제곱 탐사: 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함
      • 시간복잡도: 탐사 횟수에 비례
    • 해시함수
      • 특정 값에 치우치지 않고 해시값을 고르게 만들어내는 좋은 해시함수를 이용
      • division method: 숫자로 된 키를 해시테이블의 크기로 나눈 나머지를 해시값으로 반환
      • universal hashing: 다수의 해싱함수를 만들고, 해시함수의 집합에서 무작위로 해시함수를 선택해 해시값을 만드는 기법

Finite State Machine & Pattern matching

• 𝑆의 부분문자열을 입력으로 하고, 상태를 패턴의 매칭 수로, 상태 전이는 패턴마다의 알파벳으로 설정하면 유한 상태 기계를 통해 패턴매칭을 시도 가능
• FSM 이용
  • 정규표현식(Regular Expression) : 특정한 규칙을 가진 문자열의 집합을 표현할 때 사용하는 식
  • Knuth-Morris-Pratt(KMP) 알고리즘 : 해싱과 달리 확률론적이지 않은 패턴매칭 알고리즘. 모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있음
    • 접두사, 접미사 활용해 매칭할 문자열 점프하는 방법.
    • 일대일 문자열 패턴 매칭
    • KMP 코드s

Trie

• 검색(retrieval)의 줄임말. 각 노드가 배열로 이뤄진 트리
• 장점) 문자열 탐색 시 O(1)
• 단점) 상수 시간의 실행 시간 제공 위해 메모리 과다 사용
• Aho-Corasick(아호-코라식) 알고리즘에 사용됨
  • 일대일이 아닌 일대다 문자열 패턴 매칭
  • KMP의 확장

---

참고 링크

• ICPC 신촌 2022 겨울 알고리즘 캠프 - 문자열
• https://github.com/seohyun319/CS-interview-study/blob/main/01.%20DataStructure/08_Hash.md
• https://github.com/seohyun319/CS-interview-study/blob/main/01.%20DataStructure/09_trie.md
• kmp 알고리즘 - https://blog.naver.com/ndb796/221240660061