Рубрика «алгоритмы поиска»

Мы уже рассказывали вам об интересных статистиках текстов, делали обзор статей применений автокодировщиков в анализе текстов, удивляли нашими свежими алгоритмами поиска переводных заимствований и парафраза. Я решил продолжить нашу корпоративную традицию и, во-первых, начать статью с «Т», а во-вторых, рассказать:

  • как быстро найти абзац текста среди сотен миллионов статей;
  • во что превращается документ после загрузки в систему Антиплагиат, и что с этим делать дальше;
  • как формируется отчет, который почти никто не смотрит, а стоило бы;
  • как проиндексировать не все, но достаточно.

Так устроен поиск заимствований в Антиплагиате - 1
Читать полностью »

В этой статье рассматриваются сходства и различия двух подходов к решению алгоритмических задач: динамического программирования (dynamic programing) и принципа «разделяй и властвуй» (divide and conquer). Сравнение будем производить на примере, соответственно, двух алгоритмов: бинарного поиска (как быстро найти число в отсортированном массиве) и расстояния Левенштейна (как преобразовать одну строку в другую с минимальным количеством операций).

Хочу сразу заметить, что данное сравнение и объяснение не претендует на исключительную правильность. И возможно даже некоторые преподаватели в университетах захотели бы меня отчислить :) Эта статья является всего-лишь моей персональной попыткой разложить себе же все по полочками и понять что такое динамическое программирование и каким образом в нем участвует принцип «divide and conquer».

Итак, приступим…

image
Читать полностью »

Наступил новый учебный год. Студенты получили расписание занятий и стали задумываться о пьянках-гулянках-девушках-гитарах будущей сессии. Написание курсовых, дипломов, статей и диссертаций не за горами. А значит, грядут и анализ текстов на наличие заимствований, и отчеты о проверке, и прочая головная студенческая и администраторская боль. И у сотен тысяч людей (без шуток – мы посчитали!) уже возникает закономерный вопрос – как же обмануть «Антиплагиат». В нашем случае практически все способы обмана так или иначе связаны с искажениями текста. Мы уже научили «Антиплагиат» обнаруживать текст, «искаженный » с помощью перевода с английского на русский ( мы уже писали об этом в первой статье нашего корпоративного блога). Сегодня речь пойдет о том, как обнаруживать самый эффективный, хотя и трудоемкий способ искажения текста – парафраз.

«Трое в лодке, нищета и собаки», или как Антиплагиат ищет парафраз - 1

Читать полностью »

Здравствуйте, уважаемые читатели.

Регулярные выражения — хорошо известная вещь, которая используется в разнообразных проектах, чаще всего, для не очень сложных случаев разбора структурированных текстов. Занимаясь, на первый взгляд, такой несколько иной задачей, как обратный синтез моделей программ (когда есть код программы, порожденный автоматически некоторой системой по некоторой блочной модели решаемой задачи, и необходимо по этому коду воссоздать исходную модель), а также синтезом моделей программ по текстовому описанию задачи, я столкнулся с проблемой анализа текстов, а точнее — идентификации фрагментов текста некоторым настраиваемым шаблонам. Хотелось получить достаточно простое и гибкое (настраиваемое) решение. Регулярные выражения, с ходу, такими не казались, поскольку даже в такой простой задаче, как проверка слова по словарю, требовала, к сожалению, тщательного перечисления всех вариантов в этом выражении. Да и дерево синтаксического разбора они не строили. Однако, их явно можно было улучшить. Об этом и пойдет речь.
Читать полностью »

В нашей первой статье в корпоративном блоге компании Антиплагиат на Хабре я решил рассказать о том, как работает алгоритм поиска переводных заимствований. Несколько лет назад возникла идея сделать инструмент для обнаружения в русскоязычных текстах переведенного и заимствованного текста из оригинала на английском языке. При этом важно, чтобы этот инструмент мог работать с базой источников в миллиарды текстов и выдерживать обычную пиковую нагрузку Антиплагиата (200-300 текстов в минуту).

Трудности перевода: как найти плагиат с английского языка в русских научных статьях - 1"

В течение 12 лет своей работы сервис Антиплагиат обнаруживал заимствования в рамках одного языка. То есть, если пользователь загружал на проверку текст на русском, то мы искали в русскоязычных источниках, если на английском, то в англоязычных и т. д. В этой статье я расскажу об алгоритме, разработанном нами для обнаружения переводного плагиата, и о том, какие случаи переводного плагиата удалось найти, опробовав это решение на базе русскоязычных научных статей.Читать полностью »

Arrays, Collections: Алгоритмический минимум

Массивы и списки

Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники JDK 7.80.
Читать полностью »

(Этюд для программистов или заявка на Интернет-поиск нового типа)

Графы большие и маленькие: интеллектуальное решение проблемы выбора представления - 1

Программа, делающая из мухи слона (далее программа МС), показала, что неориентированный граф существительных с заданным количеством букв хоть и содержит тысячи вершин, но при этом довольно «тощий» (т.е. имеет сравнительно не много ребер) и до полного графа ему далеко (см. Пример 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. Здесь я покажу как пройти от корня иерархии до каждого конечного элемента и обратно, логика реализуема на любом языке программирования.

Итак, тестовая иерархия, с которой нам предстоит работать:

image

В базе данных имеется самая простая таблица на самом простом 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]

Читать полностью »

Поиск компетентного специалиста для удаленной реализации программных решений, способствующих более продуктивной работе в различных бизнес-сегментах, является достаточно сложной задачей. Среди многообразий мест поиска исполнителя, отдельного внимания заслуживают тематические форумы, или так называемы «Форумы программистов». Как правило, в структуре таких интернет ресурсов имеется специально отведенный раздел – «фриланс», где и происходит общение заказчика с исполнителем. После регистрации на одном из таких форумов, заказчику представляется возможность пойти двумя путями:

— выбрать исполнителя из списка фрилансеров, готовых вести разработку приложений (при условии, что такой список на форуме сформирован);
— создать топик в котором описать задачу, и ожидать ответов и предложений от фрилансеров.

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

Читать полностью »