[6주차] 트라이와 적응형 자료 구조

[hanana1253]

츄라이츄라이

[hanana1253]

요약

• 이진 탐색 트리의 일반적인 분기 방식 (대소 비교)을 확장해 데이터의 추가 구조를 잡아내면, 문자열 집합에서 목표 문자열을 효율적으로 탐색할 수 있다.
• 문자열 데이터에 이진탐색트리를 직접 적용할 수 있지만, 비용이 높아진다.
• 트라이는 단계마다 문자열의 문자 하나를 기반으로 분기하는 자료구조

1. 문자열로 이뤄진 이진 탐색 트리

• 두 문자열을 비교하는 것은 두 숫자를 비교하는 것보다 비싸다.
  • 문자열 비교 연산의 비용은 최악의 경우 문자열 자체의 길이에 비례
  • 문자열이 시퀀스라는 사실과, 문자의 가짓수가 제한되어 있다는 사실을 고려해 계산 비용을 절약하자
• 문자열 비교의 순차적인 성질(시퀀스), 문자의 가짓수는 영어 대소문자 무시하면 26개
  • 문자열의 다음 문자를 기준으로 여러 방향의 분할을 만드는 분할 함수를 정의 가능
  • 이 두 가지 통찰을 결합해 만들어진 자료구조가 트라이로, 문자열의 특성을 추가로 고려해 최적화한 자료 구조

2. 트라이

• 문자열을 접두사를 기준으로 다른 하위 트리로 분할하는 트리 기반 자료 구조
• 트라이의 각 노드는 지금까지 비교한 문자열의 접두사
• 실제 가지 수는 26개보다 적을 수 있다 (zn zc 등 유효한 단어가 아닐 때)
• 모든 노드가 항목을 나타내지 않고, 리프 노드를 제외하면 일부 내부 노드는 완전한 문자열에 이르는 경로 중간의 접두사
  • CAT은 내부 노드이지만 유효하고, CATALOG의 접두사이기도 하다.
  • 이런 모호성을 해결하기 위해 트라이 노드에는 현재 노드의 유효성을 나타내는 값을 저장한다.
  • bool 로 저장하기도 하고, 값의 유무로 유효성을 판단하기도 한다.
• 이진 탐색 트리와 달리 트라이에는 항상 null이 아닌 루트가 있다. 자료구조 생성과 동시에 루트도 생성된다.
  • 빈 트라이의 경우에도 루트 노드에 유효성이 false인 시작 노드를 할당
• 탐색: 이진 트리와 비슷하지만, 다음 글자에 해당하는 가지를 선택 (전체 문자열 또는 이미 비교한 앞부분은 비교할 필요 X)
  • 탐색의 각 단계에서 수행할 비교의 문자열 위치가 달라지므로, 현재 단계의 문자의 위치를 나타내는 인덱스를 재귀적인 탐색 함수에 전달해야 한다.
  • 현재 인덱스와 목표 문자열의 길이를 비교해서 해당하는 레벨인지 확인
    • 목표 문자열 길이와 현재 인덱스가 같으면 현재 노드의 유효성을 검사해 유효한 항목인지 확인한다.
    • 다르면 다음 문자를 검사하며 탐색을 계속한다. 다음 문자에 해당하는 자식이 없으면 null 반환, 있으면 다시 비교 시작
  • 막다른 골목을 만나면 목표 문자열이 없다는 뜻이므로 null 반환
• 추가와 제거
  • 추가할 때는 문자열 탐색 후 막다른 골목에 도달하면 하위 트리를 생성
  • 삭제할 때는 제거 대상 문자열의 길이를 현재 인덱스와 비교했을 때 현재 노드를 제거해야 하는 경우 유효성 값을 false로 바꾼다. 현재 노드가 제거 대상이 아니라면 계속 탐색하면서 끝까지 간 후 거슬러올라오면서 현재 노드를 제거해도 안전한지 여부를 확인한 후 (유일한 자식이라면) 부모 노드에서 빈 가지를 제거한다.
• 모두 목표 문자열의 길이에 비례하는 비용을 갖는다.

3. 트라이가 중요한 이유

• 더 많은 문자열을 추가하고, 공통 접두사를 가지는 문자열 수가 늘어날수록 트라이가 더 비용효율적이다.
  • 트라이의 탐색 비용은 저장된 항목의 개수와 무관하게 변하며
  • 문자열 비교 비용은 비싸기 때문
• 구조가 포함되는 시리얼 번호를 사용하면 앞부분 노드에서 가지 개수를 제한함으로써 저장 공간을 절약할 수 있다.
• 연산 비용을 최적화할 때 데이터 내부의 구조를 더 활용할 수 있다, 즉 데이터에 내재된 구조를 이용하면 알고리즘의 효율성을 개선할 수 있다.

