▲

아이슬란드어 이름 굴절 패턴을 3.27kB 트라이로 압축하기

 (alexharri.com)
2P by GN⁺ 2일전 | ★ favorite | 댓글 1개
  • 아이슬란드어 개인 이름의 굴절 처리는 문맥에 따라 4가지 형태로 변화함
  • 데이터 기반 자바스크립트 라이브러리를 통해 입력된 이름에 대해 적합한 문법적 격을 반환하는 기능 개발
  • 모든 이름을 직접 저장하면 용량 증가와 데이터 누락 문제가 발생하여, 트라이(trie) 구조와 압축 기법을 활용해 해결함
  • 트라이 압축 덕분에 공통 패턴 기반 자동 유추가 가능하고, 데이터의 80% 이상을 커버하는 매우 작은 크기의 데이터베이스 달성함
  • 보통 상황에선 74% 이상의 정확도를 보이며, 공공 부문과 정확성이 중요한 상황엔 별도의 스트릭트(strict) 버전을 제공함

문제의 배경

  • 아이슬란드어 인터페이스에서 개인 이름을 표시할 때, 굴절(declension) 로 인해 어려움 발생함
  • 아이슬란드어 이름은 주격, 목적격, 여격, 소유격 등 4가지 문법적 격에 따라 다른 형태를 가짐
  • 데이터베이스에는 보통 이름이 주격 형태로 저장되어 문맥상 다른 격이 필요할 때 어려움이 생김
  • 올바른 형태를 쓰지 않으면 네이티브가 아닌 느낌이나 어색함을 줌

데이터 수집 및 정제

  • 아이슬란드는 Árnastofnun이 관리하는 DIM(Database of Icelandic Morphology) 데이터를 오픈함
  • 이름에 대한 굴절 데이터는 Kristín’s Format(K-format) CSV로 가공 가능함
  • DIM 전체 데이터는 700만 행으로 지나치게 방대하나, 공식 승인된 개인 이름(4,500개) 만 추려 3,600여 개에 대해 굴절 정보를 확보 가능함
  • 각 이름에 대해 주격~소유격 형태 배열을 구성할 수 있음

라이브러리 기본 구조

  • 초기 구현은 이름~격 변형 배열로부터 적합한 형태를 반환하는 applyCase 함수로 시작함
  • 그러나 단순 배열 로딩 방식은 용량(30kB gzipped) 이 큼
  • 데이터에 포함되지 않은 이름에 대해서는 대응 불가하다는 한계 있음

중복 제거와 패턴 추출

  • 이름의 4가지 형태 간 공통 접두사를 추출해 각각의 접미사 집합(suffix encoding) 만 저장하여 중복 최소화
  • 같은 굴절 패턴을 따르는 이름들이 많음을 발견함

패턴 매칭을 위한 트라이(trie) 도입

  • 트라이 구조(접미사 기준 역순 삽입) 를 통해 비슷한 패턴을 공유하는 이름군의 값 매핑 최적화
  • 공통 패턴(name endings) 하에 한 번만 굴절 정보를 저장, 새로운 이름에도 높은 예측력 확보

트라이 압축 및 최적화 과정

  • 서브트리의 리프(leaf)마다 값이 같으면 상위 노드에 값을 할당하고 자식들을 삭제해 트리를 압축함
  • 이를 통해 노드 수를 15.4%까지 감소, 용량을 4.01kB까지 축소함
  • 형제 리프 노드 중 값이 동일한 것들을 하나의 노드로 병합하는 2차 압축으로 3.27kB까지 도달함

트라이 성능 및 일반화

  • 새로운 이름 입력 시, 유사 패턴 기반 자동 굴절 가능함
  • 실제로 알려지지 않은 이름들에 74% 옳은 굴절, 26% 오류를 보였고, 실 이용자 기준 오류율은 0.34%에 불과함
  • 데이터의 정규성(regularity)과 포괄성(comprehensiveness) 이 높을수록 압축 및 자동 추론 정확도 상승 효과 있음

