Техническое: Алгоритмические подходы

Чем дальше тем больше я убеждаюсь что все существующие подходы к оптимизации алгоритмов и повышению производительности и точности алгоритмов можно свести к 3 разным подходам.

1. Технологический

Подход по оптимизации «в лоб». Переписать алгоритм на ассемблер, взять другой компилятор, запустить расчёты в сети распределённой сети, задействовать более быстрые процессоры, диски и память, задействовать графический процессор и так далее. В некоторых случаях этот подход работает — например, в случае использования графического процессора для взлома паролей или в таких проектах как Seti@Home.

2. Математический

Вместо медленного алгоритма придумывается более быстрые вариации. Вместо пузырьковой сортировки используется быстрая сортировка. Вместо SVM используется SVM-light. Вместо полного полного пересчёта PageRank’а по хостграфу, он рассчитывается инкрементально. Вместо алгоритмов упаковки LZA использовать LZO или LZMA и так далее.

3. Смысловой

Слово «семантический» уже набило оскомину, да ему тут, на мой взгляд, и не место. Смысловой подход основывается на предварительном понимании того с чем же мы имеем дело и на последующем преобразовании алгоритма или среды в которой он работает таким образом чтобы учитывать выявленные особенности.

Примером смыслового подхода можно привести алгоритмы сжатия заточенные под определённые форматы файлов — запускаемые, графические и музыкальные. Построение сервисов рекомендаций которые используют накопленные массивы данных для уточнения своей работы. Даже такое обыденное явление как полнотекстовые индексы для файлов и баз данных можно отнести к смысловым подходам, поскольку цель создания этих индексов в оптимизированном промежуточном звене между поиском и первичными данными.

Из всех этих подходов меня лично интересовал и интересует третий, смысловой подход. Он далеко не всегда оказывается проще и быстрее остальных по началу, но далее результаты становятся весьма ощутимыми.

Например, в ЖЖ в ru_ir вплыла интересная задачка с прогоном слова по SQL базе английских слов с получением выборки слов по заданному расстоянию Левенштайна. Фактически это исправление опечаток. Учитывая что как раз сейчас я размышлял над схожей задачей прогона прогоном слова по миллионам регулярных выражений, то эта задачка мне показалась любопытной.

Но, в чём фокус, несмотря на то что я знаю что определённо есть математические алгоритмы решения этой задачи — у неё есть также и смысловые решения которые могут позволить математические алгоритмы ускорить.

Навскидку, приведу несколько подходов :

1. Построение специализированных индексов.

Поскольку мы оперируем в контексте статического набора данных в виде базы слов и простого алгоритма рассчитывающего расстояния Левенштайна, то задача принципиально может быть решена построением специализированных побуквенных и иных индексов позволяющих сократить число переборов для рассматриваемого слова.

В данном случае используются особенности выборки, особенности алгоритма и метрики рассматриваемого слова.

Простейший пример — это выборка из миллиона слов может быть существенно сокращена если ввести ограничения на длину слова по максимальному его вероятному изменению длины. Если слово длиной 5 букв, а требуемое расстояние Левенштейна 2, то длина вариантов находится между 3 и 7 буквами, соответственно все остальные слова можно отсеять ещё на этапе формирования запроса выборки слов для сравнения.

Это совсем очевидное, я думаю.

2. Анализ типовых опечаток.

Люди опечатываются не по расстоянию Левенштейна и пропускают не абы какие буквы, а вполне по фиксированным правилам специфики языка и расположения клавиш на клавиатуре. Путём сбора статистики опечаток и последующего их анализа алгоритм расчёта расстояния Левенштейна можно изменить под учёт наиболее возможных вариантов. Да, схожего решения можно добиться используя таблицы n-gram, но есть нюансы.

3. Предварительные расчёты

Этот подход всё дальше от смыслового подхода, но всё ещё в пределах преобразования датасетов. Особенность ситуации заключается в том что мы проверяем слово по статической выборке данных. Ещё раз — выборка статическая и в крайнем случае редко пополняемая. Чтобы решить задачу в лоб достаточно написать формулу которая бы рассчитывала для выбранного слова все варианты его изменения в пределах заданного расстояния Левенштейна после чего прогнать эту формулу по всему миллиону слов и получить все возможные варианты, их будет невероятно много, зато скорость поиска выбранного слова будет более чем быстрой. Это практически то же самое что хранение базы n-gram, только объёмы больше.

4. Построение смысловой модели опечаток

В этом случае мы рассматриваем не расчёт расстояния Левенштейна, а проблему исправления опечаток от корня — их возникновения. Для этой задачи строится онтологическая (смысловая) модель зависимости инструментов ввода информации, типов опечаток, наиболее вероятных опечаток. Модель корректируется собранными статистическими данными после чего вместо расчёта расстояния Левенштейна используется иная функция учитывающая природу происхождение ошибок.

Частично этот механизм используется в при анализе выборок слов по базам n-gram, но базы n-gram это заход с другой стороны, в данном случае корректировка вероятностей происходит ещё на периоде анализа искомого слова. Этот подход пересекается с анализом типовых отпечаток.

Мне лично интересны именно подходы основанные на понимании природы того с какой именно информацией мы работаем и заменой расчётных алгоритмов — алгоритмами анализа логики и сочетаемости решений.

И ряд соображений основанных на наводящих вопросах.

— Что можно сделать с выборкой для ускорения и упрощения расчётов расстояния Левенштейна?

— Нужно ли это делать со всей выборкой?

— Каково распределение расстояний Левенштейна между вариантами одного слова для фиксированного расстояния Левенштейна?

— Может ли это помочь хранение и использование промежуточных расчётов?

— Есть ли наборы внешних данных могущие помочь с ускорением расчётов?

Материалы по теме:

About This Author

Яндекс.Метрика