Max Home IndustryВ мире с таким большим количеством текстовых / символьных данных, которые необходимо генерировать, читать, хранить и искать, строковые алгоритмы становятся все более важными. Новый сложный короткий курс на платформе Coursera, открывшийся сегодня, кажется хорошим введением.
Если вы думаете о строковых алгоритмах только как о поиске подстроки или объединении строк, вам придется подумать еще раз. Есть проблемы со строками, которые намного сложнее, чем поиск фиксированной строки внутри другой. Например, найдите самое длинное совпадение между двумя строками независимо от того, где оно начинается, найдите самый длинный повтор в строке и так далее. Это достаточно легко сделать с помощью исчерпывающего поиска, но не требуется много времени, чтобы строка стала настолько большой, что время, которое занимают такие алгоритмы грубой силы, будет слишком долгим. Например, рассмотрим задачу работы с геномом человека, закодированным в виде строки символов размером 1,5 ГБ.
Алгоритмы на строках — это часть специализации по структурам данных и алгоритмам, которую мы рассмотрели, когда эта специализация была запущена в марте, см. Новая специализация Coursera Core CS. Серия состоит из пяти классов, из которых это четвертый, и Capstone Project.
Название Capstone, которое начинается в сентябре, — «Сборка геномов и поиск мутаций, вызывающих заболевания», скорее объясняет, почему первые строковые алгоритмы, с которыми вы встретитесь в этом 4-недельном модуле, мотивированы проблемами биоинформатики (секвенирование генома).
Неделя 1 курса посвящена деревьям суффиксов, и вот как описание курса вводит список мероприятий:
Как бы вы искали самый длинный повтор в строке за ЛИНЕЙНОЕ время? В 1973 году Питер Вайнер предложил удивительное решение, основанное на суффиксных деревьях, ключевой структуре данных в сопоставлении с образцом. Его алгоритм произвел такое впечатление на компьютерных ученых, что они назвали его «Алгоритмом года». В этом уроке мы рассмотрим некоторые ключевые идеи сопоставления с образцом, которые — через серию проб и ошибок — приведут нас к суффиксным деревьям.
На неделе 2 он переходит к преобразованию Барроуза-Уиллера и массивам суффиксов:
Хотя ТОЧНОЕ сопоставление с образцом с суффиксными деревьями происходит быстро, неясно, как использовать суффиксные деревья для ПРИБЛИЗИТЕЛЬНОГО сопоставления с образцом. В 1994 году Майкл Берроуз и Дэвид Уиллер изобрели гениальный алгоритм сжатия текста, который теперь известен как преобразование Барроуза-Уиллера. Они ничего не знали о геномике и даже представить себе не могли, что спустя 15 лет их алгоритм станет рабочей лошадкой для биологов, ищущих геномные мутации. Но какое отношение сжатие текста имеет к сопоставлению с образцом ??? В этом уроке вы узнаете, что судьбу алгоритма часто трудно предсказать — его приложения могут появиться в области, которая не имеет ничего общего с первоначальным планом его изобретателей.
В последние две недели курс посвящен изучению алгоритмических задач с двухнедельным заданием по программированию, охватывающим обе недели, тогда как в первые две недели каждая имела отдельное задание, которое нужно было выполнить на широком выборе языков программирования, хотя справочные решения только доступно на C ++, Java и Python 3.
Хотя «Алгоритмы на строках» — четвертый в серии курсов, вы, конечно, можете использовать его как отдельный класс. Если вы хотите пройти полную специализацию, стоит отметить, что на этой неделе снова был запущен первый из модулей.