Эта статья об алгоритме распознавания авторства, реализованном в проекте «Текстовый анализатор». В окончании статьи мы рассмотрим, как собираются частотные характеристики, и в общих чертах познакомимся с нейросистемой Хэмминга. (Начало и продолжение).

Структура статьи:

1. Анализ авторства
2. Знакомство с кодом
3. Внутренности TAuthoringAnalyser и хранение текстов
4. Разбиение на уровни конечным автоматом на стратегиях
5. Сбор частотных характеристик
6. Нейросеть Хэмминга и анализ авторства

Дополнительные материалы:

• Исходники проекта «Текстовый анализатор» (Borland C++ Builder 6.0)
• Тестирование нейросистемы Хэмминга в Excel'е ([xls])
• Таблица переходов для КА, разбивающего текст на уровни ([xls])
• Расчет благозвучия отдельных букв ([xls])
• Презентация дипломного проекта «Текстовый анализатор» ([ppt])
• Презентация проекта «Карта благозвучия» ([ppt])
• Все эти материалы в сжатом виде ([zip], [7z], [rar])

Эта статья об алгоритме распознавания авторства, реализованном в проекте «Текстовый анализатор». В продолжении статьи мы рассмотрим конечный автомат для разбиения текста на уровни. (Начало и окончание).

Структура статьи:

1. Анализ авторства
2. Знакомство с кодом
3. Внутренности TAuthoringAnalyser и хранение текстов
4. Разбиение на уровни конечным автоматом на стратегиях
5. Сбор частотных характеристик
6. Нейросеть Хэмминга и анализ авторства

Дополнительные материалы:

• Исходники проекта «Текстовый анализатор» (Borland C++ Builder 6.0)
• Тестирование нейросистемы Хэмминга в Excel'е ([xls])
• Таблица переходов для КА, разбивающего текст на уровни ([xls])
• Расчет благозвучия отдельных букв ([xls])
• Презентация дипломного проекта «Текстовый анализатор» ([ppt])
• Презентация проекта «Карта благозвучия» ([ppt])
• Все эти материалы в сжатом виде ([zip], [7z], [rar])

Добрый день, уважаемые хабражители. Я давно хотел опубликовать под GPL-лицензией свой «Текстовый анализатор» ([1]). Наконец, дошли руки. «Текстовый анализатор» — это исследовательский проект, который я разрабатывал три года на 3, 4 и 5-м курсах университета. Главная цель была: создать алгоритм распознавания авторства текста, используя нейросети Хэмминга или Хопфилда. Идея была такова: эти нейросистемы распознают образы, а к задаче распознавания образов можно свести задачу выявления авторства. Для этого необходимо по каждому тексту собрать статистику, и чем больше разных критериев, тем лучше: частотный анализ букв, анализ длин слов/предложений/абзацев, частотный анализ двухбуквенных сочетаний, и так далее. Нейросистема могла бы выявить, характеристики каких текстов наиболее сходны. Работы было — вал. Много кода, хитрые алгоритмы, ООП, паттерны проектирования. Помимо основной задачи я так же реализовал ещё одно ноу-хау: «Карту благозвучия». По задумке, такая карта должна показывать все плохо и хорошо звучащие места, выделяя их цветом. Критерии оценки благозвучия должны задаваться каким-то универсальным образом, например, правилами. Для этой цели я даже разработал специальный графический язык, RRL (Resounding Rules Language). Работы было — вал. Много кода, хитрые алгоритмы, ООП, паттерны проектирования. В итоге получилась большая и сложная программа, правда, с неприглядным интерфейсом. С этим проектом я даже выиграл в конкурсе дипломных работ, получил 1 и 3 места на университетских конференциях, а так же 2 место на международной научно-практической.

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

(У статьи есть продолжение и окончание.)

Структура статьи:

1. Анализ авторства
2. Знакомство с кодом
3. Внутренности TAuthoringAnalyser и хранение текстов
4. Разбиение на уровни конечным автоматом на стратегиях
5. Сбор частотных характеристик
6. Нейросеть Хэмминга и анализ авторства

