🧔 🤰🏾 👴🏽 Hans Peter Lun e o nascimento do algoritmo de hash 🎦 🗽 🔪

O algoritmo de hash do engenheiro da IBM deu aos computadores a capacidade de pesquisar rapidamente documentos, DNA e bancos de dados.

A partir da década de 1940, Lun desenvolveu máquinas e sistemas para analisar informações, em particular o algoritmo de hash atualmente usado, que ele propôs como método de classificação. números e texto.

Em novembro de 1958 , durante uma conferência internacional de seis dias sobre informações científicas, o inventor Hans Peter Lun demonstrou várias máquinas eletromecânicas. Eles pareciam muito comuns. Como todos os outros dispositivos de computação da época, eles eram angulares, práticos e projetados para receber e classificar pilhas de cartões perfurados em slots e cestas.

No entanto, diferentemente de outros computadores, os dispositivos Moon não funcionavam com números e fórmulas, mas com palavras e frases. Uma das máquinas que atraiu atenção particular usou o algoritmo da Lua chamado KWIC, Key for Word in Context . Tendo recebido uma grande quantidade de texto - por exemplo, um artigo de 500 a 5000 palavras, o KWIC poderia criar rápida e autonomamente algo como um índice.

Naquela época, a indexação, classificação e organização das informações por escrito era um processo extremamente demorado, mesmo para profissionais experientes. E o volume de informações em algumas áreas estava crescendo rápido demais para apoiá-lo. Precisava desesperadamente de novas e melhores ferramentas para abstrair e generalizar. Para bibliotecários e cientistas da informação reunidos em Washington, a demonstração do KWIC foi semelhante a um terremoto. Jornais em todo o país escreveram imediatamente sobre a excelente invenção da Lua.

No início dos anos 60, o KWIC havia se tornado a base para o desenvolvimento de centenas de sistemas de indexação computadorizados, incluindo os utilizados pelo Chemical Abstracts Service, Biological Abstracts e pelo Institute of Scientific Information. Alguns especialistas chamaram o desenvolvimento do KWIC de "o maior evento do mundo da química desde a invenção do tubo de ensaio". Lun, engenheiro sênior da IBM, também construiu um "sistema inteligente" para os negócios com a KWIC. (Nota: foi ele quem propôs o termo BI pela primeira vez). Ela conseguiu identificar e fornecer informações relevantes para indivíduos específicos de grandes empresas. Em essência, o KWIC era o equivalente a um mecanismo de busca na época: permitia que os usuários encontrassem rapidamente as informações necessárias.

Agora assumimos que os computadores podem trabalhar com informações e oferecer instantaneamente análises de restaurantes, resultados esportivos e preços das ações. Nos dias da lua, os computadores eram simples e primitivos. Suas tentativas de trabalhar com texto ajudaram a formar uma visão mais ampla dos computadores e de seus recursos. E suas idéias ainda são a base dos algoritmos que usamos para compras on-line, tradução automática e pesquisa genética. Certamente, na década de 1950, tudo isso era completamente impensável. Em seguida, falaremos sobre o que a lua levou a uma função de hash, uma solução para um problema que nem sequer existia.

Os anos após a Segunda Guerra Mundialteve um enorme impacto em dispositivos de computação eletrônica. As várias máquinas dos anos da guerra realizaram cálculos vitais para balística, armas atômicas e criptografia. A Guerra Fria que se seguiu forneceu aos desenvolvedores de computadores financiamento contínuo e, como resultado, as máquinas se tornaram mais rápidas, mais precisas e mais poderosas. Mas seu principal objetivo - processar e armazenar números - permaneceu inalterado.

No mundo nascente dos computadores, Lun era um personagem incomum. Sempre com um bom gosto por roupas, Lun entendia muito mais a indústria têxtil do que a ciência da computação. Ele veio trabalhar na IBM em 1941. Parecia que numerosas invenções da Lua ainda pertenciam à era pré-digital de calculadoras mecânicas e regras de slides. Até os computadores digitais da década de 1950 eram mais poderosos que seus dispositivos eletromecânicos. No entanto, as idéias da Lua, de uma maneira ou de outra repensadas e transformadas, agora são aplicadas em quase todos os tipos de software.

Hans Peter Lun nasceu em 1896 na cidade alemã de Barman. Seu pai, Johann Lun, um impressor de sucesso, era muito fiel aos hobbies de seus filhos. Por exemplo, uma vez que Hans, junto com seus irmãos e irmãs, construiu uma ferrovia em miniatura no jardim da família. Trilhos de chumbo de 70 metros foram fundidos na máquina de seu pai.

Depois de se formar, Lun estudou artesanato familiar na Suíça. Mas a Primeira Guerra Mundial e o recrutamento do exército alemão interromperam sua carreira impressa. Após a guerra, Lun começou a comercializar têxteis. Nos Estados Unidos, ele se viu em 1924 em busca de locais em potencial para a construção de fábricas têxteis. E mesmo no setor têxtil, a veia inventiva da lua encontrou aplicação. Em 1927, ele desenvolveu uma linha especial com a qual era possível contar o número de fios no tecido.O Lunometer ainda é vendido pela HP Luhn & Associates, uma empresa de engenharia e consultoria fundada por Moon.

Lun aprendeu rápido. Ele literalmente absorveu o conhecimento de vários campos e gradualmente se tornou um alpinista experiente, especialista em culinária gourmet e um bom pintor de paisagens. Na década de 1930, uma extensa lista de suas patentes incluía: uma capa dobrável , um dispositivo para modelar as meias femininas, uma mesa de jogos e o Cocktail Oracle - um guia que ajudou o usuário a fazer um coquetel com o que estava à mão.

Em 1933, pouco antes do final da Proibição, Lun registrou uma patente para um guia que ajudou a disponibilizar um coquetel dos ingredientes.

Mas, acima de tudo, a Lua estava interessada no armazenamento, transmissão e recuperação de informações, especialmente informações textuais. Na verdade, esses interesses o levaram à IBM, onde ele recebeu o "título" do inventor. Lun acabou sendo extraordinariamente prolífico - durante sua carreira, ele criou cerca de 70 patentes para a IBM. Apesar de ninguém o ter limitado na escolha de tarefas, muitas de suas invenções estavam centradas no uso de máquinas, inclusive eletrônicas, para manipular informações.

Por exemplo, em 1946 e 1947, Lun trabalhou para ensinar máquinas a "ler" documentos digitados em uma máquina de escrever. Um de seus dispositivos consistia em uma fita de metal enfiada em uma máquina de escrever que aplicava códigos magnéticos no papel. Então outra máquina poderia digitalizá-los. Um pouco mais tarde, ele, juntamente com dois químicos do MIT, Malcolm Dyson e James Perry, começou a trabalhar em uma máquina que podia procurar automaticamente compostos químicos usando cartões perfurados. Cada cartão perfurado foi codificado com informações sobre uma conexão específica. O usuário teve que inserir um "cartão de solicitação" na máquina e indicar um conjunto de critérios pelos quais é necessário comparar e classificar cartões compostos. O scanner acabou sendo extremamente especializado, e Lun continuou a procurar formas mais universais de processamento automático de informações.

O problema da informação naqueles anos estava nos lábios de todos. No período pós-guerra, o número de publicações científicas e técnicas aumentou bastante. Muitos especialistas temiam que os negócios e a ciência caíssem devido à sobrecarga de informações. Vannevar Bush , durante a guerra, líder de um grande departamento científico americano e um dos iniciadores da criação da National Science Foundation, propôs um dispositivo eletromecânico Memex do tamanho de uma mesa para armazenar e vincular informações.

A proposta de Bush nunca foi realizada, ao contrário das idéias de Moon. Por exemplo, em 6 de janeiro de 1954, ele registrou uma patente para um computador para verificação de números.. Era um dispositivo mecânico manual projetado para resolver um problema prático simples. Naquela época, vários tipos de números de identificação, como números de cartão de crédito e previdência social, começaram a desempenhar um papel importante na vida pública e privada. No entanto, os números eram difíceis de lembrar, podiam ser descriptografados incorretamente ou falsificados intencionalmente. Era necessário um meio para verificar rapidamente a correção dos números de identificação.

Uma máquina do tamanho de um bolso, a lua, era exatamente isso. Ela trabalhou com base no algoritmo de soma de verificação que ele desenvolveu. Para um número de 10 dígitos, o computador executou as seguintes ações:

dobrar a cada segundo dígito;
se qualquer resultado for maior ou igual a 10, adicione os dígitos desse resultado para obter um número de um dígito (por exemplo, “16” se tornará 1 + 6 = 7);
adicione todos os 10 dígitos do novo número;
multiplique por 9;
pegue o último dígito desse resultado.

