TopMine

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

Исходная статья: El-Kishky, Ahmed, et al. "Scalable topical phrase mining from text corpora." Proceedings of the VLDB Endowment 8.3 (2014): 305-316.APA

Особенности реализации

• Язык - C++11
• Внешние зависимости - Boost, gtest (для юнит-тестов), cpplint (для проверки code style)
• Сборка под Linux/Unix, с помощью CMake
• Многопоточный параллелизм
• На выходе исполняемый файл topmine (для тестов - topmine_tests)
• По завершению работы алгоритм сообщает о затраченном времени и пиковом объёме использованной оперативной памяти
• Юнит-тесты прогоняются запуском исполняемого файла topmine_tests
• Проверка code style производится запуском скрипта check_code_style.sh (запускать из utils)

Сборка

Стандартная для Linux/Unix с CMake (для исключения сборки тестов можно закомментировать всё с 54-й строки):

mkdir build
cd build
cmake ..
make

Опции запуска

• --help - вывести описание флагов запуска.

• --input-path <arg> - путь к текстовому файлу с данными. Каждая строка файла представляет одно предложение, на первом месте стоит числовой идентификатор документа, далее через пробелы или символ табуляции идут слова. В каждой строке должны быть как минимум идентификатор и одно слово. ВАЖНО: для внутренних нужд и для представления выходного результата TopMine резервирует символ из параметра esc-character, его не должно быть во входном корпусе! Значение по-умолчанию: "".

• --output-path <arg> - путь к текстовому файлу для сохранения документов с выделенными коллокациями. В случае num-threads > 1 документы сохраняются в случайном порядке. В зависимости от значения флага return-indices файл будет заполнен либо коллокациями, слова в которых соединёны через esc-character, либо индексами в формате <стартовый индекс><esc-character><длина коллокации>. В случае, если параметр output-path не задан, алгоритм не будет преобразовывать документы, а только выделит коллокации. Значение по-умолчанию: отсутствует.

• --collocations-output-path <arg> - путь к текстовому файлу для сохранения коллокаций. Каждая строка соответствует одной коллокации и имеет формат <коллокация> <df>, где сама коллокация представлена в виде строки, содержащей слова, разделённые esc-character, а <df> - это частота встречаемости этой коллокации в документах. Значение по-умолчанию: "collocations.txt".

• --collocation-max-size <arg> - максимальная длина коллокаций, которые нужно искать. Значение по-умолчанию: 2.

• --num-threads <arg> - число параллельных потоков-обработчиков. Значение по-умолчанию: 1.

• --batch-size <arg> - размер порции документов для одного потока для обработки за один раз. Значение по-умолчанию: 100.

• --threshold <arg> - порог фильтрации по частоте. Используется при отборе как исходных униграм, так и всх дальнейших коллокаций на первом шаге алгоритма. Коллокация проходит, если её частота >= порога. Значение по-умолчанию: 0.

• --alpha <arg> - порог для статистической значимости пары коллокаций во второй части алгоритма. Значение по-умолчанию: 1e-20.

• --return-indices <arg> - флаг, определяющий формат возвращаемых документов - в виде строк, или в виде индексов. Имеет смысл только при указанном параметре output-path. Значение по-умолчанию: 0.

• --use-cache <arg> - флаг, разрешающий или запрещающий кэширование в памяти входной коллекции. Кэширование требует дополнительного объёма ОЗУ (примерно 2 * <размер входного файла>, из-за того, что коллекция хранится в виде строк), но может ощутимо (на 20-50 процентов) ускорить работу алгоритма. Оптимальный вариант при наличии большого объёма оперативной памяти, особенно с учётом того, что параметры коллокаций, вычисляемые по ходу работы алгоритма, занимают в разы больше места, чем исходные данные. Значение по-умолчанию: 0.

• --delimiters <arg> - строка, каждый элемент которой - символ, по которому производится токенизация. Значение по-умолчанию: .

• --esc-character <arg> - выделенный символ, которого не должно быть в данных, используется алгоритмом для работы и представления итоговых коллокаций. Значение по-умолчанию: |.