Sparse Matrix: Triplet Representation and Linked Representation

Ek aisi matrix jisme majority elements zero hote hain aur bohot kam elements non-zero hote hain, use Sparse Matrix kaha jata hai. Agar hum ek large sparse matrix (jaise 1000×1000 matrix jisme sirf 50 non-zero elements hain) ko standard 2D array me store karein, toh 99.99% memory useless zeroes ko store karne me waste ho jayegi.

Is memory wastage ko eliminate karne aur computational speed badhane ke liye sparse matrix compact representations use kiye jaate hain.

Sparse Matrix Representation Methods

Original 4x5 Sparse Matrix:
           Col 0  Col 1  Col 2  Col 3  Col 4
    Row 0 [  0      0      3      0      4   ]
    Row 1 [  0      0      0      0      0   ]
    Row 2 [  0      2      0      0      0   ]
    Row 3 [  0      0      0      5      0   ]

Non-zero Elements: (0,2)=3, (0,4)=4, (2,1)=2, (3,3)=5
Total Elements = 20, Non-Zero = 4, Zeroes = 16

1. Triplet Representation (3-Tuple / Coordinate Format)

Triplet representation me matrix ke non-zero elements ko ek 2D array me store kiya jata hai jisme exactly 3 columns hote hain:

1. Row: Non-zero element ka row index.
2. Column: Non-zero element ka column index.
3. Value: Actual non-zero value.

Is representation ki Row 0 (Header Row) special metadata store karti hai: [Total Rows, Total Columns, Total Non-Zero Elements].

Triplet Table for Above Matrix:

2. Linked Representation (Orthogonal List / Multi-Linked List)

Jab sparse matrix me dynamic insertions aur deletions frequent hote hain, toh triplet array inefficient hoti hai kyunki usme shifting karni padti hai. Aise cases me Orthogonal Linked List use ki jati hai jisme har node me 5 fields hote hain:

• Row Index
• Col Index
• Value
• Right Pointer (Next non-zero element in the same row)
• Down Pointer (Next non-zero element in the same column)

Agli post me hum cover karenge String Operations, Memory Storage, and Pattern Matching Basics.