Дополнительные материалы:

• Исходники проекта «Текстовый анализатор» (Borland C++ Builder 6.0)
• Тестирование нейросистемы Хэмминга в Excel'е ([xls])
• Таблица переходов для КА, разбивающего текст на уровни ([xls])
• Расчет благозвучия отдельных букв ([xls])
• Презентация дипломного проекта «Текстовый анализатор» ([ppt])
• Презентация проекта «Карта благозвучия» ([ppt])
• Все эти материалы в сжатом виде ([zip], [7z], [rar])

Доброго времени суток!

Какое Ваше отношение к оператору goto в языках С/С++? Скорее всего, когда Вы учились программировать, Вы его использовали. Потом Вы узнали, что это плохо, и Вы о нем позабыли. Хотя иногда при сложной обработке ошибок… нет-нет, там try … throw … catch. Или же для выхода из вложенных циклов … не-ет, там флаги и куча сложностей. Или когда вложенные switch … нет-нет-нет, там те же флаги.
И все-таки, иногда в ночной тиши Вы допускали в свое подсознание грешную мысль – «а почему бы не использовать вот тут goto? И программа вроде как стройней будет, и оптимально выходит. Да-а, было бы хорошо… Но нет – нельзя, забыли!».
А почему так оно?
Под катом – небольшое расследование и мое, основанное на многолетней практике и разных платформах, отношение к этому вопросу
UPD: тут статья рассматривает С и С++, программирование для PC и слегка для микроконтроллеров. Конкретно о микроконтроллерах есть другая статья.

Введение

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

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

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

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

Натолкнулся в разделе QA на интересный вопрос. Ответ на него заставил написать эту статью как бОлее полный ответ на вопрос «как организовать поиск по множеству параметров, как в Яндекс-маркете, например».

Я знаю, что на Хабре, да и вообще есть много сторонников noSQL решений (сам не без греха), но все же я сторонник сначала подумать, а уже потом выбирать решение.

Итак, что имеем в «ДАНО»

• Имеем 120 чекбоксов — вариант 1/0
• Имеем 30 «радио» с выбором «да/нет/не важно»
• Имеем 2-3 слайдера для указания диапазона цен/размера чего нить
• Имеем самое главное: 12 млн записей в БД.
• Имеем Select * From tovar Where (wifi=true) and (led=false) and (type=3) and ….остальные параметры …; со временем выполнения близкому к истерике клиента.

С удивлением обнаружил, что про явление алиасинга (aliasing) здесь постов нет. Ситуацию нужно исправить, тк. алиасинг в любой сколько-то сложной C++ программе обязательно хоть где-нибудь, да есть. Это может быть хорошо, давая возможность ловких оптимизаций, а может быть плохо, внося повышенной паршивости баги. Под катом вкратце про оба случая (ну и неизменное «компилятор бьет спина», конечно; для разнообразия сегодня это gcc).

Многие наверняка используют индикаторы процесса, например, когда передаете/получаете какие-нибудь данные через AJAX.

Однажды я озадачился, чтобы при нажатии на кнопку, которая отправляет данные формы на сервер, внутри неё появился этот самый индикатор. Изначально фон был однотонный, но в любой момент дизайнеры могли заменить его на другой, либо вообще сделать градиент.

Делать специальный GIF под каждую ситуацию довольно глупо. Поэтому правильное решение — использовать Canvas.

Обзор практически всех *top утилит под linux (atop, iotop, htop, foobartop и т.д.).

top

Все мы знаем top — самую простую и самую распространённую утилиту из этого списка. Показывает примерно то же, что утилита vmstat, плюс рейтинг процессов по потреблению памяти или процессора. Совсем ничего не знает про загрузку сети или дисков. Позволяет минимальный набор операций с процессом: renice, kill (в смысле отправки сигнала, убийство — частный случай). По имени top суффикс "-top" получили и все остальные подобные утилиты в этом обзоре.

atop

