Biểu diễn tối thiểu ma trận thưa thớt

Question

Tôi có một ma trận thưa thớt nhị phân lớn (bất kỳ ô nào cũng có thể giữ 0 hoặc 1 làm giá trị). theo thời gian, tôi muốn chụp nhanh toàn bộ ma trận. Ảnh chụp nhanh phải càng nhỏ càng tốt.

Ma trận đại diện cho bản đồ 2d và sự kiện diễn ra trong khu vực, vì vậy có nhiều khả năng có ảnh chụp nhanh giống như Ví dụ A so với ảnh chụp nhanh giống như Ví dụ B (cả hai đều có cùng số "1") mặc dù tôi cần hỗ trợ cả hai ví dụ trong thuật toán.

Example A: 
000000000000 
000000011000 
001100111100 
001111111100 
000000111100 
000001111100 
000000000000 

Example B: 
010010010010 
001000001000 
010010100100 
000100101010 
001000010010 
010010001100 
001000010000 

Kể từ khi dữ liệu có thể khác nhau từ đơn "1" di động đến 100% của các tế bào là "1" (Trong những trường hợp rất rất phía sau) Tôi nghĩ rằng tôi cần phải sử dụng nhiều hơn một thuật toán - và khi tải dữ liệu để tải nó bằng cùng một thuật toán đã lưu trữ nó.

Ví dụ khi chỉ có một ô, tôi sẽ lưu trữ chỉ mục của nó (và định danh cho thuật toán "chỉ mục") và khi 99% ma trận là "1", tôi sẽ lưu nó dưới dạng bitmap (và định danh cho Thuật toán "bitmap").

Vì vậy, tôi có được một thuật toán tổng quát như thế này:

1. Đối với mỗi algorithem đại diện - đại diện cho ma trận
2. Chọn đại diện nhỏ nhất
3. Store dữ liệu với các đại diện nhỏ nhất

Câu hỏi của tôi

1. Tôi có thể sử dụng thuật toán nào - ngoài lưu trữ Index/bitmap?
2. Có cách nào tốt để xử lý vấn đề này không?
3. Làm cách nào tôi có thể đề xuất giải pháp của mình là tối thiểu có thể?

dòng dưới cùng: Làm cách nào để lưu trữ ma trận bitmap theo cách tối thiểu?

EDIT Sử dụng trường hợp: Tôi có một ma trận thưa thớt mà tôi cần phải chuyển qua một phương tiện tốc độ băng tần rất thấp. Vì vậy, việc gửi ma trận nên chứa càng ít bit càng tốt, giả định rằng sức mạnh tính toán trên cả hai mặt của phương tiện là mạnh.

Answer 1

nén dữ liệu là một lĩnh vực lớn (bạn có thể start here), và không có câu trả lời dứt khoát cho câu hỏi của bạn. Nếu chúng tôi biết cách nén dữ liệu ở mức tối ưu, sẽ không có thuật toán nén mới mỗi năm;)

Điều đó được nói, ý tưởng hay là chọn một thuật toán tốt nhất trong bộ sưu tập và xác định nó trong tiêu đề. Trên thực tế, hầu hết các định dạng nén đều sử dụng loại lược đồ này.

Để trả lời câu hỏi của bạn:

gì các thuật toán:

• Sử dụng exising định dạng: PNG, GIF, hoặc 7zip đến tâm.
• Không nén: bitmap, rõ ràng, nhưng chỉ để đảm bảo chúng tôi đang nói về cùng một điều, bạn cần mã hóa 1 bit (và không phải 1 byte) cho mỗi phần tử. Bit truy cập không phải là dễ dàng có sẵn trong hầu hết các ngôn ngữ (đối với hầu hết các loại bool/boolean được lưu trữ trên một byte đầy đủ). Bạn phải sử dụng các hoạt động bitwise, tính năng ngôn ngữ chuyên biệt chẳng hạn như bitfields/bitsets hoặc thư viện. Ví dụ: C++, std::vector<bool> triển khai thực hiện bitmap thực (đơn giản bool[] thì không).
• Mã hóa Entropy: ý tưởng mã hóa hầu hết các cấu hình có thể xảy ra bằng cách sử dụng ít bộ nhớ hơn so với ít lưu trữ hơn.
  • lưu trữ thưa thớt, những gì bạn gọi là chỉ mục, nhưng trái với những gì bạn ngụ ý, nó hữu ích khi có rất nhiều, nhưng cũng rất nhiều số không (chỉ phủ nhận kết quả!). Trường hợp khi chỉ có một 0 hoặc chỉ một 1 là đối xứng và phải được xử lý theo cùng một cách. Trường hợp xấu nhất cho lưu trữ dự phòng là có nhiều trường hợp như số không.
  • mã hóa khối, nghĩa là bạn có thể lưu trữ 1111 trong ít hơn 4 bit nếu bạn biết đó là mẫu có khả năng. Nhưng điều này có nghĩa là một mô hình 4 bit khác (ít có khả năng) sẽ được lưu trữ bằng cách sử dụng hơn 4 bit, vì vậy hãy cẩn thận trong việc lựa chọn các mẫu của bạn. Có nhiều cách để thực hiện điều đó: các từ có kích thước cố định hoặc kích thước biến và mã hóa có thể là phụ thuộc vào dữ liệu tĩnh hoặc dữ liệu. Một số ví dụ là: RLE, Huffman, LZ biến thể (thuật toán dựa trên từ điển được sử dụng trong chương trình nén yêu thích của bạn)
  • dựa trên ý tưởng tương tự về không gian lưu trữ trên mỗi biểu tượng/khối dựa trên xác suất của nó, nhưng mã hóa toàn bộ dữ liệu trong một lần, thay vì tách nó thành các khối, thường dẫn đến các lược đồ mã hóa tốt hơn.
  • Vì dữ liệu của bạn là hai chiều, nên xử lý nó theo khối 2D thay vì khối 1D, ví dụ bạn có thể mã hóa các ô 8x8. JPEG để thực hiện điều đó.
• chuẩn bị dữ liệu: trước khi áp dụng entropy của bạn mã hóa thuật toán (một trong đó thực sự làm giảm kích thước dữ liệu), nó thường thú vị để áp dụng một song ánh (chức năng hai chiều, điều đó không làm giảm kích thước dữ liệu) để mã hóa kiến thức của bạn về mô hình dữ liệu.Trong trường hợp của bạn, bạn nói dữ liệu của bạn đại diện cho các sự kiện và những dữ liệu đó thường được nhóm đặc biệt. Có cách nào để thể hiện điều đó như một danh sách các sự kiện + cách họ truyền bá không? Hoặc bạn có thể sử dụng một số sơ đồ nén hình ảnh như Fourier transform hoặc một số loại wavelet transform. Hoặc bạn chỉ có thể sử dụng contour matrix (một khi sự thay đổi giá trị giữa hai tế bào, bằng không khi giá trị là hằng số), mà có thể làm tăng thưa thớt của ma trận của bạn (nó ở bạn dụ Một)

Chứng minh tối thiểu:

Không có thuật toán nén tối ưu chung, vì nén thực sự phụ thuộc vào phân bố xác suất dữ liệu của bạn. Thật vậy, bạn biết ma trận của bạn luôn giống nhau, bạn thậm chí không cần mã hóa nó. Bạn biết đó là một trong hai ma trận có thể, chỉ một chút là đủ để mã hóa cái nào.

Trong trường hợp tổng quát, của Shanon entropy ước tính số lượng tối thiểu lý thuyết của các bit cần thiết để mã hóa một thông điệp:

min = E(-log2(P(message))) 

nơi E là sự mong đợi trên tất cả các thư có thể và P là hàm xác suất. Tuy nhiên, trong thực tế, bạn không biết P, vì vậy tốt nhất bạn có thể làm tốt hơn thuật toán tốt nhất trước đó;)

