단어 목록이 포함 된 사전이 있는데 문자열 URL이 있습니다. 구분 기호를 사용하여 토큰으로 분해 된 후 URL에 포함 된 모든 단어를 찾고 싶습니다. 지금 당장, 특정 숫자보다 큰 각 토큰에 대해 사전의 각 단어를 테스트하고 있습니다 (java의 String에는 함수가 들어 있습니다). 예를 들어, 나는 www.wunderground.com을 위해 서라운드에서 "ground"와 같은 단어를 검색합니다.문자열의 단어를 효율적으로 검색합니다.
나는 그 일을하는 더 효율적인 방법이있을 것이라고 확신합니다. 어떤 아이디어?
사전을 HashMap에로드하면 각 후보 부분 문자열 ("wunderground", "underground", "der der", ..., "wundergroun", ..., " ", ..."지상 ", ...) 매우 빠르게, 구체적으로, O (1) 시간.
효율성을 측정하려면 : 얼마나 많은 단계를 수행해야하는지 파악하십시오. Big-O의 복잡성을 예측할 것입니다.
현재 알고리즘은 전체 사전을 반복해야합니다. 즉, 사전 크기, D 항목에 비례하여 작업해야합니다. 각 사전 단어에 대해 을 호출합니다. URL 단어 C의 크기에 비례하는 작업을 평균 사전 단어 크기에서 뺀 값 5를 호출합니다. 따라서 D * (C - 5) URL에있는 각 단어에 대해 O (D * (C - 5))를 입력하십시오.
해시 테이블을 만든 후에 조회 비용은 항목 수와 관계가 없습니다. C 문자의 각 URL 용어에는 C 하위 문자열이 있습니다. 적어도 5 자의 하위 문자열로 자르면 하위 문자열 (C - 5) 이됩니다. [글쎄, 기술적으로는 (C - 5) * (C - 4)/2이지만, 우리는 근사화 된 복잡성을 계산하고 있습니다. 이것은 큰 그림 근사값입니다.] 그래서 사전에서 모두 살펴 보는 비용은 (C - 5) 단계. 다시 말하지만 URL의 각 단어에 해당하며 사전 크기와는 무관합니다.
사전에 10,000 개의 항목이 있고 평균 URL 용어는 10 자입니다. 그런 다음 이전 알고리즘은 URL 단위 당 50,000 단계를 소요하며 해시 알고리즘은 당 단계를 25 단계로 취합니다. 이해가 되니?
그러나 때때로 단어는 "wunderground"의 "ground"와 같은 문자열에 포함됩니다. 나는 "wunderground"에 미리 색인을 붙일 수 없다. – user436390
런타임에 "wunderground"라는 용어를 모든 후보 단어 (하위 문자열)로 분할하고 각 후보를 테스트하여 HashMap에 있는지 확인해야합니다. 후보 목록은 오래 가지 않을 것입니다 (용어가 "wunderground"와 같이 짧다고 가정 함). 각 테스트는 빠를 것입니다. – Jerry101
알겠습니다. 고마워요. 실제로 각 토큰에 대해 사전 전체를 반복하는 것보다 빠를 수도 있습니다. – user436390