트라이
트라이 Trie
- 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조(retrieval tree)
- 트리(tree)와 구분하기 위해 /트라이/라고 읽음
- 유의어 사전에서 빠르게 검색하기 위한 자료 구조
트라이의 장점
- 공간 효율성: 단어들의 공통 접두사(Prefix)를 공유하여 저장
- 적은 공간으로 방대한 어휘 사전을 표현
- 빠른 정밀/접두사 검색: 단어의 문자들을 따라 구조를 탐색함으로써 단어 길이만큼의 시간 복잡도
- 특정 노드까지 탐색하여 그 노드에서 파생되는 모든 단어(즉, 해당 접두사로 시작하는 단어)를 쉽게 찾 을 수 있음
- 자연스러운 순회 및 범위 검색 지원: 단어들이 구조 내에서 정렬되어 표현
- 알파벳 순서로 단어를 순회하거나 특정 범위 내의 단어를 찾는 것이 효율
- 전문적 검색 엔진은 FST (Finite State Transducer)와 같은 더욱 발전된 방법 사용
Aho-Corasick 알고리즘
- 트라이를 이용한 문자열 검색 알고리즘
- 파란 노드: 사전에 있음
- 회색 노드: 사전에 없음
- 파란 선: 트라이에 있는 겹치는 문자열 중 가장 긴 것으로 가는 선
- 초록 선: 파란 선을 따라서 도달할 수 있는 노드 중 사전에 있는 것.
- 다음 글자가 매칭되면 검은 선을 따라 다음 노드로 이동
- 매칭되지 않으면, 검은 선을 따라갈 수 있을 때까지 파란 선을 따라 거슬러 올라감
- 노드에 도달할 때마다, 현재 노드가 파란 노드면 현재 노드 값을 출력.
- 현재 노드에서 초록선으로 연결된 모든 노드의 값들도 출력
Aho-Corasick 알고리즘 예시
사전: a, ab, abb, bab, bc, bca, c, caa
텍스트: abccab
① a:1
② ab:2
③ bc:3 c:3
④ c:4
⑤ a:5
⑥ ab:6
FlashText
- Aho-Corasick은 부분 문자열을 모두 찾음
- 대부분의 경우 더 긴 문자열을 찾는 것이 유용 (예: 남남수수학학원, 서핑클럽)
- FlashText: Aho-Corasick의 변형 알고리즘이자, Python 라이브러리
- 설치
!pip install flashtext
- 초기화
from flashtext import KeywordProcessor
kp = KeywordProcessor()
FlashText
- 키워드 추가: Big Apple, Big, Apple을 키워드로 등록
kp.add_keywords_from_list(['Big Apple', 'Big', 'Apple'])
- 키워드 추가: java_2e와 java programmingj의 대표 키워드를 java로 등록
kp.add_keywords_from_dict({"java": ["java_2e", "java programing"]})
- 키워드 찾기:
kp.extract_keywords('I love Big Apple, big computers, java_2e and java programing.')
Þ['Big Apple', 'Big', 'java', 'java']
- Big Apple은 하나의 키워드로 인식
- big computer의 Big을 키워드로 인식
- java_2e와 java programming은 java로 인식