Atop имеет два режима работы — сбор статистики и наблюдение за системой в реальном времени. В режиме сбора статистики atop запускается как демон и раз в N времени (обычно 10 мин) скидывает состояние в двоичный журнал. Потом по этому журналу atop'ом же (ключ -r и имя лог-файла) можно бегать вперёд-назад кнопками T и t, наблюдая показания atop'а с усреднением за 10 минут в любой интересный момент времени.

В отличие от top отлично знает про существование блочных устройств и сетевых интерфейса, способен показывать их загрузку в процентах (на 10G, правда, процентов не получается, но хотя бы показывается количество мегабит).

Незаменимое средство для поиска источников лагов на сервере, так как сохраняет не только статистику загрузки системы, но и показатели каждого процесса — то есть «долистав» до нужного момента времени можно увидеть, кто этот счастливый момент с LA > 30 создал. И что именно было причиной — IO программ, своп (нехватка памяти), процесор или что-то ещё. Помимо большего количества информации ещё способен двумя цветами подсказывать, какие параметры выходят за разумные пределы.

Для чего это нужно

Когда в семье число мобильных телефонов становится более 3-х, назревает вопрос мониторинга баланса и оповещения, когда баланс приближается к критической отметке. Есть много средств для мониторинга баланса, но зачем городить огород, когда под рукой есть незаменимый Nagios (так получилось что и дома у меня есть свой мониторинговый сервер, его основная задача наблюдать за состоянием серверов организаций которые я администрирую в нерабочее время). Данное решение также подойдет для мониторинга баланса корпоративного лицевого счета.

Привет, Хабр!
Всё больше статей появляется про Canvas, и это не может не радовать. Основы, будем надеяться, уже изучены, а мне хотелось бы поделиться примером возможного практического использования canvas, а именно создать анимированный индикатор прогресса.

Для нетерпеливых результаты эксперимента можно посмотреть здесь: http://pastehtml.com/view/1d7z824.html, а также скриншот конечного результата:


Прогресс-бар получился довольно простой, но в то же время в стиле веб 2.0 — закругленный (конечно же!), с элементами глубины и объема: то есть тенями и градиентами.

За подробностями прошу под кат.

Наконец–то появилась возможность опубликовать разработанный мною когда-то алгоритм. Алгоритм был разработан для программы автоматического снятия скриншотов. Для удобства дальнейшего его описания буду называть его – SSP (sciner screenshot packer). SSP можно справедливо сопоставить PNG, поэтому в статье я буду проводить сравнения именно с ним.

Алгоритм имеет два режима компресии:

1. без потерь – в котором, изображения после декомпресии будет восстановлено с точностью до бита;
2. с потерями – который не уменьшает качества картинки, просто в нем непосредственно перед сжатием, изображение переводится палитру YcbCr
   Только лишь за счет изменения палитры удается существенно улучшить сжатие. Использую следующие коэффициенты:
   cY = 0.30078125 * R + 0.5859375 * G + 0.11328125 * B
cCb = -0.171875 * R - 0.33984375 * G + 0.51171875 * B + 128
cCr = 0.51171875 * R - 0.4296875 * G - 0.08203125 * B + 128

Суть языка Brainfuck в том, что мы всегда бегаем по ячейкам ленты, уменьшая или увеличивая значения в них. В циклах мы можем пробегать из одного конца в другой, что-то подсчитывая, зачастую используя много вложенных циклов. Не трудно догадаться, что интерпретация этого языка относительно медленна. Конечно, на современных компьютерах этого практически не заметно, но… Предлагаю небольшой тест: берите написанный вами интерпретатор, и запускайте вот этот не хитрый код:

>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.

Дождались конца выполнения? Согласитесь, что это было не так быстро, как могло показаться сразу. Что ж, давайте посмотрим, как сделать интерпретатор, который будет выполнять данный код не больше чем за несколько секунд.

Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

