상당히 큰 문자열 집합을 추적하기 위해 QSet을 사용하는 것은 좋지 않은 생각입니까? 각 문자열은 54 자 (108 바이트)입니다. 세트에는 수천 개의 항목이있을 수 있습니다 (정확한 숫자는 확실하지 않습니다). QSet은 삽입 및 멤버십 쿼리에만 사용됩니다.좋은 아이디어/나쁜 아이디어 : 매우 큰 데이터 세트에서 Qt의 QSet 사용하기?
좋지 않은 아이디어 인 경우 제안 사항에 동의하게됩니다. 내 54 개의 문자열은 6 개의 다른 문자로 구성됩니다 (예 : "AAAAAAAAABBBBBBBBBCCCCCCCCCDDDDDDDDDEEEEEEEEEFFFFFFFFF"). 이것은 아마도 압축을위한 좋은 후보자처럼 보입니다. 다른 제안 사항은 환영합니다.
기본 제공 세트를 사용하면 데이터의 성격에 따라 몇 가지 경로 수준 압축을 수행하게됩니다. 물론 이것은 컨테이너의 구현에 달려 있습니다.
기수 나무, 디지털 검색 나무, 빨강 검정 나무 등 일부 정보를 살펴보십시오. 각 문자열과 각 문자열을 저장할 필요는 없습니다. 예를 들어, 문제를 단순화하자 : 각각 최대 2 번 나타날 수있는 3 개의 문자 만 있고 각 문자열은 6 자입니다. 세 가지 문자열은 다음과 같습니다
AABBCC, AABCBC,이 예제와 함께 AACBCB
, 우리는 대신에 전체 18 개 노드의 6 + 3 + 4 = 13 개 노드의 최대를 사용하여 멀리 얻을 수 있습니다. 실용적이지는 않지만 당신이하는 일을 모릅니다. 모든 유형의 압축과 마찬가지로 접두사 패턴을 많이 사용할수록 압축률이 높아집니다.
편집 : 숫자 13과 18은 경로 수준 압축에서옵니다. 예를 들어, 스트레이트 C (인수/토론 용)에서 문자열 저장소 클래스를 배열 주위에 래퍼로 구현할 경우 패턴이 포함 된 메모리의 한 지점을 참조하는 각 포인터가있는 문자 포인터 배열을 사용할 수 있습니다. 위의 예에서 18 문자 (6 * 3 = 18)를 사용합니다. 배열의 크기를 더한다 (sizeof (char *)가 4라고 가정 해 봅시다), 우리 배열은 우리의 패턴을 저장하기 위해 3 * 4 바이트의 저장 공간 = 12 + 18 또는 30 바이트를 취합니다 ..
만약 내가 일종의 디지털 검색 트리에 패턴을 저장하면 약간의 트레이드 오프가됩니다. 트리의 노드는 1 바이트 (노드의 문자는 1 바이트, 다음 포인터는 4 바이트)보다 커야합니다. 각 노드는 5 바이트입니다.) 우리가 저장하는 첫 번째 패턴은 AABBCC입니다. 이것은 트리의 6 개 노드입니다. 다음은 AABCBC입니다. 첫 번째 트리의 AAB 경로를 다시 사용하고 CBC의 노드를 세 개 추가해야합니다. 우리는 AA를 재사용하고 CBCB를 위해 4 개의 새로운 노드가 필요합니다.총 13 노드 * 5 바이트 = 65 바이트의 저장 공간입니다. 그러나 데이터의 접두어에 길고 반복되는 패턴이 많은 경우 접두어 경로 수준 압축이 표시됩니다.
이것이 사실이 아니라면, 나는 허프만 또는 LZW 압축을 조사 할 것입니다. 이를 위해서는 정수가 연결된 패턴 사전을 만들어야합니다. 압축하면 사전을 만들고 텍스트의 각 패턴에 대한 정수 ID를 만듭니다. 그런 다음 텍스트의 패턴을 정수 ID로 바꿉니다. 압축을 풀 때, 당신은 그 반대입니다. 이 알고리즘에 대해 더 자세히 설명 할 시간이 없기 때문에이를 찾아야합니다.
단순함/시간면에서는 균형이 맞지 않습니다. 데이터에서 허용하는 경우 짧은 방법을 사용하고 기본 제공 컨테이너 만 사용하십시오. 그렇지 않은 경우 데이터에 맞게 조정해야합니다.
나는 이것이 내가 찾고있는 대답이 될 수 있다고 생각한다. 숫자 13과 18이 어디에서 왔는지 설명해 주시겠습니까? – dfetter88
@ dfetter88 업데이트 됨. 접두어 압축 대 일반 압축에 관한 제 발언을보십시오. 데이터는 선택한 컨테이너에 적합 할 수도 있고 적합하지 않을 수도 있습니다. 당신은 당신의 컨테이너가 임베디드되어 있는지 알아야하며 (링크 된리스트는 바이너리 검색 트리인가?), 데이터를보고 컨테이너의 오버 헤드가 수용 가능한지를 결정해야합니다. –
std :: set, map 또는 vector와 같은 다른 종류의 컨테이너에 대해 QSet을 사용하는 데 추가 문제가 없을 것이라고 생각합니다. 메모리 부족 문제에 대해 궁금한 점이 있다면, 저장해야하는 문자열의 수는 얼마나되는지, 더 간결하게 인코딩 할 수있는 방법이 있는지에 달려 있습니다. 예를 들어, 문자가 항상 같은 순서로 발생하지만 상대 길이가 다른 경우 모든 문자가 아닌 각 문자의 길이를 저장하십시오. 그러나이 문자열 중 50,000 개만이 약 5MB이고 그 중 500,000 개가됩니다 저장 용량이 50MB 밖에되지 않아 현대적인 컴퓨터의 메모리가 적당하지 않은 저장소 오버 헤드가 발생합니다.
아이디어는 좋지만 내 상황에서는 효과가 없을 것 같습니다. 내 문자열에는 항상 54 개의 문자가 있으며 각 문자는 항상 9 개입니다. 주문이 변경되는 유일한 것입니다. – dfetter88
이전 주석에서 "내 문자열에는 항상 54 자, 각 문자가 9 개가 있으며 순서 만 바뀝니다."
원시 문자열을 저장하지 마십시오. 실제로 사용 된 6 자로 압축 한 다음 QSet을 만들 수 있습니다. 사소한 압축은 {a, b, c, d, e, f}가 될 것이며, 문자 세트가 미리 알려졌다면 (6 문자 만) 16 비트 정수로 팩할 수도 있습니다.
캐릭터 세트는 사전에 알려져 있습니다. 항상 같은 6 자입니다. 항상 9 명이 있습니다. 주문은 변경되는 유일한 것입니다. 그럼에도 불구하고, 문자열은 여러 가지 방법으로 뒤섞 일 수 있습니다. "물건을 16 비트 정수로 묶어 라"고 말할 때, 어떻게 그렇게 암시하는지 모르겠습니다. – dfetter88
내 생각에 크리스는 캐릭터를 항상 한 캐릭터로 취급하고 나중에 여러 캐릭터로 펼칠 수있는 것처럼 항상 비슷한 캐릭터가 있어야한다고 ChrisV가 생각합니다. –
정확하게. 예를 들어, 문자 집합이 ABC이고 문자열 형식이 AABBCC (AA, BB, CC의 순서가 바뀌는 순서)이면 모든 것을 3 비트로 저장할 수 있습니다. 0 = AABBCC, 1 = AACCBB, 2 = BBAACC 등 에. – ChrisV
QSet은 좋은 생각처럼 들립니다. 기본적으로 해시 테이블이며 버킷 크기를 동적으로 최적화 할 수 있습니다. 완전한.
키 압축에 대한 또 다른 제안 : 기본 6 숫자 문자열 (A = 0, B = 1, ... F = 5로 생각)으로 처리하고 이진 (int)으로 변환하십시오.
QByteArray ba("112"); // instead of "BBC"
int num = ba.toInt(0, 6 /*base*/); // num == 44
6^8^3 < 2, 그래서 우리는 1 개 바이트 INT (또는 문자)와 문자열의 모든 3 개 문자를 대표하고 그것의이 ByteArray를 만들 수 있습니다. 그러면 54 바이트에서 18 바이트로 키의 크기가 축소됩니다.
잠깐, "우주의 크기"란 무엇입니까? 그것이 당신이 가지고있는 문자열의 양이라고 말해주지 마십시오 –
그것은 솔루션 공간입니다. 가능한 문자열의 총 수 (대부분이 중복)입니다. 나는 그 (것)들을 전부 해싱하지 않으며, 싶지도 않을 것이다. 아마 나는 더 신중하게 나의 질문을 말 했어야했다. OP를 업데이트하겠습니다. – dfetter88