Najbardziej efektywny sposób na wykonanie wyszukiwania fonetycznego

Question

Jaki jest najskuteczniejszy sposób wdrożenia wyszukiwania fonetycznego w C++ i/lub Java? Przez wyszukiwanie fonetyczne rozumiem zastępowanie samogłosek lub spółgłosek, które brzmią podobnie. Byłoby to szczególnie przydatne w przypadku nazw, ponieważ czasami nazwiska ludzi mają dziwne pisownię.

Myślę, że może zastąpić samogłoski i niektóre spółgłoski. Dobrym rozwiązaniem może być także specjalne przypadki, takie jak ciche E na końcu lub F i PH. Czy najlepiej byłoby użyć cstrings lub stringów w C++? Czy lepiej byłoby przechowywać kopię w pamięci z podstawionymi wartościami lub wywoływać funkcję za każdym razem, gdy czegoś szukamy?

Answer 1

Soundex wraz ze swoimi wariantami jest standardowym algorytmem do tego. Używa reguł fonetycznych do przekształcenia nazwy w kod alfanumeryczny. Nazwy z tym samym kodem są zgrupowane razem.

Jeśli chodzi o wdrażanie wyszukiwania, użyłbym struktury danych, która mapuje każdy kod soundex na listę nazw, które mają ten kod. W zależności od stosowanej struktury danych (tablica hash lub drzewo), wyszukiwanie może być wykonywane w czasie, który jest stały lub logarytmiczny w liczbie różnych kodów dźwiękowych.

Nie jestem pewien, co dokładnie masz na myśli przez cstring (Microsoft's CString?), Ale standardowa klasa std::string będzie doskonale pasować do tego problemu i byłaby moim preferowanym wyborem.

Answer 2

Poza Soundex znajdziesz również Metaphone lub Pokój Metaphone fonetyczne algorytm, który wydaje się być poprawa w wymowie angielskiej i jest całkiem nowy algorytm.

W przypadku niemieckiej wymowy używam "Kölner Phonetik".

Apache Commons Codec daje bardzo prosty Java realizacji tych podstawowych algorytmów (Soundex, Metaphone, ...) http://commons.apache.org/codec/ przykładowo patrz Javadoc dla soundex: http://commons.apache.org/codec/apidocs/org/apache/commons/codec/language/Soundex.html

Wystarczy wpisując poniższy kod, wartość fonetyczna Twojego ciągu:

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

A potem możesz zrobić to po prostu dla dwóch osób ciągi i porównać wartości fonetyczne. Hava spojrzenie na poniższym poście jeśli porównanie dwóch ciągów, ponieważ equals() metody jest tylko czarno-białe, a może chcesz wiedzieć, ile% jest dopasowanie:

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