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

namuid(r33 판)

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

1. 목표 및 우선순위[편집]

  1. 작은 크기
  2. 고유성 및 낮은 충돌가능성
  3. 작업과 편집 단위의 구분성
  4. 정렬성
  5. 쉬운 타이핑

theseed의 편집 요약 최대 길이는 255글자이므로, 이 크기를 초과하는 모든 명세는 무의미합니다. 특히 토론 주소 등 삽입을 위해 여백의 공간을 많이 남겨둘 필요가 있고, 무엇보다 식별자가 너무 길면 일반 사용자들의 문서 역사 조회에 방해를 줄 수 있기 때문에 크기는 유의미한 충돌가능성을 유지하는 한 최대한 작아야만 합니다.

또한 나무위키 봇의 특성상 개별 task와 edit을 구분해야 명확한 전달이 가능하므로, 이를 편집자들도 쉽고 직관적으로, 봇 또한 절차적으로 쉽게 구분할 수 있는 구성을 택했습니다.

시간 정보를 넣고, 내부적으로 개별 task들을 시간순으로 정렬할 수 있도록, lexicographically sortable하도록 설계했습니다.

마지막으로, 한국인 이용자가 대다수를 차지하는 한국어 위키인 나무위키의 상황에 맞게, 대부분의 이용자들이 한글을 읽고 쓸 수 있고 환경에 따라 적절한 IME를 가지고 있으리라는 가정 하에, 유니코드의 모든 특수 문자 범위를 전부 사용하는 것이 아닌 한글 평면만 사용해, 복사 붙혀넣기가 힘든 유사시 이용자들이 스스로의 입력기를 사용해 보이는 대로 타이핑할 수 있도록 설계하였습니다.

2. 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}

이는 다시 말해 한 작업 내에서 나무위키의 모든 문서를 편집한다 하더라도, 식별자 충돌이 발생할 가능성이 0.2%0.2\%보다 적다는 것을 의미합니다. 현실적으로 개별 작업이 한번에 다루는 문서 범위는 이보다 훨씬 좁으므로 충돌 가능성은 더욱 하락합니다. 일례로 2025-05-08 23:03:00-0400 기준 역링크가 120,827120,827개에 달하는 틀:상세 내용 등 고빈도 틀의 대규모 매개변수 작업 등을 진행한다 하여도 충돌 발생 가능성은 0.0000468566%0.0000468566\%에 지나지 않습니다.