Código superpuesto

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

Muchos nombres, algunos de ellos registrados, se han utilizado para los sistemas de tarjetas perforadas marginales: tarjetas con muescas en el borde, tarjetas con ranuras, EZ Sort, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket, etc. El centro de cada tarjeta contenía la información relevante, generalmente 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 de apertura ). Cada tarjeta en una pila tenía el mismo conjunto de agujeros preperforados. El usuario encontraría las tarjetas particulares relevantes para una búsqueda alineando los agujeros en el juego de tarjetas (usando un soporte de tarjetas o una bandeja de tarjetas), insertando una o más varillas similares a agujas de tejer a lo largo de toda la pila, de modo que las tarjetas deseadas (que habían sido muescadas o cortadas) cayeran de las tarjetas irrelevantes en la colección (que se dejaron sin muescas), que permanecieron en la(s) aguja(s). Un usuario podría repetir esta selección muchas veces para formar una consulta de búsqueda booleana compleja . Una tarjeta que fuera relevante para 2 o más sujetos tendría los espacios para cada uno de esos sujetos recortados, de modo que esa tarjeta se eliminaría cuando se seleccionara uno u otro o ambos sujetos. Los sistemas de codificación de "código superpuesto", como Zatocoding, ahorraban espacio al ingresar varios o todos los sujetos en el mismo campo; un "código superpuesto" de este tipo almacena mucha más información en menos espacio, pero al costo 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 agujeros R cerca de la parte superior de cada ficha y, para cada tema realmente discutido en un libro en particular, cortar una ranura en el 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 códigos 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 formó la Compañía 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]

La configuración de un código superpuesto para una biblioteca en particular se realiza de la siguiente manera:

• Al recorrer cada tarjeta del índice, se crea una lista de todos los temas R utilizados en esta biblioteca en particular y se anota la cantidad máxima de temas r realmente escritos en una sola tarjeta. (Por ejemplo, digamos que tenemos 8000 temas y el bibliotecario decide indexar solo los r=4 temas principales por libro).
• El bibliotecario observa la tarjeta física con el borde entallado y anota la cantidad de agujeros N en cada tarjeta. (Si N >= R, entonces podríamos usar la "forma obvia" mencionada anteriormente; el objetivo de la codificación Zato es que funcione incluso cuando N es mucho menor que R).
• El bibliotecario elige una cantidad n de espacios por asignatura, normalmente ^[2]${\displaystyle n=N(1-2^{-{\frac {1}{r}}})}$
• En la lista de todos los sujetos R, para cada sujeto, escriba qué huecos se colocarán para ese sujeto. En lugar de colocar un hueco por sujeto de la "manera obvia", un código superpuesto colocará n huecos por sujeto. (Existen varias maneras de elegir estos patrones, que distinguen entre los diversos códigos superpuestos; los analizamos a continuación).
• Cuando llegue un libro nuevo, haz una nueva tarjeta para él:
  • Consigue una tarjeta en blanco con los N agujeros estándar y escribe el nombre del libro, etc. en el medio.
  • Anota en la tarjeta los temas que trata el libro.
  • Para cada uno de los r temas principales, busque ese tema en la lista grande y vea qué n espacios debe cortar para ese tema, y ​​elimínelos.
  • Cuando la tarjeta esté terminada, es posible que tenga hasta r*n ranuras cortadas, pero lo más probable es que al menos algunos de los patrones de ranuras en cuestión se superpongan, lo que da 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 temas R, encontramos el patrón de ranuras correspondiente de n ranuras y colocamos n agujas a través de toda la pila en ese patrón. Todas las cartas que han sido cortadas con ese patrón se caerán. Es posible que también caigan algunas otras cartas no deseadas: cartas 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 carta no deseada con v ranuras cortadas caiga cuando seleccionamos algún patrón de n agujas es aproximadamente . La mayoría de los sistemas tienen un N lo suficientemente grande y r lo suficientemente pequeño como para que, v < N/2 (es decir, la carta está perforada menos de la mitad), por lo que la probabilidad de que caiga una carta no deseada es menor que . ^[2]${\displaystyle F=\left({\frac {v}{N}}\right)^{n}}$${\displaystyle F<\left({\frac {1}{2}}\right)^{n}}$

Hay varias formas diferentes de elegir qué agujeros se realizarán para cada tema.

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

La configuración de un Zatocode para una lista particular de sujetos R se realiza de la siguiente manera: ^[2]

• Para el primer tema, elija n de las N ranuras al azar.
• Para el segundo tema, elija n de los N espacios al azar, pero asegúrese de que este patrón no sea idéntico al del primer tema.
• ...
• Para el sujeto R'ésimo, elija n de los N espacios al azar, pero asegúrese de que no sea idéntico a ningún sujeto anterior.

Un Zatocode requiere un libro de códigos que enumere todos los temas y un código de notch generado aleatoriamente asociado con cada uno. Otros códigos superpuestos "directos" tienen una función hash fija para transformar las letras de (una ortografía de) un tema en un código de notch. Tales códigos requieren un libro de códigos mucho más corto que describa la traducción de las letras de una palabra al código de notch correspondiente y, en principio, pueden agregar fácilmente nuevos temas sin cambiar el libro de códigos. ^[5]

Un filtro Bloom puede considerarse un tipo de código superpuesto. ^[8]

• 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 Americana de Ciencias de la Información y Tecnología. 2007.