Алгоритмы *

Именно так называлась работа, представленная мной на Балтийском научно-инженерном конкурсе, и принёсшая мне очаровательную бумажку с римской единичкой, а также новенький ноутбук.

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

Введение

Сегодня мне хотелось бы рассказать о методе эффективного вычисления суммы элементов массива с l-того по r-тый. Самый известный из таких методов — это древо отрезков(RSQ), но он довольно сложен в написании и понимании, поэтому я хочу предложить более простой, но менее эффективный — Sqrt-декомпозиция.

Формальная постановка задачи

Дан массив A[0..n-1], нам нужно научиться эффективно вычислять сумму элементов A[l..r] для произвольных l и r, не выходящих за пределы массива. Без ограничения общности будем считать, что l <= r.

Эта статья представляет собой описание компонента HexaPath, реализующего поиск пути по алгоритму А* в гексагональной сетке. В сети мной было найдено большое количество описаний алгоритма на примере квадратной сетки и некоторое количество реализаций, но ни одного упоминания о шестиугольной сетке. И я написал свою реализацию. Выкладываю исходники. Вдруг кому-нибудь понадобится это, а писать самому будет лень.

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

Решил продолжить цикл статей по стеганографии, на хабре уже был рассмотрен примитивный алгоритм LSB. Решил написать о методе Куттера-Джордана-Боссена (его также называют методом «креста»), который применяется для встраивания информации в изображения.

В этой статье я расскажу про достаточно важную в информатике и теории автоматов тему – минимизацию булевых функций. Этим вопросом задавались пожалуй все, кто изучал или сталкивался с данной тематикой.

Существует немало методов, однако наибольший интерес представляют те, которые могут быть формализованы, а соответственно запрограммированы без особых сложностей. А также работающие с произвольными булевыми выражениями. Идеального метода не придумано, все имеют те или иные слабые и сильные качества. Я остановлюсь на так называемом методе Гиперкубов — Методе Квайна.

Метод, к сожалению, применим только для Совершенных ДНФ, поэтому при большом числе переменных использование затруднено гигантским выражением СДНФ.

Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.

Категорически приветствую! В прошлый раз я писал о вероятностном алгоритме определения принадлежности элемента множеству, в этот раз будет про вероятностную оценку похожести. Не надо большого ума, чтобы додуматься до следующего показателя схожести двух множеств А и Б:



То есть, количество элементов в пересечении делённое на количество элементов в объединении. Эта оценка называется коэффициентом Жаккара (Jaccard, поэтому «J»), коэффициент равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.

В «Занимательной арифметике» известного популяризатора наук Якова Исидоровича Перельмана в конце первой главы я нашел пример следующих «Арифметических курьезов»:

100 = 1+2+3+4+5+6+7+8*9
100 = 12+3-4+5+67+8+9
100 = 12-3-4+5-6+7+89
100 = 123+4-5+67-89
100 = 123-45-67+89

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

В первой части нашей темы мы рассмотрели решение задачи static RMQ за (O(nlogn), O(1)). Теперь мы разберёмся со структурой данных, называемой дерево отрезков, или интервалов (в англоязычной литературе – segment tree или interval tree). С помощью неё можно решать dynamic RMQ за (O(n), O(logn)).

Определение

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

Каждому листу будет соответствовать элемент массива с номером, равным порядковому номеру листа в дереве. А каждой вершине, не являющейся листом, будет соответствовать отрезок из элементов массива соответствующих листам-потомкам этой вершины.

Сегодня на Хабре появилась очень интересная статья, о поиске минимального (максимального) значения на отрезке в массиве. Так как статья оказалось интересной и популярной, я решил с вами поделиться ещё одним алгоритмом поиска в массиве некоторых «специальных» значений.

Введение

Задача RMQ весьма часто встречается в спортивном и прикладном программировании. Удивительно, что на Хабре ещё никто не упомянул эту интересную тему. Попробую восполнить пробел.

Аббревиатура RMQ расшифровывается как Range Minimum (Maximum) Query – запрос минимума (максимума) на отрезке в массиве. Для определённости мы будем рассматривать операцию взятия минимума.

Пусть дан массив A[1..n]. Нам необходимо уметь отвечать на запрос вида «найти минимум на отрезке с i-ого элемента по j-ый».



Рассмотрим в качестве примера массив A = {3, 8, 6, 4, 2, 5, 9, 0, 7, 1}.
Например, минимум на отрезке со второго элемента по седьмой равен двум, то есть RMQ(2, 7) = 2.

В голову приходит очевидное решение: ответ на каждый запрос будем находить, просто пробегаясь по всем элементам массива, лежащим на нужном нам отрезке. Такое решение, однако, не является самым эффективным. Ведь в худшем случае нам придётся пробежаться по O(n) элементам, т.е. временная сложность этого алгоритма – O(n) на один запрос. Однако, задачу можно решить эффективнее.

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

Часто довольно трудно найти в базе нетипичную фамилию, например:

— Леха, поищи в нашей базе Адольфа Швардсенеггера,
— Шворцинегира? Нет такого!

В этом случае использование фонетических алгоритмов (особенно в сочетании с алгоритмами нечеткого сопоставления) может значительно упростить задачу.

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

В этой статье я рассмотрю наиболее известные алгоритмы, такие как Soundex, Daitch-Mokotoff Soundex, NYSIIS, Metaphone, Double Metaphone, русский Metaphone, Caverphone.

Недавно я делал простой рейтрейсер 3-х мерных сцен. Он был написан на JavaScript и был не очень быстрым. Ради интереса я написал рейтрейсер на C и сделал ему режим 4-х мерного рендеринга — в этом режиме он может проецировать 4-х мерную сцену на плоский экран. Под катом вы найдёте несколько видео, несколько картинок и код рейтрейсера.

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

• БИНС — бесплатформенная инерциальная навигационная система
• БПЛА — беспилотный летательный аппарат
• ОЧ — ось чувствительности датчика

Речь в статье пойдет о навигационной системе, в которой ОЧ датчиков ориентированы неортогонально, т.е. расположены под некоторым, ненулевым, углом к осям системы координат, связанной с БПЛА. Особенность таких БИНС в том, что по информации от каждого из датчиков можно получить значения всех трех компонент угловой скорости (для гироскопов) и линейного ускорения (для линейных акселерометров) объекта.
Статья написана как дополнение к Строим мультикоптер, часть вторая. Целью является описание одного из способов борьбы с дрейфом нуля в дешевых датчиках.

Приветствую!
Наверное, многие уже слышали о проекте распределенных вычислений по поиску больших простых чисел GIMPS (Great Internet Mersenne Prime Search). На хабре уже проскакивала информация о проекте и его результатах.

Если вы из тех, кто любит разглядывать 12мегабайтные числа в поисках интересностей и просто с целью медитации, не боитесь всё время видеть 100 процентную загрузку CPU (зная, что программа работает с приоритетом «ниже среднего» и практически не влияет на быстродействие машины), а так же хотите внести свой вклад в развитие математики, то прошу под кат.

Программу, решающую головоломку «пентамино» я написал в качестве одной из первых своих программ. Дело было давно, программа как-то работала, всех вариантов найти не успела… В общем, написал и забыл.

На днях, наводя порядок на столе, решил, что пора бы убрать валяющуюся без дела головоломку «Mini Bedlam Cube»:



А перед этим ее неплохо бы собрать. Головоломка состоит из 13 фигур — 12 составлены из 5 кубиков, одна из четырех; шесть фигур симметричные, три из них — плоские. Фигуры нужно уложить в коробку 4x4x4. Надо сказать, что периодически я вспоминал об этих кубиках, пытался с ними справиться, но так ничего и не вышло. Поэтому возникла идея — написать программу, решающую головоломку, причем затратить как можно меньше усилий, а потом решить старый вопрос: что выгоднее — перебирать фигуры или клетки, и в каком порядке.

Введение

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

Основные операции в деревьях выполняются за время пропорциональное его высоте. Сбалансированные деревья минимизируют свою высоту (к примеру, высота бинарного сбалансированного дерева с n узлами равна log n). Большинство знакомо с такими сбалансированными деревьями, как «красно-черное дерево», «AVL-дерево», «Декартово дерево», поэтому не будем углубляться.

В чем же проблема этих стандартных деревьев поиска? Рассмотрим огромную базу данных, представленную в виде одного из упомянутых деревьев. Очевидно, что мы не можем хранить всё это дерево в оперативной памяти => в ней храним лишь часть информации, остальное же хранится на стороннем носителе (допустим, на жестком диске, скорость доступа к которому гораздо медленнее). Такие деревья как красно-черное или Декартово будут требовать от нас log n обращений к стороннему носителю. При больших n это очень много. Как раз эту проблему и призваны решить B-деревья!

B-деревья также представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Но, в отличие от остальных деревьев, они созданы специально для эффективной работы с дисковой памятью (в предыдущем примере – сторонним носителем), а точнее — они минимизируют обращения типа ввода-вывода.

Судоку — популярная головоломка, основной задачей которой является размещение цифр в правильном порядке.

Игровое поле представляет собой квадрат 9х9 клеток. Клетки сгруппированы в девять сегментов 3х3. В каждой клетке может быть записана цифра от одного до девяти. Основным правилом судоку является то, что цифра не может повторяться в строке, столбце и сегменте.

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

Эта небольшая заметка не претендует на звание статьи.

В прошлый раз я сравнивал LuaJIT 2.0 Beta 5 и JavaScript в различных браузерах на примере простого рейтрейсера. Результат сравнения: JavaScript в Chrome набрал 20,000 RPS и занял 1-ое место, а LuaJIT — 5,000 RPS и последнее место.

С выходом LuaJIT 2.0 Beta 6 ситуация изменилась: Lua легко вышел на первое место обогнав Chrome. Посмотрим как это получилось.