Tenemos una lista de aproximadamente 150,000 palabras, y cuando el usuario ingresa un texto libre, el sistema debe presentar una lista de palabras del diccionario, que están muy cerca de las palabras en el texto libre.

Por ejemplo, el usuario ingresa: "Me gustaría comprar juguetes de legoe en Walmart". Si el diccionario contiene "Lego", "Coche" y "Walmart", el sistema debe presentar "Lego" y "Walmart" en la lista. "Walmart" es obvio porque es idéntico a una palabra en la oración, pero "Lego" es lo suficientemente similar a "Legoe" para ser mencionado, también. Sin embargo, nada es similar a "Car", por lo que esa palabra no se muestra.

Mostrar la lista debe ser en tiempo real, lo que significa que cuando el usuario ha ingresado la oración, la lista de palabras debe estar presente en la pantalla. ¿Alguien sabe un buen algoritmo para esto?

El diccionario en realidad contiene conceptos que pueden incluir un espacio. Por ejemplo, "nave espacial lego". La solución perfecta también reconoce estos conceptos de varias palabras.

Cualquier sugerencia es apreciada.