対称距離行列 があるとしますA。たとえば、次のとおりAです4*4(行列の上と左の数字は、距離が測定される要素のインデックスであり、下の三角形のみを使用します)。
0 1 2 3
_____________
0 |0 0 0 0
1 |a10 0 0 0
2 |a20 a21 0 0
3 |a30 a31 a32 0
したがって、基本的に、 が の場合A、有用なエントリn*nしかありません。n*(n-1)/2対角線のゼロを削除すると、次の行列が得られます (Matlab と R に似ています)。
A= 0 1 2
_________
1 |a10 0 0
2 |a20 a21 0
3 |a30 a31 a32
np = n*(n-1)/2次に、要素を持つパック形式の 1 次元配列にこの行列を効率的に格納できます。
Ap = {a10, a20, a21, a30, a31, a32}
これにより、多くの検索 (たとえば、最も近い要素のペアの検索など) が高速化され、多くのスペースが節約されます (nが大きい場合に役立ちます) 。
との要素間の距離にアクセスすることは、パックされた行列の要素にアクセスすることiとj同じです。j+i(i-1)/2A[i,j] = Ap[j+i(i-1)/2]i>0, j<n-1, j<i
問題は、逆の状況にある場合、つまり、パックされた行列 に要素のインデックスがある場合、元の 2 つのインデックスをどのようにAp復元するかです。Ap[x]ijAAp[x] = A[i,j]
ありがとう！