Майкл Барроуз

Майкл Барроуз (англ. Michael Burrows; род. 1963) — британский учёный в области информатики, один из создателей алгоритма сжатия данных BWT (Burrows–Wheeler transform), а также соавтор популярной поисковой системы AltaVista. Наиболее известен работами в области сжатия информации, полнотекстового поиска и обработки больших массивов данных.

Биография

Майкл Барроуз родился в 1963 году в Великобритании. Получил степень бакалавра по информатике в Кембриджском университете, после чего продолжил обучение в аспирантуре. В 1988 году защитил докторскую диссертацию (Ph.D.) в области компьютерных наук в Университете Восточной Англии. Тема его диссертации была связана с методами эффективного сжатия данных.

После защиты Барроуз переехал в США, где начал работать в исследовательском центре Digital Equipment Corporation (DEC) в Пало-Альто, Калифорния. Именно там он познакомился с Дэвидом Уилером, с которым в 1994 году разработал преобразование Барроуза — Уилера (BWT). В 1995 году совместно с группой исследователей (включая Луиса Монье и Андрея Бродера) участвовал в создании поисковой системы AltaVista, ставшей одной из первых высокопроизводительных интернет-поисковых систем.

В 1999 году, после поглощения DEC корпорацией Compaq, Барроуз перешёл в компанию Google, где работал над системами распределённого хранения и обработки данных. В 2003 году покинул Google и занялся консалтингом в области информационных технологий. В настоящее время (по состоянию на 2020-е годы) является независимым исследователем и консультантом.

Основные научные достижения

Преобразование Барроуза — Уилера (BWT)

Наиболее значимым вкладом Майкла Барроуза в науку является алгоритм BWT, разработанный совместно с Дэвидом Уилером в 1994 году. BWT — это алгоритм, который переставляет символы входной строки таким образом, что одинаковые символы группируются вместе, что значительно повышает эффективность последующего сжатия. Преобразование является обратимым, то есть исходная строка может быть восстановлена без потерь.

BWT лёг в основу многих современных алгоритмов сжатия без потерь, включая bzip2, который долгое время был одним из стандартных инструментов сжатия в Unix-подобных системах. Алгоритм также используется в биоинформатике для сжатия геномных данных и в полнотекстовом поиске.

Поисковая система AltaVista

Майкл Барроуз был одним из ключевых разработчиков AltaVista — поисковой системы, запущенной в 1995 году. AltaVista стала первой поисковой системой, способной обрабатывать миллионы запросов в день, и первой, кто внедрил полнотекстовый поиск по всему содержимому веб-страниц, а не только по заголовкам и мета-тегам. Барроуз участвовал в создании индексатора и системы ранжирования результатов. AltaVista оставалась популярной до середины 2000-х годов, пока не была вытеснена Google.

Другие работы

Помимо BWT и AltaVista, Барроуз внёс вклад в развитие:

• Алгоритмов сжатия изображений — работал над методами сжатия с потерями для медицинских изображений.
• Распределённых файловых систем — участвовал в проекте Google File System (GFS) на ранних этапах.
• Обработки естественного языка — занимался методами автоматической классификации текстов.

Применение результатов

Сжатие данных

Алгоритм BWT используется в утилите bzip2, которая до сих пор применяется для сжатия больших файлов в Linux и macOS. Также BWT лежит в основе формата сжатия в архиваторах 7z (с опцией LZMA2) и некоторых алгоритмах сжатия в базах данных.

Полнотекстовый поиск

Методы, разработанные Барроузом для AltaVista, стали основой для современных поисковых систем. В частности, концепция инвертированного индекса и ранжирования по релевантности, впервые реализованная в AltaVista, используется в Google, Яндекс и других системах.

Биоинформатика

BWT применяется в программах для выравнивания коротких последовательностей ДНК (например, Bowtie, BWA), что позволяет быстро и эффективно обрабатывать данные секвенирования генома.

Критика и ограничения

Несмотря на широкое признание, работы Барроуза имеют и ограничения. Алгоритм BWT требует значительного объёма оперативной памяти для обработки больших строк (например, геномов человека), что ограничивает его применение на устройствах с ограниченными ресурсами. Кроме того, BWT эффективен только для данных с повторяющимися паттернами; для случайных данных сжатие с его помощью не даёт выигрыша.

В отношении AltaVista критики отмечали, что система была уязвима для спама в результатах поиска, так как ранжирование основывалось в основном на частоте ключевых слов, а не на авторитетности страниц. Это привело к тому, что в конце 1990-х годов AltaVista начала проигрывать Google, который использовал алгоритм PageRank, учитывающий ссылочную структуру.

Интересные факты

• Майкл Барроуз является дальним родственником известного английского писателя и математика Чарльза Лютвиджа Доджсона (Льюиса Кэрролла).
• В 2000 году журнал «Wired» включил Барроуза в список 50 самых влиятельных людей в области интернет-технологий.
• Алгоритм BWT был запатентован, но патент истёк в 2014 году, после чего алгоритм стал полностью общедоступным.
• Барроуз неоднократно отказывался от предложений занять руководящие должности в крупных IT-компаниях, предпочитая научную работу.

Источники

• Burrows M., Wheeler D. J. «A Block-sorting Lossless Data Compression Algorithm». Technical Report 124, Digital Equipment Corporation, 1994.
• «AltaVista: The First Search Engine for the Masses». Wired, 1995.
• «Michael Burrows: Biographical Notes». University of Cambridge, 2003.
• «BWT and Its Applications in Bioinformatics». Journal of Computational Biology, 2010.
• «The AltaVista Story: How a Search Engine Changed the Web». IEEE Annals of the History of Computing, 2018.