r18
| 1 | 유니코드 기준 현대 한글의 모든 완성형 글자는 총 [math(19 \times 21 \times 28 = 11,172)]자이며, [math(4)]개의 문자가 연달아 사용되므로 표본 공간의 크기는 |
|---|
r1
| 2 | |
|---|
r18
| 3 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(11,172^4 = 15,578,430,750,925,056 \approx 1.5578430751 \times 10^{16})]|| |
|---|
r1
| 4 | |
|---|
r8
| 5 | 입니다. 편의상 이를 [math(N)]이라고 하겠습니다. |
|---|
r3
| 6 | |
|---|
r9
| 7 | 하나의 작업에서 [math(x)]개의 식별자를 생성했을 때, 이중 '적어도 하나의 식별자 충돌이 발생할 확률'을 구하고자 합니다. 이 확률을 [math(p)]로 둡시다. 예를 들어 [math(p = 30\%)]라면 대략 [math(30\%)]의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다. |
|---|
r3
| 8 | |
|---|
r9
| 9 | 이어서 이 확률식을 역으로 계산하여 '식별자 충돌이 발생할 확률이 [math(p)] 이상이기 위해서는 적어도 [math(x)]개의 식별자를 생성해야 하는지'를 보이려고 합니다. namuid의 식별자 충돌이 거의 불가능함을 보이고 싶으므로 [math(p = 0.1\%)]로 두고 테일러 전개로 필요한 표본의 수 [math(x)]의 하한을 근사해 봅시다. 일단 자명하게 |
|---|
| 10 | |
|---|
r10
| 11 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle p = 1 - \frac{_N\mathrm P_x}{N^x})]|| |
|---|
r4
| 12 | |
|---|
r8
| 13 | 이므로 어떤 함수 [math(f(x))]에 대해 [math(f(x) \leq 1 - p)] 를 성립시키는 가장 큰 [math(x)]를 근사하면 됩니다. 우선 위에 쓴 [math(p)]를 구하는 수식을 곱의 형태로 정리해 봅시다. |
|---|
r4
| 14 | |
|---|
r10
| 15 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle 1 - p = \prod^{x-1}_{k = 1} 1 - \frac kN)]|| |
|---|
r6
| 16 | |
|---|
r8
| 17 | 이어서 [math(e^{-\frac kN})]을 테일러 전개하고 선형 근사를 구하면 |
|---|
r6
| 18 | |
|---|
r10
| 19 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle e^{-\frac kN} = \sum_{i = 0} \frac{\left(-\frac kN\right)^i}{i!} \approx 1 - \frac kN)]|| |
|---|
r6
| 20 | |
|---|
r8
| 21 | 이 근사를 적용해서 '어떤 함수' [math(f(x))]가 [math(1 - p)]를 근사하도록 조립해 봅시다. |
|---|
r7
| 22 | |
|---|
r10
| 23 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle f(x) = e^{-\frac{x(x-1)}{2N}} = \prod^{x - 1}_{k = 1} e^{-\frac kN} \approx \prod^{x - 1}_{k = 1} 1 - \frac kN = 1 - p)]|| |
|---|
r7
| 24 | |
|---|
r13
| 25 | 보기 편하게 로그 형태로 전개하면 다음과 같이 [math(x)]에 대한 이차방정식이 나옵니다. 편의상 [math(f(x))]를 [math(y)]라고 두었습니다. |
|---|
r11
| 26 | |
|---|
r13
| 27 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle x^2 - x + 2N \ln y= 0)]|| |
|---|
r11
| 28 | |
|---|
r12
| 29 | 방정식을 풀면 역함수를 구할 수 있겠군요. 시행 횟수 [math(x)]는 양의 정수임이 자명하니 음수근은 버리겠습니다. |
|---|
| 30 | |
|---|
r13
| 31 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle f^{-1}(y) = x = \frac12 + \sqrt{\frac14 - 2N \ln y})]|| |
|---|
r12
| 32 | |
|---|
r17
| 33 | 보다시피 이 함수 [math(f^{-1})]에 찾고자 하는 충돌 확률 [math(1 - p)]를 넣으면 이를 만족시키는 [math(x)]의 근사값을 구할 수 있습니다. 앞서 [math(p = 0.1\% = 10^{-3})]로 주었으므로 |
|---|
r14
| 34 | |
|---|
r15
| 35 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle\begin{aligned} |
|---|
| 36 | x &= \frac12 + \sqrt{\frac14 - 2N \ln 0.999} \\ |
|---|
r18
| 37 | &= 5,583,229.881461706 \\ |
|---|
| 38 | &\approx 5.5832298814617 \times 10^6 \\ |
|---|
r15
| 39 | \end{aligned})]|| |
|---|
r16
| 40 | |
|---|
r18
| 41 | 다시 말하면 한번에 5백만개 정도의 문서를 편집하는 경우 [math(0.1\%)] 정도의 충돌 가능성이 있을 수 있다는 소리입니다. |
|---|
r16
| 42 | |
|---|
| 43 | 반면에 [[https://namu.wiki/w/나무위키:통계|나무위키:통계]]에 따르면 2025-05-08 20:04:05-0400 기준 나무위키의 모든 문서는 [math(7,149,087)]개에 불과합니다. |
|---|