느낀점

• 문자열이 숫자 비교보다 비싸다는 1장의 이야기가 여기서 이렇게 이어지다니 소름!
• p.121 너무 엄격해 보일지 모르지만 진짜 단어들만 최고의 말장난이 어울린다 -> 이게 뭔뜻이지?
• 알고리즘이나 자료구조 공부할 때 항상 트라이에서 지레 겁먹었는데 재밌게 잘 읽었다. 대충 읽어서 그런가?

[hanana1253]

trie, pronouncing it /ˈtriː/ (as "tree"), after the middle syllable of retrieval

trie 라는 단어는 retrieval 의 중간 음절을 따온 거라는 사실 알고 계셨나요?

[thgr8ganzi]

정리

• 들어보기만하고 그때 이해가 안되었는데 이번에 이해를 했습니다.
• 이 자료구조에 한글은 너무 불리하다고 생각했습니다

[hanana1253]

근데 한글이 불리한 이유가 가갸거겨고교... 헿까지 다 해야해서 그런건가요?
저는 그냥 ㄱ - ㅏ 이런식으로 하려나 궁금했거든요.
여전히 영어보다는 종성에 있어서는 자음모음 모두 해야하니 가짓수가 많이 뻗쳐나가긴 하지만.

[hanana1253]

생각해보니 한글 유니코드가 가갸거겨 ~ 헿 까지 다 있으니까 아마 그렇게 해야할거같긴 하네용..

[thgr8ganzi]

네 그래서 개인적으로 불리하다고 생각했어요..

인코딩의 이해1
인코딩의이해2

위의 아티클보고도 그런생각을 했답니다.

보통 구조상 자음 -> 모음 -> 자음 같은 구조로 가야할것 같지만
실제로 사용하진 않지만 끊다 할때 '끊'은(는) 자음 -> 모음 -> 자음 -> 자음 같이 좀 불규칙한것도있고... 하하

[yunseorim1116]

정리
이진트리와 트라이를 비교해보는 유익한 시간이었습니닷
트라이는 완전 첨들어보는데 .. 재밌었어유우

[ella-yschoi]

정리

• 저도 이진 탐색 트리와 트라이를 비교하니 더 내용이 잘 들어왔던 것 같습니다.
• LeetCode에서 Trie를 직접 구현하는 문제가 있는데 풀어보셔요!

[sa02045]

데이터에 내재된 구조를 이용해서 알고리즘의 효율성을 개선할 수 있다!

• 기존 문자열을 다룰 때 비효율성
  • 문자열 비교는 비용이 많이드는 연산임
  • 숫자 데이터는 한번에 비교되지만, 문자열 비교는 문자를 하나하나씩 문자열 길이만큼 비교해야함
  • 만약 데이터 크기가 N인 배열에서 길이가 M인 문자열을 탐색하려면 N * M 만큼의 시간이 필요함!
  • 데이터 크기에 영향을 받지않는 자료구조가 필요함
• 트라이: 문자열을 위한 트리 자료구조
  • 검색, 삽입, 삭제를 문자열 길이 O(L) 시간 복잡도로 처리함
  • 데이터의 크기와 무관하게 문자열의 길이에만 의존하며 처리할 수 있음
  • 단어끼리 접두사 문자열을 공유하여 메모리 절약
• 삽입 연산
  • 루트부터 경로 따라가면서 문자열의 각 문자를 순차적으로 비교
  • 비교해서 없으면 생성, 있으면 자식 노드로 이동
  • 단어가 유효한지 표시하는 boolean
  • 단어가 끝인지 표시하는 boolean 등 보조데이터 추가 가능
• 삭제 연산
  • 루트부터 삭제할 문자열의 문자 따라가며 경로 탐색
  • 문자열 끝에 도달하면 유효한 단어 표시 제거 (또는 단어 끝 표시제거)
  • 제거한 노드가 다른 단어의 일부인지 확인, 자식노드가 있는지 확인
  • 해당 안되면 삭제. 재귀적으로 상위노드로 이동하면서 수행
• 트라이 어디에 써먹나?
  • 문자열을 데이터 관리하고 검색할 때
  • 자동완성기능 - 특정 접두사로 시작하는 모든 단어를 찾아서 추천
  • 철자오류검사 - 입력한 단어가 존재하는지 확인
  • 사전단어추적
