Búsqueda de interpolación en cadenas

Question

Para aquellos que no están familiarizados con la búsqueda de interpolación, es un método para buscar un valor en una matriz ordenada que es potencialmente más rápido que la búsqueda binaria. Observa el primer y último elemento y (suponiendo que el contenido de la matriz esté uniformemente distribuido) interpola linealmente para predecir la ubicación.

Por ejemplo: tenemos una matriz de longitud 100 con matriz [0] = 0 y matriz [99] = 99. Si estamos buscando a 80, es intuitiva para tratar array [80] sobre array [50], y si la matriz está cerca distribuido uniformemente, el tiempo de ejecución esperado se reduce a log(log(N))

Para los números, la ubicación para comprobar se define por la ecuación: low + ((toFind - sortedArray[low]) * (high - low + 1))/(sortedArray[high] - sortedArray[low]).

Un ejemplo común utilizado para mostrar la naturaleza intuitiva de la búsqueda de interpolación es: imaginar tratar de encontrar la palabra 'amarillo' en un diccionario. No usaría la búsqueda binaria y llegaría al punto medio. Por el contrario, iría a la ubicación esperada.

Los seres humanos pueden interpolar cadenas linealmente de forma natural, pero no entiendo cómo codificarlo. ¿Cómo se interpolan linealmente las cadenas?

Answer 1

Para encontrar la "distancia" entre dos cadenas, un método simple sería mirar la primera letra que es diferente entre ellas y asignar un valor numérico a cada una, luego tomar la diferencia.

Por ejemplo, la distancia de "a" a "y" sería 24 y la distancia de "y" a "z" sería 1, si a cada letra se le asignó un valor igual a su posición en el alfabeto.

Un método de mejor rendimiento pasaría por un diccionario para ponderar las distintas letras por lo comunes que son en palabras reales.

Otro refinamiento sería mirar dos caracteres - "aa" está más lejos de "bz" que "az" es de "ba", por ejemplo. Ir más allá de dos personajes no te compraría mucho.

La razón por la cual este método no es más popular es que complica el algoritmo de búsqueda binaria para obtener pocas ganancias. Si tuviera que medir el tiempo, incluso podría encontrar que la búsqueda binaria estándar es más rápida; lo que gana en menos comparaciones lo pierde en la complejidad de determinar distancias.

También tenga en cuenta que el peor de los casos de este algoritmo es peor que una búsqueda binaria. Considere, por ejemplo, buscar "ae" en la lista de "aa", "ab", "ac", "ad", "ae", "zz" - el valor atípico "zz" sesgará la búsqueda para que sea siempre probando el comienzo del rango de búsqueda. Se degrada a O (n) en estas condiciones.