Get best of the week

Hans Peter Lun et la naissance de l'algorithme de hachage

L'algorithme de hachage d'un ingénieur IBM a permis aux ordinateurs de rechercher rapidement des documents, de l'ADN et des bases de données.


À partir des années 40, Lun a développé des machines et des systèmes pour analyser les informations, en particulier l'algorithme de hachage actuellement largement utilisé, qu'il a proposé comme méthode de tri. chiffres et texte.

En novembre 1958 , lors d'une conférence internationale de six jours sur l'information scientifique, l'inventeur Hans Peter Lun fit la démonstration de plusieurs machines électromécaniques. Ils avaient l'air très ordinaire. Comme tous les autres appareils informatiques de l'époque, ils étaient anguleux, pratiques et conçus pour recevoir et trier des piles de cartes perforées dans des fentes et des paniers.

Cependant, contrairement à d'autres ordinateurs, les appareils Moon ne fonctionnaient pas avec des nombres et des formules, mais avec des mots et des phrases. L'une des machines qui a attiré une attention particulière a utilisé l'algorithme de la Lune appelé KWIC, Key for Word in Context . Ayant reçu une grande quantité de texte - par exemple, un article de 500 à 5000 mots, KWIC pourrait rapidement et de manière autonome construire quelque chose comme un index.

À cette époque, l'indexation, la classification et l'organisation des informations par écrit étaient un processus extrêmement long, même pour les professionnels expérimentés. Et le volume d'informations dans certaines régions augmentait trop rapidement pour le soutenir. Besoin désespérément de nouveaux et meilleurs outils pour résumer et généraliser. Pour les bibliothécaires et les informaticiens réunis à Washington, la manifestation KWIC s'apparentait à un tremblement de terre. Les journaux du pays ont immédiatement écrit sur l'invention exceptionnelle de la Lune.

Au début des années 60, KWIC était devenu la base du développement de centaines de systèmes d'indexation informatisés, y compris ceux utilisés par le Chemical Abstracts Service, les Biological Abstracts et l'Institut of Scientific Information. Certains experts ont qualifié le développement de KWIC de "plus grand événement dans le monde de la chimie depuis l'invention du tube à essai". Lun, ingénieur principal d'IBM, a également construit un «système intelligent» pour les entreprises avec KWIC. (Remarque: c'est lui qui a proposé le premier le terme BI). Elle a pu identifier et fournir des informations pertinentes à des individus spécifiques de grandes entreprises. Essentiellement, KWIC était à l'époque l'équivalent d'un moteur de recherche: il permettait aux utilisateurs de trouver rapidement les informations dont ils avaient besoin.

Nous tenons maintenant pour acquis que les ordinateurs peuvent travailler avec des informations et nous proposer instantanément des critiques de restaurants, des résultats sportifs et des cours de bourse. Au temps de la lune, les ordinateurs étaient simples et primitifs. Ses tentatives de travailler avec du texte ont aidé à former une vision plus large des ordinateurs et de leurs capacités. Et ses idées sont toujours à la base des algorithmes que nous utilisons pour les achats en ligne, la traduction automatique et la recherche génétique. Bien sûr, dans les années 50, tout cela était totalement impensable. Ensuite, nous parlerons de ce que la lune a conduit à une fonction de hachage, une solution à un problème qui n'existait même pas.

Les années après la Seconde Guerre mondialea eu un impact énorme sur les appareils informatiques électroniques. Les différentes machines des années de guerre ont effectué des calculs vitaux pour la balistique, les armes atomiques et la cryptographie. La guerre froide qui a suivi a fourni aux développeurs d'ordinateurs un financement continu et, par conséquent, les machines sont devenues plus rapides, plus précises et plus puissantes. Mais leur objectif principal - le traitement et le stockage des numéros - est resté inchangé.

Dans le monde informatique naissant, Lun était un personnage inhabituel. Ayant toujours un bon goût pour les vêtements, Lun comprenait beaucoup plus dans l'industrie textile qu'en informatique. Il est venu travailler chez IBM en 1941. Il semblerait que de nombreuses inventions de la Lune appartenaient encore à l'ère pré-numérique des calculatrices mécaniques et des règles à calcul. Même les ordinateurs numériques des années 50 étaient plus puissants que ses appareils électromécaniques. Néanmoins, les idées de la Lune, d'une manière ou d'une autre repensées et transformées, sont maintenant appliquées dans presque tous les types de logiciels.

Hans Peter Lun est né en 1896 dans la ville allemande de Barman. Son père, Johann Lun, un imprimeur à succès, était très fidèle aux passe-temps de ses enfants. Par exemple, une fois Hans, avec ses frères et sœurs, a construit un chemin de fer miniature dans le jardin familial. Des rails de plomb de 70 mètres ont fondu sur la machine de son père.

