단어 사이의 최단 길이 검색 알고리즘

Question

단어 목록 간의 최단 거리를 찾는 알고리즘을 찾으려고합니다. 단어가있는 문서의 다른 위치를 보여주는 목록 사전이 있습니다.

일치

를 찾는이 설정된 알고리즘입니까 { "를"은 : [5, 13], "애플"{45} ... [2, 24, 15, "이다"} 이 모든 것이 겹치는 최단 길이? 예를 들어,이 단어에서 모든 단어를 찾을 수 있기 때문에 13-45가 답이됩니다.

Answer 1

나는 모든 단어가 들어있는 범위의 왼쪽 끝과 오른쪽 끝에 각각 left과 right의 두 위치를 유지합니다. 나는 또한 우선 순위 대기열을 유지할 것이고, 각 엔트리는 단어이고 단어의 위치 목록은 현재 왼쪽 가장자리 또는 그 이후에 발생한다.

초기화하려면 새 빈 우선 순위 대기열을 만들고 해당 단어의 전체 목록을 적절히 정렬하여 삽입하십시오. 각 단어를 삽입 할 때 right을 업데이트하면 단어가 처음으로 최대로 나타납니다. 데이터의 경우, 초기 설정은 두 번째 구성 요소의 첫 번째 구성 요소로 분류 배열 것처럼 나는 우선 순위 큐를 보여주는거야

left=2,right=45,queue=[["the", [2,15,24]], ["is", [5, 13], ["apple", [45]] 

될 것이다. 즉, 2 ("the"의 경우), 5 (is의 경우) 및 45 (apple의 경우)입니다. 이 초기화 중에 "the"에 대한 항목을 정렬해야했습니다. right은 45, 최대 값은 2, 5 및 45입니다.

left은 암시 적입니다. 우선 순위 대기열 앞에있는 것은 항상 처음 발생합니다. 이 시점에서 우리가 찾은 가장 짧은 범위는 2.45입니다.

그런 다음 다음 루프 반복 : 데이터와

remove the first entry from the priority queue 
shift its next occurrence into `left` 
check if left..right is a new shortest sequence 
if we've shifted off the last occurrence for this entry 
    stop 
otherwise, 
    update `right` to include this new next occurrence 
    insert the entry back into the priority queue 

을 연속 값은 다음과 같습니다

left=2,right=45,queue=[["the", [2,15,24]], ["is", [5, 13], ["apple", [45]] 
left=5,right=45,queue=[["is", [5, 13], ["the", [15,24]], ["apple", [45]] 
left=13,right=45,queue=[["is", [13], ["the", [15,24]], ["apple", [45]] 

우리 때문에 대기열에서 ["is", [13]] 터지는 오프 (13)를 이동 한 후, 종료의 어커런스의 목록. 아무 것도 남지 않습니다.