Page 260 - Bkhargava_-_Grokaem_algoritmy

Преобразование Фурье 259

Ага, слово встречается на страницах А и В. Выведем эти страницы в ре ­
зультатах поиска. Или предположим, что пользователь ищет слово the1-e.
Вы знаете, что это слово встречается на страницах А и С. Несложно, верно?
Это очень полезная структура данных: хеш-таблица, связывающая слова
с местами, в которых эти слова встречаются. Такая структура данных, на­
зываемая инвертированным индексом, часто используется для построения
поисковых систем. Если вас интересует область поиска, эта тема станет
хорошей отправной точкой для дальнейшего изучения.

Преобразование Фурье

Преобразование Фурье - действительно выдающийся алгоритм: вели­
колепный, элегантный и имеющий миллион практических применений.
Лучшая аналогия для преобразования Фурье приводится на сайте Better
Explained (отличный веб-сайт, на котором просто объясняется математиче­
ская теория): если у вас есть коктейль, преобразование Фурье сообщает, из
каких ингредиентов он состоит'. Или для заданной песни преобразование
разделяет ее на отдельные частоты.
Оказывается, эта простая идея находит множество практических приме­
нений. Например, если песню можно разложить на частоты, вы можете
усилить тот диапазон, который вас интересует, - скажем, усилить низкие
частоты и приглушить высокие. Преобразование Фурье прекрасно под­
ходит для обработки сигналов. Также оно может применяться для сжатия
музыки: сначала звуковой файл разбивается на составляющие. Преобразо­
вание Фурье сообщает, какой вклад вносит каждая составляющая в музыку,
что позволяет исключить несущественные составляющие. Собственно,
именно так работает музыкальный формат МРЗ!

Музыка - не единственный вид цифровых сигналов . Графический фор­
мат JPG также использует сжатие и работает по тому же принципу. Преоб­
разование Фурье также применяется для прогнозирования землетрясений
и анализа ДНК
С его помощью можно построить аналог Shazam - приложение, которое на­
ходит песни по отрывкам. Преобразование Фурье очень часто применяется
на практике. Почти наверняка вы с ним еще столкнетесь!

' Kalid, «An Interact ive Guide to t he Fottrier Transfo пn ,» Better Explained, http://mng.
Ьх/874Х.

www.trk.kg