Nói chung, bạn càng cố nén dữ liệu, chương trình càng đắt tiền , cả về tài nguyên thời gian chạy (chu kỳ CPU và bộ nhớ) và nỗ lực phát triển.

Một ví dụ

Chỉ cần đặt nó trong thực tế trên bạn dụ 1, để cung cấp cho bạn nguồn cảm hứng - ngay cả khi nó là một ý tưởng rất xấu để thiết kế từ 1 dụ, bởi vì nó hầu như không mang lại cho bạn đại diện xác suất!

dữ liệu ban đầu (tôi sẽ luôn luôn bỏ qua các tiêu đề kích thước, vì nó sẽ không thay đổi) - bitmap, 84 bit (25 người):

000000000000 
000000011000 
001100111100 
001111111100 
000000111100 
000001111100 
000000000000 

Trong chương trình index của bạn, bạn có đầu ra một danh sách position của những người. Nếu bạn khái quát hóa, bạn có thể làm việc với danh sách position + pattern. Ví dụ, pattern có thể là số lượng liên tiếp, do đó bạn không cần xuất nhiều vị trí cho các khối của các vị trí đó. Chúng ta hãy đi xa hơn, và nói rằng chúng ta mã hóa mô hình 2D, được xác định bởi:

• một kích thước 3-bit (0-7)

• một 1-bit hình dạng:

  • 0 nghĩa liên tiếp - ví dụ: 1111 là hàng có kích thước 4;

  • 1 nghĩa một hình vuông - ví dụ:

    11 
    11 
    

    là một hình vuông kích thước 2.

Sau đó, chúng ta hãy nói đi tương đối thay vì vị trí tuyệt đối, có nghĩa là mỗi position mã hóa bao nhiêu bạn tiến từ vị trí trước đó. Ví dụ của bạn, tôi chọn vị trí 5 bit. Sau đây là cách giải mã hoạt động:

-- block #1 
00001 position +1 
     absolute position from top-left, since this is the first block 
