• Суффиксный массив — удобная замена суффиксного дерева

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

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

      Читать дальше →
    • Сегментация изображений методом квантилей

      image Сегментацией называется присвоение пикселям изображения меток так, что области, обладающие сходными в определённом смысле свойствами, имеют одинаковые метки. Также сегментацией порой называют поиск проекции объекта на изображении. Данный топик расскажет о простом, но эффективном методе поиска проекции объекта, называемом методом квантилей. Указана область применимости метода и приведены некоторые модификации, повышающие эффективность.
      Читать дальше →
    • Опыт спасения кластера Cassandra

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

      Читать дальше →
    • История одного бага

        Буквально вчера мне пришлось разбираться с одним очень тонким и специфичным багом. Баг оказался фичей, которая спотыкалась о другой баг. В ходе изучения проблемы я был вынужден изучить несколько особенностей Debian, угробить 4 часа времени и получить массу опыта.

        В слегка прилизанном виде привожу хронологию событий, надеюсь, кому-то будет интересно посмотреть, как работают системные администраторы.

        Предыстория

        В ходе разворачивания стенда для экспериментов из нескольких идентичных серверов захотелось иметь возможность запускать нужные версии приложения без ручной работы по обновлению кода на куче хостов. Было решено запускать нужные программы с NFS-шары. Приложения были internal use only, одноразовые, причём написанные под конкретную задачу. Шара монтировалась в каталог /opt при загрузке и приложения оттуда запускались с помощью скрипта rc.local. Поскольку речь шла про экспериментальный стенд с очень частым изменением кода, играть в честного разработчика (пакеты, репозиторий, обновления, init.d скрипты) было лениво. Всё происходило под Debian Squeeze.

        Шара была прописана в /etc/fstab, запуск нужных тестов — в rc.local. Казалось бы, всё сделано.

        … И тут я наткнулся на Мистику. Приложения стартовали раз из пяти, причём версия «кривое приложение» была отметена почти сразу — ровно так же иногда не запускались любые другие исполняемые файлы. Причём, с /opt. Из других каталогов отрабатывали нормально. При этом руками rc.local запускаешь — 100% всё хорошо. При загрузке — успешный запуск раз из пяти, или даже реже.

        В начале я не воспринимал эту проблему как серьёзную, и пытался её решить нахрапом. Поскольку проблема проявлялась только для /opt я дописал в rc.local команду ls -a1 /opt >/var/log/ls. Как и предполагалось, в /opt на момент выполнения rc.local было только два файла — точка и две точки. Другими словами, NFS-шара не подмонтировалась. Иногда. А иногда подмонтировалась.

        Читать дальше →
      • Использование Rebar и GProc

          Использование Rebar



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

          При разработке на Erlang часто приходится собирать зависимости из разных источников, следить за их нужными версиями, создавать OTP-релизы для распространения проектов. Дела достаточно рутинные и неприятные. Для того, чтобы разработка меньше доставляла неприятных моментов, компанией Basho был создан очень удобный инструмент — Rebar. В этой статье я постараюсь раскрыть преимущества от его использования на реальном примере с использованием сторонних зависимостей и созданием конфигурируемых OTP-релизов.
          Читать дальше →
        • Дерево Фенвика

          Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

          Что это?


          Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
          • позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
          • позволяет изменять значение любого элемента за O(log N);
          • требует памяти O(N);
          Читать дальше →
        • Разоблачение алгоритмов растеризации шрифтов (2/2)

          • Перевод
          (вторая часть перевода статьи Разоблачение алгоритмов растеризации шрифтов)

          Linux


          Наследуя худшее


          Windows растеризует шрифты плохо, Linux ещё хуже. Во всех Linux-системах, которые я видел, используется FreeType [10] Дэвида Тёрнера, Роберта Вильгельма и Вернера Лемберга. Это отличная библиотека, но способ её использования, к сожалению, нельзя назвать удачным. Типичный скриншот Linux выглядит так:



          Вот полный скриншот:
          ссылка

          Сразу заметна проблема — чёрные пятна в скругленных углах, образовавшиеся в результате сглаживания. Вцелом, можно сказать, что косые штрихи выглядят тяжелее чем вертикальные, что в регультате производит впечатление «грязи». Вы можете возразить, что FreeType и Linux могли бы использовать схожую с ClearType субпиксельную растеризацию, но по мне это не даёт заметных преимуществ.
          Читать дальше →
        • Разоблачение алгоритмов растеризации шрифтов (1/2)

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

          От переводчика


          В первый раз я столкнулся с этой статьей в 2008 году. С тех пор я неоднократно задумывался о переводе (так как лучшего материала по теме не найти), и вдруг ссылка на оригинал всплыла на Хабре в обсуждении топика «Сглаживание шрифтов, анти-алиасинг, и субпиксельный рендеринг». Это стало решающим фактором (раз на материал ссылаются, значит, он кому-то нужен), и работа была, наконец, закончена.
          Читать дальше →
        • Компрессия данных в системах промышленной автоматизации. Алгоритм SwingingDoor

            Здравствуйте, уважаемые читатели. Хочу представить вашему вниманию описание алгоритма компрессии данных SwingingDoor и рассказать о том, как мы его применяем.



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

            Зачем использовать компрессию, почему бы не хранить все данные?
            Читать дальше →
          • Материалы продвинутого уровня по Питону

              PythonВ мире все примерно распределяется в соответствии с принципом Паретто. Меньшая часть — богатые, большая часть — бедные (читающий, ты входишь в золотой миллиард). Тоже касается и материалов о программировании. Порой очень сложно найти хоть что-нибудь не начального уровня.

              После прочтения Dive into Python или подобной ей и ознакомления с документацией возникает вопрос, а что читать дальше? Можно обратиться к списку книг на python.org. Там есть раздел Advanced Books, но в нем всего лишь 6 книг (седьмая не выходила), и только одну я бы назвал по-настоящему стоящей.

              К счастью, у Питона есть очень подробная и качественная документация. Но даже в ней многие темы либо только поверхностно затронуты, либо их очень сложно найти (потому что документация большая, и если не знаешь, куда смотреть, не найдешь).

              Ниже собраны сложные материлы про Питон, его устройство и возможности. Все на английском (грех, не знать технический английский). Про Dive into Python я слукавил. Большинство приведенных материалов требуют хорошее знание Питона и наличие опыта программирования на нем.

              Подробнее