(Этюд для программистов или заявка на Интернет-поиск нового типа)
Программа, делающая из мухи слона (далее программа МС), показала, что неориентированный граф существительных с заданным количеством букв хоть и содержит тысячи вершин, но при этом довольно «тощий» (т.е. имеет сравнительно не много ребер) и до полного графа ему далеко (см. Пример 1). Вслед за Чарлзом Уэзереллом (Charles Wetherell), автором широко известной книги «Этюды для программистов», выбрал жанр этюда, чтобы представить различные способы представления таких графов. (И сделать из этого выводы для автоматизации выбора представления – вплоть, может быть, до Интернет-поиска нового типа).
Start for word length 8
6016 words loaded from dictionary file: ..DictionaryORF3.txt
Graph was made: edges number = 871
Пример 1. Характеристики графа существительных длиной 8 букв. Читать полностью »
Добрый день.
Проблема с поиска, услуг или продукта, возникает на подавляющем большинстве сайтов. И в основной свой массе реализация подобной возможности ограничиваются поиском по точному слову, которое ввели в поисковой строке.
Если есть время, и заказчик хочет чуть большего, то гуглят реализацию наиболее популярного алгоритма (коим является «расстояние Левенштейна») и вписывают его.
В данной статье, я опишу сильно доработанный алгоритм, основанный, правда, на расстояния Левенштейна, и приведу примеры кода на C# нечеткого поиска по названиям, например: кафе, ресторанов или неких сервисов… В общем всё, что можно перечислить и имеет от одного до нескольких слов в своем составе:
«Яндекс», «Mail», «ProjectArmata», «world of tanks», «world of warships», «world of warplanes» и т.д. Читать полностью »
К написанию этой статьи сподвигли многие часы раздумий и экспериментов в области построения иерархических списков. Изначально логика обкатывалась на SQL запросах на стороне СУБД, но особенности этого языка заставили выполнить реализацию на стороне приложения PHP. Здесь я покажу как пройти от корня иерархии до каждого конечного элемента и обратно, логика реализуема на любом языке программирования.
Итак, тестовая иерархия, с которой нам предстоит работать:
В базе данных имеется самая простая таблица на самом простом MSSQL сервере, тонкости подключения опустим, наша цель — разобраться с иерархией и рекурсией.
Создадим таблицу:
CREATE TABLE [dbo].[Test](
[uid] [int] IDENTITY(1,1) NOT NULL, -- уникальное поле, автоинкрементное
[pid] [int] NULL, -- это поле указывает на элемент уровнем выше, содержит uid родителя
[name] [varchar](255) NULL,
[access] [varchar](50) NULL, -- права доступа
) ON [PRIMARY]
Поиск компетентного специалиста для удаленной реализации программных решений, способствующих более продуктивной работе в различных бизнес-сегментах, является достаточно сложной задачей. Среди многообразий мест поиска исполнителя, отдельного внимания заслуживают тематические форумы, или так называемы «Форумы программистов». Как правило, в структуре таких интернет ресурсов имеется специально отведенный раздел – «фриланс», где и происходит общение заказчика с исполнителем. После регистрации на одном из таких форумов, заказчику представляется возможность пойти двумя путями:
— выбрать исполнителя из списка фрилансеров, готовых вести разработку приложений (при условии, что такой список на форуме сформирован);
— создать топик в котором описать задачу, и ожидать ответов и предложений от фрилансеров.
По какому бы из указанных путей не совершался поиск исполнителя, так или иначе предстоит принимать решение по выбору оптимальной кандидатуры на роль исполнителя.
При работе с информацией часто возникают задачи парсинга веб-страниц. Одной из проблем в этом деле является определение похожих страниц. Хороший пример такого алгоритма — «Алгоритм шинглов для веб-документов».
Часть проекта по парсингу реализована на Node.JS, поэтому и алгоритм нужно было реализовать на нем. Реализаций на javascript или npm-пакетов я не нашел — пришлось писать свою. Читать полностью »
Сегодня мы завершаем эту серию постов, посвященных лекциям Школы анализа данных. Последний по порядку, но никак не по важности курс — «Алгоритмы и структуры данных поиска».
В этом курсе рассматриваются базовые алгоритмы и структуры данных, включая хешировани, сложность и модели вычислений, деревья поиска, B-деревья, задачи геометрического поиска, динамическую связность в графах и другое.
Лекции читает Максим Александрович Бабенко, заместитель директора отделения computer science, ассистент кафедры математической логики и теории алгоритмов механико-математического факультета МГУ им. М. В. Ломоносова, кандидат физико-математических наук. Читать полностью »
Пообщавшись с некоторыми знакомыми программистами, внезапно обнаружил, что не все знают про Ханойскую башню, а среди тех кто знает — мало кто понимает как решается эта задача.
Википедия по этому поводу пишет очень строго, по делу, и ничего не объясняет. Мол принимайте как прописную истину. Поэтому понять как она решается — сходу трудновато. А ведь задача очень простая, и между тем интересная в программировании и математически.
В статье будет много картинок. Объяснение как решать задачу рекурсивно и как она решается бинарным поиском.
В общем статья посвящается тем смелым, кто пока еще боится Ханойской башни, но хочет перестать её бояться. Читать полностью »
В посте я постарался избежать сложных дефиниций и строгих матетематических доказательств, а некоторые вещи вообще понятны интуитивно. Алгоритм удобно разбивается взаимосвязные части, поэтому и уловить принцип его работы не должно составлять труда.
Начальное описание
Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.
Суть алгоритма заключена в использование структуры данных — бора и построения по нему конечного детерминированного автомата. Важно помнить, что задача поиска подстроки в строки тривиально реализуется за квадратичное время, поэтому для эффективной работы важно, чтоб все части Ахо-Корасика ассимптотически не превосходили линию относительно длинны строк. Мы вернемся к оценке сложности в конце, а пока поближе посмотрим на составляющие алгоритма. Читать полностью »
В один прекрасный день, гуляя просторами интернета, был найден лабиринт. Интересно стало узнать его прохождение и погуляв еще по сети, я так и не нашел, рабочей программной реализации, решения лабиринта.
Вот собственно и он:
Рабочий день был скучный, настроение было отличное. Цель, средства и желание имеются. Вывод очевиден, будем проходить.
Был как-то проект у меня, который был связан с картой города. И возникла идея, что раз есть карта с маршрутами и соответствующими остановками городского транспорта, то почему бы не сделать поиск пути из пункта А в пункт Б на ней.
Так как железо, где предполагалось размещать софт, имеет крайне узкий канал интернета, то поиск должен был бы полностью осуществляться локально, то есть без привлечения мощностей сервера. Кроме того, конечно же, хотелось не потерять внимание пользователя и выдать ему результат как можно быстрее.
Где-то около часа или двух я сидел и не мог ничего придумать, а потом появилась идея, что я могу рассматривать маршрут, не как множество остановок, а как 1 точку. И если я сверну маршруты в точку, то я получу очень простой граф.
Идея показалось неплохой, и мне понравилась.
Первое что сделал это запарсил с сайтов маршруты транспорта. Далее принялся за граф.
Это оказалась не сложная задача, берем каждую остановку маршрута и смотрим, нет ли остановок любого другого маршрута в заданном нами радиусе. Радиус взял 600м (в последней версии 400м) – предполагаемое расстояние, которое человек может пройти безболезненно пешком от одной остановки до другой в случае необходимости пересадки. Вероятно, это расстояние можно сократить, скажем, до 200м, так как расстояние от одной остановки до другой на перекрестке не превышает эту дистанцию.
Итак, после всех этих манипуляций я получил граф, по которому достаточно быстро можно построить путь от одного маршрута к другому. Таким образом, получился граф, который хранит информацию о переходах с одного маршрута городского транспорта на другой, эдакий, мета-граф.
За несколько месяцев алгоритм переписывался пару раз, далее поподробнее расскажу о последней реализации.
Качество видео ужас, но как сделать получше я так и не обнаружил.
Усредненное время, затрачиваемое на выполнение шагов:
gpt — 0.009с, найти ближайшие остановки к точке клика
grt — 0.001с, найти кратчайший путь от маршрута к маршруту
apt — 0.0001с, добавляем остановки и точки поворота к нашему маршруту
all — 0.01c, суммарное время выполнения поиска пути Читать полностью »