실제 라이브러리 및 적용

  • 최종적으로 압축 트라이를 사용하는 beygla 라이브러리로 배포
  • 최소 사이즈(4.46kB)와 더욱 엄격하고 완벽한 맞춤형 strict 모듈(15kB) 로 제공함
  • 공적 문서 등 100% 정확성이 필요한 곳엔 strict 버전, 일반 웹앱엔 경량 버전 선택 가능함

결론 및 확장 가능성

  • 트라이를 활용한 언어 굴절 패턴 데이터 압축은 아이슬란드어 외 여러 굴절 언어의 인명, 주소, 기타 명사 처리의 자동화에 적용 가능함
  • 정규성 높은 데이터와 트라이 압축 조합이 동형굴절 처리 자동화의 데이터/성능 효율 극대화 방안임

참고/감사의 글

  • beygla 개발 과정에서 다양한 전문가 피드백과 최적화가 이루어졌음
  • 트라이의 추가 압축으로 3.43kB → 3.27kB까지 용량 절감함

요약

  • 아이슬란드어 이름 굴절 자동화 문제를 패턴 기반 트라이 데이터 구조로 소형화, 자동화한 사례임
  • 올바른 용량–정확도 트레이드오프를 고려한 실무적 데이터 처리 전략 예시로 시사점이 큼
