고유 한 자연수 세트를 압축하고 두 세트를 비교하는 방법은 무엇입니까?

Question

웹 응용 프로그램은 양의 정수 집합 쌍을 비교합니다. 각 세트에는 고유 한 값만 있고210 000 000 (28 비트에 맞음)보다 크지 않습니다. 각 세트에서 최대 5 000 000 개의 값.

세트 A & B를 비교할 때 "A에 고유", "B에 고유", "A & B에 공통"의 결과 세트가 필요합니다. 특정 작업은 "집합 S에 숫자 N이 있습니까?"라는 질문에 대답하는 것입니다.

지금까지 프로젝트는 LAMP 스택에서 제한된 공유 호스팅 리소스에서 실행됩니다. 내가 생각해 낸 빠른 해결책은 더 많은 자원을 가진 호스팅 MySQL에 작업을 아웃소싱하는 것이 었습니다. 각 세트에 대한 임시 테이블, 숫자가있는 유일한 컬럼이 기본 인덱스입니다. 드물게 세트는 엔진 = 메모리에 들어가기에 충분히 작으며 빠릅니다. 그것은 효과가 있지만 너무 느립니다.

이 같은 메모리 내 집합을 유지하는 방법을 찾고, 그 안에있는 특정 번호를 검색하는 작업에 효과적입니다. 가능한 한 메모리 사용량을 줄입니다.

각 세트를 2^28 비트 (32Mb)의 비트 마스크로 코딩하는 아이디어가 떠 올랐습니다. 세트에있는 숫자 = 1 비트 세트. 5 mln numbers =210 mln에서 설정된 5 mln 비트. 많은 0 == 효과적으로 압축 할 수 있습니까?

나는 자전거를 발명하고있는 것처럼 보입니다. 바이너리 압축의 특별한 경우에 대한 "잘 알려진"해결책으로 안내해주십시오. 내 작업은 압축 된 집합을 통해 많은 검색이 필요하지만 그 초점은 크기 축소로 올바른 솔루션으로 보이지 않는 허프만 코딩에 대해 읽었습니다.

업데이트.Golomb coding에 대한 기사와 그 application to run-length encooding의 예가 발견되었습니다.

Answer 1

효율적인 반복을 허용하는 범위에서 표현 된 큰 정수 집합에 사용할 수있는 표준 압축 기술이 있지만 (교차점, 합집합, 차이 집합 등을 쉽게 할 수 있음) 임의 액세스를 허용하지 않습니다 "S는 N"입니다). 이 특정 문제의 경우 데이터 세트를 각각 약 7 비트로 줄이며 5,000,000 세트의 세트의 경우 약 8MB가됩니다. 유용 할 경우 아래에 설명하겠습니다.

크기가 210,000,000 비트 (대략 26MB 각각) 인 비트 벡터는 현대 프로세서의 벡터화 된 명령어로 빠르게 수행 할 수 있으므로 "is in N"쿼리와 비트 연산 모두에 대해 계산 효율이 높습니다 ; 5,000,000 요소 교차 계산을 위해 얻는 것보다 빠릅니다. 그것은 많은 기억을 소비하지만, 만약 당신이 그 많은 기억을 가지고 있다면, 그것을 위해 가십시오.

1. 정렬 집합을 (또는 정렬되도록) 다음

   세트 균일 지정된 크기의 무작위 샘플을 분산하는 경우 간단한 단지 최적 관한 압축 기술이있다 .

2. 집합 위해 세트의 각 요소에 대해서는 0

3. 의 "현재 값"

   가. 요소에서 "현재 값"을 뺍니다.

   b.그 차이는 적어도 32이고, 하나의 1 비트를 출력하고 차이로부터 32를 뺍니다.

   c. 하나의 0 비트를 출력하고 그 다음에 5 비트로 인코딩 된 차이를 출력합니다.

   d. 더 많은 요소

압축이 요소 당 약 일곱 비트가 발생합니다 나의 주장을 정당화하기보다 하나에 "현재 값"으로 설정 :

그것은 모든 요소는 6 개 비트를 차지할 것이 분명 (0 5 비트 델타 플러스); 또한 단계 3b에서 1 비트를 고려해야합니다. 그러나 모든 델타의 합계는 세트의 가장 큰 요소이며 210,000,000을 초과 할 수 없으므로 3b 단계를 210,000,000/32 회 이상 실행할 수 없습니다. 그래서 3b 단계. 단계 3c는 총 3700 만 개 또는 요소 당 7.4 비트 (실제로는 보통 이보다 조금 작을 것입니다) 동안 6 * 5,000,000 비트를 차지하면서 7 백만 비트 미만을 설명합니다.