Après avoir terminé ses études, Lun est allé étudier l'artisanat familial en Suisse. Mais la Première Guerre mondiale et le repêchage dans l'armée allemande interrompent sa carrière imprimée. Après la guerre, Lun a commencé à faire du commerce de textiles. Aux États-Unis, il se retrouve en 1924 à la recherche de lieux potentiels pour la construction d'usines textiles. Et même dans le secteur textile, la veine inventive de la lune a trouvé une application. En 1927, il développe une ligne spéciale avec laquelle il est possible de compter le nombre de fils dans le tissu.Le Lunometer est toujours vendu par HP Luhn & Associates, une société d'ingénierie et de conseil fondée par Moon.

Lun apprit vite. Il a littéralement absorbé les connaissances de divers domaines et est progressivement devenu un grimpeur expérimenté, un spécialiste gastronomique gastronomique et un bon peintre paysagiste. Dans les années 1930, une liste complète de ses brevets comprenait: une cape pliante , un appareil pour façonner des bas pour femmes, une table de jeu et le Cocktail Oracle - un guide qui a aidé l'utilisateur à préparer un cocktail à partir de ce qui était à portée de main.


En 1933, peu avant la fin de l'interdiction, Lun a déposé un brevet pour un guide qui a aidé à préparer un cocktail des ingrédients disponibles.

Mais surtout, la Lune était intéressée par le stockage, la transmission et la récupération d'informations, en particulier d'informations textuelles. En fait, ces intérêts l'ont conduit à IBM, où il a reçu le «titre» de l'inventeur. Lun s'est avéré être exceptionnellement prolifique - au cours de sa carrière, il a créé environ 70 brevets pour IBM. Malgré le fait que personne ne l'a limité dans son choix de tâches, nombre de ses inventions étaient centrées sur l'utilisation de machines, y compris électroniques, pour manipuler l'information.

Par exemple, en 1946 et 1947, Lun a enseigné aux machines à «lire» des documents tapés sur une machine à écrire. L'un de ses appareils consistait en une bande métallique nichée dans une machine à écrire qui appliquait des codes magnétiques au papier. Une autre machine pourrait alors les scanner. Un peu plus tard, avec deux chimistes du MIT, Malcolm Dyson et James Perry, il a commencé à travailler sur une machine qui pourrait automatiquement rechercher des composés chimiques à l'aide de cartes perforées. Chaque carte perforée était codée avec des informations sur une connexion particulière. L'utilisateur a dû insérer une «carte de demande» dans la machine et indiquer un ensemble de critères selon lesquels il est nécessaire de comparer et de trier les cartes composites. Le scanner s'est avéré être extrêmement spécialisé et Lun a continué à rechercher des moyens plus universels de traitement automatique des informations.

Le problème de l'information durant ces années était sur toutes les lèvres. Dans l'après-guerre, le nombre de publications scientifiques et techniques a fortement augmenté. De nombreux experts craignaient que les affaires et la science chutent en raison d'une surcharge d'informations. Vannevar Bush , pendant la guerre, chef d'un grand département scientifique américain et l'un des initiateurs de la création de la National Science Foundation, a proposé un appareil électromécanique Memex de la taille d' une table pour stocker et relier les informations.

La proposition de Bush n'a jamais été réalisée, contrairement aux idées de Moon. Par exemple, le 6 janvier 1954, il a déposé un brevet pour un ordinateur pour la vérification des nombres.. Il s'agissait d'un appareil mécanique manuel conçu pour résoudre un problème pratique simple. À cette époque, divers types de numéros d'identification, tels que les numéros de carte de crédit et les numéros de sécurité sociale, ont commencé à jouer un rôle important dans la vie publique et privée. Cependant, les chiffres étaient difficiles à retenir, ils pouvaient être mal déchiffrés ou intentionnellement falsifiés. Un moyen était nécessaire pour vérifier rapidement l'exactitude des numéros d'identification.

Une machine de poche, la lune, était à peu près cela. Elle a travaillé sur la base de l'algorithme de somme de contrôle qu'il a développé. Pour un nombre à 10 chiffres, l'ordinateur a effectué les actions suivantes:
  • doubler tous les deux chiffres;
  • si un résultat est supérieur ou égal à 10, ajoutez les chiffres de ce résultat pour obtenir un nombre à un chiffre (par exemple, «16» deviendra 1 + 6 = 7);
  • ajouter les 10 chiffres du nouveau numéro;
  • multiplier par 9;
  • prendre le dernier chiffre de ce résultat.

Cet algorithme a produit un numéro de vérification unique. Dans la formulation originale de la lune, "0" signifiait que le nombre d'origine était réel. Dans les versions ultérieures, le numéro de vérification était simplement ajouté au numéro d'origine sous la forme du dernier chiffre, et il était facile de vérifier si le dernier chiffre correspond au résultat du contrôle sur la machine Moon. La séquence de base des calculs, maintenant connue sous le nom d'algorithme lunaire, est encore largement utilisée. Cela vérifie le nombre d'identifiants internationaux d'équipement mobile (IMEI) attribués aux téléphones portables.

Mais il est beaucoup plus important que l'un des algorithmes les plus importants de l'ère numérique provienne des engrenages et des roues de la machine Moon: le hachage. Cette large classe d'algorithmes offre des moyens puissants d'organiser les informations afin qu'un ordinateur puisse les retrouver facilement. Ceci est similaire à une recette de corned-beef et de pommes de terre: un algorithme de hachage, comme un cuisinier, divise et mélange les données de diverses manières. Une telle «confusion» avec un déploiement approprié peut accélérer de nombreux types d'opérations informatiques.

Au début de 1953, Lun a envoyé une note interne à IBM, où il a suggéré de mettre des informations dans des «seaux» (seau - seau, panier) pour accélérer la recherche. Supposons que vous ayez besoin de trouver le numéro de téléphone dans la base de données et de savoir à qui il appartient. Il se compose de 10 chiffres: "314-159-2652". L'ordinateur pourra vérifier un numéro de la base de données à la fois jusqu'à ce qu'il trouve l'entrée souhaitée. Cependant, si la base de données contient des millions de numéros, cela prendra beaucoup de temps.

L'idée de la Lune était d'organiser toutes les entrées dans des paniers numérotés. Cela a été fait comme suit: les chiffres du numéro de téléphone sont regroupés par paires (dans ce cas, 31, 41, 59, 26, 52). Ensuite, les paires de nombres sont ajoutées (4, 5, 14, 8, 7), et un nouveau nombre est généré à partir d'eux. Si le résultat de l'addition à l'intérieur de la paire contient deux chiffres, seul le dernier est pris (c'est-à-dire qu'il s'avère 45487). Le numéro de téléphone d'origine et le nom / l'adresse correspondant lui seront placés dans le panier avec le numéro 45487. La

recherche par numéro de téléphone a consisté à calculer le numéro de panier (en utilisant la méthode de la Lune) puis à extraire des informations de ce panier. Même si le groupe contenait plusieurs enregistrements, une recherche parmi eux était beaucoup plus rapide qu'une recherche dans l'ensemble de la base de données.

Depuis des décennies, les informaticiens et les programmeurs perfectionnent les méthodes de la Lune et leur trouvent de nouvelles utilisations. Mais l'idée de base est restée la même: utiliser les mathématiques pour organiser les données en groupes faciles à trouver. Les problèmes d'organisation et de recherche de données étant très courants en informatique, les algorithmes de hachage sont devenus indispensables en cryptographie, graphisme, télécommunications et biologie. Chaque fois que vous envoyez un numéro de carte de crédit sur Internet ou utilisez un dictionnaire d'éditeur de texte, les fonctions de hachage fonctionnent.


Indexation rapide: lors de la Conférence internationale de 1958 sur l'information scientifique, Hans Peter Lun (à droite) présente le système IBM de création automatique d'index de documents basé sur l'algorithme KWIC qu'il a développé.

Idées de lune en informatiqueest allé bien au-delà de la recherche habituelle. Il s'est rendu compte que les ordinateurs sont capables de manipulations complexes avec le texte: lire et comprendre le langage écrit. Indexation et organisation ultérieures de l'information pour résoudre des problèmes pratiques en science et en affaires. En 1958, son trieur de cartes chimiques était devenu le scanner universel de cartes et l'analyseur d'index spécial 9900, qui ont été présentés lors de la conférence de Washington. Ces appareils électromécaniques pouvaient rechercher et trier les cartes perforées selon les critères de l'utilisateur.

Mais la majeure partie du bruit provenait de KWIC, le système lunaire pour la construction de concordances. La concordance est une liste alphabétique de mots-clés utilisés dans un livre ou une collection d'œuvres. Il ressemble à un glossaire, mais il ne répertorie que les mots qui apparaissent réellement dans le texte, et non les concepts. Les mots qui ne portent pas de charge sémantique, comme les prépositions, les conjonctions et les articles, ne tombent pas en concordance. Les concordances sont utilisées depuis longtemps en théologie et en philologie. Par exemple, la concordance de la Bible indiquera chaque utilisation du mot «amour» en référence à un livre, un chapitre et un verset. Avant l'apparition de la recherche informatisée en texte intégral, la création d'une concordance était un processus long. Le plus souvent, la concordance a été créée pour les œuvres «importantes», comme la Bible ou les œuvres rassemblées de Shakespeare.

