重ね合わせたコード

Zatocodingなどの重ね合わせコードは、限界パンチカード システムで人気があったハッシュ コードの一種です。

マージナル パンチ カード システムには、エッジ ノッチ カード、スロット カード、EZ Sort、Zatocards、McBee、McBee Keysort、Flexisort、Velom、Rocket など、多くの名前が使用されており、その一部は商標登録されています。各カードの中央には、関連情報 (近くの棚にある書籍、研究論文、または雑誌記事の名前と著者、および主題とキーワードのリスト) が記載されています。カード セットによっては、ユーザーが必要とするすべての情報がカード自体に記載されていたり、手書き、タイプ入力、またはマイクロフィルム (アパーチャ カード) に記載されていたりします。積み重ねられたカードには、すべて同じセットのパンチ穴が開いています。ユーザーは、カード セットの穴を揃えて (カード ホルダーまたはカード トレイを使用)、1 つまたは複数の編み針のような棒をスタック全体に挿入して、目的のカード (切り込みが入った、または切り開かれた) がコレクション内の無関係なカード (切り込みが入っていない) から落ち、針に残っているカードを探すことで、検索に関連する特定のカードを見つけます。ユーザーはこの選択を何度も繰り返して、複雑なブール検索クエリを作成できます。2 つ以上の主題に関連するカードは、それらの主題のスロットが切り取られているため、どちらか一方または両方の主題が選択されると、そのカードがドロップされます。Zatocoding などの「重ね合わせコード」コーディング システムは、複数の主題またはすべての主題を同じフィールドに入力することでスペースを節約します。このような「重ね合わせコード」は、より少ないスペースに多くの情報を保存しますが、時々「誤った」選択が発生するという代償を伴います。^[1]

図書館に、本、研究論文、または雑誌記事ごとに 1 枚の索引カードのコレクションがあり、その本のカードに特定の本で説明されているキーワード (主題) のリストが記載されている場合、それらの主題をコード化する「明白な方法」は、コレクション R 全体で使用されている主題の総数を数え、各カードの上部近くに R の穴の列を作り、特定の本で実際に説明されている各主題について、その本に対応するカードのその主題に対応する穴からスロットを切り取ることです。 ^[2] 当然、これには、コレクションで使用されているすべての主題の個別のリストも必要であり、各主題に対してどの穴が開けられているかを示します。残念ながら、コレクションには何千もの異なる主題がある可能性があり、すべてのカードに何千もの穴を開けることは現実的ではありません。主題ごとに 1 つ未満の穴を使用することは不可能に思えるかもしれませんが、重ね合わせたコード システムでこの問題を解決できます。

情報検索のためのザトコーディングシステムは、1947年にカルビン・ムーアズによって開発されました。 ^[3]

カルビン・ムーアズはMITで、重ね合わせたコードに基づく機械的な情報検索システムであるザトコーディングを発明し、その応用を商業化するために1947年にザトール社を設立した。^[4] このシステムで使用されている特定の重ね合わせコードはザトコーディングと呼ばれ、マージナルパンチカード情報検索システム全体は「ザトール」と呼ばれている。^[5]

特定のライブラリのスーパーインポーズ コードを設定する手順は次のようになります。

• 索引のすべてのカードを調べて、この特定のライブラリで使用されるすべての R 主題のリストを作成し、1 枚のカードに実際に書き込まれる主題 r の最大数を記録します。(たとえば、主題が 8000 あり、司書が書籍ごとに上位 r=4 主題のみを索引付けすることにしたとします)。
• 司書は、物理的な端に切り込みの入ったカードを見て、各カードの穴の数 N を記録します。(N >= R の場合は、上記の「明白な方法」を使用できます。Zatocoding の重要な点は、N が R よりはるかに小さい場合でも機能することです。)
• 司書は、主題ごとにn個のスロットを選択する。通常は^[2]${\displaystyle n=N(1-2^{-{\frac {1}{r}}})}$
• すべての R サブジェクトのリストで、各サブジェクトについて、そのサブジェクトにどのホールを配置するかを書き留めます。「明白な方法」でサブジェクトごとに 1 つのホールを配置するのではなく、重ね合わせたコードによってサブジェクトごとに n 個のホールを配置します。(これらのパターンを選択する方法はいくつかあります。これらは、さまざまな重ね合わせたコードを区別します。以下で説明します)。
• 新しい本が届いたら、新しいカードを作ります。
  • 標準の N 個の穴がある空白のカードを用意し、中央に本のタイトルなどを書き込みます。
  • その本で扱われている主題をカードに書きなさい。
  • 上位 r 科目ごとに、大きなリストでその科目を検索し、その科目に対してどの n スロットを削減するかを確認して、削減します。
  • カードが完成すると、最大 r*n 個のスロットが切り込まれている可能性がありますが、対象のスロット パターンの少なくとも一部が重なり合って、v < r*n 個のスロットのみになる可能性が高くなります。

後で、ある特定の主題の本を探す必要があるときは、R 個の主題すべてのリストからその主題を検索し、対応する n 個のスロットのスロット パターンを見つけ、そのパターンでスタック全体に n 本の針を通します。そのパターンで切り抜かれたカードはすべて落ちます。他の不要なカードもいくつか落ちる可能性があります。つまり、穴のパターンが重なり合って、目的のパターンを模倣する複数の主題を持つカードです。n 本の針のパターンを選択したときに、v 個のスロットが切り抜かれた不要なカードが落ちる確率 F は、およそ です。ほとんどのシステムでは、N が十分に大きく r が十分に小さいため、v < N/2 (つまり、カードが半分未満しか穴が開けられていない) となり、不要なカードが落ちる確率は 未満になります 。^[2]${\displaystyle F=\left({\frac {v}{N}}\right)^{n}}$${\displaystyle F<\left({\frac {1}{2}}\right)^{n}}$

各科目にどの穴を配置するかを選択するには、いくつかの方法があります。

（ザトコーディングにはいくつかのバリエーションが開発されました。ボーンは、ムーアズが1959年に発表したアプローチを使用して、「スーパーインポーズされたコーディングシステムの高性能を必要とする新しい検索システム用」のバリエーションについて説明しています。 ^{[6] [7]}）

特定のR対象リストに対してZatocodeを設定する手順は次のようになります。^[2]

• 最初の被験者については、N 個のスロットのうち n 個をランダムに選択します。
• 2 番目の被験者については、N 個のスロットのうち n 個をランダムに選択しますが、このパターンが最初の被験者と同じにならないようにしてください。
• ...
• R 番目の被験者については、N 個のスロットのうち n 個をランダムに選択しますが、以前の被験者と同一にならないようにしてください。

Zatocode には、すべての主題と、それぞれに関連付けられたランダムに生成されたノッチ コードが記載されたコード ブックが必要です。その他の「直接」重ね合わせコードには、主題 (の 1 つのスペル) の文字をノッチ コードに変換するための固定ハッシュ関数があります。このようなコードでは、単語の文字を対応するノッチ コードに変換する方法を記述した、はるかに短いコード ブックが必要であり、原理的にはコード ブックを変更せずに新しい主題を簡単に追加できます。^[5]

ブルームフィルタは一種の重ね合わせコードと考えることができる。^[8]

• Calvin N. Mooers. 「統計情報の収集へのランダム コードの応用」。論文 (修士論文) マサチューセッツ工科大学、数学部、1948 年。
• Calvin N. Mooers. 「知識の機械的組織化に応用された Zatocoding」。アメリカ情報科学技術学会誌。2007 年。