중첩코드

Zatocoding과 같은 중첩 코드는 한계 펀치 카드 시스템에서 유행했던 해시 코드의 일종이다.

한계 펀치 카드 시스템

그 중 일부는 상표인 많은 이름들이 한계 펀치 카드 시스템에 사용되어왔다: 엣지 노치 카드, 슬롯 카드, E-Z 정렬, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket 등.각 카드의 중심에는 관련 정보(일반적으로 인근 선반에 있는 책, 연구 논문 또는 저널 기사의 이름과 작성자, 주제 및 키워드 목록)가 보관되어 있었다.일부 카드 세트에는 사용자가 요구하는 모든 정보가 카드 자체에, 손으로 직접, 타이프로 작성된, 또는 마이크로필름(사서 카드)에 담겨 있었다.스택에 있는 모든 카드에는 미리 뚫은 구멍이 같은 세트가 있었다.사용자는 카드 세트(카드 홀더 또는 카드 트레이 사용)의 구멍을 정렬하고, 한 개 이상의 뜨개질 니들 같은 봉을 스택 전체에 삽입하여 원하는 카드(노치되거나 잘려진 카드)가 컬렉션의 관련 카드에서 빠지도록 함으로써 검색과 관련된 특정 카드를 찾을 수 있다.바늘에 남아 있는사용자는 이 선택을 여러 번 반복하여 복잡한 부울 검색 쿼리를 구성할 수 있다.2개 이상의 과목과 관련이 있는 카드는 각 과목의 슬롯을 잘라내서 한 과목 또는 다른 과목 또는 두 과목 모두 선택했을 때 카드가 탈락될 것이다.Zatocoding과 같은 "중복된 코드" 코드 시스템은 동일한 분야의 여러 과목 또는 모든 과목을 입력함으로써 공간을 절약했다; 그러한 "중복된 코드"는 더 적은 공간에 더 많은 정보를 저장하지만 때때로 "거짓" 선택 비용을 지불한다.^[1]

도서관에서 한 권당 한 권, 연구 논문 또는 저널 기사의 색인 카드 컬렉션을 가지고 있으면, 그 책의 카드에 쓰여진 특정 책에서 논의된 키워드(주제목록) 목록을 가지고, 그러한 과목들을 코딩하는 "확실한 방법"은 전체 컬렉션 R에 사용된 총 과목 수를 세고, 그 근처에 R홀을 만드는 것이다.모든 카드의 맨 위, 그리고 특정 책에서 실제로 논의된 각 주제에 대해, 그 책에 해당하는 카드의 제목에 해당하는 구멍에서 슬롯을 자른다.^[2] 당연히, 이것은 또한 각 피사체에 대해 어떤 구멍이 뚫렸는지를 나타내는 수집에 사용된 모든 피사체의 별도 리스트를 필요로 한다.불행히도 컬렉션에는 수천 개의 뚜렷한 주제가 있을 수 있으며, 모든 카드에 수천 개의 구멍을 뚫는 것은 비현실적이다.피사체당 1개 미만의 홀을 사용하는 것은 불가능해 보이지만, 중첩된 코드 시스템은 이 문제를 해결할 수 있다.

중첩코드

정보 검색의 자토코딩 시스템은 캘빈 무어스에 의해 1947년에 개발되었다.^[3]

캘빈 무어스는 중첩된 코드를 바탕으로 한 기계 정보 검색 시스템인 M.I.T에서 자토코딩을 발명하고 1947년 자토커 컴퍼니를 결성해 응용 프로그램을 상용화했다.^[4]그 시스템에 사용된 특정한 중첩 코드는 자토코딩이라고 불리는 반면, 한계출발 카드 정보검색 시스템은 전체적으로 자토코딩이라고 불린다.^[5]

특정 라이브러리에 대해 중첩된 코드를 설정하는 것은 다음과 같다.