Esse algoritmo produziu um número de verificação exclusivo. Na formulação original da lua, "0" significava que o número original era real. Nas versões posteriores, o número de verificação era simplesmente adicionado ao número original na forma do último dígito, e era fácil verificar se o último dígito corresponde ao resultado da verificação na máquina Moon. A sequência básica de cálculos, agora conhecida como Algoritmo da Lua, ainda é amplamente utilizada. Isso verifica o número de identificadores internacionais de equipamentos móveis (IMEIs) atribuídos aos telefones celulares.

Mas é muito mais importante que um dos algoritmos mais importantes da era digital venha das engrenagens e rodas da máquina Moon: o hash. Essa ampla classe de algoritmos oferece meios poderosos de organizar informações para que um computador possa encontrá-las facilmente. Isso é semelhante a uma receita de carne e batatas em lata: um algoritmo de hash, como um cozinheiro, divide e mistura dados de várias maneiras. Essa "confusão" com a implantação adequada pode acelerar muitos tipos de operações do computador.

No início de 1953, Lun enviou uma nota interna à IBM, onde sugeriu colocar informações em "baldes" (balde - balde, cesta) para acelerar a pesquisa. Suponha que você precise encontrar o número de telefone no banco de dados e descobrir a quem ele pertence. É composto por 10 números: "314-159-2652". O computador poderá verificar um número do banco de dados por vez até encontrar a entrada desejada. No entanto, se o banco de dados contiver milhões de números, levará muito tempo.

A idéia da Lua era organizar todas as entradas em cestas numeradas. Isso foi feito da seguinte maneira: os dígitos do número de telefone são agrupados em pares (neste caso, 31, 41, 59, 26, 52). Em seguida, os pares de números são adicionados (4, 5, 14, 8, 7) e um novo número é gerado a partir deles. Se o resultado da adição dentro do par contiver dois dígitos, apenas o último será obtido (ou seja, 45487). O número de telefone original e o nome / endereço correspondente a ele serão colocados na cesta com o número 45487. A

pesquisa por número de telefone consistiu em calcular o número da cesta (usando o método Moon) e depois extrair informações dessa cesta. Mesmo que o grupo contivesse vários registros, uma pesquisa entre eles era muito mais rápida que uma pesquisa no banco de dados inteiro.

Por décadas, cientistas da computação e programadores aperfeiçoaram os métodos da Lua e descobriram novos usos para eles. Mas a idéia básica permaneceu a mesma: use a matemática para organizar os dados em grupos fáceis de encontrar. Como os problemas de organização e busca de dados são muito comuns na tecnologia de computadores, os algoritmos de hash se tornaram indispensáveis em criptografia, gráficos, telecomunicações e biologia. Sempre que você envia um número de cartão de crédito pela Internet ou usa um dicionário de editor de texto, as funções de hash funcionam.

Indexação rápida: Na Conferência Internacional de Informações Científicas de 1958, Hans Peter Lun (à direita) demonstra o sistema IBM para criar automaticamente índices de documentos com base no algoritmo KWIC que ele desenvolveu.

Idéias da lua na ciência da computaçãofoi muito além da busca usual. Ele percebeu que os computadores são capazes de manipulações complexas com o texto: lendo e entendendo a linguagem escrita. Posterior indexação e organização da informação para resolver problemas práticos em ciências e negócios. Em 1958, seu classificador de cartões químicos havia se tornado o Universal Card Scanner e o 9900 Special Index Analyzer, demonstrados na conferência de Washington. Esses dispositivos eletromecânicos podem pesquisar e classificar cartões perfurados de acordo com os critérios do usuário.

Mas a maior parte do ruído foi feita pelo KWIC, o sistema Moon para a construção de concordâncias. Concordância é uma lista alfabética de palavras-chave usadas em um livro ou coleção de obras. Parece um glossário, mas lista apenas as palavras que realmente aparecem no texto, e não os conceitos. Palavras que não carregam uma carga semântica, como preposições, conjunções e artigos, não entram em concordância. Concordâncias são usadas há muito tempo em teologia e filologia. Por exemplo, a concordância da Bíblia indicará todo uso da palavra "amor" com referência a um livro, capítulo e verso. Antes da pesquisa computadorizada de texto completo aparecer, criar concordância era um processo demorado. Mais frequentemente, a concordância foi criada para obras "importantes", como a Bíblia ou as obras coletadas de Shakespeare.

