나는 각 토큰이 (document_id, score) 쌍의 목록에 매핑되는 역 색인을 가지고 있습니다. 각 토큰의 값 목록은 내림차순 점수로 정렬되므로 가장 높은 순위의 문서가 먼저옵니다.역 색인에서 순서가 다른 값 배열의 교차점을 찾기위한 좋은 데이터 구조가 있습니까?
불행히도, 문서에서 토큰의 컨텍스트를 기준으로 점수가 조정되므로 모든 토큰에 대해 sorted-by-id가 동시에 정렬되도록 보장하는 것은 불가능합니다. 예를 들어 내 "문서"가 (id, score) = (1, 105)이고 "적포도주"가 (id, score) = (2, 100) 인 문자열 인 "와인 레드 아이폰"인 경우 "레드 와인"은 "레드"와 "와인"이 동일하지만 "와인은 <"빨간색 반전 인덱스 내가 ID를이 목록의 교차점을 찾을 필요가
"red" -> [(2, 100), (1, 95)]
"wine" -> [(1, 105), (2, 100)]
"iPhone" -> [(1, 115)]
처럼 보이도록 점수가 조절 될 수 있도록 와인 레드 아이폰 '의 중요성 ","< "아이폰"하는을 반환 모든 토큰 집합을 포함하는 문서 ID의 순위 목록 (표준 검색 문제). 위의 예에서 ID로 다른 문서 "화이트 와인은"이 가정 = 3, 점수 = 50, 그래서 역 색인은 이제 다음과 같습니다 : 검색 토큰이 {"red", "wine"} 경우,
"red" -> [(2, 100), (1, 95)]
"wine" -> [(1, 105), (2, 100), (3, 50)]
"white" -> [(3, 50)]
"iPhone" -> [(1, 115)]
그런 문제를 기본적으로 두 개의 토큰 (이 경우 [(2, 100), (1, 95)] 및 [(1, 105), (2, 100), (3, 50)])의 값을 가져 와서 문서 ID에 교차하므로 결과는 [(2, f(100, 100)), (1, f(95, 105))]입니다. f은 일부 평균 기능이며 중요하지 않습니다.
빠른 속도가 필요하고 가능한 한 적은 메모리를 사용해야합니다 (그러나 디스크 공간에는 문제가 없습니다). 경우에 따라 수천만 개의 고유 한 문서 ID에 매핑되는 수백만 개의 고유 한 토큰을 저장합니다.
지금까지 제약 조건을 충족시키기 위해 메모리의 압축을 위해 키 값 저장소 (각각 (id, score) 쌍이 하나의 값임)로 수정 된 trie에 데이터를 저장하는 작업을 망쳤습니다. inverted_index.get(token)은 배열을 반복하고 id -> score의 해시 맵을 반환하며 get은 해시 맵을 인수로 취하여 배열을 반복하고 다음 맵을 어셈블하는 동안 교차가 완료되도록 할 수 있습니다. 목록을 기본 목록과 대체 목록, 직렬화/직렬화 해제, 나머지는 ㅋ 그것들은 더 큰 문제를 해결하지 못하는 모든 일종의 반창고입니다. 문제에 대해 올바른 데이터 구조와 알고리즘을 사용하지 않고 있습니다. 현재 가장 큰 유스 케이스는 약 20m의 고유 한 문서 ID를 가지며 메모리에 완전히로드 될 때 약 400MB를 차지합니다.
내 애플리케이션에서 성능상의 가장 큰 병목 현상입니다. 특히 토큰 집합에 매우 많은 값이 포함 된 토큰이 포함되어있는 경우에 특히 그렇습니다. 필자는 기존 라이브러리를 사용하고 처음부터 무언가를 작성하고 현재 메소드를 최적화하는 등의 작업을 할 수 있습니다. 메인 스택은 파이썬이지만이 부분은 C++과 Cython으로 작성되었습니다. 파이썬 래퍼를 쓸 수있는 한 기존 소스를 알고 있다면 모든 언어에 대해 개방적입니다.
도움 주셔서 감사합니다.
좀 더 명확하게 설명 할 수 있습니까? 입력과 출력의 명확한 예를 작성하십시오. 나는이 목록의 교차점이 무엇을 의미하는지 이해하지 못합니다. –
@robertking 완료, 이제 더 명확 해 졌으면 좋겠습니까? 의견을 보내 주셔서 감사합니다. – gmoss
점수 별 정렬을 보장 할 수 없다면 ID 순서대로 정렬 할 수 있으며 순서에 맞지 않는 순서의 해시 테이블을 사용할 수 있습니까? –