문자열의 보간 검색

Question

보간 검색에 익숙하지 않은 사용자의 경우 이진 검색보다 잠재적으로 더 빠른 정렬 된 배열의 값을 검색하는 방법입니다. 첫 번째 요소와 마지막 요소를보고 (배열의 내용이 균일하게 분포되어 있다고 가정하면) 선형 적으로 보간하여 위치를 예측합니다.

예 : 우리는 array [0] = 0 및 array [99] = 99 인 길이 100의 배열을 가지고 있습니다. 우리가 80을 찾고 있다면 배열 [50]에 배열 [80]을 시도하는 것이 직관적이며, 배열이 균일하게 분포되어 있다면 예상 런타임은 log(log(N))

으로 줄어 듭니다. 숫자의 경우 확인 할 위치 방정식 : low + ((toFind - sortedArray[low]) * (high - low + 1))/(sortedArray[high] - sortedArray[low])에 의해 정의됩니다.

보간 검색의 직관적 인 특성을 과시하는 데 사용되는 일반적인 예는 다음과 같습니다. 사전에서 '노란색'단어를 찾으려고합니다. 이진 검색을 사용하지 않고 중간 지점으로 이동합니다. 오히려 예상되는 위치로 이동합니다.

인간은 자연스럽게 선형으로 문자열을 삽입 할 수 있지만 코드 작성 방법을 이해할 수는 없습니다. 문자열을 선형 보간하는 방법은 무엇입니까?

Answer 1

두 문자열 간의 "거리"를 찾으려면 간단한 방법은 두 문자 사이에 다른 첫 글자를보고 각 숫자 값을 할당 한 다음 차이를 취하는 것입니다.

예를 들어 "a"에서 "y"까지의 거리는 24이며, "y"에서 "z"까지의 거리는 각 문자에 알파벳의 위치와 동일한 값이 지정되면 1이됩니다.

더 나은 수행 방법은 다양한 단어가 실제 단어에 얼마나 공통적인지에 따라 다양한 문자를 가중치를 부여하는 사전을 통과하는 것입니다.

"aa"가 "bz"보다 "az"가 "ba"인 것보다 두 개의 문자를 보는 것이 좋습니다. 두자를 넘으면 너를 많이 사지 못할 것이다.

이 방법이 더 일반적이지 않은 이유는 많은 이득이 아닌 이진 검색 알고리즘을 복잡하게 만드는 것입니다. 시간을 내야한다면 표준 바이너리 검색이 더 빠를 수도 있습니다. 거리를 결정할 때 복잡성이 줄어든 적은 비교에서 얻을 수있는 것.

이 알고리즘의 최악의 성능은 이진 검색보다 나쁩니다. 예를 들어 "aa", "ab", "ac", "ad", "ae", "zz"의 목록에서 "ae"를 검색하는 것을 고려해보십시오 - 이상치 "zz"는 검색을 바이어스하여 검색 범위의 시작을 항상 시도합니다. 이 조건 하에서는 O (n)로 분해됩니다.