O que o sistema Moon fez uma vez para procurar por números, o KWIC fez por textos. Tanto um como o outro tornaram possível pesquisar facilmente grandes volumes de informação. Veja um exemplo muito simples. Suponha que você queira criar uma concordância com as palavras nos títulos dos quatro livros a seguir: Longe do Vento, Guerra e Paz, Sombra do Vento e Sombra da Guerra. (Nota: no original - E o vento

levou , a guerra e a paz, a sombra do vento e as sombras da guerra) O algoritmo KWIC reorganizará as palavras dos nomes em todas as ordens possíveis e, em seguida, organizará cada permutação em ordem alfabética. O resultado será uma lista completa de palavras-chave (ou seja, tudo, exceto preposições, conjunções e artigos) no contexto em que elas apareceram.

O sistema KWIC Moon encontrou rapidamente aplicação na comunidade científica. Mas ele sabia que seria útil para os negócios também. Em 1958, ele escreveu um artigo para o IBM Journal of Research and Development, intitulado "A Business Intelligence System". Nele, ele propôs um sistema que poderia gerar automaticamente resumos de artigos, extrair idéias-chave dos resumos e enviar o resultado aos funcionários apropriados da empresa. Lun entendeu que resolver o problema da sobrecarga de informações significa desenvolver um método para classificar rapidamente as informações que não sobrecarregarão as pessoas com excesso de materiais.

No New York Times, em um obituário de 1964, Luna descreveu seu sistema abstrato da seguinte maneira:

Scientific American 2326 , IBM . , ...

O programa de abstração de Luna calculou primeiro a frequência de todas as palavras no artigo. Após descartar as palavras muito comuns, "abstrato" encontrou sentenças nas quais várias das palavras mais frequentes ocorrem juntas. Tais propostas são consideradas representativas e colocadas em um resumo. Era um método puramente estatístico que não tentava "entender" as palavras no artigo ou o relacionamento entre elas. Mas, como o KWIC, ele mostrou que os computadores podem ser efetivamente usados para organizar o texto em um formato de fácil leitura.

Lun deixou a IBM em 1961e três anos depois ele morreu de leucemia. Ele não viveu para ver o dia em que ocorreram grandes mudanças na Internet. Excluindo um pequeno círculo de especialistas em informação, trabalhadores têxteis e historiadores, poucas pessoas se lembram do nome dele. Mas as idéias da lua vivem. Hoje, o hash desempenha muitos papéis no gerenciamento e proteção de nossas vidas digitais. Quando você digita sua senha em um site, o servidor provavelmente salva uma versão em hash da senha. Quando você interage com o site usando o protocolo https seguro ou compra algo usando bitcoins, os hashes também funcionam lá. Com serviços em nuvem, como Dropbox e Google Drive, o hash ajuda a tornar o armazenamento e o compartilhamento de arquivos muito mais eficientes. Na genética e em outras pesquisas de alta tecnologia, o hash reduz significativamente o tempo necessário para analisar grandes quantidades de dados.

Hashes transformou computadores em ferramentas "textuais" que podem ser faladas com letras e palavras. O Google Translate, o gramatical do Google, o Google AdWords e a Pesquisa do Google são, de uma forma ou de outra, dedicados a encontrar o significado do texto. O boom da informação na Internet tornou a leitura e o entendimento automáticos [de notícias e outras informações] uma prioridade para os negócios, para a ciência e para todos. O desenvolvimento de hashes foi associado a textos e é um reflexo dos pensamentos de Lun sobre palavras, frases, concordâncias, trechos, índices e resumos.

Este é o legado de Luna: ele ajudou a mostrar que calculadoras e cálculos não são apenas o domínio da matemática, estatística e lógica, mas também linguagem, linguística e literatura. Naquela época, era uma maneira revolucionária de perceber as máquinas.

Historiador tecnológico Michael Mahoneychamou o computador de “uma máquina de esteróides”: “não apenas uma coisa, mas muitas coisas, uma máquina que pode ser afiada para qualquer finalidade. Mesmo agora, tendemos a ver os computadores em sentido estrito como processadores digitais gigantes que realizam milhões de cálculos e operações por segundo. O olhar de Hans Peter Moon nos computadores se estendeu ainda mais. Percebendo que o computador é multifacetado, ajudou a abrir novos e promissores horizontes para a pesquisa. ”

Hans Peter Lun e o nascimento do algoritmo de hash

More articles: