🏬 🚚 🐰 Hans Peter Lun y el nacimiento del algoritmo hash 👨🏼‍🤝‍👨🏻 🛌🏾 🍁

El algoritmo hash de un ingeniero de IBM le dio a las computadoras la capacidad de buscar rápidamente documentos, ADN y bases de datos.

A partir de la década de 1940, Lun desarrolló máquinas y sistemas para analizar información, en particular, el algoritmo hash ampliamente utilizado actualmente, que propuso como método de clasificación. Números y texto.

En noviembre de 1958 , durante una conferencia internacional de seis días sobre información científica, el inventor Hans Peter Lun demostró varias máquinas electromecánicas. Se veían muy ordinarios. Como todos los demás dispositivos informáticos de la época, eran angulares, prácticos y diseñados para recibir y clasificar montones de tarjetas perforadas en ranuras y cestas.

Sin embargo, a diferencia de otras computadoras, los dispositivos de la Luna no funcionaban con números y fórmulas, sino con palabras y oraciones. Una de las máquinas que atrajo particular atención usó el algoritmo de la Luna llamado KWIC, Clave para Word en contexto . Habiendo recibido una gran cantidad de texto, por ejemplo, un artículo de 500 a 5000 palabras, KWIC podría construir de forma rápida y autónoma algo así como un índice.

En ese momento, la indexación, clasificación y organización de la información por escrito era un proceso extremadamente lento, incluso para profesionales experimentados. Y el volumen de información en algunas áreas estaba creciendo demasiado rápido para soportarlo. Necesitaba desesperadamente nuevas y mejores herramientas para abstraer y generalizar. Para los bibliotecarios y los científicos de la información reunidos en Washington, la demostración de KWIC fue similar a un terremoto. Los periódicos de todo el país escribieron de inmediato sobre el invento sobresaliente de la Luna.

A principios de la década de 1960, KWIC se había convertido en la base para el desarrollo de cientos de sistemas de indexación computarizados, incluidos los utilizados por el Servicio de Resúmenes Químicos, Resúmenes Biológicos y el Instituto de Información Científica. Algunos expertos calificaron el desarrollo de KWIC como "el mayor evento en el mundo de la química desde la invención del tubo de ensayo". Lun, el ingeniero senior de IBM, también construyó un "sistema inteligente" para negocios con KWIC. (Nota: fue él quien primero propuso el término BI). Ella pudo identificar y entregar información relevante a individuos específicos de grandes empresas. En esencia, KWIC era el equivalente de un motor de búsqueda en ese momento: permitía a los usuarios encontrar rápidamente la información que necesitaban.

Ahora damos por sentado que las computadoras pueden trabajar con información y al instante nos ofrecen reseñas de restaurantes, resultados deportivos y precios de acciones. En los días de la luna, las computadoras eran simples y primitivas. Sus intentos de trabajar con texto ayudaron a formar una visión más amplia de las computadoras y sus capacidades. Y sus ideas siguen siendo la base de los algoritmos que utilizamos para las compras en línea, la traducción automática y la investigación genética. Por supuesto, en la década de 1950 todo esto era completamente impensable. A continuación, hablaremos sobre lo que la luna llevó a una función hash, una solución a un problema que ni siquiera existía.

Los años posteriores a la Segunda Guerra Mundialtuvo un gran impacto en los dispositivos informáticos electrónicos. Las diversas máquinas de los años de guerra realizaron cálculos vitales para balística, armas atómicas y criptografía. La Guerra Fría resultante proporcionó a los desarrolladores de computadoras fondos continuos y, como resultado, las máquinas se volvieron más rápidas, más precisas y más potentes. Pero su propósito principal, procesar y almacenar números, permaneció sin cambios.

En el naciente mundo de la informática, Lun era un personaje inusual. Siempre teniendo un buen gusto por la ropa, Lun entendió mucho más en la industria textil que en informática. Llegó a trabajar en IBM en 1941. Al parecer, numerosos inventos de la Luna todavía pertenecían a la era pre-digital de las calculadoras mecánicas y las reglas de cálculo. Incluso las computadoras digitales de la década de 1950 eran más potentes que sus dispositivos electromecánicos. Sin embargo, las ideas de la Luna, repensadas y transformadas de una forma u otra, ahora se aplican en casi todos los tipos de software.

Hans Peter Lun nació en 1896 en la ciudad alemana de Barman. Su padre, Johann Lun, un impresor exitoso, fue muy fiel a los pasatiempos de sus hijos. Por ejemplo, una vez que Hans, junto con sus hermanos y hermanas, construyó un ferrocarril en miniatura en el jardín familiar. Se fundieron rieles de plomo de 70 metros en la máquina de su padre.

Después de graduarse de la escuela, Lun fue a estudiar manualidades familiares en Suiza. Pero la Primera Guerra Mundial y el reclutamiento en el ejército alemán interrumpieron su carrera impresa. Después de la guerra, Lun comenzó a comerciar con textiles. En los Estados Unidos, se encontró en 1924 en busca de lugares potenciales para la construcción de fábricas textiles. E incluso en el negocio textil, la vena inventiva de la luna ha encontrado aplicación. En 1927, desarrolló una línea especial con la que era posible contar el número de hilos en la tela.El Lunómetro todavía es vendido por HP Luhn & Associates, una compañía de ingeniería y consultoría fundada por Moon.

Lun aprendió rápido. Literalmente absorbió el conocimiento de varios campos y gradualmente se convirtió en un escalador experimentado, especialista culinario gourmet y un buen pintor de paisajes. En la década de 1930, una extensa lista de sus patentes incluía: una capa plegable , un dispositivo para dar forma a las medias de las mujeres, una mesa de juego y el Oráculo de cóctel : una guía que ayudó al usuario a hacer un cóctel con lo que tenía a mano.

En 1933, poco antes del final de la Prohibición, Lun presentó una patente para una guía que ayudó a preparar un cóctel de los ingredientes.

Pero, sobre todo, la Luna estaba interesada en el almacenamiento, transmisión y recuperación de información, especialmente información textual. En realidad, estos intereses lo llevaron a IBM, donde recibió el "título" del inventor. Lun resultó ser inusualmente prolífico: durante su carrera, creó alrededor de 70 patentes para IBM. A pesar de que nadie lo limitó en su elección de tareas, muchos de sus inventos se centraron en el uso de máquinas, incluidas las electrónicas, para manipular información.

Por ejemplo, en 1946 y 1947, Lun trabajó para enseñar a las máquinas a "leer" documentos escritos en una máquina de escribir. Uno de sus dispositivos consistía en una cinta de metal metida en una máquina de escribir que aplicaba códigos magnéticos al papel. Entonces otra máquina podría escanearlos. Un poco más tarde, él, junto con dos químicos del MIT, Malcolm Dyson y James Perry, comenzó a trabajar en una máquina que podía buscar automáticamente compuestos químicos utilizando tarjetas perforadas. Cada tarjeta perforada se codificó con información sobre una conexión particular. El usuario tuvo que insertar una "tarjeta de solicitud" en la máquina e indicar un conjunto de criterios por los cuales es necesario comparar y clasificar las tarjetas compuestas. El escáner resultó ser extremadamente especializado, y Lun continuó buscando formas más universales de procesamiento automático de información.

El problema de la información en esos años estaba en boca de todos. En el período de posguerra, el número de publicaciones científicas y técnicas aumentó considerablemente. Muchos expertos temían que los negocios y la ciencia cayeran debido a la sobrecarga de información. Vannevar Bush , durante la guerra, el líder de un importante departamento científico estadounidense y uno de los iniciadores de la creación de la National Science Foundation, propuso un dispositivo electromecánico Memex del tamaño de una mesa para almacenar y vincular información.

La propuesta de Bush nunca se realizó, a diferencia de las ideas de Moon. Por ejemplo, el 6 de enero de 1954, solicitó una patente para "Computadora para verificar números". Era un dispositivo mecánico manual diseñado para resolver un problema práctico simple. En ese momento, varios tipos de números de identificación, como números de tarjetas de crédito y números de seguridad social, comenzaron a desempeñar un papel importante en la vida pública y privada. Sin embargo, los números eran difíciles de recordar, podían descifrarse incorrectamente o falsificarse intencionalmente. Se necesitaba una forma de verificar rápidamente la exactitud de los números de identificación.

Una máquina de bolsillo, la luna, era casi eso. Ella trabajó sobre la base del algoritmo de suma de comprobación que él desarrolló. Para un número de 10 dígitos, la computadora realizó las siguientes acciones:

duplicar cada segundo dígito;
si algún resultado es mayor o igual a 10, agregue los dígitos de este resultado para obtener un número de un solo dígito (por ejemplo, "16" se convertirá en 1 + 6 = 7);
agregue los 10 dígitos del nuevo número;
multiplicar por 9;
toma el último dígito de este resultado.

Este algoritmo produjo un número de verificación único. En la formulación original de la luna, "0" significaba que el número original era real. En versiones posteriores, el número de verificación simplemente se agregaba al número original en la forma del último dígito, y era fácil verificar si el último dígito corresponde al resultado de la verificación en la máquina Moon. La secuencia básica de cálculos, ahora conocida como el Algoritmo de la Luna, todavía se usa ampliamente. Esto verifica los números de identificadores internacionales de equipos móviles (IMEI) asignados a teléfonos celulares.

Pero es mucho más importante que uno de los algoritmos más importantes de la era digital provenga de los engranajes y las ruedas de la máquina lunar: el hashing. Esta amplia clase de algoritmos ofrece medios poderosos para organizar la información de modo que una computadora pueda encontrarla fácilmente. Esto es similar a una receta de carne en conserva y papa: un algoritmo hash, como un cocinero, divide y mezcla datos de varias maneras. Tal "confusión" con la implementación adecuada puede acelerar muchos tipos de operaciones informáticas.

A principios de 1953, Lun envió una nota interna a IBM, donde sugirió colocar información en “cubos” (cubo - cubo, cesta) para acelerar la búsqueda. Suponga que necesita encontrar el número de teléfono en la base de datos y averiguar a quién pertenece. Se compone de 10 números: "314-159-2652". La computadora podrá verificar un número de la base de datos a la vez hasta que encuentre la entrada deseada. Sin embargo, si la base de datos contiene millones de números, tomará mucho tiempo.

La idea de la Luna era organizar todas las entradas en cestas numeradas. Esto se hizo de la siguiente manera: los dígitos del número de teléfono se agrupan en pares (en este caso, 31, 41, 59, 26, 52). Luego se suman los pares de números (4, 5, 14, 8, 7) y se genera un nuevo número a partir de ellos. Si el resultado de la suma dentro del par contiene dos dígitos, solo se toma el último (es decir, resulta 45487). El número de teléfono original y el nombre / dirección correspondiente se colocarán en la cesta con el número 45487. La

búsqueda por número de teléfono consistió en calcular el número de la cesta (utilizando el método Moon) y luego extraer información de esta cesta. Incluso si el grupo contenía varios registros, una búsqueda entre ellos era mucho más rápida que una búsqueda en toda la base de datos.

Durante décadas, los informáticos y programadores han estado perfeccionando los métodos de la Luna y encontrando nuevos usos para ellos. Pero la idea básica seguía siendo la misma: usar las matemáticas para organizar los datos en grupos fáciles de encontrar. Dado que los problemas de organización y búsqueda de datos son muy comunes en la tecnología informática, los algoritmos de hash se han vuelto indispensables en criptografía, gráficos, telecomunicaciones y biología. Cada vez que envía un número de tarjeta de crédito a través de Internet o utiliza un diccionario editor de texto, las funciones hash funcionan.

Indexación rápida: en la Conferencia Internacional de Información Científica de 1958, Hans Peter Lun (derecha) demuestra el sistema de IBM para crear automáticamente índices de documentos basados en el algoritmo KWIC que desarrolló.

Ideas lunares en informáticafue mucho más allá de la búsqueda habitual. Se dio cuenta de que las computadoras son capaces de manipulaciones complejas con el texto: leer y comprender el lenguaje escrito. Posterior indexación y organización de la información para resolver problemas prácticos en ciencias y negocios. Para 1958, su clasificador de tarjetas químicas se había convertido en el Universal Card Scanner y el 9900 Special Index Analyzer, que se demostraron en la conferencia de Washington. Estos dispositivos electromecánicos podrían buscar y clasificar tarjetas perforadas de acuerdo con los criterios del usuario.

Pero la mayor parte del ruido fue hecho por KWIC, el sistema de la Luna para construir concordancias. Concordancia es una lista alfabética de palabras clave utilizadas en un libro o colección de obras. Parece un glosario, pero enumera solo las palabras que realmente aparecen en el texto, y no los conceptos. Las palabras que no llevan una carga semántica, como preposiciones, conjunciones y artículos, no caen en concordancia. Las concordancias se han utilizado durante mucho tiempo en teología y filología. Por ejemplo, la concordancia de la Biblia indicará cada uso de la palabra "amor" con referencia a un libro, capítulo y versículo. Antes de que apareciera la búsqueda computarizada de texto completo, crear concordancia era un proceso lento. La mayoría de las veces, la concordancia se creó para obras "importantes", como la Biblia o las obras recopiladas de Shakespeare.

Lo que el sistema de la Luna hizo una vez para buscar por números, KWIC hizo por textos. Tanto el uno como el otro hicieron posible buscar fácilmente a través de grandes volúmenes de información. Toma un ejemplo muy simple. Suponga que desea crear una concordancia a partir de las palabras en los títulos de los siguientes cuatro libros: Lo que el viento se llevó, Guerra y paz, Sombra del viento y Sombra de la guerra. (Nota: en el original: Lo que el viento se llevó, Guerra y paz, La sombra del viento y Sombras de guerra)

El algoritmo KWIC reorganizará las palabras de los nombres en todos los órdenes posibles y luego ordenará alfabéticamente cada permutación. El resultado será una lista completa de palabras clave (es decir, todo excepto preposiciones, conjunciones y artículos) en el contexto en el que aparecieron.

El sistema KWIC Moon encontró rápidamente aplicación en la comunidad científica. Pero sabía que también sería útil para los negocios. En 1958, escribió un artículo para el IBM Journal of Research and Development titulado "Un sistema de inteligencia empresarial". En él, propuso un sistema que podría generar automáticamente resúmenes de artículos, extraer ideas clave de los resúmenes y luego enviar el resultado a los empleados apropiados de la empresa. Lun comprendió que resolver el problema de la sobrecarga de información significa desarrollar un método para clasificar rápidamente la información que no agobiará a las personas con el exceso de materiales.

El New York Times en un obituario de 1964, Luna describió su sistema abstracto de la siguiente manera:

Scientific American 2326 , IBM . , ...

El programa de abstracción de Luna calculó primero la frecuencia de todas las palabras en el artículo. Después de descartar las palabras muy comunes, "abstracto" encontró oraciones en las que varias de las palabras más frecuentes aparecen juntas. Dichas propuestas se consideran representativas y se colocan en un resumen. Era un método puramente estadístico que no intentaba "comprender" las palabras del artículo o la relación entre ellas. Pero, al igual que KWIC, demostró que las computadoras se pueden usar de manera efectiva para organizar el texto en un formato fácil de leer.

Lun dejó IBM en 1961y tres años después murió de leucemia. No vivió para ver el día en que ocurrieron cambios importantes en Internet. Excluyendo un pequeño círculo de especialistas en información, trabajadores textiles e historiadores, pocas personas recuerdan su nombre. Pero las ideas de la luna viven. Hoy en día, el hash desempeña muchos roles en la gestión y protección de nuestras vidas digitales. Cuando ingresa su contraseña en un sitio web, el servidor probablemente guarda una versión hash de la contraseña. Cuando interactúa con el sitio utilizando el protocolo seguro https o compra algo con bitcoins, los hash también funcionan allí. Con servicios en la nube como Dropbox y Google Drive, el hash ayuda a que el almacenamiento y el intercambio de archivos sean mucho más eficientes. En genética y otras investigaciones de alta tecnología, el hash reduce significativamente el tiempo requerido para analizar grandes cantidades de datos.

Hashes convirtió las computadoras en herramientas "textuales" que se pueden hablar con letras y palabras. Google Translate, Google N-gram, Google AdWords y Google Search se dedican de una forma u otra a encontrar el significado del texto. El auge de la información en Internet ha convertido la lectura y la comprensión automáticas [de noticias y otra información] en una prioridad para los negocios, la ciencia y todos. El desarrollo de hashes se ha asociado con textos y es un reflejo de los pensamientos de Lun sobre palabras, oraciones, concordancias, extractos, índices y resúmenes.

Este es el legado de Luna: ayudó a demostrar que las calculadoras y los cálculos no solo son del dominio de las matemáticas, las estadísticas y la lógica, sino también del lenguaje, la lingüística y la literatura. En ese momento, era una forma revolucionaria de percibir las máquinas.

El historiador tecnológico Michael Mahoneyllamó a la computadora "una máquina de esteroides": "no solo una cosa, sino muchas cosas, una máquina que se puede afilar para cualquier propósito. Incluso ahora, tendemos a ver las computadoras en el sentido estricto como procesadores digitales gigantes que realizan millones de cálculos y operaciones por segundo. La mirada de Hans Peter Moon en las computadoras se extendió aún más. Al darse cuenta de que la computadora es multifacética, ha ayudado a abrir nuevos horizontes prometedores para la investigación ”.

Hans Peter Lun y el nacimiento del algoritmo hash

More articles: