Código sobreposto - Superimposed code

Cartão chanfrado com dados para um item bibliográfico. As bordas ainda não foram entalhadas.

Um código sobreposto , como Zatocoding, é um tipo de código hash popular em sistemas marginais de cartão perfurado .

Sistemas marginais de cartão perfurado

Muitos nomes, alguns deles de marca registrada, têm sido usados ​​para sistemas marginais de cartão perfurado: cartões com entalhes na borda, cartões com fenda, EZ Sort, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket, etc. O centro de cada cartão as informações relevantes - normalmente o nome e o autor de um livro, artigo de pesquisa ou artigo de jornal em uma prateleira próxima; e uma lista de assuntos e palavras-chave. Alguns conjuntos de cartões continham todas as informações exigidas pelo usuário no próprio cartão, escrito à mão, datilografado ou em microfilme ( cartão de abertura ). Cada cartão em uma pilha tinha o mesmo conjunto de orifícios pré-perfurados. O usuário encontraria os cartões específicos relevantes para uma pesquisa alinhando os orifícios no conjunto de cartões (usando um suporte de cartão ou bandeja de cartão), inserindo uma ou mais hastes semelhantes a agulhas de tricô em todo o caminho através da pilha, de modo que o desejado os cartões (que foram entalhados ou abertos) caíram dos cartões irrelevantes na coleção (deixados sem entalhes), que permanecem na (s) agulha (s). Um usuário pode repetir essa seleção muitas vezes para formar uma consulta de pesquisa booleana complexa . Um cartão que fosse relevante para 2 ou mais assuntos teria o (s) slot (s) para cada um desses assuntos recortados, de forma que o cartão cairia quando um ou outro ou ambos os assuntos fossem selecionados. Os sistemas de codificação de "código sobreposto", como o Zatocoding, economizavam espaço ao inserir vários ou todos os assuntos no mesmo campo; esse "código sobreposto" armazena muito mais informações em menos espaço, mas ao custo de seleções "falsas" ocasionais.

Depois de ter uma coleção de fichas, uma por livro, trabalho de pesquisa ou artigo de jornal em uma biblioteca, com uma lista de palavras-chave (assuntos) discutidos em um livro específico escrita no cartão desse livro, a "maneira óbvia" de codificá-los assuntos é contar o número total de assuntos usados ​​em toda a coleção R, fazer uma fileira de buracos R perto do topo de cada cartão, e para cada assunto realmente discutido em um livro particular, cortar uma fenda do buraco correspondente àquele assunto no cartão correspondente a esse livro. Naturalmente, isso também requer uma lista separada de cada assunto usado na coleção, que indica qual buraco é feito para cada assunto. Infelizmente, pode haver milhares de assuntos distintos na coleção, e é impraticável fazer milhares de furos em cada cartão. Embora possa não parecer possível usar menos de 1 buraco por assunto, sistemas de código sobrepostos podem resolver esse problema.

Códigos sobrepostos

O sistema Zatocoding de recuperação de informações foi desenvolvido por Calvin Mooers em 1947.

Calvin Mooers inventou o Zatocoding no MIT, um sistema mecânico de recuperação de informações baseado em códigos sobrepostos, e formou a Zator Company em 1947 para comercializar seus aplicativos. O código sobreposto específico usado nesse sistema é denominado Zatocoding , enquanto o sistema de recuperação de informações do cartão perfurado nas margens como um todo é denominado " Zator ".

A configuração de um código sobreposto para uma biblioteca específica é mais ou menos assim:

• Percorrendo cada cartão no índice, uma lista de todos os assuntos R usados ​​nesta biblioteca particular é criada, e o número máximo de assuntos r realmente escritos em um único cartão é anotado. (Por exemplo, digamos que temos 8.000 assuntos e o bibliotecário decide indexar apenas os r = 4 assuntos principais por livro).
• O bibliotecário olha para o cartão com entalhes físicos e anota o número de orifícios N em cada cartão. (Se N> = R, então poderíamos usar o "caminho óbvio" mencionado acima - o ponto principal da codificação zatográfica é que ele funciona mesmo quando N é muito menor que R).
• O bibliotecário escolhe algum número n de slots por assunto - normalmente ${\ displaystyle n = N (1-2 ^ {- {\ frac {1} {r}}})}$
• Na lista de todos os assuntos R, para cada assunto, escreva quais buracos serão feitos para aquele assunto. Em vez de abrir um buraco por assunto "da maneira óbvia", um código sobreposto abrirá n buracos por assunto. (Existem várias maneiras de escolher esses padrões - aqueles que distinguem entre os vários códigos sobrepostos; nós os discutiremos a seguir).
• Quando um novo livro chegar, faça um novo cartão para ele:
  • Pegue um cartão em branco com os N buracos padrão e anote o nome do livro, etc. no meio.
  • Escreva os assuntos cobertos pelo livro no cartão.
  • Para cada um dos r principais assuntos, procure aquele assunto na grande lista e veja quais n slots cortar para aquele assunto e corte-os.
  • Quando o cartão for concluído, pode ter até r * n slots cortados - mas é mais provável que pelo menos alguns dos padrões de slots do assunto se sobreponham, resultando em apenas v <r * n slots.

Mais tarde, quando precisarmos encontrar livros sobre algum assunto específico, procuramos esse assunto em nossa lista de todos os R assuntos, encontramos o padrão de slot correspondente de n slots e colocamos n agulhas em toda a pilha nesse padrão. Todos os cartões que foram cortados com esse padrão cairão. É possível que algumas outras cartas indesejadas também possam cair - cartas que têm vários assuntos cujos padrões de buraco se sobrepõem de forma a imitar o padrão desejado. A probabilidade F de alguma placa indesejada com v slots cortadas cair quando selecionamos algum padrão de n agulhas é de aproximadamente . A maioria dos sistemas tem um N grande o suficiente er pequeno o suficiente para que v <N / 2 (ou seja, o cartão está com menos da metade da perfuração), de modo que a probabilidade de um cartão indesejado cair é menor que . ${\ displaystyle F = \ left ({\ frac {v} {N}} \ right) ^ {n}}$${\ displaystyle F <\ left ({\ frac {1} {2}} \ right) ^ {n}}$

Existem várias maneiras de escolher quais buracos serão feitos para cada assunto.

(Várias variações de Zatocoding foram desenvolvidas. Bourne descreve uma variante "para sistemas de recuperação mais recentes que requerem alto desempenho do sistema de codificação sobreposta", usando uma abordagem publicada por Mooers em 1959.)

Zatocoding

A configuração de um Zatocode para uma lista específica de assuntos R é mais ou menos assim:

• Para o primeiro sujeito, escolha n dos N slots aleatoriamente.
• Para o segundo sujeito, escolha n dos N slots aleatoriamente - mas certifique-se de que esse padrão não seja idêntico ao do primeiro sujeito.
• ...
• Para o R'ésimo assunto, escolha n dos N slots aleatoriamente - mas certifique-se de que não seja idêntico a qualquer assunto anterior.

Outros códigos sobrepostos

Um Zatocode requer um livro de código que lista todos os assuntos e um código de entalhe gerado aleatoriamente associado a cada um. Outros códigos sobrepostos "diretos" têm uma função de hash fixa para transformar as letras em (uma grafia de) um assunto em um código de entalhe. Esses códigos requerem um livro de código muito mais curto que descreve a tradução das letras em uma palavra para o código de entalhe correspondente e pode, em princípio, adicionar facilmente novos assuntos sem alterar o livro de código.

Um filtro Bloom pode ser considerado uma espécie de código sobreposto.

Referências

links externos

• Calvin N. Mooers. “Aplicação de códigos aleatórios à recolha de informação estatística” . Tese (MS) Massachusetts Institute of Technology. Dept. of Mathematics, 1948.
• Calvin N. Mooers. "Zatocodificação aplicada à organização mecânica do conhecimento" . Jornal da Sociedade Americana de Ciência e Tecnologia da Informação. 2007