순위와 비용의 관계 유도

"최적화로 얻어진 거듭제곱 분포"라는 앞 글에서 이해되지 않았던 부분을 더 생각해보니 알겠더군요. 낱말이 많이 쓰이는 것부터 순서대로 나열하고 그 순위를 j라고 합니다. j번째 낱말을 이용하는 비용은 그 낱말의 길이, 즉 알파벳 개수에 비례한다고 가정합니다.

가장 쉬운 예로 a,b로만 이루어진 언어를 봅시다. 가능한 모든 낱말을 길이가 작은 것부터 나열합니다.

a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, ...

짧은 낱말일수록 많이 쓰인다는 가정이 더 필요하긴 하네요. 길이가 1인 낱말 중 순위의 최대값은 2(즉 'b')이고 길이가 2인 낱말 중 순위의 최대값은 6(=2+4)이며, 길이가 3인 것 중 순위의 최대값은 14(=2+4+8)입니다. 길이가 l이라고 하면 순위의 최대값은략 2^l+1이 됩니다. 길이가 곧 비용이라 했고, 길이가 짧을수록 순위가 높아진다고 전제했으므로, 대략 다음과 같은 관계가 생깁니다.

\(j\sim 2^{C_j}\to C_j\sim \log j\)

알파벳이 2개짜리 언어여서 로그의 밑은 2가 되겠죠. 일반적으로 알파벳이 d개라면 로그의 밑은 d입니다. 앞글의 논문에서는 d가 명시되어 있지만 제가 편의상 쓰지는 않았습니다.