Un código superpuesto como Zatocoding es un tipo de código hash que era popular en los sistemas marginales de tarjetas perforadas .
Sistemas de tarjetas perforadas marginales
Se han utilizado muchos nombres, algunos de ellos de marca registrada, para sistemas marginales de tarjetas perforadas: tarjetas con muescas en los bordes, tarjetas ranuradas, EZ Sort, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket, etc. la información relevante, generalmente el nombre y el autor de un libro, trabajo de investigación o 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, manuscrita, mecanografiada o en microfilm ( tarjeta de apertura ). Todas las cartas de una pila tenían el mismo conjunto de agujeros preperforados. El usuario encontraría las tarjetas en particular relevantes para una búsqueda alineando los orificios en el juego de tarjetas (usando un portatarjetas o bandeja para tarjetas), insertando una o más varillas con forma de aguja de tejer a lo largo de la pila, de modo que el deseado las tarjetas (que tenían muescas o se abrieron) se cayeron de las tarjetas irrelevantes de la colección (sin muescas), que permanecen 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 la (s) ranura (s) para cada uno de esos sujetos cortadas, de modo que la tarjeta se saliera cuando se seleccionara uno, el otro o ambos sujetos. Los sistemas de codificación de "código superpuesto", como Zatocoding, ahorraron espacio al ingresar varios o todos los temas en el mismo campo; tal "código superpuesto" almacena mucha más información en menos espacio, pero a costa de selecciones "falsas" ocasionales. [1]
Una vez que tenga una colección de fichas, una por libro, trabajo de investigación o artículo de revista en una biblioteca, con una lista de palabras clave (temas) discutidos en un libro en particular escrito en la tarjeta de ese libro, la "forma obvia" de codificarlos temas es contar el número total de temas usados en toda la colección R, hacer una fila de R agujeros cerca de la parte superior de cada tarjeta, 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 no es práctico perforar miles de agujeros en cada tarjeta. Si bien puede que no parezca posible usar menos de 1 hoyo por sujeto, los sistemas de códigos superpuestos pueden resolver este problema.
Códigos superpuestos
El sistema de recuperación de información Zatocoding fue desarrollado por Calvin Mooers en 1947. [3]
Calvin Mooers inventó Zatocoding en MIT, un sistema de recuperación de información mecánica basado en códigos superpuestos, y formó Zator Company en 1947 para comercializar sus aplicaciones. [4] El código superpuesto particular usado en ese sistema se llama Zatocoding , mientras que el sistema de recuperación de información de tarjetas perforadas al margen en su conjunto se llama " Zator ". [5]
La configuración de un código superpuesto para una biblioteca en particular es algo como esto:
- Al revisar cada tarjeta en el índice, se crea una lista de todas las materias R utilizadas en esta biblioteca en particular, y se anota el número máximo de materias r realmente escritas en una sola tarjeta. (Por ejemplo, digamos que tenemos 8000 materias y el bibliotecario decide indexar solo las principales r = 4 materias por libro).
- El bibliotecario mira la tarjeta física con muescas en el borde y anota el número 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 funciona incluso cuando N es mucho menor que R).
- El bibliotecario elige un número n de espacios por asignatura, normalmente [2]
- En la lista de todas las asignaturas R, para cada asignatura anote los huecos que se colocarán para esa asignatura. En lugar de hacer un agujero por sujeto de "la manera obvia", un código superpuesto colocará n agujeros por sujeto. (Hay varias formas de elegir estos patrones, los que distinguen entre los diversos códigos superpuestos; los discutimos a continuación).
- Cuando llegue un libro nuevo, cree una tarjeta nueva para él:
- Obtenga una tarjeta en blanco con los N agujeros estándar y escriba el nombre del libro, etc. en el medio.
- Anote los temas cubiertos por el libro en la tarjeta.
- Para cada uno de los r temas principales, busque ese tema en la lista grande y vea qué n espacios cortar para ese tema, y elimínelos.
- Cuando la tarjeta está terminada, puede tener hasta r * n ranuras cortadas, pero es más probable que al menos algunos de los patrones de las ranuras del sujeto se superpongan, lo que da como resultado solo v
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 ranura correspondiente de n ranuras y colocamos n agujas en toda la pila en ese patrón. Todas las tarjetas que se cortaron con ese patrón se caerán. Es posible que también se caigan algunas otras cartas no deseadas, cartas que tienen varios sujetos 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 se caiga cuando seleccionamos algún patrón de n agujas es aproximadamente. La mayoría de los sistemas tienen una N lo suficientemente grande y una r lo suficientemente pequeña como para que, v
Hay varias formas diferentes de elegir qué agujeros se colocará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] )
Codificación Zato
La configuración de un código Zato para una lista particular de sujetos R es algo como esto: [2]
- Para el primer sujeto, elija n de los N espacios al azar.
- Para el segundo sujeto, elija n de los N espacios al azar, pero asegúrese de que este patrón no sea idéntico al del primer sujeto.
- ...
- Para el tema R'th, elija n de los N espacios al azar, pero asegúrese de que no sea idéntico a ningún tema anterior.
Otros códigos superpuestos
Un Zatocode requiere un libro de códigos que enumere todos los temas y un código de muesca generado aleatoriamente asociado con cada uno. Otros códigos superpuestos "directos" tienen una función hash fija para transformar las letras en (una ortografía de) un tema en un código de muesca. Dichos 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 muesca correspondiente y, en principio, pueden agregar fácilmente nuevos temas sin cambiar el libro de códigos. [5]
Un filtro Bloom puede considerarse una especie de código superpuesto. [8]
Referencias
- ^ Robert V. Williams. "Tarjetas perforadas: un breve tutorial" . informática ahora 2002.
- ^ a b c d W. Ross Ashby. Diario de W. Ross Ashby: codificación de Zato, 22 de septiembre de 1960, pág. 6208-6222
- ^ "Acerca de la portada". Noticias de bibliotecas universitarias y de investigación, abril de 2008. [1] [2]
- ^ Eugene Garfield . "Relevancia continua de la codificación superpuesta . Journal of Information Science 8 (1984) 181.
- ^ a b Herbert Marvin Ohlman . "Frecuencias de letras de asunto-palabra con aplicaciones a la codificación superpuesta" . Actas de la Conferencia Internacional sobre Información Científica (1959).
- ^ Bourne, Charles P. (1963). Métodos de manejo de la información . John Wiley & Sons, Inc. pág. 67.
- ^ Mooers, Calvin N. (abril de 1959). La aplicación de la selección de inclusión de patrones simples a sistemas de recuperación de información a gran escala . Compañía Zator.
- ^ James Blustein; y Amal El-Maazawi. "Filtros de Bloom: un tutorial, un análisis y una encuesta" . pag. 11.
enlaces externos
- Calvin N. Mooers. "Aplicación de códigos aleatorios a la recopilación de información estadística" . Tesis (MS) Instituto de Tecnología 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.