더시드위키
최근 변경최근 토론
특수 기능

namuid(r26 판)

보기RAWBlame되돌리기비교
[주의!] 문서의 이전 버전(에 수정)을 보고 있습니다. 최신 버전으로 이동
분류
1. collision probability research

1. collision probability research[편집]

유니코드 기준 현대 한글의 모든 완성형 글자는 총 19×21×28=11,17219 \times 21 \times 28 = 11,172자이며, 44개의 문자가 연달아 사용되므로 표본 공간의 크기는
11,1724=15,578,430,750,925,056≈1.5578430751×101611,172^4 = 15,578,430,750,925,056 \approx 1.5578430751 \times 10^{16}

입니다. 편의상 이를 NN이라고 하겠습니다.

하나의 작업에서 xx개의 식별자를 생성했을 때, 이중 '적어도 하나의 식별자 충돌이 발생할 확률'을 구하고자 합니다. 이 확률을 pp로 둡시다. 예를 들어 p=30%p = 30\%라면 대략 30%30\%의 확률로 충돌이 발생할 가능성이 있다는 뜻입니다.

이어서 실제로 나무위키 모든 문서를 대상으로 하는 1회의 작업을 수행하였을 때, 동일 작업 내에서 식별자 충돌이 발생할 실제 확률 pp를 구하고자 합니다. 단순한 비교를 위해 테일러 전개로 적절한 하한을 찾아 근사하도록 합니다. 일단 자명하게
p=1−NPxNx\displaystyle p = 1 - \frac{_N\mathrm P_x}{N^x}

이므로 우변의 NPxNx\frac{_N\mathrm P_x}{N^x} 부분을 근사하는 어떤 함수 f(x)f(x)를 찾은 후 1−f(x)1 - f(x)를 구하면 pp의 근사값을 얻을 수 있습니다. 우선 NPxNx\frac{_N\mathrm P_x}{N^x} 수식을 곱의 형태로 정리해 봅시다.
1−p=∏k=1x−11−kN\displaystyle 1 - p = \prod^{x-1}_{k = 1} 1 - \frac kN

이어서 exp⁡−kN\exp -\frac kN을 테일러 전개하고 선형 근사를 구하면
exp⁡−kN=∑i=0(−kN)ii!≈1−kN\displaystyle \exp -\frac kN = \sum_{i = 0} \frac{\left(-\frac kN\right)^i}{i!} \approx 1 - \frac kN

이 근사를 적용해서 '어떤 함수' f(x)f(x)가 1−p1 - p를 근사하도록 조립해 봅시다.
f(x)=exp⁡−x(x−1)2N=exp⁡∑k=1x−1−kN=∏k=1x−1exp⁡−kN≈∏k=1x−11−kN=1−p\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

나무위키:통계에 따르면 2025-05-08 20:04:05-0400 기준 나무위키의 모든 문서는 7,149,0877,149,087개 가량입니다. 앞서 구한 f(x)f(x)에 이 값을 집어넣으면 나무위키의 모든 문서를 대상으로 하는 작업을 수행했을 해당 작업 내에서 식별자 충돌이 발생할 확률 pp를 구할 수 있습니다.
p=1−f(7,149,087)=1−exp⁡−7,149,087×7,149,0862×15,578,430,750,925,056=1−0.9983609536=0.0016390464≈0.1639%\displaystyle\begin{aligned} p &= 1 - f(7,149,087) \\ &= 1 - \exp -\frac{7,149,087 \times 7,149,086}{2 \times 15,578,430,750,925,056} \\ &= 1 - 0.9983609536 \\ &= 0.0016390464 \\ &\approx 0.1639\% \\ \end{aligned}