트라이(접두사 트리) 계산기

단어를 한 글자씩 가지로 뻗어 담는 나무로, 접두사가 같은 단어들이 그 부분을 함께 씁니다. cat·car·card를 담으면 글자 수는 10개지만 노드는 c·a·t·r·d 다섯 개뿐입니다. 그래서 «이 접두사로 시작하는 단어 모두 찾기»가 한 번 내려가는 것으로 끝납니다.

해시는 «정확히 같은 것»만 찾을 수 있기 때문입니다. «비슷하게 시작하는 것»을 찾으려면 전부 훑어야 하지만, 트라이는 접두사를 따라 내려가기만 하면 됩니다. 자동완성이 바로 이 질문이고, 찾는 비용도 담긴 단어 수와 무관하게 찾는 단어의 길이에만 달려 있습니다.

노드마다 자식 목록을 들고 있어야 해서 메모리가 많이 듭니다. 접두사가 거의 겹치지 않는 목록에서는 아끼는 것 없이 노드만 잔뜩 생겨 오히려 손해입니다. 트라이는 접두사가 겹치는 자료에서만 값을 합니다.

무엇을 찾고 싶은지에 따라 다릅니다. 음절로 담으면 «가방»과 «가족»이 «가»를 함께 쓰지만 «강»과 «가»는 서로 다른 글자라 아무것도 나누지 못합니다. 자모로 풀면 «강»이 ㄱ-ㅏ-ㅇ이라 «가»를 접두사로 가져 초성 검색이 자연스럽게 되지만, 나무가 깊어지고 노드가 늘어납니다.

노드를 새로 만들지 않고 지나가는 자리에 «여기서 끝나는 단어가 있다»고 표시만 합니다. 가·가방·가방끈을 담으면 노드는 가·방·끈 세 개이고 세 자리 모두 단어로 표시됩니다. 그래서 접두사 검색에서 자기 자신도 함께 걸립니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.