• 트라이 자료구조로부터 배울 점
  • 데이터에 내재된 구조를 이용해서 알고리즘의 효율성을 개선할 수 있다!
  • 문자열이라는 데이터의 특성
    • 순차적이다.
    • 문자열을 이루는 문자는 한정적이다.

[ainochi-kor]

정리

문자열로 트리를 구현하여 효율적으로 탐색하는 방법에 대해서 배울 수 있어서 좋았습니다!

[chloe-codes1]

내용 정리

문자열로 이뤄진 이진 탐색 트리

• 이진 탐색 트리는 정렬 가능한 모든 데이터를 저장할 수 있는 구조이다
• 문자열 데이터를 처리할 때 비교 연산 비용이 문자열 길이에 비례한다
• 문자열 비교는 숫자 비교보다 상대적으로 더 많은 비용 발생한다
• 언어에 따라 문자열의 각 위치에서 가능한 문자가 제한적일 수 있다

트라이

• 문자열을 접두사 기준으로 분할하여 저장하는 트리 형태의 자료구조
• 느린 메모리 접근 속도를 보완하고 파일 탐색 성능을 개선하기 위해 설계되었다
• 각 노드는 접두사를 나타내며, 다중 분기를 통해 데이터를 효율적으로 관리한다
• 모든 노드가 데이터 항목을 나타내지는 않으며, 접두사 등 추가 정보를 저장 가능하다
• 탐색 연산의 비교 횟수는 저장된 문자열의 개수와 무관하다

트라이가 중요한 이유

• 공통 접두사를 가진 문자열이 많아질수록 효율성이 증가한다
• 문자열 비교 비용을 줄이고 접두사를 활용해 성능 최적화 가능하다
• 시리얼 번호, 모델 번호 등 짧은 구조적 레이블을 효율적으로 관리할 수 있다
• 접두사를 활용해 저장 공간 절약 및 연산 비용 감소한다

생각

• 트라이 자료구조가 실제로 적용된 사례를 찾아봤는데, Linux kernel의 IP 라우팅 테이블에서 사용된다고 한다
  • 트라이를 사용해서 IP 주소를 prefix 단위로 분리해 저장할 수 있어서 라우팅 경로를 빠르게 탐색할 수 있음!
  • 궁금하신 분들은 이 글을 읽어보세요! IPv4 route lookup on Linux

[ddongule]

오 오늘은 59분이 아니에오

[chloe-codes1]

아아아앗~~!! 맨날 59분에 내던거 알고계셨다니!! 크하하

[ella-yschoi]

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ간파당했다 김주현!!

[iborymagic]

• 트라이: 단계마다 문자열의 문자 하나를 기반으로 분기하는 자료 구조
• 문자열 비교 시 이진 탐색 트리를 사용하는 것은 비효율적
  • 문자열을 각각 비교하는 데에 드는 비용 때문
  • 문자열의 첫 번째 문자에서 시작하여 차이를 발견할 때까지 각각의 문자를 순차적으로 비교해야함
  • 문자열이 상당 부분 중복되면 문제가 심각해짐
  • 최악의 경우, 문자열 비교 연산은 문자열 자체의 길이에 비례

[트라이]

• 현재까지 문자열의 접두사를 기준으로 트리의 가지를 나눔
• 트리가 두 분기보다 많은 분기를 허용
• 트라이의 각 노드는 지금까지 비교한 문자열의 접두사를 나타냄
• 이진 탐색 트리와 달리, 트라이에서는 모든 노드가 항목을 나타내진 않음
  • ex) COFFEE의 중간 노드에 존재하는 COFFE는 유효한 단어가 아님
  • 현재 노드가 유효한 항목인가를 표시하는 is_entry 같은 값을 트라이 노드에 저장
• 완전히 빈 트라이도 문자열의 시작(빈 문자열)을 나타내는 루트 노드를 할당

[트라이 탐색]

• 트라이는 다음 글자에 해당하는 가지를 선택
  • 전체 문자열을 비교하거나, 접두사의 앞부분은 비교할 필요가 없음(이전 노드에서 이미 그 작업을 수행했으므로)
• 현재 단계에서 확인해야하는 문자의 위치를 나타내는 인덱스가 추가 정보로 필요
• 인덱스가 문자열 길이와 같으면 현재 노드가 유효한 항목인지 검사함
  • 특히 탐색이 내부 노드에서 끝나는 경우에 이런 검사가 필요
• 많은 내부 노드를 추가하지만 탐색 비용이 크게 개선
• 성공적인 트라이 탐색의 비교 횟수는 트라이에 저장된 문자열의 갯수와 무관
• 다만, 이런 효율을 얻으려면 메모리 사용에서 상당한 비용 지불 필요
  • 접두사가 중복되면 문자열당 메모리 비용을 감소시키는 데에 도움이 됨

