Compressing Scrabble Dictionaries (2014)

이 글은 스크래블 단어 검색을 빠르게 하기 위해 사용하는 GADDAG 자료구조의 메모리 압축 기법을 상세히 설명한다. GADDAG는 단어의 모든 회전을 저장하는 트리 구조로, 메모리 사용량이 매우 크기 때문에 캐시 적중률을 높이기 위해 중복 노드 병합과 비트마스크 기반의 효율적 노드 표현 방식을 적용한다. 특히, 자식 노드가 하나인 경우를 위한 특수한 압축과 노드 간 중복 제거를 통해 대규모 단어 리스트도 L3 캐시 크기 내에 적재 가능하도록 압축한다. 이로 인해 스크래블 단어 검색 속도가 메모리 접근 병목 없이 크게 향상될 수 있다.

https://williame.github.io/post/87682811573.html

#datastructure #compression #gaddag #scrabble #cacheoptimization