Código superpuesto

Un código superpuesto como el Zatocoding es un tipo de código hash que fue popular en sistemas marginales de tarjetas perforadas .

Se han utilizado muchos nombres, algunos de ellos marcas registradas, para los sistemas de tarjetas perforadas marginales: tarjetas con muescas en el borde, tarjetas ranuradas, EZ Sort, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket, etc. El centro de cada tarjeta contenía la información relevante, normalmente el nombre y el autor de un libro, un artículo de investigación o un artículo de revista en un estante cercano; y una lista de temas y palabras clave. Algunos juegos de tarjetas contenían toda la información requerida por el usuario en la propia tarjeta, escrita a mano, mecanografiada o en microfilm ( tarjeta perforada ). Cada tarjeta de una pila tenía el mismo conjunto de agujeros preperforados. El usuario encontraba las tarjetas relevantes para una búsqueda alineando los agujeros en el juego de tarjetas (usando un soporte o bandeja para tarjetas), insertando una o más varillas similares a agujas de tejer a través de la pila, de modo que las tarjetas deseadas (que habían sido muescadas o cortadas) caían de las tarjetas irrelevantes de la colección (que quedaron sin muescar), las cuales permanecían en las agujas. Un usuario podía repetir esta selección muchas veces para formar una consulta de búsqueda booleana compleja . Una tarjeta que fuera relevante para dos o más sujetos tendría la(s) ranura(s) correspondiente(s) a cada uno de esos sujetos recortada(s), de modo que esa tarjeta se eliminaría cuando se seleccionara uno, el otro o ambos sujetos. Los sistemas de codificación de "código superpuesto", como Zatocoding, ahorraban espacio al introducir varios o todos los sujetos en el mismo campo; dicho "código superpuesto" almacena mucha más información en menos espacio, pero a costa de selecciones "falsas" ocasionales. ^{[ 1 ]}

Una vez que se tiene una colección de fichas, una por libro, artículo de investigación o artículo de revista en una biblioteca, con una lista de palabras clave (temas) discutidos en un libro en particular escrita en la ficha de ese libro, la "forma obvia" de codificar esos temas es contar el número total de temas utilizados en toda la colección R, hacer una fila de R agujeros cerca de la parte superior de cada ficha y, para cada tema realmente discutido en un libro en particular, cortar una ranura del agujero correspondiente a ese tema en la ficha correspondiente a ese libro. ^{[ 2 ]} Naturalmente, esto también requiere una lista separada de cada tema utilizado en la colección que indique qué agujero se perfora para cada tema. Desafortunadamente, puede haber miles de temas distintos en la colección, y es poco práctico perforar miles de agujeros en cada ficha. Si bien puede parecer imposible usar menos de 1 agujero por tema, los sistemas de codificación superpuestos pueden resolver este problema.

El sistema de recuperación de información Zatocoding fue desarrollado por Calvin Mooers en 1947. ^{[ 3 ]}

Calvin Mooers inventó Zatocoding en el MIT, un sistema mecánico de recuperación de información basado en códigos superpuestos, y fundó la empresa Zator en 1947 para comercializar sus aplicaciones. ^{[ 4 ]} El código superpuesto particular utilizado en ese sistema se llama Zatocoding , mientras que el sistema de recuperación de información de tarjetas perforadas marginales en su conjunto se llama " Zator ". ^{[ 5 ]}

Configurar un código superpuesto para una biblioteca en particular se hace de la siguiente manera:

• Al revisar cada ficha del índice, se crea una lista de todas las R materias utilizadas en esta biblioteca en particular, y se anota el número máximo de materias r que aparecen en una sola ficha. (Por ejemplo, supongamos que tenemos 8000 materias y el bibliotecario decide indexar solo las r=4 materias principales por libro).
• El bibliotecario observa la tarjeta física con muescas en el borde y anota el número de agujeros N en cada tarjeta. (Si N >= R, podríamos usar el método "obvio" mencionado anteriormente; la clave de Zatocoding es que funciona incluso cuando N es mucho menor que R).
• El bibliotecario elige un número n de espacios por materia, normalmente${\displaystyle n=N(1-2^{-{\frac {1}{r}}})}$^{[ 2 ]}
• En la lista de todos los sujetos R, anote para cada sujeto qué agujeros se rellenarán. En lugar de rellenar un agujero por sujeto de la forma habitual, un código superpuesto rellenará n agujeros por sujeto. (Existen varias maneras de seleccionar estos patrones; estas distinguen los distintos códigos superpuestos, que se describen más adelante).
• Cuando llegue un libro nuevo, hazle una nueva ficha:
  • Consigue una tarjeta en blanco con los agujeros estándar en forma de N y escribe el nombre del libro, etc., en el centro.
  • Anota en la ficha los temas que trata el libro.
  • Para cada una de las r materias principales, busque esa materia en la lista grande y vea qué n espacios recortar para esa materia, y recórtelos.
  • Cuando la tarjeta esté terminada, puede tener hasta r*n ranuras cortadas, pero lo más probable es que al menos algunos de los patrones de ranuras del sujeto se superpongan, dando como resultado solo v < r*n ranuras.

Más tarde, cuando necesitamos encontrar libros sobre algún tema en particular, buscamos ese tema en nuestra lista de todos los R temas, encontramos el patrón de ranuras correspondiente de n ranuras y colocamos n agujas a través de toda la pila siguiendo ese patrón. Todas las tarjetas que se hayan cortado con ese patrón caerán. Es posible que también caigan algunas otras tarjetas no deseadas: tarjetas que tienen varios temas cuyos patrones de agujeros se superponen de tal manera que imitan el patrón deseado. La probabilidad F de que alguna tarjeta no deseada con v ranuras cortadas caiga cuando seleccionamos algún patrón de n agujas es aproximadamente${\displaystyle F=\left({\frac {v}{N}}\right)^{n}}$La mayoría de los sistemas tienen un N suficientemente grande y un r suficientemente pequeño como para que v < N/2 (es decir, la tarjeta está perforada menos de la mitad), de modo que la probabilidad de que una tarjeta no deseada caiga es menor que ${\displaystyle F<\left({\frac {1}{2}}\right)^{n}}$. ^{[ 2 ]}

Existen varias formas diferentes de elegir qué agujeros se ranurarán para cada sujeto.

(Se desarrollaron varias variaciones de Zatocoding. Bourne describe una variante "para sistemas de recuperación más recientes que requieren un alto rendimiento del sistema de codificación superpuesto", ^{[ 6 ]} utilizando un enfoque que Mooers publicó en 1959. ^{[ 7 ]} )

• Matriz disjunta

• Calvin N. Mooers. "Aplicación de códigos aleatorios a la recopilación de información estadística" . Tesis (MS). Instituto Tecnológico de Massachusetts. Departamento de Matemáticas, 1948.
• Calvin N. Mooers. "Zatocoding aplicado a la organización mecánica del conocimiento" . Revista de la Sociedad Estadounidense de Ciencia y Tecnología de la Información. 2007.