Классификатор слов

Работа в конкурсе Hola: https://habrahabr.ru/company/hola/blog/282624/

Суть решения: арифметическое кодирование + фильтр Блума.

Данный набор исходников будет опубликован после завершения приема работ по адресу https://github.com/deNULL/challenge_word_classifier.

Файлы (примерно в том порядке, в котором нужно их запускать):

• fetch-tests.py

Принимает два аргумента — индекс первого теста и количество тестов. Выгружает тесты в папку tests, группируя их по 1000 штук в файлы вида 123000-pos.json (массив корректных слов) и 123000-neg.json (массив неправильных слов), в каждом получается примерно по 1000 * 100 / 2 = 50000 слов. Сделано так, чтобы не захламлять папку сотнями тысяч файлов (для надежного тестирования стоит выкачать порядка 100-500 тысяч тестов).

• build-2grams.js

Читает словарь из файла words.txt, приводит все слова к нижнему регистру, выбрасывает дубликаты, сохраняет результат в uniq.txt. Затем считает статистику биграмм по всем словам, результаты записывает в файлы 2grams.txt, 2grams.bin и 2grams.bin.gz.

В 2grams.bin не записываются сами биграммы, только количество вхождений в порядке полного перечисления биграмм (сначала для aa, потом для ab и так далее).

Если по биграмме есть статистика, пишется три байта: частота в начале слова, в середине и на конце. Так как слов в словаре много, а особо высокая точность нам не требуется, количество вхождений биграммы сначала делится на 162, если результат все равно больше 255, то заменяется на 255. Если при делении и округлении получился 0 (но реальное число вхождений больше нуля), он заменяется на 1 (иначе решение посчитает, что биграмма на этой позиции не встречается вовсе и забракует слово).

Файл 2grams.bin.gz используется только для оценки размера биграмм в сжатом виде, 2grams.txt — для человекочитабельности. 2grams.bin получается размером ~2000 байт, 2grams.bin.gz – ~1000.

• build-bloom.js

Читает словарь (без дубликатов) из uniq.txt, строит фильтр Блума и сохраняет результат в bloom.bin и bloom.bin.gz.

Для того чтобы упростить тестирование кода (и не сомневаться, что фильтр строится и используется одинаковым образом), build-bloom.js подключает файл полного решения solution.full.js и использует экспортируемые из него функции и константы.

Чтобы фильтр Блума лучше сжимался (и чуть почаще выдавал отрицательные ответы на неправильных словах), он дополнительно фильтруется: в нём сбрасываются некоторые биты (об этом ниже).

Как и при построении биграмм, bloom.bin.gz нужен только для оценки степени сжатия.

• solution.full.js

Отладочная (наиболее полная) версия решения. Используется как для тестов, так и при построении фильтра Блума, так как экспортирует функцию arithm, осуществляющую арифметическое кодирование слова.

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

У слов, заканчивающихся на 's, откусывается этот суффикс. Если в слове есть другие вхождения апострофа, оно считается некорректным (в словаре таких слов ничтожно мало). Это позволяет сократить алфавит на один символ.

Кодирование делается традиционным способом: делением интервала [0, 1] с применением чисел с плавающей запятой. Для каждой буквы слова вероятность считается с учетом предшествующей буквы (по биграммам). Результат (число из диапазона [0, 1]) просто умножается на магическое число 12064428 и берется по модулю от размера фильтра Блума. На длинных словах из редких букв теряется точность: их коды "слипаются", но нас это более-менее устраивает.

• solution.body.js

Компактное решение. Получается из solution.full.js ручным выкидыванием всего ненужного. Кроме того, оно написано с учетом того, что код выполняется из функции exports.init (поэтому она не объявляется), и ему будет доступен буфер с данными в переменной B и смещение в этом буфере, с которого начинаются данные, в переменной O.

• solution.body.min.js

Компактное решение, пропущенное через минификатор. Я использовал онлайн-сервис http://jscompress.com/ — по идее, можно поставить UglifyJS2 локально, но почему-то результат у меня получался хуже.

• concat.js

Сборка решения. Склеиваются файлы solution.body.min.js, 2grams.bin и bloom.bin, затем сжимаются в файл data.gz. Для сжатия используется библиотека Pako с небольшим хаком для большей эффективности на наших данных (конкретнее: файл lib/zlib/deflate.js, строка 755: в условии s.match_length <= 5 константа поднята до 6).

Генерируется файл solution.js: всё, что он делает — читает первые N байт из переданного в exports.init буфера и делает eval. N = размеру solution.body.min.js. На этот код хватает 52 символов: меньше, чем на его описание.

• run.js

Прогон решения на тестах. Решение подключается из solution.full.js с помощью require для скорости. Можно передать либо пару чисел — номер первой и последней тысячи в диапазоне тестов, либо слово check, чтобы быстро проверить первые 10 тысяч тестов, но не сохранять статистику по ним.

Если запуск был без параметра check, то итогам тестов генерятся файлики 2grams-stats.json и bloom-stats.json: в первый записывается число вхождений биграмм (по корректным и некорректным словам), во второй — число срабатываний на каждый бит в фильтре Блума (тоже по корректным и некорректным словам).

Статистика по биграммам в текущем решении не используется, а статистику по фильтру Блума build-bloom.js использует для прореживания фильтра: в итоге на тех тестах, на которых прогонялось решение, оно работает лучше, чем "в дикой природе". Поэтому лучше собирать данные о коллизиях на одних тестах, а потом проверять на других. Практика показывает, что результаты всё равно улучшаются (а главное, более рыхлый фильтр Блума лучше сжимается, что позволяет сделать его чуть побольше), особенно при сборе достаточно объемной статистики (чтобы на каждый бит было не 1-2 срабатывания, а хотя бы с десяток).

В целом неплохие результаты выходят при размере фильтра в 640000 бит, при условии что слова забивают около 180000 бит и ещё ~20000 бит обнуляется.

Чтобы получить готовое решение, нужно:

• Скачать файл words.txt из условий.
• Установить библиотеку pako из npm и применить к ней описанный выше хак.
• Сделать один раз

python3 fetch-tests.py 1 200000 && node build-2grams.js

Это выкачает 200 тысяч тестов, что является небыстрым процессом.

• Сделать

node build-bloom.js && node concat.js && node run.js 10 200

Это построит фильтр Блума без вычета "лишних" бит, соберет код и данные, запустит тесты с 10-тысячного по 200-тысячный, соберет по ним статистику и сохранит её в файл stats.json.

• Сделать

node build-bloom.js evict && node concat.js && node run.js check

Это заново выполнит сборку, но фильтр Блума будет вычищен от "плохих" бит, по которым была собрана статистика на предыдущем шаге. В конце буден выполнен прогон решения на первых 10 тысячах тестов.

• При изменении кода в solution.full.js нужно не забывать обновлять аналогичным образом solution.body.js, а его минифицировать в solution.body.min.js. Увы, автоматически они не генерятся. Для проверки достаточно выполнить последние две пункта.