tongrams
1.0.0
Tongrams는 다음 논문에 설명 된대로 압축 공간에서 큰 언어 모델을 색인하고 쿼리하는 C ++ 라이브러리입니다.
Giulio Ermanno Pibiri와 Rossano Venturini. Tongrams를 사용하는 경우이 서류를 인용하십시오.
보다 구체적으로, 구현 된 데이터 구조는 N- 그램을 해당 (정수) 주파수 수에 매핑하는 데 사용될 수 있으며,이를 끊어지는 무릎 제네 모델에 대한 백 오프 interpolated kmer-rey 모델에 대한 (부동 소수점) 확률 및 백 오프.
라이브러리에는 압축 된 TRIE 데이터 구조가 포함되어 있으며 N- 그램에 정수 식별자 (IDS)가 할당되고 압축 공간 내에서 효율적인 검색을 지원하기 위해 Elias -Fano 로 압축됩니다. 그러한 식별자의 컨텍스트 기반 리핑은 고정 길이 k (예 : 이전의 k 단어)의 컨텍스트에 따라 단어를 인코딩 할 수 있으며, 전체 어휘의 크기가 아니라 그러한 컨텍스트를 따르는 단어의 수에 의해 값이 값을 가진 정수 (유니-그램 수). TRIE 데이터 구조에 추가로 라이브러리는 일정한 시간 검색을 위해 최소한의 완벽한 해싱 (MPH)을 기반으로 모델을 구축 할 수 있습니다.
주파수 카운트를 저장하는 데 사용되는 경우 데이터 구조는 지정된 n- 그램의 발생 수를 반환하는 lookup() 작업을 지원합니다. 달리, 확률과 백 오프를 저장하는 데 사용될 때, 데이터 구조는 텍스트가 입력으로 주어지면 텍스트의 수신성 점수를 계산하는 score() 함수를 구현합니다.
이 안내서는 라이브러리에 대한 간단한 개요를 제공하고 몇 가지 예를 통해 그 기능을 설명하기위한 것입니다.
이 코드는 gcc 5.4.1, 7.3.0, 8.3.0, 9.0.0으로 Linux Ubuntu에서 테스트되었습니다. clang 7.3.0을 가진 Mac OS X El Capitan; clang 10.0.0을 가진 Mac OS X Mojave.
빌드에는 다음의 종속성이 필요합니다 : CMake and Boost .
--recursive 없이 저장소를 클로닝 한 경우, 구축하기 전에 다음 명령을 수행해야합니다.
git submodule init
git submodule update
UNIX 시스템에서 코드를 작성하려면 (중고 컴파일 플래그의 경우 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 count 파일은 Google 형식, 즉 행당 1 그램을 나열하는 n (주문)의 각 값에 대해 하나의 별도 파일을 따릅니다. 파일 (행)의 N- 그램의 총 수를 나타내는 파일 헤더 로이 형식을 강화합니다.
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
이러한 N 파일은 다음 규칙에 따라 이름을 지정해야합니다. <order>-grams , 여기서 <order> n 값의 자리 표시 자입니다. MPH 기반 모델 만 빌드 해야하는 경우 파일을 분류 할 수있는 반면, 선택한 어휘 매핑에 따르면 TRIE 기반 데이터 구조에 대한 접두사 순서 로 정렬해야하며, 이는 UNI-Gram 파일로 표시되어야합니다 ([1]의 3.1 항 참조). gzip 와 같은 표준 유틸리티로 입력 파일을 압축하는 것이 좋습니다. 유틸리티 sort_grams N -Gram Counts 파일을 접두사 순서로 정렬하는 데 사용될 수 있습니다. 결론적으로, 주파수 카운트를 저장하는 데이터 구조는 파일이 포함 된 디렉토리에서 구축됩니다.
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gz위에서 설명한대로 형식.
N -Gram 확률 및 백 오프를 나열하는 파일은 ARPA 파일 형식을 준수합니다. 반전 된 TRIE 데이터 구조를 구축하려면 ARPA 파일의 N- 그램을 접미어 순서 로 정렬해야합니다. 유틸리티 sort_arpa 그 목적으로 사용될 수 있습니다.
디렉토리 test_data 에는 다음이 포함됩니다.
gzip 로 압축합니다.queries.random.5K 5,000 n- 그램 (각 순서에 대해 1,000 명이고 무작위로 그려 됨)으로 구성됩니다.arpa 접미어 순서로 정렬 된 모든 ngram 을 효율적으로 구축하기 위해 목록을 작성합니다.sample_text Query 파일 (총 153,583 단어의 6,075 문장); Companion sample_text.LESSER 파일에는 처음 10 개의 문장 만 포함되어 있습니다. 다음 예제에서는 test_data 에 포함 된 샘플 데이터를 사용하는 것으로 가정합니다.
두 개의 실행 파일 build_trie 및 build_hash 각각 트리 기반 및 (최소 완벽한) 해시 언어 모델을 구축하는 데 사용됩니다. 사용에 대해 알 수있는 주장없이 실행 파일을 실행하십시오.
이제 몇 가지 예를 보여줍니다.
명령
./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> 확률 -20.0 및 양자 확률 ( --p ) 및 백 오프 ( --b )에 8 비트를 사용하는 것;arpa 라는 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를 실행하는 데스크탑 머신을 사용하여 2.3GHz Intel Core i5 프로세서 ( 데스크탑 Mac 이라고 함)를 장착했습니다. 이 코드는 모든 최적화 와 함께 Apple LLVM 버전 10.0.0 clang 과 함께 컴파일되었습니다 (코드 구축 섹션 참조). 우리는 또한 Ubuntu 19.04, 64 비트 ( 서버 Linux 라고 함) 하에서 인텔 (R) 코어 (TM) I9-9900K CPU @ 3.60 GHz로 일부 실험을 추가로 복제합니다. 이 경우 코드는 gcc 8.3.0으로 컴파일되었습니다.
데이터 구조 저장 주파수 계수의 경우 벤치 마크 프로그램 lookup_perf_test 를 사용하여 조회 쿼리 속도를 테스트 할 수 있습니다. 다음 예에서는 세 가지 다른 데이터 구조를 빌드하고 벤치마킹하는 방법을 보여줍니다. 재세포가없는 EF- 트리 , 순서 1을 갖춘 EF-RTRIE 및 순서 2가있는 PEF-RTRIE ([1]에 제시된 데이터 구조에 동일한 이름을 사용). 각 실험은 테스트 쿼리 파일 queries.random.5K 에서 1,000 회 반복됩니다. 벤치 마크 프로그램 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
이 (마이크로) 벤치 마크의 결과는 다음 표에 요약되어 있습니다.
| 데이터 구조 | 리핑 순서 | 바이트 X 그램 | µS X 쿼리 - 데스크탑 Mac | µS X 쿼리 - 서버 리눅스 |
|---|---|---|---|---|
| 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
첫 번째 명령은 데이터 구조를 구축하고 두 번째 명령은 test_data 에 포함 된 텍스트 파일 sample_text 점수로 작성합니다. 입력 텍스트 파일에는 줄 당 하나의 문장이 포함되어야하며 단어는 공백으로 분리되어 있어야합니다. 파일을 채점하는 동안 각 문장을 마커 <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 다양한 데이터 구조 구성 요소 (예 : TRIE에 대한 GRAM-ID 및 포인터 시퀀스)의 공간 사용과 관련된 유용한 통계 및 인덱스 된 N- 그램 데이터 세트의 구조적 특성 (예 : 고유 한 수, 최소/최대 범위, GRAM-ID 시퀀스의 평균 간격)에 관한 유용한 통계를 수집 할 수 있습니다.
예를 들어, 다음 명령 :
./print_stats data_structure.bin
파일 data_structure.bin 에 직렬화 된 데이터 구조에 대한 통계가 표시됩니다.
디렉토리 python 에는 몇 가지 예제가 포함 된 간단한 파이썬 래퍼가 포함되어 있습니다. 이것을 확인하십시오!
