Pesquisa de interpolação em strings

Para aqueles que não estão familiarizados com a pesquisa de interpolação, é um método procurar um valor em uma matriz classificada que seja potencialmente mais rápida que a pesquisa binária. Você observa o primeiro e o último elemento e (assumindo que o conteúdo da matriz esteja distribuído uniformemente) interpola linearmente para prever a localização.

Por exemplo: temos uma matriz de comprimento 100 com matriz [0] = 0 e matriz [99] = 99. Se estamos procurando por 80, é intuitivo tentar a matriz [80] sobre a matriz [50] e, se a matriz estiver próxima da distribuição uniforme, o tempo de execução esperado será reduzido paralog(log(N))

Para números, o local a ser verificado é definido pela equação:low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low]).

Um exemplo comum usado para mostrar a natureza intuitiva da pesquisa por interpolação é: imagine tentar encontrar a palavra 'amarelo' em um dicionário. Você não usaria a pesquisa binária e chegaria ao meio do caminho. Em vez disso, você iria para o local esperado.

Os seres humanos podem naturalmente interpolar linearmente seqüências de caracteres, mas não consigo descobrir como codificá-las. Como interpolamos linearmente seqüências de caracteres?