¿Os habéis preguntado alguna vez qué algoritmo emplea Google cuando te sugiere una búsqueda que has escrito mal?

Por ejemplo, si te equivocas escribiendoy en lugar de teclear "libros", buscas "lirbos", Google te saca el siguiente mensaje:

Bien, no sé el algoritmo exacto que Google emplea, pero yo he encontrado uno que creo que sienta la base de todos: el algoritmo Soundex (mejor ver la explicación en ingles del algoritmo)

Básicamente, trata de indexar palabras parecidas a través de su pronunciación. El psudocódigo es el siguiente:

1. Retain the first letter of the string
2. Remove all occurrences of the following letters, unless it is the first letter: a, e, h, i, o, u, w, y
3. Assign numbers to the remaining letters (after the first) as follows:
* b, f, p, v = 1
* c, g, j, k, q, s, x, z = 2
* d, t = 3
* l = 4
* m, n = 5
* r = 6
4. If two or more letters with the same number were adjacent in the original name (before step 1), or adjacent except for any intervening h and w (American census only), then omit all but the first.
5. Return the first four bytes padded with 0.

Y aquí hay una implementación en Java y otra implementación en Java.