r19
| 1 | [[분류:명세]] |
|---|
r20
| 2 | [목차] |
|---|
r28
| 3 | == 목표 및 우선순위 == |
|---|
| 4 | 1. 작은 크기 |
|---|
| 5 | 1. 고유성 및 낮은 충돌가능성 |
|---|
| 6 | 1. 작업과 편집 단위의 구분성 |
|---|
| 7 | 1. 쉬운 타이핑 |
|---|
| 8 | |
|---|
r20
| 9 | == collision probability research == |
|---|
r18
| 10 | 유니코드 기준 현대 한글의 모든 완성형 글자는 총 [math(19 \times 21 \times 28 = 11,172)]자이며, [math(4)]개의 문자가 연달아 사용되므로 표본 공간의 크기는 |
|---|
r1
| 11 | |
|---|
r18
| 12 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(11,172^4 = 15,578,430,750,925,056 \approx 1.5578430751 \times 10^{16})]|| |
|---|
r1
| 13 | |
|---|
r8
| 14 | 입니다. 편의상 이를 [math(N)]이라고 하겠습니다. |
|---|
r3
| 15 | |
|---|
r9
| 16 | 하나의 작업에서 [math(x)]개의 식별자를 생성했을 때, 이중 '적어도 하나의 식별자 충돌이 발생할 확률'을 구하고자 합니다. 이 확률을 [math(p)]로 둡시다. 예를 들어 [math(p = 30\%)]라면 대략 [math(30\%)]의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다. |
|---|
r3
| 17 | |
|---|
r21
| 18 | 이어서 실제로 나무위키 모든 문서를 대상으로 하는 1회의 작업을 수행하였을 때, 동일 작업 내에서 식별자 충돌이 발생할 실제 확률 [math(p)]를 구하고자 합니다. 단순한 비교를 위해 테일러 전개로 적절한 하한을 찾아 근사하도록 합니다. 일단 자명하게 |
|---|
r9
| 19 | |
|---|
r10
| 20 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle p = 1 - \frac{_N\mathrm P_x}{N^x})]|| |
|---|
r4
| 21 | |
|---|
r22
| 22 | 이므로 우변의 [math(\frac{_N\mathrm P_x}{N^x})] 부분을 근사하는 어떤 함수 [math(f(x))]를 찾은 후 [math(1 - f(x))]를 구하면 [math(p)]의 근사값을 얻을 수 있습니다. 우선 [math(\frac{_N\mathrm P_x}{N^x})] 수식을 곱의 형태로 정리해 봅시다. |
|---|
r4
| 23 | |
|---|
r10
| 24 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle 1 - p = \prod^{x-1}_{k = 1} 1 - \frac kN)]|| |
|---|
r6
| 25 | |
|---|
r23
| 26 | 이어서 [math(\exp -\frac kN)]을 테일러 전개하고 선형 근사를 구하면 |
|---|
r6
| 27 | |
|---|
r23
| 28 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle \exp -\frac kN = \sum_{i = 0} \frac{\left(-\frac kN\right)^i}{i!} \approx 1 - \frac kN)]|| |
|---|
r6
| 29 | |
|---|
r8
| 30 | 이 근사를 적용해서 '어떤 함수' [math(f(x))]가 [math(1 - p)]를 근사하도록 조립해 봅시다. |
|---|
r7
| 31 | |
|---|
r24
| 32 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle f(x) = \exp -\frac{x(x-1)}{2N} = \exp \sum^{x - 1}_{k = 1} -\frac kN = \prod^{x - 1}_{k = 1} \exp -\frac kN \approx \prod^{x - 1}_{k = 1} 1 - \frac kN = 1 - p)]|| |
|---|
r7
| 33 | |
|---|
r25
| 34 | [[https://namu.wiki/w/나무위키:통계|나무위키:통계]]에 따르면 2025-05-08 20:04:05-0400 기준 나무위키의 모든 문서는 [math(7,149,087)]개 가량입니다. 앞서 구한 [math(f(x))]에 이 값을 집어넣으면 나무위키의 모든 문서를 대상으로 하는 작업을 수행했을 해당 작업 내에서 식별자 충돌이 발생할 확률 [math(p)]를 구할 수 있습니다. |
|---|
| 35 | |
|---|
| 36 | ||<tablealign=center><tablebordercolor=transparent><tablebgcolor=transparent>[math(\displaystyle\begin{aligned} |
|---|
| 37 | p &= 1 - f(7,149,087) \\ |
|---|
| 38 | &= 1 - \exp -\frac{7,149,087 \times 7,149,086}{2 \times 15,578,430,750,925,056} \\ |
|---|
| 39 | &= 1 - 0.9983609536 \\ |
|---|
| 40 | &= 0.0016390464 \\ |
|---|
| 41 | &\approx 0.1639\% \\ |
|---|
| 42 | \end{aligned})]|| |
|---|
r27
| 43 | |
|---|
| 44 | 이는 다시 말해 한 작업 내에서 나무위키의 모든 문서를 편집한다 하더라도, 식별자 충돌이 발생할 가능성이 [math(0.2\%)]보다 적다는 것을 의미합니다. 현실적으로 개별 작업이 한번에 다루는 문서 범위는 이보다 훨씬 좁으므로 충돌 가능성은 더욱 하락합니다. 일례로 2025-05-08 23:03:00-0400 기준 역링크가 [math(120,827)]개에 달하는 [[https://namu.wiki/w/틀:상세 내용|틀:상세 내용]] 등 고빈도 틀의 대규모 매개변수 작업 등을 진행한다 하여도 충돌 발생 가능성은 [math(0.0000468566\%)]에 지나지 않습니다. |
|---|
r26
| 45 | |
|---|