거대한 데이터 세트에서 각 항목의 수를 효율적으로 추출하는 방법은 무엇입니까?

Question

문제는 다음입니다 :

• 입력 : 위키 백과의 모든 기사 (텍스트의 33기가바이트)
  
• 출력 : SQLite는 파일 위키 백과에서 각 단어 skipgram (최대 K 건너 뜁니다와 N-g)의 수입니다.

출력 테이블 스키마는 다음과 같습니다

INSERT OR REPLACE INTO [tokens] VALUES (@token, COALESCE((SELECT count FROM [tokens] WHERE token=@token), 0) + 1) 

문제와 :

CREATE TABLE [tokens] ([token] TEXT UNIQUE NOT NULL PRIMARY KEY, [count] INTEGER NOT NULL 

순진 접근 방식은 각 skipgram에 대해 우리가 기존의 레코드에 테이블이나 증가 카운터에서 새로운 기록을 만들 수 있다는 것입니다 이 방법은 인덱스가 지속적으로 업데이트되고 데이터베이스가 몇 기가로 커질 때 업데이트가 매우 느립니다. 우리는 색인없이 "토큰"테이블을 만들고 처리가 끝나면 색인을 추가함으로써이를 해결할 수 있습니다.

테이블을 스캔해야하는 선택문 SELECT count FROM [tokens] WHERE token=@token은 성능이 크게 저하되는 문제가 있습니다.

내가 지금까지 발견 한 가장 좋은 방법

(나는 C#을 사용하고있다) 다음입니다 :

1. 이 토큰을 계산하기 위해 Dictionary<string,int>을 만듭니다.

2. RAM에 들어가기에는 너무 커질 때까지 사전에 토큰을 추가하십시오.

3. 인덱스가없는 임시 테이블에 사전에서 토큰을 삽입 (업데이트하지 않음). 토큰이있는 경우

   CREATE TABLE [temp] ([token] TEXT, [count] INTEGER) 
   

4. , 사전을 취소하고 토큰 테이블에 임시 테이블 2.

5. 복사 토큰 단계로 이동합니다 :

   INSERT INTO [tokens] SELECT [token], SUM([count]) AS [count] FROM [temp] GROUP BY [token] 
   

를 표는 다음과 같은 스키마를 가지고

이 방법은 데이터 집합을 처리하는 데 "단 24 시간"이 걸리지 만 5 단계는 24 시간 중 22 시간이 걸리기 때문에 최선의 방법이라고 생각하지 않습니다.

이 문제를 해결할 수있는 대안이 있습니까?

P. 내 응용 프로그램은 단일 스레드이며 트랜잭션 내에서 위의 삽입을 일괄 처리 (배치 당 100000 개)로 만듭니다.

Answer 1

나는 SET TRANSACTION ISOLATION READ UNCOMMITTED을 추가 할 것을 제안합니다. 즉, 카운트가 약간 떨어져있을 가능성이 있으며, 특히 여러 개가 동시에 삽입/업데이트하려고하는 스레드 환경에서 가능할 수 있습니다.

Answer 2

나는 동일한 정의를 가진 다른 테이블을 생성하고, 특정 상태로 테이블을 채우고, 결과를 메인으로 병합하고, 테이블을 제거하고, 다음 항목 세트를 처리 할 것을 제안합니다.

Answer 3

많은 여유가 있다면 ....

토큰을 계산하지 말고 하나의 테이블에 모든 토큰을 추가하고 토큰을 구성하는 인덱스를 만듭니다. 다음 번에 토큰 하나 모두 추가

CREATE TABLE tokens (token TEXT); 
CREATE INDEX tokens_token ON tokens (token ASC); 

...

INSERT INTO tokens VALUES ('Global Warming'); 
INSERT INTO tokens VALUES ('Global Cooling'); 

결국 이것은 "계산 꽃을 사용하기에 좋은 장소처럼 소리 SELECT ... GROUP BY

SELECT token, COUNT(0) token_count FROM tokens GROUP BY token 

Answer 4

실행 필터 ".

데이터를 두 번 통과해야하며 약간 경험적이지만 빠른 속도 여야합니다. 블룸 필터를 사용하면 일정한 시간 내에 세트 삽입 및 존재 테스트를 수행 할 수 있습니다. 계수 블룸 필터는 존재 여부를 추적하는 일반적인 블룸 필터와 달리 특정 값이 몇 개 있는지를 계산합니다.