La forma más eficiente de implementar una búsqueda fonética

Question

¿Cuál es la forma más eficiente de implementar una búsqueda fonética en C++ y/o Java? Por búsqueda fonética me refiero a sustituir vocales o consonantes que suenan similares. Esto sería especialmente útil para los nombres porque a veces los nombres de las personas tienen una ortografía extraña.

Estoy pensando que podría ser eficaz para sustituir las vocales y algunas consonantes. También puede ser útil incluir algunos casos especiales como E silenciosas al final o F y PH. ¿Sería mejor usar cstrings o cadenas en C++? ¿Sería mejor almacenar una copia en la memoria con los valores sustituidos o llamar a una función cada vez que buscamos algo?

Answer 1

Soundex junto con sus variantes es el algoritmo estándar para esto. Utiliza reglas fonéticas para transformar el nombre en un código alfanumérico. Los nombres con el mismo código están agrupados.

En cuanto a la implementación de la búsqueda, usaría una estructura de datos que mapee cada código soundex a la lista de nombres que tienen ese código. Dependiendo de la estructura de datos utilizada (una tabla hash o un árbol), la búsqueda podría hacerse a tiempo constante en logarítmico en la cantidad de códigos soundex distintos.

No estoy seguro de qué quiere decir exactamente por cstring (Microsoft CString?) Pero la clase estándar std::string estará perfectamente bien para este problema y sería mi elección preferida.

Answer 2

Además Soundex encontrará también la Metaphone o doble Metaphone algoritmo de fonética, lo que parece ser una mejora para la pronunciación Inglés y es un bastante nuevo algoritmo.

Para la pronunciación alemana uso el "Kölner Phonetik".

Apache Commons Codec le da una muy simple Java aplicación de esos algoritmos básicos (Soundex, Metaphone, ...) http://commons.apache.org/codec/ Por ejemplo consulte el Javadoc para el soundex: http://commons.apache.org/codec/apidocs/org/apache/commons/codec/language/Soundex.html

Justo mediante la tipificación siguiente código que el valor fonético de la cadena:

Soundex soundex = new Soundex(); 
String phoneticValue = soundex.encode("YourString"); 

Y a continuación, sólo tiene que hacerlo para dos cuerdas y comparar los valores fonéticos. Hava un vistazo a la siguiente post si usted está comparando dos cadenas, porque los iguales() métodos es sólo blanco y negro, y tal vez le gustaría saber cuántas% que es coincidente:

How to compare almost similar Strings in Java? (String distance measure)