В задаче по «упаковке цветов графа» (в оригинале packing coloring, — прим. пер.) спрашивается, сколько чисел необходимо для заполнения бесконечной сетки так, чтобы идентичные числа никогда не оказывались слишком близко друг к другу. И новый арифметический эксперимент с использованием компьютера даёт на удивление простой ответ.
Сколько чисел потребуется для заполнения бесконечной сетки так, чтобы расстояние между вхождениями одного числа было больше самого этого числа?Читать полностью »
Поворачивая, переставляя и опуская вниз заранее заданную последовательность фигур, Tetris Printer Algorithm использует механику «Тетриса» для генерации произвольных битовых изображений.
Алгоритм построчно преобразует пиксели исходного изображения в квадраты поля «Тетриса», двигаясь снизу вверх. Для генерации отдельного квадрата алгоритм собирает структуру, состоящую из прямоугольной области, полностью опирающейся на один квадрат под ней. После завершения сборки прямоугольной области её строки очищаются, оставляя под собой один квадрат. Вот три примера такого поведения.
Как показано ниже, алгоритм также может генерировать одной структурой несколько квадратов.
В процессе построения строки все квадраты, созданные данным способом, должны на что-то опираться. На показанных выше изображениях сгенерированные квадраты стоят на полу игрового поля. Однако если произвольная строка содержит дырки, то она не сможет обеспечить опору, необходимую для построения строки над ней. Алгоритм решает эту проблему, создавая поверх строки с дырками плоскую платформу. В показанной ниже анимации построенная поверх строки платформа состоит из одного красного квадрата. Платформа — это временная структура, и вставка последней фигуры удаляет её.
Читать полностью »
Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.
Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.
Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Читать полностью »
Мы уже рассказывали вам об интересных статистиках текстов, делали обзор статей применений автокодировщиков в анализе текстов, удивляли нашими свежими алгоритмами поиска переводных заимствований и парафраза. Я решил продолжить нашу корпоративную традицию и, во-первых, начать статью с «Т», а во-вторых, рассказать:
В этой статье рассматриваются сходства и различия двух подходов к решению алгоритмических задач: динамического программирования (dynamic programing) и принципа «разделяй и властвуй» (divide and conquer). Сравнение будем производить на примере, соответственно, двух алгоритмов: бинарного поиска (как быстро найти число в отсортированном массиве) и расстояния Левенштейна (как преобразовать одну строку в другую с минимальным количеством операций).
Хочу сразу заметить, что данное сравнение и объяснение не претендует на исключительную правильность. И возможно даже некоторые преподаватели в университетах захотели бы меня отчислить :) Эта статья является всего-лишь моей персональной попыткой разложить себе же все по полочками и понять что такое динамическое программирование и каким образом в нем участвует принцип «divide and conquer».
Итак, приступим…
Наступил новый учебный год. Студенты получили расписание занятий и стали задумываться о пьянках-гулянках-девушках-гитарах будущей сессии. Написание курсовых, дипломов, статей и диссертаций не за горами. А значит, грядут и анализ текстов на наличие заимствований, и отчеты о проверке, и прочая головная студенческая и администраторская боль. И у сотен тысяч людей (без шуток – мы посчитали!) уже возникает закономерный вопрос – как же обмануть «Антиплагиат». В нашем случае практически все способы обмана так или иначе связаны с искажениями текста. Мы уже научили «Антиплагиат» обнаруживать текст, «искаженный » с помощью перевода с английского на русский ( мы уже писали об этом в первой статье нашего корпоративного блога). Сегодня речь пойдет о том, как обнаруживать самый эффективный, хотя и трудоемкий способ искажения текста – парафраз.
Здравствуйте, уважаемые читатели.
Регулярные выражения — хорошо известная вещь, которая используется в разнообразных проектах, чаще всего, для не очень сложных случаев разбора структурированных текстов. Занимаясь, на первый взгляд, такой несколько иной задачей, как обратный синтез моделей программ (когда есть код программы, порожденный автоматически некоторой системой по некоторой блочной модели решаемой задачи, и необходимо по этому коду воссоздать исходную модель), а также синтезом моделей программ по текстовому описанию задачи, я столкнулся с проблемой анализа текстов, а точнее — идентификации фрагментов текста некоторым настраиваемым шаблонам. Хотелось получить достаточно простое и гибкое (настраиваемое) решение. Регулярные выражения, с ходу, такими не казались, поскольку даже в такой простой задаче, как проверка слова по словарю, требовала, к сожалению, тщательного перечисления всех вариантов в этом выражении. Да и дерево синтаксического разбора они не строили. Однако, их явно можно было улучшить. Об этом и пойдет речь.
Читать полностью »
В нашей первой статье в корпоративном блоге компании Антиплагиат на Хабре я решил рассказать о том, как работает алгоритм поиска переводных заимствований. Несколько лет назад возникла идея сделать инструмент для обнаружения в русскоязычных текстах переведенного и заимствованного текста из оригинала на английском языке. При этом важно, чтобы этот инструмент мог работать с базой источников в миллиарды текстов и выдерживать обычную пиковую нагрузку Антиплагиата (200-300 текстов в минуту).
"
В течение 12 лет своей работы сервис Антиплагиат обнаруживал заимствования в рамках одного языка. То есть, если пользователь загружал на проверку текст на русском, то мы искали в русскоязычных источниках, если на английском, то в англоязычных и т. д. В этой статье я расскажу об алгоритме, разработанном нами для обнаружения переводного плагиата, и о том, какие случаи переводного плагиата удалось найти, опробовав это решение на базе русскоязычных научных статей.Читать полностью »
Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники JDK 7.80.
Читать полностью »