В настоящее время существует много стандартов наименования переменных, но два из них являются наиболее популярными среди программистов: это camel case («Верблюжья» нотация) и underscore (именование переменных с использованием символа нижнего подчеркивания в качестве разделителя). Кто-то может возразить, что существуют и другие популярные стандарты, но в рамках данной статьи мы сравним эти два, и узнаем у программистов — какого стандарта придерживаются они. Конечно, некоторые программисты связаны рамками стандартов кодирования языка или фреймворка, который они используют, но мы постараемся сделать независимое сравнение.

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

В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).

Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.

В статье собраны всем известные методы и предельно извращенные. Эту статью я решил написать после недавнего прочтения поста в блоге Badass JavaScript и решил её дополнить своими находками.

Первый способ

Он всем известен — обфускация минимизаторами такими как JS Packer, JSmin, YUI Compressor, Closure compiler или можно просто пугуглить «JavaScript Obfuscator» и найдется ещё сто штук разных обфускаторов.
Они превращают существующий код

function MyClass(){
    this.foo = function(argument1, argument2){
        var addedArgs = parseInt(argument1)+parseInt(argument2);
        return addedArgs;
    }
    var anonymousInnerFunction = function(){
        // do stuff here!
    }
}

В какой-то такой вид:

function MyClass(){this.foo=function(c,b){var d=parseInt(c)+parseInt(b);return d};var a=function(){}};

Или такой:

var _0xd799=["\x66\x6F\x6F"];function MyClass(){this[_0xd799[0]]=function (_0xefcax2,_0xefcax3){var _0xefcax4=parseInt(_0xefcax2)+parseInt(_0xefcax3);return _0xefcax4;} ;var _0xefcax5=function (){} ;} ;

Или вот такой:

eval(function(p,a,c,k,e,d){e=function(c){return c};if(!''.replace(/^/,String)){while(c--){d[c]=k[c]||c}k=[function(e){return d[e]}];e=function(){return'\\w+'};c=1};while(c--){if(k[c]){p=p.replace(new RegExp('\\b'+e(c)+'\\b','g'),k[c])}}return p}('4 0="3 5!";9 2(1){6(1+"\\7"+0)}2("8");',10,10,'a|msg|MsgBox|Hello|var|World|alert|n|OK|function'.split('|'),0,{}))

Но ничего не стоит его восстановить с помощью jsbeautifier.org либо просто убрать eval и получить исходный код, многое потеряем, но смысл кода восстановим. Ну и с первого взгляда мы видим, что перед нами JavaScript.

Все это были цветочки под катом жесткие методы обфускации.

Примерно два года назад я арендовал у одного немецкого хостера не очень мощный сервер на базе Centos 5.2. На нём живут несколько вебпроектов, приносящих некоторую прибыль, и поэтому, я стараюсь присматривать за ним по мере возможности.
На Centos есть стандартный анализатор логов Logwatch, который запускается ежедневно по крону, анализирует содержимое /var/log, делает сводный отчет и присылает его по электропочте. В один прекрасный день я обнаружил в этом отчете запись:

--------------------- yum Begin ------------------------ 
 
 Packages Installed:
    lzo2 - 2.02-3.el5.rf.i386
    dnstracer - 1.8-1.2.el5.rf.i386
    openvpn - 2.0.9-1.el5.rf.i386

---------------------- yum End -------------------------

В тот момент меня она очень смутила, так как в предыдущий день на сервер я не логинился и тем более ничего не устанавливал. Первое, что пришло в голову — сервер был скомпроментирован. Себя я считал уверенным пользователем Linux, однако я растерялся. Благо в тот момент в icq был мой бывший коллега, лучший системный администратор, которого я знаю, и просто очень хороший человек.
Он помог быстро проверить систему. В результате у меня сформировалось краткое HowTo о том, как быстро проверить свой сервер на предмет взлома. Уверен, что многим Храброчитателям оно будет полезно. Предполагается, что пользователь знаком с консолью Linux/Unix.

Я уже писал про скрипт audio.js, позволяющий проигрывать аудио файлы использую возможности html5 и flash. Пост был встречен хорошо, поэтому сейчас я хочу рассказать про jPlayer — jQuery плагин для проигрывания аудио и видео.