重ね合わせたコード

書誌項目のデータが記載された、端に切り込みが入ったカード。端はまだ切り込みが入っていません。

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

限界パンチカードシステム

マージナルパンチカードシステムには、エッジノッチカード、スロットカード、EZソート、ザトカード、マクビー、マクビーキーソート、フレキシソート、ベロム、ロケットなど、様々な名称が用いられてきました。中には商標登録されているものもあります。各カードの中央には、関連情報（通常は近くの棚にある書籍、研究論文、または雑誌記事の名称と著者、そして主題とキーワードのリスト）が記載されていました。カードセットの中には、ユーザーが必要とするすべての情報がカード自体に手書き、タイプライター、またはマイクロフィルム（アパーチャーカード）で記載されているものもありました。1枚のカードにはすべて、同じセットのパンチ穴があらかじめ開けられていました。ユーザーは、カードホルダーまたはカードトレイを用いてカードセットの穴を揃え、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}}$

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

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

ザトコーディング

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

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

その他の重ね合わせたコード

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

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

参照

• 分離行列

参考文献

1. Robert V. Williams. 「パンチカード：簡単なチュートリアル」 . Computing Now 2002.
2. W. ロス・アシュビー. W. ロス・アシュビーの日記: ザトコーディング 1960年9月22日. p. 6208-6222
3. 「表紙について」大学・研究図書館ニュース、2008年4月。 [1] [2]
4. ユージン・ガーフィールド. 「重ね合わせ符号化の継続的な重要性」Journal of Information Science 8 (1984) 181.
5. ハーバート・マーヴィン・オールマン. 「主語-単語文字頻度とスーパーインポーズ符号化への応用」 . 国際科学情報会議議事録 (1959).
6. ボーン、チャールズ・P. (1963). 『情報処理の方法』John Wiley & Sons, Inc. p. 67.
7. Mooers, Calvin N. (1959年4月). 「大規模情報検索システムへの単純パターン包含選択の応用」 Zator社.
8. James Blustein、Amal El-Maazawi、 「ブルームフィルタ - チュートリアル、分析、概要」 p. 11。

外部リンク

• カルビン・N・ムーアズ「統計情報収集へのランダムコードの応用」マサチューセッツ工科大学数学部修士論文、1948年。
• カルビン・N・ムーアズ. 「知識の機械的組織化へのザトコーディングの応用」 . アメリカ情報科学技術学会誌. 2007年.