두 개의 이름 목록 간의 일치를 결정하는 방법은 무엇입니까?

는 내가 가진 : 100 만 대학생의 이름과 3 백만 은행 고객 이름 난 (비슷한 문자열 유사한 해시 값이) 해싱에 따라 수치 값으로 문자열을 변환하는 관리 두 개의 이름 목록 간의 일치를 결정하는 방법은 무엇입니까?

합니다. 값이 최소 60 % 이상으로 페어링되는지 확인하기 위해 이러한 두 세트 간의 상관 관계를 어떻게 확인할 수 있습니까?

ICC를 사용하여 이것을 달성 할 수 있습니까? ICC는 양방향 무작위로 어떻게 작동합니까?

긴급하게 필요한만큼 빨리 답변하십시오.

출처

2011-03-03 Anonymous

'최소 60 %까지 페어링'이란 무엇을 의미합니까? 학생 이름의 60 % 이상이 일치하는 고객 이름을 갖고 있다는 것을 의미합니까? 고객 이름의 60 %가 학생 이름과 일치합니까? ("일치"라는 편안한 감각이 없다면 불가능합니다!) 다른 것? 내 추측으로는 통계 분석에 문제가 없다는 것입니다. 두리스트/세트/배열을 비교하는 알고리즘을 코딩하는 문제입니다. 그렇다면 SO가이 질문에 더 나은 장소 일 수 있습니다. –

왜 이렇게해야하는지 조금 말할 수 있습니까? 나는 합법적 인 이유를 생각하는 데 어려움을 겪고있다. 분명한 사실이 있으면 제가 사과드립니다. – onestop

@onestop 나는이 사이트를 방문하는 질문자의 동기를 저버리지 않을 것이라고 확신하기 때문에 "합법적"이 아닌 "통계적으로 유용한"글을 써야한다는 것을 분명히 밝히고 싶다. –

이러한 종류의 엔티티 해상도 등은 일반적으로 쉽지만 여기서는 해싱 방식에 놀랐습니다. 해싱은 엔티티 해결에 중요한 정보를 잃어 버립니다. 따라서 가능하면 원래 문자열 대신 해시를 사용하지 않아야합니다. 옵션을 원래의 문자열을한다하여 가정

은, 당신이 그런 짓을 할 것이다 :

목록 A (1M), 목록 B (3M)

// First, match the entities that match very well, and REMOVE them. 
for a in List A 
    for b in List B 
    if compare(a,b) >= MATCH_THRESHOLD // This may be 90% etc 
     add (a,b) to matchedList 
     remove a from List A 
     remove b from List B 

// Now, match the entities that match well, and run bipartite matching 
// Bipartite matching is required because each entity can match "acceptably well" 
// with more than one entity on the other side 
for a in List A 
    for b in List B 
    compute compare(a,b) 
    set edge(a,b) = compare(a,b) 
    If compare(a,b) < THRESHOLD // This seems to be 60% 
     set edge(a,b) = 0 

// Now, run bipartite matcher and take results

이 알고리즘의 시간 복잡도 는 O (n1 * n2)이며, 그다지 좋지 않습니다. 이 비용을 피할 수있는 방법이 있지만 특정 엔터티 확인 기능에 따라 다릅니다. 예를 들어, 성이 일치해야한다면 (60 %를 줄이기 위해) 성의 첫 번째 문자 쌍으로 분할 된 하위 목록을 A와 B로 만들고 해당 알고리즘 사이에서이 알고리즘을 실행하면됩니다 명부. 그러나 "Nuth"라는 성이 "Knuth"등과 일치해야합니다. 이름 비교 기능이 무엇인지에 대한 지역 지식은이 문제를보다 잘 분열하고 정복하는 데 도움이 될 수 있습니다.

출처

2011-03-27 05:26:59 Josh

두 개의 이름 목록 간의 일치를 결정하는 방법은 무엇입니까?

답변

관련 문제