▲
GN⁺ 2일전  [-]
Hacker News 의견

  • 고등학교 때 스페인어를 처음 배울 때, Windows용 소프트웨어를 써서 동사 원형과 시제가 쏟아지듯 나오고 그에 맞게 동사 변형을 입력해야 했던 경험이 있음. 이런 훈련 덕분에 문법 규칙이 몸에 배어서 능숙해졌음. 하지만 러시아어를 배울 때는 격 변화가 갑자기 어려워졌고, 비슷한 패턴을 설명하거나 연습할 수 있는 앱을 아무리 찾아도 찾지 못했음. 혹시 이런 용도의 (웹 혹은 macOS/iOS) 앱을 아는 사람이 있는지 궁금함

    • Anki에서 "KOFI(Konjugation First)"라는 방법을 사용하는 플래시카드 덱이 있음. KOFI는 언어 학습 전에 먼저 모든 활용 패턴을 익히는 방식을 의미함. 프랑스어를 공부한 뒤 활용 실력이 부족해서 나중에 이 방식을 써 봤고, 문법적으로 틀리게 말해도 일상적 소통엔 문제가 없지만, 원하는 수준은 아니었음. 이 방법은 언어를 배우기 전에 모든 활용 패턴을 단기간에 익히는 게 목표임. 언젠가 새로운 언어에는 진지하게 적용해보고 싶음. 프랑스어에 대한 흥미는 줄어들어서 중도 포기했음. 관련 Anki 덱 링크

    • 러시아어를 배우면서 spaCy Python 모듈과 러시아어용 대형 모듈을 조합해서 문맥 기반 표제어화와 문법 태그 추출을 해주는 스크립트를 만든 적이 있음. 그런데 실제로 러시아어 실력이 늘 때는 변화를 논리적으로 해체하려는 시도를 내려놓고, 사용 경험과 반복을 통해 머릿속에 패턴(예외 포함)의 라이브러리를 쌓는 게 훨씬 효과적이었음. 참고로 여기서 말하는 문맥은 문장 내에서의 의미임

    • 25년 전 스페인어를 독학할 때 스페인어/영어 사전을 썼음. 동사 원형에 숫자 인덱스가 붙어서 같은 활용 패턴을 가진 그룹으로 분류되어 있었음. 사전 앞부분엔 각 그룹별 대표 동사의 모든 시제 활용표가 있었음. 불규칙 동사는 별도의 인덱스로, 마찬가지로 비슷한 불규칙 동사끼리 같은 그룹으로 묶여 있었음(예: tener, detener). 모든 동사가 몇십 개의 고유 패턴으로 깔끔하게 정리됨. 이 시스템을 활용한 퀴즈 소프트웨어를 만들 생각도 했지만 결국 만들지 못했음. 기사에서 언급한 reverse-string trie 패턴이 이런 분류 방식에도 쓰일 수 있을지 궁금함

    • 러시아어의 격 변화를 익히기 위해 전치사+형용사+명사의 조합으로 플래시카드를 만들어 암기 속도를 높이려는 아이디어가 있었음. 라틴어를 예전에 먼저 배웠는데, 라틴어 격 변화는 빠르게 외우는 게 기대되지 않지만(수도승이라면 모를까?) 러시아어는 빨리 익히고 싶었음. 하지만 결국 프로젝트로 이어지진 못함

    • 스페인어 활용 연습을 위해 iOS용 ConjuGato를 사용하고 있음. 게임 모드에서는 동사 원형/시제/인칭이 주어지고 활용형을 떠올리는 방식임. 불규칙 동사만 따로 연습할 수 있어 예외를 익히는 데 효과적임

  • 데이터베이스에 격 변화 정보가 누락된 800개 이름의 경우, 직접 수기로 격 변화를 부여하는 게 가장 직관적인 해결책 같음. 원어민이라면 몇 시간 내로 끝낼 수 있고, 완전히 생소한 이름일 경우에도 적어도 명백히 어색하지 않은 형태로 추정할 수 있을 것임. 또는 LLM에게 시키면 아주 저렴하게 할 수 있음. 결과를 이런 trie 구조로 인코딩해 배포하는 건 여전히 좋은 생각임. 다만, trie를 격변화 추정기로까지 쓸 필요는 없음

    • 이름을 더 많이 다루는 게 바람직함—DIM에서는 계속 보완되어야 하는 부분임. 아이슬란드에서는 허가된 이름 리스트에 자주 새로운 이름이 추가되어서 항상 갭이 생길 수 밖에 없음. 나로선 직접 데이터를 추가하기에 확신이 부족하고, 100개의 미확인 이름 결과를 검토할 때마다 “이게 맞나?” 싶은 경우가 종종 있었음. 비슷한 이름을 DIM에서 조회해보고 “나는 그렇게 변화시키진 않을 텐데”라고 여러 번 생각했음. 그래서 DIM 데이터를 언어 전문가가 유지하는 ‘진실의 소스’로 삼음

    • 손작업도 좋지만, 공식 리스트에 없는 이름(외국 이름 등)에는 여전히 한계가 있음. 나도 중앙집중식 이름 리스트가 있는 나라에 살고 있지만, 예외 요청이 가능하고, 리스트가 생기기 전에 태어난 사람이나 이민자 등은 리스트에 이름이 없을 수 있음. 이런 여러 복합 상황에서 ‘대충 적절한 변화형 예측’ 기능이 여전히 유용함

    • LLM이 trie보다 격변화 예측을 잘 한다고 볼 근거는 찾지 못했음(실제 예시가 LLM의 학습 데이터에 들어있지 않다면, 웹 검색이 더 나을 것임)

    • 기존 LLM이 이미 이런 패턴을 학습하고 있는지 궁금증이 생김

  • Rails가 이 문제를 자동으로 처리해주는지 확신은 없지만, 과거엔 이런 마법을 잘 부렸음. 예전에 pluralise의 소스코드를 봤는데, 웨일스어의 불규칙 복수 규칙까지도 다 인코딩 되어 있었음

    • Rails가 정말 좋아서, 웬만한 기능을 위한 메서드가 다 마련되어 있음

  • 한 가지 최적화 아이디어는, trie가 접미사 스트링 자체로 바로 매핑하는 대신, 고유 접미사 배열을 만들어서 trie에서 그 배열의 인덱스로 접근하게 하는 방식임. 예를 들어:

    const suffixes = [",,,", "a,u,u,u", ",,i,s", ",,,s", "i,a,a,a", ...];

    그리고 다음과 같이 인덱스를 참조함:

    var serializedInput = "{e:{n:{ein:0_r: ..."

    • Claude Code로 직접 해보니 gzip 상태에서 오히려 100바이트 늘고(3456 -> 3556), 압축 전 사이즈만 20% 줄었음. gzip 자체가 반복되는 패턴에 대해 이미 최적화가 잘 되어 있어서 그런 듯함

    • 한 걸음 더 나아가 접미사 그 자체를 trie에 넣고, 동일한 서브트리를 식별해 중복 처리하는 방법도 있을 것임. gzip을 쓸 수 있다면, 접미사 배열을 활용하는 똑똑한 최적화 방법이 분명 있을 것 같음. 바이너리 최적화 포맷을 쓴다면 더 나을 수도 있음

  • 개인적으로 비압축 상태에서 <1kb로 처리할 수 있는 마법 같은 해결책이 있을 것 같다는 생각이 계속 듦. 100% 정확하게 이름을 분류하는 최소화 정규표현식 리스트를 만들어 보는 방법? 아주 큰 bloom filter? 아니면 일반 해시 대신 특화된 feature를 이용하는 방식?

  • 마치 악몽 같은 인터뷰 문제 같음. trie를 뒤집어서(역순으로) 사용하는 일은 평생 딱 한 번쯤 쓸 일인데, 그 한 번 사용하면 마법사 소리 들을 듯함

    • trie를 뒤집은 게 아니라 이름을 역순으로 넣었다는 게 더 정확하게 보임

  • 이런 처리를 JS에서 하기보다는, 데이터베이스에서 모든 name-case 조합을 반환해서, 표시 시점에 필요한 것만 골라 뿌려도 될 것 같음. 즉, 현지화 레이어에서 처리하는 방식임. 교차 언어 상황에서는 어떻게 될지 궁금함. 아이슬란드 UI가 프랑스 이름을 다룰 때는 무조건 주격만 쓸 것 같고, 영어 UI가 아이슬란드 이름을 다룰 때도 마찬가지일 것 같음. 결국 유저를 직접 지정/부르는 문맥이나 관리자 패널(“user x가 user y에게 응답”) 등에서만 필요성이 커질 듯함

  • “idur”, “tur”, “ður”로 끝나는 특정 격변화 패턴의 이름이 88개나 있지만, 동일한 접미사가 항상 같은 격변화 패턴을 따르진 않음. 문제는 단순한 규칙 같으면서도 실제로는 무척 흥미로움. 접미사 패턴이 바로 앞 음절 발음과 관련이 있을까? 만약 미지의 이름을 더 잘 대응하려면 단순히 글자 기반이 아니라 이름의 발음 표현을 NLP로 뽑아 trie 등으로 조회해야 할까 궁금함

    • 이런 고민을 하다 보면 Dependent Types 관련 토론으로 빠질 수 있으니 조심해야 함

    • 예리한 아이디어임. 실제로 동일한 발음의 이름도 격변화 패턴이 다른 경우가 있음. 예를 들어:

      • Ástvaldur -> ur,,i,ar
      • Baldur -> ur,ur,ri,urs “aldur”로 끝난 두 이름이 똑같이 발음되나 격변화 패턴이 다름. “Ástvaldur”의 패턴을 “Baldur”에 적용하면 마지막 세 형태가 정말 어색하게 느껴짐(실제로 아이슬란드인 파트너에게 물어봄). 아이슬란드어는 표기와 발음이 거의 일치하는 편이므로, 발음 기반 trie를 써도 큰 차이는 없을 것 같음

  • beygla/strict 상황에서는 perfect hashing을 대안으로 생각해볼 수 있음

    • 모든 값이 고유하지 않은 상황에서는 일반 perfect hashing보다 더 압축이 가능할 것임. 해시 버킷 하나에 여러 name->suffix 쌍을 집어넣을 수 있음. 다만 이 경우 “처리 불가한 이름” 판별 기능은 없어짐

  • 아이슬란드어 이름 격 변환이 충분히 결정적인 패턴을 가질 정도로 단순해서 이런 방식이 잘 통하는지 놀라움. 언어라는 게 일반적으로는 상당히 복잡한데 말임

    • 아이슬란드는 인구도 적고 언어가 국가에서 적극적으로 관리된다는 점이 작용했을 것임
답변달기