[Перевод] Ханс Петер Лун и рождение алгоритма хеширования
Алгоритм хеширования инженера IBM дал компьютерам возможность быстрого поиска документов, ДНК и баз данных
Начиная с 1940-х годов, Лун разрабатывал машины и системы для анализа информации, в частности, широко используемый в настоящее время алгоритм хеширования, который он предложил в качестве способа сортировки как чисел, так и текста.
В ноябре 1958, во время шестидневной международной конференции, посвященной научной информации, изобретатель Ханс Петер Лун продемонстрировал несколько электромеханических машин. Выглядели они весьма заурядно. Как и все прочие вычислительные устройства того времени, они были угловатыми, практичными и предназначались для приема и сортировки стопок перфокарт в слотах и корзинах.
Однако, в отличие от прочих вычислительных машин, устройства Луна работали не с цифрами и формулами, а со словами и предложениями. Одна из машин, привлекшая особое внимание, использовала алгоритм Луна под названием KWIC, Key for Word in Context. Получив большой объем текста — например, статью от 500 до 5000 слов, KWIC могла быстро и автономно построить что-то наподобие индекса.
В то время индексация, классификация и организация информации в письменной форме были крайне трудоемкими процессом даже для опытных специалистов. А объем информации в некоторых областях увеличивался слишком быстро для того, чтобы его поддерживать. Отчаянно требовались новые, лучшие средства для абстрагирования и обобщения. Для библиотекарей и ученых в области информации, собравшихся в Вашингтоне, демонстрация KWIC была сродни землетрясению. Газеты по всей стране тут же написали о выдающемся изобретении Луна.
К началу 1960-х годов KWIC стала основой для разработки сотен компьютеризированных систем индексации, в том числе используемых Химической реферативной службой, Biological Abstracts и Институтом научной информации. Кто-то из экспертов назвал разработку KWIC «величайшим событием в мире химии со времен изобретения пробирки». Лун, старший инженер IBM, при помощи KWIC построил также «интеллектуальную систему» для бизнеса. (Примечание: именно он впервые и предложил термин BI) Она могла идентифицировать и доставлять релевантную информацию конкретным лицам крупных компаний. По сути, KWIC была эквивалентом поисковика в то время: она позволяла пользователям быстро находить нужную им информацию.
Теперь мы считаем само собой разумеющимся, что компьютеры могут работать с информацией и моментально предлагают нам обзоры ресторанов, результаты спортивных матчей, а также цены на акции. Во времена Луна компьютеры были простыми и примитивными. Его попытки работы с текстом помогли сформировать более широкий взгляд на компьютеры и их возможности. А предложенные им идеи до сих пор лежат в основе алгоритмов, которые мы используем для онлайн-покупок, машинного перевода и генетических исследований. Конечно, в 1950-х всё это было совершенно немыслимо. Далее мы поговорим о том, что привело Луна к хэш-функции, решению еще даже не существовавшей проблемы.
Годы после Второй мировой войны оказали огромное влияние на электронные вычислительные устройства. Различные машины военных лет производили жизненно важные вычисления для баллистики, атомного оружия и криптографии. Последовавшая за тем Холодная война обеспечила разработчикам компьютеров непрерывное финансирование, и в результате машины стали быстрее, точнее и мощнее. Но их основное предназначение — обработка и хранение чисел — осталось неизменным.
В только зарождающемся компьютерном мире Лун был необычным персонажем. Всегда имевший хороший вкус к одежде, Лун понимал в текстильной промышленности куда больше, чем в информатике. Он приехал устраиваться в IBM в 1941 году. Многочисленные изобретения Луна, казалось, все еще принадлежали к доцифровой эпохе механических калькуляторов и логарифмических линеек. Даже цифровые компьютеры 1950-х были мощнее его электромеханических устройств. Тем не менее, идеи Луна, так или иначе переосмысленные и преобразованные, теперь применяются практически во всех видах программного обеспечения.
Ханс Петер Лун родился в 1896 году в немецком городе Бармен. Его отец, Иоганн Лун, преуспевающий печатник, был очень лоялен к увлечениям своих детей. К примеру, однажды Ханс вместе с братьями и сестрами построил в семейном саду миниатюрную железную дорогу. А 70-метровые рельсы из свинца были выплавлены на отцовском станке.
Окончив школу, Лун отправился учиться семейному ремеслу в Швейцарию. Но Первая мировая война и призыв в немецкую армию прервали его печатную карьеру. После войны Лун занялся торговлей текстилем. В Соединенных Штатах он оказался в 1924 году в поисках потенциальных мест для постройки текстильных фабрик. И даже в текстильном бизнесе изобретательская жилка Луна нашла применение. В 1927 году он разработал специальную линейку, с помощью которой можно было посчитать количество нитей в ткани. Lunometer («лунометр») по-прежнему продается H.P. Luhn & Associates, инженерно-консалтинговой компанией, основанной Луном.
Лун быстро учился. Он буквально впитывал знания из самых разных областей и постепенно стал опытным альпинистом, кулинаром-гурманом и неплохим художником-пейзажистом. К 1930-м в обширном списке его патентов значились: складной плащ, устройство для придания формы женским чулкам, игровой стол и «Коктейльный оракул» — руководство, которое помогало пользователю составить коктейль из того, что найдется под рукой.
В 1933 году, незадолго до окончания «Сухого закона», Лун подал заявку на патент руководства, которое помогало составить коктейль из имеющихся в наличии ингредиентов.
Но больше всего Луна интересовали хранение, передача и поиск информации, особенно текстовой. Собственно, эти интересы и привели его в IBM, где он получил «звание» изобретателя. Лун оказался необычайно плодовит — за свою карьеру он создал для IBM порядка 70 патентов. Несмотря на то, что никто его не ограничивал в выборе задач, многие его изобретения были сосредоточены вокруг использования машин, в том числе электронных, для манипулирования информацией.
Например, в 1946 и 1947 годах Лун работал над тем, чтобы научить машины «читать» документы, набранные на машинке. Одно его устройство состояло из металлической ленты, заправленной в пишущую машинку, которая наносила на бумагу магнитные коды. Затем уже другая машина могла их сканировать. Чуть позже он вместе с двумя химиками из MIT, Малкольмом Дайсоном и Джеймсом Перри, начал работу над машиной, которая могла бы автоматически искать химические соединения, используя перфокарты. Каждая перфокарта была закодирована информацией о конкретном соединении. Пользователю надо было вставить в машину «карточку запроса» и указать набор критериев, по которым требуется сравнивать и сортировать составные карточки. Сканер получился крайне узкоспециализированным, и Лун продолжил искать более универсальные способы автоматической обработки информации.
Проблема информации в те годы была у всех на устах. В послевоенное время резко возросло количество научных и технических публикаций. Многие эксперты опасались, что бизнес и наука падут из-за перегрузки информацией. Ванневар Буш, во время войны лидер крупной американского научного ведомства и один из инициаторов создания Национального научного фонда, предложил проект электромеханического устройства Memex размером со стол, чтобы хранить и связывать информацию.
Предложение Буша так и не было реализовано, в отличие от идей Луна. Например, 6 января 1954 года он подал заявку на патент «Компьютера для проверки номеров». Это было ручное механическое устройство, призванное решить простую практическую задачу. В то время различные виды идентификационных номеров, такие как номера кредитных карт и номера социального страхования, начали играть большую роль в общественной и частной жизни. Однако цифры было трудно запомнить, они могли быть неверно расшифрованы или намеренно фальсифицированы. Необходим был способ быстрой проверки правильности идентификационных номеров.
Карманная машинка Луна как раз этим и занималось. Она работала на основе алгоритма контрольной суммы, который он разработал. Для 10-значного числа компьютер выполнял следующие действия:
- удвоить каждую вторую цифру;
- если какой-либо результат больше или равен 10, сложить цифры этого результата, чтобы получить однозначное число (например,»16» станет 1 + 6 = 7);
- сложить все 10 цифр нового номера;
- умножить на 9;
- взять последнюю цифру этого результата.
Этот алгоритм выдавал однозначный проверочный номер. В оригинальной формулировке Луна »0» означал, что исходное число было действительным. В более поздних версиях проверочное число просто добавлялось к исходному номеру в виде последней цифры, и можно было легко проверить, соответствует ли последняя эта цифра результату проверки на машине Луна. Основная последовательность вычислений, теперь известная как Алгоритм Луна, все еще широко используется. Таким образом проверяются номера международных идентификаторов мобильного оборудования (IMEI), присвоенные сотовым телефонам.
Но гораздо важнее, что из шестеренок и колес машинки Луна произошел один из самых важных алгоритмов цифровой эпохи: хеширование. Этот широкий класс алгоритмов предлагает мощные средства организации информации, чтобы её легко мог найти компьютер. Это похоже на рецепт солонины с картофелем: алгоритм хеширования, как повар, разбивает и смешивает данные различными способами. Подобное «смешение» при грамотном развертывании может ускорить многие типы компьютерных операций.
В начале 1953 года Лун направил в IBM внутреннюю записку, где предложил для ускорения поиска помещать информацию в «бакеты» (bucket — ведро, корзина). Предположим, вам нужно разыскать в базе данных номер телефона и выяснить, кому он принадлежит. Он состоит из 10 цифр:»314–159–2652». Компьютер сможет проверять по одному номеру из базы за раз, пока не найдет нужную запись. Однако если в базе содержатся миллионы номеров, это займет много времени.
Идея Луна заключалась в том, чтобы разложить все записи по пронумерованным корзинам. Делалось это следующим образом: цифры номера телефона группируются в пары (в данном случае 31, 41, 59, 26, 52). Затем пары цифр складываются (4, 5, 14, 8, 7), и из них генерируется новый номер. Если результат сложения внутри пары содержит две цифры, берется только последняя (то есть, получится 45487). Исходный номер телефона и имя/адрес, ему соответствующие, будут помещены в корзину под номером 45487.
Поиск по номеру телефона заключался в вычислении номера корзины (по методу Луна) и последующем извлечении информации из этой корзины. Даже если в группе содержалось несколько записей, поиск перебором среди них был намного быстрее, чем поиск по всей базе.
Десятилетиями компьютерные ученые и программисты совершенствовали методы Луна и находили им новое применение. Но основная идея осталась той же: используйте математику, чтобы организовать данные в легкие для поиска группы. Поскольку проблемы организации и поиска данных очень распространены в вычислительной технике, алгоритмы хеширования стали незаменимы в криптографии, графике, телекоммуникациях и биологии. Каждый раз, когда вы отправляете номер кредитной карты через Интернет или используете словарь текстового редактора, работают хэш-функции.
Быстрое индексирование: на Международной конференции научной информации 1958 года Ханс Петер Лун (справа) демонстрирует систему IBM для автоматического создания индексов документов на основе разработанного им алгоритма KWIC.
Идеи Луна в сфере вычислительной техники вышли далеко за рамки обычного поиска. Он понял, что компьютеры способны на сложные манипуляции с текстом: чтение и понимание письменной речи. Последующая индексация и организация информации для решения практических задач в науке и бизнесе. К 1958 году его сортировщик химических карт превратился в Универсальный сканер карт (Universal Card Scanner) и Специальный анализатор индекса 9900 (9900 Special Index Analyzer), которые и были продемонстрированы на вашингтонской конференции. Эти электромеханические устройства могли искать и сортировать перфокарты в соответствии с критериями пользователя.
Но больше всего шума наделала KWIC, система Луна для построения конкордансов. Конкорданс — это алфавитный список ключевых слов, используемых в книге или сборнике произведений. Он похож на глоссарий, но перечислены в нем только слова, которые реально появляются в тексте, а не понятия. Не несущие смысловой нагрузки слова, такие как предлоги, союзы и артикли, в конкорданс не попадают. Конкордансы давно используются в теологии и филологии. Например, конкорданс Библии укажет на каждый случай использования слова «любовь» со ссылкой на книгу, главу и стих. До того, как появился полнотекстовый компьютеризированный поиск, создание конкорданса было трудоемким процессом. Чаще всего конкорданс создавался для «важных» работ, таких как Библия или собрание сочинений Шекспира.
То, что система Луна в свое время сделала для поиска по числам, KWIC сделала для текстов. И та, и другая позволяли без труда производить поиск по большим объемам информации. Возьмем очень простой пример. Допустим, вы хотите создать конкорданс из слов, имеющихся в названиях следующих четырех книг: «Унесенные ветром», «Война и мир», «Тень ветра» и «Тени войны». (Примечание: в оригинале — Gone With the Wind, War and Peace, The Shadow of the Wind, and Shadows of War)
Алгоритм KWIC переставит слова из названий во всех возможных порядках, а затем расположит каждую перестановку по алфавиту. Результатом станет полный список ключевых слов (то есть всего, кроме предлогов, союзов и артиклей) в контексте, в котором они появились.
Система Луна KWIC быстро была нашла применение в научном сообществе. Но он знал, что она будет полезна и бизнесу. В 1958 году он написал статью для IBM Journal of Research and Development под названием «Система бизнес-аналитики» («A Business Intelligence System»). В ней он предложил систему, которая могла бы автоматически генерировать рефераты статей, извлекать из рефератов основные мысли, а затем рассылать результат соответствующим сотрудникам компании. Лун понимал, что решение проблемы информационной перегрузки означает разработку способа быстрой сортировки информации, которая не будет обременять людей лишними материалами.
The New York Times в некрологе Луна 1964 года описала его систему автореферата следующим образом:
Мистер Лун во время демонстрации взял статью о гормонах нервной системы от Scientific American из 2326 слов, вставил ее в виде магнитной ленты в компьютер IBM и нажал на кнопку. Три минуты спустя автоматическая печатная машинка набрала четыре предложения, в которых содержалась суть статьи…
Программа абстрагирования Луна сначала подсчитала частоту всех слов в статье. После отбрасывания очень распространенных слов «автореферат» обнаружил предложения, в которых несколько наиболее частотных слов встречаются вместе. Такие предложения считаются репрезентативными и помещаются в реферат. Это был чисто статистический метод, не делавший попыток «понять» слова в статье или отношения между ними. Но, как и KWIC, он показал, что компьютеры могут эффективно использоваться для организации текста в легкий для восприятия формат.
Лун покинул IBM в 1961 году и через три года умер от лейкемии. Он не дожил до того дня, когда в интернете произошли серьезные изменения. Исключая небольшой круг информационных специалистов, текстильщиков и историков, его имя мало кто помнит. Но идеи Луна живут. Сегодня хеширование играет множество ролей в управлении и защите нашей цифровой жизни. Когда вы вводите свой пароль на веб-сайте, сервер, скорее всего, сохраняет хешированную версию пароля. Когда вы взаимодействуете с сайтом при помощи безопасного протокола https или покупаете что-то с помощью биткоинов, там тоже работают хэши. Облачным сервисам, таким как Dropbox и Google Drive, хеширование помогает сделать хранение информации и обмен файлами гораздо более эффективными. В генетике и других наукоемких исследованиях хеширование существенно сокращает время, необходимое для анализа огромных объемов данных.
Хэши превратили компьютеры в «текстовые» инструменты, которые могут изъясняться при помощи букв и слов. Google Translate, Google N-gram, Google AdWords и Google Search — все они так или иначе посвящены поиску значения текста. Информационный бум в Интернете сделал автоматическое чтение и понимание [новостей и иной информации] первостепенной задачей для бизнеса, для науки, для всех. Разработка хэшей была связана с текстами и является отражением мыслей Луна о словах, предложениях, конкордансах, выдержках, индексах и дайджестах.
Это наследие Луна: он помог показать, что вычислители и вычисления — это вотчина не только математики, статистики и логики, но и языка, лингвистики и литературы. В то время это был революционный способ восприятия машин.
Технологический историк Майкл Махони назвал компьютер «машиной на стероидах»: «не просто одна вещь, а множество вещей, машина, которую можно заточить под любые цели. Даже сейчас мы склонны рассматривать компьютеры в узком смысле, как гигантские переработчики цифр, выполняющие миллионы вычислений и операций в секунду. Взгляд Ханса Петера Луна на компьютеры простирался дальше. Осознав, что компьютер многолик, он помог открыть новые, многообещающие горизонты для исследований.»
