해시 맵의 모든 값에서 하위 문자열을 효율적으로 검색하는 방법은 무엇입니까?

Question

나는 다음과 같은 방법으로 지정된 데이터가 다음과 같은 경우,

key = (<type:id>) | value = (<relevance-score>,<data>) 

자 :이 값이 해시 맵 같은 것을 넣어된다고 가정

<type:id> <relevance-score> <data> 

예 :

a:1 0.8 "This is a post by PhD" 
a:2 0.9 "Current rep of PhD is 3,800+" 
b:1 1.0 "Pikl F'Nandez is not an existing user on stackoverflow" 
c:2 1.0 "AJAX is a tag on stackoverflow" 
... 

을 하나는 키워드 PhD을 검색하는 것이고, 해시 맵의 두 항목에서 찾을 수 있습니다.

Example output: a:2, a:1 

쿼리 문자열도 Pikl 또는 Pikl F 또는 Pikl F'n 문자열 매칭 알고리즘이 갈 수있는 가장 좋은 방법이라는 것을 의미 할 수있다 : 나는 쿼리 문자열과 일치 관련성 점수의 순서를 내림차순으로, 모든 키를 검색 할 검색에 대해서.

현재 접근 : 해시 맵의 모든 값에 Boyer-Moore 알고리즘을 사용하고 결과 데이터를 최대 힙 (관련도 점수)에 저장합니다.

시간 복잡성 :

• 보이어 - 무어 : O(m+n)
• 총, q: # of keys in hashmap
• 는 또한 힙에서 값 터지는를 추가 할 필요가 각 값 O(q(m+n))합니다. O(s) 여기서 s은 일치하는 숫자입니다. s << q부터 위 (검색)가 지배적 인 비용이라고 말할 수 있습니다.

질문 :이 방법이 가장 효율적입니까? 보다 효율적인 방법이 있습니까? 다른 데이터 구조/알고리즘, 아마 내가 생각하지 않을 수 있습니다?

Answer 1

현재 접근 방식은 기본적으로 귀결 : 모든 데이터를 통해

1. 으로 반복하고 검색 문자열과 일치하는 사람을 찾을 수
2. 종류의 모든 관련성 점수에 따라 데이터를 일치 힙을 수행

유일한 차이점은 1을 수행하는 동안 2를 수행하고 있지만 결과 시간 복잡도가 동일하다는 것입니다.

각 문자열 검색 시간이 O(1)이라해도 문자열 검색을위한 총 시간은 O(q)이되고 정렬 시간은 O(slog(s))입니다. s << q 이후로 O(slog(s)) < O(q)을 청구하는 것이 합리적입니다. 즉, 문자열 검색에 걸리는 시간이 항상 지배적입니다.

내가 생각할 수있는 유일한 방법은 모든 문자열 검색에 걸리는 시간이 실제로 O(1)에 가까워 지도록 모든 데이터를 사전 처리하는 것입니다.질의 문자열이 무작위 하위 문자열이 아닌 단어 목록으로 보장된다면 더 쉬울 것입니다. 그러나 Pikl F'n과 같은 쿼리 문자열을 사용하면 데이터 사전 처리가 매우 어려워집니다. 본질적으로 얻을 수있는 쿼리 문자열 유형에 대한 정보가있는 경우 빠른 검색을 위해 그에 따라 데이터를 사전 처리 할 수 ​​있습니다.