200 개의 문자열이 주어 졌을 때, 관계 값의 LUT를 키잉하는 좋은 방법은 무엇입니까

Question

200 개의 문자열이 있습니다. 각 문자열은 다른 모든 문자열과의 관계 (0에서 1 사이의 부동 소수점으로 측정 됨)를가집니다. 이 관계는 양방향입니다. 즉, 관계 A/B == 관계 B/A. 이것은 n (n-1)/2 관계 또는 19,800을 산출합니다. 내가 원하는 무엇

내가 빨리 관계 값을 찾을 수있는 두 단어를 부여하도록 조회 테이블에서 이러한 관계를 저장합니다.

저는 C++을 사용하고 있으므로 LUT를 저장하기 위해 std :: map을 사용할 것입니다. 문제는이 목적에 가장 적합한 키가 무엇인가하는 것입니다.

키는 고유해야하며 두 단어 모두에서 신속하게 계산할 수 있어야합니다.

내 접근 방식은 각 단어 쌍에 고유 한 식별자를 만드는 것입니다. 예를 들어 "사과"와 "오렌지"라는 단어가 주어지면 "appleorange"(알파벳 순서, 가장 작은 것부터)로 결합하여 핵심 가치로 사용합니다.

이것은 좋은 해결책입니까? 아니면 누군가가 더 똑똑한 것을 제안 할 수 있습니까? :)

Answer 1

기본적으로 매개 변수의 순서가 중요하지 않은 추가 된 속성을 사용하여 두 개의 매개 변수의 기능을 설명합니다. (I 가능한 모호성을 제거하기 위해 두 단어 사이에 혼수를 넣어 또는 같은 제안) 순서를 변경 할 때 단어 사이의 모호함이없는 경우

귀하의 접근 방식은 작동합니다. 모든 2D 배열도 사용할 수 있습니다.

아마 관계의 값을 찾기 위해 시도하기 전에 (간단한 맵을 사용하여) 몇 가지 고유 한 식별자를 각 키워드를 변환,하지만 당신이 제안하는 것과 많이 변경되지 않습니다.

Answer 2

부스트/tr1이 허용되면, 문자열 쌍을 키로 사용하여 unordered_map으로 이동합니다. 주요한 질문은 다음과 같다 : 문자열의 순서는 무엇인가? 이것은 어휘 첫 번째 문자열로 시작하는 해시 함수에 의해 처리 될 수 있습니다.

비고 : 이것은 연구가 아닌 디자인 문제를 읽은 후 제안 사항 일뿐입니다.

Answer 3

"빨리"어떻게 빠르게됩니까?

std::map<std::set<std::string>, double> lut; 

다음

당신이 "사과"를 삽입 그래서 만약 키가, 두 단어의 set이며, "오렌지 : 당신이 두 단어의 순서에 대해 걱정하지 않는다 감안할 때,이 같은지도를 시도해 볼 수도 있습니다 "다음 순서는"주황색 ""사과 "와 같으며 set은보다 작음 연산자를 지원하므로 맵에서 키로 작동 할 수 있습니다. 참고 : 나는 의도적으로 거기에 문제가 주어진 열쇠에 pair을 사용하지 않았다.

나는이 프로파일과 같은 아주 기본적인 것으로 시작해서, 조회하기 전에 얼마나 빨리/느려지는지 등을 볼 것이다. 당신은 2 차원 배열의 두 인덱스를 사용 후, 당신은 200 개 문자열 정렬 된 배열을 만드는 경우

Answer 4

, 당신은 이진 검색은 두 문자열의 일치하는 인덱스를 찾을 수 있습니다 ... 아무것도 똑똑 할 필요가있는 경우 관계 값을 찾으십시오.

Answer 5

200 개의 문자열이 배열에 있으면 20,100 개의 유사도 값도 1 차원 배열에 포함될 수 있습니다. 배열에 색인을 붙이는 방법은 모두 다 내려갑니다. x와 y는 유사성을 원하는 문자열의 인덱스라고 가정합니다. 필요하다면 x와 y를 교체하여 y> = x가되도록 한 다음, 큰 배열에서 항목 i = x + y (y + 1)/2를 봅니다.

(0,0), (0,1), (1,1), (0,2), (1,2), (2,2), (0,3), (1,3) ... 항목 0,1,2,3,4,5,6,7 ...

이렇게하면 공간이 최적으로 사용되며 더 빠르게 찾을 수 있습니다. 지도. 나는 효율성이 적어도 C++을 사용하고 있기 때문에 당신에게 중요하다고 생각합니다!

[y = x 인 자체 유사성 값에 관심이 없다면 대신 i = x + y (y-1)/2를 사용하십시오.]