• 지수의 모든 카드를 거치면, 이 특정 도서관에서 사용되는 모든 R 과목의 목록이 작성되고, 하나의 카드에 실제로 쓰여진 과목의 최대 수가 기록된다.(예를 들어, 우리는 8000과목의 과목이 있고, 사서는 책당 상위 r=4과목만 색인화하기로 결정한다.)
• 사서는 물리 엣지 노트 카드를 보고, 각 카드에 N개의 구멍 수를 메모한다.(N >= R이라면, 위에서 언급한 "확실한 방법"을 사용할 수 있을 것이다—Zatocoding의 요점은 N이 R보다 훨씬 작을 때에도 작동한다는 것이다.
• 사서는 과목당 몇 개의 슬롯 수를 선택한다. $일반적$으로 n${\displaystyle }$= N${\displaystyle (1}$- ${\displaystyle {\mathrm{}}^{}}$- ${\displaystyle {1\frac{\mathrm{}}{}}^{}}$ ${\displaystyle {\frac{r}{}}^{}}$) ${\displaystyle n=N(1-2^{-{\frac{1}{r}}}$
• 모든 R 과목 리스트에는 각 과목에 대해 해당 과목에 대해 어떤 구멍이 뚫릴지 적는다."명확한 방법"에서 피사체당 하나의 구멍을 뚫는 것보다, 중첩된 코드는 피사체당 하나의 구멍을 뚫을 것이다.(이러한 패턴을 고르는 방법에는 여러 가지가 있다. 그 방법들은 여러 가지 중첩된 코드들을 구별한다. 우리는 아래에서 그것들을 논의한다.)
• 새 책이 들어오면, 새로운 카드를 만들어라:
  • 표준 N홀이 들어간 빈 카드를 받아 가운데에 책 이름 등을 적는다.
  • 카드에 책에서 다룬 주제를 적어라.
  • 상위 r 과목 각각에 대해 큰 리스트에서 해당 과목을 찾아 해당 과목에 대해 어떤 n개의 슬롯을 잘라낼지 확인한 후 잘라내십시오.
  • 카드가 완성되면, 최대 r*n 슬롯까지 절단할 수 있지만, 최소한 일부 주제 슬롯 패턴이 겹쳐서 v < r*n 슬롯만 생성될 가능성이 더 높다.

나중에 우리가 어떤 특정한 주제에 관한 책을 찾아야 할 때, 우리는 모든 R 과목 리스트에서 그 과목을 찾아보고, n개의 슬롯에 해당하는 슬롯 패턴을 찾아내고, n개의 바늘을 그 패턴의 전체 스택에 넣는다.그런 패턴으로 잘린 카드는 다 빠진다.원하는 패턴을 모방할 수 있도록 홀 패턴이 겹치는 여러 피사체를 가진 카드들, 즉 원하지 않는 몇 개의 다른 카드들도 빠질 수 있다.n 바늘 패턴을 선택할 때 v 슬롯이 잘려진 일부 원치 않는 카드의 확률 F는 $대략{\displaystyle }$F =${\displaystyle {}^{}}$( (${\displaystyle {\frac{v}{}}^{}}$ N${\displaystyle {}^{}}$)${\displaystyle {}^{}}$ ${\$ {v$}{N}}\right$)이다$.$$^{n$ 대부분의 시스템은 충분히 크고, 충분히 작아서 v < N/2 (즉, 카드가 반쯤 튀어 나온 상태)가 되기 때문에 원하지 않는 카드가 통과될 은F < ( ){\$displaystyle$ F$<\f$>\좌$({\frac{1}{2}}\우$)보다 작다$.$$^{n}}$^[2].

각 과목별로 어떤 구멍을 뚫을지 선택하는 방법에는 여러 가지가 있다.

(자토코딩의 여러 가지 변형이 개발되었다.본은 1959년에 발표된 접근법 무어스를 사용하여 "중첩된 코딩 시스템의 고성능이 필요한 새로운 검색 시스템을 위한"^[6] 변형을 설명한다.^[7]

자토코딩

R 과목의 특정 목록에 대해 Zatocode를 설정하는 것은 다음과 같다.^[2]

• 첫 번째 피사체의 경우 N 슬롯 중 임의로 n개를 선택한다.
• 두 번째 피사체의 경우 N 슬롯 중 n개를 랜덤하게 선택하되, 이 패턴이 첫 번째 피사체와 동일하지 않은지 확인하십시오.
• ...
• R'번째 제목의 경우 N 슬롯 중 n개를 랜덤하게 선택하되, 이전 제목과 동일하지 않은지 확인하십시오.

기타 중첩 코드

Zatocode는 모든 주제와 각 주제와 연관된 임의로 생성된 노치 코드를 나열하는 코드 북을 필요로 한다.다른 "직접" 중첩 코드는 피사체의 문자를 노치 코드로 변환하기 위한 고정 해시 함수를 가지고 있다.이러한 코드는 해당 노치코드에 한 단어로 된 글자의 번역을 기술하는 훨씬 짧은 코드북이 필요하며, 원칙적으로 코드북을 변경하지 않고도 새로운 과목을 쉽게 추가할 수 있다.^[5]

블룸 필터는 일종의 중첩된 코드로 간주될 수 있다.^[8]

참조

외부 링크

• 캘빈 N.무어."통계정보 수집에 임의 코드 적용"논문 (M.S.) 매사추세츠 공과대학교1948년 수학학부.
• 캘빈 N.무어."지식의 기계적 구성에 자토코딩을 적용했다."미국정보과학기술학회지.2007.