숫자의 벡터가 주어지면 : V = (v1, v2, ..., vn). 이 n 개의 숫자는 구별되거나 분류 될 필요가 없습니다.수의 벡터를 숫자로 유일하게 나타낼 수 있습니까?
우리는 몇 개의 벡터 V1, V2, ..., Vm을 가지고 있다고 가정합니다. Vi가 같지 않은 Vj에 대해 해당 숫자 f (Vi)와 f (Vj)가 동일하지 않도록 각 숫자를 정수 (정수 또는 실수)로 고유하게 나타낼 수 있습니다.
단순한 해법은 벡터를 나타 내기위한 ID로 0에서 m-1까지의 범위에 하나의 숫자를 갖는 것이지만, 우리는 이러한 종류의 솔루션이 각 벡터가 몇 개에 저장되는 경우에는 작동하지 않는다고 가정합니다 분산 된 기계. 즉, 두 시스템의 벡터 부분이 겹칠 수 있으며 알고리즘이 전역 적으로 벡터 분포를 알지 못합니다.
나는 입력이 원칙적으로 무한대라고 가정하고 출력 번호도 다르게 가정합니다. 간단한 방법은 연결의 n과 v1, v2, .. vn의 표현입니다. 일부 기본 b. 이들을 k- 비트 숫자로 표현한 다음 각 k- 비트 숫자에 연속 비트 (해당 k- 비트 그룹이 새 숫자를 시작하면 0, 동일한 숫자에 속하면 1)로 주석을 붙입니다. 이것은 평등성 테스트를 제외하고는별로 쓸모가 없지만 다른 것을 언급하지 않았습니다.
주변 지역 (즉, 주변 지점 p, q 주변에 자주 값 f (p), f (q)가있는 경우)을 위해 일부 공간 채우기 곡선을이 용도로 사용할 수 있습니다. Hilbert curve은 더 높은 차원으로 일반화하기에 약간 복잡하며 계산은 중요하지 않습니다. Z-order curve은 지역을 보존하는 데 그리 좋지 않지만 여러 가지 차원에서 구현하는 것이 거의 쉽습니다. 즉, 이진 표현의 비트를 인터리브하는 것뿐입니다.
OP는 '각 벡터를 고유하게 나타 내기 위해 숫자 (정수 또는 부동 소수점 숫자)를 사용합니다.' 출력 번호는 제한되지 않고 8 바이트가 최대 값입니다. 해시가 선택할 수있는 열쇠입니다. ;-) –
@EgorSkriptunoff 임의의 정밀도의 정수가 있고 부동 소수점 숫자도 가변 정밀도를 사용할 수 있습니다 (예 : 많은 표준 라이브러리에서 'decimal'유형을 참조하십시오).이 컨텍스트에서 OP가 출력이 k 비트 여야한다고 명시하지 않는 한 그런 제한이 없다고 가정합니다. – delnan
임의의 정밀도 숫자를 쉼표로 구분 한 문자열을 사용하는 것보다 더 잘 사용하고 있습니까? –
물론 n 개의 숫자가있는 경우 정보를 잃지 않고 같은 길이의 숫자로 압축 할 수 없습니다 (예 : 벡터에서 해시를 계산하면 해시 충돌이 발생합니다).
자바에서 BigInteger와 같은 무제한 공간이있는 경우 벡터를 인코딩 할 수 있습니다.
vector = [12345,4711,42]
1 2 3 4 5
0 4 7 1 1
0 0 0 4 2
100240370414512 <-- your unique number
뿐만 아니라 벡터의 크기를 인코딩하기 위해 너무 열심히하지 않아야, 그래서 이것은 서로 다른 크기의 벡터를 위해 일할 것입니다 : 벡터의 길이가 고정되는 것을 가정하면, 당신은 단순히 몇 가지 "연동"패턴을 사용할 수 있습니다 잘 (예 : 길이를 8 진수로, 8을 "접두사"로 사용).
해시가 필요합니다. –
@EgorSkriptunoff 출력이 고정 크기 인 경우 해시 일 뿐이며 충돌의 위험에 직면하게됩니다 (비둘기 원리에 따라). – delnan
@delnan - 64 비트 해시 충돌 가능성을 얻으려면 약 2^32 마리의 비둘기가 있어야합니다. :-) –