tongrams
1.0.0
Tongrams - это библиотека C ++ для индекса и запроса больших языковых моделей в сжатом пространстве, как описано в следующих документах
Джулио Эрманно Пибири и Россано Вентурини. Пожалуйста, цитируйте эти документы, если вы используете Tongrams.
Более конкретно, реализованные структуры данных могут использоваться для отображения n -граммов с их соответствующими (целочисленными) частотными количествами или с (плавающей запятой) вероятностями и отборами для моделей Backoff-Interpolated Kneser-Ley.
Библиотека оснащена сжатой структурой данных TRIE, в которой N -грамм назначают целочисленные идентификаторы (ID) и сжаты Elias -Fano для поддержки эффективных поисков в сжатом пространстве. Передача таких идентификаторов, основанное на контексте, позволяет кодировать слово после контекста фиксированной длины k , то есть, его предыдущие k слов, с целым числом, значение которого ограничено количеством слов, которые следуют такому контексту, а не размером всего словаря (количество Uni-Grams). В дополнение к структуре данных TRIE, библиотека позволяет создавать модели на основе минимального идеального хэширования (MPH) для поиска постоянного времени.
При использовании подсчета частоты, структуры данных поддерживают операцию lookup() , которая возвращает количество случаев указанной N -граммы. По -другому, когда используется для хранения вероятностей и отказов, структуры данных реализуют функцию score() , которая, учитывая текст в качестве входного, вычисляет оценку недоумения текста.
Это руководство предназначено для того, чтобы предоставить краткий обзор библиотеки и проиллюстрировать ее функции с помощью некоторых примеров.
Код был протестирован на Linux Ubuntu с gcc 5.4.1, 7.3.0, 8.3.0, 9.0.0; Mac OS X El Capitan с clang 7.3.0; Mac OS X Mojave с clang 10.0.0.
Для сборки необходимы следующие зависимости: CMake и Boost .
Если вы клонировали репозиторий без --recursive , вам нужно будет выполнить следующие команды перед строительством:
git submodule init
git submodule update
Чтобы построить код в системах Unix (см. File CMakeLists.txt для используемых флагов компиляции), его достаточно.
mkdir build
cd build
cmake ..
make
Вы можете включить параллельную компиляцию, указав некоторые задания: make -j4 .
Для лучшего из выполнения, составьте следующим образом.
cmake .. -DCMAKE_BUILD_TYPE=Release -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make
Для среды отладки, вместо этого компилируйте следующим образом.
cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make
Если не указано иное, для остальной части этого руководства мы предполагаем, что мы вводим команды терминала следующих примеров из созданной build каталога.
Файлы n -gram подсчитаны, следуя формату Google, то есть по одному отдельному файлу для каждого различного значения N (порядка), в котором перечислены один грамм на строку. Мы обогащаем этот формат с заголовком файла, указывающим общее количество n -граммов в файле (строки):
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
Такие n- файлы должны быть названы в соответствии со следующей соглашением: <order>-grams , где <order> является заполнителем для значения n . Файлы можно оставить несортированным, если должны быть созданы только модели на основе MPH, тогда как они должны быть отсортированы в порядке префикса для структур данных на основе TRIE, в соответствии с выбранным сопоставлением словаря , которое должно быть представлено файлом Uni-Gram (см. Подраздел 3.1 [1]). Настоятельно рекомендуется сжатие входных файлов со стандартными утилитами, такими как gzip . Утилита sort_grams можно использовать для сортировки файлов N -Gram в порядке префикса. В заключение, структуры данных, хранящие частоты, построены из каталога, содержащего файлы
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gzОтформатировано, как объяснено выше.
Вместо этого файла n -Gram -листинга и отборочных возможностей соответствует формату файла ARPA. N -граммы в файле ARPA должны быть отсортированы в заказе суффикса , чтобы создать обратную структуру данных Trie. Утилита sort_arpa может использоваться для этой цели.
Каталог test_data содержит:
gzip ;queries.random.5K содержащий 5000 N -граммов (1000 для каждого порядка и нарисовано случайным образом);arpa , который перечисляет все n -граммы, отсортированные в заказе суффикса, чтобы эффективно построить обратную попытки;sample_text (6075 предложения в общей сложности 153 583 слов), используемый для эталона недоумения; Его компаньонный файл sample_text.LESSER включает только первые 10 предложений. Для следующих примеров мы предполагаем, что мы работаем с образцом данных, содержащимися в test_data .
Два исполняемых файла build_trie и build_hash используются для сборки Trie на основе TRIE и (минимально совершенных) языковых моделей на основе хеш, соответственно. Запустите исполняемые файлы без каких -либо аргументов, чтобы узнать об их использовании.
Теперь мы показываем несколько примеров.
Команда
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
строит Elias-Fano Trie
test_data ;ef_trie.count.bin . Команда
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
строит разделенный Elias-Fano Trie
test_data ;pef_trie.count.out . Команда
./build_trie ef_trie 5 prob_backoff --remapping 2 --u -20.0 --p 8 --b 8 --arpa ../test_data/arpa --out ef_trie.prob_backoff.bin
строит Elias-Fano Trie
<unk> вероятностей ( --p ) и отборочных ( --b );arpa ;ef_trie.prob_backoff.bin . Команда
./build_hash 5 8 count --dir ../test_data --out hash.bin
Создает модель на основе MPH
test_data ;hash.bin . test каталог содержит модульные тесты некоторых фундаментальных строительных блоков, используемых реализованными структурами данных. Как обычно, запуск исполняемых файлов без каких -либо аргументов будет отображать список их ожидаемых параметров ввода. Примеры:
./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128
Каталог также содержит модульный тест для структур данных, хранящих количество частот, с именем check_count_model , который проверяет реализацию, проверяя, что каждый счет, хранящийся в структуре данных, такой же, как и в входных файлах, из которых ранее была создана структура данных. Пример:
./test_count_model ef_trie.count.bin ../test_data
где ef_trie.count.bin -это имя двоичного файла структуры данных (возможно, построенный с командой, показанной в примере 1), а test_data -это имя папки, содержащей файлы подсчета n -грам.
Для примеров в этом разделе мы использовали настольную машину под управлением Mac OS X Mojave, оснащенной процессором Intel Core I5 2,3 ГГц (называемый Mac настольного компьютера ). Код был составлен с Apple LLVM версией 10.0.0 clang со всеми оптимизациями (см. Раздел «Создание кода»). Кроме того, мы воспроизводим некоторые эксперименты с ЦП Intel (R) Core (TM) I9-9900K @ 3,60 ГГц, под Ubuntu 19.04, 64 бита (называется Server Linux ). В этом случае код был составлен с gcc 8.3.0.
Для уровня хранилища данных в структуре данных мы можем проверить скорость поиска запросов, используя Benchmark Program lookup_perf_test . В следующем примере мы показываем, как создать и сравнить три различные структуры данных: EF-Trie без переиздания, EF-rtrie с повторным порядком 1 и PEF-RTRIE с порядком переназначения 2 (мы используем те же имена для структур данных, которые представлены в [1]). Каждый эксперимент повторяется в 1000 раз по сравнению с файлом тестового запроса queries.random.5K Benchmark Program lookup_perf_test будет показывать среднее время на пробег и среднее время на запрос (наряду с общим количеством n -граммов, общее количество байтов структуры данных и байтов на n -грамму).
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.bin
./lookup_perf_test ef_trie.bin ../test_data/queries.random.5K 1000
./build_trie ef_trie 5 count --remapping 1 --dir ../test_data --out ef_trie.r1.bin
./lookup_perf_test ef_trie.r1.bin ../test_data/queries.random.5K 1000
./build_trie pef_trie 5 count --remapping 2 --dir ../test_data --out pef_trie.r2.bin
./lookup_perf_test pef_trie.r2.bin ../test_data/queries.random.5K 1000
Результаты этого (микро) теста суммированы в следующей таблице.
| Структура данных | Порядок повторного перевода | Байты х грамм | µs x запрос - настольный Mac | µs x запрос - сервер Linux |
|---|---|---|---|---|
| EF-Trie | 0 | 2.40 | 0,435 | 0,316 |
| Ef-rtrie | 1 | 1,93 ( -19,7% ) | 0,583 | 0,428 |
| PEF-RTRIE | 2 | 1,75 ( -26,9% ) | 0,595 | 0,427 |
Для структуры данных сохраняет вероятности и откаты, мы можем вместо этого проверить скорость оценки текстового файла, используя score программы. Полный пример следует.
./build_trie ef_trie 5 prob_backoff --u -10.0 --p 8 --b 8 --arpa ../test_data/arpa --out ef_trie.prob_backoff.8.8.bin
./score ef_trie.prob_backoff.8.8.bin ../test_data/sample_text
Первая команда построит структуру данных, вторая набрала образ sample_text текстового файла, содержащийся в test_data . Входной текстовый файл должен содержать одно предложение на строку, со словами, разделенными пространствами. Во время оценки файла мы не обертываем каждое предложение с маркерами <s> и </s> .
Выходной вывод может быть (OOV означает вне словаря ):
perplexity including OOVs = 493720.19
perplexity excluding OOVs = 1094.2574
OOVs = 55868
corpus tokens = 153583
corpus sentences = 6075
elapsed time: 0.037301 [sec]
Выполняемый print_stats может использоваться для сбора полезных статистических данных, касающихся использования пространства различных компонентов структуры данных (например, грамо-ID и последовательностей указателей для попыток), а также структурные свойства индексированного набора данных n -грамы (например, число уникальных количества, длины магистратуры/максимального диапазона, средний разрыв GRAM-IID-последовательности, ECC.).
В качестве примера, следующая команда:
./print_stats data_structure.bin
покажет статистику для структуры данных, сериализованной для файла data_structure.bin .
python Directory включает в себя простую обертку Python с некоторыми примерами. Проверьте это!
