[AlgoDev] 트라이(Trie)를 이용한 메시지 입력 최적화

AI 기반 채팅 서비스를 운영하다 보면, 유저는 다양한 캐릭터와 대화하게 되고, 심지어는 함께 그룹 채팅을 하는 경우도 있다. 실제로 몇몇 AI 기반 채팅 서비스는 그룹 채팅 기능을 지원한다.

우리 서비스에서도 여러 캐릭터를 초대할 수 있으며, 채팅방 내 캐릭터 정보를 한 번에 관리할 수 있는 UI를 제공한다.

롤플레잉(RP) 기반 서비스 특성상, 사용자가 특정 캐릭터의 발화를 직접 입력해야 하는 경우가 자주 발생하는데, 매번 이름을 손으로 타이핑하는 것은 꽤 번거롭다.

그래서 아래와 같이 캐릭터 이름의 접두사(prefix)를 입력하면 자동완성되는 기능을 구현하게 되었다.

또한 캐릭터를 클릭하면 단순히 이름을 붙여넣는 것이 아니라, 아래처럼 해당 캐릭터의 발화를 입력 중이라는 상태를 명확히 보여주는 UI를 적용했다.

이 기능을 구현하기 위해 크게 두 가지 문제를 고민했다.

입력한 접두사로 어떤 캐릭터가 후보인지 어떻게 판별할 것인가?
Input Field에서 “현재 특정 캐릭터의 발화를 입력 중”임을 어떻게 자연스럽게 표시할 것인가?

1. 접두사 기반 캐릭터 검색: Trie 적용

Trie – Wikipedia

We’re on a journey to advance and democratize artificial intelligence through open source and open science.

en.wikipedia.org

채팅방에 동시에 존재하는 캐릭터 수는 많아야 10명 내외이므로,
단순 반복문으로도 O(N * M) 수준으로 충분히 빠르다.

하지만 입력 이벤트는 글자 입력마다 실행되기 때문에,
조금 더 효율적이고 구조적인 방식을 도입하고자 Trie를 사용했다.

아래는 위 예시를 Trie로 구성한 그래프다.

(root)
 ├── A
 │    └── s
 │         └── u
 │              └── k
 │                   └── a   (Asuka)
 │
 ├── B
 │    └── e
 │         └── n             (Ben)
 │
 ├── E
 │    ├── m
 │    │    └── i
 │    │         └── l
 │    │              └── y   (Emily)
 │    │
 │    └── v
 │         └── e             (Eve)
 │
 └── N
      └── a
           └── t
                └── e        (Nate)

(root)
 ├── A
 │    └── s
 │         └── u
 │              └── k
 │                   └── a   (Asuka)
 │
 ├── B
 │    └── e
 │         └── n             (Ben)
 │
 ├── E
 │    ├── m
 │    │    └── i
 │    │         └── l
 │    │              └── y   (Emily)
 │    │
 │    └── v
 │         └── e             (Eve)
 │
 └── N
      └── a
           └── t
                └── e        (Nate)

위 그래프에서 E 글자를 가진 노드를 타고 들어가면 그 하위에 있는 단어가 자동완성 단어의 후보가 된다.

아래는 자동 완성 기능의 플로우이다.

1. `getLastChunk`로 현재 입력 중인 단어를 가져온다.

getLastChunk 함수는 현재 입력 중인 단어를 가져온다.

2. 트라이 자료구조의 아래 유틸 함수를 활용하여 현재 캐릭터 리스트를 가져온다.

TypeScript

const getAutoCompletionCharacterList = (userInput: string): Character[]

const getAutoCompletionCharacterList = (userInput: string): Character[]

3. 그 길이가 1 이상이라면 자동 선택 창을 보여주고, 0번째 요소를 Input Field 내부에 자동 완성으로 보여준다. (PC면 Tab으로 자동 완성, 모바일이면 터치로 자동 완성 가능하도록 하기 위함이다.)

위 과정을 통해 어렵지 않게 트라이 자료구조를 활용하여 캐릭터 이름 자동완성 기능을 구현할 수 있었다.

2. 특정 캐릭터 발화 입력 표시하기

“지금 어느 캐릭터의 발화를 입력하고 있는가?”
이 상태를 명확히 보여주는 것이 UX적으로 매우 중요했다.

이를 위해 메시지 내부에서 커스텀 태그 규칙을 사용하기로 했다.

예를 들어, 캐릭터 ID가 690ada09a7d4a04c4c7a79d5라면,
메시지 내부에는 아래와 같은 문자열을 삽입한다.

"<690ada09a7d4a04c4c7a79d5>
</690ada09a7d4a04c4c7a79d5>"

그리고 커서를 태그 사이로 이동시키면 된다.

렌더링 시에는 이 태그를 파싱해 아래처럼 표시한다.

추가로 아래와 같은 다양한 Edge Case도 함께 해결했다

오른쪽 화살표를 누르면 캐릭터 발화 블록에서 자연스럽게 빠져나오도록 처리
Backspace 시 태그 삭제 처리
중첩 입력 방지
…

최적화 포인트

현재 사용 중인 사용자 메시지를 가져오는 코드는 단순히 “split 후 마지막 요소로 갖고오기”로 구현할 수도 있으나, 문자열을 뒤에서부터 탐색하며 공백을 처음 만날 때까지만 Buffering 후 반환하는 방식으로 구현했다.

이 방식은 대부분의 경우 10글자 이내에서 종료된다.
입력 전체 길이가 매우 길어도 매번 O(len(s)) 전체 탐색을 하지 않아도 된다.

자동완성 후보 탐색도 Trie 기반으로 최적화했기 때문에
글자 입력 시 반복적으로 발생하는 비용을 효과적으로 줄일 수 있었다.

RP 기반 AI 채팅에서 캐릭터 이름 자동완성과 캐릭터 발화 입력 인식은
별거 아니지만 사용성에 큰 영향을 주는 기능이라고 생각한다.

Trie로 prefix 검색을 최적화
메시지 내부에 커스텀 태그 규칙을 적용한 발화 관리 UI
현재 입력 중인 단어를 가져오는 함수 최적화를 통해 입력 지연을 줄이기

서비스의 특성과 사용자의 행동 패턴을 고려해 입력 비용을 줄이는 방향으로 고민한 결과 만들어진 기능이라는 점에서 겉으로 보기에는 별 거 아닌 기능이지만, 많은 디테일이 들어간 작품이라고 생각한다.