[노드 추가]

• 루트 노드에서 시작하여 트리를 따라 내려가다가 막다른 골목에 도착하면 삽입할 문자열의 나머지 문자들을 저장하기 위해 하위 트리를 생성
• 트라이 생성 과정에서 초기 루트 노드를 할당하므로 루트 노드 생성을 별도로 취급할 필요는 없음
• 문자열의 끝에 도달하면 해당 노드를 유효한 항목으로 표시

[노드 제거]

• 문자열의 끝에 해당하는 노드에서 시작해서 트리를 거슬러 올라가면서 더 이상 필요가 없는 노드를 제거
• 올바른 리프 역할을 할 수 있는 내부 노드에 도달하면 제거를 중단
• 문자열을 제거하려면 루트에서 대상 리프까지 왕복해야하므로 제거 비용도 목표 문자열의 길이에 비례
• 탐색, 삽입과 마찬가지로 제거 비용도 트라이에 저장된 전체 문자열의 갯수와 무관

---

• 따로 공부하기 귀찮아서 맨날 이진 탐색 트리만 하고 트라이는 뛰어넘었는데.. 이번 기회에 관련 문제도 한 번 풀어봐야겠읍니다..

[ddongule]

Trie (트라이)

• 단계마다 문자열의 문자하나를 기반으로 분기하는 자료 구조

• 각 노드에서 발생하는 비교 비용을 크게 감소시킴�

• 문자열을 접두사를 기준으로 다른 하위 트리로 분할하는 트리 기반 자료구조

• 대규모 콘퍼런스의 등록 테이블을 생각하면 편함

  • 성으로 나누어서 굿즈 나눠주기 (ㄱ/ㄴ/ㄷ/ㄹ/ㅁ..ㅍ/ㅎ)

• 탐색

  • 이진 탐색 트리 탐색과 유사 (루트 노드 시작 → 아래로 진행)
  • 다만 트라이는 문자열의 다음 글자에 해당하는 가지 선택
  • 효율성은 높아지지만 메모리 비용이 높아짐
  • 접두사가 중복되면 문자열당 메모리 비용을 감소시키는 데 도움이 됨

• 노드 추가

  • 이 또한 이진 탐색 트리와 유사(트리를 따라 내려감, 삽입할 문자열의 나머지 문자를 저장하기 위해 하위트리 생성 가능)
  • 그러나 이진 탐색 트리와는 달리 한 항목을 삽입하는 동안 노드를 여러개 추가할 수 있음

• 노드 제거

  • 순서가 반대
  • 문자열의 끝에 해당하는 노드에서 시작해 트리를 거슬러 올라가면서 더 이상 필요가 없는 노드 제거
  • 루트에서 대상 리프까지 왕복해야 하므로 제거 비용도 목표 문자열의 길이에 비례

• 중요한 이유

  • 탐색 비용이 단어의 길이와 수에 따라 결정된다는 문제를 해결하는 방법이 트라이
  • 더 많은 문자열을 추가하고 공통 접두사를 가지는문자열 수가 늘어날수록 트라이가 더 비용면에서 효율적
    • 트라이에서 탐색 비용은 저장된 항목의깨수와 무관하게 변함
    • 문자열 비교 자체가 비용이 많이 듬

트라이 배우는 것을 트라이 해보았습니다
이 트라이는 성공일까요 실패일까요
트라이 자체에서 의미를 찾겠습니다..
그럼 20000

[iborymagic]

펀치라인이 충격적이네요

[hanana1253]

나이스 트라이~

[thgr8ganzi]

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[sunhpark42]

• 읽어놓고 코멘트 작성 잊어버렸다. 그래도 호주 즐거웠음
• 트라이 대학생때 정말 이해하기 힘들어했던것 같은데, 지금 와서 보니 또 왜 어려워 했을까 싶긴했다. C언어도 못하면서 바로 자료구조 수업 들은 나.. 반성해
• 인상깊었던 문장: 알고리즘을 개선할 수 있는지 여부를 고려할때는 먼저 현재 접근 방식의 한겨를 이해해야한다. 현재 접근 방식으로 충분하다면, 더 복잡한 자료 구조를 구축할 이유가 없다. / 트라이 응용에서 가장 중요한 점은 연산 비용을 최적화발 때 데이터 내부의 구로를 더 활용할 수 있다는 점이다. 이런 개선은 이 책의 핵심주제, 즉 데이터에 내재된 구조를 이용하면 알고리즘의 효율성을 개선할 수 있다는 점을 다시한 번 보여준다.