001 pattern-size 1 
0  pattern-shape is row 
     for size 1, square and row are the same 
     (which means my coding isn't optimal) 
-- block #2 
00100 position +4 
     relative to last position 1, this means position 5 
010 pattern-size 2 
1  pattern-shape is square 
-- decoded output below 
0100011000... 
0000011000... 
0000000000... 
............. 

Vì vậy, với chương trình này bạn có thể mã hóa dữ liệu của bạn sử dụng 45 bit:

10100 (position [0]+20 from top-left) 
010 0 (size: 2, shape: row) 
00110 (position [20]+6) 
010 1 (size: 2, shape: square) 
00100 (position +4) 
100 1 (size: 4, shape: square) 
01000 (position +8) 
100 0 (size: 4, shape: row) 
11011 (position +27) 
001 0 (size 1, shape: row) 

Ghi chú: Thông thường bạn muốn lưu trữ một tiêu đề để biết số các khối (5 trong trường hợp này), nhưng bạn có thể suy ra nó từ kích thước tải trọng của tệp/mạng. Cũng trong ví dụ này, chúng ta chỉ cần 3 kích thước mẫu (1,2,4) để chúng ta có thể lưu trữ kích thước trên hai bit và nâng cấp lên sức mạnh 2, làm cho tải trọng 40 bit, nhưng điều đó làm cho lược đồ quá chuyên biệt. Ngoài ra, cần phải có ít nhất một số vô nghĩa shape (ở đây có hai: 000/0 và 000/1), trong trường hợp bạn không có đủ bit trong position để mã hóa một "lỗ" lớn giữa các mẫu. Ví dụ ma trận này 20 x 3:

10000000000000000000 
00000000000000000000 
00000000000000000001 

Có những người ở vị trí 0 và 59. Vì tôi không thể mã hóa 59 trên như một bước nhảy 5-bit, chúng ta phải nhảy hai lần, và chúng tôi sẽ mã hóa nó như:

00000 (+0) 001 0 (a single 1) 
11111 (+31) 000 0 (nothing) 
11100 (+28) 001 0 (a single 1) 

Answer 2

Bạn đã đề cập một số cách rõ ràng để lưu trữ các bitmap và chỉ mục này của các ô 1. Ý tưởng chỉ mục có thể dễ dàng được mở rộng bằng cách mã hóa số nhận dạng cho phương pháp 'chỉ số' và số lượng các ô 1, theo sau là nhiều cặp tọa độ. Bạn thậm chí có thể thử nén theo nhóm bởi hàng (hoặc cột) như

rowNumber colNumber1 colNumber2 ... -1 

sử dụng -1 hoặc một số giá trị cờ khác để báo hiệu kết thúc của một hàng. Điều này có thể tiết kiệm rất nhiều không gian cho ma trận kích thước lớn chỉ với một vài mục. Bạn cũng cần phải lưu trữ kích thước ma trận.

Ví dụ A, bạn muốn nhận được (sử dụng 0 lập chỉ mục, khoảng trắng chỉ để có thể đọc)

7 12 //dimensions 
1 7 8 -1 
2 2 3 6 7 8 9 -1 
3 2 3 4 5 6 7 8 9 -1 
4 6 7 8 9 -1 
5 5 6 7 8 9 -1 

Đối với trường hợp của bạn, một ví dụ về một cách để lưu trữ nó có thể là như sau - bạn phải để thử nghiệm và xem mức độ thành công của nó khi 'nén' thông tin. Ý tưởng cho thuật toán xuất phát từ việc quan sát rằng trong ví dụ A của bạn, hầu như tất cả các hàng chỉ có một phần kết nối lớn duy nhất là 1s, được bao quanh bởi 0s.

Giả sử ma trận của bạn có thể có bất kỳ thứ nguyên nào, bước đầu tiên sẽ mã hóa đó. Vì vậy, đối với ma trận n * m, chỉ cần lưu trữ hai số nguyên đó.

Sau này, cho mỗi hàng, làm thế nào các câu hỏi sau:

• cửa hàng số lượng 0s kết nối ở bên trái.
• lưu trữ số lượng 1s được kết nối theo sau đây.
• lặp lại cho đến khi kết thúc hàng.

Để giải mã, bạn chỉ cần phải làm theo một quy trình như thế này:

• cho mỗi hàng (trong số hàng nhất định)
  • hãy count được số lượng các mục ma trận đọc cho đến nay. Initialise to 0
  • let next là boolean, đại diện cho giá trị mà số tiếp theo mã hóa. Khởi tạo thành false.
  • đọc số tiếp theo
    • chèn con số của các giá trị tương đương với next vào hàng thích hợp.
    • lật next
    • increment count bởi con số đó
  • vòng lặp cho đến khi count == m (nếu count > m một cái gì đó đã đi sai)
• vòng lặp cho đến khi tất cả các hàng đã được đọc

tôi hy vọng tôi đã giải thích ý tưởng khá tốt. Như tôi đã nói, tôi không biết nó sẽ hoạt động tốt như thế nào, nhưng nó phát sinh từ một quan sát về ví dụ của bạn. Để thực sự nén nó xuống, bạn có thể đảm bảo rằng mỗi mục nhập chỉ yêu cầu nhiều bit khi cần thiết để đếm đến (và không cao hơn) chiều rộng hàng (m trong mã giả của tôi.)

Ví dụ A sẽ xuất hiện như thế này (khoảng trắng chỉ để dễ đọc):

7 12 //dimensions 
12 
7 2 3 
2 2 2 4 2 
2 8 2 
6 4 2 
5 5 2 
12 

Bạn chỉ cần 4 bit cho mỗi số, nếu bạn đã tối ưu hóa điều đó.

tôi sẽ không cố gắng làm Ví dụ B, nhưng nó sẽ thực hiện tồi tệ hơn nhiều