En primer lugar, tienes tu notación Big Oh completamente equivocada. No puede mezclar el tamaño de su cuerpo (número de teclas) con el tamaño de las teclas. El cálculo de Levenshtein solo depende del tamaño de la clave y la consulta, y cada clave, como dijiste, es de 1 a 5 elementos o quizás 100. No importa porque es CONSTANTE fijo en la longitud máxima de la clave si quieres un límite superior.
Por lo tanto, su algoritmo siempre es O (n) independientemente de cómo calcule Levenshtein. Puede ser O (n * 100 * 100) u O (n * 5 * 5) pero sigue siendo lineal.
Dicho esto, a veces O (n) no siempre es aceptable, si tiene millones de claves, es posible que no desee probar cada clave para su consulta. Una forma de resolver eso es indexar n-gramos o las rotaciones de sus teclas para cada tecla y luego buscar los n-gramos o rotaciones que puede extraer de su consulta. Luego, sobre las teclas recuperadas, verifique si la distancia de Levenshtein coincide o no con la consulta.
Por ejemplo, si tiene una clave “hola” y utiliza rotaciones, indexa:
- Si la compresión sin pérdida es completamente reversible, ¿por qué no omitimos un paso y solo usamos los archivos en su estado comprimido?
- Un hombre llega a su oficina en 2 horas y regresa en 3 horas. La ruta a su oficina incluye un sendero inclinado hacia arriba, 8 km y senderos inclinados hacia abajo. Cada vez que viaja hacia arriba, su velocidad es de 60 km / h, mientras que en un plano de 80 km / h, y cubre hacia abajo a una velocidad de 100 km / h. ¿A qué distancia está su oficina?
- Cómo aprender a escribir buenos algoritmos
- ¿Por qué la programación dinámica se llama programación dinámica?
- ¿Cuál es la prueba del algoritmo KMP?
hola $
ello $ h
llo $ he
lo $ hel
o $ infierno
$ hola
(todos apuntando a la tecla “hola”)
Luego, cuando su consulta sea “hola”, puede buscar rotaciones como “ello *” “h *”, “o $ *”, etc. no buscará en todo el conjunto de llaves. Entonces estarás en una complejidad sub-lineal.
Si la distancia es 1, es muy fácil construir las rotaciones que son útiles para usted, ya que sus opciones son eliminar un carácter de la consulta o agregar un carácter a la consulta. Si la distancia es 2, también es fácil soltar 1/2, agregar 1/2 o modificar 1.
Los N-gramos consumirán menos espacio que las rotaciones, pero tienen más falsos positivos.
Levenshtein con distancia 5 es realmente inusual, ya que coincidirá con teclas que realmente no tienen nada que ver con su consulta.
Todo eso se debe a su pregunta sobre cómo evitar sondear cada tecla. Ahora:
Tengo la sensación de que usar un algoritmo eficiente para calcular levenshtein y buscar linealmente cada tecla es una solución eficiente. Eche un vistazo al algoritmo bitap usando en agrep (algoritmo Bitap)
Finalmente, si clasifica sus claves y puede permitirse el lujo de no coincidir si el primer carácter es diferente, puede simplemente indexar el primer carácter de sus claves y Bitap sobre esas claves candidatas. Eso será realmente rápido y sencillo de codificar.
