В первой части статьи мы рассмотрели универсальный автомат Левенштейна — мощный инструмент для фильтрации слов, отстоящих от некоторого слова W на расстояние Левенштейна не более заданного. Теперь пришло время изучить способы применения этого инструмента для эффективного решения задачи нечеткого поиска в словаре.
Нечеткий поиск строк является весьма дорогостоящей в смысле вычислительных ресурсов задачей, особенно если вам необходима высокая точность получаемых результатов. В статье описан алгоритм нечеткого поиска в словаре, который обеспечивает высокую скорость поиска при сохранении 100% точности и сравнительно низком потреблении памяти. Именно автомат Левенштейна позволил разработчикам Lucene повысить скорость нечеткого поиска на два порядка
Читать полностью »
Доброго времени суток.
В той или иной степени интересуюсь алгоритмами. Наткнулся на свежую статью
«Поиск повторений в двумерном массиве, или вычислительная сложность на примере» http://habrahabr.ru/post/141258/. Автор стати,Singerofthefall, довольно интересно рассказывает про решение задачи и оптимизации алгоритма. Очень интересно. Однако, по моему мнению, прежде всего необходимо было определить не алгоритм, а инструмент которым будет решаться задача. И вот инструмент был выбран неправильный, отсюда вся сложность и оптимизации.
Для решения задачи автора более всего подходили инструменты БД, соответственно и надо было их использовать.
Читать полностью »
Доброго времени суток, уважаемое читатели.
Когда я учился в институте на втором или третьем курсе (то есть, в общем, не так и давно), был у меня, помимо прочих, предмет под названием «алгоритмы и структуры данных». Рассказывали там, однако, не только про сами алгоритмы и структуры, но и о таком понятии, как «вычислительная сложность». Признаюсь, тогда это меня не очень заинтересовало.
«Наверняка заморачиваться с исследованием алгоритма на пространственную и временную сложность нужно только при разработке либо очень высокопроизводительных/высоконагруженных систем, либо при работе с действительно большими объемами данных», — примерно такие мысли посещали меня (да и, наверное, не только меня) тогда.
Однако недавно мне пришлось сильно изменить свое мнение из-за простой, казалось бы, задачи.
Читать полностью »
