Самый эффективный способ реализации фонетического поиска

Каков наиболее эффективный способ реализации фонетического поиска в С++ и/или Java? По фонетическому поиску я подразумеваю подстановку гласных или согласных, которые звучат одинаково. Это было бы особенно полезно для имен, потому что иногда имена людей имеют странные варианты написания.

Я думаю, что было бы полезно заменить гласные и некоторые согласные. Также может быть полезно включить некоторые специальные случаи, такие как тихий E в конце или F и PH. Было бы лучше использовать cstrings или string в С++? Было бы лучше хранить копию в памяти с замещенными значениями или вызывать функцию каждый раз, когда мы что-то ищем?

Ответ 1

Soundex вместе с его вариантами является стандартным алгоритмом для этого. Он использует фонетические правила для преобразования имени в буквенно-цифровой код. Имена с таким же кодом группируются вместе.

Что касается реализации поиска, я бы использовал структуру данных, которая отображает каждый код soundex в список имен, имеющих этот код. В зависимости от используемой структуры данных (хэш-таблицы или дерева) поиск может выполняться во времени, которое либо является постоянным по логарифмическому числу различных звуковых кодов.

Я не уверен, что именно вы подразумеваете под cstring (Microsoft cstring?), но стандартный класс std::string будет отлично подходит для этой проблемы и будет моим предпочтительным выбором.

Ответ 2

Кроме Soundex вы найдете также фонетический алгоритм Метафон или Двойной метафон, который, по-видимому, является улучшением для английского произношения и является совершенно новым алгоритмом.

Для немецкого произношения я использую "Kölner Phonetik".

Apache Commons Codec предоставляет вам очень простую Java реализацию этих основных алгоритмов (Soundex, Metaphone,...) http://commons.apache.org/codec/ Например, см. Javadoc для soundex: http://commons.apache.org/codec/apidocs/org/apache/commons/codec/language/Soundex.html

Просто набрав следующий код, вы получите фонетическое значение вашей строки:

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

И тогда вы можете просто сделать это для двух строк и сравнить фонетические значения. Hava взгляните на следующую запись, если вы сравниваете две строки, потому что методы equals() просто черно-белые, и, возможно, вам нужно знать, сколько% соответствует:

Как сравнить почти похожие строки в Java? (Измерение расстояния по строкам)