Интерполяционный поиск по строкам

Question

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

Например: у нас есть массив длины 100 с массивом [0] = 0 и массивом [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).