Поиск по интерполяции по строкам

Question

Для тех из вас, кто не знаком с поиском интерполяции, это метод поиска значения в отсортированном массиве, который потенциально быстрее, чем двоичный поиск. Вы смотрите на первый и последний элемент и (при условии, что содержимое массива равномерно распределено), линейно интерполировать, чтобы предсказать местоположение.

Например: у нас есть массив длиной 100 с массивом [0] = 0 и array [99] = 99. Если мы ищем 80, интуитивно попробуйте массив [80] по массиву [50], и если массив близок к равномерно распределенному, ожидаемое время работы сводится к 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». Выйдя за пределы двух персонажей, вы не купите много.

Причина, по которой этот метод не является более популярным, заключается в том, что он усложняет алгоритм бинарного поиска для не большого выигрыша. Если бы вы были в это время, вы могли бы даже найти, что стандартный бинарный поиск быстрее; что вы получаете за меньшее количество сравнений, которые вы теряете в сложности определения расстояний.

Также обратите внимание, что наихудшая производительность этого алгоритма хуже, чем двоичный поиск. Рассмотрим, например, поиск «ae» в списке «aa», «ab», «ac», «ad», «ae», «zz» - выброс «zz» будет искажать поиск, всегда пробуя начало диапазона поиска. Он деградирует до O (n) в этих условиях.