Ce que le système de la Lune a fait autrefois pour rechercher des nombres, KWIC l'a fait pour les textes. L'un et l'autre ont permis de rechercher facilement dans de grands volumes d'informations. Prenons un exemple très simple. Supposons que vous vouliez créer une concordance à partir des mots des titres des quatre livres suivants: Autant en emporte le vent, Guerre et paix, Ombre du vent et Ombre de la guerre. (Remarque: dans l'original - Autant en emporte le vent, Guerre et paix, L'ombre du vent et Ombres de guerre)



L'algorithme KWIC réorganisera les mots des noms dans tous les ordres possibles, puis organisera chaque permutation par ordre alphabétique. Le résultat sera une liste complète de mots-clés (c'est-à-dire tout sauf les prépositions, les conjonctions et les articles) dans le contexte dans lequel ils sont apparus.

Le système KWIC Moon a rapidement trouvé une application dans la communauté scientifique. Mais il savait que cela serait également utile pour les entreprises. En 1958, il a écrit un article pour le IBM Journal of Research and Development intitulé «A Business Intelligence System». Dans ce document, il a proposé un système qui pourrait générer automatiquement des résumés d'articles, extraire des idées clés des résumés, puis envoyer le résultat aux employés appropriés de l'entreprise. Lun a compris que résoudre le problème de la surcharge d'informations signifie développer une méthode pour trier rapidement les informations qui ne surchargeront pas les personnes avec des matériaux en excès.

Le New York Times dans une nécrologie de 1964, Luna décrit son système abstrait comme suit:

Scientific American 2326 , IBM . , ...


Le programme d'abstraction de Luna a d'abord calculé la fréquence de tous les mots de l'article. Après avoir écarté les mots très courants, "abstrait" a trouvé des phrases dans lesquelles plusieurs des mots les plus fréquents se produisent ensemble. Ces propositions sont considérées comme représentatives et sont placées dans un résumé. C'était une méthode purement statistique qui ne tentait pas de "comprendre" les mots de l'article ou la relation entre eux. Mais, comme KWIC, il a montré que les ordinateurs peuvent être efficacement utilisés pour organiser le texte dans un format facile à lire.

Lun a quitté IBM en 1961et trois ans plus tard, il est mort d'une leucémie. Il n'a pas vécu le jour où des changements majeurs ont eu lieu sur Internet. À l'exception d'un petit cercle de spécialistes de l'information, de travailleurs du textile et d'historiens, peu de gens se souviennent de son nom. Mais les idées de la lune vivent. Aujourd'hui, le hachage joue de nombreux rôles dans la gestion et la protection de notre vie numérique. Lorsque vous entrez votre mot de passe sur un site Web, le serveur enregistre très probablement une version hachée du mot de passe. Lorsque vous interagissez avec le site en utilisant le protocole https sécurisé ou achetez quelque chose en utilisant des bitcoins, les hachages y fonctionnent également. Avec les services cloud tels que Dropbox et Google Drive, le hachage permet de rendre le stockage et le partage de fichiers beaucoup plus efficaces. En génétique et dans d'autres recherches de haute technologie, le hachage réduit considérablement le temps requis pour analyser d'énormes quantités de données.

Les hachages ont transformé les ordinateurs en outils «textuels» qui peuvent être parlés avec des lettres et des mots. Google Translate, Google N-gram, Google AdWords et Google Search sont tous d'une manière ou d'une autre dédiés à trouver la signification du texte. Le boom de l'information sur Internet a fait de la lecture et de la compréhension automatiques [des nouvelles et autres informations] une priorité pour les entreprises, pour la science, pour tout le monde. Le développement des hachages a été associé aux textes et reflète les réflexions de Lun sur les mots, les phrases, les concordances, les extraits, les index et les résumés.

C’est l’héritage de Luna: il a aidé à montrer que les calculatrices et les calculs ne sont pas seulement le domaine des mathématiques, des statistiques et de la logique, mais aussi le langage, la linguistique et la littérature. À l'époque, c'était une façon révolutionnaire de percevoir les machines.

Historien technologique Michael Mahoneyappelé l'ordinateur «une machine à stéroïdes»: «pas seulement une chose, mais beaucoup de choses, une machine qui peut être affûtée à n'importe quelle fin. Même maintenant, nous avons tendance à considérer les ordinateurs au sens étroit comme des processeurs numériques géants qui effectuent des millions de calculs et d'opérations par seconde. Le regard de Hans Peter Moon sur les ordinateurs s'est étendu davantage. Réalisant que l'ordinateur est multiforme, il a contribué à ouvrir de nouveaux horizons prometteurs pour la recherche. »

More articles:


All Articles