Nadie sabe realmente cómo Google hace exactamente esto o tal vez no he hecho suficiente trabajo a domicilio. Pero el enfoque más obvio y eficiente del que se habla en los documentos es sobre una estructura de datos llamada árboles de búsqueda ternaria.
Los árboles de búsqueda TSTternary son más eficientes en el espacio en comparación con los intentos habituales. Veamos una muestra TST:
Cada nodo es como el nodo en BST, donde su hijo izquierdo representa un valor menor que la raíz, el hijo derecho es el que tiene un valor mayor que la raíz y el nodo que desciende exactamente de él tiene un valor igual al siguiente carácter en la palabra. Los nodos vacíos son nodos centinela para marcar el final de la palabra.
- ¿Cuál es el costo del servidor y el costo de mantenimiento por año / mes para sitios web como Flipkart y Amazon?
- ¿Qué tan grande es Evernote en términos de espacio de almacenamiento total?
- ¿Por qué las supercomputadoras usan grupos de servidores estándar en lugar de grupos de mainframes?
- ¿Cuál es la mejor manera de configurar un servidor privado compatible con HIPAA?
- ¿Cuál es la forma de desarrollar un sistema de inicio de sesión centralizado para servidores basados en Linux que utilizan SSH?
Entonces, cuando escribe mal una palabra, busca palabras en nodos adyacentes. Como en el ejemplo anterior, si la palabra deletreada es READC, le sugerirá que pregunte si quiso decir “READS”.
Todavía hay muchos más factores a considerar, pero supongo que esto debería hacer que la rueda ruede. Puede consultar este artículo para obtener más detalles sobre cómo podemos implementar esto:
Árboles de búsqueda ternaria
Créditos de imagen: Uso de DAG ternarios para la corrección ortográfica